彩虹表

彩虹表（Rainbow table）是電腦安全領域中一種用於攻擊密碼散列函數的預計算表，主要用於在有限的時間內破解存儲的密碼哈希值。

彩虹表是時空權衡（Time-Memory Trade-off）理論的典型應用。它在暴力破解（花費大量時間、少量存儲）和簡單的查找表（花費少量時間、巨量存儲）之間取得了平衡。通過預先計算並存儲特殊的「哈希鏈」，彩虹表能夠以比暴力破解快得多的速度破解哈希，同時所需的存儲空間遠小於存儲所有可能哈希值的全量查找表。

彩虹表技術通常用於破解長度固定且字符集固定的密碼（例如純數字或字母組合）。現代的密碼安全實踐通常通過加鹽（Salt）和使用慢速哈希演算法（如bcrypt、scrypt）來防禦彩虹表攻擊。

<image>

## 背景與原理

在電腦安全認證系統中，為了防止密碼洩露，通常不會在資料庫中以明文存儲使用者密碼，而是存儲密碼的密碼散列摘要（Hash）。當使用者登錄時，系統將輸入的密碼進行同樣的哈希運算，並與資料庫中的摘要進行比對。

攻擊者如果獲取了資料庫（即獲取了所有使用者的哈希值），試圖還原明文密碼時面臨兩種極端選擇：

- 暴力破解：嘗試每一個可能的密碼組合，計算其哈希值並比對。這不需要存儲空間，但計算量極大，時間成本極高。
- 全量查找表：預先計算所有可能密碼的哈希值並存儲為`(Hash, Password)`對。破解時只需查詢即可，速度極快，但對於現代複雜的密碼規則，生成的表會大到無法存儲。

時空權衡（Time-Memory Trade-off）旨在尋找上述兩者的平衡點。1980年，馬丁·赫爾曼提出了一種基於矩陣的演算法，這是彩虹表的前身。2003年，Philippe Oechslin提出了彩虹表演算法，通過使用不同的歸約函數（Reduction Function）顯著提高了破解成功率並優化了存儲結構。

## 哈希鏈

彩虹表的核心在於哈希鏈（Hash Chain）。

注意：彩虹表中的哈希鏈與通常密碼學中定義的Lamport哈希鏈（只包含哈希函數遞歸運算）不同。彩虹表的鏈是通過交替使用哈希函數 $H$ 和歸約函數 $R$ 來生成的。

- 哈希函數 $H(p) \to h$：將明文 $p$ 映射為哈希值 $h$。
- 歸約函數 $R(h) \to p'$：將哈希值 $h$ 映射回某種格式的「偽明文」 $p'$。需要注意的是，歸約函數並不是哈希函數的反函數（哈希函數不可逆），它只是將哈希值強行變換為另一個可能的密碼字串（例如，取哈希值的前6位字符）。

一條長度為 $k$ 的哈希鏈結構如下：

$$p_0 \xrightarrow{H} h_1 \xrightarrow{R} p_1 \xrightarrow{H} h_2 \xrightarrow{R} p_2 \cdots \xrightarrow{R} p_{k-1} \xrightarrow{H} h_k$$

為了減少存儲空間，系統只存儲每條鏈的起點（Start point, $p_0$）和終點（End point, $h_k$）。中間所有的計算結果都會被丟棄。通過存儲大量的 $(p_0, h_k)$ 對，就構成了預計算表。

### 查找過程

假設攻擊者獲取了一個哈希值 $h_{target}$，想要找到其對應的密碼。

- 攻擊者對 $h_{target}$ 應用歸約函數 $R$ 得到偽明文，再進行哈希，不斷重複此過程，生成一條新的鏈。

- 在每一步計算後，檢查產生的結果是否與表中存儲的某個終點 $h_k$ 匹配。

- 如果匹配（例如在第 $j$ 步匹配到了鏈 $i$ 的終點），則說明目標密碼可能位於鏈 $i$ 中。

- 攻擊者從鏈 $i$ 的起點 $p_{0,i}$ 開始重新計算整條鏈，直到找到 $h_{target}$ 的前驅節點，該節點即為目標密碼。

