4
$\begingroup$

Given two AES (128bit, ECB mode) with almost equal keys $k_1,k_2$: 127 of the 128 key bits are equal. Is there any correlation in between the ciphers they build?

$$AES_1(m_i) = c_i$$ $$AES_2(m_i) = d_i$$

Would it be different to two keys differ by 64bit? by 128bit? Or the same key but shifted by $n$ bit?

E.g. An adversary found some correlation in between the target AES mapping and another he knows the key of. Does this help him anything for deriving the key of the target AES?

$\endgroup$
1
5
$\begingroup$

This is called a related-key attack. There are many types of related-key attacks and the AES key schedule is vulnerable to some of them, but not the one you describe. From the linked answer:

  • The key owner can somehow be persuaded to compute three other keys $K_B$, $K_C$ and $K_D$, from $K_A$, using a specific derivation algorithm ($K_B$ is equal to $K_A$ XORed with a constant that the attacker chooses; $K_C$ and $K_D$ use a more complex but equally deterministic derivation algorithm).

There are some ciphers which would be vulnerable to such a trivial related-key attack as the one you describe. The TEA block cipher has equivalent keys. Each key has two others which select the same permutation. The RC4 stream cipher is even more vulnerable. When used multiple times with keys which differ by a small number of bits, it becomes possible to calculate the key.

Even though AES is not vulnerable to such a trivial related-key attack, it is still a good idea to re-key it with independent keys (e.g. by passing a master key through HKDF), for two primary reasons:

  1. So the security of your scheme is not dependent on the particular cipher being used.
  2. To protect from future attacks against AES' relatively simple key schedule.
$\endgroup$
2
  • $\begingroup$ does the constant the attacker chooses need to have some special properties? E.g. if you know the key is different at a specific key position the constant could be 00..010..00. For my use case the keys are know. It should only serve as pseudo random number generator with special properties. Computations already done with AES1 should not simplify computations done with AES2. $\endgroup$ – J. Doe Mar 21 at 23:11
  • $\begingroup$ @J.Doe Yes, but XORing with the constant is not enough to perform that attack. See section 5.1 of Related-key Cryptanalysis of the Full AES-192and AES-256. Although AES should be safe from "simple" related keys (you won't be generating those related keys by accident), it's still a better idea to use HKDF or even just a hash of the master key + counter/identifier and feed that result into AES. $\endgroup$ – forest Mar 21 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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