Biclique cryptanalysis of the full AES

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.

Publications

Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger

Biclique cryptanalysis of the full AES (PDF, to appear at ASIACRYPT 2011)

Cryptology ePrint entry

Media

Contact - Dmitry Khovratovich, dkhovrat@microsoft.com

Press release by KU Leuven

Bing News Feed