主题：【文摘】山东大学王小云教授成功破解MD5 -- 懒厨

MD5碰撞，及相关解释

摘自［坐看云起－Brian的博客］

http://www.kantianxia.net/blog/briancai/index.php?subaction=showfull&id=1094839036&archive=&cnshow=news&start_from=&ucat=1&

2004年8月17日，在美国加州圣巴巴拉召开的国际密码学会议（Crypto’2004）上，来自山东大学的王小云教授做了MD5、HAVAL-128、 MD4和RIPEMD碰撞的报告。

这篇文章随即在密码学界引起了巨大的反响。甚至有个专家说，这天是：“Bad day at the hash function factory”。（当然，这句话还包括了当天的另外两个碰撞的报告）

一、王小云等人的工作是什么？

通常，我们把一段明文，通过一个MD5(HASH函数)运算，得到一个所谓的密文。那么，在实际中是怎么应用的呢？

这里举一个简单的说明，通常的网站的密码认证都是这样的。

用户通过网页注册用户名和密码。服务器在获得密码后，会把这个用户设置的密码用MD5函数做个运算，然后把这个运算结果存放到数据库中。

当下次用户登录网站的时候，用户通过网页提交了用户名和密码。服务器程序会把这个密码用MD5加以运算，然后在数据库中查找，是否存在这个用户名和这个MD5过的密码。如果存在，那就认为该用户通过了认证。

我们都知道，MD5这种加密算法是不可逆的。既没有办法从密文简单地通过某种算法得到原来的明文。

那么，王小云的这个论文讲的是什么呢？

MD5虽然没有相对应的可逆算法。但有一种情况，就是可能有两个或多个明文，通过MD5运算后，得到相同的密文。这些相同的明文就叫做碰撞。

显而易见，由于碰撞的存在，使得解密的可能性大增。（通常解密的方法是一种叫“暴力法Brute Force”，就是通过计算机，尝试每一种可能性，从而得到密码）。注意，碰撞可能并不是原始密码，而是被认证程序误认为是密码。

因此，密码界把重要的经历放在怎样寻找碰撞上而不是找到可逆算法。

王小云的工作就是找到了一种算法，能在比较短的时间内，找到某段密文的碰撞的算法。按照她论文中的说法，是在IBM P690上，大概一个小时就找到了其中的M，随后在几秒到15分钟，找到了其中的N。

这里是那篇文章，你可以下载下来仔细研究。

http://eprint.iacr.org/2004/199.pdf

二、这会给我们的安全问题带来什么？

那么，我们看看，这回带给我们什么麻烦，或对目前的基于MD5算法的安全性带来什么样的影响？注意，我这里仅探讨三种情况。其他的，都可以按照这些思路分析。

１）用户密码认证

就是前面提到的那种情况，如果刚好这个数据库中存放的密文被破坏者得到的话，那么可以得到相应的碰撞。也就是说，类似于找到了密码。

２）数字签名方面

这通常的应用是这样的。比如从某个网站下载一个文件或软件。通常，这个网站还提供了一个相应的MD5值。即这个文件或软件经过MD5运算后的结果。

这样，当我们下载到本地后，可以对这个文件或软件进行MD5运算。如果结果和网站提供的MD5值是一样的话，就认为这个文件是正确的。

通常，这种方法用来保证文章或软件的来源。

那么，如果找到了一个碰撞，使得有同样的MD5值。也就是说，找到一个可以冒充原来的文件或软件的东西。

其实，我们都知道，即使在实际中找到了这样一个东西，其现实意义恐怕并不大。因为，即使找到了这样的碰撞，而这些碰撞所代表的信息是否有实际含义，还是一个未知数。比如一个软件相对应的碰撞是否还是一个可以运行的软件，那就很难说。同样，一篇文章的碰撞是否还是一篇有实际意义的文章也很难说。

３）数字证书

所谓的数字证书可以看成是上面这种情况的一个特例。即是通过第三方机构签名的包含被认证方信息的密文。

由于受到第三方的控制，存在被攻破的机会要比上面说的要小。

尽管通过分析，可以发现，找到了碰撞可能并没有给安全带来很大的影响。但无论如何，使得MD5存在了被攻破的更大的可能性。

不管怎么说，王小云等人的这一系列工作有重大的意义。这让我们又一次体验奥运会田径项目突破带来的喜悦，不过这次是在信息安全科学上的突破。