You are on a submarine and there is an encrypted message that you want to read. Two people must use their keys at the same time in order to obtain the plain text. What is best cryptographic primitive to use? Are the following two implementations suitable?
plain_text=decrypt(Key1 XOR key2,ciper_text,IV)
plain_text=decrypt(Key1,decrypt(key2,ciper_text,IV2),IV1)
(Assume AES256-CMAC if it matters to you.)
XOR'ing the keys, while the simplist method, may not be the best. I don't think the resulting key would be random enough - if someone with key 1 was able to get their hands on the resulting key they may be able to derive key 2.
To throw further complexity into the mix, perhaps some kind of one-time pad would be a good plan. It's probably not a good idea to re-use keys for this kind of system :)
Here's an example of when reusing keys caused problems:
http://en.wikipedia.org/wiki/Venona_project
UPDATE
I've just blown the dust off my copy of Bruce Schneier's excellent Applied Cryptography, and taken a look at section 3.6 Secret Splitting. It's a different scenario, but he suggests that simply XOR'ing keys with a message is secure:
Here’s a protocol in which Trent can split a message between Alice and Bob:
(1) Trent generates a random-bit string, R, the same length as the message, M.
(2) Trent XORs M with R to generate S.
M ⊕ R = S
(3) Trent gives R to Alice and S to Bob.
Note he says nothing of whether this might be suitable for a guarding a missile launch system ;)
With this, I don't see how you could implement the requirement that any two people of sufficient rank - together - will be able to read the message...
Other than that: depending on the underlying encryption algorithm, having one half the XOR'ed key may allow one to derive parts of the complete key, significantly weakening the protection.
Then again, IANAC :)
The second option:
plain_text=decrypt(Key1,decrypt(key2,ciper_text,IV2),IV1)
doesn't follow the requirement that both parties must use their keys at the same time. Key2 must be used before Key1, but once that happens, the first party (the possessor of Key1) can wait to decipher until a time of her choosing, leaving the second party out of the loop. This may or may not be a problem for the application.
As Cocowalla's Schneier quote suggests, XOR works, unless one of the parties can get the combined key (the decryptor may be able to keep this secret) and the other key has other uses. If the keys aren't statistically independent, the speed of XOR means the key combination step is vulnerable to guided brute-forcing (decrypt is still a bottleneck). If the keys are independent, then there's no need to figure out either partial key, nor does knowing one partial key help figure out the combined key, so a brute-force attack may as well target the combined key and ignore the parts. As caf mentions, figuring the other partial key is moot because it requires the combined key; also, you can only fire the nukes once. If one key is only used in combination with the other key (and we don't reuse passwords for different systems, right?), XOR is safe.
There are a couple of cryptographic systems that allow k-out-of-n keys to decrypt a message when used simultaneously, but I can't remember the term for them off the top of my head, and my copy of Applied Cryptography isn't at hand.
Edit: thanks to Cocowalla, the name of the scheme is "(m,n) threshold scheme". For a visual example, read "Visual Cryptography and Bit-Plane Complexity Segmentation" by Daniel Stoleru, published in Dr. Dobbs. Visual cryptography was created by Naor and Shamir, and presented at EUROCRYPT '94 (according to Doug Stinson).
Wikipedia lists still more examples of k-out-of-n secret sharing: using n points, where the secret is an k-1 degree polynomial; using k k-hyperplanes, where the secret is the point of intersection.
By XORing the keys you're guaranteeing that every single bit in Key1 can potentially be modified by every single bit in Key2 (and vice-versa). It means that the holder of Key1 has no way of calculating either Key2 or the result of XORing Key1/Key2.
Another way of stating this is that the holder of Key1 would have to brute force every single possible combination of bits to exhaust the available keyspace. The fact that he already holds one of the keys doesnt help him at all.
There are other ways of combining two keys together, but a simple XOR is all that is required when the keys are the same length.
XORing two randomly generated keys together to obtain the final secret is certainly secure. The general form of this is known as 'secret sharing', and there are secure algorithms that allow you to generate 'm of n' schemes, where you generate n shares, and any m are sufficient to deduce the original key.
The best known scheme is Shamir's Secret Sharing, and involves generating a random m-1 degree polynomial with the key as the constant, then sampling it at n locations, and giving those to the individuals as key shares.
Before thinking about solutions, you probably want to think about the requirements. In the given scenario, where you have two persons that are both needed to decrypt the message it is reasonable to require that
After all you want to avoid that one person just chooses a random ciphertext, pretends that this just came in, sees the key of the other person, and then notices that the ciphertext must have been a hoax. This requirement makes the decryption with option 1 difficult. Since you are using a MAC you probably also want that
This seems to rule out option 2. After all how can the holder of Key2 know that the holder of Key1 decrypted correctlty and did not just replace the legitimate plaintext with one of his choosing.
I must admit that I don't know a good solution for the scenario that you describe. A potential scheme might look like this: The ciphertext is tuple c1, c2, d1, d2, where
c1 = EncryptAndMAC(Key1, Share1)
d1 = MAC(Key2, hash(Share1))
c2 = EncryptAndMAC(Key2, Share2)
d2 = MAC(Key1, Share2)
message = Share1 XOR Share2
Now both keys are needed to find the message, both parties can decrypt their shares independently without having to share their keys, and both parties can verify that the other party decrypted correctly. Of course, this is an ad-hoc protocol, so it is likely that I missed something.