World's toughest encryption scheme found 'vulnerable'

Aug 23, 2011 by Jennifer Seberry, Professor of Computer Security at University of Wollongong

It was announced last week that cryptography researchers have found a “vulnerability” in the encryption scheme used in the vast majority of secure online transactions – a scheme known as AES-256.

Every important electronic transaction you make online is encrypted – your banking, your census form, your credit card payments.

AES-256 – the Advanced Encryption Standard – was approved by the US National Institute of Standards in 2002 to be used in all unclassified communications.

As well as its almost almost-ubiquitous use in e-commerce, AES-256 is used to secure household WiFi connections, mobile phone connections and a range of other applications.

So how does AES-256 work?

Simply, it takes the data you are trying to encrypt – your online banking username and password, for example – and scrambles it with with a secret “key” 256 bits in length.

If you know the encryption key (as the bank does) then you can decrypt the scrambled information and use it accordingly – logging you in, in the case of online banking.

If you don’t know the encryption key and want to get access to it, you effectively need to try all of the possible combinations – a so-called “brute force” attack.

Being a 256-bit key, there are a lot of possible combinations: 2256 to be precise or, written in it’s full form: 116,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000.

That’s more than the number of atoms in the entire universe.

AES emerged from a competition in which cryptographers were asked to submit their attempt at a secure encryption scheme. Fifteen submissions from all around the world were considered, including one called LOKI which was developed by myself and my colleagues.

After a lengthy analysis process by academics and government agencies the winning algorithm – known as Rijndael – became the new international encryption standard.

Academics and government analysts continue to study algorithms – such as AES-256 – long after they have been deployed by industry as there is always new research and new improvements in computer technology that might make an algorithm insecure.

Academics say an algorithm is “broken” if it has a “certification weakness”. Simply, an encryption implementation is said to have a certification weakness if the content of the encrypted message can be read in less time than it would take to try every possible key.

So what does the vulnerability discovered in AES-256 mean for those of us using online transactions?

Firstly, it’s worth noting that the recent attack was part of a program undertaken by renowned cryptanalysists at Microsoft and the Katholieke Universiteit of Leuven in Belgium – a university famous for its design and analysis of cryptographic algorithms.

This is an attack by the “good guys” to determine how hard it would be for someone with less-than-noble intentions to access encrypted information.

Media reports suggest the researchers found a way of decrypting AES that is three to five times faster than any previous method.

Fine. Good. But let’s put that into context.

Until this new development, any attempts to decrypt information encrypted with AES-256 would have taken many times the length of the universe to carry out. This is due simply to the number of possible encryption keys that need to be guessed.

Three or four times faster than the age of the universe is still billions of years and as a result, circumventing AES-256 encryption is still incredibly impractical, to put it mildly.

Even if the largest botnet ever discovered – the 30-million-computer-strong BredoLab botnet – was given the task of attacking an AES-256 implementation, the sheer number of possible combinations would make the task virtually impossible.

So, should you be worried about you electronic transactions being insecure? At the moment, no.

The newly-discovered vulnerability is certainly interesting but plenty of further study is needed before we are even close to thinking AES implementations are insecure.


This story has been republished from The Conservation (http://theconversation.edu.au). [licensed under Creative Commons — Attribution/No derivatives]

Explore further: Ride-sharing could cut cabs' road time by 30 percent

More information: Research paper research.microsoft.com/en-us/p… yptanalysis/aes.aspx

Related Stories

Stellar super soaker

Jun 15, 2011

Located in the constellation of Perseus and just a mere 750 light years from Earth, a young protostar is very busy spewing forth copious amounts of water. Embedded in a cloud of gas and dust, the hundred thousand ...

Recommended for you

Ride-sharing could cut cabs' road time by 30 percent

Sep 01, 2014

Cellphone apps that find users car rides in real time are exploding in popularity: The car-service company Uber was recently valued at $18 billion, and even as it faces legal wrangles, a number of companies ...

Avatars make the Internet sign to deaf people

Aug 29, 2014

It is challenging for deaf people to learn a sound-based language, since they are physically not able to hear those sounds. Hence, most of them struggle with written language as well as with text reading ...

Chameleon: Cloud computing for computer science

Aug 26, 2014

Cloud computing has changed the way we work, the way we communicate online, even the way we relax at night with a movie. But even as "the cloud" starts to cross over into popular parlance, the full potential ...

User comments : 10

Adjust slider to filter visible comments by rank

Display comments: newest first

stealthc
1 / 5 (1) Aug 23, 2011
how many minutes of time did this discovery shave off using a quantum computer to eat through this encryption like it's butter? so far we have the dwave one, can't it do the job?
JoshuaHill
5 / 5 (7) Aug 23, 2011
This AES coverage is quite misleading. The old work factor for guaranteed key recovery was 2^256. The new work factor is 2^(254.4). Let's all run around screaming now!
blazingspark
not rated yet Aug 23, 2011
how many minutes of time did this discovery shave off using a quantum computer to eat through this encryption like it's butter? so far we have the dwave one, can't it do the job?
Quantum computing might turn out to be pointless. You entangle the computations so you get all the answers at once. Then you need to disentangle the answers.

Only time will tell if there is any benefit to be had from that stuff.
that_guy
5 / 5 (1) Aug 23, 2011
how many minutes of time did this discovery shave off using a quantum computer to eat through this encryption like it's butter? so far we have the dwave one, can't it do the job?

you're mixing pie in the sky theoretical potential with reality. There is only one model of 'quantum' computer, and even at that, it is questionable if it truly is (IEEE says it isn't a true quantum computer), as the company that makes it is very secretive. That said, it is very slow, and even given its possible advantages, It couldn't gain a significant edge on this.

