Cryptology ePrint Archive: Report 2009/241

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