Related-key attacks on AES

Question

According to Wikipedia:

Related-key attacks can break AES-192 and AES-256 with complexities $2^{176}$ and $2^{99.5}$, respectively.

What are the requirements for these attacks (i.e how many related keys, what should the relationship between the keys be)? Optionally, how do the attacks work in summary?

Answer 1

The attack is described in the article Related-key Cryptanalysis of the Full AES-192 and AES-256 and applies in the following situation:

• There is a key owner; the key is $K_A$ and the attacker tries to guess it.
• 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).
• Then, the attacker can make the key owner encrypt and decrypt arbitrary blocks -- that the attacker chooses -- with the keys $K_A$, $K_B$, $K_C$ and $K_D$. The key owner will accept to process up to $2^{99.5}$ blocks (that's 16-byte blocks, hence a grand total of about 14 thousands of billions of billions of gigabytes).
• Finally, the attacker has access to some storage space of about one million of billions of gigabytes.

Under those conditions, the attacker can guess $K_A$. For details, see the article.

The name "related-key attack" comes from the involvement of several distinct keys, linked together by known relations. Resistance to such attacks were not part of the evaluation criteria during the AES competition (when Rijndael was chosen as AES). Related-key attacks are not very practical (even if the $2^{99.5}$ chosen plaintext/ciphertext value was not ludicrously large, the conditions on the four keys would still make the attack only theoretical).