Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds

AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the 2128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2176 and 2100 time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems.
In this talk we describe several attacks which can break with practical complexity variants of AES-256 whose number of rounds are comparable to that of AES-128. One of our attacks uses only two related keys and 239 time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2120 time).
Another attack can break a 10 round version of AES-256 in 245 time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys by these attacks, the fact that their hybrid (which combines the smaller number of rounds from AES-128 along with the larger key size from AES-256) can be broken with such a low complexity raises serious concern about the remaining safety margin offered by the AES family of cryptosystems.
This is joint work with Alex Biryukov, Nathan Keller, Dmitry Khovratovich, and Adi Shamir.

Speaker Details

Orr Dunkelman has received his Ph.D. in computer sceince from the Technion, Israel institute of technology, where he did his studies under Prof. Biham. Orr is the author of more than 40 international research papers in cryptography, and specificially, in cryptanalysis of symmetric key primitives. Orr has served as the program chair of the top venue for symmetric key cryptography, FSE 2009, and has served in committees of almost 30 international conferences. Orr is well known for his attacks on widely deployed ciphers, such as AES, A5/1 (used in GSM communications), KASUMI (used in the 3GPP communication protocols), IDEA (used in PGP), keeloq (used in cars as an anti-theft mechanism), etc. Finally, Orr is co-designer of the SHAvite-3 hash function that was selected to the second round of the SHA-3 competition held by NIST.

Date:
Speakers:
Orr Dunkelman
Affiliation:
Technion, Israel institute of technology,
    • Portrait of Jeff Running

      Jeff Running