Slashdot Mirror
New AES Attack Documented
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.'"
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.
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.
2^119 is a massively large number.
664613997892457936451903530140172288
Meh. I've seen bigger.
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.
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".
If I can be modded down for being a troll, can I be modded up for being an orc, or a balrog?
>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.
1 in 4 Maine children in struggle with hunger.
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.
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.
Live today, because you never know what tomorrow brings
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.
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
I took a class on QC, and I assure you that you are mis-reading Grover's Algorithm. It applies to any pure-guessing problem for which all possible answers are equally likely. If you can create a quantum circuit that can check whether a given key is correct, and no one key is any more likely than any other key, then you can apply Grover's algorithm.
It appears you are a little trigger-happy with calling BS.
There are some physics I know (I was one once...) that work on quantum computers. They don't think they will ever be faster at cracking than classic computers.
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.
The Grey Goo disaster happened 3 billion years ago. This rock is covered in self replicating machines!
That's a pretty common myth.
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...)