Advanced Encrpytion Standard

most widely used symmetric cipher today

---

• Overview
• Internal Structure
  • Byte Substitution
    • Math Basis
  • Diffusion
    • Shift Rows
    • Mix Columns
  • Key Addition
  • Key Schedule
• Decryption
• Modes of Operation
  • Electronic Codebook
  • Cipher Block Chaining
  • Output Feedback
  • Cipher Feedback
  • Counter

---

Overview

• Rjindael Cipher
• block length 128 bits
• key can be 128, 192, or 256 bits long
• number of rounds depend on key length (10-14)

flowchart LR
	P[PLAINTEXT]
	A[Key Addition]
	B[S-Box]
	C["Diffusion (shiftrows/mixcolumns)"]
	D[CIPHERTEXT]
	
	P --> A --> B --> C
	B --> D
	C --> A

• $8\times 8$ S-box
• byte wise permutation Shift rows
• mix columns
• key addition

Internal Structure

imagine state as 16 byte 4x4 matrix

$$\left(\begin{array}{cccc}{A}_0& A_4& A_8& A_{12}\\ A_1& A_5& A_9& A_{13}\\ A_2& A_6& A_{10}& A_{14}\\ A_3& A_7& A_{11}& A_{15}\end{array}\right)$$

Byte Substitution Layer

$$S(A_i)=B_i$$

only non-linear element. bijective mapping.

• No fixed points $S(A_i)\ne A_i$
• No opposite fixed points $S(A_i)\oplus A_i\ne FF$

Mathematical Basis:

flowchart LR

	A[A]
	B[B]
	C["GF(2) Inverse"]
	D[affine map]
	
	A --> C --> D --> B

• the affine map involves a constant bitmatrix multiplication followed by the addition of a constant 8-bit vector on the result of the $GF(2)$ inverse (Math Basics)

Diffusion Layer

Shift Rows

$$\left(\begin{array}{cccc}{A}_0& A_4& A_8& A_{12}\\ A_1& A_5& A_9& A_{13}\\ A_2& A_6& A_{10}& A_{14}\\ A_3& A_7& A_{11}& A_{15}\end{array}\right)\to \left(\begin{array}{cccc}{B}_0& B_4& B_8& B_{12}\\ B_5& B_9& B_{13}& B_1\\ B_{10}& B_{14}& B_2& B_6\\ B_{15}& B_3& B_7& B_{11}\end{array}\right)$$

• first row ← no shift
• second row ← one left shift
• third row ← two left shift
• fourth row ← three left shift

Mix Columns

new columns formed by multiplying each column with a constant matrix

$$\left(\begin{array}{c}{C}_0\\ C_1\\ C_2\\ C_3\end{array}\right)=\left(\begin{array}{cccc}2& 3& 1& 1\\ 1& 2& 3& 1\\ 1& 1& 2& 3\\ 3& 1& 1& 2\end{array}\right)\cdot \left(\begin{array}{c}{B}_0\\ B_5\\ B_{10}\\ B_{15}\end{array}\right)$$

TIP

after only 3 rounds every byte of the state matrix depends on all 16 plaintext byes

this matrix multiplication takes place in the $GF(2)$ field.

• Additions are just XOR
• multiplication is also in $GF(2)$ as shown in Math Basics
• the constants 0x01, 0x02, 0x03 were chosen specifically because the software implementation of this multiplication is easy
  • multiplication by 0x01 is just the identity
  • multiplication by 0x02 is just a left shift (into $x$) followed by reduction with the AES polynomial
  • multiplication by 0x03 is a left shift added to the original polynomial followed by the modular reduction
  • 0x02 and 0x03 are usually implemented with lookup tables though

Key Addition

simple XOR with round key

Key Schedule

1. precomputation:
2. on-the-fly:

Decryption

Modes of Operation

for messages with more than block size number of bits OR for construction of stream ciphers

flowchart TB
	A[modes]
	B[deterministic]
	C[probabilistic]
	D[Block Cipher]
	E[Stream Cipher]
	F[ECB]
	G[CBC]
	H[OFB]
	I[CFB]
	J[Counter]
	
	A --> B --> F
	A --> C --> D
		  C --> E
	            D --> G
	            E --> H
	            E --> I
	            E --> J

1. Electronic Codebook

• deterministic: same plaintext always same ciphertext for given key
• very very very very insecure never use
• (most straightforward application, just AES on each received block)

2. Cipher Block Chaining Mode

• probabilistic: same message encrypted at different times have different ciphertexts
• uses an initialization vector (IV)
• ciphertexts chained together

$$\begin{array}{rl}{y}_1& =E_k(\text{IV}\oplus x_1)\\ y_2& =E_k(y_1\oplus x_2)\\ & =\dots \end{array}$$

3. Output Feedback Mode

• random key stream (continuous keys)
• initial IV
• these two will essentially keep generating random numbers of block size
• that output is added to the IV and used in the next encryption
• and the output is xored with the message stream to encrypt the message

4. Cipher Feedback Mode

• same thing as above but the encrypted message is used as IV in the next encryption instead

5. Counter Mode

• instead of passing encrypted message/output into new IV, just maintain a counter
• eg 96 bit IV + 32 bit counter