8
$\begingroup$

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?

$\endgroup$
1
  • 8
    $\begingroup$ As long as the encryption used with k1 and k2 is secure Eve won't be able to learn kaes1. But there are two risks here: 1) Charlie will be able to decrypt messages sent before he joined the group 2) If Eve ever learns kaes1 she can decrypt all messages. I prefer shorter lived keys to limit the window of exposure. $\endgroup$ Aug 14, 2013 at 17:35

3 Answers 3

5
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ I think part of the question was if the two key exchanges leak any information about the aes key, not so much about multiple messages with the same aes key leaking the key. But in order to answer that, it depends highly on the key exchange protocol and the randomizers (e.g. if the same finite group is used or a new one for each key exchange). $\endgroup$
    – tylo
    Aug 15, 2013 at 12:31
3
$\begingroup$

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).

$\endgroup$
1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.