Understanding the Advanced Encryption Standard (AES)

Advanced Encryption Standard (AES)

With concerns over DES and 3DES not providing a secure basis for the future, the US government opened a competition for a successor, and chose the variable block size Rijndael algorithm from Vincent Rijmen and Joan Daemen as the basis of the Advanced Encryption Standard (AES). In the AES standard a fixed block size of 128-bits is chosen with 128-bit, 192-bit and 256-bit key lengths, and the number of rounds to produce a result varies with the key size (i.e. 4 rounds for 128-bits, 6 rounds for 192 bits, and 8 rounds for 256-bits). Blocks are split into a matrix of four rows and four to eight columns (depending on key size) of 8-bit values called the state. The encryption algorithm consists of a number of rounds of the following four named steps, and is heavily dependent on matrix operations and the XOR operation:

1)   SubBytes – In this step, each element of the state matrix is run through a substitution box (S-box).

2)   ShiftRows  - In this step, each of the row elements is cyclically shifted via a shifting permutation box (P-box).

3)   MixColumns – In this step, another permutation box (P-box) is used to mix up the bits of each column using a function.

4)   AddRoundKey – In this step, a portion of the key schedule uses an exclusive OR (XOR) operation with the state matrix. This is the only step that makes use of the key.

The encryption steps are executed as follows:

a)    Perform AddRoundKey on the state matrix values

b)   Perform the following steps n - 1 times, where n is the number of rounds for the given key size

a.     Run SubBytes on the current state matrix

b.     Run ShiftRows on the current state matrix

c.      Run MixColumns on the current state matrix

d.     Run AddRoundKey on the current state matrix

End Round Loop

c)    Run SubBytes on the current state matrix

d)   Run ShiftRows on the current state matrix

e)    Run AddRoundKey on the current state matric

So, the first round just runs AddRoundKey, and the last round misses out the MixColumns step.

Decryption uses the some of same process steps, and some inverse process steps.

a)    Perform AddRoundKey on the state matrix values

b)   Perform the following steps n - 1 times, where n is the number of rounds for the given key size

a.     Run InverseSubBytes on the current state matrix

b.     Run InverseShiftRows on the current state matrix

c.      Run InverseMaxColumns on the current state matrix

d.     Run AddRoundKey on the current state matrix

End Round Loop

c)    Run InverseSubBytes on the current state matrix

d)   Run InverseShiftRows on the current state matrix

e)    Run AddRoundKey on the current state matric

SubBytes

The S-box for the SubBytes step for the Rijndael algorithm, essentially a lookup table, works on an inverse multiplication algorithm that transforms every one of the 256 possible byte values to another individual byte value. It can be described in many different ways, but here we will describe it with matrix multiplication at the bit level followed by an XOR of the result. Often it is implemented as a simple lookup table.

Consider the input matrix a consisting of bits 0 to 7 and the output matrix b for encryption purposes in big endian format for the forward S-box:

b7		1	1	1	1	1	0	0	0		a7		0
b6		0	1	1	1	1	1	0	0		a6		1
b5	=	0	0	1	1	1	1	1	0	x	a5	XOR	1
b4		0	0	0	1	1	1	1	1		a4		0
b3		1	0	0	0	1	1	1	1		a3		0
b2		1	1	0	0	0	1	1	1		a2		0
b1		1	1	1	0	0	0	1	1		a1		1
b0		1	1	1	1	0	0	0	1		a0		1

Note that in the core transformation matric, the values across the rows consist of five 1s followed by three zeros, shifted in each row. So, the rows at the byte level consist of the bytes 248 (0xF8), 124 (0x7C), 62 (0x3E), 31 (0x1F), 143 (0x8F), 199 (0xC7), 227 (0xE3), and 241 (0xF1); which can be implemented as a circular bit shifter, so after half way through the byte the values have 128 or 0x80 added and it should be evident the hexadecimal digits swap in the pattern half way through as a result. The values in the core transformation matrix are multiplied with the bit values from the input and then an XOR operation with [0, 1, 1, 0, 0, 0, 1, 1] is performed.

