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

Yawn

[Shikaku]

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:Complexity

[Anonymous Coward]

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

Quantum Computers

[religious freak]

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:Complexity.

[cpu_fusion]

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.

[xZgf6xHx2uhoAj9D]

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:Quantum Computers

[JambisJubilee]

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

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

[droopycom]

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

Re:Complexity

[man_of_mr_e]

Unless of course you start in the middle and expand outwards in both directions ;)

Re:Quantum Computers

[mathimus1863]

I probably should've linked to my post about Quantum Computing [slashdot.org] from yesterday.

The power of Quantum Computers is in getting really smart people to figure out how to take advantage of quantum interference to our benefit. There have been some really impressive results for a variety of pure-math problems that only a few people care about. But integer factorization and discrete-logarithms are among them - hence why QCs threaten most/all asymmetric encryption protocols (they're all based on one or both of those problems). However, for a vast array of problems, QCs won't offer us any computational improvement.

There are some improvements for more-practical algorithms, but the speed-up isn't usually as impressive. However, using Grover's algorithm to reduce a pure guessing problem from O(n) to O(sqrt(n)) is intriguing, to say the least.

Re:Complexity.

[nine-times]

You can make fun of me anyway. It's a dumb mistake to make.

Re:Yawn

[Eivind]

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. Luckily for you, AES256 was at a lot more than a million years before the break, so there's still some air left in it.