Beta

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Another New AES Attack

ScuttleMonkey posted about 5 years ago | from the this-time-we-mean-it dept.

Encryption 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."

cancel ×

93 comments

Sorry! There are no comments related to the filter you selected.

That's nice... (3, Insightful)

clone53421 (1310749) | about 5 years ago | (#28902085)

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... (-1, Flamebait)

jo42 (227475) | about 5 years ago | (#28902285)

Really makes you wonder if these folks have anything better to do with their lives, other than spend countless hours applying heavy thought and mathematical algorithms to such a problem...

Re:That's nice...makes you wonder... (4, Funny)

lorenlal (164133) | about 5 years ago | (#28902303)

Like posting here?

Re:That's nice...makes you wonder... (4, Insightful)

autocracy (192714) | about 5 years ago | (#28902405)

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."

Re:That's nice...makes you wonder... (2, Interesting)

sortius_nod (1080919) | about 5 years ago | (#28902515)

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:That's nice...makes you wonder... (2, Funny)

Anonymous Coward | about 5 years ago | (#28906449)

Ah now I understand, you guys just wanted to *understand* Iraq.

Re:That's nice...makes you wonder... (1)

iced_773 (857608) | about 5 years ago | (#28902413)

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.

Re:That's nice... (1, Insightful)

Anonymous Coward | about 5 years ago | (#28907407)

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. ;-)

first post? (1, Redundant)

Mr. Firewall (578517) | about 5 years ago | (#28902093)

All your AES are belong to us!

Re:first post? (1, Informative)

Icegryphon (715550) | about 5 years ago | (#28902857)

What you say !!

There is no such thing as ten-round AES-256 (5, Interesting)

Anonymous Coward | about 5 years ago | (#28902139)

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 (3, Interesting)

johannesg (664142) | about 5 years ago | (#28902365)

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.. (2, Interesting)

roguegramma (982660) | about 5 years ago | (#28902825)

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

Re:There is no such thing as ten-round AES-256 (5, Insightful)

Joce640k (829181) | about 5 years ago | (#28903047)

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 (1)

jcrivello (1268622) | about 5 years ago | (#28904053)

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.

Small correction; 14 rounds are specified in the AES-256 standard, not 12.

http://en.wikipedia.org/wiki/AES-256 [wikipedia.org]

Re:There is no such thing as ten-round AES-256 (4, Informative)

Ex-Linux-Fanboy (1311235) | about 5 years ago | (#28902401)

To be more precise, Rijndael has two parameters:

  • Key size, which can be 128, 160, 192, 224, or 256 bits in size
  • Block size, which can also be 128, 160, 192, 224, and 256 bites in size

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 (5, Insightful)

evanbd (210358) | about 5 years ago | (#28902663)

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:There is no such thing as ten-round AES-256 (0, Offtopic)

nextekcarl (1402899) | about 5 years ago | (#28903341)

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:There is no such thing as ten-round AES-256 (1)

afabbro (33948) | about 5 years ago | (#28903633)

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:There is no such thing as ten-round AES-256 (2, Funny)

darpo (5213) | about 5 years ago | (#28904563)

This is Slashdot, home of thousands of Asperger's sufferers. He probably has a whole world that's known only to him.

Re:There is no such thing as ten-round AES-256 (1)

nextekcarl (1402899) | about 5 years ago | (#28904685)

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 it would have made it too obvious. Oh well.

Re:There is no such thing as ten-round AES-256 (0)

Anonymous Coward | about 5 years ago | (#28905403)

I got it.....

Re:There is no such thing as ten-round AES-256 (0)

Anonymous Coward | more than 4 years ago | (#28919811)

It's lucky you forgot your sarcasm tags, because what you said wasn't sarcasm. Though you could describe the comment as facetious.

Re:There is no such thing as ten-round AES-256 *$* (1)

Nom du Keyboard (633989) | about 5 years ago | (#28903459)

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.

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.

Re:There is no such thing as ten-round AES-256 *$* (2, Insightful)

dch24 (904899) | about 5 years ago | (#28904339)

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.

Re:There is no such thing as ten-round AES-256 *$* (2, Insightful)

setagllib (753300) | about 5 years ago | (#28904813)

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:There is no such thing as ten-round AES-256 (4, Informative)

slackergod (37906) | about 5 years ago | (#28904703)

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:There is no such thing as ten-round AES-256 (0)

Anonymous Coward | more than 4 years ago | (#28910141)

This poster is full of crap.

OAEP, OAEP+ are completely inappropriate for a symmetric cipher like AES. Good symmetric block cipher modes (not ECB) provide for nondeterministic encryption by proper use of IVs.

The recent attacks on AES-256 all exploit weaknesses in that variant's (as opposed to 128's) key schedule. You avoid those issues by avoiding related keys (for example, don't use it in a MAC construction where data feeds key input, like Microsoft did with TEA for the XBOX). Using something like OAEP to fix a symmetric cipher related-key issue is like feeding your horse a higher grade of gasoline.

Re:There is no such thing as ten-round AES-256 (1)

slackergod (37906) | more than 4 years ago | (#28910777)

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, and needed the similarly of plaintext in order to finess the original key's bits out of the schedule. Because of that, doing something like OAEP to scramble the plaintext would seriously hamper this exploit, since they effectively wouldn't know the anything about the masked bits passed into AES. It wasn't meant to be a fix, but more of a suggestion of a stop-gap for those of us who will continue to work with legacy AES systems, and need any extra security we can throw in.

[OTHO, if I mis-read, and the exploit doesn't rely on any knowledge of the plaintext, or even similar plaintext, OAEP wouldn't be applicable]

Re:There is no such thing as ten-round AES-256 (1, Informative)

Anonymous Coward | about 5 years ago | (#28902703)

"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 (5, Funny)

mwvdlee (775178) | about 5 years ago | (#28902207)

So I guess this is an AES-hole?

Re:AES crack (0)

Anonymous Coward | about 5 years ago | (#28902497)

You can laugh, I know from a good source that the name AES is a cryptographically secure hash for "broken"

Re:AES crack (2, Funny)

ozbird (127571) | about 5 years ago | (#28902855)

Sounds like the cryptographers need to do their belts up a notch; nobody likes to see AES cracks.

Practical? (5, Insightful)

GigsVT (208848) | about 5 years ago | (#28902211)

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:Practical? (1)

jaysonsings (1608093) | about 5 years ago | (#28902233)

bruce schnier said this is no big deal. and he know. the media is hyping this but not a thang to worrie about.

Re:Practical? (0)

Anonymous Coward | about 5 years ago | (#28904831)

bruce schnier said this is no big deal. and he know. the media is hyping this but not a thang to worrie about.

You should be pulled into the street and garrotted with a shoelace.

Whatever subhuman sludge-pile put a keyboard in front of you should be shot.

Re:Practical? (5, Informative)

UltimApe (991552) | about 5 years ago | (#28902337)

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:Practical? (1)

DarkOx (621550) | about 5 years ago | (#28903837)

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:Practical? (0)

Anonymous Coward | about 5 years ago | (#28904827)

Switching from one broken hash function to another broken one is a good idea?

Re:Practical? (0)

Anonymous Coward | more than 4 years ago | (#28910047)

Asleep in class?

You can't use this vulnerability to inject code into something without the MD5 changing.

All you can do is create two things, one malicious and one not, which have the same MD5. From a cryptographic point of view this is quite different and much easier.

If you don't understand why those are different, you learned nothing in the class, pay attention next time.

Re:Practical? (1)

clone53421 (1310749) | more than 4 years ago | (#28926531)

...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:Practical? (2, Insightful)

Conley Index (957833) | about 5 years ago | (#28902701)

> 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:Practical? (1)

Joce640k (829181) | about 5 years ago | (#28903301)

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:Practical? (1)

QuoteMstr (55051) | about 5 years ago | (#28903645)

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 mode is also recommended, since reusing an IV can leak information about the first block. Sometimes you don't care, and in special circumstances when you can't generate a nonce, CBC may be the least bad option. But for general purpose use, you might as well start with CTR.

Re:Practical? (1)

Joce640k (829181) | about 5 years ago | (#28904069)

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:Practical? (1)

QuoteMstr (55051) | about 5 years ago | (#28904175)

He seems to be contradicting himself there - in CTR mode you can easily flip bits of the cyphertext then make a new MAC.

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 Protecting Communications [iacr.org] ".

Re:Practical? (1)

cperciva (102828) | more than 4 years ago | (#28913323)

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:Practical? (1)

stefancaunter (1198951) | about 5 years ago | (#28905967)

I trust Colin Percival implicitly. His speaking matches his writing to an astonishing extent.

Re:Practical? (1)

asdf7890 (1518587) | about 5 years ago | (#28902723)

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 have to support other algorithms as an option.

Unless you are working in an embedded environment with very little computing power available (so your hand is forced by what-ever algorithms your chosen CPU/chipset has built-in hardware functions for) or are hashing *massive* amounts of data and the hashing is a significant bottleneck, the computational complexity difference between MD5 and SHA1 is not significant so why not use the method that is generally considered more future proof at this point?

Re:Practical? (0, Redundant)

m50d (797211) | about 5 years ago | (#28902813)

The "programmer on the streets" should not be writing crypto code; it needs to be written or at the absolute least audited by specialists. And they have the expertise to understand these things; it's their job.

Re:Practical? (1)

rtechie (244489) | about 5 years ago | (#28903513)

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:Practical? (1)

jhol13 (1087781) | about 5 years ago | (#28906535)

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... (1)

gweihir (88907) | about 5 years ago | (#28902297)

... 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 (5, Insightful)

al0ha (1262684) | about 5 years ago | (#28902339)

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.

Re:The beauty of public cryptographic algorithms (5, Funny)

natehoy (1608657) | about 5 years ago | (#28902421)

Like one of my bosses once said, years ago, "If we implement industry standards in our processes, then we'll be doing things just like everyone else does! Where's the competitive advantage in THAT?"

Re:The beauty of public cryptographic algorithms (0)

Anonymous Coward | about 5 years ago | (#28902599)

I don't know if that was ironic, stupid, or just outside the box revolutionary thinking.

Speaking as an investor, I like to see a balance between innovative thinking and established best practices, though.

Re:The beauty of public cryptographic algorithms (1)

DigitAl56K (805623) | about 5 years ago | (#28902459)

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.

Re:The beauty of public cryptographic algorithms (0, Redundant)

T Murphy (1054674) | about 5 years ago | (#28902631)

I'm trying to come up with a joke here but I can't come up with something absurd enough that the pointy-hairs wouldn't try it.

Re:The beauty of public cryptographic algorithms (0)

Anonymous Coward | about 5 years ago | (#28904879)

The best minds in the world work on cracking them and come up with theoretical proofs of a weakness which ultimately prove to everyone

Hold it right there. The best minds in the world work for the NSA, and while they do crack stuff and prove stuff, their results aren't made public.

Shuda gone with Blowfish stupid american nists (0)

Anonymous Coward | about 5 years ago | (#28902357)

Shuda gone with Blowfish those stupid american nists. Ulana that!

Not sure if its time for AES2, but... (3, Interesting)

mlts (1038732) | about 5 years ago | (#28902673)

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.. (2, Insightful)

Nom du Keyboard (633989) | about 5 years ago | (#28903515)

attacks only get better and better, so every decade or so, maybe it would be time to consider another standard encryption algorithm.

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:Not sure if its time for AES2, but...BUT THIS.. (0)

Anonymous Coward | about 5 years ago | (#28903913)

But there isn't anything that's going to protect that data once AES is (hypothetically) broken.

So it has no bearing on whether or not to move off of AES.

Re:Not sure if its time for AES2, but...BUT THIS.. (0)

Anonymous Coward | about 5 years ago | (#28904457)

But will the data still be useful when the crack comes? If not, then the encryption did it's job for it's time. NO ENCRYPTION IS ETERNALLY SECURE!

Never say 'never' in cryptography! (1)

jonaskoelker (922170) | about 5 years ago | (#28908083)

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 ;-)

Re:Not sure if its time for AES2, but...BUT THIS.. (0)

Anonymous Coward | more than 4 years ago | (#28920065)

What data that you have today will still be of value (excepting historical and entertainment purposes) in 100 years?

My point is, that the encryption only has to hold until it does not matter if the information becomes known or not.

So, moving to a better encryption may do nothing for currently encrypted data, but current encryption could hold long enough for it not to matter.

Re:Not sure if its time for AES2, but... (1)

FutureDomain (1073116) | about 5 years ago | (#28906055)

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:Not sure if its time for AES2, but... (0)

Anonymous Coward | about 5 years ago | (#28907987)

I have heard a lot of good about the Serpent cypher. It definitely is a strong candidate, else TrueCrypt would not include it as one of the main algorithms it uses.

Even if AES is not broken, perhaps it is a good idea to have a new standard cryptographic algorithm designed every 10-15 years. This is because there are always new ways being made remove key space from existing algorithms. One thing about security is to always keep moving so one is ahead of the black hats. (Of course, one needs to be careful and spend a lot of research making sure the algorithm is secure, passing it between lots of eyes, from academic researchers to those working for intel agencies.) Right now, there isn't a hurry, AES is still doing a great job of protecting information. However, it can't hurt to have work being done on what will replace it in 5-10 years. I'd like to see a 256 bit key standard across the board, and perhaps either a 128 bit or 256 bit block size.

Re:Not sure if its time for AES2, but... (1)

evilviper (135110) | about 5 years ago | (#28906339)

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.

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, but damn slow, which is one of the major reasons for AES. The very large keys possible with AES mean it should remain practical for a long time.

And have you ever heard of the Soviet Union? They were highly interested in cracking DES for a lot more reasons than the mere challenge of it... More than mere MONEY was on the line.

Re:Not sure if its time for AES2, but... (0)

Anonymous Coward | about 5 years ago | (#28907205)

You are right. DES has not been attacked in any meaningful way, but its keyspace is so low by today's standards that even with TDES, the key is a bit small.

DES's blocksize is also 64 bits. For small sections of data, this not an issue, but once you get into terabytes, an attacker can in theory start figuring out a key. This is why modern algorithms use 128 bit (or variable size) blocks.

aes cracks (0, Redundant)

pornolar (1609697) | about 5 years ago | (#28902699)

So I guess this is an AES-hole? ------------- porno izle [hardpornolar.com] sikis [onlinesikisler.com]

TwoFish (1, Interesting)

Nom du Keyboard (633989) | about 5 years ago | (#28903407)

They should have picked TwoFish.

Re:TwoFish (2, Interesting)

QuoteMstr (55051) | about 5 years ago | (#28903529)

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:TwoFish (1)

afabbro (33948) | about 5 years ago | (#28903667)

One of the comments on Schneier's site was that Serpent/Twofish was largely scored down because of speed (which was one of the design criteria). If more rounds are added to AES, its advantage over Serpent may vanish.

Re:TwoFish (1)

QuoteMstr (55051) | about 5 years ago | (#28903679)

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:TwoFish (0)

Anonymous Coward | about 5 years ago | (#28903897)

No, the cardinal sin is spending more resources on security than the value of what you're securing. Fast, good-enough algorithms are useful in many applications.

Re:TwoFish (1)

dido (9125) | about 5 years ago | (#28906109)

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 AES was speed in resource constrained environments such as microcontrollers and smart cards. I believe Bruce Schneier once said something to the effect that any bloke knowing the construction theory of block ciphers can design one that is all but impervious to the publicly known cryptanalytic attacks, but it's quite likely that such a design will be unusably slow. (too lazy to look up the reference, but I believe he said something like this at around the time AES was declared) The real challenge in block cipher design is designing a reasonably secure cipher that is also efficient.

Re:TwoFish (0)

Anonymous Coward | about 5 years ago | (#28907575)

I have heard this logic before, and I think it's a good idea for hardware implementations.

But who TRUSTS hardware implementations? It's years down the road, and every hardware implementation of AES that *I* can buy has the key in some place on a the drive, and my password locks and unlocks that key, and the drive manufacturer has the key somewhere in plaintext. Vulnerable to subpoena, disgruntled employees, clever hackers, etc. The open source software implementations fully LACK this disadvantage, yet they don't support (talking truecrypt here, and the nice encryption libraries Linux has) multi round variants like you offhandly discuss- they support the standard (128 AES), the 256 version, and twofish and serpent.

So how much more secure can I get for 100x as slow? Because that seems like a good deal to make, with hard drive speeds so much faster now than in 96, and processors having WHOLE BONUS CORES compared to back then.

Besides how can you even really TRUST code that runs as part of a microcontroller on some board?

Re:TwoFish (0)

Anonymous Coward | more than 4 years ago | (#28927663)

Besides how can you even really TRUST code that runs as part of a microcontroller on some board?

Um, you're asking the guy who wrote it...

Re:TwoFish (2, Interesting)

whoisisis (1225718) | about 5 years ago | (#28903603)

> 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:TwoFish (1)

TheRaven64 (641858) | about 5 years ago | (#28903803)

Technically, we'd still be reading about a new 'veakness' in AES, because AES was the name given to the algorithm that won the context. Rijndael would still be called Rijndael, TwoFish would be called AES.

Re:TwoFish (0)

Anonymous Coward | about 5 years ago | (#28904911)

They should have picked TwoFish.

I say we move on to RedFish.

Welcome to the world (1)

AHuxley (892839) | about 5 years ago | (#28903887)

of Enigma and Crypto AG :)
Hi the the NSA and GCHQ :)

Clarifications (1)

jcrivello (1268622) | about 5 years ago | (#28903979)

Schneier was asked about this at BlackHat and talked about it further at DefCon.. so I will clarify a few things that are inaccurate/incomplete in the original submitter's story since I was at both..

The new attack is only "completely practical" in the sense that it has a 2^40 complexity for 10 rounds, but... similarly to the other papers it is a related key attack. Related key attacks are almost never applicable to the real world. The only case that I can think of where a related key attack was used in a real attack on a crypto system were the old WEP attacks. See Wikipedia for details: http://en.wikipedia.org/wiki/Related_key_attack [wikipedia.org]

Also don't forget that 10 rounds are less than 14, 14 being the standard for AES-256.

Schneier shed some light in the BlackHat talk on why AES-256 is ironically now considered more secure than AES-128. The new attack builds off weaknesses in the key schedule which is apparently the same for AES-128, 192 and 256. The key schedule seems "good enough" for 128 and potentially 192 bits but when you get to 256 bits there is simply not enough "churning" going on. This will be a great case study for proving "more bits != better" in the future.

So if you have to use AES use the 128 or 192-bit key lengths. This attack does not prove AES is insecure but rather only that the key schedule of AES is not good enough for it's longer key lengths. It certainly does cast AES in a negative light though and could be a premonition of a practical real world break sometime in the future.

Schneier also commented that there are two possible fixes:

1) NIST could amend the standard to "AES-1" or something (similar to SHA -> SHA-1) and apply a very simple quick fix by significantly increasing the number of rounds. Schneier commented that this was probably the easiest and most reliable fix.

2) Similar to Triple DES we could create a Double AES standard which doubles up the key size and per block passes. Schneier commented that he thinks that this _might_ be a good idea but also said that he might change his mind later.

Schneier was also asked in the BlackHat talk when the next AES competition would start and amusingly responded that if you called up NIST and asked them that they would probably hang up on you (because they are so busy with SHA-3 right now). So definitely not until after 2012 when the SHA-3 competition ends at the very soonest.

Re:Clarifications (1)

QuoteMstr (55051) | about 5 years ago | (#28904117)

So definitely not until after 2012 when the SHA-3 competition ends at the very soonest.

If Skein [wikipedia.org] wins the competition, we get Threefish [wikipedia.org] , a perfectly good block cipher, for free.

Re:Clarifications (1)

jcrivello (1268622) | about 5 years ago | (#28904217)

Granted, but Threefish would not be "AES version 2" for use as a general purpose block cipher by NIST. Although as you imply it's sort of standardized indirectly. Still though, 90% of the folks out there that just go with the latest buzz words, trends and standards would not jump for Threefish unless it were standardized specifically for use as a general purpose block cipher by NIST or some other big standards body.

Re:Clarifications (0)

Anonymous Coward | about 5 years ago | (#28907439)

Perhaps, but Threefish is a little too weird as it stands to propose as a conventional block cipher. (Decryption slower than encryption? Bizarro world!) It'd make a brilliant expansion function though.

Re:Clarifications (1)

jcrivello (1268622) | about 5 years ago | (#28904159)

Sorry.. to clarify my own post I said the second stated option for short term fixes would be to create a Double AES standard that "doubles up the key size and per block passes". That was actually partially incorrect; the proposal was to double up the AES passes with a single key, e.g. C = AES(K,AES(K,P)) to encrypt P to C.

http://www.schneier.com/blog/archives/2009/07/another_new_aes.html#c386973 [schneier.com]

Schneier directly referenced this comment in answering the question at the BlackHat talk.

Consider best attacks against DES and SKIPJACK (1)

onionman (975962) | about 5 years ago | (#28904549)

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.

I want to see attacks on Twofish and RC6 (1)

kriston (7886) | about 5 years ago | (#28905929)

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.

Oh NO! (0)

Anonymous Coward | about 5 years ago | (#28906325)

Amateur Electronic Supply is being attacked!! What dastardly deed will these hackers think of next!!!

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?
or Connect with...

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>