具有不同文件大小的哈希冲突是否与文件大小相同？

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.

Answer 2

取决于您的散列函数,但通常,大小相同但内容不同的文件不太可能生成与大小不同的文件相同的散列.尽管如此,简单地使用具有更大空间的经过时间考验的哈希(例如MD5而不是CRC32,或SHA1而不是MD5)可能比在您自己的解决方案(如存储文件大小)上下注更简洁.