如何计算一组(无序列表)值的哈希值？

Question

我想计算一组(无序列表)元素的sha1哈希值.我已经计算了每个元素的sha1哈希值.我正在考虑两种解决方案:

1. 按其哈希值对元素进行排序,并计算此列表的顶部哈希值.

2. 将元素哈希值处理为160位整数值,并将它们XOR(按位运算)一起处理为一个160位哈希值.

第二个解决方案在安全散列函数属性方面是否较弱？(图像前电阻,第二图像前电阻,抗冲击性).

Answer 1

选项1是在ERS中完成的:该标准使用散列树,其中每个节点包含通过子节点的散列值集合计算的散列值; 由于树中的顺序不重要,因此在散列之前按字典顺序对值进行排序.这很好,据我们所知,安全.

选项2非常不安全:如果散列函数具有160位输出,那么我可以轻松生成160个随机输入,使得相应的散列值构成向量空间GF(2)^160的基础,此时我可以生成匹配任何聚合哈希值的集合.攻击成本可以忽略不计.

@ paj28建议的选项3(将值排序为哈希值,然后哈希它们)也可以,只要您将排序值与一个明确的分隔符"连接"起来.例如,如果散列包含"bar"和"foo"的字符串集,则不希望获得与包含"ba"和"rfoo"的字符串集相同的散列值.当哈希的所有值具有相同的长度时,更容易获得安全的东西.

因此,使用选项1:对集合中的每个值进行散列,然后按字典顺序对散列值进行排序,并再次对排序的值列表进行散列.

关于选项2的攻击:这是线性代数.假设你有n个位的k个向量,这样它们都不等于某些k-1个其他向量的XOR (它们被认为是线性无关的).然后考虑一个新的随机向量v ; 这向量等于一些的XOR的概率ķ矢量等于2 ^k-n个,即,它是小只要ķ<N .如果新的向量v确实与你已经拥有的k个向量线性独立(因此概率为1-2 ^k-n),然后将其添加到集合中:您现在有k + 1个线性独立向量.

递归:您将很快获得n个n位向量,这些向量彼此线性无关.但是你不能走得更远,因为任何新矢量与n先前线性无关的概率都降到了0. n个矢量被认为是矢量空间的基础.

在这种情况下,通过简单地散列值来获得向量(随机值,或具有结构的值,它并不重要,因为散列函数充当随机化器).

对于给定的一组k个矢量,利用高斯消元确定新的矢量v是否与k个矢量线性无关.一旦你有了基础,同样的算法就会让你知道你的n个基矢量中的哪一个应该被异或,以产生任何矢量v'.在这个问题的设置中,这意味着一旦我产生n个值m _i使得h(m _i)构成基础,那么对于任何目标n位输出t,我可以使用高斯消除来计算出哪个我的h(m _i)可以一起进行异或运动以准确地产生值t.然后,相应的m _i值是为t设置的原像.