### 簡單哈希鏈的缺陷

如果使用單一的歸約函數 $R$，會面臨嚴重的碰撞合併（Chain Merger）問題。

如果在兩條不同的鏈中，任意位置生成的偽明文 $p$ 相同（即 $R(h_a) = p = R(h_b)$），那麼這兩條鏈隨後的所有節點都將完全相同，最終匯聚到同一個終點。這意味著表中的大量存儲空間被重複的鏈占據，導致實際覆蓋的密碼空間大幅減少，效率降低。

## 彩虹表的改進

彩虹表解決了簡單哈希鏈的碰撞合併問題。Philippe Oechslin引入了一系列不同的歸約函數 $R_1, R_2, \dots, R_k$。

在彩虹表中，哈希鏈的每一步使用特定的歸約函數，其順序是固定的：

$$p_0 \xrightarrow{H} h_1 \xrightarrow{R_1} p_1 \xrightarrow{H} h_2 \xrightarrow{R_2} p_2 \cdots \xrightarrow{R_{k-1}} p_{k-1} \xrightarrow{H} h_k$$

### 解決碰撞

由於每一步使用的歸約函數不同，即使兩條鏈在中間某處發生了數值碰撞（例如鏈A的第2步結果等於鏈B的第2步結果），如果它們發生碰撞的位置（步驟序號）不同，它們的下一步將使用不同的歸約函數（例如鏈A使用 $R_3$，鏈B使用 $R_5$）。

這樣，生成的下一個偽明文將大機率不同，從而使兩條鏈「分道揚鑣」，避免了鏈的合併。只有當兩條鏈在相同的位置發生數值碰撞時，它們才會合併。這種機率遠低於簡單哈希鏈，從而允許彩虹表在相同的存儲空間下覆蓋更多的密碼空間。

## 應用實例

彩虹表在破解早期的作業系統密碼時效果顯著，典型的例子是微軟的LAN Manager（LM Hash）。

- 不區分大小寫：LM Hash將密碼轉換為大寫，字符集大幅縮小。
- 分段加密：它將14位密碼分為兩組7位分別哈希。這使得攻擊者只需分別生成針對7位字符的彩虹表，複雜度從 $95^{14}$ 驟降至 $2 \times 95^7$。
- 無鹽值：LM Hash 不使用鹽，這意味著通用的彩虹表可以直接用於攻擊任何使用該系統的電腦。

隨著現代作業系統廣泛採用加鹽的哈希演算法（如NTLMv2、SHA-512），通用的預計算彩虹表已難以直接奏效。

## 防禦措施

彩虹表攻擊極其有效，但可以通過特定的密碼學實踐進行防禦。

### 加鹽（Salting）

加鹽是防禦彩虹表最有效的方法。

- 原理：在對密碼進行哈希之前，系統會生成一個隨機字串（鹽），將其拼接到密碼上：$H(\text{salt} + \text{password})$。
- 效果：彩虹表是針對特定哈希函數預先計算的。如果加入了鹽，相當於修改了哈希函數。攻擊者必須為每一個可能的鹽值重新計算一整套彩虹表。如果鹽足夠長且隨機（例如128位），預計算所有可能的彩虹表在計算上和存儲上都是不可行的。

### 密鑰延伸（Key Stretching）

使用計算成本高昂的哈希演算法，如PBKDF2、bcrypt、scrypt或Argon2。

- 原理：這些演算法通過成千上萬次的迭代哈希運算，或者強制要求大量的記憶體訪問，使得計算一次哈希值需要顯著的時間（例如0.5秒）。
- 效果：這使得生成彩虹表的成本呈指數級上升，同時也極大地拖慢了暴力破解的速度。

## 外部連結

- Project RainbowCrack - 著名的彩虹表生成工具（原始官網僅支持HTTP，此為網際網路檔案館備份）
- Ophcrack - Philippe Oechslin開發的基於彩虹表的Windows密碼破解工具（項目已遷移至SourceForge）
- Computers/Hacking/Cryptography/