彩虹表

彩虹表(Rainbow table)是用于加密散列函数逆运算的预先计算好的表，常用于破解加密过的密码散列。彩虹表常常用于破解长度固定且包含的字符范围固定的密码（如信用卡、数字等）。这是以空间换时间的典型实践，比暴力破解（Brute-force attack）用的时间少，空间更多；但与储存密码空间中的每一个密码及其对应的哈希值（Hash）实现的查找表相比，其花费的时间更多，空间更少。使用加盐的密钥派生函数可以使这种攻击难以实现。

彩虹表是马丁·赫尔曼早期提出的简单算法^[1]的应用。

背景[编辑]

每台需要密码认证的电脑都包含一个储存密码的数据库，密码储存方式有多种，如摘要或纯文本。由于储存密码的表很容易被窃取，所以以纯文本形式储存密码非常危险，大多数数据库会储存用户密码的加密摘要。在这种系统内，即使是认证系统本身都无法简单地通过查表来获得用户密码。当用户输入密码时，系统会生成一个加密摘要与储存的加密摘要比较，如果相同就允许访问请求。

骇客在盗取到散列后的密码表时，并不能仅凭借输入散列后的用户的加密摘要来获取权限（使用加密摘要作为输入密码并不可行，因为认证系统会把加密摘要再次加密，产生一个与储存的加密摘要不匹配的摘要）。为了获取用户的密码，骇客必须找到一个能产生相同加密摘要的密码。

彩虹表是仅通过加密摘要来尝试获取用户密码的工具之一。

由于有更简单的逆向散列运算（hash reversal）方法，彩虹表不一定会用到。相比之下，暴力破解法和字典攻击是更简单的破解方法。但这些方法在面对存储了大量密码的系统时会非常乏力，因为储存用于逆向查找的所有选项以及搜索大型数据库十分困难。

若要破解大型的密码库，则需要引入储存相对较少，但可以逆向形成由长链密码的散列值构成的逆向查找表。虽然破解单个的密码时会花费更多的计算时间，但这会大大降低整体的字典大小，因而可以储存更长的密码散列值。彩虹表正是在此类链接技术的基础上改进得到的一种支持碰撞链的密码破解工具。

预先计算的散列链[编辑]

注：这里表达的散列链与哈希链中解释的是不同的散列链。

假设有哈希方程H和有限的密码集合P，需要预先计算出一个数据结构来决定哈希方程H的任一输出结果h是否可以通过密码集合P里面的一个元素p经哈希函数H(p)=h得到。实现这一目的的最简单的方法是计算出P集合内所有密码p的哈希值H(p)。但是这个方法需要的储存空间为Θ(|P|n)，（n代表哈希函数H的一个输出值的大小）对于较大的|P|，其对于存储空间的要求会过高。

哈希链可以用来减少对于储存空间的需求。大致想法是通过定义一个归约函数（reduction function）R来映射散列值h在集合P中对应的密码p。（注意，这里的归约函数并不是真正意义上哈希函数的反函数。)通过交替施行哈希函数与归约函数，形成交替的明文与哈希值。例如，假设P是6个字符的密码集合，而哈希值有32位元长，那么他们形成的长链可以表示作：

\mathbf {aaaaaa} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {281DAF40} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {sgfnyd} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {920ECF10} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt}

此处，对于归约函数的唯一要求是，它能将任意哈希值映射成特定字符的纯文本值。

为了生成查找表，可从集合P随机选一子集，对子集每个元素计算长度为k的哈希链，然后只保存每条哈希链的初始和末尾密码。初始密码称为起点，末尾密码称为终点。在上述哈希链的例子中，"aaaaaa"和"kiebgt"即为起点和终点，而哈希链中的其他密码或者哈希值均不会保存。^{[来源请求]}

现在计算给定哈希值h0的逆（即找到对应的密码），从哈希值h0开始轮流用函数R和H生成一条哈希链。如果哈希链任何节点与查找表的某个终点发生碰撞，就可以借由与之对应的起点，重建对应的哈希链。而这个哈希链很可能包含了需要搜寻的哈希值h0，如果这样的话，那么它的前驱节点即为要寻找的密码p0。^{[来源请求]}

例如哈希值920ECF10，首先施加函数R：

\mathrm {920ECF10} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt}

"kiebgt"在建立的查找表的终点集合中，所以借由对应的起始密码"aaaaaa"生成的哈希链，直到找到920ECF10：

\mathbf {aaaaaa} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {281DAF40} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {sgfnyd} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {920ECF10}

因此，哈希值"920ECF10"的前驱节点"sgfnyd"即为搜寻的目标密码。

