彩虹表

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

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

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

简化的彩虹表结构示意图，展示了三个归约函数（Reduction functions）的使用。

背景与原理

在计算机安全认证系统中，为了防止密码泄露，通常不会在数据库中以明文存储用户密码，而是存储密码的密码散列摘要（Hash）。当用户登录时，系统将输入的密码进行同样的哈希运算，并与数据库中的摘要进行比对。

攻击者如果获取了数据库（即获取了所有用户的哈希值），试图还原明文密码时面临两种极端选择：

1. 暴力破解：尝试每一个可能的密码组合，计算其哈希值并比对。这不需要存储空间，但计算量极大，时间成本极高。
2. 全量查找表：预先计算所有可能密码的哈希值并存储为`(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）
• 开放目录项目中的“Cryptography”