Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series: Advanced Encryption Standard

Last time I wrote about the DES cipher, so today (yes, you guessed it) I'm writing about how the AES works. AES was created as a result of an open contest proposed by the NIST. In 1997, the NIST announced their wish to have a new encryption standard which would substitute the Data Encryption Standard and was to be called AES: Advanced Encryption Standard.

Several researchers submitted their proposals to the AES contest, but the winning candidate was the so called Rijndael cipher. This cipher was originally created by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, who submitted it to the AES selection process.

The other finalists were Twofish (Bruce Schneier and others), Serpent (Ross Anderson and others), MARS (the team included Don Coppersmit) and RC6 (Ron Rivest [the R in RSA :-p ] and others).

After the contest, the NIST published AES as a FIPS standard, and since then the AES cipher has been extensively used and analyzed. In the remaining of this post we see how AES works, as we did with DES in the previous post.

NOTE: Just as in previous entry, images are taken from Wikipedia. Let me know if you try to read the post and they don't work anymore.

AES Structure

Again, we start by looking at the overall structure of the AES cipher. In the case of AES, the block size is 128 bits and the key size can be 128, 192 or 256 bits. The original Rijndael specification also supported several block sizes, but in the AES standard itself only 128 bits blocks are defined.

Just like with DES, the cipher consists of a basic operation called round which is repeated a number of times. In this case, AES is based in a design principle called Substitution-Permutation Networks which means that the cipher is composed of a series of substitutions and permutations one after each other.

The number of rounds (R) in AES depends on the key length: 10 rounds for 128, 12 rounds for 192 and 14 rounds for 256 bits. AES works on a structure known as the AES state, which is simply an arrangement of the block in a 4x4 matrix. Furthermore, most AES operations can be described as operations in the finite field. This gives AES a quite neat algebraic description.

However, they can also seen as byte operations, and we'll look at it mainly as a byte operation, since we don't really want to get into math here (I promised you!). But if you really want to get deep into crypto, then you will certainly need to learn about finite fields. They get more important in public key crypto, where we actually use difficult mathematical problems to protect our data... but we'll get into that later.

The basic building blocks of the AES cipher are as follows:

• SubBytes - A non-linear substitution, the AES S-boxes
• ShiftRows - Shifts the rows of the AES state (hence the name!)
• MixColumn - Mixes columns of the AES state, making each result cell a combination of other cells
• AddRoundKey - Mixes the input AES state with the current round key

As you can see, like in DES we have S-boxes, we have transpositions (ShiftRows), a mixing operation (MixColumn) and an operation to mix the data and the key. An AES encryption consists of the following steps:

1. Initial round:
   • AddRoundKey
2. R-1 rounds:
   • SubBytes
   • ShiftRows
   • MixColumns
   • AddRoundKey
3. Final round (without MixColumns):
   • SubBytes
   • ShiftRows
   • AddRoundKey

So, we have an initial AddRoundKey step, which mixes input data with the 0th round key. Then, R-1 (9,11 or 13) identical rounds take place, and at the end a final round is applied. Now we'll see a more detailed explanation of each of these round components.

SubBytes

As I already said, this is just a substitution table. In this case, we don't have 8 different substitutions as in DES but just one. For those who can understand it, this substitution table is actually an operation on the field with irreducible polynomial which finds the multiplicative inverse of the input byte and then applies an affine transformation.

For those of you who don't know anything about finite fields, let's look at a very basic example of a finite field: the set of integer numbers modulo 7 (i.e., numbers from 0 to 6). With this set of numbers, we can define an addition operation (just add modulo 7) and a product operation (multiply modulo 7), then we would have:

And now, we define the multiplicative inverse of a given member of the field, , as the member such that . So, from our previous example 4 is the multiplicative inverse of 2 modulo 7.

In the case of AES, the operations take place in the field, but the idea is basically the same: we have an addition and a multiplication operation, and we find a number such that after multiplying it by the input number (in the field!) we get 1. I hope it's clear 🙂

Now, after taking the inverse (which can be done pretty fast with the extended version of Euclid's algorithm), AES applies an affine transformation to avoid some kind of attacks. An affine transformation is just a construction which takes x as an input, and produces an output of the form a·x+b.

Don't worry, you don't really need to know these details, but it doesn't hurt to have some concept of what AES actually does 😉

ShiftRows

This operation just shifts the rows of the AES state. It's easier to see it with an image:

So you can see how row zero remains intact, row one is shifted once to the left (and therefore the first element goes to the last position), row 2 two times and row 3 three times.

MixColumns

This is another mathematical operation which can be seen in several forms. First, it can be seen as a multiplication by a polynomial modulo another polynomial (wow!). Second, it can be seen as a multiplication by an MDS matrix... or you can just think of it as a way of mixing several columns which is easier.

If you want to actually know what happens at this stage, look at the Wikipedia page for the Rijndael mix columns operation.

AddRoundKey

This is the simplest step, but an important one nonetheless... otherwise we wouldn't have any key involved so far! For each round, a round key of the same length as the input block (128 bits) is generated and transformed into the state form. Then, each byte of the current AES state is XORed with the corresponding byte of the key state.

AES Key schedule

So far we've seen all the components of the AES cipher, but we don't know how to generate the round keys. This is done by a scheduling algorithm, which can be run beforehand or together with the cipher. Devices with the luxury of having plenty of memory will normally precompute the round keys, and small devices such as smart cards probably prefer to compute them on the fly because they lack memory space.

The components of the key schedule are:

• Rotate - Rotates a 32 bit word 8 bits to the left
• Rcon - A round dependent constant, which can also be defined as a certain power of two in Rijndael's finite field
• SubBytes - The same SubBytes as in the main cipher

The key schedule algorithm steps are quite large and I do not want to write them down here. You can find them in the standard or in the corresponding wikipedia page: Rijndael key schedule.

AES Decryption

In this case, decryption is not as easy as for DES. Decryption involves performing the inverse operations of the ones performed for encryption, which means that one needs to define the inverse operations for ShiftRows, SubBytes and MixColumns. AddRoundKey does not need an inverse since it is already its own inverse.

Obviously, all these operations are also defined in the standard, and you can take a look at it to know how they are defined.