New Attack on AES

There’s a new cryptanalytic attack on AES that is better than brute force:

Abstract. In this paper we present two related-key attacks on the full AES. For AES-256 we show the first key recovery attack that works for all the keys and has complexity 2119, while the recent attack by Biryukov-Khovratovich-Nikolic works for a weak key class and has higher complexity. The second attack is the first cryptanalysis of the full AES-192. Both our attacks are boomerang attacks, which are based on the recent idea of finding local collisions in block ciphers and enhanced with the boomerang switching techniques to gain free rounds in the middle.

In an e-mail, the authors wrote:

We also expect that a careful analysis may reduce the complexities. As a preliminary result, we think that the complexity of the attack on AES-256 can be lowered from 2119 to about 2110.5 data and time.

We believe that these results may shed a new light on the design of the key-schedules of block ciphers, but they pose no immediate threat for the real world applications that use AES.

Agreed. While this attack is better than brute force—and some cryptographers will describe the algorithm as “broken” because of it—it is still far, far beyond our capabilities of computation. The attack is, and probably forever will be, theoretical. But remember: attacks always get better, they never get worse. Others will continue to improve on these numbers. While there’s no reason to panic, no reason to stop using AES, no reason to insist that NIST choose another encryption standard, this will certainly be a problem for some of the AES-based SHA-3 candidate hash functions.

EDITED TO ADD (7/14): An FAQ.

Tags: , , , , , , ,

Posted on July 1, 2009 at 11:49 AM • 41 Comments

Comments

Timmy303 • July 1, 2009 1:53 PM

Weren’t there structural weaknesses evident in Rijndael and the ciphers it was modeled after that were discussed during the NIST competition nine years ago? I also remember somebody finding key schedule weaknesses in the cipher around that time that were demonstrable in reduced-round variants. I refuse to believe that anyone is surprised by this, but I’m sure there will be plenty of chicken-little-ing.

Bruce Schneier • July 1, 2009 2:06 PM

“Bruce, does this strengthen the case for your hash candidate, skein?”

Maybe. It puts a cloud over some of the SHA-3 candidates that used AES directly, rather than piece parts of AES. But it’s unclear how this attack generalizes, so I don’t know for sure.

RH • July 1, 2009 2:30 PM

“…attacks always get better, they never get worse.”

This always amazes me. Attacks keep getting more and more vicious, yet the crypto community keeps comming up with more resilient algorithms. It makes me wonder how quickly a modern cryptographer could break older algorithms using equipment of the day. If we’d had people like Bruce around in WWII, would Enigma have fallen faster thanks to the improved techniques we’ve learend?

Thomas Peyrin • July 1, 2009 2:55 PM

Note that the attack doesn’t apply on AES-128, which is the most used primitive for AES-based hash functions submitted to the NIST competition.

Tim • July 1, 2009 6:28 PM

What should the complexity be? 2^256? And what can realistically be brute forced at the moment?

Randall Farmer • July 1, 2009 7:37 PM

And, importantly, it’s a related-key attack. SSH, SSL, etc. don’t allow related-key queries, at least not in a way that would make most related-key attacks straightforward. The attack is important if the AES key schedule is used in a hash function, as Bruce says, and it’s interesting if it leads to other, non-related-key attacks.

@Ariel: Seems unlikely that AES-256 would be weaker than AES-128 in real applications.

And as a commenter at your ycombinator.com link says, don’t panic. Academically “broken” algorithms can still be fine in practice. (On the other hand, they can also be MD5.) More importantly, we’re bitten every day by much less exciting security bugs that have nothing to do with cutting-edge algorithm research.

caf • July 1, 2009 8:04 PM

This is a good example of why the TLS IETF working group’s aversion to including more well-tested block ciphers – like other AES candidates – (“We’ve already got a good block cipher, why would we need more?”) was pretty shortsighted.

Jones • July 1, 2009 9:33 PM

@Tim A brute-force search would be around 2^128 (probabilistically,) thanks to the Birthday Paradox.

Eivind Kjørstad • July 2, 2009 12:20 AM

I don’t know how weak enigma is to an attack using hardware from WW-II, but modern cryptoanalytic techniques, but I do know that it’s beyond trivial to crack enigma today.

Infact, doing so was one of 9 different tasks for the ACM collegiate programming contest when I took part — that is, cracking enigma was one of 9 tasks that a team consisting of one graduate and two undergraduate students where expected to have a chance of solving in 5 hours.

Gian-Carlo Pascutto • July 2, 2009 12:48 AM

What’s the actual complexity of the attack? Is it 2^119, 2^(119+119) or 2^(119+77)? This is not clear to me from the paper.

bbad34 • July 2, 2009 7:19 AM

Tim : “What should the complexity be? 2^256? And what can realistically be brute forced at the moment?”
Jones : “@Tim A brute-force search would be around 2^128 (probabilistically,) thanks to the Birthday Paradox. ”

