彩虹表通常与另一种更简单的技术混淆，该技术利用密码恢复中的计算时间存储权衡：哈希表。

哈希表是通过对密码字典中的每个单词进行哈希处理来构建的。密码哈希对存储在一个表中，按哈希值排序。要使用哈希表，只需获取哈希并在表中执行二进制搜索以找到原始密码（如果存在）。

彩虹表更复杂。构建彩虹表需要两件事：散列函数和归约函数。给定彩虹表集的散列函数必须与您要恢复的散列密码匹配。归约函数必须将散列转换为可用作密码的东西。一个简单的归约函数是对哈希进行 Base64 编码，然后将其截断为一定数量的字符。

彩虹表由一定长度的“链”构成：例如 100,000。要构建链，请选择一个随机种子值。然后对这个种子及其输出应用散列和归约函数，并继续迭代 100,000 次。仅存储种子和最终值。重复此过程以创建所需数量的链。

要使用 Rainbow Tables 恢复密码，密码哈希经过上述过程的长度相同：在本例中为 100,000，但链中的每个链接都被保留。将链中的每个环节与每个链的最终值进行比较。如果匹配，则可以重建链，同时保留每个散列函数的输出和每个归约函数的输出。该重建的链将包含相关密码的哈希值以及产生它的密码。

哈希表的优势在于恢复密码的速度非常快（二进制搜索），构建哈希表的人可以选择其中的内容，例如前 10,000 个密码。与 Rainbow Tables 相比的弱点是哈希表必须存储每一个哈希密码对。

彩虹表的好处是，构建这些表的人可以通过选择每个链中的链接数量来选择需要多少存储空间。种子和最终值之间的链接越多，捕获的密码就越多。一个弱点是构建链的人不会选择他们捕获的密码，因此 Rainbow Tables 无法针对常见密码进行优化。此外，密码恢复涉及计算长链哈希，使恢复成为一项昂贵的操作。链越长，其中捕获的密码就越多，但在其中找到密码需要更多时间。

哈希表适用于普通密码，彩虹表适用于强密码。最好的方法是使用哈希表和/或使用前 N 个密码的字典进行常规破解来恢复尽可能多的密码。对于那些剩下的，使用彩虹表。

彩虹表是什么有很多很好的解释，这一篇彩虹表的工作原理特别好。维基百科的文章也有很好的解释。如需更深入地阅读有关该主题的权威论文，请参阅《做出更快的密码分析时间-记忆权衡》。

彩虹表的一个简单解释是它们使用了时间记忆权衡技术。意思不是获取目标散列值和单词字典，然后散列每个单词并动态进行比较（使用类似John的蛮力方法），而是提前散列字典中的所有值（这可能需要很长的时间取决于字典的大小）。但是一旦完成，您可以将任意数量的哈希值与彩虹表中的预哈希值进行比较，这比再次计算哈希值要快得多。

我之前为了简短而写在这里的解释具有误导性，因为它没有解释彩虹表使用的减少的使用。要获得更好的解释，直到我重写这一点，请参阅@Crunge 答案。

您可以使用RainbowCrack 之类的应用程序自己生成彩虹表，也可以从The Shmoo Group、Free Rainbow Tables项目网站、Ophcrack项目和许多其他地方下载它们，具体取决于您需要表的哈希类型。

为了防止基于 Rainbow Table 的攻击，最有效的对抗方法是确保系统中的每个散列都是加盐的。这使得预先生成的彩虹表毫无用处，并且意味着攻击者必须生成一组自定义表来针对目标哈希使用，这只有在他们知道盐的情况下才有可能。

目的和相关性

彩虹表有助于破解困难的密码，即那些甚至无法在大字典中找到的密码。密码在历史上被存储为数据库中的普通哈希，这就是彩虹表有效的方法：创建一个彩虹表（慢）并针对它运行任意数量的充满哈希的数据库（快速）。

如今，越来越多的系统使用适当的密码存储算法，例如 Bcrypt、Scrypt 或 Argon2。请参阅：如何安全地 [存储] 密码？这些算法不再对彩虹表“脆弱”：因为每个哈希都是唯一的，即使密码相同，彩虹表也不再起作用。

这就是为什么彩虹桌今天不受欢迎的原因。即使不使用像 Argon2 这样的现代东西，现在的开发人员通常都知道他们至少应该使用盐。这已经足以使彩虹表无用了。

他们是如何工作的

创建表

假设我们创建了一个只有两条链的彩虹表，每条链的长度为 5。彩虹表用于虚构的散列函数 MD48，它输出 48 位（只有 12 个十六进制字符）。在构建链时，我们看到：

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj
Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD

