哈希冲突和附加数据

Question

假设我有两个字符串（或字节数组）A 和 B，它们都有相同的散列（散列我指的是 MD5 或 SHA1 之类的东西）。如果我在后面连接另一个字符串，A+C 和 B+C 也会有相同的哈希值 H' 吗？C+A 和 C+B 会发生什么？

我用它测试了 MD5 在我所有的测试中，在末尾附加一些内容会使散列相同，但在开头附加则不会。

这总是正确的（对于所有输入）吗？

对于所有（众所周知的）哈希函数都是如此吗？如果不是，是否存在一个（众所周知的）哈希函数，其中 A+C 和 B+C 不会发生冲突（C+A 和 C+B 也不会发生冲突）？

（除了从 MD5(x + reverse(x)) 和我的意思是其他构造的东西）

Answer 1

这取决于的完全在散列函数。同样，你有这些冲突的概率是非常小的。

Answer 2

细节取决于哈希函数 H，但通常它们的工作原理如下：

1. 使用输入 X 块（例如 512 位）
2. 将输入分成更小的部分（例如 32 位）并根据输入更新哈希内部状态
3. 如果还有更多输入，请转至步骤 1
4. 最后将内部状态吐出为哈希值H(X)

所以，如果 A 和 B 碰撞，即H(A) = H(B)，消耗它们后哈希将处于相同的状态。使用相同的输入 C 进一步更新状态可以使生成的哈希值相同。这解释了为什么 H(A+C) 有时是 H(B+C)。但这取决于 A 和 B 的大小如何与输入块大小对齐以及哈希如何在内部破坏输入块。

如果 C 是哈希块大小的倍数，则 C+A 和 C+B 可以相同，但否则可能不同。

Answer 3

被这里讨论的散列函数通常是加密（SHA1，MD5）。这些散列函数有一个雪崩效应 - 输出将与一个细微的变化发生急剧变化输入。

C的前缀和后缀扩展将有效地使一个较长的输入。 所以，增加任何内容到前部或后部的输入应该显著改变有效散列输出。

我不明白你是怎么做到的MD5校验，这里是我的测试。

echo "abcd" | md5sum
70fbc1fdada604e61e8d72205089b5eb

echo "0abcd" | md5sum
f5ac8127b3b6b85cdc13f237c6005d80

echo "abcd0" | md5sum
4c8a24d096de5d26c77677860a3c50e3

你是说，你位于两个输入其有相同的MD5哈希值，然后附加一些东西到输入的结束或开始后发现，在末处加入导致相同的MD5作为原始输入？

请提供样品与测试结果。