注意，这里的哈希链并不一定会有要找的哈希值h；可能以h开始的链会和起点在h链之后的某个查找链重合。例如，在以下情况，可以从FB107E70的哈希链中找到kiebgt：

\mathrm {FB107E70} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {bvtdll} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {0EE80890} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt}

但FB107E70并不在以"aaaaaa"开头的链中。这情况称为误报（false alarm）。在这例子可忽略这个匹配然后继续扩增h链同时寻找下个匹配。如果h的哈希链在扩增到长度为k后仍然没有发生匹配，那么与之对应的密码一定不在查找表的任何哈希链中。

查找表的内容并不依赖于查询的哈希值。它是在一次性建立之后，被无修改的重复用于查找。增加链的长度可以减小表的规模，但同时也会增加查询时间，这就是彩虹表空间换时间的折中策略。在单元链的最简单情况下，查询速度会非常快，但表也会非常大。一旦链变得更长，查找速度也会降下来，但表的规模变得更小了。

简单的哈希链方法有很多缺陷。最严重的问题是，如果两条链中的任何两个点碰撞（有同样的值）了，他们后续的所有点都将重合，这将导致在付出了同样的计算代价之后并不能使表尽可能多的覆盖到密码。由于链的前部并没有整个的保存，这使得碰撞不可能有效检测到。例如，如果链3的第三个值和链7的第二个值重合了，那么这两条链将覆盖几乎同样的值，但他们的终点值却不相同。哈希函数H本身不大可能产生碰撞，因为这就是它最重要的安全特性之一。但对于衰减函数R来说，由于他需要正确的覆盖掉可能的明文（即之前讨论的密码），所以不会是抗碰撞的。

其他的困难是由选择正确R函数的重要性导致的。选择恒等映射作为函数R要比暴力搜索好一点。只有当攻击者明确知道明文的可能取值是什么时，他/她才需要选择一个好的R函数使得时间和空间花费在这些可能的明文上，而不是整个可能的密文空间。尽管把R的取值限定到可能的明文空间能带来好处，但它的弊端是攻击者选择的用于生成哈希链的明文子集可能并不能覆盖所有的可能明文空间。设计一个能匹配明文期望分布的R函数也非常困难。

彩虹表[编辑]

为了解决简单的哈希链中的碰撞问题，彩虹表选用一系列相关的归约函数R₁，…，R_k来代替原先的归约函数R。这样，如果两条哈希链发生碰撞并且重合，那么它们的碰撞必定发生在相同的位置，从而它们的终点也将相同。这样可以通过后处理来排序哈希链，从而找出并移除所有终点相同，因而可能是重复的链，并生成新的链来将整个表补充完整。这样得到的表中的链可能有碰撞的部分，但它们不会发生链的重合，从而大幅降低了碰撞的次数。^{[来源请求]}

采用归约函数列代替归约函数将改变查找的方式。因为给定的哈希值可能出现在哈希链任意位置，需要计算k条不同的链：首先假定给定的哈希值出现在哈希链最后一位（此时只需施加函数R_k），然后假定哈希值出现在哈希链尾二位（此时依次施加函数R_k-1，H和R_k），依此类推，直至找到所需密码。注意，如果错误假定了目标哈希值在哈希链的位置，可能会得到一条与表中的链部分重合的链，从而产生误报。

常见用途[编辑]

几乎所有Unix，Linux和BSD的发行版和变体都使用哈希值，尽管许多应用程式只使用没有盐的哈希（通常是MD5）。Microsoft Windows NT / 2000系列使用LAN Manager和NT LAN Manager散列方法（基于MD4）并且也是无保留的，这使其成为常用的生成表。

参考资料[编辑]

^ Hellman, M. A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory (Institute of Electrical and Electronics Engineers (IEEE)). 1980, 26 (4): 401–406. ISSN 0018-9448. doi:10.1109/tit.1980.1056220.

参考书籍[编辑]

Oechslin, Philippe. Making a Faster Cryptanalytical Time-Memory Trade-Off (PDF). Advances in Cryptology: Proceedings of CRYPTO 2003, 23rd Annual International Cryptology Conference. Lecture Notes in Computer Science (Santa Barbara, California, USA: Springer). 2003-08-17 [2014-09-27]. ISBN 3-540-40674-3. （原始内容 (PDF)存档于2007-09-26）.

外部链接[编辑]

Ophcrack page by Philippe Oechslin The original rainbow table research
开放式目录计划中和Cryptography相关的内容

[Hellman_1980_pp._401–406-1] Hellman, M. A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory (Institute of Electrical and Electronics Engineers (IEEE)). 1980, 26 (4): 401–406. ISSN 0018-9448. doi:10.1109/tit.1980.1056220.

[1]