Submitting a review for consideration is easy; please first read Slashdot's book review guidelines. Updated: 2008114 by samzenpus
All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.
Yawn (Score:3, Insightful)
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 (Score:5, Informative)
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.
Parent
Obligatory XKCD quote (Score:5, Funny)
Security [xkcd.com]
Parent
Obligatory Cryptonomicon Quote (Score:5, Interesting)
If you want your secrets to remain secret past the end of your life expectancy, then, in order to choose a key length, you have to be a futurist. You have to anticipate how much faster computers will get during this time. You must also be a student of politics. Because if the entire world were to become a police state obsessed with recovering old secrets, then vast resources might be thrown at the problem of factoring large prime numbers.
So the length of the key that you use is, in and of itself, a code of sorts. A knowledgeable government eavesdropper, noting Randy's and Avi's use of a 4096-bit key, will conclude one of the following:
-Avi doesn't know what he's talking about. This can be ruled out with a bit of research into his past accomplishments. Or,
-Avi is clinically paranoid. This can also be ruled out with some research. Or,
-Avi is extremely optimistic about the future development of computer technology, or pessimistic about the political climate, or both. Or,
-Avi has a planning horizon that extends over a period of at least a century.
-- Neal Stephenson, Cryptonomicon
Parent
Sigh... I'll repeat again: (Score:4, Funny)
Lord Farquaad: I've tried to be fair to you creatures, now my patience has reached it's end! Tell me or I'll...
Gingerbread Man: NO! Not the buttons! Not my gumdrop buttons!
Lord Farquaad: Alright then! Who's hiding them?
Gingerbread Man: Ok. I'll tell you. Do you know... the muffin man?
Parent
Re: (Score:3, Insightful)
http://valerieaurora.org/hash.html [valerieaurora.org]
Pay special attention to the reaction of the "slashdotter" to "minor weakness found", and compare it to your reaction.
Remember, attacks always gets better, never worse. The first attack that weakens an algorithm *is* a big deal.
Oh, and reducing complexity from 2^128 to 2^110 isn't as it may appear a reduction of 10% in time-to-break, infact it's a reduction of 2^18 or about a factor of a million, so it's more like if before it took a million years, now it takes ONE year. Lu
Complexity (Score:3)
Re: (Score:3, Insightful)
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: (Score:3, Informative)
Re: (Score:2)
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 (Score:4, Interesting)
I'm not familiar with the term "complexity" being used in this context and with these specific numbers.
Because it's not a problem that scales with n, it's an attack on one particular value of n. Ideally brute forcing an n-bit cipher has complexity O(2^n). For 256 bit AES, they've found an attack that instead of the ideal 2^256 attempts takes 2^119 attempts. But you can't say O(2^119) because that is equal to O(1), and any function with n would be false since it doesn't apply to other n. I guess you could say an attack with "complexity O(2^(n*119/256) for n=256" but you're likely to confuse a hundred times as many as are enlightened.
Parent
Re:Complexity (Score:5, Informative)
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.
Parent
Re: (Score:2)
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
Re:Complexity (Score:5, Informative)
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.
Parent
Re: (Score:3, Insightful)
Unless of course you start in the middle and expand outwards in both directions ;)
Re: (Score:3, Funny)
Any attack which starts with things like "first you encrypt 2^128 carefully chosen plaintexts and store them in a hash table" isn't really an attack you should worry about.
Furthers my stand on crypto, which is: DON'T (Score:4, Funny)
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: (Score:2)
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 (Score:5, Insightful)
Refutation: Crypto is indeed all about WHEN. WHEN is not pointless, it is the point.
Parent
Complexity. (Score:5, Funny)
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. (Score:5, Informative)
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.
Parent
Re:Complexity. (Score:5, Insightful)
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.
Parent
Re: (Score:2, Insightful)
Re: (Score:3, Interesting)
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: (Score:2, Informative)
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: (Score:3, Informative)
Re:Complexity. (Score:5, Informative)
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
Parent
Re: (Score:3, Informative)
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
Re:Complexity. (Score:5, Interesting)
>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.
Parent
Re: (Score:3, Interesting)
2^119 is a massively large number.
664613997892457936451903530140172288
Meh. I've seen bigger.
Re:Complexity. (Score:4, Informative)
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.
Parent
Re: (Score:3, Funny)
Note to self: never try to tell a cryptography joke.
Re: (Score:2)
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: (Score:2, Interesting)
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
Re: (Score:2)
The attack doesn't work in AES-128 or AES-192. It only works on AES-256.
Re: (Score:2)
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 mig
Re: (Score:3, Insightful)
That's Today... (Score:2)
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: (Score:2)
Quantum Computers (Score:3, Insightful)
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 (Score:4, Informative)
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.
Parent
Re: (Score:3, Informative)
There are several methods of public-key encryption which are secure against quantum computers. Try Lamport Signatures for a start:
http://en.wikipedia.org/wiki/Lamport_signature [wikipedia.org]
Re: (Score:3, Interesting)
There are 2 reasons.
First a quantum computer construction complexity goes up to the power of qbits. ie a quantum computer with n qbits has construction complexity of O(2^n), so with Moores law in place the number of qbits goes up linearly with time... This is leaving out the extra qbits you need for error correcting with decoherence that makes a
Re: (Score:3, Insightful)
2^119 is... (Score:5, Interesting)
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: (Score:3, Interesting)
2^40 would take very little time on a home PC, an afternoon or maybe a day.
40 bits is also the size of the keyspace used by HDCP for HDMI and DVI, for "encrypted" HD displays. I don't feel like doing the math, but determining all of the 40-bit keys used in HDCP could probably be done in a short time on a reasonable home PC, using a man in the middle attack. However, for copying HD video, one would still probably get better quality by showing Macrovision, the MPAA, and the Blu-Ray consortium that using BD+
Re:2^119 is... (Score:5, Interesting)
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
Parent
this a RELATED-KEY attack (Score:5, Informative)
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.
Mod parent way the fuck up (Score:4, Informative)
Almost everyone here seems to be missing the bit in the summary that mentions that it's time and data complexity. It's not nearly as bad as 2^119 time and some tiny data.
Parent
Re:Improvement (Score:4, Informative)
erm only a 99.7% improvement.
Parent