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 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"
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.
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'?
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.
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."
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.
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.
This post has been deleted by its author
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
@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...
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...
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.
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.
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
"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.
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.
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.
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 ...
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
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.
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.
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".
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!
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.
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.
"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.
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!
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
