A group of cryptographers has devised a new attack against AES, the de facto standard encryption algorithm, that enables them to recover an encryption key in far less time than had been possible before. The attack can recover an AES-256 key in a small enough amount of time to make the method practical for common attackers, leading some experts to recommend that users stop using AES-256 immediately.
The attack was devised by a group that includes Adi Shamir, one of the designers of the RSA algorithm, as well as Alex Biryukov, Orr Dunkelman, Nathan Keller and Dmitry Khovratovich. Their method is described in a new paper due to be published soon, and is designed specifically to attack AES-256 at nine and 10 rounds. Bruce Schneier has seen a draft of the paper and has some of the details. From the abstract :
In this paper we describe several attacks which can break with practical complexity variants of AES-256 whose number of rounds are comparable to that of AES-128. One of our attacks uses only two related keys and 239 time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2120 time). Another attack can break a 10 round version of AES-256 in 245 time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys and 2172 time).
AES is the current NIST standard for encryption and is widely implemented at various key lengths. Schneier said that while there’s no reason to panic right now, this attack is by far the most impressive to date against AES, and recommends that people not use AES-256.
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 — now, before there is a reason to panic. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Of maybe even more; we don’t want to be revising the standard again and again.
And, even more strongly, I suggest that people don’t use AES-256. AES-128 provides more than enough security margin for the foreseeable future.
There have been a number of other similar attacks against AES, but none has proven to be as practical as this new one.
