CPSC 253 - Lecture 4: Advanced Encryption Standard

Features of AES bit sizes

• Block cipher with a block size of 128 bits.

• Allows for three different key lengths: 128, 192, and 256 bits, can be more.

  • Mostly assume that the key length is 128-bit.

  • For a key length other than 128 bits,the main difference is how the key schedule is generated from the key

  • Key schedule determines handling

How does AES encryption round amounts change based on key size?

• 10 rounds of processing for 128 bit keys

• 12 rounds for 192 bit keys

• 14 rounds for 256 bit keys

• Identical rounds excluding the last round which has a different key, put everything back to 128 buts

Steps in AES processing rounds for encryption

1) 1 single-byte based substitution step(Byte level)

2) Row-wise permutation(Word level permutation)

3) Column wise mixing step(Word level)

4) Addition of a round key(XoR operation, use with input block)

• Order is different for encryption and decryption

• Word: 4 bytes,

Processing steps in 1 round(AES)

• After a 1st block goes through all the rounds, the processing goes block by block, column by column

• 16 bytes * 8 bits = 128 bits

• The 128 bit block is a 4×4 matrix of bytes

• 1st 4 bytes occupy the 1st column and so on

State Array

• 4×4 bytes matrix of bytes/a block

• Input for AES

• Each block is repped by a 4×4 matrix, columns numbered starting at w₀

AES Words

• 4 bytes/32 bits = 1 word

• Each column/row of the state array is a row

• Each processing round takes the inout state array and produces an output state array

• This output is rearranged into a 128-bit output block

Substitution

Confusion: Relationship between key and ciphertext being obscured is the goal

Permutation

Diffusion: Influence of 1 plaintext symbol is spreadover many ciphertext symbols with the goal of hiding statistical properties of the plaintext (original message)

MixColumns/InvMixColumns

• Step 3 in encryption

• Step 4 in decryption

• Mixes up bytes in each column seperately

• Goal is to scramble up 128 bit input block

Expanding the Encryption Key

• If the key size is larger or smaller than 128 bits

• Assuming a 128-bit key, the key is also arranged in the form of a matrix of 4 × 4 bytes. As with the input block, the first word from the key fills the first column of the matrix, and so on.

• The four column words of the key matrix are expanded into a schedule of 44 words. Each round consumes four words from the key schedule.

Decryption Steps

• Inverse shift rows

• Inverse substitute bytes

• Add round key

• Inverse mix columns

SubBytes/InvSubBytes

• 1st step in encryption

• 2nd step in decryption

• Goal is to reduce correlation between input and output bits at byte level

• Bit scrambling ensures substitution can’t be described in simple math function

• 1 single-byte-based substitution (Byte level), byte by byte using a rule that stays the same for all rounds

• 8 bit binary numbers

• Uses a 16×16 lookup table to find a replacement byte for the given one in the input state array(traditional way)

Traditional way

• 16×16 lookup table

• Divide input byte by 2 4-bit patterns to find substitution bytes to get a value between 0-15

• Repped by hex values between 0-F

• 1 value is the row index and the other is the column index for the table

• Always use 4 bit binary numbers

• Results in 256 byte state array/lookup table

Lookup table

• Substitution step(confusion) is done to reduce correlation between input and output bits at the byte level

Construction of a 16×16 lookup table for AES encryption/decryption with Byte Substitution

• Hexadecimal numbers, 4 bits each

• GF(2^8) Unique 8 bit binary numbers based on multiplicative inverse

• For 0×00 there’s no multiplicative inverse, it replaces itself

• Bit scrambling to destroy bit-level correlations in each byte

• The 16×16 table made is called the S-box, same for all bytes in the state array

• Steps that go into this are reversed for the decryption table

  • 1st use reverse of bit scrambling to each byte and then use multiplicative inverse

slide 28

• 0×95: 10010101, inverse is 0×84: 10000100

Bit scrambling for encryption

• 0×00 byte is changed with this, use XoR operation on right column with a column of 0s

