哈希上的多次迭代：这不会减少熵吗？

我看到在很多地方（包括堆栈）都推荐了这种技术，而且我无法摆脱这种技术会减少熵！毕竟，您正在再次对已经被散列过并且有碰撞机会的东西进行散列。碰撞机会大于碰撞机会会不会导致更多的碰撞机会？经过研究，似乎我错了，但为什么呢？

既然您标记了 md5，我将使用它作为示例。从维基百科 http://en.wikipedia.org/wiki/Md5#Collision_vulnerabilities:

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

然后他们给出的示例明文长度为 256 字节。第128章 128byte数据块，哈希摘要只有128bits，在第一次迭代之后，碰撞攻击成功的风险实际上并没有增加 - 也就是说，您无法真正影响在第一次哈希之后发生碰撞的可能性。

还要考虑哈希的熵是前面提到的 128 位。即使考虑到总碰撞几率仅为 2^20.96（再次来自维基百科 http://en.wikipedia.org/wiki/Comparison_of_cryptographic_hash_functions），需要大量迭代才能导致两个输入发生冲突。我认为您成为受害者的第一眼推理是：

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

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

• 两个输入发生冲突的几率是 1:2^21（从维基百科对 MD5 的密码学分析中获取最坏的情况）
• 再次哈希会导致同等概率的碰撞复合，因此第二轮碰撞的概率为 1:2^20
• 因此，对于任意两个输入，哈希次数等于摘要熵的次数一定会发生冲突。

MD5任意两个输入连续128次，你会发现这不是真的。您可能不会在它们之间找到单个重复的哈希值 - 毕竟，您只从可能的 2^128 个哈希值中创建了 256 个，还剩下 2^120 个可能性。每轮之间发生碰撞的概率为独立的 http://www.mathgoodies.com/lessons/vol6/independent_events.html所有其他回合。

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

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

我没有其他哈希算法的确切数字，但我认为我提出的所有观点都可以推广到其他哈希函数和单向/映射函数。