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)
Re:That's nice...makes you wonder... (Score:5, Funny)
Re:That's nice...makes you wonder... (Score:5, Insightful)
Re: (Score:3, Interesting)
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.
Re: (Score:2, Funny)
Ah now I understand, you guys just wanted to *understand* Iraq.
Re: (Score:1)
Re: (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 us
first post? (Score:1, Redundant)
All your AES are belong to us!
Re: (Score:1, Informative)
There is no such thing as ten-round AES-256 (Score:5, Interesting)
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.
Re:There is no such thing as ten-round AES-256 (Score:4, Interesting)
Do you know why AES-256 is apparently more vulnerable than AES-128? Reading the article, attacks on AES-256 have apparently reduced the search time far more (to 2^119) than they have for AES-128 (which still stands at 2^128). Shouldn't a longer key make the attack more difficult as well because it increases the search space?
..longer key make the attack more difficult.. (Score:2, Interesting)
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
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:There is no such thing as ten-round AES-256 (Score:5, Informative)
To be more precise, Rijndael has two parameters:
This means Rijndael is a set of 25 different ciphers; AES is a subset of three of these ciphers. The number of rounds is derived from the maximum of these two parameters; for a 256-bit key and 128-bit block, it is defined as 14 rounds. Fewer rounds means we're not analyzing Rijndael, but a reduced-round Rijndael variant.
Related key attacks, by and large, are only an issue with "make a hash out of a block cipher" constructions. I don't know offhand if this is an issue with Whirlpool [wikipedia.org], a hash construction using an AES variant; as I recall, some changes were made to the key schedule of Whirlpool.
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: (Score:1, Offtopic)
Attacks always get better, never worse.
That's only because my last boss hasn't worked in cryptanalysis (yet). If he ever does, we will all be safe again.
Re: (Score:2)
That's only because my last boss hasn't worked in cryptanalysis (yet). If he ever does, we will all be safe again.
Are you trying to impress us by being mysterious? Or do you often write online posts that only you understand?
Re: (Score:3, Funny)
Re: (Score:2)
I forgot my sarcasm tag apparently. Attacks get better, not worse in cryptanalysis because my old boss hasn't been able to make them worse. He can make anything worse (it's his specialty). We'd all be safe again if he worked in the field because he'd mess the entire field up so bad no one would ever be able to decrypt anything again. I'd say you made me ruin the joke by explaining it, but if I had to explain it, then it couldn't have been that good. I almost included a bit more with the post, but I thought
Re:There is no such thing as ten-round AES-256 *$* (Score:2)
The problem isn't the ability to move to 28 rounds for security now, but w
Re: (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: (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
Re:There is no such thing as ten-round AES-256 (Score:5, Informative)
Another (somewhat less-well known) thing that can be done is to use OAEP+ (http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding) to encrypt the datablocks that you're transmitting. The link is to OAEP but OAEP+ is probably what you'd want to use with AES... I don't have a link handy, and the basic principle of the two is the same...
The OAEP algorithm scrambles your data chunks by XORing your plaintext with randomly generated bits, but done in a way that's recoverable IF and ONLY IF you have the entire ciphertext decoded (designed for RSA, but can apply to AES). This means that the same key+plaintext will always result in different ciphertext, and also means that in order to get any useful bits of key/plaintext information, the attacker must get them all, or they're just guessing as to which set of random bits OAEP used (and it generally puts 128 bits worth in).
While the actual OAEP protocol is a block-level action, and the safe version adds 128 bits of randomness (and thus size), the general idea can be modified to be as cheap or expensive as you want... the idea in general makes many asymetric ciphers MUCH more secure.
Re: (Score:1)
I'm well aware that OAEP was designed for asymetric ciphers... but I try not to be straight-jacketed by the on-the-box labelling of an algorithm, and keep my mind on what the algorithm actually does. OAEP is basically just a general principle for armoring a block of data to foils partial recovery unless you can decrypt a large % of it.
I agree, OAEP doesn't do _anything_ to fix the weakness in the key-schedule, but I was under the impression this attack required not just related keys, but related plaintext,
Re: (Score:1, Informative)
"Attacks only get better. They never get worse."
Breaking reduced-round versions of a cipher show that they are not as strong as originally hoped. Beating 10 out of 14 rounds show that this algorithm has serious problems.
AES crack (Score:5, Funny)
So I guess this is an AES-hole?
Re: (Score:3, Funny)
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.
Re: (Score:1)
Re:Practical? (Score:5, Informative)
I've seen real world attacks against md5 where being used as a checksum/verification. Malicious individuals injected code, but the md5 didn't change. http://en.wikipedia.org/wiki/MD5#Vulnerability [wikipedia.org] We researched it in a security course I took recently.
Re: (Score:2)
Right I think the message though should be; if you are not going to take your time to understand why its broken and if its still safe to use for your application and are going to just use something else instead than make that something else another well known well researched standard.
For example
MD5 is broken, so you decided to use sha1 --good idea
MD5 is broken, so you decided to write your own hash function --bad idea
Re: (Score:2)
...yes, and then the identical-MD5 "malicious" and "not" can be prefixed ("injected") onto whatever you like and the MD5 of the result will be identical.
I.e, if the MD5 of $a is identical to that of $b, then the MD5 of $a . $c is also identical to that of $b . $c, regardless of the actual value (or MD5 hash) of $c.
Grandparent simply omitted to mention that the injection point must, by design, be at the beginning.
Re: (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 a
Re: (Score:2)
His "CTR+HMAC" method relies completely on the quality of your nonce for security.
Software-generated nonces are notoriously error-prone, especially on systems which need to generate millions of them every day. Several SSL cracks have been based on guessing parts of the nonce.
Re: (Score:2)
A CTR denialist? They still make you?
A nonce doesn't need to be secret or unpredictable, but only unique. You can just use a counter. If you need a unique start, you can use a large random number to start the sequence, and it's easy to modularize a good cryptographic RNG. (Not that it's necessarily easy to create a good RNG.) There are a variety of ways to generate a good nonce.
The only other reasonable alternative is the venerable CBC mode, but using a non-repeating IV (a nonce by another name) for that mo
Re: (Score:2)
Ummmm ... ok. I can see how that works.
OTOH I'm very worried about this statement in his "why I recommend using the Encrypt-then-MAC composition" page:
"Of these three, only Encrypt-then-MAC is provably secure, in the sense of guaranteeing INT-CTXT (integrity of ciphertexts -- it's unfeasible for an attacker to construct a valid ciphertext.."
He seems to be contradicting himself there - in CTR mode you can easily flip bits of the cyphertext then make a new MAC.
Re: (Score:2)
Your "attack" works against any plain hash used a MAC. Good MACs, like HMAC [wikipedia.org], are not vulnerable to such trivial tampering: because an attacker does not have the secret key used to construct the original MAC, he can't create a valid MAC for his modified ciphertext.
The paper the author is implicitly mentioning, by the way, is Hugo Krawczyk's "The Order of Encryption and Authentication for Pr [iacr.org]
Re: (Score:2)
in CTR mode you can easily flip bits of the cyphertext then make a new MAC.
No. MAC != hash. You cannot compute a new MAC unless you have the MAC key.
Re: (Score:1)
Re: (Score:2)
I say this because I have to constantly hear stupid stuff from fellow programmers like "MD5 is broken!!!11.
While MD5 can not be considered broken as a hash for data verification where not malicious modification is suspected, enough potential practical "attacks" have been published to suggest that all new cryptographic code should use something else.
We do work for banking organisations, and a number of them now specify that MD5 should not be used as a has function in any new project work and should be phased out of existing code where practical. If our clients consider it broken, then we have to, or at least we h
Re: (Score:2)
Please mod the OP up.
At least 90% of problems with cryptographic systems are based on implementation, not broken algorithms. There are countless examples of this. While a new attack against AES is important, it's really only of interest to the relatively small group of mathematicians doing algorithm design. Vulnerabilities in the SSL signing process (for example) are of much more interest to programmers.
Re: (Score:2)
MD5 is broken.
For example now http://www.copyclaim.com/ [copyclaim.com] is completely useless: I can trivially "sign" two texts with same hash.
No need to worry... (Score:2)
... 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.
The beauty of public cryptographic algorithms (Score:5, Insightful)
Re:The beauty of public cryptographic algorithms (Score:5, Funny)
Re: (Score:2)
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.
It only proves beyond a shadow of a doubt the maximum security of the algorithm while the actual security remains in question.
Not sure if its time for AES2, but... (Score:4, Interesting)
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.
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 simpl
Never say 'never' in cryptography! (Score:2)
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
Re: (Score:2)
Maybe Serpent would be a good candidate because it was discussed that it had a larger margin of safety than Rijndael/AES.
With all the talk of 28-round AES, Serpent is definitely worth another look. The authors purposefully made it 32 rounds even though they thought that 16 rounds would be very secure. It was rejected in the AES competition because 10-14 round Rijndael was faster than 32-round Serpent, but if it moved to 28-rounds, I doubt Rijndael would still be faster than Serpent.
Re: (Score:2)
That's utter nonsense. DES was used extensively, and for plenty of critical data. What do you think all those web browsers have been using for SSL?
DES STILL hasn't been broken. It's short key-length just ran up against Moore's law. 3DES is still a sound algo, b
TwoFish (Score:2, Interesting)
Re: (Score:3, Interesting)
Maybe. Twofish is almost as fast as AES, and possibly more secure. Schneier has a lengthy discussion in Practical Cryptography on possible weaknesses in AES that are a result of its simple algebraic structure, and to this day there are no successful attacks against Twofish or its 64-bit-blocked ancestor Blowfish. Then again, AES has received more scrutiny.
Re: (Score:2)
Re: (Score:2)
The cardinal sin of security is sacrificing safety for speed. It applies to all work, really, but in security, the effects are particularly harmful.
Re: (Score:2)
At around the time the AES contest was ongoing, I was doing work on writing a cryptographic layer for an embedded system based on small microcontrollers. I wrote assembler implementations of Serpent, Twofish, RC6, and Rijndael for the embedded microcontroller (it was an 8-bit 8051-type controller, if I recall correctly), and Rijndael was consistently the most efficient, so it came as no surprise to me that Rijndael was several months later declared the Advanced Encryption Standard. One of the criteria for
Re: (Score:2, Interesting)
> They should have picked TwoFish.
I would choose TwoFish over AES because TwoFish was very close to being picked as a standard,
and didn't make it. That means AES gets all the attention, and "nobody" attacks TwoFish.
However, if they'd chosen TwoFish, would we today be reading about a new veakness of TwoFish,
and would you have made a comment on how they should've picked AES ?
Re: (Score:2)
Welcome to the world (Score:2)
Hi the the NSA and GCHQ
Re: (Score:2)
If Skein [wikipedia.org] wins the competition, we get Threefish [wikipedia.org], a perfectly good block cipher, for free.
Consider best attacks against DES and SKIPJACK (Score:1)
I want to see attacks on Twofish and RC6 (Score:2)
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.