# 【密碼學 VIII - Modern Stream Ciphers】

## 01. 現代串流加密法基礎

### 01-01. 定義與核心概念
現代串流加密法將資料視為連續的位元流，其運作單位不再僅限於單一位元，而是可以一次處理 **$r$ 位元 ($r$ bits)**。
* **系統模型**：
1. 明文串流 $P = p_n \dots p_2 p_1$、密文串流 $C = c_n \dots c_2 c_1$ 與金鑰串流 $K = k_n \dots k_2 k_1$，其中的 $p_i, c_i, k_i$ 皆為 $r$-bit 的字組 (Words)。
2. 加密時，使用金鑰串流對應的 $r$-bit 區塊來加密明文區塊。
* **本質**：這種方式可被視為一種運作在極小區塊上的**機率性區塊加密法 (Probabilistic Block Cipher)**。將明文串流（Plaintext Stream）的每一個位元，與金鑰串流（Keystream）的對應位元進行運算（通常是 XOR）以產生密文。
* **特性**：
1. 可以視為一種運作在極小區塊上的機率性區塊加密法。
2. **優點**：速度快、程式碼量小，非常適合即時視訊、瀏覽器連線等需要連續傳輸的場景。
3. **禁忌**：金鑰串流絕對**不可重複使用**（Key Reuse）。

### 01-02. 同步與非同步架構
根據金鑰串流的產生方式，可分為兩類：

**同步串流加密（Synchronous Stream Ciphers）**：
* 金鑰串流的產生**獨立**於明文或密文。
* 傳送方與接收方必須保持精確同步，若傳輸中遺失一個位元，後續解密將全部錯誤。

**非同步串流加密（Asynchronous / Self-synchronizing）**：
* 金鑰串流的產生**依賴**於先前的密文區塊。
* 具有自我同步能力，若發生傳輸錯誤，僅會影響後續幾個區塊，之後會恢復正常。

### 01-03. 關鍵特性與安全禁忌
* **主要優勢**：
1. **速度快 (High Speed)** 與 **程式碼量小 (Small Code Size)**。
2. 非常適合需連續傳輸的資料流，例如：**即時視訊 (Real-time video)** 與瀏覽器連線。
* **絕對禁忌：金鑰串流不可重複使用 (Must Not Be Reused)**
1. 若兩段不同的密文使用了相同的金鑰串流，將兩段密文進行 XOR 運算，其結果等於兩段明文直接進行 XOR ($C_1 \oplus C_2 = P_1 \oplus P_2$)。
2. 這會導致攻擊者在不知道金鑰的情況下，直接分析出明文之間的關係。

:::success
**重點筆記**：信用卡號攻擊
- 假設你使用相同的金鑰串流加密了兩筆交易資料。
- 攻擊者攔截到密文後將它們 XOR，得到了兩段明文的 XOR 值。若其中一段明文是已知的（例如常見的信用卡號前綴格式），攻擊者就能輕易利用這個結果去比對或還原另一張信用卡的號碼。
:::
<br>

## 02. 單次密碼本 (One-Time Pad, OTP)

### 02-01. 完美保密性
OTP 是串流加密的理論基礎，具有「資訊理論安全性」（Information-Theoretic Security），即理論上無法被破解。

* **條件**：
1. **真隨機性 (True Randomness)**：加密金鑰必須是真正的隨機產生，不能是偽隨機 。
2. **長度要求 (Length)**：加密金鑰的長度必須**至少與訊息一樣長**。
3. **單次使用與銷毀 (One-Time Use & Destruction)**：金鑰必須只使用一次，且需防止未經授權的存取。使用後應立即銷毀以防止被重複使用。

### 02-02. 運作原理與實務限制
* **加密公式**：$C_i = P_i \oplus K_i$
* **解密公式**：$P_i = C_i \oplus K_i$
* **實務限制**：在現實中，要產生並安全傳輸與訊息等長的真隨機金鑰非常困難，因此現代加密多使用「偽隨機」來模擬 OTP。

