Reference : Distinguisher and Related-Key Attack on the Full AES-256
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
http://hdl.handle.net/10993/17509
Distinguisher and Related-Key Attack on the Full AES-256
English
Biryukov, Alex mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Khovratovich, Dmitry mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Nikolic, Ivica [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
2009
Advances in Cryptology - CRYPTO
Springer
231-249
Yes
International
978-3-642-03355-1
Advances in Cryptology - CRYPTO
August 16-20
Santa Barbara
CA
[en] AES ; related-key attack ; chosen key distinguisher ; Davies-Meyer ; ideal cipher
[en] 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·267 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·237 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.
http://hdl.handle.net/10993/17509
10.1007/978-3-642-03356-8_14

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
AES-related-key-break.pdfPublisher postprint334.69 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.