Slashdot Mirror

← Back to Stories (view on slashdot.org)

New AES Attack Documented

Posted by timothy on from the ponder-don't-panic dept.

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

11 of 236 comments (clear)

  1. Yawn by Shikaku · · Score: 2, 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.

    1. Re:Yawn by Eivind · · Score: 2, Insightful

      http://valerieaurora.org/hash.html
      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.

  2. Re:Complexity by Anonymous Coward · · 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).

  3. Quantum Computers by religious+freak · · Score: 2, Insightful

    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.

    --
    If you can read this... 01110101 01110010 00100000 01100001 00100000 01100111 01100101 01100101 01101011
    1. Re:Quantum Computers by JambisJubilee · · Score: 2, Insightful

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

    2. Re:Quantum Computers by mathimus1863 · · Score: 2, Insightful

      I probably should've linked to my post about Quantum Computing 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.

  4. Re:Complexity. by cpu_fusion · · 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.

  5. Re:Complexity. by xZgf6xHx2uhoAj9D · · Score: 1, Insightful

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

  6. Re:Furthers my stand on crypto, which is: DON'T by droopycom · · Score: 4, Insightful

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

  7. Re:Complexity by man_of_mr_e · · Score: 2, Insightful

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

    --
    If you need web hosting, you could do worse than here
  8. Re:Complexity. by nine-times · · Score: 2, Insightful

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