Cryptology ePrint Archive: Report 2009/374

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

Alex Biryukov and Orr Dunkelman and Nathan Keller and Dmitry Khovratovich and Adi Shamir

Abstract: 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 $2^{128}$ complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require $2^{176}$ and $2^{119}$ 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 paper we describe several attacks which can break {\it 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 $2^{39}$ 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 $2^{120}$ time). Another attack can break a 10 round version of AES-256 in $2^{45}$ time, but it uses a stronger type of {\it related subkey attack} (the best previous attack on this variant required 64 related keys and $2^{172}$ time). While neither AES-128 nor AES-256 can be directly broken 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.

Category / Keywords: secret-key cryptography / AES, cryptanalysis, related key attacks, practical attacks

Date: received 29 Jul 2009, last revised 19 Aug 2009

Contact author: adi shamir at weizmann ac il

Available formats: PDF | BibTeX Citation

Version: 20090819:164811 (All versions of this report)

Discussion forum: Show discussion | Start new discussion