Sample Chapter

Chapter 3 ADVANCE ENCRYPTION STANDARD 3.1

The History Advance Encryption Standard was announced by the National Institute of

Standards and Technology (NIST) as a computer security standard, cryptography [19]. It is used to protect electronic data while being a symmetric block cipher that can encrypt a plaintext data into unintelligible form called ciphertext; and then decrypt the ciphertext back to plaintext. The Advanced Encryption Standard (AES) has been selected as the replacement of the Data Encryption Standard (DES) algorithm by the National Institute of Standards (NIST), since Data Encryption Standard (DES) was expired in 1998 [23]. In September 1997 NIST requested proposals for the selection of AES [22].Selection round was the first round, in which five candidates were selected. At the end of second round NIST announce that the five algorithms showed similar characteristics [21]. Rijndael was selected on October 2, 1997 [21] on the basis of security, performance, efficiency, implementability and flexibility1. This standard specifies the Rijndael algorithm [4, 5]. Rijndael can be implemented to compute on variable sizes of blocks as well as keys; i.e. 128,192 or 256. However the NIST specification defines that AES, can process data blocks of 128 bits only using ciphering keys with lengths of 128, 192, and 256 bits [19]. AES may be used with the three different key lengths indicated above, and they are referred as “AES-128”, “AES-192”, and “AES-256” [17]. The functionalities defined in AES are with respect to key generation process, encryption and decryption process. However, in this research counter mode (CTR) is used and it requires only encryption process of AES to encrypt the counters, which can then be used to either encrypt or decrypt the data blocks. Key generation is also done before the encryption process and keys are stored in memory for further use. Therefore the emphasis is only on the encryption process of AES and defines the functionalities used in the encryption process. 1

http://www.nist.gov/public_affairs/releases/g00-176.htm

Chapter 3. Advance Encryption Standard

The elementary operation behind this cipher is astonishingly simple: byte wise substitution, byte exchange, and XOR. If AES is working on 128 bits block then it will use 4x4 matrixes as state and subkey respectively. The 128-bit algorithm executes 10 rounds; for longer keys i.e. 192 and 256 bits size, this number is increased to 12 and 14 rounds, respectively. For simplicity, in this research 128-bit keys and 128-bit data blocks have been chosen2.

3.2

Parameters of AES Encryption

State

State is used to define a data block of 128 bits or 16 hexadecimal values of 1 byte each.

AddRoundKey

It is a XOR operation during each round of computation. The operation is performed between the state and one of the subkeys. Subkey size is equal to the state.

SubBytes

Conversion of data with the help of a lookup table called SBox. The S-Box is predefined and it has 256 fixed values with 1 byte each. However, these values can be computed by composing two transformations mentioned in [12, 13].

ShiftRows

Shifting of rows of the state is performed during this operation.

MixColumns

Matrix multiplication on state by using another predefined 16 hexadecimal values of 1 byte each.

3.3

AES Encryption Process The encryption process of AES can be defined in two steps. Step 1: A 128 bits key is used to generate 10 more keys (128 bits 16 bytes

each) that will be used during the 10 rounds process of AES. The key generation process uses subByte transformation with the help of the same S-Box that will use during the AES encryption process, rotate word, a technique used to rotate the word of 8 bits in the same column and an XOR operation with predefined values in an array called Rcon. This process is also called key expansion. The generated key is 1408 bits in size; that is eleven (11), 128 bits blocks. Step 2: The encryption operation starts with AddRoundKey function, this step is called initial round. Initial round uses the first key (first 128 bits) from the eleven generated keys. The rest of the key blocks (128 bits each) are used during the next 10 subsequent stages. For the next 9 rounds all four functionalities, SubBytes, 2

http://csrc.nist.gov/CryptoToolkit/aes/

19

Chapter 3. Advance Encryption Standard

ShiftRows, MixColumns and AddRoundKey are used. In the final round only SubBytes, ShiftRows and AddRoundKey will be used. AddRoundKey is in fact a form of Vernam cipher and the other three stages SubBytes, ShiftRows and MixColumns provides nonlinearity, confusion, and diffusion [22]. Plaintext

Substitute Bytes

Expand Key

Add round key Inverse sub bytes

Shift Rows

Inverse shift rows

Mix Columns

Inverse mix cols

Add round key

w[4,7]

Add round key

. .

Inverse sub bytes

.

Inverse shift rows

. .

Substitute Bytes

01 dnuo R

9 dnuo R

Shift Rows

.

Mix Columns Add Round Key

Inverse mix cols

w[36,39]

Add round key

Substitute Bytes

Inverse sub bytes

Shift Rows

Inverse shift rows

Add Round Key

01 dnuo R

w[0,3]

9 dnuo R

Add round key

w[40,43]

Add round key

1 dnuo R

1 dnuo R

Plaintext

Ciphertext

Ciphertext

Figure 3.1: Encryption and Decryption process of AES

3.4

Modular Transformations

3.4.1 SubBytes SubBytes transformation is a non-linear byte substitution [19]. A predefined lookup table is used for this operation that is S-Box figure 3.2. Each byte in a state is divided in two nibbles. The first four bits represent the ‘x’ value and the second 4 bits represent the ‘y’ value i.e. if the byte has a value 5b, ‘5’ will be used to select the row and ‘b’ will be used to select the column from the S-Box. So in the case of value ‘5b’, the substitution value will be 39. A substitution of all 16 bytes in a state completes the SubBytes process, in every round.