@Tim : No AES256 complexity should be 2^256. Since bruteforce consist to try all keys, in practice you have 1 chance over 2 to find it in 2^255 tries, 1/4 in 2^254 …

@Jones : Birthday paradox does not work like this (if so AES128 complexity should be 2^64, I would be able to crack it with my dual core in days 🙂 )

Roger • July 2, 2009 7:24 AM

First, congratulations to Alex and Dmitry on this great work!

A couple of observations: people tend to write down related key attacks as not being very practical, but in at least one area they are devastating: use of the block cipher as a primitive in one of the hash functions constructions in which the message is put into the cipher’s “key” input.

The second and even more interesting thing concerns NSA’s certification of AES for protection of classified information. They approved AES-128 for protection of SECRET information, and AES-192 and AES-256 for protection of TOP SECRET information: the different certifications strongly suggesting that not only does NSA accept that these algorithms are strong, but more particularly that they believe, as one might expect, that AES-256 and AES-192 are stronger than AES-128.

This new analysis seems to show that at least for one type of attack, this is not true and AES-128 is actually the strongest of the three. This seems to suggest that NSA’s review did not discover Alex and Dmitry’s attack before certifying these algorithms for TOP SECRET applications. (Or perhaps they did discover them, and decided the attacks are too impractical for them to care; it will be interesting what happens to the AES certifications in the coming days.)

Roger • July 2, 2009 7:34 AM

@Gian-Carlo Pascutto:

The complexity is 2^119. (To be stricter, it is actually 2^119 plus a few other steps on the order of 2^72. But whereas 2^(119+72) is much larger than 2^119, 2^119 + 2^72 is negligibly more than 2^119.)

2^77 is the amount of memory required. (Quite a lot.)

mike • July 2, 2009 8:38 AM

forgive my ignorance, but what’s to keep, say, intel from building a highly-specialized 32nm AES-dedicated chip that can run through trillions/quadrillions of encryptions per second? is it just not possible?

David • July 2, 2009 9:05 AM

@mike: The problem is sheer scale. We’re dealing with numbers on the order of 10 ^ 38 for a brute force attack on a 128-bit key. If you can run through a trillion keys a second, you can get the key in 10 ^ 26 seconds, which is a few hundred trillion years. If you can somehow speed that up by a factor of a thousand, perhaps by dealing with Intel, you can crack it in a few hundred billion years.

As far as the chip goes, there are significant limitations on how fast a chip can go, with fundamental limitations based on the speed of light, the necessary size of chip elements to avoid drowning in random and quantum effects, and the like. There are also engineering issues, such as the fact that signals in any medium go slower than the speed of light, the difficulty of making extremely small chip elements, and the like.

Several years ago, people were able to use expensive equipment to brute-force the 56-bit DES key. An AES-128 key is 72 bits longer, as I understand it, which multiplies the number of cases by about four sextillion. We’re nowhere near a sextillion times as efficient as we were back then, and we’d have to have an entirely new idea of computation to get there.

Therefore, keys like that can’t be brute-forced. The systems have to be cracked.

Flip-Flopper • July 2, 2009 12:19 PM

@mike The world fastest supercomputer has around 2^50 FLOPS. Assume that we can check with one FLOP one key. Also assume we can shrink this giant to an area of 1 mm^2. The surface of the earth is around 2^69 mm^2. Conclusion, if we cover the whole earth with this super mini computers we would still need around 8 1/2 minutes to crack one key with 100% certainty.

David Schwartz • July 3, 2009 6:11 PM

Mike: Nothing. That’s precisely how people break cryptographic schemes. When you consider how suitable an algorithm is, you have to figure in the resources of your attacker. An algorithm that would keep your little sister from reading your diary won’t keep out the CIA.

That is why AES-128 is used almost exclusively for applications where it is believed to be billions of times more secure than it needs to be. And that’s why an attack that makes AES-256 a billion times easier to break is still impractical to use.

Randall • July 4, 2009 6:16 PM

@Roger: Some of NSA’s algorithms from the FORTEZZA project (BATON, JUNIPER) had a 160-bit keyspace; it’s documented in the PKCS#11 spec. So I think they required AES-192/256 just because 160 bits is their standard key length for TOP SECRET info. Myself, I don’t think AES’s use to handle TOP SECRET data will change unless a much better attack comes along.

@caf: Guess I have to agree it would be better to have more TLS ciphers. We don’t want another MD5 problem; we want uninterrupted security with minimal pain when algorithms start to look shaky. Of course, AES does not look shaky yet by a long shot.

outer • July 5, 2009 3:47 PM

In retrospect, however, several of the other AES candidates (though none of the other finalists) were eliminated early-on for having far less serious “certificational” weaknesses.

Anon users • July 7, 2009 3:11 AM

