既然您标记了 md5,我将使用它作为示例。来自维基百科:
如果可以构造具有相同散列的两个前缀,则可以向两者添加一个公共后缀,以使冲突更有可能被使用它的应用程序接受为有效数据。此外,当前的冲突查找技术允许指定任意前缀:攻击者可以创建两个以相同内容开头的冲突文件。攻击者生成两个冲突文件所需的只是一个包含 128 字节数据块的模板文件,在 64 字节边界上对齐,可以通过冲突查找算法自由更改该边界。两个消息相差 6 位的 MD5 冲突示例如下:
然后他们给出的示例明文长度为 256 字节。由于碰撞攻击依赖于 128字节的数据块,而哈希摘要只有 128位,因此在第一次迭代之后,碰撞攻击成功的风险实际上并没有增加 - 也就是说,您实际上不能影响第一个哈希之外的冲突的可能性。
还要考虑哈希的熵是前面提到的 128 位。即使考虑到总碰撞几率仅为 2^20.96(同样来自维基百科),也需要大量迭代才能导致两个输入发生碰撞。我认为您成为受害者的第一眼推理是:
这可以很容易地通过反例来反驳。再考虑MD5:
MD5 任意两个输入连续 128 次,你会发现这不是真的。您可能不会在它们之间找到单个重复的哈希值 - 毕竟,您只从可能的 2^128 个哈希值中创建了 256 个,还剩下 2^120 个可能性。每轮之间的碰撞概率独立于所有其他轮次。
有两种方法可以理解为什么会这样。首先,每次迭代本质上都是试图击中一个移动的目标。我认为您可以根据生日悖论构建一个证明,即散列迭代的次数出人意料地少,您可能会看到一个输入的一个散列摘要与另一个输入的散列摘要相匹配。但它们几乎肯定会发生在迭代的不同步骤。一旦发生这种情况,它们在同一迭代中永远不会有相同的输出,因为哈希算法本身是确定性的。
另一种方法是认识到哈希函数在运行时实际上会增加熵。考虑到空字符串与任何其他输入一样具有 128 位摘要;如果在算法步骤中不添加熵,这种情况就不可能发生。这实际上是加密哈希函数的必然部分:必须销毁数据,否则可以从摘要中恢复输入。对于比摘要更长的输入,是的,熵总体上丢失了;它必须是为了适合摘要长度。但也增加了一些熵。
我没有其他哈希算法的确切数字,但我认为我提出的所有观点都可以推广到其他哈希函数和单向/映射函数。