Insights into the AES Algorithm: Introduction, History, and Functionality

AES algorithm Introduction/history How it works

AES algorithm history/introduction DES heads downhill It s still around, often as triple DES 3DES is still considered secure investment in implementation can pay back a little longer But DES is yesterday, AES is today

AES algorithm history/introduction 1997 call for submissions 1998 - 15 entries including IBM and some of the big names in crypto 1999 5 finalists 2000 ish - Rijndael (rine dale) wins, becomes AES two young, lesser known, Belgian guys beat them all Joan Daemen, Vincent Rijmen

AES algorithm Most widely used algorithm Public and transparent (unlike DES origins) Symmetric key block cipher NSA uses it with longer keys used to be all proprietary

AES algorithm 128 bit key (default), but also 192, 256 Longer keys require more rounds Byte oriented Key length (in bits) number of rounds 128 10 192 12 256 14

DES algorithm DES structure, (and others) L R per round Feistel network subkeys f Left/right swap + L R

AES algorithm All 128 bits encrypted each round Round 1 subkey 1 Round 2 . . . Round 9 subkey 2 . . . subkey 9 Round 10 subkey 10

AES algorithm Within a round: Roundi has 4 layers a. Byte substitution b. Shift row c. Mix column d. Key addition Last round has a,b,d

AES algorithm Byte substitution Confusion Shift row Diffusion Mix column Key addition

AES algorithm 128 bits/16 bytes Byte substitution Shift Row A round: Mix Column Key Addition

AES algorithm Checklist, stuff to know/remember: What are we doing? Matrix multiplication Galois Field polynomial multiplication

Checklist what are we doing again? Say I have a great new business plan I m going to change the world! Here it is:

Checklist what are we doing again? Since we are computer scientists, here it is again from our viewpoint:

Checklist what are we doing again? I need to keep a soft copy of it, but since it is so important I decide to encrypt it with AES so nobody else can read it businessPlan readable businessPlan encrypted AES

Checklist what are we doing again? Remember that this business plan is a thing every thing is a file therefore this is a file a file is a stream of bytes a byte is 8 bits and can represent a number from 0-255 therefore this business plan is a list of numbers from 0 - 255

Checklist what are we doing again? So I ve got a big list of numbers from 0-255 And I want to turn it into a different big list of numbers from 0-255 The first list is easily readable by using tables of what the numbers mean (think ASCII chart) The second list just looks like a random (mathematically speaking) set of numbers

Checklist what are we doing again? Here are the first 64 bytes of the unencrypted business plan (in hex, 16 per line): AES works 16 bytes at a time, turning one set of these numbers into a different set

Checklist what are we doing again?

Checklist what are we doing again? Here are the first 64 bytes of the encrypted business plan (in hex, 16 per line): And the unencrypted one again for comparison:

Checklist matrix multiplication We keep writing polynomials: X7+ X3+ X + 1, X3 + X2 If we always use all the terms: 1X7 + 0X6 + 0X5 + 0X4 + 1X3 + 0X2 + 1X + 1 0X7 + 0X6 + 0X5 + 0X4 + 1X3 + 1X2 + 0X + 0 The position tells you the power, And writing the X over and over feels a bit pointless and redundant

Checklist matrix multiplication 1X7 + 0X6 + 0X5 + 0X4 + 1X3 + 0X2 + 1X + 1 0X7 + 0X6 + 0X5 + 0X4 + 1X3 + 1X2 + 0X + 0 While we re at it, let s skip the plus signs as well, and just write: 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0

Checklist matrix multiplication? D0 D1 D2 D2 1 2 3 4 5 6 7 8 9 0 1 11 1 1 1 1 C0 C1 C2 C3 = * 5 * C0 + 6 * C1 + 7 * C2 + 8 * C3 For each row turn it sideways multiply and add 1 * C0 + 2 * C1 + 3 * C2 + 4 * C3 D0 = D1 = etc 1*C0 + 2*C1 + 3*C2 + 4*C3

Checklist Galois (X2+1) * (X2 + X + 1) = X4 + X3 + X2 + X2 + X + 1 = X4 + X3 + 2X2 + X + 1 = X4 + X3 + X + 1 = X3 + X + 1 X4 + X3 + X + 1

Checklist Galois 2710 033 338 X4 + X3 + X + 1 These are all the same! 0x1B 1B16 0001 1011

Checklist Galois A (ASCII) 1018 These are all the same! X6 + 1 0x41 4116 6510 0100 0001 0101

4 bytes AES algorithm A10 A11 A12 A13 A14 A15 A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 a set of 16 bytes from the file to be encrypted B Y S T U E B s b15 b0 b1 S H I R F O T W Mix column Mix column Mix column Mix column + Ki,15 K A E D Y D + Ki,0

AES algorithm Diffusion on the algorithm level Input 1 : Output 1 A E S 0x0000000000000000 Input 2: Output 2 0x8000000000000000 Worst case: output 2 is different in one bit from output 1 We want output1 and output 2 to look completely uncorrelated

