Another New AES Attack 93
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."
That's nice... (Score:4, Insightful)
But all I really want is something that'll crack a RAR password without taking months. (AES-128)
Practical? (Score:5, Insightful)
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.
The beauty of public cryptographic algorithms (Score:5, Insightful)
Re:That's nice...makes you wonder... (Score:5, Insightful)
Re:There is no such thing as ten-round AES-256 (Score:5, Insightful)
Reduced-rounds attacks are a standard cryptographic technique. You start by breaking a reduced strength version of the cipher with a completely impractical attack that's marginally better than brute force. Then someone comes along and observes that they can improve your attack to more rounds or shorter time. Then that repeats a few times. Eventually, the cipher is broken.
No, they haven't broken AES. However, this is a step along the way. If the designers of AES had known that there was a good attack against the 10-round version, they wouldn't have recommended 14 rounds -- standard practice is to include a larger safety factor than that. This is a big deal, not because you can now break AES, but because the attacks are much closer to doing that than previously thought. Hence, the recommendation by Schneier to move to 28 rounds -- improve the safety factor. Attacks always get better, never worse. It's possible (though unlikely) that there are unpublished attacks on AES known by some organizations -- and the closer to a real break the publicly known attacks are, then the more plausible that scenario becomes. Attacks that get this close and weren't anticipated by the cipher designers are scary things.
Also, this is a related-key attack -- meaning the attacker needs two keys that are related somehow and the same piece of plaintext encrypted with both. If the implementation of AES that you use does a good job of selecting a truly random key, then the attacker can't implement this attack because he can't get you to use the requisite pair of related keys. That doesn't mean it isn't a valid attack, just that it's an attack that can be defended against. Again, the biggest worry is that someone will take this attack and realize how to improve upon it to make an attack that's even better.
Re:Practical? (Score:2, Insightful)
> I'm not sure how practical it is for any "programmer on the streets" to pay attention to this sort of thing.
These "any programmer on the street" guys hopefully never implement anything in the vicinity of crypto code.
You do not need to read the papers. Reading something like http://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html [daemonology.net] -- if you happen to trust Colin Percival -- should be enough, if you do not try to be creative in what you use.
What is so bad about considering MD5 broken and make design choices because of that? Better than the other way around, if you are not in the field. How much more expensive is it to verify an MD5 and an SHA256 hash instead of MD5 only -- for many practical application, it is irrelevant. So why not do it?
Re:There is no such thing as ten-round AES-256 (Score:5, Insightful)
AES-256 and AES-192 are really AES-128 in disguise. They were created only to meet NIST requirements for three different key sizes, not from any practical security reasons (128 bits is definitely enough to prevent brute-force cracking).
The AES algorithm needs 128 bits of key for each pass through the encryption loop.
For AES-256 they select 128 bits from the 256-bit key for each round. Some of the key bits don't make it into the encryption loop until quite late in the process so in the final output they've only had a few rounds of encryption and can be brute-forced with much less than 2^256 effort. When you have some of the key you can go back and get a few more bits, and so on...
nb. The designers weren't stupid, they designed AES-256 to completely lose the key and this attack doesn't work against all twelve rounds of AES-256. The surprise is that somebody managed to extract the key out of a ten round version. This was unexpected.
nb. In AES-128 *all* of the key bits have been through *all* the rounds of encryption so inferring anything about the key by looking at the output is much more difficult (and hopefully impossible).
Re:Not sure if its time for AES2, but...BUT THIS.. (Score:3, Insightful)
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.
Re:There is no such thing as ten-round AES-256 *$* (Score:3, Insightful)
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.
Re:There is no such thing as ten-round AES-256 *$* (Score:3, Insightful)
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.
Re:That's nice... (Score:1, Insightful)
RAR passwords? Everyone seems to do it via brute force or nearly brute-force, assuming Eugene Roshal is good at crypto. He isn't bad (good enough to use elliptic curve in the registration scheme), but apparently, the people who write the password crackers are terrible.
It's not the AES-128 you want to focus on. It's the hash protecting the AES-128 decryption key in the header.
It's iterated (hence the slow speed of traditional brute-force) and salted, but the salt isn't very big. It's therefore possible to use a rainbow-table construct against it, but there's still a considerable amount of computation because of the salt. Fortunately that has no branches, parallelises extremely well and you don't have to mix the lookups with the computation, so it's suitable for GPU shader acceleration; a handy 100x performance boost.
Using all of that in the attack, it should be possible to crack any RAR archive's password of 60 bits of entropy or less in about a day - so 10-character alphanumeric (2^59.54) is dead for sure, as is anything in a precalculable dictionary attack. (However, any more than that, and the attack begins to fail; you can't cover it in a practically-sized table, or rather you have to spool to disk which slows things down several orders of magnitude.)
That assumes the hash is secure, of course. You may want to take a close look at that. ;) However I'm not currently aware of any effective attacks which help a full preimage yet, although collisions can help the table construction considerably and of course this will only get easier in time as the whole class of those hashes is now looking rather suspect. Maybe you could use the tunnels currently known to help in a meet-in-the-middle attack to refine it, but I suspect at the moment you'd still be looking at a computational factor too high to actually use.
However, it doesn't look like anyone has ever fully implemented this attack. Perhaps I should launch my own line of ludicrously overpriced shareware. ;-)