math - md5 对短字符串（有限数量的字符串）有任何唯一性保证吗？

Question

所以我知道有证据表明 MD5 不能保证唯一性，因为宇宙中的字符串比 MD5 哈希字符串多，但是对于有限数量的字符串有任何逆向证明吗？

基本上，如果我有最大长度为 X 的字符串，是否有一个 X 保证 MD5 是唯一的？如果是，那么那个 X 是什么？如果 X 有多个值，那么 X 的最大值是多少？

或者对于任何其他散列算法、SHA-1 等是否有这样的 X？

Answer 1

在这里总结出色的答案：导致 MD5 冲突的最短字符串对是什么？

已知最短的 MD5 攻击需要 2 个输入块，即 128 字节或 1024 位。

sqrt(2^N)对于任何输出 N 位的哈希算法，假设它近似随机分布输入，您可以假设在大约输入中发生冲突的可能性超过 50% 。例如，MD5 散列到 128 位，因此您可以预期所有 64 位输入之间会发生冲突。这假设一个均匀随机的散列。任何弱点都会在预计发生碰撞之前减少输入的数量。

Answer 2

你的问题的答案是肯定的。对于任何散列函数，都有一个最大长度 X，您将返回唯一的字符串。但是，找到 X 可能非常困难。这个想法是运行这个程序：

X= 0;
For i = 0 onward
   For all strings of length i
      Compute the hash code of that string.
      If a collision is found, return X.
   X = i

这个想法是只列出越来越长的字符串，直到发现哈希冲突。最终您将不得不这样做，因为最终您将生成比可能的哈希输出更多的字符串。

按照预期，假设哈希函数实际上是非常随机的，您需要在发现冲突之前生成 O(√U) 个不同的字符串，其中 U 是哈希函数映射到的空间大小。对于 256 位哈希，这是 2 ²⁵⁶。这意味着在实践中，除非哈希函数被严重破坏，否则上述程序永远不会真正终止，但理论上这意味着您的数字 X 存在。

希望这可以帮助！