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.'"
That's only a 0.3% improvement!
The troll with karma.
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.
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
Funny how news of just about every major break of an existing cryptography system or secure hash method has started out with just about those same exact words.
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
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.
...but they pose no immediate threat for the real world applications that use AES.'"
Wait a minute... where's the fear mongering, sensationalism and hyperbole? You call this reporting? I want my money back.
I don't know if the size of the hash has anything to do with the package or the resultant file, but what about simply doubling (or greater) the hash?
I did try to read the article, but got a bit lost when I began to read stuff like, "A basic boomerang distinguisher [12] is applied to a cipher EK() which is
considered as a composition of two sub-ciphers: EK(1) = E1 2 E0. The rst sub-cipher is supposed to have a dierential  ! , and the second one to have a..."
Man, it is hard being a PHB!
The Kai's Semi-Updated Website Thingy
For some reason that SSL link to the paper uses the name of a server that doesn't have the SSL certificate so Firefox complains. Replacing the hostname gives this link that Firefox doesn't complain about:
https://www.cryptolux.org/mediawiki/uploads/1/1a/Aes-192-256.pdf
Things you think are in the Constitution, but are not.
http://xkcd.com/538/
What a coincidence! I use the starting lineup of the Green Bay Packers for my encryption key too!
If I have been able to see further than others, it is because I bought a pair of binoculars.
Let me decrypt this disinformation for y'all. Namely:
If you lived a few days before this was discovered, you would expect "128 bits of security" in your AES. But now you only get 119. What's that extra 9 bits between friends? That's just a factor of 512. It means if a few weeks ago, someone would have had to pay $70 billion for hardware capable of decrypting your message within 600 days guaranteed (with an expected success time at the 300-day mark), now they only have to pay $136 million, obviously no big change. Oh and
Which is another 8.5 bits, or a further factor of 362, leaving the tab at $377,000 for the equipment to brute-force your data within 600 days (with the expected success time at the 300-day mark). Really, it is hard to imagine how any organization might have $377,000 for such an activity but not $70 billion, so far as I can see this doesn't really change much of anything.
If 128 bits is good enough, 129 bits is twice as good as good enough. 130 bits is 4x, 131 is 8x, and so on. I am aware that nerdless wanna bes will never grok this binary stuff, but I know you don't know, and that's all that needs to be known, for the both of us.
... and wondered if perhaps there were some bad cartridges being distributed these days.
That is true in exactly the same way it is true that if it had rained during my walk yesterday, I would have gotten soaked.
Are you adequate?
Security
Good life strategy: if you truly don't understand something, and you're not interested in learning, make a joke about it. Those who laugh identify themselves as your peers, while the rest of us will (normally) engage in a silent shunning so you'll never have to confront the anguish of feeling uniformed.
Not knowing the difference between a block cipher for bulk encryption and a public key cipher for key exchange is on par (in this neck of the woods) with not knowing the difference between a debt and a deficit, or the difference between mass and weight. You might wish to append finance and physics to your note to self.
What I don't get is your mirth circuit determined that a discussion on a cryptographic attack was in need of a mirth tweet, as if this kind of thread isn't drowning in misinformation/misunderstanding 99% of the time.
Around the advent of Netscape, I briefly dabbled in an online MUD of the tedious variety. In the name of realism, your character had to sleep a lot. The game did have one good feature. You would go "con bartender" (short for "consider kicking bartender's ass") and the game would respond "you wet your pants" if you were hopelessly outclassed.
> con mirth zeta function
You wet your pants!
Well, we can dream.
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.
ok, someone needs to check my math and logic because I'm basically asleep at the moment, but:
2^100.5 = 1.8e30
2^119 = 664613997892457936451903530140172288 = 6.6x10^35
In atoms:
Avogadro's number is 6x10^23.
1 mole of iron contains 6x10^23 Fe atoms, and has a mass of 55 grams. So, 2^119 atoms are 2^119/6^23 = 1e12 moles. This means that 2^119 atoms of iron would have a mass of 55 megatonnes. (1 tonne = 10^6g), which is (very roughly) the mass of a solid cube of iron 200 meters to the edge.
So, if you take a 200 m cube of iron, the number of atoms in that will be about 2^119. Which is pretty big.
The same math for 2^100.5 makes it roughly equal to the number of atoms in a cube of iron only 3 m across.
Compare that, though, to 2^256:
2^256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936 = 10^77.
This is equal to the number of atoms in a cube of iron one light year (!) across.
So, from 2^256 to 2^119 and then to 2^100.5 are massive steps. But then again, bear in mind that 2^100.5 = 1.8x10^30 is still massive, so no worries as yet.
Unless I made a mistake. My formula from number of atoms to cube size is: ( numberOfAtoms/ (6e23 atoms per mole) * (55 g per mole) / (8 g per cubic cm) ) ^ (1/3). Output in cm.
2^256
26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
115 792 089 237 316 195 423 570 985 008 687 907 853 269 984 665 640 564 039 457 584 007 913 129 639 936
2^119
12 11 10 9 8 7 6 5 4 3 2 1
664 613 997 892 457 936 451 903 530 140 172 288
2^110.5 (rounded off to nearest units)
12 11 10 9 8 7 6 5 4 3 2 1
1 835 754 156 221 338 741 132 617 695 578 321
2 significant figures improvement! That's freaking amazing.
"Don't let fools fool you. They are the clever ones."
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
actually, via basic statistics -- (10^119 - 10^110.5) / 10^119 = approx 99.7% improvement
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?
Just wait for their torture chambers...
You know, possibility of plausible deniability can and will be cross-checked and verified over there.
Why it's so?
$5 wrench is a perfect password-extraction device in experienced hands.
With all appropriate kicking and screaming, of course.
We have tried this approach at my company.
We were tasked to destroy a stick with sensitive data (the requester did not believe in formatting).
It was not easy!
The chip itself was quite a hardy one and we had to use a stationary drill to get it done.
I am afraid the capturing act will be very swift and disallowing of any such an activity.
its bits, so that should be base 2, not 10. Doesn't change the numbers much however.
The Grey Goo disaster happened 3 billion years ago. This rock is covered in self replicating machines!
Parent is wrong. This is a related key attack and not one of the standard known plaintext attacks. AES-128 is supposed to have a complexity of 2^64 against those (please google before talking about the obvious "this is just for hashes"). So AES-256 is still better than AES-128.
The authors have a useful FAQ regarding the attack here: https://cryptolux.org/FAQ_on_the_attacks
First: Don't panic.
This attack is not practical, it requires from what I read at least 2^62 encryptions with 4 related keys. Name me one transaction where that's likely to open to the attacker. Most things like SSL use only 1 key [then the next is randomly generated] and every SSL session so far in history has been far less than 2^66 bytes in length (nor were they with related texts). So it's an attack in the sense that yes, in theory you can break AES in very contrived [in the lab] scenarios. But under those circumstances you could already break AES-256 in 2^128 effort [hint: encrypt every plaintext and look it up].
What this attack REALLY shows is that AES cannot be used as an MD style hash. Which is fine because a real hash would be faster, and for MAC'ing purposes like CMAC, CCM, or GCM they don't operate in MD mode anyways.
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...)
Try RTFA. The attack is against AES-256, which although the attack is still theoretical, 2^119 is more than collapsing the keylength to less than half its original size.
That actually doesn't look too good, because as pointed out by Scheier, attacks are only going to get better.
Brute-forcing a n bit symmetric cipher like AES doesn't take O(2^n) steps to break worst-case, but it takes O(2^(n/2)) steps. So it's a reduction from 2^128 to 2^119 in the case of AES-256. Not from 2^256 to 2^119.
It takes 2^128 instead of 2^256 because of the birthday paradox.