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


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


84
2017-11-18 13:36


起源




答案:


对于一组甚至数十亿的资产, 随机碰撞的可能性微不足道  - 你不应该担心什么。考虑到 生日悖论,给出一组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)。缺点是它稍微慢一点,并且哈希输出更长。


89
2017-11-18 13:51



正如我所理解的那样,“天”在这一点上是一个巨大的夸大其词。 - Nick Johnson
是的,我更新了我的帖子。 2004年的随机碰撞攻击非常快。 2007 MD5 字首 碰撞攻击可能需要数天 - 但通常对攻击者更有用 - intgr
请参阅Rubens的回答,了解一个可在几小时内在两个不同的可执行文件之间产生冲突的工作示例。 :) - Nick Johnson
谢谢,你是对的。 - intgr


MD5是一个 哈希函数  - 是的,两个不同的字符串绝对会产生碰撞的MD5代码。

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


37
2017-11-18 13:38





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

看到 这个 和 这个 问题的例子。


12
2017-11-18 13:38



什么概率?碰撞?不,那将是1,即非常高。 ;-) - Konrad Rudolph
嗯,是的。肯定存在两个具有相同MD5哈希的字符串。 - sharptooth
我知道这是一个鸽子洞的问题。 - Daniel A. White
en.wikipedia.org/wiki/Pigeonhole_principle - Daniel A. White
生日问题只关系到碰撞的可能性。为了证明必须有一个你想要皮江孔的原则 - jk.


是的,当然:MD5哈希的长度是有限的,但是有无数个可能的字符串可以是MD5哈希值。


10
2017-11-18 13:41





是的,两个不同的字符串可能会生成相同的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: 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

上面的例子改编自陶燮和邓国峰: 仅使用一个消息块构造MD5冲突,2010。


有关:


5
2018-02-05 12:50





对的,这是可能的。它被称为a 哈希碰撞

话虽如此,MD5等算法旨在最大限度地减少碰撞的可能性。

维基百科上的条目 MD5 解释了MD5中的一些漏洞,您应该注意这些漏洞。


4
2017-11-18 13:40





只是为了提供更多信息。 从数学的角度来看,Hash函数不是 内射
这意味着起始集与结果集之间不存在1对1(但单向)关系。

维基百科上的双射

编辑:完整的内射哈希函数存在:它被称为 完美的哈希


4
2017-11-18 13:45



当输出尺寸小于输入尺寸时,没有完美的散列函数。 - Paŭlo Ebermann


是的!碰撞  是一种可能性(尽管风险非常小)。如果没有,你会有一个非常有效的压缩方法!

编辑:正如Konrad Rudolph所说:可能无限制的输入转换为有限的输出集(32个十六进制字符)  导致无数次碰撞。


3
2017-11-18 13:38





正如其他人所说,是的,两个不同的输入之间可能会发生冲突。但是,在您的用例中,我不认为这是一个问题。我非常怀疑你会遇到碰撞 - 我曾使用MD5指纹识别上一份作业中数十个图像(JPG,位图,PNG,原始)格式的数十万个图像文件而且我没有碰撞。

但是,如果您尝试指纹某种数据,也许您可​​以使用两种哈希算法 - 一次输入的几率导致两种不同算法的相同输出几乎是不可能的。


3
2017-11-18 13:44



实际上,如果攻击者可以使用一个哈希算法产生冲突,他可以使用它来获得第二个算法的冲突。这是最近讨论过的 我在crypto.stackexchange的问题。 - Paŭlo Ebermann


我认为我们需要小心根据我们的要求选择散列算法,因为散列冲突并不像我预期的那么罕见。我最近在我的项目中发现了一个非常简单的哈希冲突案例。我正在使用xxhash的Python包装器进行散列。链接: https://github.com/ewencp/pyhashxx

s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266

它在系统中引起了一个非常棘手的缓存问题,然后我终于发现它是一个哈希冲突。


1
2018-02-02 06:12





我意识到这是旧的,但我想我会贡献我的解决方案。有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


1
2017-12-15 22:21