### 02-03. 密文型態分析 (Example 8.1)
為了理解 OTP 的性質，我們探討在四種不同明文情境下，產生的密文特性：

- **情境 A：明文全為 0 ($n$ zeros)**
1. **結果**：密文串流將與金鑰串流完全相同 ($0 \oplus k_i = k_i$)。
2. **隨機性**：因為金鑰是隨機的，所以密文也是隨機的，完全不會保留明文的「全 0」樣式 。

- **情境 B：明文全為 1 ($n$ ones)**
1. **結果**：密文串流將是金鑰串流的補數 (Complement, 即 $1 \oplus k_i = \overline{k_i}$) 。
2. **隨機性**：若金鑰是隨機的，其補數也是隨機的，因此密文依然保持隨機。

- **情境 C：明文為 0 與 1 交錯 ($0101\dots$)**
1. **結果**：每一個密文位元要麼等於金鑰位元，要麼等於其補數 。
2. **隨機性**：在金鑰隨機的前提下，組合出來的結果仍然是隨機的 。

- **情境 D：明文為隨機位元串**
1. **結果**：密文必然是隨機的 。
2. **原理**：因為兩個隨機位元的 XOR 運算結果，本身就是隨機的 。

無論明文長什麼樣子（全 0、全 1、規律或隨機），只要金鑰是真隨機且不重複使用，OTP 產生的密文就會呈現完美的隨機分佈，攻擊者無法從中分析出任何規律。

:::success
**重點筆記：XOR 的特性**
1. 設明文 $P = 1011$，金鑰 $K = 1100$。
2. **加密**：$1011 \oplus 1100 = 0111$ (密文 $C$)
3. **特性**：若你重複使用金鑰 $K$ 加密另一個明文 $P_2$，攻擊者將兩段密文 XOR，就會消掉金鑰，直接暴露兩段明文的關係（$C_1 \oplus C_2 = P_1 \oplus P_2$），這是極大的安全漏洞。
:::

<br>

## 03. 隨機數生成器 (Random Number Generators)
### 03-01. 基本定義與架構
**偽隨機數生成器 (PRNG) 的目標是產生一個看似隨機的數列，該數列必須具備以下特性：**
* **長週期 (Long Period)**：數列重複之前的間隔要夠長。
* **均勻分佈 (Uniform Distributed)**：0 與 1 出現的機率應相等。
* **不可預測 (Unpredictable)**：攻擊者無法推測下一個數值。

**系統運作流程**：
- **輸入來源**：必須是獨立且不可預測的（例如系統雜訊、滑鼠移動軌跡等）。
- **種子生成 (Seed Generation)**：透過種子生成演算法將輸入轉換為初始種子 ($x_0$)。
- **PRNG 演算法**：利用 $x_0$ 透過演算法產生隨機數列 ($x_1, x_2, \dots$)。

**記憶性元件 (Memory Device)**：PRNG 通常包含記憶裝置，這意味著生成的數列會受到「先前數值」的影響。常見的實作方法包括：
* 線性回授移位暫存器 (Linear Feedback Shift Register, LFSR)
* 線性同餘產生器 (Linear Congruence Generator, LCG)
* 非線性亂數產生器 (Nonlinear Random Number Generator)
* 截切亂數產生器 (Truncated Random Number Generator)
* 數學建構亂數產生器 (Mathematically Constructed Random Number Generator)

### 03-02. 隨機性的三個層次
根據安全強度與特性的不同，隨機性可嚴謹地分為三個層級：

- **統計學偽隨機性 (Statistical Pseudo-randomness)**
1. **定義**：位元序列滿足統計上的隨機分佈，即 1 的數量約等於 0 的數量。
2. **限制**：僅「看起來」隨機，但可能容易被預測。
3. **代表例子**：線性同餘產生器 (LCG)。

