两个不同的string可以生成相同的MD5哈希码吗?

对于我们的每个二进制资产,我们生成一个MD5散列。 这用于检查某个二进制资产是否已经在我们的应用程序中。 但有可能两个不同的二进制资产生成相同的MD5散列。 那么有可能两个不同的string生成相同的MD5哈希?

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

但是,由于MD5散列函数已经被破坏(容易受到冲突攻击 ),任何确定的攻击者都可以在几秒钟内产生两个冲突资产 。 所以如果你想使用MD5,确保这样的攻击者不会损害你的应用程序的安全!

另外,考虑一下攻击者是否可以与数据库中的现有资产发生冲突 。 虽然目前还没有这种针对MD5的已知攻击( preimage攻击 )(截至2011年),但是通过扩展目前关于碰撞攻击的研究成为可能。

如果这些都是问题,我build议看看SHA-2系列的散列函数(SHA-256,SHA-384和SHA-512)。 不足之处是它稍微慢一些,并且有较长的散列输出。

MD5是一个散列函数 – 是的,两个不同的string可以绝对生成冲突的MD5代码。

特别要注意的是,MD5码具有固定的长度,所以MD5码的可能数量是有限的。 然而,string(任何长度)的数量肯定是无限的,所以在逻辑上必须有碰撞。

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

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

是的,当然:MD5散列有一个有限的长度,但是有无数个可能被MD5散列的string。

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

话虽如此,MD5等algorithm的devise是为了尽量减less碰撞的可能性。

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

只是为了更丰富。 从math的angular度来看,哈希函数不是内射的
这意味着起始集合和结果集合之间不存在1:1(但是单向)的关系。

双向注视维基百科

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

是的,两个不同的string可能会生成相同的MD5哈希码。

这是一个简单的testing,在hexstring中使用非常相似

$ 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的哈希值相同。 其次,string非常相似,所以很难find它们之间的区别。

差异可以通过以下命令find:

 $ 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单块碰撞 ; 他解释了他的方法,源代码(本文的替代链接 )。


另一个testing:

 $ 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 Xie和Dengguo Feng:2010年使用一个单块消息构造MD5碰撞


有关:

  • 是否有两个具有相同MD5散列值的已知string? 在Crypto.SE

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

编辑 :正如康拉德·鲁道夫所说:一组可能无限的input转换为一组有限的输出(32个hex字符) 导致无数的冲突。

正如其他人所说,是的,两个不同的投入之间可能会发生冲突。 但是,在您的使用案例中,我不认为这是一个问题。 我非常怀疑你会遇到碰撞 – 我已经使用MD5在前一个作业中指纹图像(JPG,位图,PNG,原始)格式的成千上万的图像文件,我没有碰撞。

但是,如果您正在尝试指定某种数据,那么也许可以使用两种散列algorithm – 一种input导致两种不同algorithm输出相同的几率几乎是不可能的。

我认为我们需要按照我们的要求来select哈希algorithm,因为哈希碰撞并不像我期望的那么难得。 我最近在我的项目中发现了一个非常简单的散列冲突案例。 我正在使用xxhash的Python包装来散列。 链接: https : //github.com/ewencp/pyhashxx

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

它在系统中造成了一个非常棘手的caching问题,然后我终于发现它是一个散列冲突。

我意识到这是旧的,但认为我会贡献我的解决scheme。 有2 ^ 128个可能的散列组合。 因此生日悖论的概率是2 ^ 64。 虽然下面的解决scheme不会消除碰撞的可能性,但它肯定会将风险降低很多。

 2^64 = 18,446,744,073,709,500,000 possible combinations 

我所做的是我根据inputstring放在一起哈希得到一个更长的结果string,你认为你的哈希…

所以我的伪代码是这样的:

 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))) 

好吧,不是最干净的解决scheme,但现在让你更多地玩弄你偶尔遇到碰撞的频率。 在这个意义上,我可能认为这个术语在所有的现实意义上都是不可能的。

为了我的缘故,我认为碰撞的可能性是不经常的,我认为这不是“绝对的”,但不太可能发生,以适应需要。

现在可能的组合显着上升。 虽然你可以花费很长时间在这个组合上可以得到多less个组合,但是在理论上它会使你比上面引用的数字显着更多

 2^64 (or 18,446,744,073,709,551,616) 

可能还有一百多位数字。 这理论上的最大可能会给你

可能的结果string数量:

528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336