彩虹表如何用于字典攻击？

#1 楼

我一直在努力寻找合适的彩虹桌说明，因此首先我将介绍它们的含义。最后我会回答你的问题。我的资料来源是本指南和Wikipedia文章。

为什么我不能只使用一大堆哈希？

首先是天真的方法来建立反向查找桌子是这个。假设我们要使用设置[A-Za-z0-9]为每个现有的8位密码生成所有哈希。在这种情况下，有62个唯一字符，使用计数函数$ n ^ r $，其中$ n $是可能的输出数量，而$ r $是我们可以选择的数量，那么就有$ 218340105584896 $此输出空间中的字符串。幼稚地存储此数据，我们可以采用8个字符串，因为每个字符需要8位（因此每个字符串需要64位），加上分隔符再加上256位输出（例如sha256），则总成本为$ 218340105584896（64 + 1 + 256）= 70087173892751616 $位。将其转换为字节，即$ \ frac {70087173892751616} {8 *（1024）^ 3} \ approx 8159220 $ GB。

对此有两个注意事项：


它只考虑8个字符的密码。如果要考虑包含4-8个条目的密码，则需要$ 62 ^ 4 + 62 ^ 5 + 62 ^ 6 + 62 ^ 7 + 62 ^ 8 $。
假定您实际上要存储该数据。以原始形式。解决这个问题的方法可能更好。

所以第一个问题是存储。上面，我们仅计算了哈希函数的总输出空间。

什么是彩虹桌子？

彩虹桌子背后的想法是抵消空间问题。为此，让我们定义一些事情：首先，我们有一个搜索域，我们将其称为$ \ mathbb {P} $，一个哈希输出域，我们将其称为$ \ mathbb {H} $。然后我们有一个要反转的哈希，我们将其定义为$ \ mathcal {H}：\ mathbb {P} \ rightarrow \ mathbb {H} $。即哈希函数采用搜索域的元素，并在哈希输出域中产生一个值。

然后，我们介绍一个称为链接的概念。为此，请考虑我们可以定义一个相当简单地映射其他方式的函数。我们称它为$ \ mathcal {R}：\ mathbb {H} \ rightarrow \ mathbb {P} $。在彩虹表中，一条链以一个起始值开始，并依次应用$ \ mathcal {H} $和$ \ mathcal {R} $，但始终成对使用，这样一来，您最终得到第一个和最后一个元素$ p_0，p_k \ in \ mathbb {P} $。这是您存储的内容。

彩虹表要比每对使用相同的$ \ mathcal {R} $稍微复杂一些；这存在与碰撞有关的问题。如果两个链产生的值相同，那么它们会聚，这意味着我们浪费时间在计算所述链上–这是链冲突。我很难想象这一点，因此绘制了一个图表：

a_1 ----> a_2 ----> a_3 / b_2 --> a_4 / b_3 --> a_5 / b_4 ---> a_6 / b_5
                        |                                         |
b_1 ---------------------                                         -----> b_6.

相反，一组函数$ \ {\ mathcal {R} _0，\ ldots，\ mathcal {应用R} _ {k-1} \} $，每对链一对。因此，当链条使用此设置合并时，它们始终会产生相同的最终值，然后可以进行重复数据删除，从而节省空间-在生成时也更容易检测到浪费的空间。

然后：



生成Rainbow表：选择长度$ k $并定义函数$ \ mathcal {R} _ {0}，\ ldots，\ mathcal {R} _ {k- 1} $。然后，对于给定的输入$ p \ in \ mathbb {P} $，我们计算$ c_0 = p，c_ {n + 1} = \ mathcal {R} _ {n-1}（r_ {n}），r_ { n} = \ mathcal {H}（c_ {n}）\; \;（n = 0,1,2，\ ldots，k）$。这些$ c $构成了一个链$ C $。我们计算链，并为每个链仅存储对$（c_0，c_k）$。

搜索彩虹表。现在，假设我们要反转哈希值$ h $。为此，我们执行此过程，从$ i = k-1 $开始：

从$ R_ {i} $
开始为$ h $生成链使用上述链的最终值，在我们的最终值列表中搜索计算出的链。如果找到匹配的最终值，则一次计算其链项（我们可以这样做，因为我们知道起始值）。如果我们在该链中找到$ h $，例如$ r_n $，则对应的$ c_n $值就是$ h $的倒数。停止。如果我们在链表中找不到最终值，请继续。如果在生成的链中没有找到我们找到链值的哈希，请继续操作。
如果$ i \ neq 0 $做$ i = i-1 $，然后返回1。
如果到达这里，我们还没有找到相反的东西。



