Vulnerabilities if encrypting the same data with 2 different keys

Question

Let's say that Alice and Bob complete a key exchange and then Alice uses that key k1 to encrypt a 256-bit key kaes1 and sends it to Bob. From there, Alice and Bob exchange a lot of messages back and forth, using AES-256 to symmetrically encrypt the data with the key kaes1.

Then, Charlie comes along and wants to participate, so Alice and Charlie complete a key exchange and Alice then uses that key k2 to encrypt the same original kaes1 and sends it over to Charlie. From there, Alice and Bob and Charlie now exchange a bunch of messages symmetrically encrypted with AES-256.

Eve has been listening in this whole time, and she has all the data, but none of the keys. Does Eve gain an advantage if she knows that kaes1 was the payload for 2 different messages encrypted with 2 different keys k1 and k2?

Answer 1

You basically ask the following question: Is there a weakness anywhere if I encrypt the same message independently with 2 different keys? To answer this, please consider the following:

1. The cipher text coming from a perfect encryption algorithm is indistinguishable from random data.
2. Practical encryption algorithms have some flaws, leading to ciphertexts that are not truely random.
3. Any hint in the encryption process (including implementation flaw, input data processing, ciphertext output etc) that would provide some statistical bias away from a "chaotic" process flow may help an attacker.
4. It is well established that using the same key to encrypt different messages may provide some hints regarding the encryption process. Looking from a "system" perspective, this is due to a strong bias in the input variables - the encryption key has no random differential value any more.
5. In your case, different keys but same message also have an input factor with no random differential value, namely the plaintext. So yes, this may provide some cryptanalysis hints to Eve.
6. The practical question would be - how strong is this hint? should I be concerned? well, if your are a researcher, then you can write a paper on this and present it in some conference. But if you are talking about real security in the field, I would say that this is still secure: AES 256 is well known cipher, and the attacks based on (4) above may reduce its strengh from 256 bit to several notches below that (and only if you encrypt insane amount of messages with the same key), but still it stays resistant (read: infeasible) now and in the foreseeable future to any breakage due to these input biases - especially when you talk about a fairly limited number of key sharing in your application.

Answer 2

No. This does not help Eve the eavesdropper. AES is secure against known-plaintext attacks, so knowing that the same plaintext (kaes1) was encrypted under two different keys (k1 and k2) does not help her to recover any of the keys or break of the traffic.

Of course, it still might not be a good idea to do what you suggested: there might be other reasons not to do that (as CodesInChaos explains succinctly).

Answer 3

Yes, this does help Eve, in the sense that it reduces her costs below what you might have naively expected of a $b$-bit key. Fortunately, this help is not enough to matter for AES-256.

This is the multi-target setting. The best generic attacks to find the first of $t$ targets parallelized $t^2$ ways cost an expected ${\sim}2^b/t$ evaluations of the cipher and run in expected time for ${\sim}2^b/t^3$ sequential evaluations of the block cipher. This is much cheaper than the naive estimate of an expected ${\sim}2^b$ evaluations of the block cipher, and much faster than the naive parallelization.

(This is why AES-128 should not be considered to meet the standard 128-bit security level—you should use AES-192 or AES-256 if you want that, or just use NaCl crypto_secretbox_xsalsa20poly1305 instead and save yourself the trouble of auditing your software stack all the way to the assembly to confirm you're not leaking secrets through cache-timing side channels.)