October 22, 2014

Theoretical Weaknesses in AES Discovered

(LiveHacking.Com) – The Advanced Encryption Standard (AES) encryption algorithm used by the U.S. government has been the subject of much research since it was adopted in 2001. The latest research by Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger has discovered a way to reduce the number of keys needed to perform a brute force attack by more than a factor of 3.

The research has shown that by using a method of attack known as Biclique Cryptanalysis the effective key lengths of 128, 192 and 256 bits are reduced to 126, 190 and 254 bits. According to the authors, as this attack is of high computational complexity, it does not threaten the practical use of AES in any way.

To break a cipher by brute force requires that every key combination is tested to see if it successfully unlocks the encrypted data. For a 128 bit key this means that there are 2128 possible keys. If a computer could test 1,000,000,000 keys per second it would take 10,000,000 quadrillion years to break the code.

The new attack against AES reduces a 128 bit key to effectively a 126 bit key. This means the same data could now be decrypted in just 2,690,000 quadrillion years!

Even if the key could be reduced to just 264 key possibilities it would still take about 500 years to decipher the data.

However, in 2002 a distributed network of some 300,000 computers all over the world, known as distributed.net, was able to find a 64-bit RC5 key using brute force attack in just under 5 years.

It was estimated that this network of computers had a throughput of over 30 teraFLOPS (30,000,000,000,000). This was in the age of single core 1.3Ghz Pentium 4 CPUs and limited access to GPUs for deciphering.

A modern super-computer can compute at 2 petaFLOPS. Although this is a measure of its raw computing power, for illustration we can imagine that it can test keys at 2 petaFLOPS (which it can’t). That means it could break a 128 bit key in 5 quadrillion years. Or a 126 key in only one quadrillion years. However, such a computer can break a 64 bit key in just 2.5 hours.

To quote the U.S. National Security Agency, “Attacks always get better; they never get worse.”

What this new research means is that it is possible to reduce the effectiveness of AES. Further research will most likely yield other weaknesses. If the keys can be reduced even further then the time needed to break them will also reduce.