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 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 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 · 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.
in REF with q = 2.
Distinguisher and Related-Key Attack on the Full AES-256
Advances in Cryptology – CRYPTO 2009, Proceedings, volume 5677 of Lecture Notes in Computer Science
Computer Science