对，那么到底有什么好处呢？

这是一个空间/时间权衡。具体而言，反向查找表占用大量空间。这种方案占用的空间更少，但是每次查找需要更多的时间才能工作。由于完整的反向表的大小对于大多数人来说是令人望而却步的，因此通常最好增加计算成本。存储空间已大大减少，但实际上却很难计算，因为它取决于$ k $和您使用的$ \ mathcal {R} $。

很显然，rainbow有多种选择表的长度为$ k $。 $ k $越长，覆盖$ \ mathbb {P} $中的所有元素之前的总链数就越少。但是，这也增加了查找的运行时间。

哦，不，现在我不知道盐如何加入其中？！

盐会增加$ \的大小mathbb {P} $通过增加$ n ^ r $中的$ r $来实现。这不仅使反向哈希列表从天文角度上来说非常大，而且还增加了彩虹表所需的大小和计算时间。

攻击者然后有两个选择：


产生给定盐的彩虹表，使其对于另一种盐无效。
产生巨大的彩虹表。

慢速哈希函数又如何呢？

到目前为止，我们主要是将空间作为考虑因素，而不考虑查找功能所花费的时间。大多数密码散列的设计速度都相当快，因此对于说MD5来说，这最终是可行的。

现在，如果我们选择$ \ mathcal {H} $会发生大约一秒钟的时间，那会发生什么计算每个哈希？假设没有捷径可以消除这笔额外的时间成本，那么巨大的反向表将花费$ 218340105584896 $秒，或大约$ 6923519 $年。您的彩虹表也将花费很长时间生成-假设您永远不会发生冲突并覆盖整个域，只要进行哈希反向查找，再加上要增加的搜索成本，这取决于$ k $的长度。

将两者结合在一起可有效抵御彩虹表，使其既针对特定的盐，又因生成和使用昂贵。

为什么密码策略会提及诸如此类的内容字符类，例如必须具有大写字母，必须具有标点符号吗？

我们将$ \ mathbb {P} $定义为集合[A-Za-z0-9]。如果将标点符号添加到混合中，则会再次增加$ \ mathbb {P} $的大小，因此再次增加Rainbow表的大小（所需的链数）。密码长度要求也可以做到这一点。

那么词典呢？

相当著名的XKCD漫画背后的整个前提是信息熵。粗鲁地讲一个有趣的科学领域（对不起！），基本上，您说的是，尽管$ \ mathbb {P} $的总排列很大，但实际上，其中很多对人类完全没有意义，我们会不能选择使用它们。那个XKCD漫画说的是，实际上，如果您对密码的可能格式做出某些判断，则使用信息熵来衡量这些格式中的不确定性，那么较长的密码短语实际上比较短的复杂密码得分更高。

没有理由不能使用考虑了这种假设的一组归约函数来生成Rainbow表。

字典只是这种猜测的简化版本-也就是说，您假设要反转的东西实际上是已知的字典单词。您还可以生成具有已知字典密码短语的彩虹表。

在两种情况下，您都减少了$ \ mathbb {P} $，从而减少了彩虹表的大小和执行时间查找；但是，这种技术容易受到以下事实的影响：您的密码近似表示可能不正确。

彩虹表的复杂性是什么？

假设我们要构建一个彩虹表来覆盖一组$ N $潜在密码。 （换句话说，$ N = | \ mathbb {P} | $。）令$ t $表示平均链长；这是一个您可以自由选择的参数，以优化攻击成本。

然后，构建表的成本约为$ 1.7N $哈希计算（是的，它要贵70％而不是对集合进行简单的详尽搜索）。存储成本为$ N / t $个元素，大小至少为$ \ lg N $（但不一定更大）。攻击密码大约需要$ t ^ 2/2 $哈希计算和$ t $查找（“查找”是指您实际上在硬盘上查找数据时；通常比哈希计算要慢得多）。 br />

#2 楼

Rainbow表只是预先计算的哈希值表的一个被大肆宣传的名称，带有一些技巧，可以在较小的存储空间（例如，太字节）中处理huuuuge表。

