6

我看到在很多地方（包括堆栈）都推荐了这种技术，我不能忘记这会减少熵！毕竟，您正在再次散列一些已经被散列并且有碰撞机会的东西。碰撞机会超过碰撞机会不会导致更多的碰撞机会吗？经过研究，似乎我错了，但为什么呢？

4

2 回答 2

3

由于您标记了 md5，我将使用它作为示例。来自维基百科：

如果可以构造具有相同哈希的两个前缀，则可以向两者添加一个共同的后缀，以使使用它的应用程序更有可能将冲突作为有效数据接受。此外，当前的冲突查找技术允许指定任意前缀：攻击者可以创建两个以相同内容开头的冲突文件。攻击者生成两个冲突文件所需的只是一个模板文件，其中包含一个 128 字节的数据块，对齐在 64 字节的边界上，可以通过冲突查找算法自由更改。一个示例 MD5 冲突，两条消息的 6 位不同，是：

然后他们给出的示例明文长度为 256 个字节。由于碰撞攻击依赖于 128字节的数据块，而哈希摘要只有 128位，因此在第一次迭代之后，碰撞攻击成功的风险实际上并没有增加——也就是说，你真的不能影响超出第一个哈希的冲突的可能性。

还要考虑哈希的熵是前面提到的 128 位。即使考虑到总碰撞几率仅为 2^20.96（再次来自wikipedia），也需要大量迭代才能导致两个输入发生碰撞。我认为你成为受害者的第一眼推理是：

  • 任意两个任意输入都有 x% 的碰撞机会。
  • 第一个哈希的输出本身就是两个这样的输入。
  • 因此，每次迭代都会增加 x% 的碰撞机会。

这可以很容易地通过反例来反驳。再次考虑 MD5：

  • 两个输入发生冲突的几率是 1:2^21（取自维基百科对 MD5 的密码学分析的最坏情况）
  • 再次哈希会导致同样可能的碰撞机会复合，因此第二轮碰撞的机会是 1:2^20
  • 因此，对于任何两个输入的散列次数等于摘要的熵，都保证会发生冲突。

MD5 任意两个连续输入 128 次，你会发现这不是真的。您可能不会在它们之间找到一个重复的哈希值 - 毕竟，您只在可能的 2^128 个哈希值中创建了 256 个，剩下 2^120 个可能性。每轮之间的碰撞概率独立于所有其他轮。

有两种方法可以理解为什么会这样。首先是每次迭代本质上都是试图击中一个移动的目标。我认为您可以基于生日悖论构建一个证明，即散列迭代的次数非常少，您可能会看到来自一个输入的一个散列摘要与不同输入的散列摘要匹配。但它们几乎肯定会发生在迭代的不同步骤中。一旦发生这种情况，它们在同一次迭代中永远不会有相同的输出，因为哈希算法本身是确定性的。

另一种方法是意识到哈希函数在运行时实际上会增加熵。考虑一个空字符串有一个 128 位的摘要，就像任何其他输入一样；如果没有在算法步骤中添加熵，这是不可能发生的。这实际上是加密散列函数的必要部分：必须销毁数据，否则可以从摘要中恢复输入。对于比摘要更长的输入，是的，熵总体上会丢失；它必须是为了适合摘要长度。但也增加了一些熵。

对于其他散列算法，我没有准确的数字，但我认为我所做的所有要点都可以推广到其他散列函数和单向/映射函数。

于 2012-07-30T04:01:08.187 回答
1

它确实减少了熵。

在 Flajolet 和 Odlyzko 的一篇名为Random Mapping Statistics的论文中，一个定理（定理 2）表明：

“如果一个n位随机函数迭代k次，预期的图像点数为 ( 1 - t_k ) * 2^n (对于大n )，其中t_k满足递归关系t_0 = 0和t_{k+1 " _ _ _ _ _

进一步参考如下：

  • Gligoroski, D. 和 Klima, V.，2010 年 9 月。窄管散列设计偏离理想随机函数的实际后果。在 ICT 创新国际会议上（第 81-93 页）。施普林格柏林海德堡。

  • Bhaumik, R.、Dutta, A.、Guo, J.、Jean, J.、Mouha, N. 和 Nikolić, I.，2015 年。更多轮次，更少安全性？

  • Dinur, I. 和 Leurent, G.，2014 年 8 月。改进了针对基于哈希的 MAC 和 HAIFA 的通用攻击。在国际密码学会议上（第 149-168 页）。施普林格柏林海德堡。

从上一篇参考论文中，我们会发现以下两个引理： 关于熵损失的两个引理。因此，如果使用k个独立的随机函数，而不是使用一个迭代k次的随机函数，对熵损失的观察也成立。

于 2017-03-11T13:42:18.567 回答