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.