选择哈希函数

Question

我在想：在保持哈希函数预期冲突计数的情况下，可以安全地哈希的最大字节数是多少？

对于md5、sha-*，甚至crc32或adler32等哈希函数。

- Folkert van Heusden

Answer 1

您的问题不够清晰。您所说的“最大字节数”是指“最大项目数”吗？被散列文件的大小与碰撞次数没有关系（当然，假设所有文件都是不同的）。而“保持预期的碰撞计数”是什么意思呢？严格来讲，答案是“无限的”，但在一定数量后，总会有碰撞发生，这是可以预料的。至于问题“在保持碰撞概率低于x％的情况下，我可以对多少个项目进行哈希处理？”的答案，请参见以下表格：

http://en.wikipedia.org/wiki/Birthday_problem#Probability_table

来自链接：

作为比较，10^-18到10^-15是典型硬盘的不可纠正位错误率[2]。理论上，即使可能的输出很多，128位的MD5应该在大约8200亿个文档内保持在这个范围内。

这假设哈希函数输出一个均匀分布。您可以假设有足够的要哈希和密码哈希函数（如md5和sha）或好的哈希（如Murmur3、Jenkins、City和Spooky Hash）。

还假设没有恶意对手积极制造冲突。那么您真的需要一个安全的密码哈希函数，例如SHA-2。

而且要小心：CRC和Adler是校验和，旨在检测数据损坏，而不是最小化预期冲突。它们具有诸如“检测所有位大小为< X或> Y的位清零，适用于Z kbytes以下的输入”等属性，但统计属性不如其他哈希函数。

编辑：不要忘记这一切都是关于概率的。完全有可能仅对小于0.5kb的两个文件进行哈希，得到相同的SHA-512值，尽管这极其不可能（例如迄今为止从未发现SHA哈希的碰撞）。

- ReneSac

---

非常感谢您详细的回复！它完全回答了我的问题。 - Folkert van Heusden

Answer 2

你基本上在看生日悖论，只是在考虑非常大的数字。 假设你的数据有一个正常的“分布”，我认为在遇到问题之前，你可以尝试使用可能性的5-10％，但不能保证一定不会出现问题。 只需使用足够长的哈希即可避免出现问题;)

- Sig-IO

---

所以使用512位的哈希大小，那么安全散列的位数应该在26至51位之间，对吗？ - Folkert van Heusden