Another New AES Attack

Jeremy A. Hansen writes "Bruce Schneier gives us an update on some ongoing cryptanalysis of AES. 'Over the past couple of months, there have been two new cryptanalysis papers on AES. The attacks presented in the paper are not practical — they're far too complex, they're related-key attacks, and they're against larger-key versions and not the 128-bit version that most implementations use — but they are impressive pieces of work all the same. This new attack, by Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, and Adi Shamir, is much more devastating. It is a completely practical attack against ten-round AES-256.' While ten-round AES-256 is not actually used anywhere, Schneier goes on to explain why this shakes some of the cryptology community's assumptions about the security margins of AES."

Comments

There is no such thing as ten-round AES-256

[Anonymous Coward]

AES-256 by definition has 14 rounds. AES-128 has ten rounds. Ten rounds were determined by the designer to give enough security to support a 128 bit keyspace. Not 256 bits. For 256 bits, the designers specified 14 rounds.

AES is based on a cipher called Rijndael, whose number of rounds, number of key bits, and maybe block size (not sure of the last) can be set arbitrarily. So there is such a cipher as 10-round Rijndael-256. For that matter, there is even 1-round Rijndael-256, which is of course insecure. And there's 1000-round Rijndael-128, which is secure but dirt slow. The AES standardization process used Rijndael parameter settings which the designers claimed to be as fast as possible while still being secure to the strength specified by the key size. That is, the used the minimum sufficiently-secure number of rounds for the key size.

Got that? For AES-128, the designers said 10 rounds was enough. For AES-256, this new research showed that 10 rounds is not enough, which is what the designers pretty much said all along, though nobody had a specific proof of that until now.

Re:There is no such thing as ten-round AES-256

[Ex-Linux-Fanboy]

To be more precise, Rijndael has two parameters:

• Key size, which can be 128, 160, 192, 224, or 256 bits in size
• Block size, which can also be 128, 160, 192, 224, and 256 bites in size

This means Rijndael is a set of 25 different ciphers; AES is a subset of three of these ciphers. The number of rounds is derived from the maximum of these two parameters; for a 256-bit key and 128-bit block, it is defined as 14 rounds. Fewer rounds means we're not analyzing Rijndael, but a reduced-round Rijndael variant.

Related key attacks, by and large, are only an issue with "make a hash out of a block cipher" constructions. I don't know offhand if this is an issue with Whirlpool, a hash construction using an AES variant; as I recall, some changes were made to the key schedule of Whirlpool.

Re:There is no such thing as ten-round AES-256

[evanbd]

Reduced-rounds attacks are a standard cryptographic technique. You start by breaking a reduced strength version of the cipher with a completely impractical attack that's marginally better than brute force. Then someone comes along and observes that they can improve your attack to more rounds or shorter time. Then that repeats a few times. Eventually, the cipher is broken.

No, they haven't broken AES. However, this is a step along the way. If the designers of AES had known that there was a good attack against the 10-round version, they wouldn't have recommended 14 rounds -- standard practice is to include a larger safety factor than that. This is a big deal, not because you can now break AES, but because the attacks are much closer to doing that than previously thought. Hence, the recommendation by Schneier to move to 28 rounds -- improve the safety factor. Attacks always get better, never worse. It's possible (though unlikely) that there are unpublished attacks on AES known by some organizations -- and the closer to a real break the publicly known attacks are, then the more plausible that scenario becomes. Attacks that get this close and weren't anticipated by the cipher designers are scary things.

Also, this is a related-key attack -- meaning the attacker needs two keys that are related somehow and the same piece of plaintext encrypted with both. If the implementation of AES that you use does a good job of selecting a truly random key, then the attacker can't implement this attack because he can't get you to use the requisite pair of related keys. That doesn't mean it isn't a valid attack, just that it's an attack that can be defended against. Again, the biggest worry is that someone will take this attack and realize how to improve upon it to make an attack that's even better.

Re:There is no such thing as ten-round AES-256

[Joce640k]

AES-256 and AES-192 are really AES-128 in disguise. They were created only to meet NIST requirements for three different key sizes, not from any practical security reasons (128 bits is definitely enough to prevent brute-force cracking).

The AES algorithm needs 128 bits of key for each pass through the encryption loop.

For AES-256 they select 128 bits from the 256-bit key for each round. Some of the key bits don't make it into the encryption loop until quite late in the process so in the final output they've only had a few rounds of encryption and can be brute-forced with much less than 2^256 effort. When you have some of the key you can go back and get a few more bits, and so on...

nb. The designers weren't stupid, they designed AES-256 to completely lose the key and this attack doesn't work against all twelve rounds of AES-256. The surprise is that somebody managed to extract the key out of a ten round version. This was unexpected.

nb. In AES-128 *all* of the key bits have been through *all* the rounds of encryption so inferring anything about the key by looking at the output is much more difficult (and hopefully impossible).

Re:There is no such thing as ten-round AES-256

[slackergod]

Another (somewhat less-well known) thing that can be done is to use OAEP+ (http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding) to encrypt the datablocks that you're transmitting. The link is to OAEP but OAEP+ is probably what you'd want to use with AES... I don't have a link handy, and the basic principle of the two is the same...

The OAEP algorithm scrambles your data chunks by XORing your plaintext with randomly generated bits, but done in a way that's recoverable IF and ONLY IF you have the entire ciphertext decoded (designed for RSA, but can apply to AES). This means that the same key+plaintext will always result in different ciphertext, and also means that in order to get any useful bits of key/plaintext information, the attacker must get them all, or they're just guessing as to which set of random bits OAEP used (and it generally puts 128 bits worth in).

While the actual OAEP protocol is a block-level action, and the safe version adds 128 bits of randomness (and thus size), the general idea can be modified to be as cheap or expensive as you want... the idea in general makes many asymetric ciphers MUCH more secure.

AES crack

[mwvdlee]

So I guess this is an AES-hole?

Practical?

[GigsVT]

I'm not sure how practical it is for any "programmer on the streets" to pay attention to this sort of thing.

Time and again it's the stupid stuff that gets us... broken implementations, not broken algorithims. Like the null terminated strings in SSL certs, or the Debian ssh keys being one out of only 64k possible.

I say this because I have to constantly hear stupid stuff from fellow programmers like "MD5 is broken!!!11". They make design choices based off these unlikely attacks, without fully understanding the real nature of this stuff.

Re:Practical?

[UltimApe]

I've seen real world attacks against md5 where being used as a checksum/verification. Malicious individuals injected code, but the md5 didn't change. http://en.wikipedia.org/wiki/MD5#Vulnerability We researched it in a security course I took recently.

Re:That's nice...makes you wonder...

[lorenlal]

Like posting here?

The beauty of public cryptographic algorithms

[al0ha]

The best minds in the world work on cracking them and come up with theoretical proofs of a weakness which ultimately prove to everyone, beyond the shadow of a doubt, the security of the algorithm. Too bad many corporations don't understand and try to create closed cryptographic algorithms which, in almost every case, turn out to be very lame.

Re:The beauty of public cryptographic algorithms

[natehoy]

Like one of my bosses once said, years ago, "If we implement industry standards in our processes, then we'll be doing things just like everyone else does! Where's the competitive advantage in THAT?"

Re:That's nice...makes you wonder...

[autocracy]

Roughly quoting Bruce from a few hours ago at DEFCON: "Cryptographers need to write papers... the best way to write something is to break something. Nobody wants to read about all the work you did to setup something... they want to know how you tore it apart. That's how you get cred before you submit an algorithm."