Galois Fields Motivation groups, rings, fields Finite/Galois fields Prime fields Extension Fields, GF(256) AES algorithm in depth Cryptology cryptanalysis cryptography

symmetric stream ciphers LFSR SECURITY asymmetric protocols

block ciphers We are here DES, 3DES, AES Motivation Why bother with Galois fields? Arbitrary application of substitution/transposition (Claudes confusion & diffusion) is not enough.

Even with computers scrambling a lot an insane speeds, we need to understand the resulting probability distributions to ease worry over frequency analysis Motivation Galois fields (GF(256)) provide the mathematical basis for AES so we have a reasonable handle on what its doing We need just enough understanding for AES Math courses in abstract algebra, groups rings and fields, field

theory, etc. can fill out the pictures Groups, Rings, Fields Groups closed set under binary operation associative identity inverse + Groups, Rings, Fields

If a and b are in the group, then a op b = c is also in the group The op is associative: a op (b op c) == (a op b) op c There is an identity element i such that a op i == i op a == a for all a For each element there exists an inverse element a-1 such that a op a-1 == a-1 op a == i Integers under + Add any two, get another integer - closed a + (b + c) = (a + b) + c for all a,b,c - associative Identity = 0; a+0 =

0 + a = a for all a For all a there exists a-1 such that a + a-1 = a -1 + a = 0 (in other words - a + -a, or a-a) Groups, Rings, Fields Rings Add a second binary operation * Not all elements need have an

inverse under op2 Groups, Rings, Fields Group + (-) Ring + (-) * Field + (-), * (/) (two groups) Very informally A closed set of elements where you can add, subtract, multiply & divide

Groups, Rings, Fields Two groups: all elements form an additive group: +, identity = 0 all elements != 0 form a multiplicative group: *, identity = 1 Distributive law holds when you mix operation a * (b + c) = (a * b) + (a * c) Groups, Rings, Fields Real numbers are a field

Complex numbers are a field Integers? Finite/Galois Fields We care about Finite Fields finite fields must have pm elements p a prime m a positive integer

Finite/Galois Fields We write: GF(13) p == 13, m==1 We write: GF (121) or GF(112 ) p == 11, m==2 Finite/Galois Fields GF(2) {0, 1} - a field? (all ops are mod 2) Closed?

Plus, times, identity, inverse, associative? Finite/Galois Fields GF(12) ? GF(11) ? GF(256) ? Finite/Galois Fields GF(256) = GF(28 ) is the Galois field used by AES

Prime Fields If m == 1 we call it a prime field If (m > 1) we call it an extension field GF(pm ) Prime field Extension field GF(p) m == 1

GF(pm ) m>1 Prime Fields Both prime fields and extension fields are of interest in crypto but mostly, and for us, GF(2m) Prime Fields GF(p) = {0, 1, 2, , p-1} since it is finite, we use (mod p) to wrap back around

then +, * as usual: a + b c mod p a * b d mod p Prime Fields {0, 1, 2, 3, 4}, +,identity = 0 Inverse satisfies a + a-1 ? say you have GF(5) {0, 1, 2, 3, 4}

what is the additive inverse of each? Prime Fields GF(5) additive group {0, 1, 2, 3, 4}, +,identity = 0 {0, 1, 2, 3, 4}, +,identity = 0 what is the additive inverse of each? 4 + 1 = 1 + 4 0 mod p 3 + 2 = 2 + 3 0 mod p 2 + 3 = 3 + 2 0 mod p 1 + 4 = 4 + 1 0 mod p 0 ? Whats the general form?

Prime Fields GF(5) additive group: {0, 1, 2, 3, 4}, +,identity = 0 For a, a-1 = (p a) mod p Prime Fields GF(5) multiplicative group: {0, 1, 2, 3, 4}, *,identity = 1 {0, 1, 2, 3, 4}, *,identity = 1 what is the multiplicative inverse of each? 4 * ? = ? * 4 1 mod 5

3*? 2*? 1*? Prime Fields GF(5) multiplicative group: {0, 1, 2, 3, 4}, *,identity = 1 {0, 1, 2, 3, 4}, *,identity = 1 what is the multiplicative inverse of each? 4 * 4 = 16, 16 mod 5 = 1, which is the identity 3 * 2 = 6, 6 mod 5 = 1 2 * 3 = 6,

6 mod 5 = 1 1 * 1 = 1, 1 mod 5 = 1 what about 0? Prime Fields GF(5) multiplicative group: {0, 1, 2, 3, 4}, *,identity = 1 Whats the general form? a * a-1 = a-1 * a 1 mod p Extended Euclidean algorithm

