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

*Alex Biryukov and Dmitry Khovratovich and 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.

**Category / Keywords: **secret-key cryptography / AES, related-key attack, chosen key distinguisher, Davies-Meyer, ideal cipher

**Publication Info: **A shortened version has been accepted to CRYPTO 2009

**Date: **received 28 May 2009, last revised 10 Aug 2009

**Contact author: **khovratovich at gmail com

**Available format(s): **PDF | BibTeX Citation

**Note: **In the extended version we describe in details how we constructed the differential trails and give more information on the triangulation algorithm. We also discuss consequences and relevance of our attacks.

**Version: **20090810:075245 (All versions of this report)

**Short URL: **ia.cr/2009/241

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]