[cryptography] Single-key key recovery for full AES

Jack Lloyd lloyd at randombit.net
Wed Aug 17 11:52:28 EDT 2011


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

I'm wondering how easily the new preimage attack they describe (on AES
in Davies-Meyer) can be applied to any of the AES-based SHA-3
candidates.

Abstract follows

"""
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 2^126.1
  - The first key recovery attack on the full AES-192 with computational complexity 2^189.7
  - The first key recovery attack on the full AES-256 with computational complexity 2^254.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 2^124.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 related-keys.  Most of our attacks only need a very small
part of the codebook and have small memory require- ments, 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.
"""



More information about the cryptography mailing list