Lecture 8: AES: The Advanced Encryption Standard Lecture ...

Lecture 8: AES: The Advanced Encryption Standard

Lecture Notes on "Computer and Network Security"

by Avi Kak (kak@purdue.edu)

February 7, 2024

11:11pm

?2024 Avinash Kak, Purdue University

Goals: ? To review the overall structure of AES and to focus particularly on the four steps used in each round of AES: (1) byte substitution, (2) shift rows, (3) mix columns, and (4) add round key. ? Python and Perl implementations for creating the lookup tables for the byte substitution steps in encryption and decryption. ? Python and Perl implementations of the Key Expansion Algorithms for the 128 bit, 192 bit, and 256 bit AES. ? Perl implementations for creating histograms of the differentials and for constructing linear approximation tables in attacks on block ciphers.

CONTENTS

Section Title

Page

8.1

Salient Features of AES

3

8.2

The Encryption Key and Its Expansion

10

8.3

The Overall Structure of AES

12

8.4

The Four Steps in Each Round of Processing

15

8.5

The Substitution Bytes Step: SubBytes and

19

InvSubBytes

8.5.1

Traditional Explanation of Byte Substitution:

22

Constructing the 16 ? 16 Lookup Table

8.5.2

Python and Perl Implementations for the AES 27 Byte Substitution Step

8.6

The Shift Rows Step: ShiftRows and InvShiftRows 32

8.7

The Mix Columns Step: MixColumns and

34

InvMixColumns

8.8

The Key Expansion Algorithm

37

8.8.1

The Algorithmic Steps in Going from one 4-Word

41

Round Key to the Next 4-Word Round Key

8.8.2

Python and Perl Implementations of the Key

46

Expansion Algorithm

8.9

Differential, Linear, and Interpolation Attacks on

57

Block Ciphers

8.10

Homework Problems

91

2

Computer and Network Security by Avi Kak

Lecture 8

Back to TOC

8.1 SALIENT FEATURES OF AES

? AES is a block cipher with a block length of 128 bits.

? AES allows for three different key lengths: 128, 192, or 256 bits. Most of our discussion will assume that the key length is 128 bits. [With regard to using a key length other than 128 bits,

the main thing that changes in AES is how you generate the key schedule from the key -- an issue I address at the end of Section 8.8.1. The notion of key schedule in AES is explained

in Sections 8.2 and 8.8.]

? Encryption consists of 10 rounds of processing for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys.

? Except for the last round in each case, all other rounds are identical.

? Each round of processing includes one single-byte based substitution step, a row-wise permutation step, a column-wise mixing step, and the addition of the round key. The order in

which these four steps are executed is different for encryption and decryption.

3

Computer and Network Security by Avi Kak

Lecture 8

? To appreciate the use of "row" and "column" in the previous bullet, you need to think of the input 128-bit block as consisting of a 4 ? 4 array of bytes, arranged as follows:

byte0 byte4 byte8 byte12

byte1

byte5

byte9

byte13

byte2

byte6

byte10

byte14

byte3 byte7 byte11 byte15

? Notice that the first four bytes of a 128-bit input block occupy the first column in the 4 ? 4 array of bytes. The next four bytes occupy the second column, and so on.

? The 4 ? 4 array of bytes shown above is referred to as the state array in AES. If you are trying to create your own implementation of AES in Python, you will find following statement, which uses the notion of list comprehension in Python, very useful for creating an initialized structure that looks like the state array of AES:

statearray = [[0 for x in range(4)] for x in range(4)]

Next, try the following calls in relation to the structure thus created:

import sys statearray = [[0 for x in range(4)] for x in range(4)] print(statearray)

4

Computer and Network Security by Avi Kak

Lecture 8

print(statearray[0]) print(statearray[2][3])

block = list(range(128)) print("\n\nblock: ", block) for i in range(4):

for j in range(4): statearray[j][i] = block[32*i + 8*j:32*i + 8*(j+1)]

for i in range(4): sys.stdout.write("\n\n") for j in range(4): sys.stdout.write( str(statearray[i][j]) ) sys.stdout.write("\t")

sys.stdout.write("\n\n")

This is a nice warm-up exercise before you start implementing AES in Python.

? AES also has the notion of a word. A word consists of four bytes, that is 32 bits. Therefore, each column of the state array is a word, as is each row.

? Each round of processing works on the input state array and produces an output state array.

? The output state array produced by the last round is rearranged into a 128-bit output block.

? Unlike DES, the decryption algorithm differs substantially from the encryption algorithm. Although, overall, very similar steps

5

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download