security - 为什么叫彩虹桌？

Question

谁知道为什么叫彩虹桌？刚刚记得我们已经了解到有一种攻击称为“字典攻击”。为什么不叫字典？

Answer 1

因为它包含了可能性的全部“范围”。

字典攻击是一种尝试可能性的蛮力技术。像这样（python伪代码）

mypassworddict = dict()

for password in mypassworddict:
    trypassword(password)

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

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

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

彩虹表是对给定箱的所有可能性的计算，即对于每个箱，该箱的所有可能倒数......这就是它最终如此之大的原因。如果第一个 bin 值是，0x1那么您需要bin2通过哈希反向查找 bin3 的所有值和所有值的查找列表，最终为您提供一个值。

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

正如我已经看到您之前的问题一样，让我详细介绍您在那里寻找的细节。理想情况下，加密安全哈希需要从较小的输入大小到整个文件都是安全的。预先计算整个文件的哈希值需要很长时间。因此，彩虹表是在一小部分易于理解的输出子集上设计的，例如所有字符 az 在一个 10 个字符的字段上的排列。

这就是为什么用于击败字典攻击的密码建议在这里起作用的原因。您为哈希输入的整个可能输入集的子集越多，彩虹表需要包含的搜索就越多。所需的数据量最终会变得非常大，搜索时间也是如此。所以，想一想：

• 如果您有一个[a-z]用于5-8字符的输入，那么彩虹表还不错。
• 如果将长度增加到 42 个字符，那就是一个巨大的彩虹表。每个输入都会影响哈希，因此影响所述哈希的 bin。
• 如果您将数字输入到您的搜索要求中，您将需要[a-z][0-9]进行更多搜索。
• 同样[A-Za-z0-9]。最后，[\w]插入任何你能想到的可打印字符，再一次，你看到的是一张巨大的桌子。

因此，使密码变得又长又复杂，使得彩虹表开始获取蓝光大小的数据光盘。然后，根据您之前的问题，您开始添加加盐和哈希派生函数，并为哈希破解困难（呃）制定通用解决方案。

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

Answer 2

Rainbow 是字典攻击的一种变体（准确地说是预计算字典攻击），但它比完整字典占用更少的空间（以在表中查找键所需的时间为代价）。这种空间-内存权衡的另一端是完全搜索（蛮力攻击 = 零预计算，很多时间）。

在彩虹表中，预先计算的密钥-密文对字典被压缩成链。链中的每一步都是使用不同的压缩功能完成的。而且桌子上有很多链子，所以看起来像彩虹。

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

Answer 3

我不知道这个名字来自哪里，但区别是：

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

Answer 4

不幸的是，有些陈述是不正确的。与所发布的彩虹表相反，它不包含给定键空间的所有可能性，而不是我见过的为使用而生成的可能性。它们可以生成以覆盖 99.9，但由于散列函数的随机性，无法保证每个明文都被覆盖。

每个链都由链接或步骤组成，每个步骤都由散列和归约函数组成。如果您的链有 100 个链接长，那么您将使用该数量的哈希/归约函数，然后丢弃除开始和结束之外的所有内容。

要找到给定散列的原始值，您只需执行链长度的缩减/散列 x 量。因此，您运行该步骤一次并检查端点是否会重复...直到您遍历整个链条长度。如果有匹配项，您可以从起点重新生成链，您可能会找到平原。如果在再生之后它不正确，那么这是一个误报。这是由于归约散列函数引起的冲突。由于该表包含许多链，因此您可以在每一步对所有链端点进行大量查找，这基本上是魔术发生的地方，允许速度。这也会导致误报，因为您只需要重新生成匹配的链，您可以通过跳过不必要的链来节省大量时间。

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

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