Symmetric Key Cryptography

• Identical keys used to encrypt/decrypt messages
• Can be implemented as block ciphers or stream ciphers

• Speed
• Much less computationally intensive than public-key crypto
• Easy to implement in hardware as well as software

• Key Management
• n users require n(n-1)/2 keys for all to communicate
• secure key distribution is a challenge
• Cannot be used (directly) for authentication or non-repudiation

AES - The Advanced Encryption Standard

• Rijndael algorithm invented by Joan Daemen and Vincent Rijmen and selected as AES winner by NIST in 2001
• AES uses fixed block size of 128-bits and key sizes of 128, 192 or 256 bits (though Rijndael specification allows for variable block and key sizes)
• Most of the calculations in AES are performed within a finite field
• There are a finite number of elements within the field and all operations on those elements result in an element also contained in the field

AES Operations

• AES operates on a 4x4 matrix referred to as the state
• 16 bytes == 128 bits == block size
• All operations in a round of AES are invertible
• AddRoundKey - each byte of the round key is combined with the corresponding byte in the state using XOR
• SubBytes - each byte in the state is replaced with a different byte according to the S-Box lookup table
• ShiftRows - each row in the state table is shifted by a varying number of bytes
• MixColumns - each column in the state table is multiplied with a fixed polynomial

AES Operation - AddRoundKey

• Each byte of the round key is XORed with the corresponding byte in the state table
• Inverse operation is identical since XOR a second time returns the original values

AES Operation - SubBytes

• Each byte of the state table is substituted with the value in the S-Box whose index is the value of the state table byte
• Provides non-linearity (algorithm not equal to the sum of its parts)
• Inverse operation is performed using the inverted S-Box

# do sbox transform on each of the values in the state table def subBytes(state): for i in range(len(state)): state[i] = sbox[state[i]]

# sbox transformations are invertible >>> sbox[237] 85 >>> sboxInv[85] 237 >>> sbox[55] 154 >>> sbox[154] 184 >>> sboxInv[184] 154 >>> sboxInv[154] 55

AES Operation - ShiftRows

• Each row in the state table is shifted left by the number of bytes represented by the row number
• Inverse operation simply shifts each row to the right by the number of bytes as the row number

# returns a copy of the word shifted n bytes (chars) positive # values for n shift bytes left, negative values shift right def rotate(word, n): return word[n:]+word[0:n] # iterate over each "virtual" row in the state table # and shift the bytes to the LEFT by the appropriate # offset def shiftRows(state): for i in range(4): state[i*4:i*4+4] = rotate(state[i*4:i*4+4],i)

AES Operation - MixColumns

• MixColumns is performed by multiplying each column (within the Galois finite field) by the following matrix:

• The inverse operation is performed by multiplying each column by the following inverse matrix:

# Galois Multiplication def galoisMult(a, b): p = 0 hiBitSet = 0 for i in range(8): if b & 1 == 1: p ^= a hiBitSet = a & 0x80 a <<= 1 if hiBitSet == 0x80: a ^= 0x1b b >>= 1 return p % 256 # mixColumn does Galois multiplication on a state column def mixColumn(column): temp = copy(column) column[0] = galoisMult(temp[0],2) ^ galoisMult(temp[3],1) ^ \ galoisMult(temp[2],1) ^ galoisMult(temp[1],3) column[1] = galoisMult(temp[1],2) ^ galoisMult(temp[0],1) ^ \ galoisMult(temp[3],1) ^ galoisMult(temp[2],3) column[2] = galoisMult(temp[2],2) ^ galoisMult(temp[1],1) ^ \ galoisMult(temp[0],1) ^ galoisMult(temp[3],3) column[3] = galoisMult(temp[3],2) ^ galoisMult(temp[2],1) ^ \ galoisMult(temp[1],1) ^ galoisMult(temp[0],3)

AES - Pulling It All Together

• A round of AES consists of the four operations performed in succession: AddRoundKey, SubBytes, ShiftRows, and MixColumns (MixColumns is omitted in the final round)
• 128-bit key → rounds, 192-bit key → 12 rounds, 256-bit key → 14 rounds
• The AES cipher key is expanded according to the Rijndael key schedule and a different part of the expanded key is used for each round of AES
• The expanded key will be of length (block size * num rounds+1)
• 128-bit cipher key expands to 176-byte key
• 192-bit cipher key expands to 208-byte key
• 256-bit cipher key expands to 240-byte key

AES - Key Expansion Operations

1. Rotate - takes a 4-byte word and rotates everything one byte to the left, e.g. rotate([1,2,3,4]) → [2, 3, 4, 1]
2. SubBytes - each byte of a word is substituted with the value in the S-Box whose index is the value of the original byte
3. Rcon - the first byte of a word is XORed with the round constant. Each value of the Rcon table is a member of the Rinjdael finite field.

