密码学安全的加性哈希函数

Question

我正在开发一个基于Fountain Code的文件传输系统。在该系统中，数据块将被下载，并与xor函数组合。我想在到达时验证这些块。

我需要的是一个具有以下属性的加密安全散列函数：

哈希（A）^ 哈希（B）== 哈希（A ^ B）

这种东西存在吗？

注意：数据块必须与xor函数结合，哈希可以与任何您喜欢的函数结合，只要它计算起来相当便宜即可。

- Martin

---

我碰巧也在寻找同样的东西，用于同样的目的！很高兴找到了你的问题。+1！ - Matt Thomas

Answer 1

如果您请求的身份正是

Hash(A) ^ Hash(B) == Hash(A ^ B)

如果是这样，那么没有这样的具有密码学安全性的哈希函数。这是因为您的函数将成为一个从可能块的空间到可能哈希的空间的线性映射（在二元域上）。

简单来说，这意味着什么？

好吧，假设您的映射接受长度为6的块并返回长度为3的哈希值，并且这些是一些哈希值：

Hash(000001) = 010
Hash(000010) = 111
Hash(000100) = 001
Hash(001000) = 101
Hash(010000) = 110
Hash(100000) = 001

然后，您可以通过上述的线性组合计算任何给定块的哈希值。例如，

Hash(101000) = Hash(100000) ^ Hash(001000) = 001 ^ 101 = 100.

这意味着您的哈希函数可以用一个6x3矩阵表示。

这意味着什么？

维基百科将理想密码哈希函数定义为具有四个主要或重要属性：

- 对于任何给定的消息，计算哈希值很容易， - 很难找到具有给定哈希值的消息， - 修改消息而不改变其哈希值是不可行的， - 很难找到两个具有相同哈希值的不同消息。

当然，第一个属性可能是正确的，但其他属性则不是。反转哈希函数就像解决线性方程组一样简单，这很容易。我假设您已经对实数上的线性映射做过这个操作，但在这里完全相同的方法也适用。

如果你发现哈希函数的内核中有一个元素，即一个消息K使得Hash(K)全为零，则最后一个属性也失败了。取任何消息M；然后M和M^K将具有相同的哈希值，因为Hash(M^K) = Hash(M)^Hash(K) = Hash(M)^0 = Hash(M)。找到内核的元素也很容易。

第三个属性有点困难，但也可以被破解。（例如，假设你正在哈希一份合法合同。找到几个地方可以修改一些杂散的逗号之类的东西。考虑这些更改对哈希函数的影响，然后解一个线性方程组。）

- A. Rex

---

他不需要那个身份 - 对于任意两个运算符x和y，只要x有逆元，H(A x B) = H(A) y H(b)就足够了。我在这篇论文中看到的同态哈希使用一个素域上的加法和乘法作为两个操作。 （http://scholar.google.com/scholar?cluster=14785643307688189605&hl=en&as_sdt=2000） - Nick Johnson

是的，我的回答只涉及方程式 H(x^y)=H(x)^H(y) -- 但鉴于我第一句话中的“确切”一词，它声称不做更多的事情。实际上，我对你提到的情况有点好奇。 - A. Rex

没错 - 我只是在指出这只是可能解决方案的一个子集。即使添加块的函数必须是异或（对于喷泉码来说并不是这样），添加哈希的函数仍然可以是其他东西。 - Nick Johnson

我只是说要使用异或来组合块，因为我已经实现了这个功能，如果真的有必要，可以更改。 - Martin

Answer 2

你所需要的是一种称为同态哈希的东西。我不了解最新的进展，但我看到的一篇论文描述的计算速度极慢，几乎无法实现。原始论文在这里，后续论文对其使用进行了一些改进，在这里可以找到。

至于合并块，哈希通常要求您在素域中使用加法。如果您正在使用喷泉码，您不必使用异或，任何可逆函数都可以，包括加法。上述哈希使用素域中的加法和乘法，并被证明是安全的。

- Nick Johnson

---

你提供的那些论文看起来非常有前途，我会去阅读一下 :) - Martin

这些论文正好解决了我正在尝试解决的问题。太棒了！ - Martin

这些链接现在已经失效了。你有任何想法它们去哪了吗？ - Jeff Burdges