对于我们的每个二进制资产，我们生成一个 MD5 哈希。这用于检查某个二进制资产是否已经在我们的应用程序中。但是两种不同的二进制资产是否有可能生成相同的 MD5 哈希。那么两个不同的字符串是否有可能生成相同的 MD5 哈希？
问问题
85035 次
12 回答
99
对于一组甚至数十亿的资产，随机碰撞的可能性微乎其微——无需担心。考虑到生日悖论，给定一组 2^64（或 18,446,744,073,709,551,616）个资产，在该集合中发生单个MD5 碰撞的概率为 50%。在这种规模下，您可能会在存储容量方面击败 Google。
但是，由于 MD5 哈希函数已被破坏（它容易受到碰撞攻击），任何坚定的攻击者都可以在几秒钟内产生 2 个碰撞资产，相当于 CPU 功率。因此，如果您想使用 MD5，请确保此类攻击者不会危及您的应用程序的安全性！
此外，如果攻击者可以伪造与数据库中现有资产的冲突，请考虑后果。虽然没有针对 MD5 的此类已知攻击（原像攻击）（截至 2011 年），但可以通过扩展当前对碰撞攻击的研究来实现。
如果这些结果成为问题，我建议查看 SHA-2 系列哈希函数（SHA-256、SHA-384 和 SHA-512）。缺点是它的速度稍慢并且具有更长的哈希输出。
于 2009-11-18T13:51:33.470 回答
45
MD5 是一个哈希函数——所以是的，两个不同的字符串绝对可以生成冲突的 MD5 代码。
特别要注意 MD5 代码具有固定长度，因此可能的 MD5 代码数量是有限的。然而，字符串的数量（任意长度）绝对是无限的，因此从逻辑上讲，必然存在冲突。
于 2009-11-18T13:38:51.770 回答
13
是的，当然：MD5 散列的长度是有限的，但是有无数个可能的字符串可以进行 MD5 散列。
于 2009-11-18T13:41:43.317 回答
13
是的，两个不同的字符串可能会生成相同的 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: Single-block collision for MD5 , 2012; 他用源代码（论文的替代链接）解释了他的方法。
另一个测试：
$ 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
上例改编自谢涛和冯登国：Construct MD5 Collisions Using Just A Single Block Of Message，2010。
有关的：
- 是否存在两个具有相同 MD5 哈希值的已知字符串？在 Crypto.SE
于 2016-02-05T12:50:44.970 回答
4
只是为了提供更多信息。从数学的角度来看，哈希函数不是单射的。
这意味着在起始集和结果集之间没有一对一（而是一种方式）的关系。
编辑：存在完整的单射散列函数：它称为Perfect hashing。
于 2009-11-18T13:45:40.813 回答
3
是的！有可能发生碰撞（尽管风险很小）。如果没有，您将有一个非常有效的压缩方法！
编辑：正如 Konrad Rudolph 所说：一组可能无限的输入转换为一组有限的输出（32 个十六进制字符）将导致无数次冲突。
于 2009-11-18T13:38:51.037 回答
3
正如其他人所说，是的，两个不同的输入之间可能存在冲突。但是，在您的用例中，我认为这不是问题。我非常怀疑你会遇到冲突 - 我在之前的工作中使用 MD5 对数十万个图像（JPG、位图、PNG、原始）格式的图像文件进行指纹识别，但我没有发生冲突.
但是，如果您尝试对某种数据进行指纹识别，也许您可以使用两种哈希算法 - 一个输入导致两种不同算法的相同输出的可能性几乎是不可能的。
于 2009-11-18T13:44:47.920 回答
3
我认为我们需要根据我们的要求谨慎选择散列算法，因为散列冲突并不像我预期的那么罕见。我最近在我的项目中发现了一个非常简单的哈希冲突案例。我正在使用 xxhash 的 Python 包装器进行散列。链接：https ://github.com/ewencp/pyhashxx
s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266
它在系统中引起了一个非常棘手的缓存问题，然后我终于发现这是一个哈希冲突。
于 2016-02-02T06:12:29.923 回答
2
我意识到这已经过时了，但我想我会贡献我的解决方案。有 2^128 种可能的哈希组合。因此，生日悖论的概率为 2^64。虽然下面的解决方案不会消除碰撞的可能性，但它肯定会大大降低风险。
2^64 = 18,446,744,073,709,500,000 possible combinations
我所做的是我根据输入字符串将一些散列放在一起，以获得一个更长的结果字符串，你认为你的散列......
所以我的伪代码是：
Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))
那是碰撞的实际可能性。但是如果你想变得超级偏执并且不能让它发生，并且存储空间不是问题（计算周期也不是问题）......
Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))
& Hash(Reverse(SpellOutLengthWithWords(Length(string))))
& Hash(Rotate13(string)) Hash(Hash(string)) & Hash(Reverse(Hash(string)))
好吧，这不是最干净的解决方案，但现在这让你更多地了解你会遇到碰撞的频率。在这一点上，我可能会假设在该术语的所有现实意义上都是不可能的。
就我而言，我认为发生碰撞的可能性很小，我认为这不是“万无一失的”，但不太可能发生，它适合需要。
现在可能的组合显着增加。虽然您可能会花很长时间来了解这可以为您带来多少组合，但我会说理论上它比上面引用的数字要多得多
2^64 (or 18,446,744,073,709,551,616)
可能还有一百多位数左右。这可以给你的理论最大值是
结果字符串的可能数量：
528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336
于 2016-12-15T22:21:47.077 回答
0
看起来理论理解在实践中谈论理论时无济于事，需要知道什么意思只有 2 个数字 1 和 0 表示 1111111111，所以 100 表示 10 倍。
要在一个文件系统或一个生日系统上使用所有哈希值，世界上每个人都需要有 18446744073709551616/8000000000=2305843009.21 个文件，如果文件大小为 1mb，则为 2305843009 MB 或 2305843 GB 或 2305 TB 或 153722 Google 每人免费驱动 15 GB。
如果我们让文件更大，那么使用更多的空间和更少的文件数意味着更少的哈希值。所以我们仍然不会有更小的文件，而只会有更大的文件。
计算某人需要多大的文件，以便我们可以填充 MD5 所有哈希值。
如果平均文件大小在 2002 年为 3.22 MB，而 2005 年为 8.92，我们可以假设我们仍然使用相同质量的文件大小。所以即使是谷歌文件系统也永远不会在一个系统上拥有这么多文件，因为如果 15gb 的免费谷歌驱动器已满，世界上每 8 百万人平均有很多 3 mb 的小文件，那么来自所有 MD5 散列的 40000000000000 0.0000021684% 的可能性是所有可散列的文件大小。
谈论不相关的事情，例如 2 人的 100 生日当天将比较 2 天或 0.02，在 2 人中的 365 人中，将比较 0.00547% MD5 文件 2/18446744073709551616=0.00000000000000000000108420217%全部。
这就像在世界上没有 365 个人或文件系统文件或根本没有这么多密码时，在亚当和夏娃的世界中询问他们是否有相同的哈希生日。
因此，试图破解的冲突是如此之多，以至于在现实生活中的安全服务器中是不可能的。
如果 MD5 完全限制为 18,446,744,073,709,551,616，那么您将永远不会拥有这么多文件。
MD5 是将所有世界字符串都计入哈希的示例，它永远不会存在这么长时间，所以这只是 MD5 短的问题，但是我们是否会有数万亿个具有相同哈希的巨大长度的字符串？
实际上，这就像比较 365 个不同日子的婴儿和 366 个婴儿来找出哪个生日相同。
如您所见，理论上所有答案都是肯定的，但无法证明现实生活中的例子。如果它的密码，那么只有很长的字符串可能与短字符串相同。
如果其文件标识散列，则使用不同的散列或它们的组合。
生日问题是一个人的单词“abcd”是一个 4 个字母的单词，而其他人的 DNA 只有当它的“abcdfijdfj”时才可能相同。
如果您阅读有关生日问题的维基百科，它不仅像生日日期，而且像生日出生日期，小时，秒，毫秒，更像是 DNA 问题。
使用哈希，您可以与双胞胎拥有相同的 DNA 和生日吗？没有。有时甚至和别人在一起。
生日悖论当然是概率置信度数学把戏结果的可能性 365 个选项或天数，而哈希值是多少？多得多。因此，如果您有 2 个不同的匹配字符串，那只是因为 MD5 哈希对于太多文件来说太短了，所以请使用比 MD5 更长的东西。
Its not comparing 50 babies in 365 days, its comparing 2 hashes if they are the same from multiple length strings been hashed like abcd same as 25 letter abcdef...zdgdege and 150 letter sadiasdjsadijfsdf.sdaidjsad.dfijsdf.
So if its password, then its birthday sibling will be much longer that doesn't even exist, since no one makes birth of 25 letter password.
For file size comparing, I'm not sure how big the probability is but its not 97% and not even 0.0000001%.
Ok let's be more specific.
If its file then can occur of huge system since files will be different but needs to be not a problem in practice since 5 quadrillion or 5 000 000 000 000 000 files should be on same system for UUID and for MD5.
And if it is a password, then 10 years to try every second, but could try every millisecond, but then in 3 wrong guesses blocking ip for 1minute would make guessing millions of years.
When I see something wrong, then I know it's wrong. Theory promises vs reality.
于 2021-12-18T10:51:24.133 回答