Symmetric Key Cryptography

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

Strengths:

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

Weaknesses:

• 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 4×4 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

# XOR each byte of the roundKey with the state table
def addRoundKey(state, roundKey):
    for i in range(len(state)):
        state[i] = state[i] ^ roundKey[i]

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

The AES Cipher operates using a varying number of rounds, based on the size of the cipher key.

• 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

AES key expansion consists of several primitive 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)

Pseudo-code for AES Key Expansion:

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]

Another function to note…

# 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'