20

Chapter 3. Advance Encryption Standard

Figure 3.2: S-Box substitution values table

3.4.2 ShiftRows It is a left shift operation in a row. In ShiftRows transformation rows of the state are shifted in a cyclic way. The first row is not shifted, second row is shifted with one byte from right to left, third row is shifted with two bytes and the last row is shifted with three bytes shifted towards left. The bytes are inserted from the right side of the same row i.e. left circular shift figure 3.3.

Figure 3.3: Shift Row transformation

3.4.3 MixColumns The Columns of the state perform MixColumns transformation by multiplying each column of the state with the columns of the predefined block. (Equation 3.1 and 3.2). The first column of the state is multiplied with the first column of the block and the resultant four bytes perform a XOR operation between them to generate a single byte value. Same operation continues for the first column of the state being multiplied by the second, third and fourth column of the predefined block. The first column of

21

Chapter 3. Advance Encryption Standard

the state is now replaced by the generate four bytes through this operation. Same operation will continue for the second, third and fourth column of the state.

02 03  01  01

 s 0' , j  '  s1, j  s 2' , j  '  s3, j

01 02 03 01

01 01 02 03

03  01   01   02 

 s 0,0 s  1, 0  s 2, 0   s 3, 0

s 0,1 s1,1 s 2,1 s3,1

s 0, 2 s1, 2 s 2, 2 s 3, 2

s 0,3  s1,3  = s 2,3   s 3, 3 

 s 0' ,0  '  s1, 0  s 2' , 0  '  s3, 0

s 0' ,1 s1' ,1

s 0' , 2 s1' , 2

s 2' ,1 s3' ,1

s 2' , 2 s3' , 2

= (2 • S 0, j ) ⊕ (3 • S1, j ) ⊕ S 2, j ⊕ S 3, j   = S 0, j ⊕ (2 • S1, j ) ⊕ (3 • S 2, j ) ⊕ S 3, j  = S 0, j ⊕ S1, j ⊕ (2 • S 2, j ) ⊕ (3 • S 3, j )  = (3 • S 0, j ) ⊕ S1, j ⊕ S 2, j ⊕ (2 • S 3, j )

s 0' ,3   s1' ,3  (3.1) s 2' ,3   s3' ,3 

(3.2)

3.4.4 AddRoundKey In this transformation each byte of the state performs a XOR operation with the key. Eleven (11) keys of length 128 bits each (total 1408 bits) are stored in the computational unit. AddRoundKey transformation takes the keys one by one and XOR it with the state of the corresponding round. First 128 bits are used in the initial round then the rest of the 10 keys are used for the next 10 rounds. Keys are generated by the key expansion process in which a 128 bits long key is expended to 1408 bits. In this research, it is assumed that keys are already generated by the key expansion process and stored in memory for the use of AddRoundKey transformation.

3.5

Hardware Dependencies in AES

3.5.1 SubBytes Transformation For hardware implementations of AES encryption process, the SubBytes transformation is the most expensive AES transformations [17]. The SubBytes transformation operates with every byte of the state separately. SubBytes process uses the S-Box for the replacement of the bytes in the state. The S-Box consists of 256 values of 8 bits each. Total memory space used by S-Box is 2048 bits. The hexadecimal values in the state will identify the location of the replacing value from the S-Box. A state has 16 hexadecimal values, so in 10 rounds there will

22

Chapter 3. Advance Encryption Standard

be 160 hexadecimal values. For 160 hexadecimal values the SubBytes operation searches S-Box values 160 times for the replacements. There are two choices available to implement SubBytes transformation. First, all the values of S-Box are put in the memory to create a lookup table. In second choice, the replacing values composing two transformations mentioned in [13, 19] can be calculated. The two transformations are: a) Multiplicative inverse of the value (1 byte) in GF (28). The zero element is mapped to itself. b) Affine transformation which can be expressed in matrix form (equation 3.3)

b0'  1  '   b1  1 b2'  1  '   b3  = 1 b '   1  4'    b5   0 b '  0  6  b7'   0

1  b0   1 1  b1   1 1 b2   0     1  b3   0 ⊕ 0 b4   0     0  b5   1 0  b6   1     0 0 1 1 1 0 1 b7   0

0 1 1 1 1 1 0

0 0 1 1 1 1 1

0 0 0 1 1 1 1

1 0 0 0 1 1 1

1 1 0 0 0 1 1

1 1 1 0 0 0 0

(3.3)

It will save the memory but it will increase the computational load. As the available FPGAs have built-in memory features, so it is considerable to make use of built-in features of FPGA there fore in this research S-Box is stored as lookup table.

3.5.2 Multiplication operation in MixColumns Transformation If a byte of state is going to be multiplied by the value 02, the MSB of the byte is to be checked. If the MSB of the byte is 1, a left shift of one byte is required and then XOR it with hexadecimal value 1b. If the MSB of the byte is 0, only a left shift of one is required. If a byte is going to be multiplied with the value 03, the MSB bit is to be checked. If the MSB bit is 1, the byte has to be shifted left once then an XOR operation between the shifted byte, hexadecimal value 1b and the same byte before shifting is performed. If the MSB of the byte is 0, the byte has to be left shifted once

23

Chapter 3. Advance Encryption Standard

and an XOR operation is performed between it and the same byte before shifting. MixColumns transformation is not included in the final round.

24