什么是彩虹桌，如何使用？

#1 楼

Rainbow Table通常与另一种更简单的技术（在哈希密码恢复中利用计算时间存储权衡）相混淆：哈希表。哈希表是通过对密码字典中的每个单词进行哈希处理来构造的。密码哈希对存储在一个表中，按哈希值排序。要使用哈希表，只需进行哈希处理，然后在表中执行二进制搜索以找到原始密码（如果存在）。

彩虹表更为复杂。构造Rainbow表需要两件事：哈希函数和归约函数。给定彩虹表集的哈希函数必须与您要恢复的哈希密码匹配。约简功能必须将哈希转换为可用作密码的内容。一个简单的归约函数是对Base64进行编码，然后将其截断为一定数量的字符。彩虹表由一定长度的“链”构成：例如100,000。要构建链，请选择一个随机种子值。然后将散列和归约函数应用于此种子及其输出，并继续迭代100,000次。仅存储种子和最终值。重复此过程以创建所需的任意数目的链。保留。将链中的每个链接与每个链的最终值进行比较。如果存在匹配项，则可以重新构建链，同时保留每个哈希函数的输出和每个归约函数的输出。重建的链将包含所讨论密码的哈希值以及产生该密码的密码。

哈希表的优势在于恢复密码的速度非常快（二进制搜索），并且构建哈希表的人可以选择要输入的内容，例如前10,000个密码。与Rainbow Tables相比，缺点是哈希表必须存储每个单独的哈希密码对。在每个链中。种子和最终值之间的链接越多，捕获的密码越多。一个弱点是，构建链的人不会选择他们捕获的密码，因此Rainbow Tables无法针对常见密码进行优化。同样，密码恢复涉及计算哈希的长链，使恢复成为昂贵的操作。链条越长，捕获的密码就越多，但是在其中查找密码需要更多的时间。最好的方法是使用哈希表和/或使用前N个密码的字典进行的常规破解来恢复尽可能多的密码。对于剩下的那些，请使用Rainbow Tables。

#2 楼

关于什么是彩虹表，有很多很好的解释，这一表特别好。 Wikipedia文章也有很好的解释。
更深入地阅读有关该主题的权威论文是“更快地进行密码分析时间记忆权衡”。

Rainbow Tables的简单解释是它们利用了时间记忆权衡技术。意思是，您无需预先哈希目标值和单词词典，然后哈希每个单词并即时进行比较（使用John之类的强力方法），而是预先哈希字典中的所有值（这可能需要一个时间长短取决于字典大小）。但是一旦完成，您就可以将所需的散列与彩虹表中的预散列值进行比较，这比再次计算散列要快得多。

我之前在这里写的解释旨在简短是一种误导，因为它没有解释彩虹表利用的减少量的用法。要获得更好的解释，直到我重写此位，请参见@Crunge答案。项目网站，Ophcrack项目以及许多其他地方，具体取决于您需要使用哪种哈希表。

为了抵御基于Rainbow Table的攻击，最有效的应对方法是确保系统中的每个哈希值都固定。这使得预先生成的彩虹表变得无用，这意味着攻击者必须生成一组定制表才能用于目标散列，只有当他们知道盐分时才有可能。

#3 楼

目的和相关性

彩虹表有助于破解困难的密码，即在大型词典中甚至找不到的密码。密码历来以普通哈希存储在数据库中，这就是有效的Rainbow表的方法：创建一个Rainbow表（慢速）并针对它运行任意数量的带有哈希表的数据库（快速）。

如今，越来越多的系统使用适当的密码存储算法，例如Bcrypt，Scrypt或Argon2。请参阅：如何安全地[存储]密码？这些算法不再对彩虹表“易受攻击”：由于每个哈希都是唯一的，即使密码相同，彩虹表也不再起作用。即使不使用Argon2之类的现代工具，如今的开发人员通常也知道他们至少应该使用盐。这足以使彩虹表失效。链，每个长度为5。Rainbow表用于虚构的哈希函数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。现在，我们使用“减少”功能，该功能基本上将哈希值格式化为密码，最后得到“ 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

缩放属性

简而言之：


快速查找意味着更大的表，假设覆盖范围保持不变。 br />更好的覆盖率意味着查找速度较慢或表较大。
较小的表意味着查找速度较慢或覆盖率较低。并没有考虑到冲突。这些都是标准数字，仅作为示例，并非确切值。并且每条链的万次减少大约需要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次缩减才能到达链中的正确点。基本上，我们在查找时会执行与生成单个链时一样多的操作。因此，查找时间是一万次微秒，即十毫秒（如果可以的话，也可以是一毫秒）。

存储要求

完整，快速的哈希表（甚至是MD5）的查找表，您仍然需要1000亿兆兆字节的存储空间。那不是很有帮助。但是，如果我们只想覆盖小写密码直到10个字符怎么办？

如果我们要花费最多30秒的时间来查找哈希，并假设每个哈希+缩减周期需要1微秒（百万分之一秒），则链长为：1 million × 30 = 3000万。有2610个（或1014个）可能的10个字符的小写密码，并且每条链涵盖3000万个值。这给我们留下了400万个连锁店。我们知道每个链仅存储一个开始和结束值，并且每个值都是10个字符。因此2 × 10 × 4 million = 76 MiB数据。

通过迭代所有10个字符的密码来生成表需要很长时间：每个链30秒，乘以400万链约91年。但是，很多人会对这种表感兴趣，因此，通过合并1092个CPU（= 91×12），只需1个月。这表明可以将这样的表与其所覆盖的密码空间进行比较：查找仅需30秒，而您只需要存储76MiB数据。

结论

彩虹表可以认为是时间记忆的权衡：一个人仅存储表的一小部分，并通过对查找时间进行一些额外的计算来恢复它。这就是为什么盐，或者说像Scrypt或Argon2之类的良好密码存储算法对确保密码安全很重要的部分原因。如果彩虹表包含足够大的条目来容纳盐和密码，则彩虹表只能恢复已加盐的密码，这将非常低效，并且无法实现整个目的。

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

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