200台PS3可破解安全网页MD5加密算法

200台PS3可破解安全网页MD5加密算法https://www.wendangku.net/doc/b214934062.html, 2008年12月31日 10:04 比特网ChinaByte
2008年12月31日消息，据国外媒体报道，周二，一个来自美国和欧洲的联合研究团队在柏林25C3安全大会上公布论文称，他们利用由200台索尼PlayStation 3组成的超级计算网络已经可以成功破解用于安全网页数字签名的加密算法MD5，并成功伪造安全网页数字证书，由此完全可以伪造安全网页。此前，研究称MD5加密算法至少需要30年时间才能破解一台桌面PC。

通常情况下，在使用浏览器浏览网页时，如果看到页面左下角出现"安全锁"，用户就认为该网页是安全网页。当该加密算法被破解之后，所谓的安全网页可能不再安全。

早在4年前，中国研究人员就曾指出加密算法MD5存在安全漏洞，但根据当时的计算能力，一台桌面PC至少需要30年的时间才能完成破解。但周二公布的研究报告显示，使用索尼PlayStation 3组成的计算网络只要3天就可以完成破解。

虽然MD5加密算法有些过时，但目前仍有部分网站使用MD5加密算法进行数字签名，而且这种签名的验证可以所有浏览器上通过。利用MD5的安全漏洞，就可以建立浏览器无法发现的钓鱼网站，因为浏览器会认为通过MD5验证的网页是安全的。

因此，一些安全研究人员认为，该研究成果的影响非常深远，将对各种浏览器甚至电子邮件、聊天服务器、在线协作等产生影响。

安全专家表示，已经将该情况通报给包括Mozilla和微软在内的主要浏览器厂商。

【推荐文章】：

2004年8月17日的美国加州圣巴巴拉，正在召开的国际密码学会议(Crypto’2004)安排了三场关于杂凑函数的特别报告。在国际著名密码学家Eli Biham和Antoine Joux相继做了对SHA-1的分析与给出SHA-0的一个碰撞之后，来自山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告。在会场上，当她公布了MD系列算法的破解结果之后，报告被激动的掌声打断。王小云教授的报告轰动了全场，得到了与会专家的赞叹。报告结束时，与会者长时间热烈鼓掌，部分学者起立鼓掌致敬，这在密码学会议上是少见的盛况。王小云教授的报告缘何引起如此大的反响?因为她的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准MD5的堡垒轰然倒塌，引发了密码学界的轩然大波。会议总结报告这样写道：“我们该怎么办?MD5被重创了;它即将从应用中淘汰。SHA-1仍然活着，但也见到了它的末日。现在就得开始更换SHA-1了。”

关键词：碰撞=漏洞=别人可以伪造和冒用数字签名。

Hash函数与数字签名(数字手印)

HASH

函数，又称杂凑函数，是在信息安全领域有广泛和重要应用的密码算法，它有一种类似于指纹的应用。在网络安全协议中，杂凑函数用来处理电子签名，将冗长的签名文件压缩为一段独特的数字信息，像指纹鉴别身份一样保证原来数字签名文件的合法性和安全性。在前面提到的SHA-1和MD5都是目前最常用的杂凑函数。经过这些算法的处理，原始信息即使只更动一个字母，对应的压缩信息也会变为截然不同的“指纹”，这就保证了经过处理信息的唯一性。为电子商务等提供了数字认证的可能性。

安全的杂凑函数在设计时必须满足两个要求：其一是寻找两个输入得到相同的输出值在计算上是不可行的，这就是我们通常所说的抗碰撞的;其二是找一个输入，能得到给定的输出在计算上是不可行的，即不可从结果推导出它的初始状态。现在使用的重要计算机安全协议，如SSL，PGP都用杂凑函数来进行签名，一旦找到两个文件可以产生相同的压缩值，就可以伪造签名，给网络安全领域带来巨大隐患。

MD5就是这样一个在国内外有着广泛的应用的杂凑函数算法，它曾一度被认为是非常安全的。然而，王小云教授发现，可以很快的找到MD5的“碰撞”，就是两个文件可以产生相同的“指纹”。这意味着，当你在网络上使用电子签名签署一份合同后，还可能找到另外一份具有相同签名但内容迥异的合同，这样两份合同的真伪性便无从辨别。王小云教授的研究成果证实了利用MD5算法的碰撞可以严重威胁信息系统安全，这一发现使目前电子签名的法律效力和技术体系受到挑战。因此，业界专家普林斯顿计算机教授Edward Felten等强烈呼吁信息系统的设计者尽快更换签名算法，而且他们强调这是一个需要立即解决的问题。

国际讲坛 王氏发现艳惊四座

面对Hash函数领域取得的重大研究进展，Crypto 2004 会议总主席StorageTek高级研究员Jim Hughes 17 日早晨表示，此消息太重要了，因此他已筹办该会成立24年来的首次网络广播(Webcast )。Hughes在会议上宣布：“会中将提出三份探讨杂凑碰撞(hash collisions )重要的研究报告。”其中一份是王小云等几位中国研究人员的研究发现。17日晚，王小云教授在会上把他们的研究成果做了宣读。这篇由王小云、冯登国、来学嘉、于红波四人共同完成的文章，囊括了对MD5、HAVAL-128、 MD4和RIPEMD四个著名HASH算法的破译结果。在王小云教授仅公布到他们的第三个惊人成果的时候，会场上已经是掌声四起，报告不得不一度中断。报告结束后，所有与会专家对他们的突出工作报以长时的热烈掌声，有些学者甚至起立鼓掌以示他们的祝

贺和敬佩。当人们掌声渐息，来学嘉教授又对文章进行了一点颇有趣味的补充说明。由于版本问题，作者在提交会议论文时使用的一组常数和先行标准不同;在会议发现这一问题之后，王小云教授立即改变了那个常数，在很短的时间内就完成了新的数据分析，这段有惊无险的小插曲倒更加证明了他们论文的信服力，攻击方法的有效性，反而凸显了研究工作的成功。

会议结束时，很多专家围拢到王小云教授身边，既有简短的探讨，又有由衷的祝贺，褒誉之词不绝。包含公钥密码的主要创始人R. L. Rivest和A. Shamir在内的世界顶级的密码学专家也上前表示他们的欣喜和祝贺。

国际密码学专家对王小云教授等人的论文给予高度评价。

MD5的设计者，同时也是国际著名的公钥加密算法标准RSA的第一设计者R.Rivest在邮件中写道：“这些结果无疑给人非常深刻的印象，她应当得到我最热烈的祝贺，当然，我并不希望看到MD5就这样倒下，但人必须尊崇真理。”

Francois Grieu这样说：“王小云、冯登国、来学嘉和于红波的最新成果表明他们已经成功破译了MD4、MD5、HAVAL-128、RIPEMD-128。并且有望以更低的复杂度完成对SHA-0的攻击。一些初步的问题已经解决。他们赢得了非常热烈的掌声。”

另一位专家Greg Rose如此评价：“我刚刚听了Joux和王小云的报告，王所使用的技术能在任何初始值下用2^40次hash运算找出SHA-0的碰撞。她在报告中对四种HASH函数都给出了碰撞，她赢得了长时间的起立喝彩，(这在我印象中还是第一次)。…… 她是当今密码学界的巾帼英雄。……(王小云教授的工作)技术虽然没有公开，但结果是无庸质疑的，这种技术确实存在。…… 我坐在Ron Rivest前面，我听到他评论道：‘我们不得不做很多的重新思考了。’”

石破惊天 MD5堡垒轰然倒塌

一石击起千层浪，MD5的破译引起了密码学界的激烈反响。专家称这是密码学界近年来“最具实质性的研究进展”，各个密码学相关网站竞相报导这一惊人突破。

MD5破解专项网站关闭

