<style>
p {
display: inline;
}

.orange {
color: rgb(255, 153, 51);
font-weight: bold;
}

.lightblue {
color: rgb(0, 112, 192);
font-weight: bold;
}

.lightgreen {
color: rgb(0, 176, 80);
font-weight: bold;
}

.purple {
color: rgb(154, 51, 255);
font-weight: bold;
}
</style>

# Advanced Encryption Standard

## Introduction

- Object: **replace DES**
- AES Candidate Requirements: a **block cipher** standard
- <font class="lightblue">128-bit block</font>
- <font class="lightblue">128-bit, 192-bit, 256-bit key (at least)</font>

## Mathematical Preliminaries

- The arithmetic operations of AES are performed over the finite field <p class="orange">$GF(2^8)$</p>
- polynomial with coefficient <p class="lightblue">modulo 2</p>
- modulo an <p class="lightgreen">irreducible poly of degree 8</p>
- $GF(2^8)$ contains 2^8^ (= 256) elements
- Polynomial form: $\Box x^7 + \Box x^6 + \Box x^5 + \Box x^4 + \Box x^3 + \Box x^2 + \Box x + \Box 1$
- Example:
- <font class="lightblue">polynomial</font> notation: $x^6 + x^4 + x^2 + x + 1$
- <font class="lightgreen">binary</font> notation: "01010111"
- <font class="orange">hexadeciaml</font> notation: 57
### Basic Operation in GF(2^8^)

- Addition: sum of coefficients modulo 2
- (x^6^ + x^4^ + x^2^ + x + 1) + (x^7^ + x + 1) = x^7^ + x^6^ + x^4^ + x^2^ (<font class="lightblue">polynomial</font>)
- "0101 0111" $\oplus$ "1000 0011" = "1101 0100" (<font class="lightgreen">binary</font>)
- '57' $\oplus$ '83' = 'D4' (<font class="orange">hexadeciaml</font>)
- Multiplication: multiplication of polynomial modulo <p class="purple">$m(x)$</p>
- Irreducible polynomial <font class="purple">$m(x) = x^8 + x^4 + x^3 + x + 1$</font> (“100011011”)

### Polynomials with Coefficients in $GF(2^8)$


## Specification

- <font class="lightblue">Block size: 128 bits</font>
- Note: block sizes of original Rijndael: 128, 192, 256 bits
- <font class="lightgreen">Key length: 128, 192, 256 bits</font>
- AES-128, AES-192, AES-256
- <font class="orange">Number of Rounds: 10, 12, 14</font>
- Key-Block-Round Combinations
- ==**1 word = 4 bytes in AES**==
- <font class="lightgreen">$Nk$: length of the key (words)</font>
- <font class="lightblue">$Nb$: size of the block (words)</font>
- <font class="orange">$Nr$: number of rounds</font>
- Cipher/ InvCipher: encryption/decryption

- General Data Structure
- Key 的部分，若 $Nk$ 等於 6 或 8，row 依然是 4 列，但 column 會變成 6 或 8 行。
- Encryption Process

- Parameters

## Cipher

- The rounds in Cipher() include the following **4 transformations** on the **state**:
- **SubBytes**(State)
- applies a substitution table (S-box) to each byte.
- **ShiftRows**(State)
- shifts rows of the state array by different offsets.
- **MixColumns**(State)
- mixes the data within each column of the state array.
- **AddRoundKey**(State, RoundKey)
- combines a round key with the state.
- Cipher($in, Nr, w$)
- $in$: input plaintext block
- $w$: expandedkey $\equiv$ key schedule
- Block Diagram for Cipher and InvCipher (Encryption and Decryption)
- Round Structure

## SubBytes Transformation

### SubBytes(State)

- an **invertible**, **non-linear** transformation of the state in which a substitution table, called an S-box, is applied independently to **each byte** in the State.
- Affine transformation for each Byte

### S-Box: Table of SubBytes(State)


- Example

### IS-Box (Inverse S-Box)


## ShiftRows Transformation

### ShiftRows(State)

A transformation of the state in which the bytes in **the last three rows** of the state are **cyclically shifted**.


Example:


### InvShiftRows(State)


Example:


## MixColumns Transformation

### MixColumns(State)

- a transformation of the state that multiplies **each of the four columns** of the state by a **single fixed matrix**
- each column of the State is considered as a polynomial over $GF(2^8)$ and multiplied mod $y^4 + 1$ with a fixed polynomial a(y) = ‘03’ y3 + ‘01’y2 + ‘01’y + ‘02’（引號內是以 16 進制表示的 **byte**，需要當成 polynomial 計算）.
- MixColumns(State) can be performed by the following **matrix multiplication** on State.
- Example（==必考==）

