彩虹表

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

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

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


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

攻击者如果获取了数据库（即获取了所有用户的哈希值），试图还原明文密码时面临两种极端选择：
 暴力破解：尝试每一个可能的密码组合，计算其哈希值并比对。这不需要存储空间，但计算量极大，时间成本极高。
 全量查找表：预先计算所有可能密码的哈希值并存储为`(Hash, Password)`对。破解时只需查询即可，速度极快，但对于现代复杂的密码规则，生成的表会大到无法存储。

时空权衡（Time-Memory Trade-off）旨在寻找上述两者的平衡点。1980年，马丁·赫尔曼提出了一种基于矩阵的算法，这是彩虹表的前身。2003年，Philippe Oechslin提出了彩虹表算法，通过使用不同的归约函数（Reduction Function）显著提高了破解成功率并优化了存储结构。

 哈希链 
彩虹表的核心在于哈希链（Hash Chain）。

注意：彩虹表中的哈希链与通常密码学中定义的Lamport哈希链（只包含哈希函数递归运算）不同。彩虹表的链是通过交替使用哈希函数  和归约函数  来生成的。

 哈希函数 ：将明文  映射为哈希值 。
 归约函数 ：将哈希值  映射回某种格式的“伪明文” 。需要注意的是，归约函数并不是哈希函数的反函数（哈希函数不可逆），它只是将哈希值强行变换为另一个可能的密码字符串（例如，取哈希值的前6位字符）。

一条长度为  的哈希链结构如下：

为了减少存储空间，系统只存储每条链的起点（Start point, ）和终点（End point, ）。中间所有的计算结果都会被丢弃。通过存储大量的  对，就构成了预计算表。

 查找过程 
假设攻击者获取了一个哈希值 ，想要找到其对应的密码。
1. 攻击者对  应用归约函数  得到伪明文，再进行哈希，不断重复此过程，生成一条新的链。
2. 在每一步计算后，检查产生的结果是否与表中存储的某个终点  匹配。
3. 如果匹配（例如在第  步匹配到了链  的终点），则说明目标密码可能位于链  中。
4. 攻击者从链  的起点  开始重新计算整条链，直到找到  的前驱节点，该节点即为目标密码。

 简单哈希链的缺陷 
如果使用单一的归约函数 ，会面临严重的碰撞合并（Chain Merger）问题。
如果在两条不同的链中，任意位置生成的伪明文  相同（即 ），那么这两条链随后的所有节点都将完全相同，最终汇聚到同一个终点。这意味着表中的大量存储空间被重复的链占据，导致实际覆盖的密码空间大幅减少，效率降低。

 彩虹表的改进 
彩虹表解决了简单哈希链的碰撞合并问题。Philippe Oechslin引入了一系列不同的归约函数 。

在彩虹表中，哈希链的每一步使用特定的归约函数，其顺序是固定的：

 解决碰撞 
由于每一步使用的归约函数不同，即使两条链在中间某处发生了数值碰撞（例如链A的第2步结果等于链B的第2步结果），如果它们发生碰撞的位置（步骤序号）不同，它们的下一步将使用不同的归约函数（例如链A使用 ，链B使用 ）。
这样，生成的下一个伪明文将大概率不同，从而使两条链“分道扬镳”，避免了链的合并。只有当两条链在相同的位置发生数值碰撞时，它们才会合并。这种概率远低于简单哈希链，从而允许彩虹表在相同的存储空间下覆盖更多的密码空间。

 应用实例 
彩虹表在破解早期的操作系统密码时效果显著，典型的例子是微软的LAN Manager（LM Hash）。

 不区分大小写：LM Hash将密码转换为大写，字符集大幅缩小。
 分段加密：它将14位密码分为两组7位分别哈希。这使得攻击者只需分别生成针对7位字符的彩虹表，复杂度从  骤降至 。
 无盐值：LM Hash 不使用盐，这意味着通用的彩虹表可以直接用于攻击任何使用该系统的计算机。

随着现代操作系统广泛采用加盐的哈希算法（如NTLMv2、SHA-512），通用的预计算彩虹表已难以直接奏效。

 防御措施 
彩虹表攻击极其有效，但可以通过特定的密码学实践进行防御。

 加盐（Salting）
加盐是防御彩虹表最有效的方法。
 原理：在对密码进行哈希之前，系统会生成一个随机字符串（盐），将其拼接到密码上：。
 效果：彩虹表是针对特定哈希函数预先计算的。如果加入了盐，相当于修改了哈希函数。攻击者必须为每一个可能的盐值重新计算一整套彩虹表。如果盐足够长且随机（例如128位），预计算所有可能的彩虹表在计算上和存储上都是不可行的。

 密钥延伸（Key Stretching）
使用计算成本高昂的哈希算法，如PBKDF2、bcrypt、scrypt或Argon2。
 原理：这些算法通过成千上万次的迭代哈希运算，或者强制要求大量的内存访问，使得计算一次哈希值需要显著的时间（例如0.5秒）。
 效果：这使得生成彩虹表的成本呈指数级上升，同时也极大地拖慢了暴力破解的速度。

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

 参考资料 

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


Category:密码分析
Category:搜尋演算法
Category:密码散列函数