- **密碼學安全偽隨機性 (Cryptographically Secure Pseudo-randomness, CSPRNG)**
1. **定義**：除了滿足統計隨機性，還必須**不可預測**。
2. **嚴格要求**：給定隨機序列的前 $k$ 個位元，沒有任何多項式時間演算法能以顯著大於 $1/2$ 的機率準確預測出第 $k+1$ 個位元。
3. **代表例子**：Blum Blum Shub (BBS) 產生器。

- **真隨機性 (True Randomness)**
1. **定義**：除了滿足上述所有條件（統計性 + 密碼學安全性），還必須具備**不可重現性 (Non-reproducibility)**。
2. **特性**：無法從相同的輸入數據重複產生相同的位元序列。
3. **限制**：由於電腦演算法本質上是確定性的 (Deterministic)，因此真隨機無法僅靠演算法產生，必須依賴物理現象。
4. **代表例子**：放射性物質的衰變速度、設計良好的實體擲骰子結果。

:::success
**重點筆記**：三種隨機性的差異
- 想像你在玩猜數字遊戲：
1. **統計偽隨機 (LCG)**：就像一個依照特定公式洗牌的機器。雖然牌看起來很亂（紅黑各半），但如果你知道洗牌公式和第一張牌，你就能算出下一張牌是什麼。
2. **密碼學安全 (CSPRNG)**：就像一個超級複雜的密碼鎖。即使你看了前面 100 個開出來的號碼，你也完全猜不到第 101 個號碼會是什麼，除非你能破解背後的超難數學題。
3. **真隨機 (True Randomness)**：就像觀測原子衰變或擲骰子。上帝也不知道下一次什麼時候衰變或骰出幾點，這才是真正的「隨機」，且無法重來一次得到相同結果。
:::

<br>

## 04. 線性回授移位暫存器 (LFSR)

### 04-01. 結構與運作
**LFSR 是由一串暫存器（Register）和一個回授函數（Feedback Function）組成。**
* **運作**：每個時脈週期，位元向左（或右）移位，最末端的位元輸出作為金鑰流的一部分，同時根據「抽頭（Taps）」位置的位元進行 XOR 運算，將結果回填至輸入端。
* **數學表示**：使用**回授多項式**（Feedback Polynomial）來描述 XOR 的連接位置。
* **多項式定義**：對於一個 $m$ 位元的 LFSR，我們將位元 $b_0$ 到 $b_m$ 對應到變數 $x^m, x^{m-1}, \dots, x^0$。
1. **LSB ($b_0$)**：對應最高次項 $x^m$。
2. **回授位元 ($b_m$)**：對應常數項 $1$ ($x^0$)，且必定存在於每個回授多項式中。
3. **係數 $c_i$**：若 $c_i = 1$，代表該位元參與 XOR 運算；若 $c_i = 0$，則斷開連接。

:::success
**種點筆記**：建構 5-bit LFSR
- **題目**：建構一個 5 個記憶單元的 LFSR，回授函數為 $b_5 = b_4 \oplus b_2 \oplus b_0$。
- **分析**：
1. 參與運算的位元是 $b_4, b_2, b_0$，因此對應的 $c_4, c_2, c_0$ 為 1。
2. $b_3, b_1$ 未參與，係數為 0。常數項設置為 1 (代表$x^0 = 1$)
3. **對應多項式**：$f(x) = x^5 + x^3 + x + 1$ (注意 $b_0$ 對應 $x^5$, $b_4$ 對應 $x$)。
- **電路圖**：如下圖所示，只有 $b_4, b_2, b_0$ 拉出線路進入 XOR。
:::

### 04-02. 週期與安全性
* **最大週期**：對於 $m$ 位元的 LFSR，最大週期為 $2^m - 1$（排除全 0 狀態）。
* **本原多項式 (Primitive Polynomial)**：若回授多項式是本原多項式（既不可約也是Primitive），則該 LFSR 可產生最大週期的序列。

