---
# System prepended metadata

title: 'Ch06: Advanced Encryption Standard'
tags: [密碼學]

---

<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”)
    ![image.png](https://hackmd.io/_uploads/HJfCWvP7p.png)

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

![image.png](https://hackmd.io/_uploads/BJEfdwP7T.png =600x)
![image.png](https://hackmd.io/_uploads/ByBXOvPma.png =600x)
![image.png](https://hackmd.io/_uploads/SynrOvwX6.png)
![image.png](https://hackmd.io/_uploads/SyxIaOPmT.png)

## 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
    ![image.png](https://hackmd.io/_uploads/rJ2XhTDma.png =500x)
    - ==**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
  ![image.png](https://hackmd.io/_uploads/SJQBkYwma.png =500x)
  ![image.png](https://hackmd.io/_uploads/SJeL1tDma.png =500x)
  - Key 的部分，若 $Nk$ 等於 6 或 8，row 依然是 4 列，但 column 會變成 6 或 8 行。
- Encryption Process
  ![image.png](https://hackmd.io/_uploads/rkMYWCvma.png)

- Parameters
  ![image.png](https://hackmd.io/_uploads/ByKA1Fw76.png)

## 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$)
  ![image.png](https://hackmd.io/_uploads/ryWBs0vma.png =500x)
  - $in$: input plaintext block
  - $w$: expandedkey $\equiv$ key schedule 
- Block Diagram for Cipher and InvCipher (Encryption and Decryption)
  ![image.png](https://hackmd.io/_uploads/BJM3iCvQT.png)
- Round Structure
  ![image.png](https://hackmd.io/_uploads/SyjZ3CDQa.png)

## 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.
  ![image.png](https://hackmd.io/_uploads/BydSlJuQT.png)
- Affine transformation for each Byte
  ![image.png](https://hackmd.io/_uploads/HkoLeyOXp.png)

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

![image.png](https://hackmd.io/_uploads/HkmFlJdXp.png)

- Example
  ![image.png](https://hackmd.io/_uploads/BkNk-Jd7p.png)

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

![image.png](https://hackmd.io/_uploads/rk1B-yOQT.png)

## ShiftRows Transformation

### ShiftRows(State)

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

![](https://hackmd.io/_uploads/SkrdzvPfT.png)

Example:

![](https://hackmd.io/_uploads/HkJcGDwMp.png)

### InvShiftRows(State)

![](https://hackmd.io/_uploads/By2sGDvMa.png)

Example:

![](https://hackmd.io/_uploads/ryC3fwPG6.png)

## 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 計算）.
  ![image.png](https://hackmd.io/_uploads/BkWuoIOXT.png)
- MixColumns(State) can be performed by the following **matrix multiplication** on State.
  ![image.png](https://hackmd.io/_uploads/BkvUiIdQp.png)
- Example（==必考==）
  ![image.png](https://hackmd.io/_uploads/HyEWa8uQ6.png)

### InvMixColumns(State)

- InvMixColumns(State) is the inverse of MixColumns(State)  
  ![image.png](https://hackmd.io/_uploads/r1QgVwOXT.png)  
  which is equivalent to showing  
  ![image.png](https://hackmd.io/_uploads/S14AEvu7a.png)

## 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.
  ![image.png](https://hackmd.io/_uploads/Bka7BvOQ6.png)
- Example
  ![image.png](https://hackmd.io/_uploads/S1g8Sv_Q6.png)
- **Inverse** of AddRoundKey(State, RoundKey) is ==**itself**==.

## Single Round of Cipher()

![image.png](https://hackmd.io/_uploads/SknWYAdQp.png)

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

![](https://hackmd.io/_uploads/ByNIEPvzp.png)

- Illustration for $Nk = 4$ (**128-bit key**)
  ![image.png](https://hackmd.io/_uploads/BJvasRuQT.png)

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

![image.png](https://hackmd.io/_uploads/BksG2AuX6.png)

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

![image.png](https://hackmd.io/_uploads/HyjXAC_m6.png)

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

![image.png](https://hackmd.io/_uploads/r15K00u7T.png)

## Cipher Example ($Nk = 4$)

![2023-11-08_18-20-53.png](https://hackmd.io/_uploads/rJ2rW1tQa.png)

### The progression of State

![image.png](https://hackmd.io/_uploads/SJJiZJFmp.png)

## Inverse Cipher

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

![image.png](https://hackmd.io/_uploads/Sk-1M1F7p.png)

## Avalanche Effect

### Change in Plaintext

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

![image.png](https://hackmd.io/_uploads/H138Q1Fm6.png)

### Change in Key

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

![image.png](https://hackmd.io/_uploads/SJE9QJtma.png)

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

![image.png](https://hackmd.io/_uploads/HJF7AOxQT.png)

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

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

### 32-bit Processor

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

- Key Expansion
  ![image.png](https://hackmd.io/_uploads/By5FyFgX6.png)
- Cipher/InvCipher
  ![image.png](https://hackmd.io/_uploads/By43JtxQa.png)
  
使用查表時，加解密速度相同