So stealth, in conclusion, quantum computing is at the eniac level, and outside of that, it's all hype and theory.
that_guy
5 / 5 (1) Aug 23, 2011
Some Quotes from the D-Wave wikipedia page about the D-Wave One
May 20, 2011, D-Wave Systems is marketing a $10,000,000 Quantum Computer named "D-Wave One" with a 128-qubit (quantum bit) chipset that performs just a single task -- discrete optimization.

A single task - discrete optimization. Like coming up with "3" for pi, instead of 3.14...
That speed up unfortunately does not hold in the setting at hand, and therefore D-Wave's "quantum computer" even if it turns out to be a true quantum computer, and even if it can be scaled to thousands of qubits, would likely not be more powerful than a cell phone."

No more powerful than a cell phone...at the things that it is supposed to excel in...

If you're going to shill for something, you could try doing a little bit of research on it first.
default_ex
1 / 5 (2) Aug 24, 2011
It's not common at all to find wireless routers/access points that support AES-256 without modifying it, much more commonly you find AES-128 and AES-192. In any case AES has been cracked to death by high end gaming hardware, all the way up to AES-512. Step up into the computational realm (Nvidia Tesla) then AES-1024 becomes crackable.

It's convincing enough, AES is not secure at all when the methods to crack it in a reasonable amount of time given powerful hardware is known before that hardware becomes available. Forget the realm of 0day cracking, welcome to yesterday cracking.
Expiorer
5 / 5 (2) Aug 24, 2011
and thats why VULNERABLE is in quotes in title.
john0
5 / 5 (5) Aug 24, 2011
@ default ex:

1) There is no such thing as AES-512 or AES-1024. You should have at least read a wikipedia entry about AES before spitting out such bizarre things

2) Nvidia Teslas aren't a lot more powerful than regular high end GPUs, they are just built with more ram, better drivers, 24/7 rated operation and double precision.

3) Computational realm isn't only about 'Teslas'. Computational realm is everything from CPU to your average cuda-capable GPU.

4) 'AES is not secure at all' is a tremendous stretch. You talk about future hardware, forgetting that when technology advances so much, software usually follows the trend. When something 1000x more powerful than our current supercomputers come out, its likely we will have already engineered new encryption algorythms.

5) You say 'AES has been cracked to death by high end gaming hardware'. Yeah, seriously, when did it happen? Can you cite a reliable source?

6) Nice trolling, I've never seen a post so dense of mis-information
Doug_Huffman
3 / 5 (2) Aug 24, 2011
PhysOrg's headline writer's use of scare-quotes, 'vulnerable', is as pathetic as the overuse of virtually. The word that follows virtually is virtually a lie, often called out with scare-quotes.
that_guy
5 / 5 (1) Aug 26, 2011
@ John. Nice, you pulled apart that troll piece by piece. Only caveat is that you just knowingly allowed yourself to get trolled...

@Doug - Did you read the other guy about 'vulnerable' in quotes? Now, if you had actually read or comprehended said article, you would have seen where it meticulously explains that 'vulnerable' here is specifically a technical definition which is the exact correct conclusion. By putting it in the quotes, the physorg editor specifically set it out, where 'vulnerable' is the correct term, but allowing us to know that there is more to it. Physorg did not pick the term vulnerable.