MD5 不是在 10 年前已经被山东大学王小云破解了吗？

[andybest]

为什么现在还在用彩虹表、碰撞？
山东大学王小云到底是如何破解的 MD5 ？

[lightening]

破解的意思是找出一个碰撞。
Wikipedia http://zh.wikipedia.org/wiki/王小雲：

“以有長度限制的雜湊函數計算沒有長度限制的訊息是必然會有衝撞情況出現的。可是一直以來，電腦保安專家一直無法給出實際例子，而王小雲提供了第一個碰撞範例。”

[sanddudu]

2004年的国际密码讨论年会（CRYPTO）尾声，王小云及其研究同事展示了MD5、SHA-0及其他相关杂凑函数的杂凑冲撞。所谓杂凑冲撞指两个完全不同的讯息经杂凑函数计算得出完全相同的杂凑值。根据鸽巢原理，以有长度限制的杂凑函数计算没有长度限制的讯息是必然会有冲撞情况出现的。可是一直以来，电脑保安专家一直无法给出实际例子，而王小云提供了第一个碰撞范例。

以上来自维基百科
杂凑函数就是散列函数，或者叫哈希函数

[andybest]

@lightening @sanddudu
也就是说，她找出了第一个 两个值不同，但 MD5 值相同的碰撞的例子？
这就等于破解了 MD5 是吗？

[sanddudu]

@andybest 每个哈希函数都会有这样的碰撞，被找到是迟早的
但是足以构成安全威胁，所以大家现在都加盐了

[lightening]

@andybest 我们把它叫做“破解”了。实际上这个碰撞必然存在，而且有无穷多个，王小云找到了一组，并且提供了找的方法。

但是没找到的话，也是需要加盐的。不然大家可以预先算出常用密码的MD5，然后拿去数据库比对。

MD5的碰撞找到，对实际使用的安全性影响并不是很大。但是安全起见，现在基本上都用 SHA 了吧

[wy315700]

他只是缩小了寻找碰撞的运算次数

比如sha1 本来要2^160次才有一次碰撞 她好像给缩小到2^80次了

然后任何强劲的加密算法都搞不定一个弱密码

[lsylsy2]

@andybest 她给出了计算这个碰撞的方法；
按照维基百科，比如SHA-1，原先破解需要的复杂度是2^80，王小云做到了2^63，可以称为“速度提高了131072倍”；
但是2^63依旧是一个非常大的数，所以很多地方依旧在用也并不是不可接受（安全度降低，做用来检验是否出错的校验码还是足够的）

[sanddudu]

@lightening
http://cmd5.com
我以前就在用，其实碰撞还是很常用的
另外，SHA-1 的碰撞也是王小云提出的的，把步骤缩小到了 2^69

[sanddudu]

更正：于同年缩短到了 2^63

[davidli]

在Google Scholar 上有她的《Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD》这篇论文，大意应该是这样的：

对任何原文P及其hash值D， 她这个算法能在1小时内找到另一个明文P' ,使P'的hash值 D'=D

原文：
On IBM P690, it takes about one hour to find such M and M' , after that, it takes only 15 seconds to 5 minutes to find Ni and Ni', so that ( M,Ni ) and (M' , Ni' ) will produce the same hash same value. Moreover, our attack works for any given initial value.

不知道理解得对不对。。

[lightening]

@sanddudu 但是使用场景并不同啊，王小云的算法是已知明文，找一个碰撞。而实际密码破解是找一个能 salt 过后还能算出给定 hash 值的算法。所以王小云的算法和实际脱裤后找原密码的关系并不大。

[msg7086]

@andybest 我用一个通俗易懂不太严谨的方式来回答吧

比如原本攻破一个md5需要1000000年的时间来运算，现在王小云的研究结果使得这个破解速度变快了，同样的一个md5只要100年就能攻破了。

[otakustay]

直接回答楼主的疑问：找碰撞的算法搞不定加盐的MD5，所以彩虹表还得用

[SoloCompany]

就是说，假设你用了一个很牛哔的密码，完全是机器随机生成的，并且熵值不低于64位，假设每个字符的信息量是6位，也就是说，不少于11个字符；然后你被脱裤子了，还是用的没加盐的md5；那么，通过破解算法，可以通过和直接暴力穷举相若的运算量，把你的密码给破解了。

当然，不是把原密码给破出来，而只是找到一个md5结果完全相同的字符序列，来冒充你的密码，当然服务器是区分不出来的。

噢我还漏了个前提，你的服务器得接受输入接近无限长度的密码才行。

或者换一种说法，如果你的密码强度（熵值）远低于这个数量级，那么还不如直接穷举来的方便。

这个破解主要针对的是对文件校验这种熵值比较高的应用场景，就是说，中间人可以通过md5碰撞让你下载到一个错误的文件而误以为真，当然，文件里面可以注入他想注入的东西。而不是说密码加密这种熵值低得多的用例场景。

另外，对于那些以安全为由，还瞧不起SSL，自己发明一个客户端直接计算md5发到服务器进行验证的安(dou)全(be)系统，什么彩虹表什么暴力破解你们都弱爆了，直接运算量为0就搞定，其它就没啥可说的了！