### InvMixColumns(State)

- InvMixColumns(State) is the inverse of MixColumns(State)
which is equivalent to showing

## AddRoundKey Transformation

### AddRoundKey(State, RoundKey)

- a transformation of the state in which a **Round Key** is combined with the state by applying the bitwise **XOR** operation.
- Example
- **Inverse** of AddRoundKey(State, RoundKey) is ==**itself**==.

## Single Round of Cipher()


## KeyExpansion

### KeyExpansion(key)

- a routine that is applied to the **key** to generate the **array key schedule** $w$, including $4 \times (Nr+1)$ **words** (i.e., 44, 52, or 60 words), for $Nr + 1$ **Round Keys** (i.e., 11, 13, 15 Round Keys).
- **key $\Rightarrow$ KeySchedule $\equiv$ ExpandedKey ($w$) $\Rightarrow$ Round Keys**
- The length of each **Round Key** is 4 words (128 bits).
- 1st Round Key: $w[0 .. 3]$
- 2nd Round Key: $w[4 .. 7]$
- ...
- $Nr + 1$th Round Key: w[$4Nr .. 4(Nr +1) − 1$]
- Total Number of Round Key bits = $(4 \times 32) \times (Nr + 1)$ bits
- Example: 1408 Round Key bits for Nr = 10 rounds.

### Algorithm of KeyExpansion(key)


- Illustration for $Nk = 4$ (**128-bit key**)

### KeyExpansion for AES-128 (128-bit key; $Nk = 4$)

KeyExpansion() for AES-128 to generate the words $w[i]$ for $4 \le i < 44$, where $l$ ranges over the multiples 4 between 0 and 36.


### KeyExpansion for AES-192 (192-bit key; Nk = 6)

KeyExpansion() for AES-192 to generate the words $w[i]$ for $6 \le i < 52$, where $l$ ranges over the multiples 6 between 0 and 42.


### KeyExpansion for AES-256 (256-bit key; Nk = 8)

KeyExpansion() for AES-256 to generate the words $w[i]$ for $8 \le i < 60$, where $l$ ranges over the multiples 8 between 0 and 48.


## Cipher Example ($Nk = 4$)


### The progression of State


## Inverse Cipher

Illustration for $Nk = 4$ (**128-bit key**)


## Avalanche Effect

### Change in Plaintext

Illustration for $Nk = 4$ (**128-bit key**)


### Change in Key

Illustration for $Nk = 4$ (**128-bit key**)


## Security Strength of AES

### Brute-Force Attack

- The large key space of AES makes **brute-forcing** the encryption extremely **computationally infeasible with current technology**.
- **Potential Threat**
- Quantum Cryptanalysis could brute-force a N-bit AES in roughly $2^{N/2}$ iterations by using future **large-scale quantum computers**, e.g., AES-128 provides only 64 security bits in quantum computing.
- Fortunately, **AES-256** provides **128 security bits** in quantum computing.

### Differential Cryptanalysis

- An attack technique that analyzes the differences in plaintexts and ciphertexts to extract information about the key.
- AES has been extensively studied for **differential cryptanalysis**, and no **practical attacks** have been found against the **full** AES algorithm.

### Linear Cryptanalysis

- An attack technique that exploits linear approximations in the encryption algorithm to recover the key.
- AES has been carefully designed to resist **linear cryptanalysis**, and **no practical attacks** have been discovered against the **full** AES algorithm.

### Side-Channel Attacks

- Side-channel attacks, such as **timing attacks** or **power analysis**, exploit information leaked during the encryption process, rather than directly attacking the algorithm itself.
- AES is **not inherently vulnerable to side-channel attacks**.
- It's important to ensure that proper countermeasures are applied in the **implementation** to protect against these attacks.

## Advantages

- **Secure**
- having withstood extensive analysis and being widely adopted as a trusted encryption algorithm
- **Efficient**
- enabling fast encryption and decryption speeds
- the availability of hardware acceleration options
- **Flexible**
- supporting various key lengths and block sizes to accommodate different security requirements.
- Widespread **hardware and software support**
- **Compact code length**
- **No bias towards processor architectures**

## Performance

Data extracted from **Rijndael’s AES Proposal in 1999**.

### 8-bit Processor

==Without== using **Lookup Tables**


由於 192 不是 2 的冪次，需要做額外處理，因此 code length 比較長。

- Key Expansion + InvCipher is **30% slower** than Cipher

### 32-bit Processor

==Using== **Lookup Tables**（因為有空間儲存 table）

- Key Expansion
- Cipher/InvCipher

使用查表時，加解密速度相同