Slashdot Mirror
New AES Attack Documented
avxo writes "Bruce Schneier covers a new cryptanalytic related-key attack on AES that is better than brute force with a complexity of 2^119. According to an e-mail by the authors: '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 2^119 to about 2^110.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.'"
Pardon me, but isn't the article about AES-256? So this is a much more significant drop in the number of bits.
Of course, I've only read the summary. This is slashdot, natch.
For those who are asking "what's 2^119 complexity mean?"
2^64 is about as hard a problem as we can reasonably solve these days.
2^80 is about as hard a problem as we can unreasonably solve. I.e. we can do it, but it would take the budget of a country for several years to do.
A can of soda has about 2^83 molecules in it.
2^119 is still way beyond anything we can reasonably do, but isn't so hard that we can rule out any theoretical possibility of solving it.
A house sized computer built of solid nano-compute units, each a few hundred molecules on a side, with a cycle time of about 10 petahertz could do it in less than a lifetime.
Perhaps possible but I wouldn't worry about it.
2^256 is so hard that it may not even be theoretically possible to solve - or maybe you could if you're willing to destroy a few solar systems, and wait a few million years.
While cracking 2^256 may not be theoretically impossible, it would be easier to look everywhere the information you want might be hidden - including inside the mind of your opponent - even if he's dead.
Two things:
First, they are talking about AES-256.
Second, I find it useful to think about how much faster that is. In this case, it means it is 2^137 times faster than a pure brute force attack, which certainly seems impressive. Fortunately, as you mentioned, this is still far too difficult to be applied.
Just for fun, google this: 2^119 picoseconds in millenia
It means you only have to test 2^119 possible keys to break 256-bit AES - still far beyond what's ever going to be feasible (do the math - give everybody on the planet a million PCs running at 1THz and see how long it takes to do 2^119 things, then figure out where you're going to get that much electricity from)
Interesting to note is that AES-128 is immune to this attack - it's now the strongest variant of AES. Everybody (like me) who thought the 256-bit and 192-bit were a waste of time now has a reason to be smug about it.
Reason: Both AES-192 and AES-256 are just AES-128 internally but they mess around with the key data between each loop of the encryption process. The new attack only works on the "messing around" part of the process so AES-128 is unaffected.
No sig today...
>Just for fun, google this: 2^119 picoseconds in millenia
And for even more fun - 64 minutes after the parent posted, the post itself was the first result.
1 in 4 Maine children in struggle with hunger.
Security
The usual threat model for a cipher is either a "chosen plaintext attack" (CPA) or a "chosen ciphertext attack" (CCA). In both of those, you have a lot of plaintext-ciphertext pairs all encrypted under the same key, and your job is to use that info against the cipher. Not necessarily to actually compute the key (which would totally destroy the cipher) but even to be able to infer anything about it statistically (for example, to have a better than random chance of guessing whether a new plaintext/ciphertext pair was encrypted with the same key).
This attack is a related-key attack, which traditionally means that you get to see the same plaintext encrypted under enormous numbers (like 2^119 in this case) of different but related keys, rather than under the same key (or a "small" number of keys like a few trillion). This is a threat model that most ciphers aren't designed against and it's instead countered by designing the application to not rely on it. For example, don't use the cipher as a hash function by using the plaintext as a key and encrypting some constant. Properly designed crypto applications don't let attackers access the keys, and they generate their keys randomly rather than letting them be related. I don't think related-key attack resistance was part of the specification given to entrants of the AES contest, and IIRC the AES standard doesn't claim such resistance.
Nonetheless, the designers of Rijndael (the cipher that is the basis of AES) designed Rijndael to be "ideal", which among other things Rijndael was supposed resist related-key attacks, which was above and beyond the AES requirements.
This new discovery finds that the AES cipher in fact does not meet Rijndael's design goals. Rijndael's design goals, however, exceeded the requirements stated in the AES standardization process, and any applications using AES are supposed to only use the characteristics of AES stated in the standard. So, even if this attack were of low enough complexity to be practical, it STILL should not affect valid AES applications, unless they are relying on characteristics that AES was never promised to have.
If you want your secrets to remain secret past the end of your life expectancy, then, in order to choose a key length, you have to be a futurist. You have to anticipate how much faster computers will get during this time. You must also be a student of politics. Because if the entire world were to become a police state obsessed with recovering old secrets, then vast resources might be thrown at the problem of factoring large prime numbers.
So the length of the key that you use is, in and of itself, a code of sorts. A knowledgeable government eavesdropper, noting Randy's and Avi's use of a 4096-bit key, will conclude one of the following:
-Avi doesn't know what he's talking about. This can be ruled out with a bit of research into his past accomplishments. Or,
-Avi is clinically paranoid. This can also be ruled out with some research. Or,
-Avi is extremely optimistic about the future development of computer technology, or pessimistic about the political climate, or both. Or,
-Avi has a planning horizon that extends over a period of at least a century.
-- Neal Stephenson, Cryptonomicon