AES algorithm Byte substitution What s going on here to provide confusion? si a, b are bytes all 16 of the si functions are the same S(ai) = bi

AES algorithm ai let ai be a cleartext byte let bi be the ciphertext byte to which you will change it B Y S T U E B s apply two functions, s1 and s2, to ai to get bi bi ( = ai-1 ) s1(ai) = In other words, first find the inverse under the multiplicative group in GF(28) that s s1 Then apply the affine transformation that s s2 s2( ) = bi

s1 is the multiplicative inverse under GF(256) e.g. say the cleartext byte is a dollar sign, find the hex ASCII value:

The dollar sign $ is: 0x24 in hex, which is 0010 0100 in binary, which is the polynomial: x5 + x2 so for the first function, s1, find the multiplicative inverse, i.e. find a polynomial in gf(256) such that, when I multiply it by x5 + x2, then divide the product by x8 + x4 + x3 + x + 1, you get a remainder of 1 (which is the multiplicative identity) --that is the definition of multiplicative inverse--

0 0 1 0 So, now we have a different polynomial, here it is: s2 is the affine transform: 0 1 0 0 this is x5 + x2 ai B Y S T U E B s you multiply this fixed matrix (always the same) by the multiplicative inverse polynomial, exclusive-or it with this other fixed matrix, to get the new polynomial bi bi

Inverse affine transform this undoes the affine transform

AES algorithm consider the input byte expressed in hex the two nibbles provides the x and y coordinates for the table lookup Let a = 0xb3 = (x,y) = 1011 0011 x = row b = 0x6d = 0110 1101 y = column Replace it with the byte value found in row b, column 3 of the AES substitution table

AES substitution table (multiplicative inverses + affine)

Yellow = input byte = ai Corresponding white = output byte = bi input byte value ai S1 (find * inverse) S2 (affine transform) output byte value bi

input byte value ai S1 (find * inverse) S2 (affine transform) output byte value bi So to check one, take a number in white, apply the inverse affine transform that should give us the multiplicative inverse if we multiple an element and its inverse we should get 1 mod p(x)

AES algorithm Consider a = 0x20, b = 0xb7 (the entry at row 2, column 0) Apply the inverse affine transform to 0xb7 to get 0x3a 0x3a = X5 + X4 + X3 + X So: X5 * (X5 + X4 + X3 + X ) = X10 + X9 + X8 + X6 Which should = 1 mod p(x) where p(x) = x8 + x4 + x3 + x + 1

AES algorithm In other words, we should get a remainder of 1 when we: X10 + X9 + X8 + X6 x8 + x4 + x3 + x + 1

AES algorithm Perhaps surprisingly, table lookup is not necessarily the way to go for hardware implementations: http://www.design-reuse.com/articles/30375/pipeline-aes-s-box-implementation-starting-with-substitution-table.html

AES algorithm example Let ai = 4016 then bi = 0916 = x3 + 1 Inverse affine transform (the 09 came from the table)

40 maps to 09 according to the table Inverse affine maps 09 to ? 40 ? 09 Affine transform Multiplicative inverse

AES algorithm Apply inverse affine transform to 09: =

turn this sideways x7 + x6 + x5 + x4 + x3 + x2 + x1 + x0 0 0 0 0 1 0 0 1 which is x3 + 1 hence it s: 0x7 + 0 x6 + 0x5 + 0 x4 + 1x3 + 0x2 + 0x1 + 1x0

this matrix is also fixed xor the two as the final step this matrix is fixed, it s always exactly this one multiply it by x3 + 1 to get 0 0 0 1 1 0 0 0

AES algorithm 0 0 0 1 1 1 0 1 = X4 + X3 + X2 + 1 so this is the multiplicative inverse for the tab character (0x09, X3 + 1) This should be the multiplicative inverse for X6 under GF(28) do the division, did you get a remainder of 1? X6 * (X4 + X3 + X2 + 1) = X10 + X9 + X8 + X6 if so, it is the multiplicative inverse if not, you made a mistake X10 + X9 + X8 + X6 x8 + x4 + x3 + x + 1

so, in summary, how are the table entries calculated? use the same algorithm for all 256 possibilities e.g say we want to find what @ becomes during substitution 1) look up @ in the ASCII chart, learn that it has the value 64 (in base 10) 64 = 0x40 = 0100 0000 = X6 2) find the multiplicative inverse of X6 it is: X4 + X3 + X2 + 1 3) apply the affine transform to: X4 + X3 + X2 + 1 you get: X3 + 1 (which is a tab character) 4) therefor, the at sign @ changes to a tab character control i in the S box (AES byte sub table)

do this for the other 255 1) look up character in the ASCII chart, write it as a polynomial 2) find the multiplicative inverse of that polynomial 3) apply the affine transform to the multiplicative inverse 4) write that polynomial as a byte, enter that into the AES byte sub table

this step: 2) find the multiplicative inverse of that polynomial is hard to do, so we can t easily fill the table. That s ok though, as it is already filled for us, and it s not going to change. What we can do however, is prove that the entries which are there, are correct.