Distinguisher and Related-Key Attack on the Full AES-256

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

differential q

-multicollision

and show that for AES-256

q

-multicollisions can be constructed in time

q

·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 mode, a scheme which is provably secure in the ideal-cipher model. We have also computed partial

q

-multicollisions in time

q

·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.