New AES Attack Documented 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.'"
Re:Complexity. (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 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.
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:Complexity. (Score:3, Interesting)
2^119 is a massively large number.
664613997892457936451903530140172288
Meh. I've seen bigger.
Re:Yawn (Score:1, Interesting)
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:2^119 is... (Score:1, Interesting)
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:Complexity. (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: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
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.
Re:Complexity. (Score:2, Interesting)
Basically, it says how long it would take to be sure to crack it.
To give a comparison, most machines on the net today is clocked at ~4Ghz, that is 4 000 000 000 instructions per second. Imagine a CPU:s doped for only one thing, and one cpu-cycle would mean one key tested ( in reality, there's more like maybe 1000s of cycles/test or something like that ). That would mean that the cpu crunched 172 000 billions of tests per day. With that monster cpu, it would still take 5 billions of billion years to be sure to crunch that encryption.
Even if you filled the theoretical limits of todays internet (unfortunately, IPv6 is still the internet of tomorrow) with these monster machines, it would still take 1,25 billon years to be sure to find the key. This all is of course just theory. Who knows, if you're lucky you may get it in a tenth of that time, only 125 million years. ;)
As a footnote, for the cost of those monster-machines, the operational cost of them and the staff to support them, you'd be much better off bying an army. Physical security in most places is much weaker than AES currently, so it would be much easier just to force the secrets out.
Disclaimer: All this assumes turing-machines, where only one solution at a time can be evaluated. In a quantum-processor, you could theoretically do much better.
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.
Re:Yawn (Score:1, Interesting)
Correct me if I'm wrong but I heard that for 128 bits if we had a supercomputer that was the size of a grain of sand that could test 1 key in the time it takes for light to cross the width of that grain of sand, and we put a layer 10 feet deep of this "sand" all over the Earth, it'd still take 1,000 years to crack.
Keeping that in mind, I don't think that "adding a datacenter" is going to make it crackable in the time the Parent suggests.
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
Re:2^119 is... (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+ to protect BD-ROM discs is stupid. For the original developers it was a surprisingly good scam that they managed to pull off on the movie industry. BD+ attempts to determine what physical hardware a Turing-complete machine is running, using an obfuscated Java program. This is futile because another unauthorized Turing-complete machine can easily mimic the behavior of an authorized Blu-Ray player. The ability of any Turing-complete machine to execute the same program as another Turing-complete machine allows for emulation and is a cornerstone of the Church-Turing Thesis. For instance, if done properly, an Apple IIe could run the BD+ decryption program, thus mimicking an authorized Blu-Ray player. However, one should expect quite a bit of floppy disk swapping, and good luck finding enough 5.25" disks in usable shape, especially if you decide to play a 50GB movie on that machine. On the other hand, trying it on an older machine that used punch cards. Imagine the size of a 50GB punch card deck using standard IBM punch cards.
Re:Quantum Computers (Score:2, Interesting)
It appears you are a little trigger-happy with calling BS.
Re:Quantum Computers (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 adding qbits even harder.
Second a 128 qbit quantum computer cannot efficiently simulate a 129 qbit computer. Thus to factor 1024 bit primes you need at least a 1024 qbit computer. This is in contrast to a classic computer where it can emulate larger internal register computer in polynomial time.
There are other things to consider. They are not so good with classic encryption. ie cracking AES. In fact I don't think there is an algorithm to crack AES or other symmetric encryption methods. Also the algo is probably different for each type of block cipher. However I have not bothered to follow the literature on this.
Quantum computers seem to trade a hard math problem with a hard construction problem.... Oh but note we don't know if factoring is hard (ie not in P). Ironically we also don't know that P!=NP, or if trap door functions exist. We just think they do.
"Crypto is always broken." is a myth (Score:2, Interesting)
It might hold for most symmetric key cryptography algorithms (such as AES, SHA, MD5, DES, etc) however there is a whole other branch of (admitidely mainly theoretical) cryptography which relies on provable security. I.e. formal reductions showing that breaking security of the scheme is at least as hard as solving some difficult underlying problem. For such schemes it's a lot more plausable that there may simply not be a poly-time algorithm which solves them. (Take the short vector problem of lattice based crypto for example. To date we don't even have a _quantum_ algorithm that solves it efficiently let alone a classical one. Yet there are schemes that are at least as hard to break as that problem is difficult to solve.)
And of course then there is another branch of cryptography which considers information theoretic security. These are provably _unconditionally_ secure. (The most common example being the "one time pad".) For these algorithms, protocols, and applications as long as the under lying model is a good model of the real world there is simply no way to break security regardless of computing technology and future developments in algorithms.
So no. Crypto is not just broken. Quite a lot of modern crypto is actually pretty secure. (Now whether it's practically efficient is a whole other new ball game of course, but then that wasn't the claim...)