Lecture notes on Computer and network security: Lecture 8 - Avinash Kak

Lecture 8: AES: The Advanced Encryption Standard Lecture Notes on “Computer and Network Security” by Avi Kak (kak@purdue.edu) April 12, 2016 10:41am 2016 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 implementation 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 8 8.3 The Overall Structure of AES 10 8.4 The Four Steps in Each Round of Processing 13 8.5 The Substitution Bytes Step: SubBytes and 17 InvSubBytes 8.5.1 Traditional Explanation of Byte Substitution: 20 Constructing the 16 ×16 Lookup Table 8.5.2 Python and Perl Implementations for the AES 25 Byte Substitution Step 8.6 The Shift Rows Step: ShiftRows and InvShiftRows 29 8.7 The Mix Columns Step: MixColumns and 31 InvMixColumns 8.8 The Key Expansion Algorithm 34 8.8.1 The Algorithmic Steps in Going from one 4-Word 38 Round Key to the Next 4-Word Round Key 8.8.2 Python Implementation of the Key Expansion 44 Algorithm 8.9 Differential, Linear, and Interpolation Attacks on 50 Block Ciphers 8.10 Homework Problems 83 2 Computer and Network Security by Avi Kak Lecture 8 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 iden-tical. • Each round of processing includes one single-byte based substi-tution step, a row-wise permutation step, a column-wise mixing 3 Computer and Network Security by Avi Kak Lecture 8 step, and the addition of the round key. The order in which these four steps are executed is different for encryption and decryption. • To appreciate the processing steps used in a single round, it is best to think of a 128-bit block as consisting of a 4×4 matrix of bytes, arranged as follows:  byte0 byte4  byte1 byte5  byte2 byte6 byte3 byte7 byte8 byte12  byte9 byte13  byte10 byte14  byte11 byte15 • Therefore, the first four bytes of a 128-bit input block occupy the first column in the 4 × 4 matrix of bytes. The next four bytes occupy the second column, and so on. • The 4×4 matrix of bytes shown above is referred to as the state array in AES. [If you are trying to create your own implementa-tion 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: 4 Computer and Network Security by Avi Kak Lecture 8 print statearray print statearray[0] print statearray[2][3] block = range(128) 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): for j in range(4): print statearray[i][j], " ", 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. 5 ... - tailieumienphi.vn