Rijndael is a family of block ciphers developed by Belgian cryptographers Vincent Rijmen and Joen Daemen. It was submitted as an entry to the National Institute of Standards and Technology’s (NIST) competition to select an Advanced Encryption Standard (AES) to replace Data Encryption Standard (DES). In 2001, Rijndael won the competition and the 128, 192, and 256-bit versions of Rijndael were officially selected as the Advanced Encryption Standard.

The three variants of AES are based on different key sizes (128, 192, and 256 bits). In this article, we will focus on the 128-bit version of the AES key schedule, which provides sufficient background to understand the 192 and 256 bit variants as well. At the end, we’ll include a note the other variants, and how they differ from the 128-bit version.

Encryption with AES

The encryption phase of AES can be broken into three phases: the initial round, the main rounds, and the final round. All of the phases use the same sub-operations in different combinations as follows:

• Initial Round
• AddRoundKey
• Main Rounds
• SubBytes
• ShiftRows
• MixColumns
• AddRoundKey
• Final Round
• SubBytes
• ShiftRows
• AddRoundKey

The main rounds of AES are repeated a set number of times for each variant of AES. AES-128 uses 9 iterations of the main round, AES-192 uses 11, and AES-256 uses 13.

Overall structure of encryption and decryption in Advanced Encryption Standard

The four sub-operations of AES are AddRoundKey, SubBytes, ShiftRows, and MixColumns. These are explained in more detail in the following subsections.

AddRoundKey

The AddRoundKey operation is the only phase of AES encryption that directly operates on the AES round key. In this operation, the input to the round is exclusive-ored with the round key.

SubBytes

The SubBytes phase of AES involves splitting the input into bytes and passing each through a Substitution Box or S-Box. Unlike DES, AES uses the same S-Box for all bytes. The AES S-Box implements inverse multiplication in Galois Field 2⁸. The AES S-Box is shown in the Table below.

To read this Table, the byte input is broken into two 4-bit halves. The first half determines the row and the second half determines the column. For example, the S-Box transformation of 35 or 0x23 can be found in the cell at the intersection of the row labeled 20 and the column labeled 03. Therefore decimal 35 becomes 0x26 or decimal 38.

ShiftRows

In the ShiftRows phase of AES, each row of the 128-bit internal state of the cipher is shifted. The rows in this stage refer to the standard representation of the internal state in AES, which is a 4x4 matrix where each cell contains a byte. Bytes of the internal state are placed in the matrix across rows from left to right and down columns.

In the ShiftRows operation, each of these rows is shifted to the left by a set amount: their row number starting with zero. The top row is not shifted at all, the next row is shifted by one and so on. This is illustrated in the Figure below.

In the Figure, the first number in each cell refers to the row number and the second refers to the column. The topmost row (row 0) does not shift at all, row 1 shifts left by one, and so on.

MixColumns

Like the ShiftRows phase of AES, the MixColumns phase provides diffusion by mixing the input around. Unlike ShiftRows, MixColumns performs operations splitting the matrix by columns instead of rows.

A visual representation of the MixColumns operation is shown above. Unlike standard matrix multiplication, MixColumns performs matrix multiplication as per Galois Field 2⁸. Although we won’t describe this step in detail, it is important to note that this multiplication has the property of operating independently over each of the columns of the initial matrix, i.e. the first column when multiplied by the matrix, produces the first column of the resultant matrix.

The AES Key Schedule

The AES Key Schedule is used to produce a set number of round keys from the initial key. In AES, the initial key is used in the initial round of AES as input to the AddRoundKey operation. From this key, 10, 12, or 14 round keys are produced as input to the other AddRoundKey operations in the 128, 192, and 256-bit versions of AES.

The Figure above illustrates the round key transformation of AES-128. Each of the cells at the top and bottom of the image represents a byte of the previous round key (the initial key for round one). Each word (32 bytes) of the previous round key is exclusive-ored with some value to produce the corresponding word of the current round key. In the case of words 1-3, the value used in the exclusive-or is the previous word (words 0-2) of the previous round key. For the first word of the round key, the value used in the exclusive-or is the result of passing the last word of the previous round key through the g function.

The g function of the AES key schedule is illustrated in the Figure above. As shown, the operation consists of three stages: an S-Box transformation, a permutation, and an exclusive-or. The S-Box operation used in the AES key schedule is identical to the one used in the encryption phase as described previously. In the permutation phase of the g function, each byte of the word is shifted one position to the left. Finally, the leftmost byte is exclusive-ored with a round constant. The rounds constants in AES are the value of 2^round_number modulo Galois Field 2⁸.

The output of the key schedule function is used as the round key input to the AddRoundKey operation in AES encryption. An identical transformation on the round key is performed to produce the next round key.

Decryption in AES

To decrypt an AES-encrypted ciphertext, it is necessary to undo each stage of the encryption operation in the reverse order in which they were applied. The three stage of decryption are as follows:

• Inverse Final Round
• AddRoundKey
• ShiftRows
• SubBytes
• Inverse Main Round
• AddRoundKey
• MixColumns
• ShiftRows
• SubBytes
• Inverse Initial Round
• AddRoundKey

Of the four operations in AES encryption, only the AddRoundKey operation is its own inverse (since it is an exclusive-or). To undo AddRoundKey, it is only necessary to expand the entire AES key schedule (identically to encryption) and then use the appropriate key in the exclusive-or.

The other three operations require an inverse operation to be defined and used. The first operation to be undone is ShiftRows. The Inverse ShiftRows operation is identical to the ShiftRows operation except that rotations are made to the right instead of to the left. This is illustrated in the Figure below.

The next operation to be undone is the SubBytes operation. The Inverse S-Box is shown in the Table below. It is read identically to the S-Box matrix.

The last inverse operation to define is MixColumns. Like MixColumns, Inverse MixColumns can be defined as the matrix multiplication in Galois Field 2⁸. This is illustrated in the Figure below.

The reason why this multiplication inverts the initial operation is because of how math works in the Galois Field 2⁸, which we won’t describe in detail in this tutorial. However, note that the specific values in both matrices are chosen in a way such that one multiplication is the inverse of the other in Galois Field 2⁸.

AES ciphertexts are decrypted by following the order of operations explained at the beginning of this section, using the appropriate inverse operations and using round keys in reverse order.

Variants of AES

There are three variants of AES based on different key sizes (128, 192, and 256 bits). Above we described the 128-bit version of the AES key schedule.

All three variants of AES use a 128-bit block size, only the key sizes differ. The overall structure of the encryption stage of AES is identical for all three variants, but the number of rounds varies for the 128, 192, and 256-bit variants (10, 12, and 14 rounds respectively). The key schedule is different for each variant.

Advantages of AES

One of the primary advantages of AES is its ubiquity. Since it is defined as the standard used by the US government, it is supported by most vendors. Also, it is relatively fast in both hardware and software.

The three possible key lengths supported by AES allow users to pick a tradeoff between speed and security. Increased key length increases the execution time of both encryption and decryption. At this time, all three key lengths are considered secure and the best known attacks against AES reduce effective key length by at most three bits.

AES uses a single S-Box for all bytes in all rounds. In contrast, DES uses eight distinct S-Boxes, which increases implementation requirements.

Disadvantages of AES

AES has a very simple key schedule and simple encryption operations. Many AES attacks are based upon the simplicity of this key schedule and it is possible that one day an attack will be created to break AES encryption.