ShiftRows

The ShiftRows step performs a circular shift of the bytes at each row of the state matrix, with the four columns for 128-bit blocks, six columns for 192-bit blocks, and eight columns for 256-bit blocks. So, the first row is left as it is unchanged, the second row is rotated once to the left, the third row is rotated twice to the left, and the fourth row is shifted three times to the left. So, for 128-bit and 192-bit blocks each row is circular shifted left by n – 1 bytes, but for 256-bit blocks the offsets are zero for the first row, but one byte for the second row, three bytes for the third row, and four bytes for the fourth row in Rijndael, but this is not relevant to the AES implementation which does not use 256-bit blocks. ShiftRows is one of the steps that contributes to the statistical randomization of the ciphertext.

MixColumns

This is the most complicated part of the Rijndael/AES algorithm, and in it the four bytes of each column of the state are combined via a linear transformation such that the four bytes input result in four bytes output, each of which is dependent on each of the four input bytes. It is the matrix multiplication in the Galois Field (8) that gives this effect. The matrix is as follows to give the new entries b_ic from the original entries a_ic for each column where _c is 1,2,3 and 4:

b0c		2	3	1	1		a0c
b1c	=	1	2	3	1	XOR	a1c
b2c		1	1	2	3		a2c
b3c		3	1	1	2		a3c

Essentially, we are multiplying two eight bit numbers and taking the remainder modulo 283, which is binary 100011011, and we use a binary XOR long division. We have shown the operation for one column above, but it is repeated for all four columns.

AddRoundKey

The final step, AddRoundKey, takes each 8-bit value within the state matrix with an 8-bit value of the key schedule, i.e. a bitwise XOR of the current block with a portion of the expanded key. It consists of a number of sub operations.

Block sizes are computed in terms of 32-bits that are split into 4 8-bit bytes, so a 128-bit cipher has block size of 4, a 192-bit block cipher has a block size of 6, and a 256-bit block cipher has a block size of 8.  Each of the 8-bit bytes is run through the SubBytes function and concatenated back together, and then each is cyclically rotated left 8-bits to replace each value with that on its right. A constant matrix is then used for multiplication with values [1,2,4,8,16,32,64,128,27,54,108,216]; each less than 256 to avoid overflowing a byte value. 

InvSubBytes

This merely uses an inverted version of the S-Box matrix from the SubBytes operation to reverse the operation.

For decryption purposes, an inverse S-box is used, in little endian form, and again we use matrix multiplication although usually a simple lookup table is used for implementation to give the new entries b from the original entries a:

b7		0	1	0	1	0	0	1	0		a7		0
b6		0	0	1	0	1	0	0	1		a6		0
b5	=	1	0	0	1	0	1	0	0	x	a5	XOR	0
b4		0	1	0	0	1	0	1	0		a4		0
b3		0	0	1	0	0	1	0	1		a3		0
b2		1	0	0	1	0	0	1	0		a2		1
b1		0	1	0	0	1	0	0	1		a1		0
b0		1	0	1	0	0	1	0	0		a0		1

Thus, the rows at byte level consist of the bytes 82 (0x52), 41 (0x29), 148 (0x94), 74 (0x4A), 37 (0x25), 146 (0x92), 73 (0x49), and 164 (0xA4). Again, these can be implemented as a circular bit shifter, and it should be evident the hexadecimal digits swap in the pattern half way through as a result. The values in the core transformation matrix are multiplied with the bit values from the ciphertext input and then an XOR operation with [0, 0, 0, 0, 0, 1, 0, 1] is performed.

InvShiftRows

This InvShiftRows operation simply rotates each row in the opposite direction to that in the ShiftRows, so the shift is to the right instead of to the left.

InvMixColumns

For decryption, the inverse mix columns operation just uses a different matrix to get the result:

b0c		15	11	14	9		a0c
b1c	=	9	15	11	14	XOR	a1c
b2c		14	9	15	11		a2c
b3c		11	14	9	15		a3c