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.'"
So instead of taking 1 million years to brute force, it will take .9 million years?
I totally made up those numbers but that's about the difference.
erm only a 99.7% improvement.
The troll with karma.
TFA refers (as does the summary) to complexity of 2^119, and possibly lowering it to 2^110.5. Could somebody rephrase that in a way that people like me, who aren't cryptography specialists can understand what they're talking about?
Good, inexpensive web hosting
Crypto is broken. It's not IF, but WHEN. That's why crypto is pointless to use. this is why I use open source, and even keep all doors unlocked. It's pointless to try and protect propery, real or intellectual/imaginary.
For those who don't have a degree in oh-shit-that's-a-big-number, can someone give a comparative analysis of what "2^119" complexity means? I mean what else is "2^119" hard to solve? And yes, the math nerds are undoubtedly either dying of laughter or yelling at the screen for my abuse of powers of two... I don't care.
#fuckbeta #iamslashdot #dicemustdie
Yeah, this is interesting math, but I don't think our cryptographic scheme is in danger until quantum computers become a stable and reliable source of heavy computing. Then we're all in trouble. How do you create a key, when the entire large number method is made obsolete by quantum computing? I haven't looked into it much, but I don't think anyone has found an answer yet.
To my knowledge quantum cryptography is still limited to very close distances, while cracking a crypto key is obviously not affected by this limitation.
If you can read this... 01110101 01110010 00100000 01100001 00100000 01100111 01100101 01100101 01101011
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.
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.
Almost everyone here seems to be missing the bit in the summary that mentions that it's time and data complexity. It's not nearly as bad as 2^119 time and some tiny data.
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
Lord Farquaad: I've tried to be fair to you creatures, now my patience has reached it's end! Tell me or I'll...
Gingerbread Man: NO! Not the buttons! Not my gumdrop buttons!
Lord Farquaad: Alright then! Who's hiding them?
Gingerbread Man: Ok. I'll tell you. Do you know... the muffin man?
That's a pretty common myth.
It might hold for most symmetric key cryptography algorithms (such as AES, SHA, MD5, DES, etc) however there is a whole other branch of (admitidely mainly theoretical) cryptography which relies on provable security. I.e. formal reductions showing that breaking security of the scheme is at least as hard as solving some difficult underlying problem. For such schemes it's a lot more plausable that there may simply not be a poly-time algorithm which solves them. (Take the short vector problem of lattice based crypto for example. To date we don't even have a _quantum_ algorithm that solves it efficiently let alone a classical one. Yet there are schemes that are at least as hard to break as that problem is difficult to solve.)
And of course then there is another branch of cryptography which considers information theoretic security. These are provably _unconditionally_ secure. (The most common example being the "one time pad".) For these algorithms, protocols, and applications as long as the under lying model is a good model of the real world there is simply no way to break security regardless of computing technology and future developments in algorithms.
So no. Crypto is not just broken. Quite a lot of modern crypto is actually pretty secure. (Now whether it's practically efficient is a whole other new ball game of course, but then that wasn't the claim...)