加密安全的附加哈希函数
我正在开发基于 Fountain Code 的文件传输系统。在该系统中，下载数据块并结合异或函数。我想在块到达时对其进行验证。
我需要的是一个加密安全的哈希函数，它具有以下属性：
Hash(A) ^ Hash(B) == Hash(A ^ B)
这样的东西存在吗？
注意：数据块必须与异或函数组合，哈希值可以与您喜欢的任何函数组合，只要计算成本相当便宜即可。
I am working on a Fountain Code based file transfer system. In this system blocks of data are downloaded, combined with an xor function. I want to verify the blocks as they arrive.
What I need is a cryptographically secure hash function which has the property:
Hash(A) ^ Hash(B) == Hash(A ^ B)
does such a thing exist?
Note: The data blocks must be combined with an xor function, the hashes can be combined with any function you like, so long as it's reasonably cheap to compute.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您请求的身份正是“
否”，则不可能有这样的加密安全哈希函数。这是因为您的函数将是一个 线性映射 （在 具有两个元素的字段）从可能的块空间到可能的哈希空间。
简单来说，这意味着什么？
好吧，假设您的映射采用长度为 6 的块并返回长度为 3 的哈希值，并且这些是一些哈希值：
然后您可以通过上述的线性组合来计算任何给定块的哈希值。例如，
这意味着您的哈希函数可以用 6×3 矩阵表示。
这意味着什么？
维基百科将理想的加密哈希函数定义为具有四个主要或重要的属性：
当然，第一个属性可能是正确的，但其余的则不会。反转哈希函数就像求解线性方程组一样简单，这很容易。我假设您已经对实数上的线性映射执行了此操作，但完全相同的方法在这里也适用。
如果您找到哈希函数的内核的元素，即消息
K使得Hash(K)全部为零，那么最后一个属性也会失败。接受任何消息M；那么M和M^K将具有相同的哈希值，因为Hash(M^K) = Hash(M)^Hash(K) = Hash(M )^0 = 哈希值(M)。查找内核元素也很容易。第三个属性稍微困难一点，但也可以破解。 （例如，假设您正在对一份法律合同进行哈希处理。找到一些可以修改一些杂散逗号或其他内容的地方。考虑这些更改对哈希函数的影响，然后求解线性方程组。）
If the identity you are requesting is exactly
then no, no such cryptographically secure hash function is possible. This is because your function would then be a linear map (over the field with two elements) from the space of possible blocks to the space of possible hashes.
What does this mean, in simpler terms?
Well, suppose your map takes blocks of length 6 and returns hashes of length 3, and that these are some of the hashes:
Then you can compute the hash of any given block by linear combinations of the above. For example,
This means that your hash function can be represented by a 6-by-3 matrix.
What does this imply?
Wikipedia defines the ideal cryptographic hash function as having four main or significant properties:
The first property may be true, of course, but the rest will not be. Inverting the hash function is as simple as solving a system of linear equations, which is easy. I assume you've done this for linear maps over the real numbers, but the exact same approach works here.
If you find an element of the kernel of the hash function, that is, a message
Ksuch thatHash(K)is all zeros, then the last property fails also. Take any messageM; thenMandM^Kwill have the same hash, becauseHash(M^K) = Hash(M)^Hash(K) = Hash(M)^0 = Hash(M). Finding elements of the kernel is easy, also.The third property is a little more difficult, but can be broken also. (For example, suppose you're hashing a legal contract. Find a few places where some stray commas can be modified or something. Consider the effect that these changes have on the hash function, and then solve a system of linear equations.)
你想要的叫做 同态哈希。我不了解最新的进展，但我看到的描述的计算速度极其缓慢，几乎不可行。原始论文位于此处，以及一些后续文章此处对其使用进行了改进。
至于组合块，哈希通常要求您在素数字段中使用加法。如果您使用喷泉码，则不必使用异或 - 任何可逆函数都可以，其中包括加法。上述散列适用于素数域中的加法和乘法，并且可证明是安全的。
What you want is called a Homomorphic Hash. I'm not up with the latest developments, but the one I saw described is extremely - almost unfeasibly - slow to compute. The original paper is here, and a followup with some refinements to its use is here.
As for combining blocks, the hash typically requires you use addition in a prime field. If you're using fountain codes, you don't have to use xor, though - any reversible function is fine, and that includes addition. The hash described above works on addition and multiplication in a prime field, and is provably secure.