kotfu.net

I got an email this week from a well-intentioned colleague informing me that AES had been hacked and we should go find another encryption algorithm to use. I assumed he was talking about the Biclique Cryptanalysis of the Full AES by Microsoft Research, a recently published break in the AES algorithm. So what does a break really mean?

Cryptographers (those who practice the art and science of keeping messages secret) always assume that the attacker knows all the details of the encryption algorithm, like having the source code to the encryption software. They also assume the encryption keys are random. Given those assumptions, there are three basic ways for an attacker to get the cleartext of an encrypted message. The first way is to try all of the available encryption keys, knowing that one of them has to be the one that will expose the contents. This is called a brute force attack. The second approach requires exploiting some flaw in the encryption algorithm to eliminate large numbers of potential keys without actually having to try them. The third way would be to get the key or the cleartext via some other method, like stealing the disk from the server that contains the key. If you can’t keep your keys or cleartext safe then it doesn’t matter what encryption algorithm you use. Cryptographers consider an algorithm broken when there is a way to attack it that is faster that brute forcing all of the available keys.

Background on AES

On Jan 2, 1997, the National Institute of Standards and Technology (NIST) announced they were interested in choosing a successor to the Data Encryption Standard (DES). This newly selected algorithm would be known as the Advanced Encryption Standard (AES). Eight months later, after reviewing public input on how the new algorithm should be chosen, they solicited block ciphers supporting key lengths of 128, 192, and 256 bits. They received 15 submissions.

For the next three years, the new algorithms were investigated by cryptographers and performance tested in a variety of settings both software and hardware. In late 2000, Rijndael was announced as the winner, and a year later AES was approved as FIPS PUB 197. There are three authorized variants of Rijndael defined in AES that differ in the key length and the number of rounds: 10 rounds for 128 bit keys, 12 rounds for 192 bit keys, and 14 rounds for 256 bit keys.

In June 2003 the NSA announced that any official variant of AES was secure enough to protect classified information up to the SECRET level; TOP SECRET information requires the use of 192 or 256 bit keys.

Brute Forcing AES

So how long would it take to brute force attack a message encrypted with AES using a 128 bit key? It would of course depend on how fast of a device you were using. In June 2011 TOP500 updated their list of the fastest super computers in the world. The fastest one, the K Computer, can do 8,200,000,000,000,000 (8.2 quadrillion) calculations per second. According to the Wall Street Journal (article requires login, google it to get the whole thing without logging in), this device cost $1.25 billion to construct. Let’s borrow it for our attack.

During the NIST selection process, the various algorithms were benchmarked carefully for encryption speed. That paper doesn’t specifically address decryption speed, but it does have one relevant nugget: Rijndael, the eventual winner, takes 1400 clocks to set up a decryption key before you can even try and decrypt anything. For this example we’ll sprinkle pixie dust over the K Computer and speed it up by several orders of magnitude so it can setup a decryption key and decrypt the ciphertext using all 10 rounds of AES-128 in a single clock cycle (or calculation as they are called in the TOP500 list).

Using this now magical device, we could brute force a 56 bit key (the old DES standard used 56 bit keys) in 2⁵⁶ clock cycles, which would take 8 seconds.

Brute forcing a 128 bit key using this device would take 1,315,888,179,366,587 (1.3 quadrillion) years. That’s the same as 1,315,888 billion years. Current scientific models predict the universe to be 13 billion years old. The times required to brute force 192 and 256 bit keys are astronomically larger.

But AES is broken right?

When talking about the cryptanalysis (the art of deciphering coded messages without the key) of AES, it’s important to remember the definition of AES. AES requires the Rijndael algorithm used with a block size of 128 bits and one of the following key lengths and number of rounds: 128 bit key for 10 rounds, 192 bit key for 12 rounds, or a 256 bit key for 14 rounds.

There have been several published breaks of the Rijndael algorithm, many of them require a reduced number of rounds from those specified in AES. In 2009, two significant breaks of AES-192 and AES-256 were published. These attacks exploit the weak key schedule of AES-192 and AES-256 that is not present in AES-128. The best of these breaks on AES-256 reduces the complexity of the attack from 2²⁵⁶ to 2¹¹⁹, a substantial decrease. Nevertheless, it is still not a practical attack. Our magical cracking device would still take 2.5 trillion years to recover an AES-256 key.

The new Biclique Cryptanalysis my co-worker was worried about describes a key recovery attack that works against all three variants of AES. It’s different than most of the other published attacks in several important ways. In many of the other breaks, the attacker requires the use of several different keys which have some sort of mathmatical relationship. These related-key attacks tend to be less practical to implement. Having said that, the Wired Equivalent Privacy (WEP) scheme used in WiFi networks failed because of a related-key attack. The algorithmic weakness was combined with a poor implementation that didn’t use a random key. The new attack is also unique because all three AES variants are affected, it is a different attack vector than the key schedule weakness in AES-192 and AES-256.

In the abstract of the new paper the authors state:

As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

So what do they mean by “high computational complexity”. When applied to AES-128, they reduce the computational complexity from 2¹²⁸ to 2^126.1. Instead of taking 1.3 quadrillion years, our magical cracking supercomputer would only need 328 trillion years.

So now what?

There are still no known practical attacks on AES, there is still plenty of safety margin on all three AES variants. Bruce Schneier, a widely recognized security expert, weighs in on the new attack:

And for new applications I suggest that people don’t use AES-256. AES-128 provides more than enough security margin for the forseeable future.

There is no need to have NIST call for new algorithms and choose a new standard and there is certainly no need for my colleague to switch from AES to Serpent. Even so, attacks always get better, they never get worse.

Maybe we can teach our magical supercomputer how to steal someone’s password.