Paper 2009/241

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

Alex Biryukov, 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.

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. A shortened version has been accepted to CRYPTO 2009
Keywords
AESrelated-key attackchosen key distinguisherDavies-Meyerideal cipher
Contact author(s)
khovratovich @ gmail com
History
2009-08-10: revised
2009-05-30: received
See all versions
Short URL
https://ia.cr/2009/241
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/241,
      author = {Alex Biryukov and Dmitry Khovratovich and Ivica Nikolić},
      title = {Distinguisher and Related-Key Attack on the Full AES-256 (Extended Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2009/241},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/241}},
      url = {https://eprint.iacr.org/2009/241}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.