:::success
**重點筆記**：4-bit LFSR 運作
- **設定**：4 個記憶單元，回授函數 $b_4 = b_1 \oplus b_0$。初始種子 (Seed) 為 $(0001)_2$。
- **多項式**：$f(x) = x^4 + x^3 + 1$ (對應 $b_0, b_1$ 參與回授)。
- **運作結果**：
1. 產出的金鑰串流 ($k_i$) 為：`100010011010111...`
2. 觀察發現，每 **15 個位元** 就會重複一次。
- **結論**：此 LFSR 產生的序列週期為 15。因為 $x^4 + x^3 + 1$ 是一個**本原多項式 (Primitive Polynomial)** 且不可約，因此它能達到該長度 LFSR 的**最大週期** ($2^m - 1 = 2^4 - 1 = 15$)。

:::

### 04-03. 增加週期的策略
為了提高安全性，我們希望週期越長越好，讓攻擊者難以預測。
- **增加長度**：理論上，$m$ 位元的 LFSR 最大週期可達 $2^m - 1$。長度越長，週期指數增長。
- **多重 LFSR 組合**：將多個不同週期的 LFSR 輸出進行 XOR 結合。
1. **新週期計算**：若兩個 LFSR 週期分別為 $T_1$ 和 $T_2$，結合後的週期為 $\text{lcm}(T_1, T_2)$ (最小公倍數)。
2. *公式*：$\text{lcm}(2^{m_1}-1, 2^{m_2}-1)$。

### 04-04. 線性複雜度 (Linear Complexity)
**線性複雜度** 是評估串流加密安全性的重要指標。
- **定義**：要產生特定序列 $s$，所需的**最短** LFSR 長度。
- **意義**：
1. 若一個序列的線性複雜度 $L$ 很小，攻擊者只需攔截 $2L$ 長度的密文，就能解出整個 LFSR 的結構（利用矩陣運算求解係數 $c_i$）。
2. 這屬於**已知明文攻擊 (Known-plaintext attack)**。
- **防禦**：現代串流加密通常會加入**非線性組合 (Nonlinear Combinations)**，以大幅提高線性複雜度，使攻擊者難以用單一 LFSR 來模擬。

### 04-05. Berlekamp-Massey 演算法
這是一個用來攻擊 LFSR 的強大演算法。
- **功能**：給定一段長度為 $n$ 的位元序列，能在多項式時間內算出該序列的**線性複雜度 $L$** 以及對應的**回授多項式 $f(x)$**。
- **運作邏輯**：這是一個遞迴演算法，逐一檢查序列中的位元。若目前的 LFSR 無法產生下一個位元（出現差異 $d=1$），就修正多項式 $f(x)$ 並增加長度 $L$，直到能完美產生該序列為止。

INPUT: a binary sequence 𝑠𝑛 = 𝑠0, 𝑠1, 𝑠2, … , 𝑠𝑛−1 of length 𝑛.
OUTPUT: the linear complexity 𝐿 𝑠𝑛 of 𝑠𝑛, 0 ≤ 𝐿 𝑠𝑛 ≤ 𝑛.
1. Initialization: 𝑓 𝑥 ← 1, 𝐿 ← 0, 𝑚 ← −1, 𝐵 𝑥 ← 1, 𝑖 ← 0
2. While (𝑖 < 𝑛) do the following:
    2.1 Computing the next discrepancy 𝑑 ← 𝑠𝑖 + σ𝑗=1 𝐿 𝑐 𝑗𝑠𝑖−𝑗 mod 2
    2.2 If 𝑑 = 1, then do the following:
        𝑇 𝑥 ← 𝑓 𝑥 , 𝑓 𝑥 ← 𝑓 𝑥 + 𝐵 𝑥 ∙ 𝑥𝑖−𝑚.
        If 𝐿 ≤ 𝑖/2, then 𝐿 ← 𝑖 + 1 − 𝐿, 𝑚 ← 𝑖, 𝐵 𝑥 ← 𝑇 𝑥 .
    2.3 𝑖 ← 𝑖 + 1
