哈希碰撞发生的时间是什么时候？

Question

我知道根据鸽巢原理，如果物品的数量大于容器的数量，那么至少会有一个容器包含多个物品。这个容器是哪个并不重要吗？这如何应用于MD5、SHA1、SHA2哈希？

- user963241

Answer 1

不论是哪个容器，对于密码哈希来说这并不重要， 生日悖论 更加重要，它表明在找到冲突之前，你只需要哈希平均数为sqrt(numberNeededByPigeonHolePrincipal)的值。

因此，哈希值需要足够大，以至于搜索空间的平方根太大而无法暴力破解。 SHA1的搜索空间的平方根为2⁸⁰，截至2012年3月，没有发现两个值具有相同的SHA1哈希值（尽管我预测这将在未来一两年内发生）。SHA2也是如此，这是一系列具有更大搜索空间的哈希函数族。MD5已经被破解了一段时间。

- BlueRaja - Danny Pflughoeft

---

值得注意的是，SHA1在2017年实际上已经被破解了。https://shattered.io/ - Filip Haglund

Answer 2

如果要散列的项比槽位多，就会产生哈希冲突。但是如果使用的哈希算法较差，则即使项/槽比非常小，也会发生冲突。好的哈希算法（包括大多数你在实际应用中看到的算法）将尝试尽可能平均地分布结果哈希值于整个输出空间，从而最小化碰撞。

请注意，哈希冲突并不是世界末日。例如，在哈希表中使用时，它只意味着一个槽中存储了多个项，表代码将必须稍微遍历一下才能找到或添加目标项，增加查找时间。

你会看到有人将MD5称为“破解”的哈希算法，但实际上，它只是作为加密哈希使用时较差的选择。但它仍然比你自己构建的哈希算法好。

- Michael Petrotta

---

MD5已经被破解，因为它不具备密码学安全性；各种SHA算法应该代替MD5使用。话虽如此，如果你只是用它作为下载文件的校验和，那么MD5已经足够好了。 - Michael Aaron Safyan

大多数情况下，MD5并不用于加密安全。它是一种非常快速的哈希算法，在大多数情况下足够好了。这不像他建议将其用于密码...或者您建议在哈希算法中实现一个真正安全且故意缓慢的Blowfish算法，以加快在数据快速更改的情况下的查找速度？至少它将是加密安全的。MD5仍然具有有效的目的，并且非常擅长它。 - John Nicholas

@MrTortoise：没错，就是这样。MD5在非加密使用时是可以的。为了让其他人清楚，千万不要在安全敏感（加密）的情况下使用MD5。 - Michael Petrotta

如果你只是用MD5作为下载文件的校验和，那么它已经足够好了。但这取决于你是否预期意外损坏或故意干扰。 - Nick Johnson

Answer 3

哈希函数的要点是将项目随机分配到容器中。对于任何良好的哈希函数，容器之间应该是无法区分的，因此哪个容器是哪个都不应该“有所区别”。

这并不适用于“完美哈希”实现，它试图比随机分布做得更好——不像你提到的算法。

正如Michael所提到的，在项目数量达到插槽数量之前，就会发生冲突。如果想处理[生日悖论](https://zh.wikipedia.org/wiki/%E7%94%9F%E6%97%A5%E6%82%96%E8%AE%BA)，则必须具备优雅的冲突处理（或完美哈希）。

- Potatoswatter

Answer 4

我认为你使用哈希函数的应用是一个重要的区别。例如，在哈希容器中频繁发生冲突可能会降低性能。在密码学中，频繁碰撞将产生更为严重的后果（参见：Wikipedia上的密码哈希函数）。

即使使用“不错”的哈希算法，碰撞也相对容易发生。例如，在Java中，

String s = new String(new char[size]);

始终哈希为0。也就是说，在Java中，所有仅包含 \0 的字符串都会哈希为0。

---

至于“容器是什么并不重要吗？”，这取决于应用程序。您可以设计哈希函数，将“相似”的对象哈希到附近的值。例如，当您想搜索相似的对象时，只需将它们全部哈希并查看它们所在的位置即可。在这种情况下，碰撞或接近碰撞是可取的，因为它将相似的对象分组。

在其他应用中，您希望即使对象发生最微小的变化，也会导致完全不同的哈希值。例如，在加密中，您希望尽可能确定某些内容未被修改。在这种情况下，更难找到哈希到相同值的不同对象。

- polygenelubricants

Answer 5

根据您的应用程序，像MDA、SHA1/2等加密哈希可能不是理想的选择，因为它们看起来完全随机，因此会出现由生日悖论预测的冲突。传统上，使用基于余数运算的简单哈希的一个原因是，期望键是序列号或类似的东西，因此余数运算将比随机预期的冲突少。例如，如果键是1..1000的整数，则如果您的哈希函数是key mod 1009，则在大小为1009的容器中可能根本没有冲突。人们有时会通过精心选择容器大小和哈希函数来手动调整系统，以实现均匀分割。

当然，如果您必须担心人们恶意选择会给您带来困难的键，或者上游系统发送给您非常偏向某些键（例如，它有自己的哈希表并决定一次处理所有哈希到X的键），则您可能希望使用基于密钥的加密哈希函数来防御这种情况。

- mcdowella