This is an ‘engineered’ bug!!!

AES-192 & 256 are ‘intentionally’ weakened in the key expansion phase… The original Rijndael versions use 192-bit and 256 bit block sizes (a 192b key MATCHes with a 192b block & the 256b key MATCHes with a 256b block)

so is it surprising to see AES192 & 256 are weaker than expected??? NOOOO

Looking for another next-gen cipher (like SHA-3) competition??? NO NEED Just use the original Rijndael.

PackagedBlue • July 7, 2009 9:59 PM

Different revisions of candidates/submissions/footnote details giving “enhancements” are a bit creepy to outsiders. Hard to trust such a small community of independent skillsets like programming, math, and computer knowledge.

I would like to see more serpent implementations, however, AES is the “standard.” Too bad that Serpent does not get the attention and $’s.

The devil is always in the details. Banks pay good money for good reasons for hopefully good work. I do not trust NSA/NIST to do the right thing, they are not trustworthy, but only a rat race security. GRR.

Would be interesting to read more about the custom crypto business.

Security is a very closed world, you only read about some of the insecurity.

greg • July 8, 2009 8:24 AM

@PackagedBlue

In the early 90s I would have agreed with you. But not anymore.

NSA turns up to open conferences cus they are not that far ahead anymore.

Like others I feel pretty confidant that they can’t crack PGP with reasonable settings.

Keyboard loggers yes. But directly crack.. No.

Billy Crook • July 9, 2009 1:40 PM

OT: @Bruce, nice touch on the comment system. It’s been getting awfully busy in the last year, and hard to tell yours apart from the rest.

Smarry • July 13, 2009 11:10 PM

so is it surprising to see AES192 & 256 are weaker than expected??? NOOOO

Smarry
Get 28 movie channals for 3 months free

Yessomat • September 7, 2009 8:20 PM

Another example that our future is more to combine all.:

Encryption (Password and Keyfiles) + Hide-Out + small, mobile Hardware.

Brute Force is only possible if the file is visible / known / acccessible. We can give forensic much more frustration if we encrypt + hide files.

Here you can find new compression algorithms – no forensic software can read it – if so than its mostly to late cause some dozen new algorithms are out every 6 month.:

http://encode.ru/forum/

To say here is one new encryption algorithm and anything is fine is no longer our future.

Encryption + Hiding Place + no physical access etc. etc.

Funny – 99% of all forensic workers and police officers forget the postbox. Its true – they strip search you, the house, the garden, garage, basement, top flor, car but they look not at the postbox for an ciphered USB Stick.

kd borch • March 24, 2010 6:22 PM

Interesting. It made me want to ask (naively), contrary to what Bruce suggests, about the possible bad consequences for AES based contenders to SHA-3, why not see it as an advantage that an encryption scheme has been vigorously tested, and more weaknesses explored, so long of course, that it is still way outside of current computational reaches to exploit these weaknesses. It should give a clearer picture of just how secure the encryption is, and maybe a better estimate of when it will be easily breakable. The others are not neccesarily more secure, just haven’t been attacked so much, or am I misunderstanding something?

Thanks for the read everyone!

Ryan • August 3, 2010 7:48 PM

So how many qubits in a quntum compter would one need to solve this in 256 tries? 121 +/- 1?

Ryan • August 3, 2010 8:01 PM

That and if we knew what even one page of text within the document had, or even several key phrases (I dunno like “osama”). There are some frequently used combinations that could reduce the complexity more? (most specifically thinking that wikileaks ‘insurance’ should be cracked open, I’m sure julien has more dirt, and next time around he should use rc5.

Colin Johnston • August 20, 2010 1:31 PM

looking to implement rubix cube solving parallel implementation to Rijndael-S box with mapping matrix to rubix cube sides. This seems possible with dummy values on cube sides which are not needed. shout if you think this is not useful route of attack ?
transputer array implementation of above worked for one side of cube mapped to first 3 values in first 3 rows of S box matrix
colinj@mx5.org

wrya • July 31, 2013 6:33 AM

could you please help me to understand the biclique cryptanalysis of the AES paper?

First: In the backward direction of AES-128 , why the difference in the relevant subkeys is a linear function of i but in backward direction is nonlinear function of j?

second: In forward direction of AES-128, you mentioned that only 3 S-boxes need recomputing. which 3 S-boxes you mean?
third: In section 3.2 , what we really do in inbound and outbound phase?

I cant find any review of the paper. If a review or video is available related to this study please email it to me.
wrya_1987@yahoo.com

I appreciate your help.
Wrya

Gokhan Gun • September 17, 2013 8:21 PM

Hi – Can you please provide the full paper about this subject matter? I did not see the all details the mathematics worked behind it and some links are not working on the page.
Is there an IEEE paper about it as well please?
Thanks
Gokhan Gun

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.