3. Return (𝐿)

:::success
**重點筆記**：演算法執行結果
- 給定序列 $s = (1, 0, 1, 0, 0, 1, 1)$，長度 $n=7$。
- 執行 Berlekamp-Massey 演算法後，得出：
1. 線性複雜度 $L = 3$
2. 回授多項式 $f(x) = 1 + x + x^3$
- 這代表只要用一個 3-bit 的 LFSR 就能完全預測這個序列的後續發展。
:::

<br>

## 05. 其他生成演算法

### 05-01. 線性同餘產生器 (Linear Congruence Generator, LCG)
這是一種最基本且常見的偽隨機數生成方法，基於遞迴關係。
* **演算法公式**：
$$x_{i+1} = (a \cdot x_i + b) \pmod m$$
1. $x_0$：初始種子 (Seed)。
2. $a, b, m$：構成密鑰的參數（$m$ 為模數，$a$ 為乘數，$b$ 為增量）。
* **全週期特性 (Full-Period)**：根據數論，若 $a, b, m$ 選擇得當，產生器可以產生一個包含 $m$ 個相異整數的「全週期」序列（最大週期 = $m$）。

:::success
**重點筆記**：參數選擇對週期的影響
- **案例 A (好的參數)**：
1. 設 $m=8, a=5, b=3, x_0=3$。
2. 序列：2, 5, 4, 7, 6, 1, 0, 3, 2...
3. **結果**：週期為 8 (等於 $m$)，這是全週期序列。
- **案例 B (壞的參數)**：
1. 設 $m=12, a=3, b=4, x_0=5$。
2. 序列：7, 1, 7, 1...
3. **結果**：週期僅為 2 (遠小於 $m$)，隨機性極差。
:::

* **LCG 的變形**：
1. **k 階 LCG (k-th Order LCG)**：當前的數值不僅取決於前一個 ($x_i$)，還取決於前 $k$ 個數值 ($x_i, \dots, x_{i-k+1}$)。
2. **簡化版 LCG (Simplified LCG)**：不使用增量 $b$。公式為 $x_{i+1} = a \cdot x_i \pmod m$。其週期取決於 $a$ 對模 $m$ 的階（Order）。

### 05-02. 非線性亂數產生器 (Nonlinear Random Number Generator)
為了克服線性產生器（如 LCG, LFSR）容易被預測的缺點，這類產生器引入了非線性結構。
* **架構**：使用多個 LFSR 作為輸入源，將它們的輸出送入一個 **非線性函數 (Nonlinear Function)** 進行混合運算。
* **目的**：破壞線性的數學關係，增加攻擊者逆推內部狀態的難度。

### 05-03. 截切亂數產生器 (Truncated Random Number Generator)
* **原理**：不輸出產生器生成的完整序列，而是**部分擷取**。例如，產生了一長串數列，但只挑選其中的特定片段按順序輸出。
* **優點**：即使攻擊者破解了背後的線性關係，由於缺乏完整的連續數據，也很難重建整個序列。

:::success
**重點筆記**：截切操作
- 假設公式為 $x_{i+1} = 5x_i + 3 \pmod{16}$，種子 $x_0=1$。
- **原始完整序列**：`8, 11, 10, 5, 12, 15, 14, 9, 0, 3, 2, 13, 4, 7, 6, 1, 8...`
- **截切後輸出** (例如每隔幾個取一段)：`11, 10, 5, 15, 14, 9, 3, 2, 13, 7, 6, 1...` (原本連貫的數學關係被「跳過」的動作打斷了)。
:::

### 05-04. 數學建構亂數產生器
這類方法利用數論中的難題來確保隨機性與安全性。

**質數倒數法 (Prime Method)**
- 選擇一個大質數 $p$，計算 $1/p$。
- 取小數點後的第一個非零數字開始作為序列。
- 因為 $p$ 是質數，其最大週期可達 $p-1$。

