back to article AES crypto broken by 'groundbreaking' attack

Cryptographers have discovered a way to break the Advanced Encryption Standard used to protect everything from top-secret government documents to online banking transactions. The technique, which was published in a paper (PDF) presented Wednesday as part of the Crypto 2011 cryptology conference in Santa Barbara, California, …


This topic is closed for new posts.


  1. Rob Moss.

    'Groundbreaking' attack breaks AES crypto

    “This research is groundbreaking because it is the first method of breaking single-key AES that is (slightly) faster than brute force,”

    Holy cow, I didn't even have to write anything of my own to contradict the "headline" :-)

    Every time a crypto is "broken" by researchers, the word "broken" is used pretty loosely, like "I dropped my teacup on to some soft foam and a tiny fleck of paint broke off from the surface"

  2. petur

    Misleading title!

    Broken means there is a practical way to decrypt the protected content.

    1. Anonymous Coward

      define "Broken"

      Sorry chaps,but there are so many comments bitching about the - actually correct - use of the term broken, that an explanatory footnote should be added.

      Broken, in cryptographic circles, means that a means exists for deducing the encryption key, with certainty, in less than the 2^n operations (i.e. complete encryption cycles) that a brute-force attack would require.

      Unbroken means the only way to deduce the key is to run through all possibilites and check them - "brute force"

      Many breaks require additional information, for instance previous AES breaks required either message pairs encrypted with related keys (an unlikely gift) - or, a huge set of ciphertext/plaintext pairs, again an unlikely starting point for a real attack.

      This one is a considerable improvement, requiring no additional information. - however, it only loses a couple of bits of key strength - so the cipher is technically "broken", but not "compromised".

      Unfortunately the terminology doesn't very well distinguish the level of "break", terms like "very broken" or "completely broken" are seen, but "compromised" seems to be the trigger word that indicates its no longer considered safe to use.

      1. Chris Miller

        Well, maybe

        I'm not privileged to move in cryptographic circles, but I dare say that as a security specialist I have more dealings with cryptography than the average reader of ElReg; and I had never come across this strange reversal of the normal English usage of 'compromised' and 'broken'. I don't think the chaps in Hut 7 at Bletchley spoke of breaking Enigma, meaning they'd reduced its security by a couple of bits. So no-one should be surprised if, on a general IT web site, readers are confused by this odd terminology.

        Anyway, accepting your and DanG's definition, AES has been 'broken' since at least 2009, so shouldn't the headline read 'rebroken'?

      2. Anonymous Coward
        Anonymous Coward

        Thanks Kevin

        Thanks for the concise, clear explanation.

      3. Archimedes_Circle


        Generally I've always been taught that cryptographers create codes and cryptanalysts break them, hence I've always referred to myself as a cryptanalyst. As for 'broken' I completely agree with Kevin, broken simply means we've shortened the crack time from the max time of an exhaustive search. I've seen cracks for crypto schemes that literally shorten it by a single bit.

      4. Anonymous Coward

        order of complexity

        You missed an important word out of your analysis; a "break" reduces the _ORDER_ of complexity of the brute force.

        The original brute force is O(2^n); with this "break" the brute force is O(2^{n-2}) which is _still_ O(2^n). Thus the algorithm isn't broken, merely weakened.

  3. Chris Miller

    For a sufficiently small value of 'break'

    No, AES is not 'broken'. This is a very clever attack, but it only makes it 5x better than brute force (which, for a correctly implemented encryption scheme would take billions of years of computer power). To quote from the abstract: "In this paper we present a novel technique of block cipher cryptanalysis with bicliques, which leads to the following results:

    * The first key recovery attack on the full AES-128 with computational complexity 2^126.1.

    * The first key recovery attack on the full AES-192 with computational complexity 2^189.7.

    * The first key recovery attack on the full AES-256 with computational complexity 2^254.4.

    * Attacks with lower complexity on the reduced-round versions of AES not considered before, including an attack on 8-round AES-128 with complexity 2^124.9."

    As Bruce Schneier puts it: "there is no reason to scrap AES in favor of another algorithm, NST should increase the number of rounds of all three AES variants. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds."

  4. WinHatter


    1 trillion years rather than 5 to break the key ... I'm worried sick.

  5. Keith T

    no matter the security measures, a functioning criminal justice system is necessary

    This all goes to demonstrate that there is no such thing as entry-proof software or fool proof encryption (besides on-time cyphers, which are infeasible in IT).

    Security is all about delay delay delay, with time consuming steps, until law enforcement can intervene apprehend the attacker/vandal.

    And a human expert figuring out the secret protocols will in the end be just as time consuming or more so than graphics cards and the cloud breaking secret cypher keys.

    Therefore it is as much a violation, as much a criminal act to disclose the commercially secret protocols as to disclose commercially secret encryption keys.

    And no matter what security measures are used, a functioning criminal law and justice system is necessary to limit the time-line that black hat hackers have to figure out the protocols and break the encryption keys.

    Every IT compatible encryption method can be broken -- there is no challenge, no cleverness to being a black hat "security expert" or script kiddie.

    The only way to demonstrate cleverness is to work on the white hat side, finding ways to help safeguard sites and safeguard privacy.

    1. Anonymous Coward
      Anonymous Coward

      I thought law enforcement was "the attacker/vandal"

      see title

      1. asdf
        Thumb Down

        not quite

        Won't you think of the children. That is why gov has the right to attach battery leads to your genitals to get your password. Simple really and oh so dystopian.

  6. Tom Wood


    Seriously... informative article but the headline is downright misleading. It doesn't "break" AES crypto, any more than throwing a handful of sand at an toughened glass window breaks that. Scratches, maybe. Weakens, ever so slightly. But not breaks.

  7. bolccg


    is surely a bit much if it still takes a ridiculously long time and is considered secure?

  8. Herby

    Microsoft Research??

    THAT is an oxymoron for sure.

    Isn't this the same group that brought us "Bob" and "Clippy".

    They may have some ground breaking research, but Microsoft, can it be true?? Has the red sea parted? Must be the ice cubes in hell or some such...

    1. Cliff

      Microsoft Research

      They really do - I was privvy to some of the very very clever things they were developing about 8 yrs ago - they do some incredibly leading-edge work.

    2. IndianaJ


      Great research project. Probably never see the light of day, but an interesting idea.

    3. asdf


      Their research team is actually decent I hear. The problem is that chimp Balmer and his other cronies are incapable of delivering anything ground breaking even if it falls in their lap.

      1. paulc

        There's a reason for this...

        If Microsoft has them, then the competition doesn't and therefore cannot leap forwards leaving Microsoft wilting in the dust. Microsoft is singlehandedly responsible for so much damage to the progress of computing... we'd be well on the way to practical real time speech recognition and translation software by now if Microsoft wasn't performing their dirty tricks.

  9. Anonymous Coward

    Thanks for the heart attack!

    Misleading article title - but it sure did make me read ... <3

  10. This post has been deleted by its author

  11. Anonymous Coward


    A better headline for the article would be "Groundbreaking attack doesn't break AES crypto"

    It still takes trillions of years to recover a single key. That's about as far from broken as it's possible to be.

  12. DrXym


    Speeding up an attack by reducing a 128-bit key to 126-bits is certainly interesting but it doesn't really mean much in real terms. 2^126 is still an unfeasibly enormous number.

  13. M7S

    "Cryptographers have discovered ....."

    Just musing on a Friday: Should they be called "Decryptographers"?

    No slight intended to their competence but it seems a bit like referring to demolition workers as builders.

  14. The_Snapper67
    Thumb Down

    Seriously misleading headline

    Interesting read but forget the headline guys

  15. Anonymous Coward
    Black Helicopters

    Has anyone considered this?

    I recall reading about using Monte-Carlo analysis to make a mostly opaque surface transparent by measuring photon paths with a point source.

    Wonder if the same technique would work here, by writing the encrypted message as a holographic interference pattern then shining a variable wavelength laser through the photographic film from different angles to look for any changes in the random "speckle" ?

    Essentially this uses light as the computational medium so the usual limitations wouldn't apply.

    At least it would give a starting point i.e. "the key is between positions A and B", which could then be farmed out to the GPU cluster...


    1. Destroy All Monsters Silver badge

      "Wonder if" just doesn't cut it.


    2. K. Adams

      "... by writing the ... message as a [holo] ... pattern then shining a ... laser through [it]..."

      @AC 11:12GMT: Interesting method...

      However, I think we'd need to build viable quantum computers before such an attack could be viable.

      The problem lies in computing the path that an individual photon took while traversing the film. Due to the Heisenberg Uncertainty Principle, you can undoubtedly determine where the photon originated, and where it ended up when it reached the other side, but would probably not be able to track its course while in transit, unless you etched the interference pattern into some sort of material that can act as an optical trap, and can find a way to examine the states of the atoms within:

      -- -- Harvard University Gazette: Researchers now able to stop, restart light

      -- -- -- --

      Cool idea, though...

  16. Anonymous Coward


    Now, if somebody manages to make the attack recursive, as turning a 128-bit in a 126-bit encryption, using this algorithm, turning it into 124-bit... get the point.

  17. Anonymous Coward

    Broken = a method exists that is faster than brute force

    In cryptanalysis, an encryption scheme is considered broken if a method exists that is faster than brute force, so the article is correct.

    What should be considered when looking at the strength of a key is moore's law, and (assuming it continues... which some consider possible) how long until a key is breakable.

    for a key that would take 1 Trillion years on current hardware you can work out how many years (if we say computing power doubles each year to simplyfy things) by working out 2^x = 1 Trillion.

    Comes out to about 40 years to get that 1 trillion years down to 1 year.

    OK we probably won't be seeing a doubling every year, but even at much lower growth rates it could well be under 100 years to have hardware that can break encryption schemes that currently give ~1 trillion years protection...

    1. Tom Wood

      Depends on your readership

      In cryptanalysis, yes. But the previous headline would be sensationalist even in an academic journal. In a mainstream news publication it was basically scaremongering.

      Most readers of El Reg don't know what the specific definition of "break" is in the cryptographic community and many would have interpreted the previous headline to mean "is fatally flawed and therefore completely worthless". Cue all sorts of panic.

      The new headline is much more level-headed.

    2. asdf
      Thumb Up


      Some of the early generation of computer (1950s) destroyed Moore's law which quantum computers will do when they become available. I would like to think before 40 years but who knows. Quantum computer very early on I hear will make all encryption we have now nearly solvable instantly if they have enough qbits.

      1. Chris Miller


        No, quantum computing will wreck some current public-key systems, because it allows fast factorisation. It will effectively halve key-length for symmetric encryption schemes (leaving them still, mostly, effective). Nicked from Bruce's blog:

  18. Jeff 11

    Another cracking headline



    “However, it doesn't compromise AES in any practical way.”

    Jesus, Reg. That's a headline worthy of the Daily Fail.

    1. Anonymous Coward


      Just because it's not compromised in a practical way doesn't mean that it isn't compromised! It is now, by definition, less secure than it was.

      1. Destroy All Monsters Silver badge

        "It is now, by definition, less secure than it was."

        There is a dead parrot sketch in there somewhere.

      2. peter 45

        Soooooooo, by definition.

        Today I am one day older that I was yesterday. I am therefore by definition, one day less alive than I was yesterday. Does less alive mean that I am dead?

        1. Steve Knox

          Noooooo, bad analogy

          "Alive" is not a function of time, but a point-in-time attribute*. You are either alive, or not alive, at any given point in time. You do not become less alive over time.

          "Broken", as used in crypographic circles, is a function of the time needed for an attacker to decrypt a cipher. If that time is the same amount of time as trying all possibilities, then the cipher is not broken. The closer the time needed comes to a practical span of time, the more broken the cipher is; you can call a cipher completely broken if the time needed is short enough to allow exploitation of the message.

          * That's actually apparent in the subtext of the Python sketches about the dead parrot, and the corpse collector in Holy Grail.

          1. david 12 Silver badge

            "Alive" is ... a point-in-time attribute*.

            Oddly, one of the things my brother told me about working in intensive care is that, "Alive" is NOT a point-in-time attribute. It's more of a continuum. Not in the philisophical sense that we are all dying, but in the practical medical sense that a dying person in intesive care has some dead bits, and some alive bits, and some not-working-correctly bits, and the balance shifts, and a medico-legal decision is made at some point: "this patient is dead", but the actual decision may be technically arbitrary.

            Even then you won't be all dead. Galvani was getting muscle response from dissected frog muscles.

          2. Annihilator

            @Steve Knox

            "You are either alive, or not alive, at any given point in time."

            Two words: Schrodinger's cat

            1. Anonymous Coward


              And to Schrodinger I say "thermo scan of the box". You're not observing the cat, but the outside of the box. Compile that thermo scan over time and determine if it remains steady or decreases, if it decreases the cat is dead.

              Of course, this is still observing and forcing something linked to the cat to decide a state and thus you are breaking the logical test in a string theory kinda way.

          3. James Cullingham

            Mostly dead...

            '"Alive" is not a function of time, but a point-in-time attribute'?

            You tell that to Miracle Max and the Man In Black

  19. Gordon Barret

    How Long

    If they have reduced the average time taken to break the code then very well done to them and their cleverness.

    But I don't doubt that in the future someone else (or indeed the same people again) may have another idea on how to reduce the number of keys to check/total time taken.

    Also - those who "estimate" the time taken - what hardware do they consider?

    If they only consider a single cpu PC then what about someone who uses the relatively new method of using the hundreds or thousands of computing cores in modern GPUs?

    And if they were then to use a zombie botnet of millions of such PCs ...

  20. Joe 34
    Thumb Down


    Just wasted 5 mins of my life on this article

  21. Anonymous Coward

    I liked clippy

    But I longed to be able to replace it with my home grown icon I liked to call "Gimpy," modeled on the fanboi icon.

  22. Martin

    Nice piece of history rewriting there, Reg

    When I read the article, the headline said:-

    "Groundbreaking" attack breaks AES crypto.

    When I read the comments (most of which said "No it didn't!" or words to that effect), I returned to the article to discover:-

    AES crypto compromised by "groundbreaking" attack

  23. Absent
    Big Brother

    Setec Astronomy

    There isn't a government on this planet that wouldn't kill us all for that thing.

  24. NoneSuch Silver badge

    Who do you trust?

    AES was the first publicly accessible and open cipher approved by the National Security Agency (NSA) for top secret information.

    Would the US Gov put out a cypher they could not read themselves? You can bet they do not have to brute force it either. DES was official and NSA approved as well until someone showed how to decrypt it in real time using modified hardware.

    Encryption delays access to information. It does not stop access.

    1. Anonymous Coward
      Anonymous Coward


      AES is approved for keeping things secret that the US government would like to keep secret from foreign governments also. If they had an easy means of breaking it, it should be assumed that foreign governments also have it, or are not far from finding it, or in the case of the Chinese, have a better version already.

      Of course the US might be assumed to have greater computing means - better architecture and faster processors, but it would be a dangerous assumption, and even if true, it would not be true for long.

      1. Steve Knox

        Dangerous assumption indeed...

        given where the vast majority of the US's computing components come from.


This topic is closed for new posts.

Other stories you might like