A group of researchers have developed a new attack that enables them to find AES keys several times faster than was previously thought possible, reducing the complexity of finding the keys on AES-128, AES-192 and AES-256. However, the attack does not pose any practical threat to currently deployed systems that use the AES encryption algorithm, the researchers said.
The new attack, called a biclique attack, was developed by a team of researchers from Microsoft and a Belgian university and is considered to be the first practical attack capable of finding AES-128 keys faster than a brute force search. There are several different versions of AES–which is the current NIST encryption standard–based on the length of the encryption key. AES-128 is probably the most widely used, and while there have been other attacks against AES-256 in recent years, the new work by the Microsoft and Belgian researchers is the first to put a real dent in AES-128.
Past research on the Advanced Encryption Standard have typically involved related-key attacks, but the new paper, “Biclique Cryptanalysis of the Full AES”, does not employ that kind of attack.
“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 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,” the authors wrote in the paper, which was released this week.
The attack, developed by Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger, reduces the effectiveness of AES-128 by about three bits, down to about 125, experts say. They estimate that their attack is roughly three to five times more effective than a brute-force key search.
“The use of bicliques in combination with the technique of matching with precomputation, results in a surprisingly low recomputation in the innermost loop, varying from about 1/3 to approximately 1/5 of the cipher depending on the key size, while having data complexities of 288, 280 and 240 plaintext-ciphertext pairs, respectively. Arguably no known generic approach to key recovery allows for that gain. We notice that the data complexity of key recovery can be significantly reduced by sacrificing only a small factor of computational advantage,” the authors wrote.
Cryptographer Bruce Schneier said at the time of the 2009 attack on AES-256 that 128-bit AES was still strong enough for most applications, and he reiterated that advice in the wake of the new attack.
“Cryptography is all about safety margins. If you can break n round of a cipher, you design it with 2n or 3n
rounds. What we’re learning is that the safety margin of AES is much
less than previously believed. And while there is no reason to scrap AES
in favor of another algorithm, NST should increase the number of rounds
of all three AES variants. At this point, I suggest AES-128 at 16
rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Or maybe even
more; we don’t want to be revising the standard again and again,” Schneier said on his blog.
