19 Advanced Encryption Standard(part2)

Learning Objectives:

• To understand the AES selection process
• To know the details of Rijndael – the AES cipher
• Discuss about the steps in each round and the key expansion
• To understand the implementation aspects

2.1 Introduction

We have studied AES selection process, key expansion and implementation aspects in last module. This section deals with different operations such as ShiftRows,MixColumns,AddRoundKey in each round of AES in details.

2.2 ShiftRows

The ShiftRows stage provides a simple “permutation” of the data, whereas the other steps involve substitutions. Further, since the state is treated as a block of columns, it is this step which provides for diffusion of values between columns. It performs a circular rotate on each row of 0, 1, 2 & 3 places for respective rows. When decrypting it performs the circular shifts in the opposite direction for each row. This row shift moves an individual byte from one column to another, which is a linear distance of a multiple of 4 bytes, and ensures that the 4 bytes of one column are spread out to four different columns.

2.3 ShiftRows Scheme

Figure given below illustrates the Shift Rows permutation.

2.4 MixColumns

The MixColumns stage is a substitution that makes use of arithmetic over GF(28 ). Each byte of a column is mapped into a new value that is a function of all four bytes in that column. It is designed as a matrix multiplication where each byte is treated as a polynomial in GF(28). The inverse used for decryption involves a different set of constants.

Effectively a matrix multiplication in GF(28) using prime poly m(x) =x8+x4+x3+x+1

The constants used are based on a linear code with maximal distance between code words

– this gives good mixing of the bytes within each column. Combined with the “shift rows” step provides good avalanche, so that within a few rounds, all output bits depend

on all input bits.

The following figure illustrates the Mix Columns transformation.

In practise, you implement Mix Columns by expressing the transformation on each column as 4 equations (Stallings equation 5.4) to compute the new bytes for that column. This computation only involves shifts, XORs & conditional XORs (for the modulo reduction).

The decryption computation requires the use of the inverse of the matrix, which has larger coefficients, and is thus potentially a little harder & slower to implement.

The designers & the AES standard provide an alternate characterisation of Mix Columns, which treats each column of State to be a four-term polynomial with coefficients in GF(28). Each column is multiplied by a fixed polynomial a(x) given in Stallings eqn 5.7.

MixColumn and InvMixColumn is illustrated in the following figure.

2.5 AddRoundKey

Lastly is the Add Round Key stage which is a simple bitwise XOR of the current block with a portion of the expanded key. Note this is the only step which makes use of the key and obscures the result, hence MUST be used at start and end of each round, since otherwise could undo effect of other steps. But the other steps provide confusion/diffusion/non-linearity. That us you can look at the cipher as a series of XOR with key then scramble/permute block repeated. This is efficient and highly secure it is believed

The above figure illustrates the Add Round Key stage, which like Byte Substitution, operates on each byte of state independently.

2.6 AES Round

Now view all the internal details of the AES round, showing how each byte of the state is manipulated, as shown in figure below.

2.7 AES Key Scheduling

The AES key expansion algorithm takes as input a 4-word (16-byte) key and produces a linear array of words, providing a 4-word round key for the initial AddRoundKey stage and each of the 10/12/14 rounds of the cipher. It involves copying the key into the first group of 4 words, and then constructing subsequent groups of 4 based on the values of the previous & 4th back words. The first word in each group of 4 gets “special treatment” with rotate + S-box + XOR constant on the previous word before XOR’ing the one from 4 back. In the 256-bit key/14 round version, there’s also an extra step on the middle word.

The above table takes 128-bits (16-bytes) key and expands into array of 44 32-bit words

2.8 Key Expansion Scheme

The sub keys are generated according to the above figure.

2.9 Key Expansion submodule

RotWord performs a one byte circular left shift on a word For example:

RotWord[b0,b1,b2,b3] = [b1,b2,b3,b0]

SubWord performs a byte substitution on each byte of input word using the S-box SubWord(RotWord(temp)) is XORed with RCon[j] – the round constant

Round Constant (RCon)

RCON is a word in which the three rightmost bytes are zero. It is different for each round and defined as:

RCon[j] = (RCon[j],0,0,0)

where RCon[1] =1 , RCon[j] = 2 * RCon[j-1]

Multiplication is defined over GF(28) but can be implement in Table Lookup given below.

2.1.0 Key Expansion Example (1st Round)

Example of expansion of a 128-bit cipher key Cipher key

= 2b7e151628aed2a6abf7158809cf4f3c w0=2b7e1516

w1=28aed2a6 w2=abf71588 w3=09cf4f3c

2.1.1 AES Security

AES was designed after DES. Most of the known attacks on DES were already tested on AES. In terms of security, AES is definitely more secure than DES due to the larger-size key. Numerous tests have failed to do statistical analysis of the ciphertext. There are no differential and linear attacks on AES as yet.

2.1.2 Implementation Aspects

AES can also be very efficiently implemented on an 32-bit processor, by rewriting the stage transformation to use 4 table lookups & 4 XOR’s per column of state. These tables can be computed in advance using the formulae shown in the text, and need 4Kb to store.

The developers of Rijndael believe that this compact, efficient implementation was probably one of the most important factors in the selection of Rijndael for AES.

Summary

We have considered:

• The AES selection process
• The details of Rijndael – the AES cipher
• Looked at the steps in each round in AES
• The key expansion in AES
• Implementation aspects of AES