Welcome to the resource topic for 2009/241
Title:
Distinguisher and Related-Key Attack on the Full AES-256 (Extended Version)
Authors: Alex Biryukov, Dmitry Khovratovich, 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.
ePrint: https://eprint.iacr.org/2009/241
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .