Paper 2011/274

A Splice-and-Cut Cryptanalysis of the AES

Dmitry Khovratovich and Christian Rechberger

Abstract

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 256-bit key variant 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 9 out of 14 rounds of AES-256 with computational complexity 2^{253.1} and success rate 1. - The first key recovery attacks on 8 out of 10 rounds of AES-128. The best attack has computational complexity 2^{124.8} and success rate 0.63. - The first combination of a non-random property and an algorithm that allows to distinguish the full 10-round AES-128 from an ideal cipher in a non-trivial way. This may be interpreted as a weak deviation from an ideal behavior in a model where the adversary is allowed to choose the key, and has some relevance when AES-128 is used in a compression function of a cryptographic hash function. In contrast to most shortcut attacks on AES variants, we do not need any related-keys. As our attacks are of high complexity, yet practically verified to large extent, they do not threaten the practical use of AES-128 or AES-256 in any way.