MD5破解工程权威网站https://www.wendangku.net/doc/b214934062.html,/ 是为了公开征集专门针对MD5的攻击而设立的，网站于2004年8月17日宣布：“中国研究人员发现了完整MD5算法的碰撞;Wang， Feng， Lai与Yu公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术，在数个小时内就可以找到MD5碰撞。……由于这个里程碑式的发现，MD5CRK项目将在随后48小时内结束”。

对此，https://www.wendangku.net/doc/b214934062.html,主页专门转载了该报道https://www.wendangku.net/doc/b214934062.html,/distributed/distrib-recen

t.html和几个其它网站也进行了报道。

权威网站相继发表评论或者报告这一重大研究成果

经过统计，在论文发布两周之内，已经有近400个网站发布、引用和评论了这一成果。国内的许多新闻网站也以“演算法安全加密功能露出破绽 密码学界一片哗然”为题报道了这一密码学界的重大事件。(报导见https://www.wendangku.net/doc/b214934062.html,/perl/board/mboard.pl?board=lnitalkback&thread=895&id=896&display=1&tview=expanded&mview=flat，该消息在各新闻网站上多次转载。)

东方神韵MD5终结者来自中国

MD5破解工作的主要成员王小云教授是一个瘦弱、矜持的女子，厚厚的镜片透射出双眸中数学的灵光。她于1990年在山东大学师从著名数学家潘承洞教授攻读数论与密码学专业博士，在潘先生、于秀源、展涛等多位著名教授的悉心指导下，她成功将数论知识应用到密码学中，取得了很多突出成果，先后获得863项目资助和国家自然科学基金项目资助，并且获得部级科技进步奖一项，撰写论文二十多篇。王小云教授从上世纪90年代末开始进行HASH函数的研究，她所带领的于红波、王美琴、孙秋梅、冯骐等组成的密码研究小组，同中科院冯登国教授，上海交大来学嘉等知名学者密切协作，经过长期坚持不懈的努力，找到了破解HASH函数的关键技术，成功的破解了MD5和其它几个HASH函数。

近年来她的工作得到了山东大学和数学院领导的大力支持，特别投资建设了信息安全实验室。山东大学校长展涛教授高度重视王小云教授突出的科研成果。 2004年6月山东大学领导听取王小云教授的工作介绍后，展涛校长亲自签发邀请函邀请国内知名信息安全专家参加2004年7月在威海举办的“山东大学信息安全研究学术研讨会”，数学院院长刘建亚教授组织和主持了会议，会上王小云教授公布了MD5等算法的一系列研究成果，专家们对她的研究成果给予了充分的肯定，对其坚持不懈的科研态度大加赞扬。一位院士说，她的研究水平绝对不比国际上的差。这位院士的结论在时隔一个月之后的国际密码会上得到了验证，国外专家如此强烈的反响表明，我们的工作可以说不但不比国际上的差，而且是在破解HASH函数方面已领先一步。加拿大CertainKey公司早前宣布将给予发现MD5算法第一个碰撞人员一定的奖励，CertainKey的初衷是利用并行计算机通过生日攻击来寻找碰撞，而王小云教授等的攻击相对生日攻击需要更少的计算时间。

数字认证 你的未来不是梦

由于MD5的破译，引发了关于MD5产品是否还能够使用的大辩论。在麻省理工大学Jeffrey I. Schiller教授主持的个人论坛上，许多密码学家在标题为

“Bad day at the hash function factory”的辩论中发表了具有价值的意见(https://www.wendangku.net/doc/b214934062.html,/pipermail/saag/2004q3/000913.html)。这次国际密码学会议的总主席Jimes Hughes发表评论说“我相信这(破解MD5)是真的，并且如果碰撞存在，HMAC也就不再是安全的了，…… 我认为我们应该抛开MD5了。” Hughes建议，程序设计人员最好开始舍弃MD5。他说：“既然现在这种算法的弱点已暴露出来，在有效的攻击发动之前，现在是撤离的时机。”

同样，在普林斯顿大学教授Edwards Felton的个人网站(https://www.wendangku.net/doc/b214934062.html,/archives/000664.html)上，也有类似的评论。他说：“留给我们的是什么呢?MD5已经受了重伤;它的应用就要淘汰。SHA-1仍然活着，但也不会很长，必须立即更换SHA-1，但是选用什么样的算法，这需要在密码研究人员达到共识。”

密码学家Markku-Juhani称“这是HASH函数分析领域激动人心的时刻。(http://www.tcs.hut.fi/~mjos/md5/)”

而著名计算机公司SUN的LINUIX专家Val Henson则说：“以前我们说"SHA-1可以放心用，其他的不是不安全就是未知"， 现在我们只能这么总结了："SHA-1不安全，其他的都完了"。

针对王小云教授等破译的以MD5为代表的Hash函数算法的报告，美国国家技术与标准局(NIST)于2004年8月24日发表专门评论，评论的主要内容为：“在最近的国际密码学会议(Crypto 2004)上，研究人员宣布他们发现了破解数种HASH算法的方法，其中包括MD4，MD5，HAVAL-128，RIPEMD还有 SHA-0。分析表明，于1994年替代SHA-0成为联邦信息处理标准的SHA-1的减弱条件的变种算法能够被破解;但完整的SHA-1并没有被破解，也没有找到SHA-1的碰撞。研究结果说明SHA-1的安全性暂时没有问题，但随着技术的发展，技术与标准局计划在2010年之前逐步淘汰SHA-1，换用其他更长更安全的算法(如SHA-224、SHA-256、SHA-384和SHA-512)来替代。”

2004年8月28日，十届全国人大常委会第十一次会议表决通过了电子签名法。这部法律规定，可靠的电子签名与手写签名或者盖章具有同等的法律效力。电子签名法的通过，标志着我国首部“真正意义上的信息化法律”已正式诞生，将于2005年4月1日起施行。专家认为，这部法律将对我国电子商务、电子政务的发展起到极其重要的促进作用。王小云教授的发现无异于发现了信息化天空的一个惊人黑洞。我们期待着王小云教授和她的团队能够成就“女娲补天”的壮举，为人类的信息化之路保驾护航。

MD5是在Web应用程序中最常用的密码加密算法。由于MD5是不可逆的，因而经过MD5计算得到后的密文，不能通过逆向算法得到原文。

回顾在Web应用程序中使用MD5加密文本密码的

初衷，就是为了防止数据库中保存的密码不幸泄露后被直接获得。但攻击者不但拥有数据量巨大的密码字典，而且建立了很多MD5原文/密文对照数据库，能快速地找到常用密码的MD5密文，是破译MD5密文的高效途径。然而，MD5密文数据库所使用的是最常规的MD5加密算法:原文-->MD5-->密文。因此，我们可以使用变换的MD5算法，使现成的MD5密文数据库无所作为。

下面演示一些变换算法的例子，当然，在其它的Web开发语言中，也大同小异，完全能得到相同的结果。

变换一：循环MD5

最容易理解的变换就是对一个密码进行多次的MD5运算。自定义一个函数，它接受$data和$times两个形参，第一个是要加密的密码，第二个是重复加密的次数。实现这种变换有两种算法：

//迭代算法

function md5_1_1($data， $times = 32)

{

//循环使用MD5

for ($i = 0; $i < $times; $i++) {

$data = md5($data);

}

return $data;

}

//递归算法

function md5_1_2($data， $times = 32)

{

if ($times > 0) {

$data = md5($data);

$times--;

return md5_1_2($data， $times); //实现递归

} else {

return $data;

}

}

?>

变换二:密文分割MD5

尽管用户的密码是不确定的字符串，但是只要经过一次MD5运算后，就会得到一个由32个字符组成的字符串，这时可以再针对这个定长字符串变换。有点BT的算法是，把这段密文分割成若干段，对每段都进行一次MD5运算，然后把这堆密文连成一个超长的字符串，最后再进行一次MD5运算，得到仍然是长度为32位的密文。

//把密文分割成两段，每段16个字符

function md5_2_1($data)

{

//先把密码加密成长度为32字符的密文

$data = md5($data);

//把密码分割成两段

$left = substr($data， 0， 16);

$right = substr($data， 16， 16);

//分别加密后再合并

$data = md5($left).md5($right);

//最后把长字串再加密一次，成为32字符密文

return md5($data);

}

//把密文分割成32段，每段1个字符

function md5_2_2($data)

{

$data = md5($data);

//循环地截取密文中的每个字符并进行加密、连接

for ($i = 0; $i < 32; $i++) {

$data .= md5($data{$i});

}

//这时$data长度为1024个字符，再进行一次MD5运算

return md5($data);

}

?>

当然，这种密文分割的具体算法是数之不尽的，比如可以把原密文分割成16段每段两字符、8段每段4字符，或者每一段的字符数不相等……

变换三:附加字符串

干涉

在加密过程的一个步骤中，附加一个内容确定的字符串(比如说用户名)，干涉被加密的数据。不可以用随机字串，因为这样会使原算法无法重现。这种算法在某些情况下是很具有优势的，比如说用于大量的用户密码加密，可以把用户名作为附加干涉字串，这样攻击者就算知道你的算法，也很难从他们手中的字典中一下子生成海量的对照表，然后大量地破译用户密码，只能有针对性的穷举为数不多的用户。

//附加字符串在原数据的尾部

function md5_3_1($data， $append)

{

return md5($data.$append);

}

//附加字符串在原数据的头部

function md5_3_2($data， $append)

{

return md5($append.$data);

}

//附加字符串在原数据的头尾

function md5_3_3($data， $append)

{

return md5($append.$data.$append);

}

?>

变换四:大小写变换干涉

由于PHP所提供的md5()函数返回的密文中的英文字母全部都是小写的，因此我们可以把它们全部转为大写，然后再进行一次MD5运算。

function md5_4($data)

{

//先得到密码的密文

$data = md5($data);

//再把密文中的英文母全部转为大写

$data = strtotime($data);

//最后再进行一次MD5运算并返回

return md5($data);

}

?>

变换五:字符串次序干涉

把MD5运算后的密文字符串的顺序调转后，再进行一次MD5运算。

function md5_5($data)

{

//得到数据的密文

$data = md5($data);

//再把密文字符串的字符顺序调转

$data = strrev($data);

//最后再进行一次MD5运算并返回

return md5($data);

}

?>

变换六、变换七、变换八……

MD5变换算法是数之不尽的，甚至无须自己再去创造，就用上面的五个互相组合就可以搞出很BT的算法。比如说先循环加密后再分割，并在每一段上附加一个字符串再分别加密，然后变换大小写并颠倒字符串顺序后连成一个长字符串再进行MD5运算……

如果真的很不幸，由于某些漏洞，比如说SQL Injection或者文件系统中的数据库被下载而异致用户密码数据暴露，那么MD5变换算法就能大大地增加破译出密码原文的难度，首先就是使网上很多的MD5原文/密文对照数据库(要知道，这是破译MD5最高效的方法)没有用了，然后就是使攻击者用常规算法去穷举一串由变换算法得到的密文而搞得焦头烂额。当然，MD5变换算法特别适合用于非开源的Web程序使用，虽说用在开源的程序中优势会被削弱(大家都知道算法)，但是也能抑制MD5原文/密文对照

数据库的作用。要进行这些复杂的变换运算，当然就要花费的更多的系统开销了，然而对于安全性要求很严格的系统来说，多付出一些来换取高一点的安全性，是完全值得的。


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

通信密码学前瞻:量子密码技术A Bright Outlook for Communication Encryption:Quantum Cryptography


<<上海大学学报(自然科学版)JOURNAL OF SHANGHAI UNIVERSITY(NATURAL SCIENCE)>>2000年第6卷第2期
作者: 熊红凯, 施惠昌, 戴善荣


学术期刊 QCode : shdxxb200002014
此文讨论了量子加密的相关研究及实用化实验模型,详细说明了量子密钥分发协议,对量子密码体制进行了预想.
关键词: "Catch 22"问题, 量子密钥分发, 海森伯格测不准原理, 本征态, 不对易 | 全部关键词