What Protects Your Privacy Like No Other Method? … AES

In this article we will look at the basic stages of AES encryption.

What Protects Your Privacy Like No Other Method? … AES

In this article we will look at the basic stages of AES encryption.

Data blocks

With AES we have blocks of 16 bytes (128 bits) and with key sizes of 16, 24, 32 bytes. We go through a number of processes and where we operate on 16 bytes as an input and output. Each block, known as a state, is operated on as a 4x4 matrix, such as:

01 02 03 04
05 06 06 07
08 09 0A 0B
0C 0D 0E 0F

For different key sizes we go through a number of rounds (N):

  • 128-bit (16 bytes) key -> N=10 rounds
  • 192-bit (24 bytes) key -> N=12 rounds
  • 256-bit (32 bytes) key -> N=14 rounds

Figure 1 outlines the process for 128-bit encryption, and where we have 10 rounds. For a 128-bit key it is expanded to 44 words with 33 bits each, and where each round uses four words (128 bits) as an input for each round. With Round 0, the initial transformation consists of add round key. The following rounds (apart from the final round) consists of:

  • Substitute Bytes.
  • Shift Row.
  • Mix Column.
  • Add round key.

and final round consists of:

  • Substitute Bytes.
  • Shift Row.
  • Add round key.
Figure 1

S-box and Inverse S-box

Within the process, transforms the inputs to a new value as an output each state into a new value using an S-box table (such as Table 1). In this case the S-Box table is 16x16 matrix which takes each input value, and where the first four bits is used to define row of the table, and the next four bits defines the column (Figure 2). For example if the input byte is CF, then the output will be 8A. The inverse S-box does the reverse of the S-box process, so the DF maps back to CF (Figure 3).

Figure 2
Figure 3

The following is some sample Python code which implements the S-box and the Inverse S-box:

sbox = [
        0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
        0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
        0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
        0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
        0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
        0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
        0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
        0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
        0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
        0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
        0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
        0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
        0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
        0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
        0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
        0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
]
sboxInv = [
        0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
        0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
        0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
        0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
        0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
        0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
        0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
        0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
        0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
        0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
        0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
        0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
        0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
        0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
        0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
        0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d
]
def subBytes(state):
    for i in range(len(state)):
state[i] = sbox[state[i]]
def subBytesInv(state):
    for i in range(len(state)):
		state[i] = sboxInv[state[i]]
state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
subBytes(state)
print state
subBytesInv(state)
print state

If we run we some sample data, we can see we get the original data back when we implement the inverse S-box:

Output from S-box: [124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 215, 171, 118, 202]
Inverse S-box: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Shift Row Transformation

With this process, the following transformation is applied:

  1. First row remains unchanged.
  2. Second row has a one-byte circular left shift.
  3. Third row has a two-byte circular left shift.
  4. Fourth row has a three-byte circular left shift.

For example:

54 33 AB C1  54 33 AB C1
32 15 8D BB  15 8D BB 32
5A 73 D5 52->D5 52 5A 73
31 91 CC 98  98 31 91 CC

For the reverse process, a right shift will be used. Sample code of the shift is:

def rotate(word, n):
	return word[n:]+word[0:n]
def shiftRows(state):
    for i in range(4):
        state[i*4:i*4+4] = rotate(state[i*4:i*4+4],i)
def shiftRowsInv(state):
    for i in range(4):
	state[i*4:i*4+4] = rotate(state[i*4:i*4+4],-i)
state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
shiftRows(state)
print state
shiftRowsInv(state)
print state

A sample run gives:

[1, 2, 3, 4, 6, 7, 8, 5, 11, 12, 9, 10, 16, 13, 14, 15]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Within this transformation, each column is taken one at a time and each byte within the column is transformed to a new value based on all four bytes in the column. For each column (a0, a1, a2 and a3) we have (where we use Galois Multiplication):

The inverse is given by:

The Python code for the mix column transformation for a single column is:

from copy import copy
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

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)
def mixColumnInv(column):
    temp = copy(column)
    column[0] = galoisMult(temp[0],14) ^ galoisMult(temp[3],9) ^ \
                galoisMult(temp[2],13) ^ galoisMult(temp[1],11)
    column[1] = galoisMult(temp[1],14) ^ galoisMult(temp[0],9) ^ \
                galoisMult(temp[3],13) ^ galoisMult(temp[2],11)
    column[2] = galoisMult(temp[2],14) ^ galoisMult(temp[1],9) ^ \
                galoisMult(temp[0],13) ^ galoisMult(temp[3],11)
    column[3] = galoisMult(temp[3],14) ^ galoisMult(temp[2],9) ^ \
		    galoisMult(temp[1],13) ^ galoisMult(temp[0],11)
g = [1,2,3,4]
mixColumn(g)
print 'Mixed: ',g
mixColumnInv(g)
print 'Inverse mixed', g

The result gives:

Mixed: [3, 4, 9, 10]
Inverse mixed: [1, 2, 3, 4]

Add round key transformation

With this transformation, we implement an XOR operation between the round key and the input bits. A Python method to implement this is:

def addRoundKey(state, roundKey):
    for i in range(len(state)):
	state[i] = state[i] ^ roundKey[i]
state=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
roundkey=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,1]
addRoundKey(state,roundkey)
print state
addRoundKey(state,roundkey)
print state

A sample run does:

[3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 17]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Conclusion

So there you go. AES protects your privacy like few other things.