为什么叫做彩虹表？

Question

为什么叫做彩虹表？

securityrainbowtablerainbowattack

8

有人知道为什么它被称为彩虹表吗？只记得我们学过一种攻击叫做“字典攻击”。为什么不叫字典呢？

- user496949

1

如果你对加密货币感兴趣，我建议支持http://area51.stackexchange.com/proposals/15811/cryptography - user257111

FYI，您接受了一个无效的答案。请查看resonances的答案作为参考。此外，在原始论文中，它说：（http://lasec.epfl.ch/pub/lasec/doc/Oech03.pdf） 我们称之为彩虹链。他们为链中的每个点使用连续的减少函数。就是这样，他们称之为Rainbow表，因为他们在表的每一列上使用不同的减少函数。 - Alfonso Embid-Desmet

4个回答

6

彩虹表攻击是字典攻击的一种变体（准确来说是预先计算的字典攻击），但它所需的空间比完整字典小（代价是需要更多时间在表中查找密钥）。这个空间-内存权衡的另一端是完全搜索（暴力攻击=零预计算，需要很长时间）。

在彩虹表中，密钥-密文对的预计算字典被压缩成链。每个链中的每一步都使用不同的压缩函数。该表有许多链，因此看起来像一条彩虹。

在这张图片中，不同的压缩函数K1、K2、K3具有像彩虹一样的颜色：存储在文件中的表只包含第一列和最后一列，因为中间列可以重新计算。

- osgx

有趣。+1。我对事物的运作有一个高层次的理解；我认为我必须更详细地阅读它！ - user257111

@user496949，如果你需要额外的解释，只需问我。我阅读了几篇关于它的论文，并理解了彩虹表的原理。 - osgx

1

很不幸，有些陈述是不正确的。与发布的内容相反，彩虹表并不包含给定密钥空间的所有可能性，至少我见过的用于生成的表格不包含。它们可以生成以覆盖99.9％为目标，但由于哈希函数的随机性，不能保证每个明文都被覆盖。

每个链由链接或步骤组成，每个步骤由哈希和减少函数组成。如果您的链长度为100，则需要进行该数目的哈希/减少函数，然后丢弃中间的所有内容，仅保留起始和结束。

要找到给定哈希的明文，只需执行减法/哈希x您链的长度。因此，您运行一次步骤并检查终点是否错过，如果是，则重复...直到您穿过整个链的长度。如果有匹配，则可以从起始点重新生成链，然后可能可以找到平面。如果在再生后不正确，则这是虚警。这是由于减少散列函数引起的冲突。由于表格包含许多链，因此您可以针对每个步骤的所有链端点进行大型查找，这基本上是魔术发生的地方，允许加速。这也会导致虚警，因为您仅需要重新生成具有匹配项的链，通过跳过不必要的链，节省了大量时间。

它们不包含字典...好吧，传统表格没有变体的彩虹表使用字典。

就是这样。已经优化了许多此过程的方法，包括删除合并/重复链和创建完美表格，并将它们存储在不同的包装中以节省空间和加载时间。

- resonance

1

我不知道这个名称的来源，但它们之间的区别如下：

字典包含一些选定的项目（例如英语单词），而彩虹表则包含每个可能的组合。
字典仅包含输入，而彩虹表则包含输入和输出。
字典用于测试不同的输入以查看输出是否有效，而彩虹表用于反向查找，即查找哪个输入会产生特定的输出。

- Guffa

如果您不知道，可以尝试维基百科：http://en.wikipedia.org/wiki/Dictionary_attack，这是关于预先计算字典攻击的内容。 - osgx

并不完全正确，字典包含的项很少，而彩虹表包含所有组合。这完全取决于您将什么键值或彩虹链放入字典和彩虹表中。彩虹链只是更节省空间。 - kefeizhou

彩虹表也可以包含搜索空间的一部分，例如所有长度为 i 的字母数字或所有长度为 2i 的数字等。 - osgx

@osgx：我不明白你的意思。我查看了你提供的链接页面，但是没有找到关于这个名字的来源信息。 - Guffa

Guffa，可能会有一种字典的变体，它既有输入又有输出（预计算字典）。 - osgx

1

@osgx：这一点并没有让事情变得更加清晰。你的意思是什么？你链接的页面上有任何与名称来源有关的内容吗？ - Guffa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user257111 · Accepted Answer

因为它包含了所有可能性的“光谱”。

字典攻击是一种暴力破解技术，只是尝试各种可能性。就像这样（Python伪代码）

mypassworddict = dict()

for password in mypassworddict:
    trypassword(password)

然而，彩虹表的工作方式不同，因为它是用于反向哈希。哈希的高级概述是它具有许多 bin：

bin1, bin2, bin3, bin4, bin5, ...

它们对应于输出字符串的二进制部分 - 这就是字符串最终长度的原因。随着哈希的进行，它以不同的方式影响不同部分的容器。因此，第一个字节（或接受的任何输入字段）影响（比如说，简单地说）容器3和4。下一个输入会影响2和6。依此类推。

彩虹表是给定二进制数的所有可能性的计算，即每个容器的所有可能逆转，对于每个容器……这就是为什么它最终变得如此庞大。如果第一个容器值为0x1，则需要拥有所有bin2的值和所有bin3的值的查找列表，通过哈希向后工作，最终给出一个值。

为什么它不被称为字典攻击？因为它不是。

正如我看过你之前的问题一样，让我扩展一下你正在寻找的细节。加密安全哈希需要在理想情况下从小输入大小到整个文件都是安全的。要预先计算整个文件的哈希值将永远需要很长时间。因此，彩虹表是设计在一个小而且易于理解的输出子集上的，例如a-z上所有字符的置换超过10个字符的字段。

这就是为什么打败字典攻击的密码建议在这里起作用。您将更多的整个可能输入集合子集放入哈希的输入中，彩虹表需要包含更多内容来搜索它。所需的数据大小变得非常大，搜索时间也很长。所以，请考虑一下：

- 如果您的输入是5-8个字符的[a-z]，那不算太糟糕的彩虹表。 - 如果您将长度增加到42个字符，那就是一个巨大的彩虹表。每个输入都会影响哈希和其容器。 - 如果你在你的搜索要求中加入数字[a-z][0-9]，你需要进行更多的搜索。 - 同样地，[A-Za-z0-9]。最后，加入[\w]，即任何您可以想到的可打印字符，再次，您正在查看一个巨大的表格。

因此，使密码变得又长又复杂会使彩虹表开始采取蓝光大小的数据。然后，根据您之前的问题，您开始添加盐和哈希派生函数，并使哈希破解的一般解决方案变得更加困难。

这里的目标是保持领先于可用的计算能力。