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!

New AES Attack Documented

timothy posted about 5 years ago | from the ponder-don't-panic dept.

Encryption 236

avxo writes "Bruce Schneier covers a new cryptanalytic related-key attack on AES that is better than brute force with a complexity of 2^119. According to an e-mail by the authors: 'We also expect that a careful analysis may reduce the complexities. As a preliminary result, we think that the complexity of the attack on AES-256 can be lowered from 2^119 to about 2^110.5 data and time. We believe that these results may shed a new light on the design of the key-schedules of block ciphers, but they pose no immediate threat for the real world applications that use AES.'"

cancel ×

236 comments

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

Gordon Moore Says Best (-1, Troll)

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

Well, AES is in for a big one! [nimp.org]

Uhm...READ THIS FIRST (-1, Troll)

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

You might want to try going here [google.com] instead...

Improvement (0)

WaXHeLL (452463) | about 5 years ago | (#28550479)

That's only a 0.3% improvement!

Re:Improvement (3, Informative)

WaXHeLL (452463) | about 5 years ago | (#28550503)

erm only a 99.7% improvement.

Actually, nerdless wanna be, 1 bit = 100% stronger (0)

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

If 128 bits is good enough, 129 bits is twice as good as good enough. 130 bits is 4x, 131 is 8x, and so on. I am aware that nerdless wanna bes will never grok this binary stuff, but I know you don't know, and that's all that needs to be known, for the both of us.

Yawn (2, Insightful)

Shikaku (1129753) | about 5 years ago | (#28550501)

So instead of taking 1 million years to brute force, it will take .9 million years?

I totally made up those numbers but that's about the difference.

Re:Yawn (0)

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

nach, instead of a trillion years it now takes only a billion.
thats about the difference.

and if you add more computers (a datacenter or such) and add new mathematics, this number will go down further, to say a thousand years.
thats where everybody using this should start worrying

Re:Yawn (1, Interesting)

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

The article seems to say that AES 256 can be lowered from 2^256 to 2^110.5... that's huge. For your example, if 2^256 iterations takes 1 million years, 2^110.5 iterations would take less than a second.

Re:Yawn (4, Informative)

a_n_d_e_r_s (136412) | about 5 years ago | (#28551301)

Given that the new theory lowers the time to break it with about 99.7% if it before took 1 million years it now only takes 3000 years.

Remember for everý less bit it takes to decrypt - it halves the time it takes to break a cipher.

Obligatory XKCD quote (5, Funny)

snikulin (889460) | about 5 years ago | (#28551685)

Security [xkcd.com]

Complexity (2)

techno-vampire (666512) | about 5 years ago | (#28550509)

TFA refers (as does the summary) to complexity of 2^119, and possibly lowering it to 2^110.5. Could somebody rephrase that in a way that people like me, who aren't cryptography specialists can understand what they're talking about?

Re:Complexity (3, Insightful)

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

I believe the complexity is a rough measure of how long it should take to break the code. So in this case, a reduction from 2^119 to 2^110.5 is approximately 360 times faster (that is, a 2^119 complexity attack takes 360 times as long as a 2^110.5 complexity attack).

Re:Complexity (2, Informative)

wealthychef (584778) | about 5 years ago | (#28550613)

Normally, "complexity" in computer science refers to how long it takes to do a given task, given the size of the task. It's usually expressed as O(blah), read, "Order of blah". For example, an O(n^2) ("order n squared") complexity means that if it takes "m" minutes to finish a problem of size x, then it will take 16m minutes to finish a problem of size 4x. I'm not familiar with the term "complexity" being used in this context and with these specific numbers.

Re:Complexity (1)

techno-vampire (666512) | about 5 years ago | (#28550773)

It's usually expressed as O(blah)...

Yeah; I know, and I'd not have wondered if they'd expressed it that way. It's good to know that I'm not the only reader that doesn't understand the terminology.

Re:Complexity (4, Informative)

vux984 (928602) | about 5 years ago | (#28550809)

Could somebody rephrase that in a way that people like me, who aren't cryptography specialists can understand what they're talking about?

Sure I'll rephrase it for you. "Don't worry."

What? You wanted something deeper without having to know anything? Ok...so AES was thought to require 2^128 time units to brute force. So 2^119 time complexity means essentially that the new algorithm takes 2^119 units of time to complete which is a lot better, and they think it might be able to optimize it down to 2^110 units of time.

What a 'unit of time is' is a computing science hand-wave because it doesn't really matter what it is. When comparing algorithms for large problems you are interested in how it compares relative to other algorithms, not how much absolute time it will take on a Commodore 64 or Intel i7 or whether its programmed in Smalltalk vs C. Those details while important in their own right aren't really relevant to the comparison of the algorithms themselves.

A 2^110 algorithm is significantly better than a 2^119 algorithm for 'large problems' regardless of what we set the unit of time to be, and in turn 2^119 is much better than 2^128.

In practice the unit of time is rooted in how long it takes a computer to do 'an operation'. So it might be milliseconds or nanoseconds, or whatever. And the upshot is that even 2^110 is STILL gazillion years even if its programmed in C on an i7 and every i7 on the planet is contributing to the effort...

Hence... "Don't worry."

Its mathematically very interesting, but for the moment, its nothing to "worry" about.

Re:Complexity (1)

techno-vampire (666512) | about 5 years ago | (#28551657)

What? You wanted something deeper without having to know anything?

Not quite. I wanted to learn enough to understand what they were talking about, even if I couldn't follow the math they used in the proof, and that you (and a few others) have given me. Thank you.

Re:Complexity (1)

jrl87 (669651) | about 5 years ago | (#28550891)

Basically they're looking for weaknesses in the encryption or a way to break the encryption. The basic idea is that if you have a x-bit key for you encryption system then you should be able to generate 2^x different keys. So for instance if you had 4-bit encryption, then you would have 4 bits that you could assign a value to. That is you have something like _ _ _ _ where each _ can be either a 1 or a 0. When you work out the number of unique ways you can make this assignment you get 16, or 2^4.

To break the encryption, you need to find the key. In the 4-bit example above, it is easy you just try all 16 of the possibilities. Now, if you raise the encryption strength to say 256-bit, you have 2^256 theoretically possible keys. Now, if you assume that you can check 30,000 keys per second it would take you well over a million years to check all of the keys (actually somewhere on the order of 10^60 years). So doing that is obviously not a practical solution.

So what they're doing is trying to find a method that is more efficient. There are sometimes reasons why certain keys don't need to be tested and there are statistical methods that should theoretically be more efficient that simply randomly trying keys. So previous to this study they think the complexity is 2^119. Though it's not quite right, you can think of this as the average number of keys you would have to try before getting the right one. With the method they are suggesting they are claiming that the complexity could be lowered to 2^110.5. Practically speaking, this doesn't really make cracking the key any easier. But in the future, who knows ...

Re:Complexity (1)

Cajun Hell (725246) | about 5 years ago | (#28550931)

It means it just got roughly 400 times faster.

Re:Complexity (1)

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

No, 119 to 110.5 is the amount they predict this attack could be improved with more work.

If it reduces an attack 256-bit AES to 2^119 complexity then it's 2^137 times better, and 2^137 times better is half a metric asston.

Re:Complexity (0)

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

No, there's already a simple time/memory tradeoff attack that reduces AES-256 to 2^128 in time and space, so they were just reducing it from 128 to 119, which is 512 times better.

Re:Complexity (2, Funny)

jcwayne (995747) | about 5 years ago | (#28551481)

... 2^137 times better is half a metric asston.

I measure algorithmic complexity in imperial asstons, you insensitive clod.

Re:Complexity (5, Informative)

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

It means you only have to test 2^119 possible keys to break 256-bit AES - still far beyond what's ever going to be feasible (do the math - give everybody on the planet a million PCs running at 1THz and see how long it takes to do 2^119 things, then figure out where you're going to get that much electricity from)

Interesting to note is that AES-128 is immune to this attack - it's now the strongest variant of AES. Everybody (like me) who thought the 256-bit and 192-bit were a waste of time now has a reason to be smug about it.

Reason: Both AES-192 and AES-256 are just AES-128 internally but they mess around with the key data between each loop of the encryption process. The new attack only works on the "messing around" part of the process so AES-128 is unaffected.

Re:Complexity (1)

techno-vampire (666512) | about 5 years ago | (#28551589)

Thank you. However, one question remains: is that the maximum number of keys, or the average number. Either way, of course, it's a huge number, but it does make a difference.

Re:Complexity (1)

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

That's the maximum, the average would be half that.

...unless they're expecting you, in which case they can put the key towards the end of the keyspace to make it take longer. You could of course anticipate that move and start searching at the end but in return they could anticipate that and put it at the beginning. It's a Sicilian mind game.

Re:Complexity (0)

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

I love that this got moderated redundant while a post that is essentially the same that comes AFTER this one gets modded insightful.

Oh look, that one was by a girl! Let's mod her up! WOWOWOWOWOWOWOWOWOWOW

Furthers my stand on crypto, which is: DON'T (4, Funny)

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

Crypto is broken. It's not IF, but WHEN. That's why crypto is pointless to use. this is why I use open source, and even keep all doors unlocked. It's pointless to try and protect propery, real or intellectual/imaginary.

Re:Furthers my stand on crypto, which is: DON'T (1)

wealthychef (584778) | about 5 years ago | (#28550557)

It's pointless to try and protect propery, real or intellectual/imaginary.

Really, would you mind posting your credit card information here please? Also your home address? I didn't think so.

Re:Furthers my stand on crypto, which is: DON'T (1)

The End Of Days (1243248) | about 5 years ago | (#28550615)

I get your point, but logically your response doesn't refute the OP directly.

Re:Furthers my stand on crypto, which is: DON'T (4, Insightful)

droopycom (470921) | about 5 years ago | (#28551249)

Refutation: Crypto is indeed all about WHEN. WHEN is not pointless, it is the point.

Re:Furthers my stand on crypto, which is: DON'T (1)

caluml (551744) | about 5 years ago | (#28550985)

You can have it AES-256 encrypted if you like.

Re:Furthers my stand on crypto, which is: DON'T (1)

droopycom (470921) | about 5 years ago | (#28551213)

The point of cryptography is to protect stuff for a sufficiently long amount of time.

So you are right, its all about WHEN. WHEN IS the point, and is not pointless.

Complexity. (4, Funny)

girlintraining (1395911) | about 5 years ago | (#28550517)

For those who don't have a degree in oh-shit-that's-a-big-number, can someone give a comparative analysis of what "2^119" complexity means? I mean what else is "2^119" hard to solve? And yes, the math nerds are undoubtedly either dying of laughter or yelling at the screen for my abuse of powers of two... I don't care.

Re:Complexity. (0)

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

I'll assume you know what asymptotic notation is. If an algorithm is O(2^n) then for every unit increase in the size of the input, the time to complete doubles. This algorithm takes 2^119 steps on a 256 bit input (AES-256). Which is a lot.

Re:Complexity. (4, Informative)

xZgf6xHx2uhoAj9D (1160707) | about 5 years ago | (#28550631)

AES-128 uses keys which are 128 bits long. That means in order to "break AES" (in order to decrypt something you don't have the key to), all you have to do is try all possible keys of length 128 until you find one that works. That means you would have to try 2^128 different combinations, which is a lot.

What these people have done is found some clever way where you can break AES trying only 2^119 combinations. Effectively this means AES is no better than if it had used 119-bit keys instead of 128-bit keys. Sometimes you'll hear this colloquially as something like "AES has 119 bits of security", referring to how many combinations of keys you have to try before you find the one works.

2^119 is a massively large number. Trying 2^119 combinations is still terribly far outside of the realm of what all of the world's most powerful supercomputers combined could hope to do. This is an attack of theoretical interest, not practical interest.

Re:Complexity. (5, Insightful)

cpu_fusion (705735) | about 5 years ago | (#28550725)

Pardon me, but isn't the article about AES-256? So this is a much more significant drop in the number of bits.

Of course, I've only read the summary. This is slashdot, natch.

Re:Complexity. (1, Insightful)

xZgf6xHx2uhoAj9D (1160707) | about 5 years ago | (#28550761)

Oh dear, you're absolutely right. This is about AES-256. That's quite a significant attack indeed (though still not enough to make it practical).

Re:Complexity. (2, Informative)

dermoth666 (1019892) | about 5 years ago | (#28551083)

I believe the probability being halved has something to do with the birthday paradox. It's been a time where I could explain this better; if you wish to find out just search for it on Google... This page seems to have a good explanation too:

http://betterexplained.com/articles/understanding-the-birthday-paradox/ [betterexplained.com]

Re:Complexity. (2, Interesting)

BitterOak (537666) | about 5 years ago | (#28551193)

I believe the probability being halved has something to do with the birthday paradox.

Actually, that just applies to secure hash functions (like MD5 and SHA, and the like) and not to block ciphers. If AES-256 can be cracked with only 2^119 calculations, that is a HUGE drop in security.

The reason that hash functions really only give you half as many bits of security as you have bits in the digest is that a hash is considered broken if you can find two messages which have the same hash. Since you can vary both messages, you only have to try 2^(n/2) as many, just like the birthday "paradox".

Re:Complexity. (1)

wirelessbuzzers (552513) | about 5 years ago | (#28551691)

It's a time/memory/data trade-off. If you have 2^128 AES-256-encrypted copies of a known plaintext, you can already find one of the keys using 2^128 time. You just encrypt using 2^128 random keys and find collisions.

This attack does better by a factor of 2^9 = 512 if the keys are related in some way known to (or maybe chosen by) the attacker. They think they can get another factor of 2^9 out of it with a more careful analysis. Even so, this is only a theoretical weakness.

Re:Complexity. (2, Informative)

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

Except IYRTFA, the attack only works on AES-192 and AES-256. AES-128 is unaffected, which would seem to imply that, oddly, AES-128 could be stronger than AES-256 and AES-192 in some circumstances.

Re:Complexity. (2, Informative)

betterunixthanunix (980855) | about 5 years ago | (#28551185)

This is an attack on key schedules; the key schedule of AES-128 is different from that of AES-192 and AES-256, thus rendering it impervious to this particular attack. As the authors note, this sheds new light on key schedule design, much in the same way that differential cryptanalysis shed light on S-box design.

Re:Complexity. (1)

Skuto (171945) | about 5 years ago | (#28551429)

Not really. The thing is that a break against AES-256 can use up to 2^256-1 operations and be considered faster than brute force. The same technique wouldn't count as a break against AES-128, because that is brute forceable in 2^128 anyway.

If there's an attack against AES-256 that takes 2^200 operations, it's considered a break. But this is still more effort than the one needed to just brute force AES-128. So AES-256 would still be more secure.

Re:Complexity. (5, Informative)

quercus.aeternam (1174283) | about 5 years ago | (#28550793)

Two things:

First, they are talking about AES-256.

Second, I find it useful to think about how much faster that is. In this case, it means it is 2^137 times faster than a pure brute force attack, which certainly seems impressive. Fortunately, as you mentioned, this is still far too difficult to be applied.

Just for fun, google this: 2^119 picoseconds in millenia

Re:Complexity. (3, Informative)

electrostatic (1185487) | about 5 years ago | (#28551483)

Just for fun, google this: 2^119 picoseconds in millenia.

Google says:

2.10607966 × 10^13 millenia -- which equals about 21,000,000 billion years

With the new attack the figure is 2^110.5 trys, which is

(2^110.5) picoseconds = 5.81727815 × 10^10 millenia

a mere 58,000 billion years.

Looking at it another way, 119 - 110.5 = 8.5, which is the reduction of the exponent, giving 2^8.5 = 362. So knocking off 8.5 bits reduces the amount of time+effort by that ratio.

"Picosecond" is the assumed amount of time it takes for one attempt here, which I assume is reasonable given a massively-parallel attack machine.

Still, 58 trillion years...

Re:Complexity. (5, Interesting)

AlHunt (982887) | about 5 years ago | (#28551597)

>Just for fun, google this: 2^119 picoseconds in millenia

And for even more fun - 64 minutes after the parent posted, the post itself was the first result.

Re:Complexity. (1)

Kjella (173770) | about 5 years ago | (#28551641)

I think that's the only kind of number that makes sense without using the 2^x notation - 137 bits broken, 119 bits of strength left. It's lost over half the bitstrength. If it'd been the same for 128 bit keys, it'd be well into crackable ranges. That's really the big issueeasily here, why would this NOT affect 128 bit AES? Did they do something really, really smart in that version that leaves them immune? Or is it rather we don't want to set of every alarm bell there is?

Re:Complexity. (3, Interesting)

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

2^119 is a massively large number.

664613997892457936451903530140172288

Meh. I've seen bigger.

Re:Complexity. (2, Funny)

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

that's what she said.

Re:Complexity. (0)

DriedClexler (814907) | about 5 years ago | (#28550885)

AES-128 uses keys which are 128 bits long. That means in order to "break AES" (in order to decrypt something you don't have the key to), all you have to do is try all possible keys of length 128 until you find one that works. That means you would have to try 2^128 different combinations, which is a lot.

What these people have done is found some clever way where you can break AES trying only 2^119 combinations.

Pff. Well if that's all they're claiming, then even I can do better. Hint: don't guess composite numbers! The two factors you have to find are prime!

Re:Complexity. (1)

Chabo (880571) | about 5 years ago | (#28550959)

Yes, but how do you know if the potential factors are prime? Do you keep a giant list/table, or do you attempt to factor the potential prime?

Re:Complexity. (1)

NAR8789 (894504) | about 5 years ago | (#28550963)

...and how, might I ask, are you generating your primes?

Re:Complexity. (3, Informative)

tabrisnet (722816) | about 5 years ago | (#28551003)

Bull.

a) AES is not based on prime numbers, nor is it a public-key cipher. you're thinking RSA or some other public-key cipher. Hence why RSA has to be at least 1024 (and now 2048 and up is recommended) bits long.

b) There's a lot more bull going around here. AES256 was believed to require 2^128 operations to bruteforce, not 2^256. Thus any question of 256 -> 119 is bull. It's 128 -> 119.

c) Brute-forcing a 64bit RC5 key took distributed.net years (and note that that was with the benefit of Moore's [so called] Law). Mind you, that actually required searching a 64bit keyspace.

Re:Complexity. (2, Funny)

DriedClexler (814907) | about 5 years ago | (#28551327)

Note to self: never try to tell a cryptography joke.

you wet your pants (1)

epine (68316) | about 5 years ago | (#28551741)

Good life strategy: if you truly don't understand something, and you're not interested in learning, make a joke about it. Those who laugh identify themselves as your peers, while the rest of us will (normally) engage in a silent shunning so you'll never have to confront the anguish of feeling uniformed.

Not knowing the difference between a block cipher for bulk encryption and a public key cipher for key exchange is on par (in this neck of the woods) with not knowing the difference between a debt and a deficit, or the difference between mass and weight. You might wish to append finance and physics to your note to self.

What I don't get is your mirth circuit determined that a discussion on a cryptographic attack was in need of a mirth tweet, as if this kind of thread isn't drowning in misinformation/misunderstanding 99% of the time.

Around the advent of Netscape, I briefly dabbled in an online MUD of the tedious variety. In the name of realism, your character had to sleep a lot. The game did have one good feature. You would go "con bartender" (short for "consider kicking bartender's ass") and the game would respond "you wet your pants" if you were hopelessly outclassed.

> con mirth zeta function
You wet your pants!

Well, we can dream.

Re:Complexity. (1)

dermoth666 (1019892) | about 5 years ago | (#28551135)

As far as I know, besides primes there's a bunch of random data that gets in key generation. Knowing the primes only make it slightly easier to crack the key.

By default PGP use a known set of primes to generate keys, and so far keys generated by it are still secure.

Re:Complexity. (1)

bmajik (96670) | about 5 years ago | (#28551035)

Not only is 2^119 a big number...its around 6e35.

Wolfram says that the milky way galaxy weighs around 6e45 grams.

assuming 1 mol of electrons in 1 gram of galaxy, you're talking about 3e69 electrons in the whole galaxy.

I suppose it might be possible within the confines of our galaxy to do something 2^119 times. We do have enough electrons. That's an important upper bound to not violate.

Re:Complexity. (1, Funny)

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

Why limit yourself to electrons? Photons man, photons - they're the new "it" particle for computation!

Re:Complexity. (1)

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

If I'm reading the paper correctly, it appears that AES-128 is unaffected. (Please correct me if I'm wrong!)

Re:Complexity. (0)

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

If you had a computer that could perform 7 libraries of congress per hogshead, it would take 4563 quintillion hectares to do the Kessel run in under 12 parsecs (per milliliter squared)

Re:Complexity. (1)

sammykrupa (828537) | about 5 years ago | (#28550709)

Well just look at how fast the numbers double:

1, 2, 4, 8,16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576
2097152
4194304
8388608
16777216
33554432
67108864

2^30 = 1 073 741 824
2^60 = 1.1529215 Ã-- 10^18

2^60 IS NOT one less than 2^61, it's HALF.

Re:Complexity. (1)

cperciva (102828) | about 5 years ago | (#28550741)

I mean what else is "2^119" hard to solve?

Finding a file which has an MD5 hash of either 000000000000000000000000000000XX or 000000000000000000000000000001XX for some pair of hexadecimal digits XX.

Computing the 2^100th bit of Pi (approximately -- the BBP algorithm has some factors of log thrown in, so I've dropped a factor of 2^19 to account for those).

Sorting a list of 31 elements using bogo-sort.

Re:Complexity. (2, Interesting)

godrik (1287354) | about 5 years ago | (#28550747)

A couple of years ago (2003), a cryptographic system was said to be secured if it requires more than 2^80 computation. I do not know what is the current standard and I have no clue how to find it.
However 2^110 is still way to large for us at the moment.
To give an estimation. Supose you have one million processors clocked at 10Ghz (which nobody have nowadays), you can do 10^6 * 10^10 = 10^16 ~= 2^48 computations per second. To crack AES and using this machine you'll need 2^110 / 2^48 = 2^62 seconds to do so which is approximatively 150 billions year.
The attack is of theoretical interest mainly but should tell people not to use AES with a cryptographical key smaller than 256.

Re:Complexity. (1)

Mike Buddha (10734) | about 5 years ago | (#28550823)

The attack doesn't work in AES-128 or AES-192. It only works on AES-256.

Re:Complexity. (1)

a_n_d_e_r_s (136412) | about 5 years ago | (#28551151)

CPU power doubles about every 18 months (Moores Law) so every 3 years a new computor can decrypt 2 bits more in the same time frame.

Thus to get it down to 80 bits from 119 it will take 39 bits divided by 2 times 3 or in about 60 years the AES will become breakable.

However given that Moores law is starting to get hard to continue with - it might take smore time than that. By that time the new crypto standard will probably use 1024 bits to be safe.

Re:Complexity. (2, Informative)

RaymondKurzweil (1506023) | about 5 years ago | (#28551627)

CPU power doubles about every 18 months (Moores Law)

Moore's Law never claimed this.

Re:Complexity. (1)

nine-times (778537) | about 5 years ago | (#28550787)

Well I'm not particularly a math geek, but 2^10=1KB. 2^20=1MB. 2^30=1GB. And so on. So if you were storing 2^120 bits, it would be basically be a trillion trillion terabytes. Is that right? Someone feel free to check my math.

I mean, that doesn't give an explanation of the problem, so it doesn't really answer your question. But maybe it gives you an idea of scale? I guess by lowering the complexity of the attack by 2^8.5 it means that an encryption key that would take you 300 years to crack, you might now be able to crack it in a year...? I don't know. I'm not an encryption expert.

Re:Complexity. (1)

nine-times (778537) | about 5 years ago | (#28550991)

I'm confusing bits and bytes, so I'm wrong already. Oh well.

Re:Complexity. (0)

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

To get you an idea, it would take a billion computers trying 1 key every nanosecond more than 20 billion years to try out all the key combinations of 2^119.
 

Re:Complexity. (1)

SoVeryTired (967875) | about 5 years ago | (#28550955)

Well, it's the expected length of time you'd need to spend tossing a coin before you got 119 heads in a row. A very long time.

That's Today... (1)

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

but they pose no immediate threat for the real world applications that use AES.

Funny how news of just about every major break of an existing cryptography system or secure hash method has started out with just about those same exact words.

Re:That's Today... (1)

parvin (846446) | about 5 years ago | (#28550633)

That's because ~362x faster than effectively forever is still effectively forever.

Re:That's Today... (1)

Godji (957148) | about 5 years ago | (#28550681)

Examples?

Quantum Computers (2, Insightful)

religious freak (1005821) | about 5 years ago | (#28550643)

Yeah, this is interesting math, but I don't think our cryptographic scheme is in danger until quantum computers become a stable and reliable source of heavy computing. Then we're all in trouble. How do you create a key, when the entire large number method is made obsolete by quantum computing? I haven't looked into it much, but I don't think anyone has found an answer yet.

To my knowledge quantum cryptography is still limited to very close distances, while cracking a crypto key is obviously not affected by this limitation.

Re:Quantum Computers (0)

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

Aren't you effectively in the shit? I'm not quite sure what/how, but my sixth sense tells me that unless you have a secure means of communications (In which to transfer a one time pad, or something), you can't send any useful information and have it be impossible to read. Public key crypto seems to just bend this rule by making it damn difficult to read.

Re:Quantum Computers (2, Insightful)

JambisJubilee (784493) | about 5 years ago | (#28550825)

You are not in the shit. Secure communication can be established on an insecure channel using quantum cryptography. Look it up on Wikipedia.

Re:Quantum Computers (1)

Chyeld (713439) | about 5 years ago | (#28551021)

I did but the article kept telling me that I'd only know if I were in deep shit if I opened the box...

Re:Quantum Computers (1)

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

Quantum computers won't do much to break block ciphers, they'll only be useful against ciphers which rely on finding factors of large numbers.

The real-world applications for quantum computers are very limited.

Re:Quantum Computers (1)

Xtravar (725372) | about 5 years ago | (#28551453)

The government will require licenses to run quantum computers, and they'll be so fast that the FBI can run spyware on them without you noticing performance degradation! If you are innocent you have nothing to hide!!!

Re:Quantum Computers (4, Informative)

mathimus1863 (1120437) | about 5 years ago | (#28551713)

Parent is slightly off on the Quantum computing comment. Quantum computers can break cryptographic protocols based on the difficulty of integer factorization (RSA/PGP/GPG/PKI/SSL/TLS), and discrete-logarithms (all of the above plus elgamal, elliptic curves). However, AES is a block cipher which relies on neither of these pure-math problems.

The only advantage of QCs in breaking AES is that Grover's Algorithm can be applied for random guessing of the encryption key. AES-256 has 2^256 possible encryption keys. It takes a classical computer an average of n/2 guesses to find the right key, or 2^255 operations. However a QC running Grover's Algorithm does it in an average of approx sqrt(n) "guesses." This means that it takes about 2^128 operations to get the AES-256 key using a quantum computer.

As previous posters have mentioned, 2^128 is still far out of our reach. And to subvert QCs for this type of problem, all we have to do is double our key length to get the same security. Perhaps if we find a way to combine Grover's Algorithm with this new AES vulnerability, we can get it down to 2^60 to 2^64, but that is still extremely prohibitive. Additionally, that's a big "if," since Grover's Algorithm is intended for pure-guessing problems.

2^119 is... (5, Interesting)

AnotherBlackHat (265897) | about 5 years ago | (#28550757)

For those who are asking "what's 2^119 complexity mean?"

2^64 is about as hard a problem as we can reasonably solve these days.
2^80 is about as hard a problem as we can unreasonably solve. I.e. we can do it, but it would take the budget of a country for several years to do.
A can of soda has about 2^83 molecules in it.
2^119 is still way beyond anything we can reasonably do, but isn't so hard that we can rule out any theoretical possibility of solving it.
A house sized computer built of solid nano-compute units, each a few hundred molecules on a side, with a cycle time of about 10 petahertz could do it in less than a lifetime.
Perhaps possible but I wouldn't worry about it.
2^256 is so hard that it may not even be theoretically possible to solve - or maybe you could if you're willing to destroy a few solar systems, and wait a few million years.
While cracking 2^256 may not be theoretically impossible, it would be easier to look everywhere the information you want might be hidden - including inside the mind of your opponent - even if he's dead.

Re:2^119 is... (1, Interesting)

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

2^64 was solved by the EFF over a decade ago for less than $250K. Trivially by raw brute force. It's available to people with a bit of technical expertise and about $10k hardware budget as of maybe 3-5 years ago. It took them a few days then.

Look--I don't know what you consider reasonable--but calling 2^64 "about as hard as is reasonable". Maybe it isn't reasonable with your expertise, or on your desktop, or without a bit of dedicated budget--but it isn't just reasonable...it's *trivial* in a cryptographic context.

As far as I'm concerned, if it's below 2^128 it isn't good enough. Also--brute forcing 2^256 *is* theoretically impossible (at least, until you get into quantum mechanics).

Re:2^119 is... (2, Informative)

b00fhead (669286) | about 5 years ago | (#28551115)

No, EFF's Deep Crack [wikipedia.org] brute-forced 2^56 - a fair way from 2^64.

Re:2^119 is... (1)

Dahamma (304068) | about 5 years ago | (#28551417)

2^64 was solved by the EFF over a decade ago for less than $250K. Trivially by raw brute force.

Actually, it was DES they cracked, which uses 56 bit keys, not 64. A 64 bit key would take 256 times longer. That 56 hours Deep Crack took would be 597 days for a 64 bit key, which is not "trivial".

It's available to people with a bit of technical expertise and about $10k hardware budget as of maybe 3-5 years ago. It took them a few days then.

From their site, in 2007 (2 years ago) it took an average or 6.4 days. Use Moore's law and knock that down to, say 36 hours today. That's still over a year for a 64 bit key.

Look--I don't know what you consider reasonable--but calling 2^64 "about as hard as is reasonable". Maybe it isn't reasonable with your expertise, or on your desktop, or without a bit of dedicated budget--but it isn't just reasonable...it's *trivial* in a cryptographic context.

Over a year to decrypt a message is not trivial... though yeah, it's clearly not complex enough for truly sensitive data (ie anything worth either waiting a year or spending a few million bucks to decrypt).

Hello!! Person with Key, meet Rubber Hose (-1, Redundant)

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

Person with Key, meet rubber hose.
Rubber hose, meet person with key.

Guess how long that key will take to "break"? Can you say SMACK !! children? I thought so, children.

   

Re:Hello!! Person with Key, meet Rubber Hose (1)

Qzukk (229616) | about 5 years ago | (#28551235)

What a coincidence! I use the starting lineup of the Green Bay Packers for my encryption key too!

Re:2^119 is... (0)

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

While cracking 2^256 may not be theoretically impossible, it would be easier to look everywhere the information you want might be hidden - including inside the mind of your opponent - even if he's dead.

So you're saying that 256 bits should be enough for anyone?

Re:2^119 is... (4, Interesting)

Kjella (173770) | about 5 years ago | (#28551539)

So you're saying that 256 bits should be enough for anyone?

Unless you discover reversible computing, yes. Otherwise you could have an infinitely fast computer, but even the Sun at E=mc^2 and 100% efficiency couldn't do it. It's not a speed limitation, it's an energy limitation. Take the Landauer limit [wikipedia.org] at background radiation temperature [wikipedia.org] . Plug that into a calculator and you get joules required:

(2^256) * 1.3806504 * (10^(-23)) * 2.72500 * ln(2) = 3.0196359 * 10^54

Energy of sun:
1.98892 * (10^30) * (299 792 458^2) = 1.78755215 * 10^47

Re:2^119 is... (0)

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

of course, there is always the 2^119 chance that you just happen to guess the answer on the first try.

Where's the Hyperbole? (0)

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

...but they pose no immediate threat for the real world applications that use AES.'"

Wait a minute... where's the fear mongering, sensationalism and hyperbole? You call this reporting? I want my money back.

Re:Where's the Hyperbole? (1)

fuzzyfuzzyfungus (1223518) | about 5 years ago | (#28550973)

That quote is from a scientist, probably not a good source of hyperbole, on average. Just wait until a couple of quote/requote cycles have occurred, and you'll get Fox's "World's Scariest Cryptoanalytic breakthroughs: Do they threaten the children?"

Re:Where's the Hyperbole? (1)

maugle (1369813) | about 5 years ago | (#28551517)

Fox's "World's Scariest Cryptoanalytic breakthroughs: Do they threaten the children?"

Not frightening enough. Try "Coming up next: Have these scientists just told terrorists how to steal your children's identities?"

Re:Where's the Hyperbole? (0)

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

ZOMG!!! We gonna DIE!!!

Happy now? AC Wanker!

What about an AES 512 or 1024?? (1)

filesiteguy (695431) | about 5 years ago | (#28551005)

I don't know if the size of the hash has anything to do with the package or the resultant file, but what about simply doubling (or greater) the hash?

I did try to read the article, but got a bit lost when I began to read stuff like, "A basic boomerang distinguisher [12] is applied to a cipher EK() which is
considered as a composition of two sub-ciphers: EK(1) = E1 2 E0. The rst sub-cipher is supposed to have a dierential  ! , and the second one to have a..."

Man, it is hard being a PHB!

Re:What about an AES 512 or 1024?? (1)

Sique (173459) | about 5 years ago | (#28551645)

I don't know if the size of the hash has anything to do with the package or the resultant file, but what about simply doubling (or greater) the hash?

Here comes the irony: The attack is possible, because AES-256 and AES-192 are "extended" versions of AES-128. While AES-128 still goes strong, the extended versions are attacked, and their complexity is reduced to at least 2^119. AES-128 remains at 2^128.

Fixed SSL Link (1)

Mr. Sketch (111112) | about 5 years ago | (#28551121)

For some reason that SSL link to the paper uses the name of a server that doesn't have the SSL certificate so Firefox complains. Replacing the hostname gives this link that Firefox doesn't complain about:
https://www.cryptolux.org/mediawiki/uploads/1/1a/Aes-192-256.pdf [cryptolux.org]

Only one thing come to my mind: (1)

geantvert (996616) | about 5 years ago | (#28551123)

decrypting this disinformation (0)

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

Let me decrypt this disinformation for y'all. Namely:

"better than brute force with a complexity of 2^119"

If you lived a few days before this was discovered, you would expect "128 bits of security" in your AES. But now you only get 119. What's that extra 9 bits between friends? That's just a factor of 512. It means if a few weeks ago, someone would have had to pay $70 billion for hardware capable of decrypting your message within 600 days guaranteed (with an expected success time at the 300-day mark), now they only have to pay $136 million, obviously no big change. Oh and

"we think that the complexity of the attack on AES-256 can be lowered from 2^119 to about 2^110.5 data and time."

Which is another 8.5 bits, or a further factor of 362, leaving the tab at $377,000 for the equipment to brute-force your data within 600 days (with the expected success time at the 300-day mark). Really, it is hard to imagine how any organization might have $377,000 for such an activity but not $70 billion, so far as I can see this doesn't really change much of anything.

Yes. (1)

Estanislao Martnez (203477) | about 5 years ago | (#28551675)

It means if a few weeks ago, someone would have had to pay $70 billion for hardware capable of decrypting your message within 600 days guaranteed (with an expected success time at the 300-day mark), now they only have to pay $136 million, obviously no big change.

That is true in exactly the same way it is true that if it had rained during my walk yesterday, I would have gotten soaked.

My brain saw NES... (0)

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

... and wondered if perhaps there were some bad cartridges being distributed these days.

this a RELATED-KEY attack (5, Informative)

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

The usual threat model for a cipher is either a "chosen plaintext attack" (CPA) or a "chosen ciphertext attack" (CCA). In both of those, you have a lot of plaintext-ciphertext pairs all encrypted under the same key, and your job is to use that info against the cipher. Not necessarily to actually compute the key (which would totally destroy the cipher) but even to be able to infer anything about it statistically (for example, to have a better than random chance of guessing whether a new plaintext/ciphertext pair was encrypted with the same key).

This attack is a related-key attack, which traditionally means that you get to see the same plaintext encrypted under enormous numbers (like 2^119 in this case) of different but related keys, rather than under the same key (or a "small" number of keys like a few trillion). This is a threat model that most ciphers aren't designed against and it's instead countered by designing the application to not rely on it. For example, don't use the cipher as a hash function by using the plaintext as a key and encrypting some constant. Properly designed crypto applications don't let attackers access the keys, and they generate their keys randomly rather than letting them be related. I don't think related-key attack resistance was part of the specification given to entrants of the AES contest, and IIRC the AES standard doesn't claim such resistance.

Nonetheless, the designers of Rijndael (the cipher that is the basis of AES) designed Rijndael to be "ideal", which among other things Rijndael was supposed resist related-key attacks, which was above and beyond the AES requirements.

This new discovery finds that the AES cipher in fact does not meet Rijndael's design goals. Rijndael's design goals, however, exceeded the requirements stated in the AES standardization process, and any applications using AES are supposed to only use the characteristics of AES stated in the standard. So, even if this attack were of low enough complexity to be practical, it STILL should not affect valid AES applications, unless they are relying on characteristics that AES was never promised to have.

Load More 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>