彩虹表

**彩虹表**（）是计算机安全领域中一种用于攻击密码散列函数的预计算表，主要用于在有限的时间内破解存储的密码哈希值。

彩虹表是时空权衡（Time-Memory Trade-off）理论的典型应用。它在暴力破解（花费大量时间、少量存储）和简单的查找表（花费少量时间、巨量存储）之间取得了平衡。通过预先计算并存储特殊的“哈希链”，彩虹表能够以比暴力破解快得多的速度破解哈希，同时所需的存储空间远小于存储所有可能哈希值的全量查找表。

彩虹表技术通常用于破解长度固定且字符集固定的密码（例如纯数字或字母组合）。现代的密码安全实践通常通过加盐（Salt）和使用慢速哈希算法（如bcrypt、scrypt）来防御彩虹表攻击。

## 背景与原理
在计算机安全认证系统中，为了防止密码泄露，通常不会在数据库中以明文存储用户密码，而是存储密码的密码散列摘要（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}，想要找到其对应的密码。
1. 攻击者对 h_{target} 应用归约函数 R 得到伪明文，再进行哈希，不断重复此过程，生成一条新的链。
2. 在每一步计算后，检查产生的结果是否与表中存储的某个**终点** h_k 匹配。
3. 如果匹配（例如在第 j 步匹配到了链 i 的终点），则说明目标密码可能位于链 i 中。
4. 攻击者从链 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秒）。
* **效果**：这使得生成彩虹表的成本呈指数级上升，同时也极大地拖慢了暴力破解的速度。

## 参见
* 密码散列函数
* 暴力破解
* 字典攻击
* 时空权衡
* A5/1（GSM流密码，常被彩虹表攻击）

## 参考资料

## 外部链接
* Project RainbowCrack - 著名的彩虹表生成工具（原始官网仅支持HTTP，此为互联网档案馆备份）
* Ophcrack - Philippe Oechslin开发的基于彩虹表的Windows密码破解工具（项目已迁移至SourceForge）
*