• This transformation is applied to each bit b of the byte stored in a lookup table

• c_i is the ith bit of a byte c with hex calue 0×63

  • 4 of the digits represent 6, other rep 3 for the far right column

• Breaks correlation between bits before and after substitution

• Bytes c and d are choosen so the S-box(substituion box) has no fixed points

• A=00001111

• a complement is = 11110000

  • Can lead to weakness in the system

Implementation of AES in python

• statearray = [[0 for x in range(4)] for x in range(4)]

• Thanks to the nature of substitutions and permutations in AES, it can be implemented quickly as software

AES vs. Rijndael cipher

• Rijindael works with any block and key size that’s a multiple of 32 & > 128

  • AES needs a 128 bit block size

• The state array for the different block sizes still has only four rows in the Rijndael cipher.

• However, the number of columns depends on size of the block. For example, when the block size is 192, the Rijndael cipher requires a state array to consist of 4 rows and 6 columns.

How does substitution for AES and DES differ?

• AES uses a substitution-permutation network in a more general sense.

• Each round of processing in AES involves byte-level substitutions followed by word-level permutations.

• Speaking generally, DES also involves substitutions and permutations, except that the permutations are done by dividing the input block into two halves, processing each half separately, and then swapping the two halves.

What is being portrayed in this image?

Four words of the original 128-bit key being expanded into a key schedule consisting of 44 words.

What is this image depicting?

• Overall structure of AES for a 128 bit encryption key

• Goes through 10 rounds

• 4 words

• w0-w3: Input and key block added

• Round 1: Take the 4 w’s and repeat until the end, 44 w’s

AES Pre processing step

• Input state array is XORed w/ the 1st 4 words of the key schedule

• Also happens during decryption except you use the ciphertext state array with the last 4 words of the key schedule

Steps in AES processing rounds for dencryption

1) Inverse shift rows

2) Inverse substitute bytes

3) Add round key

• XOR the output of the previous 2 steps

4) inverse mix columns

What is this figure depicting?

1 round of AES encryption

What is this figure depicting?

1 round of AES decryption

ShiftRows/InvShiftRows

• Aims to scramble the byte order in each 128-bit block for AES

• For encryption this is the 2nd step

• For decryption it’s the 1st

• Affects state array

• 1st row is unshifted

• 2nd is shfited 1 byte to the left

• 3rd is 2 bytes to the left

• 4th is 3 bytes to left

• Array is written column wise

• In decryption, same shifts but to the right

Understanding a lookup table

• For a cell located at (2,7) you place hex 0×27 in that cell

• Replace the next value in each cell with its multiplicative inverse in GF(2^8)

• The byte stored in (9,5) is the multiplicative inverse of 0×95 which is 0×8A

  • IT stores 10001010 implying the MSB(b₇ is 1 and b₀ is 0

Importance of the c byte(value: 0×63)

• For byte substitution to be invertible the byte-to-byte mapping by the 16 × 16 table must be one-to-one.

• For each input byte, there must be a unique output byte. And, each output byte must correspond to only one input byte.

• No input byte should map to itself, would make the cipher weak

• Multiplicative inverses gives unique entries for each input byte(excluding 0×00)

• Without this, the bit scrambling step would also leave the input byte 0x00 unchanged. With the affine mapping shown above, the 0x00 input byte is mapped to 0x63. At the same time, it preserves the one-to-one mapping for all other bytes.

• c₇…..c₀ = 01100011

• Used in encryption

Bit scrambling for decryption

• After transforming each cell:

• d_i is the ith bit of a specially designated byte d with hex value 0×05(d₇ d₆ d₅ d₄ d₃ d₂ d₁d₀ = 00000101)

• Replace the byte in the cell with its GF(2^8) multiplicative inverse

Purpose of c and d bytes

• No fixed points in S-box

• Ex: S_box(a) = a should not be true

• Ex: S_box(a) = ā indicates a fixed point with a bitwise complement, also undesirable