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, …

COMMENTS

This topic is closed for new posts.
  1. Rob Moss.
    FAIL

    '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
    FAIL

    Misleading title!

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

    1. Anonymous Coward
      Boffin

      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 - i.e.by "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
        Happy

        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

        Technically

        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
        Facepalm

        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
    Pint

    Groundbreaking

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

  5. Keith T
    Holmes

    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
    Stop

    Headline

    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
    Meh

    "breaks"

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

  8. Herby
    Joke

    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.

      http://research.microsoft.com/en-us/labs/cambridge/default.aspx

    2. IndianaJ

      Singularity

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

    3. asdf
      FAIL

      yep

      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
    Mushroom

    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
    Pint

    Well

    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

    "Groundbreaking"

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

    AC/DC

    1. Destroy All Monsters Silver badge
      WTF?

      "Wonder if" just doesn't cut it.

      SHOW ME THE MATH!

    2. K. Adams
      Boffin

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

      -- -- -- -- http://news.harvard.edu/gazette/2001/01.24/01-stoplight.html

      Cool idea, though...

  16. Anonymous Coward
    Devil

    Recursive?

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

    ...you get the point.

  17. Anonymous Coward
    Trollface

    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

      except

      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

        @asdf

        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:

        http://www.schneier.com/blog/archives/2011/08/new_attack_on_a_1.html

  18. Jeff 11
    Facepalm

    Another cracking headline

    "AES CRYPTO COMPROMISED BY 'GROUNDBREAKING' ATTACK"

    ...

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

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

    1. Anonymous Coward
      Stop

      Wait

      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
        Pint

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

        There is a dead parrot sketch in there somewhere.

      2. peter 45
        Holmes

        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
          Boffin

          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
            Happy

            @Steve Knox

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

            Two words: Schrodinger's cat

            1. Anonymous Coward
              Pint

              title

              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
    Boffin

    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

    Ugh!

    Just wasted 5 mins of my life on this article

  21. Anonymous Coward
    Joke

    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
    Happy

    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
    Coffee/keyboard

    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

      conspiracy

      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.

  25. Anonymous Coward
    Joke

    My paranoia is getting to me

    I'm changing my router key once a week.

  26. amanga
    Linux

    Not so impressive if compared to other research results.

    According to the mentioned paper the full computational complexity amounts for AES-128 - one of the most used implementation of Rijndael - key recovery is about 2^125. No doubt this represents an improvement over any brute-force but I would not be so impressed.

    There are other papers showing different attack techniques and most of them would deserve more attention.

    I.e. a theoretical attack on the AES-128 block-cipher was proved two years ago ("A related-key distinguishing attack on the full AES128")

    www.science.unitn.it/~sala/workshopcry09/Abst_slides.pdf

    As stated into the paper, the computational cost of this kind of attack should be 2^45. IMHO this is more impressive that a new attack technique "that is (slightly) faster than brute force".

  27. MrEee
    Mushroom

    Everyone seems to be ignoring the real breakthrough here.

    Imagine you were trying to crack the AES encryption and it took you trillions of years. Now imagine you could do that with just 1/4 as many machines in the same trillions of years. Bam! HUGE power savings!

    Cracking AES hasn't become more feasible, but it just got much greener, so we should all be applauding these researchers! Woohoo!

  28. Anonymous Coward
    Unhappy

    Use Twofish now?

    So we should start using Twofish now?

    It took TrueCrypt 8 hours encrypting in AES-256 my new 1 TB hardrive on my brand new PC...

  29. Anonymous Coward
    Pint

    Dictinoary attacks

    Could you "bruteforce" a dictionary attack 5 times faster as well, like a rainbow table but not exhaustive?.

    Wouldn't this also mean that if you can get the target to encrypt something you already have the plain text for and get a copy of the encrypted version that would help speed it up even more.

  30. Oliprof
    FAIL

    El Reg, I AM DISAPPOINT

    AES isn't broken; This research does prove that the algorithm isn't an "ideal" cipher because these attacks do nonetheless reduce the complexity to less than brute force of the entire key space.

    However, these attacks have not reduced the computational complexity to any level where they are feasible; the complexity of AES-128 still remains slightly larger than the entire IPv6 Global Unicast Internet, have a pop at enumerating that if you like and see how long it takes you.

    AES is not broken, it is not compromised, it is merely weakened, and very slightly at that.

  31. Winkypop Silver badge
    Alien

    Trillions of years

    So, no time to grab a cuppa then?

  32. Sirius Lee
    Unhappy

    Update

    "Broken" may have a specific meaning in the hallowed halls of cryptanalysis but if you know that and choose to use the word while at the same time knowing that no one outside the halls will be aware the specificity of the term then as a "journalist" you have responsibility to share - or look like an arse using a cheap gimmick to get page hits. Sad.

  33. Stevie

    Bah!

    Well it would *help* if the stupid software didn't tell the cracker when each character had been guessed. I can't count the number of Casino Heists, intrusions into government computers by disaffected radicals with unfeasible tech or penetrations into vaults in secret SPECTRE hideouts have been facilitated by that nitwit stupidity.

    Encryptors! Bloody well keep the whole password secret until the entire thing has been guessed!

This topic is closed for new posts.

Other stories you might like