**Blum Blum Shub (BBS)**：這是最著名的 **密碼學安全偽隨機數生成器 (CSPRNG)**，安全性基於二次剩餘 (Quadratic Residue) 問題。
* **設定步驟**：
1. 選兩個大質數 $p, q$，滿足 $p \equiv q \equiv 3 \pmod 4$。
2. 計算 Blum 整數 $n = p \times q$。
3. 選一個與 $n$ 互質的數 $r$，計算種子 $x_0 = r^2 \pmod n$。
* **生成公式**：
$$x_{i+1} = x_i^2 \pmod n$$
* **輸出**：通常取 $x_i$ 的最低有效位 (LSB) 作為隨機位元。
* **特性**：只要 $n$ 的因數分解很難，這個序列就無法被預測。
* **地位**：被證明具有極高的密碼學強度（CSPRNG），但運算速度較慢，適合產生金鑰而非大量資料加密。

<br>

## 06. 安全性評估：卡方檢定 (Chi-Square Test)

### 06-01. 基本概念與公式
卡方檢定是一種統計方法，用來評估隨機數生成器（RNG）產生的序列是否符合預期的機率分佈（即是否具備統計隨機性）。
* **原理**：比較「觀察到的次數」與「理論上應有的次數」之差異。
* **公式**：
$$\chi^2 = \sum_{1 \le i \le k} \frac{(Y_i - nP_i)^2}{nP_i}$$
1. $Y_i$：第 $i$ 種結果的**觀察次數** (Observed frequency)。
2. $nP_i$：第 $i$ 種結果的**期望次數** (Expected frequency)，其中 $n$ 為總次數，$P_i$ 為該結果的理論機率。
* **先決條件**：為了確保準確性，樣本數 $n$ 必須夠大，使得每一項的期望次數 $nP_i$ 至少為 **5**。

### 06-02. 實例演示：擲骰子實驗
我們使用「同時擲兩顆骰子」的總和來進行檢定。


* **情境**：
1. 可能結果 ($k$)：2 到 12，共 11 種可能。
2. 總次數 ($n$)：144 次。
* **數據比對**：理論上，擲 144 次骰子，總和為 2 的機率是 $1/36$（期望次數 4 次），總和為 7 的機率是 $6/36$（期望次數 24 次）。實驗數據如下：
1. **觀察值 ($Y_i$)**：2, 4, 10, 12, 22, 29, 21, 15, 14, 9, 6
2. **期望值 ($nP_i$)**：4, 8, 12, 16, 20, 24, 20, 16, 12, 8, 4
* **計算 $\chi^2$ 值**：將上述數據代入公式
$$\chi^2 = \frac{(2-4)^2}{4} + \frac{(4-8)^2}{8} + \dots + \frac{(6-4)^2}{4} = 7 \frac{7}{48} \approx 7.146$$

### 06-03. 自由度與結果判讀
算出 $\chi^2$ 值後，我們需要判斷這個數值代表「隨機」還是「被操縱」。

- **計算自由度 (Degrees of freedom, df)**：在本例中，可能的結果有 11 種 ($k=11$)，因此自由度 $df = 10$。
$$df = k - 1$$

- **查表判讀**：對照下方的卡方分佈表，找到 $df=10$ 的那一列。
1. 我們算出的數值 **7.146** 落在 **6.18** ($p=0.80$) 與 **7.27** ($p=0.70$) 之間。
2. 這代表其 $p$-value（機率）介於 70% 到 80% 之間。

- **決策規則 (Decision Rules)**：根據 $p$-value 來評估隨機性好壞
1. **拒絕 (Reject)**：$p < 1\%$ 或 $p > 99\%$。 (**注意**：如果 $p$ 值過高（例如 99.9%），代表數據「太完美了」，反而極大可能是人為偽造的。)
2. **可疑 (Suspect)**：$1\% \le p \le 5\%$ 或 $95\% \le p \le 99\%$。
3. **良好 (Good)**：$20\% \le p \le 30\%$ 或 $70\% \le p \le 80\%$。
4. **優秀 (Excellent)**：$30\% \le p \le 70\%$。

