我知道MD5已经发生了一些碰撞，但这更多是有关哈希函数的高级问题。
如果MD5将任意字符串哈希为32位十六进制值，则根据鸽巢原理，这显然不可能是唯一的，因为存在比32位十六进制值更多的唯一任意字符串。
哈希函数（如MD5）是如何保证唯一性的？
73
- Aly
1
我认为这是一个好链接：https://www.mscs.dal.ca/~selinger/md5collision/ - Nabi K.A.Z.
8个回答
121
你说得没错，MD5 不能保证唯一性，但是在一个32位十六进制值（16^32）中有大约3.402823669209387e+38种不同的值。这意味着，在算法背后的数学给出良好分布的情况下，发生重复的可能性极小。然而需要记住的是，在考虑如何使用它时，存在重复的可能性。通常使用 MD5 来确定某些东西是否被更改过（例如校验和）。修改某个内容后产生相同的MD5校验和几乎是不可能的。
编辑：（鉴于最近有关SHA1哈希的新闻） 上面的答案仍然是正确的，但您不应期望使用MD5哈希作为任何形式的反篡改安全检查。 SHA-1 哈希碰撞的概率比 MD5 小2^32（超过40亿），并且已经证明可以构造输入以产生相同的值。（在相当长时间之前，这已经针对MD5被证明过）。如果您想确保没有恶意地修改某个内容以产生相同的哈希值，则现在需要使用 SHA-2 来获得可靠的保证。
另一方面，如果不涉及安全检查，MD5 仍然具有其用处。
可以认为，SHA-2 哈希的计算成本足够低，因此您应该无论如何都使用它。
- Mike Cargal
6
9设计哈希函数的巧妙之处在于，所有这些输出的概率都是相等的。如果你有两个几乎相同的文档，它们只有一个比特位的差异，它们将产生完全不同的哈希值。 - Martin Beckett
6密码哈希的另一个有趣特性是它们被设计为难以“反向”或“针对”。换句话说，给定一个哈希值，想要找到一个能产生该哈希值的消息应当是困难的。 - Michael Burr
3有趣。这意味着两个不同的电子邮件生成相同的MD5哈希的可能性非常大，因此Gravatar会提供错误的用户图片。http://de.gravatar.com/site/implement/hash/ - Christian
SHA-2 是否也存在与 MD5 相同的问题，并且有可能出现重复结果？ - Nabi K.A.Z.1在某种意义上，SHA-2与MD5和SHA-1存在相同的问题，即它们都受到OP引用的鸽巢原理的影响。然而，SHA-1比MD5有更多的鸽巢，SHA-2比SHA-1有更多的鸽巢，每个鸽巢使碰撞的可能性更小。据我所知，没有人成功地找出了导致相同SHA-2哈希的操作，但这只是所需处理资源的差异。 - Mike Cargal
47
您完全正确。但是哈希并不是关于“唯一”的，而是关于“足够唯一的”。
- Ignacio Vazquez-Abrams
12
正如其他人所指出的，像MD5这样的哈希函数的目标是提供一种方便的方法来检查两个对象是否相等，而不需要知道它们最初是什么（密码）或者将它们整个进行比较（大文件）。
假设您有一个对象O及其哈希hO。您获得另一个对象P并希望检查它是否等于O。这可能是一个密码，或者是您下载的文件（在这种情况下，您可能没有O，而是与P一起提供的哈希值hO）。首先，您对P进行哈希以获得hP。
现在有两种可能性：
1. hO和hP不同。这必须意味着O和P是不同的，因为在两个值/对象上使用相同的哈希必须产生相同的值。哈希是确定性的。没有错误的负面效应。
2. hO和hP是相等的。正如您所述，由于鸽笼原理，这可能意味着不同的对象被哈希到同一个值，需要采取进一步的措施。
a. 由于可能性的数量非常高，如果您信任自己的哈希函数，这就足够了，就可以说：“在发生冲突的可能性为2的128次方中，有1次是一样的（理想情况），所以我们可以假设O=P。”例如，如果限制字符的长度和复杂性，这对于密码可能起作用。这就是为什么您看到存储在数据库中的密码哈希而不是密码本身的原因。
b. 您可能会决定，仅仅因为哈希值相等并不意味着对象相等，并直接比较O和P。您可能会出现误报。
假设您有一个对象O及其哈希hO。您获得另一个对象P并希望检查它是否等于O。这可能是一个密码，或者是您下载的文件（在这种情况下，您可能没有O，而是与P一起提供的哈希值hO）。首先，您对P进行哈希以获得hP。
现在有两种可能性：
1. hO和hP不同。这必须意味着O和P是不同的，因为在两个值/对象上使用相同的哈希必须产生相同的值。哈希是确定性的。没有错误的负面效应。
2. hO和hP是相等的。正如您所述，由于鸽笼原理，这可能意味着不同的对象被哈希到同一个值，需要采取进一步的措施。
a. 由于可能性的数量非常高，如果您信任自己的哈希函数，这就足够了，就可以说：“在发生冲突的可能性为2的128次方中，有1次是一样的（理想情况），所以我们可以假设O=P。”例如，如果限制字符的长度和复杂性，这对于密码可能起作用。这就是为什么您看到存储在数据库中的密码哈希而不是密码本身的原因。
b. 您可能会决定，仅仅因为哈希值相等并不意味着对象相等，并直接比较O和P。您可能会出现误报。
因此，虽然您可能会有误报的匹配，但您不会有误报的未匹配。根据您的应用程序以及对象是否预期始终相等或始终不同，哈希可能是一个多余的步骤。
- Phil
5
尽管哈希值的长度远大于输入值时很可能会发生碰撞，但对于大多数情况来说，碰撞的数量仍然足够低（总共有2的128次方种可能的哈希值，因此两个随机字符串产生相同哈希值的理论概率接近于10的38次方）。
MD5主要用于完整性检查，因此对于最小的更改非常敏感。输入的微小修改将导致截然不同的输出。这就是为什么仅根据哈希值猜测密码很困难的原因。
虽然哈希本身不可逆，但仍然可以通过纯暴力方法找到可能的输入值。因此，如果您使用MD5存储密码哈希，则始终要确保添加盐：如果在输入字符串中包含盐，则匹配的输入字符串必须完全包含相同的盐才能产生相同的输出字符串，否则匹配输出的原始输入字符串将在自动加盐后无法匹配（即您不能仅“反转”MD5并使用它进行登录，因为反转的MD5哈希很可能不是最初导致哈希创建的盐字符串）。
因此，哈希不是唯一的，但可以通过认证机制使其足够唯一（这是一个相当合理的为密码限制提供替代盐的论点之一：产生相同哈希值的字符串集可能包含许多不符合密码限制的字符串，因此通过暴力破解哈希更加困难--显然，仍然需要使用盐）。
较大的哈希意味着相同输入集的可能哈希集合更大，因此重叠的机会更低，但是在处理能力足够使MD5变得微不足道的情况之前，它仍然是大多数情况下的不错选择。
MD5主要用于完整性检查，因此对于最小的更改非常敏感。输入的微小修改将导致截然不同的输出。这就是为什么仅根据哈希值猜测密码很困难的原因。
虽然哈希本身不可逆，但仍然可以通过纯暴力方法找到可能的输入值。因此，如果您使用MD5存储密码哈希，则始终要确保添加盐：如果在输入字符串中包含盐，则匹配的输入字符串必须完全包含相同的盐才能产生相同的输出字符串，否则匹配输出的原始输入字符串将在自动加盐后无法匹配（即您不能仅“反转”MD5并使用它进行登录，因为反转的MD5哈希很可能不是最初导致哈希创建的盐字符串）。
因此，哈希不是唯一的，但可以通过认证机制使其足够唯一（这是一个相当合理的为密码限制提供替代盐的论点之一：产生相同哈希值的字符串集可能包含许多不符合密码限制的字符串，因此通过暴力破解哈希更加困难--显然，仍然需要使用盐）。
较大的哈希意味着相同输入集的可能哈希集合更大，因此重叠的机会更低，但是在处理能力足够使MD5变得微不足道的情况之前，它仍然是大多数情况下的不错选择。
- Alan Plum
2
- bmargulies
2
正如Mike（以及其他人）所说，它并不完美，但它能够完成任务，而碰撞性能实际上取决于算法（实际上相当不错）。
真正有趣的是自动操作文件或数据以保持相同哈希值但具有不同数据的功能，请参见此演示。
- Bolster
1
正如其他人所回答的那样，哈希函数在定义上不能保证返回唯一值，因为对于无限数量的输入，只有固定数量的哈希。它们的关键特性是它们的碰撞是不可预测的。
换句话说，它们不容易被反转--因此，虽然可能有许多不同的输入会产生相同的哈希结果（“碰撞”），但找到其中任意两个是计算上不可行的。
- Pinko
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接