Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Encryption Security

New Research Cracks AES Keys 3-5x Faster 176

Posted by Unknown Lamer from the before-the-heat-death-of-the-universe dept.
Landing his first accepted submission, qpgmr writes "AES, generally thought to be the gold standard for encryption, is showing weaknesses. From Computerworld: 'Researchers from Microsoft and the [Belgian] Katholieke Universiteit Leuven have discovered a way to break the widely used Advanced Encryption Standard, the encryption algorithm used to secure most all online transactions and wireless communications.'" The full paper has lots of details. Note that it would still take a few billion years with current computers to actually break anything, but there may be further vunerabilities yet to be discovered.
This discussion has been archived. No new comments can be posted.

New Research Cracks AES Keys 3-5x Faster More

New Research Cracks AES Keys 3-5x Faster

Comments Filter:

  • Correction (Score:5, Informative)

    by CharlyFoxtrot ( 1607527 ) on Thursday August 18, 2011 @08:58PM (#37137060)

    The Katholieke Universiteit Leuven (KUL) is a Belgian, specifically Flemish, university not Dutch.

    • Re:Correction (Score:4, Funny)

      by CharlyFoxtrot ( 1607527 ) on Friday August 19, 2011 @05:13AM (#37139542)

      Cool, the mods changed the summary. Since the error was in TFA this means we are in the historically nearly unprecedented situation of having a summary that's more correct than TFA ;-)
      (What I meant to say is, good job.)

      • Cool, the mods changed the summary. Since the error was in TFA this means we are in the historically nearly unprecedented situation of having a summary that's more correct than TFA ;-) (What I meant to say is, good job.)

        Er, hopefully it was the near legendary "slashdot editors" who changed the summary.

    • Re: (Score:2)

      by packman ( 156280 )

      Funny thing is, Joan Daemen and Vincent Rijmen - the ones who developed the Rijndael which later became AES, both worked at the KUL...

  • That's some mighty fine print you got there... (Score:5, Interesting)

    by geekmux ( 1040042 ) on Thursday August 18, 2011 @09:06PM (#37137136)

    "New Research Cracks AES Keys 3-5x Faster"

    (the fine print)

    "it would still take a few billion years with current computers to actually break anything.."

    • Given Moores law a crypto attack will get double the speed about every 2 years so it was known from the start
      that AES had a limited time to be secure. It was just a matter of time until the crypte lenght become too short given the CPU power you can add to break it.

      So this means that we just have to upgrade to a new krypto about 4 years earlier then if it had not been found for it to still be safe.

      • Re: (Score:2)

        by afidel ( 530433 )
        No, AES-256 would take the energy of every atom in the earth to brute force using known methods (it was in the same order of magnitude anyway, saw the calculations once).

        • Re: (Score:3)

          by Bengie ( 1121981 )

          Yeah, my cousin took an advanced cryptography class for CS, and his teacher ran the math on brute forcing a 256bit key with the theoretical physical minimum amount of energy required with ultra-advanced technology, on average would consume more usable energy than there is in the MilkyWay.

          Brute forcing is out of the question for sure, unless we start to consume galaxies for energy.

          Unfortunately, AES isn't perfect, and it's effective strength is much lower than 256bit. The 3-5x reduction might be enough to br

          • Brute forcing is out of the question for sure, unless we start to consume galaxies for energy.

            It's OK as long as it's other people's galaxies and not our own though isn't it?

        • Re: (Score:2)

          by mcrbids ( 148650 )

          As stated elsewhere, there are various ways around this limitation, including the use of reversible computing which works by "borrowing" entropy resulting in an extremely low entropy computation mechanism.

          • Re: (Score:2)

            by delt0r ( 999393 )
            Reversible computing reduces, but does not remove the limit. Basically anything that has a different number of inputs to outputs must have a non zero entropy logic. Since things like adders are like this (twice as many inputs as output) etc, then you can't reduce to levels that solve the problem. Note the calculation on the energy required is not from the entropy limit of a logic gate, but the "entropy" of just that many keys.

          • Doesn't matter: Do the math with a single electron transition per key and you still need to capture the entire energy output of the Sun to brute force a 128-bit key in a useful time. Not going to happen.

      • Given Moores law a crypto attack will get double the speed about every 2 years so it was known from the start
        that AES had a limited time to be secure. It was just a matter of time until the crypte lenght become too short given the CPU power you can add to break it.

        I don't think you quite grasp the scale of the numbers here. It's easy to say "just use a million PCs" but setting up that many PCs, powering them all and just plain keeping them all running is way harder than you think. Numbers in the tens of thousands is probably more realistic (even for the NSA).

        Quoting Moore's Law doesn't work either: A better way to think of it is to figure out how much energy you'd need to brute force a 128-bit crypto key. Assuming the lowest power unit possible to check a key, ie. on

    • Re:That's some mighty fine print you got there... (Score:5, Interesting)

      by FuzzyDaddy ( 584528 ) on Thursday August 18, 2011 @09:17PM (#37137212) Journal
      Or "New attack reduces 256 bit key strength by two bits"

      • Re: (Score:2)

        by mysidia ( 191772 ) *

        Or "New attack reduces 256 bit key strength by two bits"

        I'm not too worried about it, as i've already switched to Triple-Rjindeal scheme, eg 3AES256 with a keying analogous to 3DES keying option 1

        So they're reducing a 768 bit key strength by what, 0.2% ?

        • That's weak, you need at least 1Gigabit key strength to protect your emails. Man up.

          • I use 1.21 jiga-bit flux encryption.

            As soon as I think up something that I need to encrypt, I bang my head into the sink until I forget it, confident that I'll come back in time from the future (or send a suitable representative in a life vest) to remind myself what it is I wanted encrypted when I need the information.

          • 1Gigabit key might be fine for encrypting tweets, but what if I want to secure something larger?

        • i've already switched to Triple-Rjindeal scheme, eg 3AES256
          with a keying analogous to 3DES keying option 1

          You're doing it wrong:
          a) There's no proof that this will increase the strength, it might weaken it.
          b) You'd be better off adding whitening (ie. AESX, analogous to DESX)
          c) Much better to just increase the number of rounds in standard AES.

          (Yeah, I know you were being facetious, but...)

    • Ah. So it might be enough time to develop a new standard.

      Incidentally, do any of these calculations of "a billion years" take into account Moore's Law? Has anyone developed an actual calculation taking into account the rate of computer advancement? (It'd still be secure enough for daily use, but still.) Some quick math shows that if computers double in power every 2 years, then the time to break it halves every 2 years. Or, in 60 (2*2^30=~ 1 billion) years computers will be 1 billion times more powerful an

      • http://everything2.com/user/dogganos/writeups/Thermodynamics+limits+on+cryptanalysis [everything2.com]

        Who cares about Moore's law. Read that.

        Now it STILL might get broken. Attacks better than brute force are always the largest threat. However nobody need worry about the brute force computer to break their codes. Not even quantum computers help here, by the way. See Grovers Algorithm. Preview: "Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storag

        • Reversible Computing [wikipedia.org]

          It could theoretically overcome the limits of thermodynamics on computers. Basically, AFAICT it requires us to (nearly) perfectly observe the computer so that we could reverse any changes that take place in the system, so they would generate very, very little entropy (limited by how well we could build them.) Essentially, they can reuse any energy already used in computation with a very low degree of loss. Also, you might want to look at "Adiabatic quantum computation". Essentially thi

          • Re: (Score:2)

            by bondsbw ( 888959 )

            Nor, for that matter, that P!=NP, which is a more or less essential assumption in public-key cryptography. If it isn't, then as the key size grows, time to brute-force increases linearly, not exponentially as we think it does.

            Not necessarily. Even assuming P = NP, the conversion from the NP problem to the equivalent P problem doesn't necessarily take linear time. And it doesn't mean that the P solution itself can run in linear time. If it turns out that both the conversion and the P solution are O(n^10^10^10^10^10), they would be practically worthless for anything.

            • Re: (Score:2)

              by fyngyrz ( 762201 )

              Look. Brute force: Division... divide a million by three, by subtracting three from the dividend and counting how many times it happens before the dividend rolls past zero. 333k cycles. Now do long division. 8 cycles. Snap, it's done.

              Now jump forward a decade or two... quantum computing... probabilistic algorithms... Snap, AES is cracked. Never assume that today's technology will be applied to tomorrow's problems. If you do -- everything you come up with is very likely to be wrong.

              Finally -- never assume th

              • Re: (Score:2)

                by delt0r ( 999393 )
                Block Ciphers and their kin are not cracked by quantum computers. They only reduce the search space by a square root. ie half the key size. Since quite a few modes of using these ciphers gives time/memory trade off attacks that give the same square root key size reduction (ie hash functions and birthday attacks), its not really a problem.

                • ECRYPT II specifically lists AES-256 as protected against analysis by quantum computer (unless Shor's algorithim applies), People should be more worried about asymmetric crypto, although even there alternatives have been developed. As a fully capable quantum computer won't spring into existence suddenly, I presume we would have a few years to switch.

                  "Both of the fundamental intractability assumptions on integer factoring and discrete loga-
                  rithms break down if a (large) quantum computer could be built as dem

    • Re: (Score:2)

      by Entrope ( 68843 )

      The fine print from the summary isn't even quite accurate -- the attack complexity is slightly more than 2^125. If you assume computers can check about a billion (2^30) keys per second, and given that you have about 2^25 seconds in a year, you would need about a trillion (2^40) computers to guarantee success in a billion years. (125=30+25+40+30.)

    • "New Research Cracks AES Keys 3-5x Faster"

      (the fine print)

      "it would still take a few billion years with current computers to actually break anything.."

      Yeah, but that still means were down to 5 billion years from the previous 25 billion years, right?

  • Bruce Schneier's take (Score:5, Informative)

    by condition-label-red ( 657497 ) on Thursday August 18, 2011 @09:07PM (#37137144) Homepage
    linky [schneier.com]...

  • (sic) "Dutch Katholieke Universiteit Leuven."

    Leuven/Louvain is in Belgium, not the Netherlands.

  • The AES-128 "crack" requires 2^88 bytes of storage (Score:3)

    by yeremein ( 678037 ) on Thursday August 18, 2011 @09:51PM (#37137416)

    To put that number in perspective, it would take a stack of 4GB hard drives extending past the orbit of Saturn...

    • 135TB in a 4U Blackblaze storage pod [backblaze.com], 280 rack units in a 20' x 8' [ ... x 8' high? ] shipping container [pingdom.com], gives 9.5PB or log2(135 * 8 * 10^12 * 280 / 4) 2^56 bits of raw online storage.

      So now you *only* need 4 billion (2^32) shipping containers... yeah right. Stacking them 8 high, with no space for walkways or roads, would cover an area at least 55 miles on each side.

      • Re:The AES-128 "crack" requires 2^88 bytes of stor (Score:5, Funny)

        by flonker ( 526111 ) on Friday August 19, 2011 @02:29AM (#37138714)

        The NSA called. They deny that any such data center exists.

        • In the time it would take to create such a thing efficiently, it would probably be possible to do it in 1/4th of the size :)

          • In the time it would take to create such a thing efficiently, it would probably be possible to do it in 1/4th of the size :)

            And in the time it would take the government to build such a thing, it will have become commodity desktop hardware.

      • Re: (Score:2)

        by lyml ( 1200795 )
        Twenty years ago hard drives were 100 MB. Now they are 2 TB, that's a x20000 increase roughly 2^14 increase. If the trend continues (I have no idea when we will hit a hard wall in storage space) it will probably fit into something the size of a thumb drive in 60 years.
  • They say, as the payload sentence of the abstract,

    As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

  • As someone who knows next to nothing about encryption, here's a question. If this ever becomes a problem, can't one VERY easily increase the bit count from 256 to 512 or more for an exponentially stronger encryption?

    And more generally, I've heard these algorithms are very complicated. Rather than having this enormous complexity, can't you use a simpler, more elegant math algorithm, and again, just increase the bit count say from 256 to 512bit or more? Or does math not support that?

    In this age of terabytes,

    • Re: (Score:3)

      by Entrope ( 68843 )

      It is usually not practical to pick "a simpler, more elegant math algorithm" because those are easy -- or at least easier -- to break. As someone mentioned up-thread, and as Bruce Schneier likes to remind us, attacks tend to get better over time -- they never get worse.

      Modern cryptosystems are carefully tuned to resist a lot of clever attacks. Probably every stage in every (credibly) proposed encryption scheme has been closely examined by very smart people to understand its behavior and look for weaknesse

    • To try to answer your question as simply as possible: Yes, and No. It is generally fairly easy to increase the bit count, but then you have to go through and reencrypt all your data, which takes time, and energy, and depending on the attack, you still might be susceptible.

      The reason the algorithms are complex is because they can't be easily reversible. It can't be obvious from the encrypted text as to what the key is, or what the decrypted message is, otherwise your encryption is useless. These algorithm

    • Re: (Score:2)

      by flonker ( 526111 )

      Increasing key size is not simply a matter of encoding things twice, as there may be an attack where they can take a shortcut, reducing the practical key strength.

      Some additional reading:
      http://x5.net/faqs/crypto/q61.html [x5.net]
      http://x5.net/faqs/crypto/q85.html [x5.net]

    • Re: (Score:2)

      by slew ( 2918 )

      As someone who knows next to nothing about encryption, here's a question. If this ever becomes a problem, can't one VERY easily increase the bit count from 256 to 512 or more for an exponentially stronger encryption?

      And more generally, I've heard these algorithms are very complicated. Rather than having this enormous complexity, can't you use a simpler, more elegant math algorithm, and again, just increase the bit count say from 256 to 512bit or more? Or does math not support that?

      In this age of terabytes, does it really matter if we all save a few bits?

      Cipher design is pretty complicated, but with a little bit of hand-waving, it might be able to explain the problem.

      The task of creating a cipher (encryption algorithm) is basically the same problem as creating set of algorithms for shuffling a deck of cards a certain way. The deck of cards starts in order and the data you want to encrypt is where the deck is "cut". Then you shuffle the cards using some instructions (set by the key) and then you figure out where in the deck that card ended up. You decrypt

    • I don't know that you'll ever be able to brute force a 256-bit key, presuming that there are no weaknesses and you get all 256-bits of entropy. I mean the energy levels involved would be, like, galactic (as in the energy contained in a galaxy) in scale. So until we develop a completely different method of computing, that isn't a problem.

      The problem comes in when you are able to find weaknesses in the algorithm and break rounds of it, and thus decrease the complexity. So really, more rounds are the more usef

  • Broken by Microsoft?? (Score:4, Informative)

    by AftanGustur ( 7715 ) on Friday August 19, 2011 @03:19AM (#37138990) Homepage

    If you choose to believe some of the articles [computerworld.com], it was Microsoft who "broke" this encryption algorithm.

    However, if you read the actual research paper [microsoft.com] the first page explicitly explains the relation between Microsoft and the researchers as "The authors were visiting Microsoft Research Redmond while working on these results."

  • I have a method to crack them 10 times faster.

    Its called using 10 machines.

    That said its not going to make much of a difference if you're pressed for time because the universe is going to die of death-heat before you finished.

  • They build in this weakness to be able to present the paper - one more paper to let your research institute exist! AES is (mostly/partly?) from Leuven.

    Nah, just joking, Leuven is pretty well respected, I don't think it will disappear overnight.

  • If this was China, you'd all be up in arms, firearms, probably.

Slashdot Top Deals

Two can Live as Cheaply as One for Half as Long. -- Howard Kandel

Close