* **結論**：本例結果落在 70%~80% 區間，屬於 **"Good"**，表示這組骰子沒有明顯的作弊嫌疑。
* **建議**：通常建議至少進行 **3 次** 獨立測試，以獲得更具說服力的評估結果。

<br>

## 07. RC4 加密演算法

### 07-01. 簡介與特性
RC4 是由 Ron Rivest 於 1987 年為 RSA Security 設計的串流加密演算法。
- **運作單位**：以 **Byte (位元組)** 為單位進行運算，每位元組約需 8 到 16 次操作，速度極快。
- **金鑰長度**：可變動 (Variable)，提供彈性的加密強度。
- **週期**：研究顯示其週期極長，可能超過 $10^{100}$。
- **應用歷史**：由於效率高，曾廣泛用於 SSL、WEP 和 WPA 等協定中。

**RC4 的核心是維護一個 256 bytes 的狀態向量 $S$，運作分為兩個階段：**

- **初始化階段 (KSA, Key-Scheduling Algorithm)**：利用暫存向量 $T$ (填滿金鑰 $K$) 來打亂狀態向量 $S$ 的初始排列 ($0 \sim 255$)。

    j = 0;
    for i = 0 to 255 do
        j = (j + S[i] + T[i]) mod 256
        swap(S[i], S[j])

:::info
**注意事項**：經過此步驟，S 陣列內的數值已被金鑰打亂，但仍包含 0 到 255 的所有數值。
:::

- **生成階段 (PRGA, Pseudo-Random Generation Algorithm)**：持續交換 $S$ 內部的元素並輸出金鑰流 $k$，再與明文 $M$ 進行 XOR。

    i = 0, j = 0;
    For each message byte M_i:
        i = (i + 1) mod 256
        j = (j + S[i]) mod 256
        swap(S[i], S[j])
        t = (S[i] + S[j]) mod 256
        k = S[t]          // 產出的金鑰流 byte
        C_i = M_i XOR k   // 加密


### 07-03. 廣播攻擊 (Broadcast RC4 Attack)
由 Itsik Mantin 與 Adi Shamir 於 2001 年提出，揭露了 RC4 的重大統計弱點。
* **垂直分析 (Vertical Analysis)**：不同於傳統分析單一金鑰流的偏差，此攻擊觀察「使用同一把金鑰加密不同明文」時，**相同位置**的輸出位元組。
* **偏差發現**：
1. RC4 的 **第二個輸出 byte** 有強烈的偏差，傾向於出現 **0**。
2. 實驗顯示，第二個 byte 為 0 的機率約為 $1/128$，遠高於隨機分佈應有的 $1/256$。
* **影響與解法**：
1. 攻擊者可利用大量密文區分出 RC4 加密流與真隨機流 (Distinguishing Attack)，甚至還原資訊。
2. **解法**：只要拋棄 RC4 輸出的**前幾個 bytes** (Drop the first few outputs)，即可避開此偏差。

### 07-04. 運作流程
RC4 分為兩個主要階段：
- **KSA (Key-Scheduling Algorithm)**：利用金鑰 $K$ 來打亂 S-Box 的初始排列（原本是 0~255 的順序）。
- **PRGA (Pseudo-Random Generation Algorithm)**：
1. 持續交換 S-Box 內的元素並輸出數值作為金鑰流 $k$。
2. 最後將 $k$ 與明文 $M$ 進行 XOR：$C = M \oplus k$。

