Welcome to the resource topic for
**2009/241**

**Title:**

Distinguisher and Related-Key Attack on the Full AES-256 (Extended Version)

**Authors:**
Alex Biryukov, Dmitry Khovratovich, Ivica Nikolić

**Abstract:**

In this paper we construct a chosen-key distinguisher and a related-key attack on the full 256-bit key AES. We define a notion of {\em differential q-multicollision} and show that for AES-256 q-multicollisions can be constructed in time q\cdot 2^{67} and with negligible memory, while we prove that the same task for an ideal cipher of the same block size would require at least O(q\cdot 2^{\frac{q-1}{q+1}128}) time. Using similar approach and with the same complexity we can also construct q-pseudo collisions for AES-256 in Davies-Meyer hashing mode, a scheme which is provably secure in the ideal-cipher model. We have also computed partial q-multicollisions in time q\cdot 2^{37} on a PC to verify our results. These results show that AES-256 can not model an ideal cipher in theoretical constructions. Finally, we extend our results to find the first publicly known attack on the full 14-round AES-256: a related-key distinguisher which works for one out of every 2^{35} keys with 2^{120} data and time complexity and negligible memory. This distinguisher is translated into a key-recovery attack with total complexity of 2^{131} time and 2^{65} memory.

**ePrint:**
https://eprint.iacr.org/2009/241

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .