浅谈MD5和SHA-1被破解和应用改进策略

2004年8月17日在美国加州圣巴巴拉举行了一次国际密码学学术年会（Crypto’2004）,当晚来自中国山东大学的王小云教授做了关于破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告。当她公布了破解结果之后，报告被激动的掌声打断,引起了全场的轰动。

会议结束后，很多专家来到王小云教授身边向她表示祝贺,连世界顶尖级的密码学大师Rivest和Shamir也上前表示他们的欣喜和祝贺，世界信息安全方面的专家们对王小云教授等人的论文给予高度评价，MD5的设计者和著名的公钥密码系统RSA的第一设计者Rivest在邮件中写道：“这些结果无疑给人非常深刻的印象，她应当得到我最热烈的祝贺，当然，我并不希望看到MD5就这样倒下，但人必须尊崇真理。”为了公开征集专门针对MD5的攻击而设立的MD5破解工程权威网站http://www.md5crk.com/ 随后关闭。在该次学术年会总结报告这样写道：“我们该怎么办？MD5被重创了；它即将从应用中淘汰。SHA-1仍然活着，但也见到了它的末日。现在就得开始更换SHA-1了。”但是，不久，王小云教授又宣布SHA-1也被破解。

王小云教授的报告为什么能够引起如此大的反响？因为她的成果作为密码学领域的重大发现宣告了通常被认为是非常安全的MD5算法轰然倒塌，引发了密码学界的一场地震。

1 MD5和SHA-1算法简单介绍

MD5和SHA-1算法的核心是哈希函数。密码学哈希函数(Cryptography Hash Function，简称为哈希函数)又称杂凑函数，是在信息安全领域有广泛和重要应用的密码算法，主要作用是数据完整性验证和消息认证。它有一种类似于指纹的应用,所以有时候我们也把它叫做“数字指纹”。因为它具有以下特性：原始信息只要改变一点点，哪怕是几比特，对应的消息摘要也会改变很大。

哈希函数把任意有限长的输入行映射到固定长的行。哈希函数的值域与定义域相比规模要小得多，它是“多对一”的映射，因此可能会发生碰撞。所谓碰撞(Collision)是指定义域的两个不同元素x1、x2映射到同一个消息摘要，即h(x1)=h(x2)，也就是存在不同的消息具有相同的消息摘要。

从信息论的观点看，哈希函数存在碰撞是必然的，这一点在数学上可以严ge的证明。因此安全的杂凑函数在设计时必须满足两个要求：其一是寻找两个输入得到相同的输出值在计算上是不可行的，这就是我们通常所说的抗碰撞的；其二是找一个输入，能得到给定的输出在计算上是不可行的，即不可从结果推导出它的初始状态。现在使用的重要计算机安全协议，如SSL，PGP都用杂凑函数来进行签名，一旦找到两个文件可以产生相同的压缩值，就可以伪造签名，给网络安全领域带来巨大隐患。哈希算法的安全性从理论上来说与消息摘要的长度是成正比的，对于具有128位消息摘要的MD5，要在短时间内寻找到一组碰撞在计算上是比较困难的，而国际标准安全哈希算法( Secure Hash Algorithm, 简称SHA)是具有160位消息摘要，如果要找到一组碰撞在计算上更困难。

MD5它曾一度被认为是非常安全的，各国著名密码学家、数学家和顶级黑客们对它进行了多年的密码学分析和攻击，曾提出的著名的“生日攻击”和“袋鼠攻击”等一系列攻击方法，但是在实质上没有突破性的进展，因此MD5经受住了多年的考验，同时又由于因为它易于实现，算法理解相对也比较简单，所以在国内外有着非常广泛的应用。但是王小云教授发现的这种方法，可以很快的找到MD5的“碰撞”，使得两个文件可以产生相同的“指纹”。这意味着什么？意味当当你在网络上使用电子签名签署一份合同后，还可能找到另外一份具有相同签名但内容迥异的合同，这样两份合同的真伪性便无从辨别，你很有可能要背负黑锅了。她的这项研究成果证实了利用MD5算法的碰撞可以严重威胁信息系统安全，这一发现使目前电子签名的法律效力和技术体系受到挑战，下面我们将具体谈谈这次发现对社会各方面的影响。

对网络系统安全的影响

学习黑客技术的人都知道，黑客攻击网络系统的最高目标是获得超级用户权限，因为获得超级用户权限那你就可以为所欲为。典型的为了获得系统权限的攻击方法主要有以下几大类：

（1） 缓冲区溢出，这是目前我觉得最有研究深度和价值的一种黑客技术；

（2） 木马技术与社交工程，这两种技术相信朋友们都很清楚是怎么回事，相信有不少朋友通过这种手段知道了MM的QQ和邮箱密码；

（3） 端口监听和网络截获，难度很高，成功的可能性也不太大，但成功后威胁性很大；

（4） 病毒与蠕虫；

（5） 暴力破解，攻击的最后的希望了！

由于一些网络系统的口令验证是这样设计的：系统保留的是用户密码经过加密算法MD5得到的消息摘要，而不保留用户密码本身，验证用户身份时，只需要将用户输入的密码再次用MD5生成消息摘要，与记录的MD5消息摘要作一个比较即可验证其密码的合法性。例如采用这种口令验证技术的系统有Linux和某些UNIX，另外一些网络应用系统也是采用的这种方法。

从理论上来说，如果我们要攻击Linux系统，只要得到用户密码文件（其中记录了密码的MD5），然后随便生成一个碰撞的密码（不一定要跟原密码相同），就可以用这个密码登录了，超级用户密码也不例外。以前做到这一点是非常困难的，而现在王小云教授的成果已经完全使Linux用的那种基于MD5的身份验证技术失效了，而且攻击成功后可以嫁祸于人，这使得Linux的安全神话再次打破。攻击基本思路如下：首先获得一个普通用户权限，再通过普通用户权限对存在缓冲区漏洞的某些程序进行缓冲区溢出，进行权限提升，最终获得超级用户权限，寻找到/etc/passwd和/etc/shadow文件，开始破解吧！按照王小云教授的方法你将获得包括ROOT口令在内的所有口令，当然这些口令不一定与原口令相同，但是可以用合法的原用户名和这种口令大摇大摆登陆系统。这样，你无需担心在系统中添加新用户被系统管理员发觉，而且你做了什么不光彩的事情会有人帮你背黑锅！

另外一个例子就是论坛系统，很多网上论坛采用的就是这种技术。基于ASP、PHP、JSP的各种论坛的漏洞很多，攻击手法更是层出不穷，比如很多人常用的SQL注入技术，因此获得含有用户名与密码消息摘要的数据表信息并不是件非常艰难的事情！如果有一天，在论坛上的有很高声望和名声