hash - 选择哈希函数

Question

我想知道：在保持散列函数的预期冲突计数的同时，可以安全散列的最大字节数是多少？

对于 md5、sha-*，甚至可能是 crc32 或 adler32。

score 3 · Accepted Answer

你的问题不清楚。“最大字节数”是指“最大项目数”？被散列的文件的大小与冲突的数量无关（当然，假设所有文件都不同）。

“保持预期的碰撞次数”是什么意思？从字面上看，答案是“无限的”，但在一定数量之后，你会如预期的那样发生碰撞。

至于“在保持碰撞概率低于 x% 的情况下，我可以散列多少个项目？”这个问题的答案，请看下表：

从链接：

作为比较，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 哈希的冲突）。

score -2 · Accepted Answer

你基本上是在看生日悖论，只看非常大的数字。鉴于数据的正常“分布”，我认为在遇到问题之前您可以达到大约 5-10% 的可能性，尽管没有任何保证。

只需使用足够长的哈希就不会遇到问题；）

2 回答 2