预计算表，包括Rainbow表，被盐腌彻底打败了。假设您使用了正确的密码哈希处理，其中包括一个盐，并且可以配置为适当的慢速（提示：它称为bcrypt），剩下的一个弱点是攻击者“尝试”密码来攻击单个哈希密码（假设他得到了它的副本）。盐可以防止小人并行攻击多个密码；他必须为尝试攻击的每个哈希密码付出全部代价，尝试使用潜在的密码。此外，可配置的缓慢性可能会使每次尝试对于攻击者来说都是任意昂贵的（这是有代价的：它对您来说也很昂贵；因此是“可配置”的部分：您将其变得尽可能昂贵，在上下文中仍然可以容忍）。 br />
现在，如果您仍然使用现有软件，则上面的某些建议可能不适用。请记住，密码哈希是第二道防线：攻击者不应访问哈希密码；密码散列可以防止确实获得未经授权的读取访问权限的攻击者将其攻击升级为用户模拟和相关的写访问权限。


“密码策略”的主要问题在于它们就像放牧猫（猫是用户的隐喻）。用户是人类，因此他们很容易选择密码，因为他们无法随机选择。这与成为人类是相当重要的。通过执行策略，您正在尝试消除某些极端糟糕的随机性情况，人类可以用惊人的创造力来发明这种情况。我认为，更好的“策略”将是提供一种工具，该工具可以创建统一的随机密码，以便用户可以运行它并获得“强密码”。一种方案如下所示：密码包含两个小写字母，然后是两个数字，然后是两个小写字母，然后是两个数字。仅8个字符，相当容易记住，但熵却超过32位。如果您还具有适当的哈希过程（如上所述），则32位熵足以阻止攻击者（bcrypt！）。

#3 楼

彩虹表可以与字典中的单词一起使用，而不能与字符集中的字母一起使用。

ophcrack vista liveCD是一个示例。中包含两个字典，并尝试单词和修饰词的组合。例如，主词典包含“ house”和“ boat”，第二词典包含“ 2010”，“ 2011”和“ january”。然后，它将创建类似boat2010或BOAT2010或h0us3january的密码。

您只需要创建一个归约函数即可从字典中选择单词，并从一组修饰中选择修饰。假设您有2 ^ 15个单词的字典（包括一个空单词），并且您希望创建最多三个单词的组合。要将哈希值减少为密码，您可以
-使用哈希值的前15位从字典中选择第一个单词
-使用哈希值的后15位以从字典中选择第二个单词字典
-将最后一个单词的前15个位用作第三位
，然后您可以使用哈希的其他位来选择一些修改（例如大写，向后写单词，保持沉默）。

#4 楼

ninefingers很好地回答了这个问题，但是这个问题暴露了Mitchell的根本困惑。

NT哈希没有加盐，并且是密码等效的。不需要使用哈希来获取密码，只需使用哈希来访问资源！

其次，密码必须大于14个字符，以避免LM哈希，请参阅MS KB299656。您可以通过本地安全策略或GPO杀死LM哈希。

最后，攻击者获取哈希的用例意味着您已经拥有了。由于MS对CredSSP的选择不多，因此可以从RAM提取密码本身，其访问级别与从RAM提取哈希值的访问级别相同。米米卡兹此访问级别（如果拥有）。永远不会以一种微弱的方式提供哈希，除非通过请求可以通过Reg密钥打败哈希哈希攻击；请参阅本文。

#5 楼

据我所知，NTLM v2使用带有用户密码的MD5 HMAC作为密钥，以及用户名和域的MD4哈希。

MD5本身作为哈希不是很安全（可以轻松找到冲突），但是对于像这样的应用程序，它仍然保留了一些价值，因为众所周知的原像攻击大约有$ 2 ^ {123} $的复杂度（因此几乎是$ 2 ^ {128} $的全部）。

但是，Microsoft自己建议不要在应用程序中使用它（来源：实施者的安全注意事项）。

就是说，即使不加盐，也有$ 26 ^ {14} $的不同小写的14个字符的密码。 MD5哈希具有16字节输出，因此完整的Rainbow表将容纳$$ 26 ^ {14} \ cdot 16 \字节\大约2 ^ {69.8} \字节= 2 ^ {29.8} \ Tebibytes \大约900 \百万Tebibytes。$$

但是，如果您要求用户使用短语，请记住英语中只有那么多单词。假设其中有$ 10,000 $可能会被使用（可能更少）。大约两个字可容纳14个字符。这可能只是$ 100,000,000 $的密码。

如果知道HMAC和用户名（或哈希和盐），则将通过简单的蛮力攻击来揭示该密码。