无序哈希

Question

我正在使用少量（小于10个）标识数据的信息创建键值对数据的键，并从这些信息组合中产生一个哈希值。为此，我一直在使用CryptoPP的SHA256 :: Update函数，它可以让您逐步添加这些信息：

#include "sha.h"
...
byte outputBuf[CryptoPP::SHA256::DIGESTSIZE];
CryptoPP::SHA256 hash;
hash.Update(pData1, lenData1); // pData* can point to int, double or std::string
hash.Update(pData2, lenData2);
...
hash.Final(outputBuf);

我注意到调用Update的顺序很重要（即如果更改两个Update语句的顺序，则会得到不同的哈希值）。我希望这可以独立于顺序。所以：

• CryptoPP是否提供了一种实现这一点的方法？
• 如果没有，您能否提出另一种替代方法？ 到目前为止，我认为使用xor来组合参数会起作用。 一个问题是如果两个数据相同，它们将抵消。 您能预见这方面的问题吗？

- Ari

---

几乎所有好的哈希函数（即使是非加密）都会依赖于输入顺序。否则，它会导致可预见的冲突以一种非常规律的模式出现，这是不好的。 - Damon

对于每个数据块，独立地进行一次哈希，然后将结果 ^ 在一起。当然，它很糟糕，缺少许多你想要的好哈希的特性，但它是一个无序的哈希。 - Yakk - Adam Nevraumont

只需提供一个带有命名参数的函数（或带有命名成员的结构体），让函数自行处理哈希顺序。任何使哈希顺序独立的方法都会增加碰撞，可能相当显著。 - Useless

无序性不仅会稍微增加碰撞的数量，而且会显著增加（因为对于 N 个字节有 N! 种排列方式，20! 大约是 10^18）。更糟糕的是，正如已经提到的，不仅有碰撞，而且它们发生在一种模式中。还要注意，使用异或作为散列的“缺点”在每个可交换操作中都存在。逆元素总是会抵消掉。对于异或来说，这恰好是一个相同的块，但对于每个可交换操作（例如 a + b + (-b) = a），它是相同的（只是值不同而已）。这就是它的工作原理。 - Damon

这个问题似乎不适合在此讨论，建议您转到crypto.stackexchange.com或security.stackexchange.com。 - jww

Answer 1

评论中说异或会增加碰撞的数量，这仅在您认为{1,2}和{2,1}是不同的输入时才是真的。我猜您不这么认为，否则您将不希望有一个与顺序无关的哈希。因此，h（{1,2}）= h（{2,1}）不是碰撞，因为您提供了相同的输入。

最简单的解决方案是排序，然后使用您喜欢的哈希函数。与您的哈希函数一样安全（如果您关心，请在crypto.stackexchange.com上确认）。

异或哈希绝对是个坏主意，因为两个相等的元素会互相抵消。将它们相加要好得多，但是对于两个相等的元素，最低有效位将为零（对于四个这样的元素，两个位将为零，等等）。这可能是可以接受的。

请注意，任何这种方法都非常不安全，因为它可以更快地找到碰撞（请求证明）。您可能需要或不需要安全性，但不要尝试发明一个安全的方法，因为这几乎是不可能的（每个众所周知的哈希函数都有许多月的分析背景）。

- maaartinus