Extension Fields The elements of GF(2m) are polynomials am-1 xm-1 + am-2 xm-2 + + a1x + a0 ai GF(2) Extension Fields GF(23) the polynomials are the 8: a2x2 + a1x + a0

{0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1 } 0 0 0 Extension Fields So how do the binary operations work? a(x) + b(x) = c(x) = ai + bi mod 2 a(x) - b(x) = c(x) = ai- bi ai + bi mod 2

+,- add coefficients term by term ((mod 2) of course) Extension Fields X2+1 X ------------- X2 + X + 1 X2 +1 -----------------------

Q Q ----------- Q GF(23) Extension Fields How does multiplication work? (X2+1) * (X2 + X + 1) X4 + X3 + X2 + X2 + X + 1 = X4 + X3 + 2X2 + X + 1 = X4 + X3 + X + 1

but of course Extension Fields Mod reduction, we want the remainder when divided by when divided by what? In a prime field what = m In an extension field, what = some divisor prime polynomial irreducible polynomial (cant be factored) Extension Fields so c(x) a(x) * b(x) mod p(x)

For GF(23): p(x) = x3 + x + 1 For AES, GF(28): p(x) = x8 + x4 + x3 + x + 1 (youll always have >= 1 p(x)) Extension Fields How does multiplication work? (X2+1) * (X2 + X + 1) X4 + X3 + X2 + X2 + X + 1 = X4 + X3 + 2X2 + X + 1 = X4 + X3 + X + 1

but of course Extension Fields X3+ X + 1 X4 + X3 + X + 1 Extension Fields X3+ X + 1 X4 + X3 + X + 1

r = X2 + X Extension Fields (X2+1)*(X2 + X + 1) = X4 + X3 + X2 + X2 + X + 1 = X4 + X3 + 2X2 + X + 1 = X4 + X3 + X + 1 mod x3 + x 1 = X2 + X Extension Fields

a-1(x) * a(x) 1 mod p(x) AES algorithm Introduction/history How it works AES algorithm history/introduction DES heads downhill Its 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 2000ish - 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 keysused 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 +

L subkeys f R Left/right swap AES algorithm All 128 bits encrypted each round Round 1

Round 2 . . . Round 9 Round 10 subkey 1 subkey 2 . . . subkey 9

subkey 10 AES algorithm Within a round: Roundi has 4 layers a. b. c. d. Byte substitution Shift row

Mix column Key addition Last round has a,b,d AES algorithm Byte substitution Shift row Mix column Key addition Confusion Diffusion

AES algorithm 128 bits/16 bytes Byte substitution A round: Shift Row 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 Im 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 AES

businessPlan encrypted 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 Ive 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 were at it, lets 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 =

For each row turn it sideways multiply and add 1 5 9 1 D0 = 2 6

0 1 1 2 3 4 3 7 1 1 * *

* * 4 8 11 1 C0 C1 * C2 C3

C0 + C1 + C2 + C3 1*C0 + 2*C1 + 3*C2 + 4*C3 D1 = 5 6 7 8

* * * * etc C0 + C1 + C2 + C3

Checklist Galois (X2+1) * (X2 + X + 1) = X4 + X3 + X 2 + X 2 + X + 1 = X4 + X3 + 2X2 + X + 1 = X4 + X3 + X + 1 = X3 + X + 1 X4 + X 3 + X + 1 Checklist Galois 2710 033 338

0x1B 1B16 0001 1011 X +X +X+1 4 3 These are all the same! 4 bytes

A0 B Y S T U E B A1 A2 AES algorithm A3

A4 A5 A6 A7 A8 A9

A10 A11 A12 A13 A14 A15 a set of 16 bytes from the file to be encrypted s b0 b1

b15 S H I R F O T W

Mix column K A E D Y D + Ki,0 Mix column Mix column Mix column

+ Ki,15 AES algorithm Diffusion on the algorithm level Input 1 : 0x0000000000000000 Input 2: 0x8000000000000000 A E S

Output 1 Output 2 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 si

Whats going on here to provide confusion? a, b are bytes all si are the same S(ai) = bi AES algorithm Apply two functions to ai to get bi S1(ai) =

( = ai-1 ) ai B Y S T U E B s bi S2( ) = bi

In other words, first find the inverse under the multiplicative group in GF(28) thats S1 Then apply the affine transformation thats S2 S2 is the affine transform: - wikipedia Inverse 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 b 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 Let input a = 0xb3 = 1011 0011 , look in row b, column 3 to find output b = 0x6d ai GF(28) a = 0xb3 = 1011 0011 = x7 + x5 + x4 + x + 1 a * S2-1 (b) = (x7 + x5 + x4 + x + 1) * S2-1 (b) 1 mod (x8 + x4 + x3 + x + 1) 8 4