### 07-05. 安全性崩潰與禁用
隨著時間推移，RC4 的安全性逐漸瓦解，最終被網路標準淘汰。
- **WEP 的設計缺陷**：IEEE 802.11 WEP 協定雖然使用 RC4，但因 IV (初始向量) 的構建方式有誤，導致金鑰極易被破解，WEP 因此被視為完全不安全。
- **NOMORE 攻擊**：2015 年針對 TLS 與 WPA-TKIP 的新攻擊，進一步證實了 RC4 在現代環境下的脆弱性。
- **正式禁用**：
1. 2015 年 2 月，**RFC 7465** 發布，正式禁止在 TLS 的所有版本中使用 RC4。
2. 取而代之的主流演算法為 **AES-GCM** 與 **ChaCha20-Poly1305**。

<br>

## 08. 常見串流加密攻擊手法

### 08-01. 相關初始化向量攻擊 (Related-IV Attack)
許多串流加密法會結合金鑰 (Key) 與初始化向量 (IV) 來產生金鑰串流，目的是確保即使使用同一把金鑰，每次加密也能產生不同的輸出。然而，若 IV 管理不當，將導致嚴重漏洞。

**攻擊原理**：
* 若兩個不同的加密過程使用了**相同**或**極為相似**的 IV，可能會產生相似甚至完全相同的金鑰串流 (Keystream Reuse)。
* **數學推導**：
當金鑰串流 $K$ 被重複使用時：
$$C_1 = P_1 \oplus K$$
$$C_2 = P_2 \oplus K$$
將兩式進行 XOR 運算：
$$C_1 \oplus C_2 = (P_1 \oplus K) \oplus (P_2 \oplus K) = P_1 \oplus P_2$$
* **後果**：攻擊者無需知道金鑰 $K$，只要攔截密文 $C_1, C_2$，就能消除金鑰的保護，直接分析出明文之間的關係。

:::success
**重點筆記**：WEP 協定的崩潰
- IEEE 802.11 無線網路早期的 WEP 協定是此攻擊最著名的受害者。
- **設計缺陷**：WEP 直接將 24-bit 的 IV 與金鑰串接 (`RC4 key = IV || key`) 作為種子。
- **IV 過短**：24-bit 的空間太小，導致 IV 在短時間內就會發生重複 (Collision)。
- **結果**：攻擊者只需收集足夠的封包（Packet），利用 IV 重複的特性，幾分鐘內就能完全破解 WEP 金鑰。
:::

### 08-02. 區別攻擊 (Distinguishing Attack)
一個安全的串流加密法，其輸出應無法與「真隨機亂數」區分開來。此攻擊旨在打破這個假設。

* **攻擊目標**：不需要直接解出金鑰，而是試圖證明該加密法的輸出具有**統計偏差 (Statistical Bias)** 或非均勻的模式。
* **意義**：
1. 若能將金鑰串流與真隨機區分開來，代表加密法存在結構性弱點。
2. 這些統計偏差往往是更進一步攻擊（如金鑰還原）的基礎。
* **實例**：RC4 金鑰串流的**前幾個 Bytes** 具有顯著偏差（例如 Mantin's Bias），攻擊者利用這些偏差可以識別出 RC4 流量，甚至在 TLS 等協定中協助還原明文。

### 08-03. 猜測與決定攻擊 (Guess-and-Determine Attack)
這是一種針對加密法「內部狀態 (Internal State)」的攻擊方式，常見於攻擊基於 LFSR 的系統。

* **運作邏輯**：
1. **猜測 (Guess)**：攻擊者先猜測內部狀態的「一部分」（例如暫存器中的某幾個 bits）。
2. **推導 (Determine)**：利用加密法的結構特性（如遞迴公式），根據剛剛猜測的部分，推導出剩餘的內部狀態。
3. **驗證**：將推導出的完整狀態用來產生金鑰流，並與實際攔截到的金鑰流比對。若符合則猜測正確；若不符則修正猜測。
* **威脅**：一旦內部狀態被完全還原，攻擊者就能重建出過去與未來的所有金鑰串流，導致通訊完全透明化。