我们开始是0因为它是第一个链（我们只需要一些价值开始）。当我们用 MD48 对它进行哈希处理时，它变成了cfcd208495d5. 现在我们应用一个“reduce”函数，它基本上将这个哈希格式化回密码，我们最终得到“z”。当我们再次对其进行哈希处理时，我们得到fbade9e36a3f，然后再次减少它并得到renjaj820。还有一些循环，最后的结果是WLgOSj。

第二条链也一样。我们只是从另一个值开始并做同样的事情。这以0uUoAD.

我们完整的彩虹表现在是这样的：

WLgOSj => 0
0uUoAD => 1

这就是你必须存储的所有内容。

查找哈希

假设我们在网上找到了一个哈希，7668b2810262. 让我们用我们的桌子破解它！

Looking for hash '7668b2810262', reduced to 'aL'.
hashed=>reduced 'aL' to ieioB
hashed=>reduced 'ieioB' to WLgOSj
Found a match, 'WLgOSj' is in our rainbow table:
    WLgOSj => 0
The chain starts with '0'. Let's walk that chain and look for the hash.
hashed '0' to cfcd208495d5
hashed 'z' to fbade9e36a3f
hashed 'renjaj820' to 7668b2810262
That hash matches! Found the password: renjaj820

为了自己动手，上面的例子是使用这个 Python 脚本创建的：https ://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

缩放属性

简而言之：

• 假设覆盖率保持不变，快速查找意味着更大的表。
• 更好的覆盖意味着更慢的查找或更大的表。
• 较小的表意味着更慢的查找或更差的覆盖率。

以下部分假设每次哈希+减少的时间为 1µs，并且未能考虑冲突。这些都是大致数字，仅作为示例而非确切值。

查找时间

如果哈希+归约操作需要一微秒，那么生成一个包含一百万条链和每条链 10000 条归约的表将需要大约 3 小时：
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 =2.8 小时。

在该表中进行查找平均需要 10 毫秒。chain_length/2这是因为在找到包含哈希的链之前，我们通常必须进行缩减。例如，在找到表中的值之前，我们可能需要对哈希进行 3000 次归约。接下来，我们必须从头开始重新执行该链，直到找到匹配的值。如果我们只需要执行 3000 次才能在表中找到它，那么我们必须从一开始就执行 7000 次减少才能到达链中的正确点。基本上，我们在查找时执行的操作与生成单个链时一样多。因此，查找时间是每微秒 10 000 次，也就是十毫秒（或者一厘秒，如果你愿意的话）。

存储要求

当您想为哈希函数（甚至 MD5）创建完整、快速的查找表时，您仍然需要 1000 亿 TB 的存储空间。这不是很有帮助。但是，如果我们只想覆盖 10 个字符之前的小写密码怎么办？

如果我们想花最多 30 秒的时间来寻找一个哈希，并假设我们每个哈希 + 减少周期需要 1 微秒（百万分之一秒），那么我们可以有一个链长：1 million × 30 =3000 万。有 26 ¹⁰（或 10 ¹⁴）可能的 10 个字符的小写密码，每个链我们覆盖 3000 万个值。这给我们留下了 400 万条链。我们知道每条链只存储一个开始和结束值，每个值都是 10 个字符。所以2 × 10 × 4 million =76 MiB 数据。

通过遍历所有 10 个字符的密码来生成表需要很长时间：每条链 30 秒，乘以 400 万条链大约需要 91 年。不过，很多人会对这样的表感兴趣，因此通过汇集 1092 个 CPU (=91×12)，只需 1 个月。这显示了这样一个表与它所覆盖的密码空间相比有多小：查找只需要 30 秒，而您只需要存储 76MiB 数据。

结论

彩虹表可以被认为是时间-内存权衡：一个只存储表的一小部分，并通过一些额外的查找时间计算来恢复它。这就是为什么盐，或者更确切地说，像 Scrypt 或 Argon2 这样的良好密码存储算法对于保证密码安全很重要的部分原因。彩虹表只有在表包含足够大的条目以包含盐和密码时才能恢复加盐密码，这将非常低效并且违背了整个目的。

请注意，类似的事情也适用于加密：当人们使用密码加密文件时，可以构建彩虹表来破解文件。假设该软件使用 AES，并且文件的第一个块应该使用用户提供的密码解密为“密码正确”，然后彩虹表将使用 AES 而不是散列函数。

每当您处理密码（强度未知的秘密，特别是如果用户可能重复使用它）时，请始终通过适当的（慢速）密码存储算法运行它，以使其缓慢且唯一可以破解。