两个不同的字符串可以生成相同的MD5哈希码吗？

Question

对于我们的每个二进制资产,我们生成MD5哈希.这用于检查某个二进制资产是否已存在于我们的应用程序中.但两个不同的二进制资产是否可能生成相同的MD5哈希值.那么两个不同的字符串是否可能生成相同的MD5哈希？

Answer 1

对于一组甚至数十亿的资产,随机碰撞的可能性几乎可以忽略不计 - 你不应该担心什么.考虑到生日悖论,给定一组2 ^ 64(或18,446,744,073,709,551,616)资产,该集合内单个 MD5碰撞的概率为50%.在这种规模下,您可能会在存储容量方面击败Google.

但是,由于MD5哈希函数已被破坏(它容易受到冲突攻击),任何确定的攻击者都可以在几秒钟的CPU功率下产生2个冲突资产.因此,如果您想使用MD5,请确保此类攻击者不会损害您的应用程序的安全性!

此外,如果攻击者可能伪造数据库中现有资产的冲突,请考虑其后果.虽然没有针对MD5的这种已知攻击(preimage攻击)(截至2011年),但通过扩展目前关于碰撞攻击的研究,它可能成为可能.

如果这些问题成为问题,我建议查看SHA-2系列哈希函数(SHA-256,SHA-384和SHA-512).缺点是它稍慢并且具有更长的哈希输出.

Answer 2

MD5是一个哈希函数 - 所以是的,两个不同的字符串绝对会产生冲突的MD5代码.

特别要注意的是,MD5代码具有固定长度,因此MD5代码的可能数量是有限的.然而,字符串的数量(任何长度)肯定是无限的,因此逻辑上遵循必须存在冲突.

Answer 3

对的,这是可能的.这实际上是一个生日问题.然而,具有相同MD5散列的两个随机选择的字符串的概率非常低.

有关示例,请参阅此问题和此问题.

Answer 4

是的,当然:MD5哈希的长度有限,但是有无数个可能的字符串可以进行MD5哈希处理.

Answer 5

是的,两个不同的字符串可能会生成相同的MD5哈希码.

这是一个使用十六进制字符串中非常相似的二进制消息的简单测

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc  -
008ee33a9d58b51cfeb425b0959121c9

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca  -
008ee33a9d58b51cfeb425b0959121c9

它们生成不同的SHA-1总和,但具有相同的MD5哈希值.其次,字符串非常相似,因此很难找到它们之间的区别.

可以通过以下命令找到差异:

$ diff -u <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 | fold -w2) <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 | fold -w2)
--- /dev/fd/63  2016-02-05 12:55:04.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:55:04.000000000 +0000
@@ -33,7 +33,7 @@
 af
 bf
 a2
-00
+02
 a8
 28
 4b
@@ -53,7 +53,7 @@
 6d
 a0
 d1
-55
+d5
 5d
 83
 60

以上碰撞示例取自Marc Stevens:2012年MD5的单块碰撞 ; 他用源代码解释了他的方法(文章的替代链接).

另一个测试:

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82  -
cee9a457e790cf20d4bdaa6d69f01e41

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb  -
cee9a457e790cf20d4bdaa6d69f01e41

不同的SHA-1总和,相同的MD5哈希值.

差异在一个字节中:

$ diff -u <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2) <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2)
--- /dev/fd/63  2016-02-05 12:56:43.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:56:43.000000000 +0000
@@ -19,7 +19,7 @@
 03
 65
 9e
-70
+74
 4f
 85
 34
@@ -41,7 +41,7 @@
 a3
 f4
 15
-5c
+dc
 bb
 86
 07

以上示例改编自Tao Tao和Dengguo Feng:2010年使用单块消息构建MD5碰撞.

有关:

• 是否有两个已知的字符串具有相同的MD5哈希值？在Crypto.SE