3 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: x +x +x +x+1 8 4 3 X10 + X9 + X8 + X6

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 example AES algorithm Let ai = 4016 then bi = 0916 = x3 + 1

(the 09 came from the table) AES algorithm = AES algorithm 0 0 0 1 1 1

0 1 = X4 + X 3 + X 2 + 1 This should be the multiplicative inverse for X6 under GF(28) X6 * (X4 + X3 + X2 + 1) = X10 + X9 + X8 + X6 x +x +x +x+1 8

4 3 X10 + X9 + X8 + X6 4 bytes A0 B Y S T U E B

A1 A2 b1 AES algorithm A3 A4

A5 A6 A7 A8 A9 A10 A11

A12 A13 A14 A15 s b0 b15 S H I R F O

T W Mix column K A E D Y D + Ki,0 Mix column Mix column

Mix column + Ki,15 Shift rows AES algorithm Shifting the bytes around to induce diffusion/transposition Shift rows B0

1 2 AES algorithm 3 b4 5 6

7 b8 B0 c0 B1 c13 B2 c10 C0 1 2

3 c4 5 6 7 Whats the pattern? B9 ? B14

9 10 11 b12 13 14

15 11 c12 13 14 15 B3 c7

B4 c4 B5 c1 c8 9 ? 10 B15 ? AES algorithm - Mix column

Mix column another matrix operation C0 C1 C2 C3 ? D0

D1 D2 D3 AES algorithm - Mix column All are bytes, the constants too D0 D1 D2 D2

= 02 01 01 01 03 02 01 01

01 03 02 01 01 C0 01 C1 * 03 C2 02

C3 The middle matrix is constant 01 = 1 02 = x 03 = x + 1 D0 = 02*C0 + 03*C1 + 01*C2 + 01*C3 Each is a polynomial multiplication under GF(256) Each is a polynomial multiplication under GF(28) Assign some values to c0,c1,c2,c3 for demonstration:

D0 = 02*1F + 03*05 + 01*10 + 01*C0 Q = X * (X4+X3+X2+X+1) //this is 02*1F + (X+1) * (X2+1) //this is 03 * 05 + 1 * X4 //this is 01 * 10 + 1 * (X7+X6) //this is 01 * C0 D0 = Q mod x8 + x4 + x3 + x + 1 AES algorithm All are bytes, including the constants

D0 D1 D2 D2 = 02 01 01 01 03

02 01 01 01 03 02 01 01 C0 01 C1

* 03 C2 02 C3 Note that each Di is now a function of all four Cis this completes our story of diffusion given a single bit The middle matrix is fixed 01 = 1 02 = x

03 = x + 1 AES algorithm Remember that the algorithms for encryption schemes must be public. Somewhat ironically, secrecy is a very bad tool AES algorithm So, all the impressive slicing and dicing is worthless!

The spy has computers too, and inverting it all is not difficult in fact its already programmed and available in the public domain AES algorithm So whats the point and how does it provide protection? AES algorithm AES algorithm

Key addition The Rijndael Key Schedule Expand the original key into a series of keys, one for each round AES algorithm Overall animation, including Epilog Prolog Key generation https://youtu.be/gP4PqVGudtg

Asymmetric encryption (public-private key, public key) Cryptology cryptanalysis cryptography symmetric stream

ciphers LFSR asymmetric protocols We are here block ciphers

DES, 3DES, SECURITY AES Asymmetric encryption Conventional cryptography uses a symmetric key -- Asymmetric encryption Symmetric key cryptography is:

fast useful for encrypting data that is not to be transmitted also used for transmitted data But Whats the but ? Asymmetric encryption Key distribution problem, a catch 22 You need secure communications to be able to have secure communications!

Key distribution is solved by public-private key distribution Keys come in pairs, encrypt with one, decrypt with the other -Diffie, Hellman Asymmetric encryption Asymmetric encryption allows people who have no preexisting security arrangement to exchange messages securely Changed 3000+ years of cryptography Provides strong cryptography to the masses

Asymmetric encryption https://youtube.com/watch?v=YEBfamv-_do&t=127s Asymmetric encryption Symmetric encryption is much faster than public/private key encryption Leading to a hybrid system encrypt with symmetric, use public/private to transmit the key Asymmetric encryption

Asymmetric encryption Generate a public/private key pair: $ openssl genrsa -out private.pem 1024 Extract the public key: $ openssl rsa -in private.pem -out public.pem -outform PEM -pubout Encrypt a file using a public key: openssl rsautl -encrypt -inkey public.pem -pubin -in file.txt -out file.ssl decrypt using the private key:

openssl rsautl -decrypt -inkey private.pem -in file.ssl -out decrypted.txt