# takes 4-byte word and iteration number def keyScheduleCore(word, i): # rotate word 1 byte to the left word = rotate(word, 1) newWord = [] # apply sbox substitution on all bytes of word for byte in word: newWord.append(sbox[byte]) # XOR the output of the rcon[i] transformation with the first part of the word newWord[0] = newWord[0]^rcon[i] return newWord

AES - Key Expansion Algorithm (256-bit)

1. expandedKey[0:32] → cipherKey[0:32] # copy first 32 bytes of cipher key to expanded key
2. i → 1 # Rcon iterator
3. temp = byte[4] # 4-byte container for temp storage
4. while size(expandedKey) < 240 temp → last 4 bytes of expandedKey # every 32 bytes apply core schedule to temp if size(expandedKey)%32 == 0 temp = keyScheduleCore(temp, i) i → i + 1 # since 256-bit key -> add an extra sbox transformation to each new byte for j in range(4): temp[j] = sbox[temp[j]] # XOR temp with the 4-byte block 32 bytes before the end of the current expanded key. # These 4 bytes become the next bytes in the expanded key expandedKey.append( temp XOR expandedKey[size(expandedKey)-32:size(expandedKey)-28]

# returns a 16-byte round key based on an expanded key and round number def createRoundKey(expandedKey, n): return expandedKey[(n*16):(n*16+16)]

AES - Encrypting a Single Block

1. state → block of plaintext # 16 bytes of plaintext are copied into the state
2. expandedKey = expandKey(cipherKey) # create 240-bytes of key material to be used as round keys
3. roundNum → 0 # counter for which round number we are in
4. roundKey → createRoundKey(expandedKey, roundNum)
5. addRoundKey(state, roundKey) # each byte of state is XORed with the present roundKey
6. while roundNum < 14 # 14 rounds in AES-256 roundKey → createRoundKey(expandedKey, roundNum) # round of AES consists of 1. subBytes, 2. shiftRows, 3. mixColumns, and 4. addRoundKey aesRound(state, roundKey) roundNum → roundNum + 1
7. # for the last round leave out the mixColumns operation roundKey = createRoundKey(expandedKey, roundNum) subBytes(state) shiftRows(state) addRoundKey(state)
8. return state as block of ciphertext

AES - Encrypting a Single Block (Demo)

>>> key = passwordToKey("s0m3_p@ssw0rD") >>> key [62, 142, 78, 2, 164, 231, 18, 196, 148, 177, 82, 186, 240, 44, 136, 242, 23, 13, 20, 169, 248, 69, 163, 79, 13, 155, 97, 200, 241, 15, 76, 15] >>> plaintext = textToBlock("Hiro Protagonist") >>> plaintext [72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116] >>> blockToText(plaintext) 'Hiro Protagonist' >>> ciphertext = aesEncrypt(plaintext, key) *** aesMain *** initial state: [72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116] state after adding roundKey0: [118, 231, 60, 109, 132, 183, 96, 171, 224, 208, 53, 213, 158, 69, 251, 134] *** AES Round1 *** state after subBytes: [56, 148, 235, 60, 95, 169, 208, 98, 225, 112, 150, 3, 11, 110, 15, 68] state after shiftRows: [56, 148, 235, 60, 169, 208, 98, 95, 150, 3, 225, 112, 68, 11, 110, 15] state after mixColumns: [66, 80, 228, 230, 148, 33, 121, 29, 106, 95, 226, 146, 255, 98, 121, 117] state after addRoundKey: [85, 93, 240, 79, 108, 100, 218, 82, 103, 196, 131, 90, 14, 109, 53, 122] <-- SNIP --> *** AES Round 14 (final) *** state after subBytes: [0, 229, 171, 70, 93, 137, 135, 251, 99, 182, 88, 166, 228, 229, 251, 97] state after shiftRows: [0, 229, 171, 70, 137, 135, 251, 93, 88, 166, 99, 182, 97, 228, 229, 251] state after addRoundKey: [195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142] >>> ciphertext [195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142] >>> blockToText(ciphertext) '\xc3{\xcd\xb7\xd5\xca2\xdf\xdf\xa4cV~"k\x8e' >>> cleartext = aesDecrypt(ciphertext, key) *** aesMainInv *** initial state: [195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142] *** AES Round 14 *** state after addRoundKey: [0, 229, 171, 70, 137, 135, 251, 93, 88, 166, 99, 182, 97, 228, 229, 251] state after shiftRowsInv: [0, 229, 171, 70, 93, 137, 135, 251, 99, 182, 88, 166, 228, 229, 251, 97] state after subBytesInv: [82, 42, 14, 152, 141, 242, 234, 99, 0, 121, 94, 197, 174, 42, 99, 216] <-- SNIP --> *** AES Round 0 (final) *** state after adding roundKey0: [72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116] >>> cleartext [72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116] >>> blockToText(cleartext) 'Hiro Protagonist'