First dent in the AES crypto algorithm

A team of researchers has discovered a first vulnerability in the AES encryption standard that shortens the algorithm's effective key length by two bits. This means that the usual key lengths of 128, 192 and 256 bits are reduced to 126, 190 and 254 bits.

Andrey Bogdanov from the Catholic University of Leuven, Christian Rechberger from ENS Paris and Dmitry Khovratovich from Microsoft Research, who discovered the hole, say that the attack has no practical relevance. Nevertheless, the findings are considered an important step in the research into the security of AES, a standard that was officially adopted in 2000.

Talking to The H's associates at heise Security, Bogdanov said that the developers of AES, Joan Daemen and Vincent Rijmen, have confirmed the vulnerability. Details of the attack were presented at the CRYPTO 2011 conference and can be downloaded from the Microsoft Research web site.

The researchers used a Meet-in-the-Middle attack, an approach that has so far mainly been used with hashing algorithms, and combined it with a "Biclique" attack. Their method allowed the researchers to compute the key from a single plain text/cipher text pair more quickly than by launching a brute force attack on the entire key space. It would take a cluster of a billion PCs, that can each try out a billion keys, ten million years to compute a 128-bit key. While shortening the key by two bits does reduce the required time to about three million years, it is still not enough for a practical attack.

(ehe)