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
[ Cryptology ePrint archive ]