Slashdot Mirror
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."
But all I really want is something that'll crack a RAR password without taking months. (AES-128)
Alexander Peter Kristopeit bought his basement from his mommy for one dollar.
All your AES are belong to us!
In times of universal deceit, telling the truth gets you modded -1 Troll
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.
So I guess this is an AES-hole?
Slashdot social media options: AIM, ICQ, Yahoo, Jabber and Mobile Text. Why no MySpace?
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.
I've had enough abrasive sigs. Kittens are cute and fuzzy.
... just yet. ON the other hand it is always necessary to follow what happens in cipher breaking for an undertsanding on what to use and what hot.
My impression in this thogh, is that people just invest more time in more obscure attacks. Related key attacks have no relevance in most apllications. Still the right thing to do for the crypto researchers if more general attacks fail, but less revant to practive, if at all.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Like posting here?
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.
Did you ever wake up in the morning, with a Zombie Woof behind your eyes? -- FZ
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."
SIG: HUP
As an academic researcher with interests in security, I take offense at that. We do things like this for a living. It's kind of important to analyze cryptographic schemes for vulnerabilities, since data privacy and security depends on it.
I also find, for myself, that the best way for me to learn is to deconstruct what I want to learn about. Physical or not, the deconstruction gives you insight into how the hardware/software works.
It's all fine to know something exists, but finding out how it works is a different matter.
Even though AES is far from being truly broken, I wonder if it's time for NIST to start working on the AES2 spec. Maybe Serpent would be a good candidate because it was discussed that it had a larger margin of safety than Rijndael/AES.
As stated in TFA, attacks only get better and better, so every decade or so, maybe it would be time to consider another standard encryption algorithm. The reason DES lasted so long as an algorithm was that cryptography was not as vital to day to day operations as it is now, so a complete break would have been more of an academic excercise than one that would get the cryptographer financial gain. These days, if a blackhat does a break, or reduces the keyspace to a low level where brute forcing is possible, there are billions of dollars to be gained.
Well, if you had asked whether more rounds make the attack more difficult, then I would have an answer: more rounds don't necessarily make the attack more difficult.
To verify this take a rubiks cube in its solved state. Hold it such that your fingers touch the top middle and bottom middle square. Now begin to rotate the right side of the cube by one turn, then turn the entire cube by 90 degrees. Repeat this. After some time you will notice that the cube begins to return to the starting position, although it looked quite mixed in between.
Mixed= Good hashing function
Solved= Very bad hashing function
Hey don't blame me, IANAB
They should have picked TwoFish.
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
The problem isn't the ability to move to 28 rounds for security now, but with everything that was encrypted at only 14 rounds before. You're not going to re-encrypt everything from before, and you can't recall all of those less secure copies. That's the problem.
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
That does nothing to protect all of the existing AES data. And you can't go back and simply re-encrypt the old data to the new standard. The whole idea of encrypting it in the first place was that it was likely to get stolen somewhere along the way and when it did it would never be of any use to the thief. There is a lot of AES protected data that has been copied and can simply be held until an AES crack arrives -- or the key is determined by other means.
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
of Enigma and Crypto AG :) :)
Hi the the NSA and GCHQ
Domestic spying is now "Benign Information Gathering"
If Skein wins the competition, we get Threefish, a perfectly good block cipher, for free.
Good point.
If we move to 28 rounds now, then the hope is that by the time AES-256 with 14 rounds is broken, there will not be much valuable data left encrypted with it.
I think it's a safe assumption that the value of data decreases with time.
The best attack against DES breaks 15 out of 16 rounds faster than brute force. However for the full 16 rounds, the best attack against DES is brute force. Likewise, the best attack against SKIPJACK breaks 31 out of 32 rounds. In both cases NSA was fairly involved with the development of the algorithms and they just happen to have no "security margin". Perhaps that means NSA was ignorant of the methods (such as impossible differential cryptanalysis) that the academic sector developed. Perhaps it means that NSA is willing to play fast and loose with securing government communications. Or maybe, just maybe, it means that NSA knows exactly how strong the algorithms are and doesn't need to rely on ad-hoc measures like "security margins". I don't know, but the fact that AES-192/256 is specified for Top Secret while AES-128 is for Secret makes me suspect that NSA knows far more about the real security levels of AES than the keysize would indicate.
If attackers against any system have the resources to store all of the system's traffic in the hopes of decrypting it with a complete break later (e.g. as WEP was broken after months/years of wireless traffic), then the fact is they'll have a lot of sensitive information. To an individual, corporation or defence organisation, there is plenty of "old" data that would be very damaging for others to have, and yet in general the old data inches closer to exposure. So sure, it drops in value, but never enough to make a break acceptable.
Sam ty sig.
Honestly I want to see more articles on how people are attacking RC6 and Twofish. Some of us like the 1:1 complexity algorithms, not the Rijndael compromise that was decided upon for AES which gets slower the more secure you want it. I want more exposure of Twofish.
Kriston
Ah now I understand, you guys just wanted to *understand* Iraq.
The whole idea of encrypting it in the first place was that it was likely to get stolen somewhere along the way and when it did it would never be of any use to the thief.
I disagree with your use of the word 'never'.
While we would like to design cryptographic tools that last forever, it's really hard.
For one, there's (almost always) the brute-force attack. By buying more computers, you can always do it faster, since it by its nature is embarrassingly parallel.
The best we can hope for is that for all thieves, their (perceived expected) cost of breaking the crypto exceeds their (perceived expected) gain.
As long as computers yield more cycles per dollar over time, we will have to keep using larger and larger keys; and as algorithms get broken, we will have to start using new (and hopefully better) ones.
In cryptography, not even diamonds are forever ;-)