Is there any correlation in between two AES with a key differ only by one bit? (ECB mode)

Question

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?

Answer 1

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.