Encrypting data with two separate keys

Question

Goal

We want to find the most secure way to encrypt message of arbitrary length M with AES such that the recipient can only decrypt if they have both AES keys K1 and K2.

Preconditions:

• AES keys K1 and K2 are independent and randomly generated, 256-bit keys
• Assume we'll be running AES-GCM
• Key exchange for the valid recipient has already be performed
• Performance is not a concern (operation is performed less than once a couple of seconds)

Options (I could think of)

Option 1: XOR

Derive a new key K3 = K1 ^ K2 and perform encryption on M using K3.

Given that there are no known weak keys or known weaknesses in AES, only practical way for deriving K3 is by having pre-existing knowledge of K1 and K2.

Option 2: KDF

Compute $K_1\mathbin\|K_2$ (concatenation of the two keys) and feed the result to a KDF (perhaps HMAC based KDF) and use the resulting key as the AES key to encrypt M. I don't think this is significantly different from Option 1, but I'm listing it as an option anyway.

Option 3: Encrypt twice

Perform two layers of encryption:

C1 = Encrypt(M, K1)
C2 = Encrypt(C1, K2)

Send C2 as the cipher text. My intuition is that this should be no less secure than Option 1.

Additional Information/Clarifications

This question is gear towards the two keys being used as something similar to the cryptographic equivalent of "Multi-factor Authentication". In particular, the user has to obtain two different keys (through different means) before being able to decrypt the data.

This question could be extended to the case where there are N keys. The constraint is that all N keys will always be required to decrypt the data.

Answer 1

I would say that all of them are valid options, with the security differences they might have negligible. So I focused on other properties of the approaches:

Option 1: XOR

I think the most interesting property here is the malleability that gives us the XOR function. If I'm a keyholder under this chema, I could give n keys which XOR to my half to my n children, and their keys combined will be as good as mine.

Similarly, it the requisites went from 2-people to 3-people (such as including a new partner in the business), they could each provide a random half-key to combine with their now-new-half.

It also has the property of being commutative. This is silly from a cryptographic and technological point of view, but if you are giving two keys to two people, one might think to be more important to have the "first" key, or feel hurted on their big ego for only being given the "second" key. Here, both keys are equal rank, their order doesn't matter at all.

Option 2: KDF

This woud be similar to the above, but not allowing you such malleability (which you may consider good or bad).

You may want to combine them in lexicographical order, so that it doesn't matter the order in which they are provided. For the reasons provided above and less user errors by not being possible to provide them in an order it doesn't work.

Option 3: Encrypt twice

This option would be slower, although just doing two layers of encryption would not be a noticeable hit. You should perhaps be careful to do both things "at once" or with pipes, not using intermediate temporary files that might end up recovered. Although you would still have the same concern with the final decrypted item.

This solution would be subject to a Meet-in-the-middle attack. I don't think this would actually be a realistic concern, since you would still need to break AES.

A new keyholder could be added by encrypting the existing ciphertext with the new key.

Same comment as above about setting an order would be applicable.

Option 4: Split the key in two

Just for completeness, I'm adding the trivial solution of, instead of giving 128 or 256 bit keys to each of them, directly providing half the key (64/128 bit keys) to each one. This means each key is half the size, with no benefit over the other solutions, so I wouldn't recommend it.