对于像MD5这样的哈希函数，两个纯文本字符串有多相似并且仍然会生成相同的哈希？

#1 楼

这个答案是基于AleksanderRas的工作，尽管我的结论是不同的。

首先，要列出定义，散列是将任意长度的输入输入到固定长度的输出的函数。例如，MD5接受任何输入并产生128位输出。

加密哈希是具有某些附加安全性属性的哈希函数。

因为哈希函数采用任意长度的输入并产生固定长度的输出，所以可以保证有些输入产生相同的输出。这些是碰撞。

最后，汉明距离是相同长度的两个输入相差的位数。密码散列函数，汉明距离为2的输入会发生冲突。信鸽原理也可以证明这一点：


假设哈希函数返回n位输出。
有2n种可能的输出。
考虑一个长度为2n + 1位的字符串B。
然后考虑与B完全不同的所有字符串的集合。有2n + 1个这样的字符串。
该组中任何两个不同的字符串之间的汉明距离为2：将1位更改返回到B，将第二个1位更改返回到该集中的另一个字符串。
因为此集合中的字符串多于可能的输出哈希，所以至少两个字符串必须共享一个哈希。
因此哈希函数具有2位差异冲突。


可以构造一个哈希函数，该函数在汉明距离为1的字符串之间没有任何冲突。可以显示如下：


考虑字符串B
考虑与汉明距离为1的字符串C。
B的奇偶性必须与C的奇偶性不同。也就是说，如果B中设置的位数为奇数，则存在在C中必须为偶数，反之亦然。
因此，任何直接编码输入奇偶校验的哈希函数，例如带有奇偶校验位的常规MD5，都将具有至少2的汉明距离。最小碰撞汉明距离为2。例如，CBC-MAC是一系列算法，可以在CBC模式下使用固定密钥加密位串，然后返回最后一个块。这符合哈希函数的定义：它接受任意长度的输入，并返回固定为块大小的输出。尽管（像所有哈希函数一样）CBC-MAC容易受到冲突的影响，但如果所有更改都发生在单个块中，它就不会发生冲突。 （此属性来自以下事实：它是一种加密函数，因此是一种置换，但是将不再赘述）。因为汉明距离为1对应于单个位更改，并且该单个位更改仅需一个块，它不会引起冲突。


这不意味着每个哈希函数的冲突输入之间的最小汉明距离为2。有些函数的最小汉明距离为1：例如，平凡的哈希函数截断。也就是说，给定一个n位哈希函数，该函数仅丢弃除前n位以外的所有位，则变化的位n + 1将（由于算法忽略）会产生冲突。

因此，当涉及特定的哈希函数时，答案可能是1或2。

其他人认为，对于MD5和其他标准密码哈希函数，可能是1.这是一个纯概率论证，但是在没有相反证据的情况下，将概率与设计为随机行为的哈希函数一起使用是合理的。

#2 楼

对于任何加密哈希算法，答案都是1位（Hamming-distance = 1）。
肯定存在冲突，因为MD5算法的摘要始终为128位长，但可能有2128个以上的输入。 />由于鸽子洞原理，我们可以对此进行解释。

数学上的解释
假设我们接受一个3位输入消息：
总共有8种可能性，因为23 = 8：

000
001
010
011
100
101
110
111

因此对于n位输入长度，我们有2n个可能的值。
如果以第一个位字符串为例（000），您可以很容易地看到存在汉明的三种可能性-distance of 1（001，010，100）
理论上，您可以采用长度为2129的位字符串，其中所有位均为零（000 ... 000）。我们对该位字符串进行哈希处理，并将其称为A。然后将第一个零替换为1（000 ... 001），并寻找与A的冲突，如果未将第二个零替换为1（000 ... 010），并且以此类推。因为2129> 2128（您有2129个可能的输入，但只有2128个可能的输出），所以这肯定会给您带来哈希冲突。这是我能想到的最简单的示例（尽管要花很长时间才能实现）。
请注意，如果假设MD5是完美的哈希函数（肯定不是），就属于这种情况。 t）。实际上，我们可以用少于2129位的位数执行此实验，并期望发生冲突。
请注意，您不能确保通过上述过程获得所有可能的哈希输出。鸽子原则只说至少有一些碰撞。可能存在与任何输入都不对应的哈希值，即没有输入可以生成128位零（000 ... 000）的哈希值。我们假设每个哈希值都是可能的，但我们无法证明它。
如果我们接受确实没有输入限制（显然有输入大小限制），则理论上也可以使用其他哈希函数（MD5，SHA1，SHA2等）执行相同的实验。您只需要更改实验可能的哈希值的长度即可。它甚至可以应用于完美的哈希函数。

#3 楼

