Biclique Cryptanalysis of the Full AES

http://research.microsoft.com/en-us/projects/cryptanalysis/aes.aspx

Since Rijndael was chosen as the Advanced Encryption Standard, improving upon 7-round attacks on the 128-bit key variant or upon 8-round attacks on the 192/256-bit key variants has been one of the most difficult challenges in the cryptanalysis of block ciphers for more than a decade. In this paper we present a novel technique of block cipher cryptanalysis with bicliques, which leads to the following results:

• The first key recovery attack on the full AES-128 with computational complexity 2126.1.
• The first key recovery attack on the full AES-192 with computational complexity 2189.7.
• The first key recovery attack on the full AES-256 with computational complexity 2254.4.
• Attacks with lower complexity on the reduced-round versions of AES not considered before, including an attack on 8-round AES-128 with complexity 2124.9.
• Preimage attacks on compression functions based on the full AES versions.

In contrast to most shortcut attacks on AES variants, we do not need to assume any related-keys. Most of our attacks only need a very small part of the codebook and have small memory requirements, and are practically verified to a large extent. As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

-----------------------------------------------------------------------------------

http://research.microsoft.com/en-us/projects/cryptanalysis/aesbc.pdf

The biclique cryptanalysis successfully applies to all full versions of AES and compared to brute-force provides an advantage of about a factor 3 to 5, depending on the version. Also, it yields advantages of up to factor 15 for the key recovery of round-reduced AES variants with numbers of rounds higher than those cryptanalyed before.