散列冲突和附加数据

问题描述：

假设我有两个字符串（或字节数组）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))等构成的东西，我的意思是）

答

这对哈希函数依赖完全。而且，你碰到这种碰撞的可能性非常小。

所以，你知道任何引用列出它的几个哈希函数？ – mihi 2009-06-15 14:50:55

答

详细取决于散列函数H，但通常它们的工作方式如下：

消耗输入X（比方说，512位）的块
打破输入成小块（比方说，32基于输入比特）和更新散列内部状态
如果有更多的输入，则转到步骤1
在结束时，吐出的内部状态作为出的散列值H（X）

因此，如果A和B发生碰撞，即H（A）= H（B），则散列在消耗后将处于相同的状态。用相同的输入C进一步更新状态可以使结果散列值相同。这解释了为什么H（A + C）有时是H（B + C）。但它取决于A和B的大小如何与输入块大小以及哈希如何在内部中断输入块。

如果C是散列块大小的倍数，C + A和C + B可以是相同的，但可能不是。

我不同意这个描述。如果A和B（不同的输入）在特定的哈希计算中发生碰撞，他们会这样做，因为它们已经运行了不同的“内部”状态，它们已经达到了相同的最终计算（通过一个非常怪异的机会，只要我们有一个好的哈希函数）。 – nik 2009-06-15 15:05:15

现在，如果一个额外的输入C被添加到两个输入的前缀或后缀中，那么在计算序列中看到的这些“内部”状态应该显着改变，不会达到（A，C）和（B，C）的最终计算结果。其中（X，Y）代表Y前缀或后缀X. – nik 2009-06-15 15:07:31

答

这里讨论的散列函数通常是密码（SHA1，MD5）。这些哈希函数有一个Avalanche effect - 随着输入的轻微变化，输出将发生急剧变化。

C的前缀和后缀扩展名将有效地提供更长的输入。因此，向输入的前面或后面添加任何内容都会显着改变有效散列输出。

我不明白你是如何做MD5检查的，这里是我的测试。

echo "abcd" | md5sum 
70fbc1fdada604e61e8d72205089b5eb 

echo "0abcd" | md5sum 
f5ac8127b3b6b85cdc13f237c6005d80 

echo "abcd0" | md5sum 
4c8a24d096de5d26c77677860a3c50e3

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

请提供样品与您的测试结果。

散列冲突和附加数据

相关推荐