彩虹表

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

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

Simplified rainbow table with 3 reduction functions

背景

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

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

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

由于存在更为简单的逆向散列运算（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比特长，那么他们形成的长链可以表示作：

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

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

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

例如，如果给定的哈希值为920ECF10，我们首先施加函数R：

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

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

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

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


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

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

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


彩虹表

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

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

参考资料
  1. Hellman, M. . 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.

常见用途

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

参见
  • Oechslin, Philippe. (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）.

外部链接
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.