什么是用于数据完整性和重复数据删除的最佳散列算法？

Question

我试图在其中散列大量具有二进制数据的文件,以便:(1)检查将来的损坏,以及(2)消除重复文件(可能具有完全不同的名称和其他元数据).

我知道md5和sha1及其亲属,但我的理解是这些是为安全而设计的,因此故意减慢以降低暴力攻击的效力.相比之下,我希望算法尽可能快地运行,同时尽可能减少冲突.

有什么建议？

Answer 1

你是最正确的.如果您的系统没有任何攻击者,则使用加密哈希函数会因其安全属性而过度使用.

碰撞取决于位数,b,你的散列函数和散列值的数量,N,你估计来计算.学术文献认为这种碰撞概率必须低于硬件错误概率,因此与逐个字节[ ref1,ref2,ref3,ref4,ref5 ] 比较数据的可能性不大.硬件错误概率在2 ^ -12和2 ^ -15 [ ref6 ]的范围内.如果您希望生成N = 2 ^ q哈希值然后你的碰撞概率可以由这个等式给出,它已经考虑了生日悖论:

散列函数的位数与其计算复杂度成正比. 因此,您有兴趣找到具有可能最小位的散列函数,同时能够将碰撞概率保持在可接受的值.

以下是如何进行分析的示例:

• 假设你有f = 2 ^ 15个文件;
• 每个文件的平均大小lf是2 ^ 20字节 ;
• 你假装将每个文件分成平均大小lc等于2 ^ 10字节的块 ;

• 每个文件将分为c = lf/lc = 2 ^ 10个块 ;

• 然后,您将散列q = f*c = 2 ^ 25个对象.

根据该等式,几个散列大小的碰撞概率如下:

• P(散列= 64位)= 2 ^(2*25-64 + 1)= 2 ^ -13(小于2 ^ -12)
• P(散列= 128位)= 2 ^(2*25-128 + 1)2 ^ -77(远小于2 ^ -12的方式)

现在你只需要确定你将使用64或128位的非加密散列函数,知道64位它非常接近硬件错误概率(但会更快)和128位是一个更安全的选项(虽然更慢).

在Bellow中,您可以找到从非加密哈希函数维基百科中删除的小列表.我知道Murmurhash3,它比任何加密哈希函数都快得多:

1. Fowler-Noll-Vo:32,64,128,256,512和1024位
2. 詹金斯:64位和128位
3. MurmurHash:32,64,128和160位
4. CityHash:64位,128位和256位