Feeds

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.

Page:

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"

9
3
Bronze badge
FAIL

Misleading title!

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

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

27
1
Silver badge
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
1
Anonymous Coward

Thanks Kevin

Thanks for the concise, clear explanation.

1
0

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.

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

2
0
Silver badge

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

5
0
Pint

Groundbreaking

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

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

0
15
Anonymous Coward

I thought law enforcement was "the attacker/vandal"

see title

2
0
Silver badge
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.

0
0
Meh

"breaks"

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

2
0

This post has been deleted by a moderator

Bronze badge
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
8
Silver badge

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

0
0

Singularity

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

0
0
Silver badge
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
0
Bronze badge

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.

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

2
2
Mushroom

Thanks for the heart attack!

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

0
0
Bronze badge
Facepalm

Why the fearmongering headline?

What's wrong with:-

'Groundbreaking' attack doesn't compromise AES in any practical way

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

1
0
Silver badge

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

0
0
M7S
Bronze badge

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

0
0
Thumb Down

Seriously misleading headline

Interesting read but forget the headline guys

0
0
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
0
Silver badge
WTF?

"Wonder if" just doesn't cut it.

SHOW ME THE MATH!

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

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

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

2
1

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.

1
0
Silver badge
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.

0
1
Silver badge

@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

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

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

0
0
Silver badge
Pint

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

There is a dead parrot sketch in there somewhere.

2
0
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
0
Silver badge
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.

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

0
0
Silver badge
Happy

@Steve Knox

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

Two words: Schrodinger's cat

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

0
0

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

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

0
1
Thumb Down

Ugh!

Just wasted 5 mins of my life on this article

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

0
0
Bronze badge
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

0
0
Big Brother

Setec Astronomy

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

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

2
0

Page:

This topic is closed for new posts.