关于MD5算法破解对实际应用影响的讨论

关于MD5算法破解对实际应用影响的讨论

国家信息中心信息安全研究与服务中心　

李丹

北京天威诚信电子商务服务有限公司　龙毅宏

摘要：

在2004国际密码学会议（Crypto’2004）上，

王

小云

教授公布了破解MD5算法的研究成果，引起了密码学界轰动，国内有些媒体甚至认为这一破解会导致数字签名安全大厦的轰然倒塌，那么，实际情况究竟是怎样的呢？本文就MD5算法破解对实际应用的影响进行分析讨论，回答了这个问题。

正文：

在2004年8月17日美国加州圣巴巴拉召开的国际密码学会议（Crypto’2004）上，来自中国山东大学的王小云教授做了破解MD5算法的报告。当她公布了她的研究结果之后，会场上响起激动的掌声。王小云教授的报告轰动了全场，得到了与会专家的赞叹。国内有些媒体甚至认为这一破解会导致数字签名安全大厦的轰然倒塌。那么，实际应用的情况究竟是怎样的呢？

    MD5是一种散列算法(Hash function)，又称为哈希算法、消息摘要算法，它的作用是获取数字信息的特征(我们有时称之为“信息指纹)。一个任意长度的任意数字信息，通过散列算法运算后，会产生一串固定长度(比如160bit)的数字信息，称为散列值(或哈希值、消息摘要)。安全的散列算法有这样的特点：

⑴ 两个不同数字信息产生同样的散列值的概率是非常小的(小到现实中几乎无法发生)；

⑵ 仅从散列值无法演推出原信息；

⑶ 原信息的微小改变，哪怕只改变一位(bit)，将导致散列值的很大变化。

数字签名要使用散列值。MD5是一种常用散列算法，另外目前常用的散列算法还有SHA-1。两个不同的数字信息产生相同的散列值就是人们所说的“散列值碰撞“。散列算法是一个将无穷维空间的信息映射到有限维空间的变换，学过数学的人都知道这不是一个一一对应的变换。实际上一个散列值可能对应有无穷多个数字信息，换言之，会有无穷多个数字信息产生同样一个散列值。这点是研究密码的人众所周知的，而不像有些媒体所说的那样，散列值是唯一的。

一个安全散列算法的安全性是基于这样的假设，知道一个信息A的散列值H，很难找到，或者从H倒推出另一个信息B具有同样的散列值H。中国学者的发现是这样的，对于MD5散列算法，针对某些信息集合，找到了一种方法，当我们知道它的散列值H时，能推出一个信息数据B具有同样的MD5散列H。需要强调的是，王小云教授的破解算法是一个概率性的破解算法，只对部分信息集合适用。这当然是密码学界的一个重大发现，这说明了MD5不像我们原先认为的那样安全。但是，这个研究发现的实际影响要远远小于它的理论意义。这可以从以下几方面加以说明。

根据MD5破解算法，对一个信息A及其散列值H，我们有可能推出另一个信息B，它的MD5散列值也是H 。现在的问题是，如果A是一个符合预先约定格式的、有一定语义的信息，那么演推出的信息B将不是一个符合约定格式、有语义的信息。比如说，A是一个甚于Word文档的、有语义的电子合同，而B却不可能是一个刚好符合Word格式的文档，只能是一堆乱码，也就是说，B不可能是一个有效的、有意义的并且符合伪造者期望的电子合同。再比如说，A是一个符合X509格式的数字证书，那么我们推出的B不可能刚好也是一个符合X509格式而且是伪造者希望的数字证书。

还有我们知道，电子合同是需要双方、甚至多方电子签名的。对于双方签名，这相当于我们先产生A的散列值H1，然后对A和H1合起来的信息进一步产生散列值H2。我们目前的研究发现还无法找到一个方法，推出一个信息B刚好产生同样的H1和H2。（这个B是一定存在的!只是目前不知道怎样找!)

其次，MD5被破解了，我们现在还有SHA-1等其他散列算法，以后还可以有新的、更安全的散列算法。

总之，这里MD5算法的破解对实际应用的冲击要远远小于它的理论意义，不会造成PKI、数字签 名安全体系的崩溃，这也是为什么MD5散列算法的破解并没有造成密码界、PKI行业的恐慌的原因。当然，我们也为中国人在密码学上取得的杰出成就起立鼓掌。

参考文献

【1】       2004国际密码学会议（Crypto’2004）破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告　王小云等

【2】       应用密码学，Bruce Schneier著，吴世忠等译。