我想计算一组元素（无序列表）的 sha1 哈希。我已经计算了每个元素的 sha1 哈希值。我正在考虑两种解决方案：
按哈希对元素进行排序并计算此类列表的顶部哈希。
将元素散列视为 160 位整数值，并将它们一起异或（按位运算）成一个 160 位散列。
第二种解决方案在安全散列函数属性方面是否较弱？(抗原像性、抗二次原像性、抗碰撞性)。
mikosik
问问题
2392 次
2 回答
8
选项 1 是在ERS中所做的：该标准使用哈希树，其中每个节点包含一个哈希值，该哈希值是根据来自子节点的哈希值集计算得出的；由于顺序在树中并不重要，因此在散列之前按字典顺序对值进行排序。这很好，而且，据我们所知，安全。
选项 2 非常不安全：如果哈希函数有 160 位输出，那么我可以轻松生成 160 个随机输入，使得相应的哈希值构成向量空间GF(2) 160的基础，此时我可以生成任何聚合哈希值的匹配集。攻击成本可以忽略不计。
@paj28 建议的选项 3（将值排序以散列，然后散列）也很好，只要您使用明确的分隔符“连接”排序值。例如，如果您对包含“bar”和“foo”的字符串集进行哈希处理，您不希望获得与包含“ba”和“rfoo”的字符串集相同的哈希值。当所有要散列的值具有相同的长度时，更容易获得安全的东西。
因此，使用选项 1：对集合中的每个值进行哈希处理，然后按字典顺序对哈希值进行排序，然后再次对排序后的值列表进行哈希处理。
关于选项 2 的攻击：这是线性代数。假设您有k个n位的向量，这样它们中的任何一个都不等于其他k-1个向量的 XOR（它们被称为线性无关）。然后考虑一个新的随机向量v；该向量等于k个向量中的一些向量的 XOR 的概率等于2 k-n，即只要k < 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的原像集。
于 2013-10-21T11:01:16.100 回答
0
另一个选项 (3) 是先对元素进行排序，然后使用不能作为元素一部分出现的分隔符将它们组合成单个字符串。
在这些可能性中，我最关心的有两种。我现在想不出你如何以实际的方式攻击它，但它似乎是最危险的。
所以1和3基本没问题。但我会推荐 3，因为您正在按照预期的方式使用哈希。
于 2013-10-21T10:09:14.283 回答