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

Question

我理解到有证据表明MD5无法保证唯一性，因为宇宙中的字符串数量比MD5哈希字符串还要多，但是否存在有限数量的字符串的逆证明呢？

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

或者对于其他哈希算法，如SHA-1等，是否存在这样的X呢？

- xtrahelp.com

---

根据以下答案 https://dev59.com/B3I-5IYBdhLWcg3wI0x9，x = 1024位。 - Oli

@Oli- 那个答案说最短的已知哈希碰撞需要1024位。由于MD5输出128位值，因此可以保证最短的哈希碰撞必须比1024位短得多。 - templatetypedef

它已被证明对于1024位是不唯一的，但对于小于1024位是否被证明为唯一？ - xtrahelp.com

@xtrahelp.com- 当字符串长度为128位时，必然会发生碰撞，因为字符串数量太多了，不可能不发生碰撞。1024位比实际需要的要大得多，但这似乎是我们目前最好的方案。 - templatetypedef

尽管这是一个明确的问题，但你问关于哈希唯一性的事实引起了警觉... - AakashM

Answer 1

总结以下这里的优秀回答：什么是导致MD5碰撞的最短字符串对？

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

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

- Clueless

---

之前的问题询问了最小的已知哈希碰撞。1024位的值比哈希函数的输出大小128位大得多，因此答案在这个问题中毫无意义。 - templatetypedef

你可以期望得到一个大约64位的哈希值，但我们只知道如何在1024位中可靠地生成它们。我不知道是否有人测试过所有大约2^64个短输入的碰撞。这是一项艰巨的工作，在一台计算机上需要多年时间，但并非不可能。 - Clueless

@Clueless：使用每个哈希600个周期（使用http://cr.yp.to/talks/2008.06.05/slides.pdf作为600个周期的参考），对于一个8核4 GHz的机器，我得到了11000年。 - Charles

是的，现在计算2^64个MD5是可行的。但我认为存储2^64个输出要昂贵得多（并且写入存储可能会使您受到IO限制？）。有方法可以减少存储->增加时间，但是时间变得昂贵...无论如何，是的，只需要几年时间就可以合理地降低成本... - Beni Cherniavsky-Paskin

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 存在。

希望这可以帮助!

- templatetypedef

---

嗯，是的，有人找到 X 了吗？ - xtrahelp.com

@templatetypedef 那个断言并不完全正确——已知散列算法中存在大量碰撞，而且这些算法被认为是强的。此外，攻击者还可以利用这种碰撞进行攻击。 - Charles Duffy

@CharlesDuffy- 是的，你说得对（抱歉！）。 我的意思是找到X的值可能意味着有人已经找到了最短的哈希碰撞，而我理解大多数哈希函数尚未完成此操作（我们只知道短哈希碰撞，而不是最短的）。 - templatetypedef