有两个答案：一个是实用的，一个是理论的。第二，理论上，汉明距离为6的碰撞，但这是一个重要的设计目标，因为实际上是如何使用哈希的）。 MD5证明是对随机函数的较差的近似值（因为已知它已被破坏），但让我们假设它不是。 1），发生碰撞的几率为2 ^ 128。仅仅因为其他任何数据发生冲突的几率为2 ^ 128。这是不太可能的，但是您可以尝试使用其他不同的数据及其邻居。每次尝试时，您都会有2 ^ 128的机会有1个发现碰撞的机会，因此，如果您一直努力尝试（这是很长的时间），几乎可以肯定会与邻居发生碰撞。 br />
因此理论上最小碰撞距离为1，我们怀疑存在这种碰撞。

但是在实践中，发现该碰撞所需的时间过长大（大于宇宙年龄）。确实，在设计良好的密码哈希函数中，根本找不到冲突（即不限于邻居）所花费的时间应该过长。在合理的时间内根本没有MD5中的任何冲突。我们可以做到的事实就是为什么我们说它被打破了。

#4 楼

密码哈希函数的一个重要方面是，即使输入的最小差异也通常会导致不同的输出。但是，与加密散列的有限输出空间相比，给定无限的输入空间，则可能存在仅存在很小差异（例如单个位）但具有相同散列值的序列。

但是，为了获得更可靠的陈述以及其背后的一些数学信息，我建议在crypto.stackexchange.com进行询问。

#5 楼

我们可以证明任何算法的2位上限（汉明距离= 2）
上限
该上限适用于哈希算法，其输出是长度为128的位串（如MD5）。可以通过用n
替换128来概括它。让A为长度为2128的任何位串。让S为A及其所有邻居的集合。这里的邻居是一个与A完全不同的字符串。
因为字符串中有2128位，所以| S | = 2128 + 1
Pigeonhole原理告诉我们，任何输出为128位长字符串的哈希算法，都必须在集合S上至少发生一次冲突（不同字符串的数目为2128）。
由于S中任意两个元素之间的汉明距离最大为2，我们证明了一个上限。
下界
对于优化最小汉明距离的哈希函数，我们可以证明下界2在碰撞之间。
直觉
考虑一个散列函数，该函数输出输入字符串的奇偶校验。该哈希函数在相邻的输入字符串上不会有任何冲突。优化碰撞之间最小距离的哈希算法至少会同样好。
图论
借助一些有关图着色和二部图的知识，我们可以创建稍微形式化的证明。 />考虑一个无向图G。它的节点是长度为n的二进制输入字符串，并且当且仅当输入字符串的汉明距离为1时，两个节点之间才存在一条边。节点的颜色将与其哈希相对应。
二进制字符串的奇偶校验总是与其邻居不同，该图必须是二分图。
二分图可以用两种颜色着色，以使任何邻居都不共享颜色。这意味着具有至少一位输出（两个选项）的哈希函数可以避免任何相邻输入字符串之间的冲突。
结论
我们已经证明，对于MD5和任何其他哈希算法，存在两个汉明距离最大为2的输入字符串，这将导致冲突。
对于使该距离最大化的哈希算法，我们可以证明2的下界。

#6 楼

MD5和SHA-1是严重损坏的功能。但是您可以考虑一个抽象的，好的密码哈希函数，并假装它为每个不同的输入生成一个不同长度的不同随机数，并以此方式对冲突进行建模。两个随机哈希是长度相同的另一个随机数。因此，您可以通过选择字符串s和XORing哈希（后跟字节0x00）与哈希（后跟字节0x01）进行XOR运算，从而生成哈希函数输出长度的随机数。

当您从该XOR获得的数字为0时，您将发生冲突。现在，将所有2 ^ 128个16字节字符串作为s进行尝试，并如上所述对两个哈希进行XOR。您获得的2 ^ 128 128位随机数之一将为零，很有可能不是-我认为概率是（非常接近）1-1 / e。

如果不走运并且没有碰撞，请尝试几次，用0x00和0x01替换为一对不同的后缀（例如0x02和0x03或多个一字节对用完时，字节数）。随着尝试次数的增加，仍然不会从随机散列的哈希中获得任何碰撞的机会呈指数下降。

您可以对其进行更精确的建模，并填写更多细节。但是我希望这足以直观地表明，一个好的哈希可能会有一对冲突的输入，它们之间只有一点点的差异，不会比散列的输出长很多。

由于您无法尝试2 ^ 128个散列的输入，因此您无能为力。我们专门设置了输出长度，以使这些搜索变得不可能。很高兴看到这样的示例应该在那里存在。

#7 楼

简单答案：MD5是一个有限集，这意味着由于MD5长为32个字符，由十六进制字符组成，因此您可以逐字写出或计算每个组合。但是，输入集是无限的，可以放入MD5哈希中的对象没有限制。对于无限输入集和有限输出集，必须有来自不同输入的重叠。