hash - 不同文件大小的哈希冲突与相同文件大小的哈希冲突的可能性相同吗？

Question

我正在对大量文件进行哈希处理，为了避免哈希冲突，我还存储了文件的原始大小 - 这样，即使存在哈希冲突，文件大小也不太可能相同。这是听起来的声音吗(哈希冲突同样可能是任何大小)，还是我需要另一条信息(如果冲突更有可能与原始长度相同)。

或者，更一般地说:无论原始文件大小如何，每个文件都可能产生特定的哈希值吗？

Answer 1

哈希函数通常被编写为将数据均匀分布在所有结果存储桶中。

如果您假设您的文件均匀分布在固定的可用大小范围内，则可以说您的文件只有 1024 (2^10) 个均匀分布的不同大小。存储文件大小最多只能通过不同文件大小的数量来减少冲突的可能性。

注意:我们可以假设它是 2^32 均匀分布且大小不同，但它仍然不会改变其余的数学计算。

人们普遍认为 MD5 上发生冲突的一般概率(例如)是 1/(2^128) .

除非有专门内置到哈希函数中的东西另有说明。给定任何有效的 X使得 P(MD5(X) == MD5(X+1)) 的概率与任何两个随机值保持相同{Y , Z也就是说 P(MD5(Y) == MD5(Z)) =P(MD5(X) == MD5(X+1)) =1/(2^128)对于 X 的任何值, Y和Z .

将此与 2^10 个不同文件相结合意味着通过存储文件大小，您最多可以获得额外的 10 位来表示项目是否不同(同样假设您的文件对于所有值均匀分布) .

因此，您所做的最好的事情就是为 <=N 字节的唯一值添加另外 N 字节的存储空间(它永远不会 >N)。因此，您最好使用 SHA-1/2 等内容来增加哈希函数返回的字节数，因为与存储文件大小相比，这更有可能为您提供均匀分布的哈希值数据。

简而言之，如果 MD5 不足以应对冲突，请使用更强的哈希值，如果更强的哈希值太慢，则使用冲突几率较低的快速哈希值，例如 MD5，并且然后使用较慢哈希(例如 SHA-1 或 SHA256)来减少冲突的机会，但如果 SHA256 足够快并且双倍空间不是问题，那么您可能应该使用 SHA256。