山东大学王小云教授震惊美国-破解全球两大密码算法！

aizy_cn

香港大公报：山大女教授破译「白宫密码」
  U) W, A' z# D; j" v继去年8月份成功破解了应用广泛的HASH函数MD5震惊整个国际密码学界之后，日前，山东大学王小云教授三人又顺利完成了SHA-1的破译工作，再次震惊世界。
: c0 w3 m4 n; L& G0 v  f, p; Y6 f     2004年8月，在美国国际密码会议上，王小云教授成功破解MD5曾引起国际专家震惊。去年12月，王小云教授与其博士生于红波以及另外一位研究人尹依群立刻全力以赴投入到破解SHA-1的研究工作中，2月14日，王教授的密码小组顺利完成了SHA-1的破译工作，并将该结果公布。
% \* j  _/ d8 b3 A$ a9 J     记者日前在山东大学信息安全实验室采访了王小云教授。王小云教授告诉记者，MD5是由国际著名密码学家图灵奖获得者兼RSA的第一设计者Rivest设计，SHA-1则是由美国标准技术所NIST与美国国家安全局NSA设计的HASH函数标准算法，早在1994年便为美国政府采纳，现为美政府广泛利用的计算机密码系统，也被人们称为「白宫密码」。两大算法也是目前国际电子签名及许多其它密码应用的关键技术。
- Q2 Q$ L' _& [  u" A, i     关于SHA-1被破的消息引起了国际社会尤其是国际密码学领域的极大反响。2月15日，在美国洛杉矶召开的万人参加的RSA年会上，Rivest,　Shamir,　Diffie等五位世界顶级密码学家在密码学家讨论板块上（paneldiscussion）公布了王小云教授关于SHA-1的破译结果，并给予了高度评价。Shamir评论说：「这是近几年密码学领域最美妙的结果（most　wonderful）」。Rivest评论道说：「数字签名的安全性在降低，这再一次提醒需要替换算法」。记者从美国《华盛顿时报》报道中了解到，美国国家标准与技术研究院已经表示，为配合先进的计算机技术，美国政府五年内将不再使用SHA-1，并计划在2010年改用先进的SHA-224、SHA-256、SHA-384及SHA-512的密码系统。  
王小云教授曾师从著名解析数论专家潘承洞院士，1993年以来一直致力于密码算法的分析与设计的研究。王小云教授提出的「比特追踪法」对SHA-1的破解工作取得突破性进展，为密码分析技术开辟一条新思路，进一步提升了我国信息安全领域的国际地位。对于外界流传的是否可以利用密码技术「攻击白宫」一类问题，王小云教授回应说，自己只是纯密码分析人员，不是「黑客」，外界很多报道并不准确。SHA-1的破译肯定会带来一些潜在的危机，但她认为这会进一步提高密码安全，促进整个信息安全行业的长期健康发展。

aizy_cn

来自美国《华尔街日报》的报道

3月15日，美国《华尔街日报》在头版刊登了该报报记者查尔斯.方莱尔（Charles Forelle）采写的专题报道，介绍了我校王小云教授的有关科研成果。转载如下：
     
     网络安全问题已经令人们十分担心，最近，在广泛应用于网络加密技术的SHA-1上发现的漏洞，又为政府机构和计算机密码专家们亮起了一盏红灯。
% E" ]& g' V4 s& D2 `0 u     多年来，网站运营者一直用“hash 函数”这项技术把在线传送的数据打乱，如信用卡信息、社会保险号和其他的一些敏感数据。对于每天在Internet上进行的上百万的交易，hash函数都在发生着作用。这个系统，即一个算法，或者说是数学公式，曾被认为是不可攻破的。
     但是上个月，来自中国华东地区山东大学的一个研究小组发布了一篇文章的草稿。文章显示，一个用于最先进加密技术的hash函数密钥并不像想象的那样能够抵御攻击。
& \3 w. W7 Z0 z7 ]9 \     Hash函数给文档或数据产生数字指纹。有了这些指纹，hash的唯一性使hash函数成为信息身份认证的强有力的工具。
中国的研究小组还没有发表关于SHA-1的论文，但是漏洞是“确实存在的”，Bruce Schneier（密码学家，Counterpane网络安全公司的技术主管）曾经看过论文的草稿，他说：“从学术的角度，他们的工作确实令人震惊！”
     中国的科学家“还没有引起骚动”，来自Johns Hopkins大学的计算机安全专家Avi Rubin说：“但那确实敲响了警钟！”
' u6 f6 V7 i' s+ j0 t     这项发现紧跟在日前发现其他hash函数漏洞的研究之后，这时，一些不涉及hash函数的问题使得人们大大地提高了对信息安全的关注程度。

aizy_cn

美国国家标准技术研究院和几大知名公司也做出积极反应。
     
     希捷科技（Seagate Technology）的一位安全问题研究总监Mark Willet表示，“现在美国国家标准技术研究院可能需要将更新密码的日程提前。”
  m3 z# d$ a/ p1 `+ Q     
8 c5 Z4 P; N, a0 ]9 L. V1 N8 t     此外，微软、SUN和Atmel等几家知名公司的专家也发表了他们的应对之策。一位美国律师协会顾问说：“中国的这几位研究人员太疯狂了。”
     
     幕后不可思议的女子解码团队
     
     让世界震惊的是，绝大多数密码专家认为固若金汤的两大密码算法，最终被一位中国女子带领的女子团队无情地击倒，而且这个过程看起来似乎并不是太难，SHA－1的破解只用了两个多月的时间，很多密码学界的专家认为“这听起来简直有些不可思议”。
     
! @6 P. L6 P7 u- |! W1 k  d* R: u: F     王小云1990年在山东大学师从著名数学家潘承洞教授攻读数论与密码学专业博士，在潘承洞、于秀源、展涛等多位名师的指导下，她成功将数论知识应用到密码学中，并从上世纪90年代末开始进行Hash函数的研究。
% L; L. h% q+ B0 U7 d; |     
     王小云在成功之前一直默默无闻，同行评价她，从不急功近利，没有新思想新进展的论文她是绝对不主张发表的，平时对一些耽误研究工作时间的荣誉或应酬也没有热情。她不赞同大批量的阅读文献，主张抓住几篇经典的论文仔细研究，吃透论文思想，然后自己独立思考，寻找突破性的方法，迅速将自己的方法进行实验。她就是这样周而复始地在数字王国里进行着钻研。
     
8 D/ W! u; o( r4 `     参与破译密码SHA－1的研究小组是以王小云为首的一支3人女子团队，其中包括王小云的一名博士生于红波，另一位合作者是来自清华大学的一位女研究人员。“我的8名博士生里面有6个是女性，她们在密码学领域表现出不凡的才能。很多人觉得密码学是很玄妙的学问，而我们觉得它非常有趣。因为我们习惯于用数学方式思维，而一旦养成了这种思维方式，数字在我们眼中就变成了美妙的音符，我们的研究就象音乐创作一样有趣。”王小云说

aizy_cn

齐鲁晚报：
% B% V# O6 D3 @' c
2 U/ g0 W$ d- m7 n- [5 u山东大学王小云教授带领的密码研究小组继去年成功破解世界通行密码标准ＭＤ５后，近日，又破解了应用更为广泛的另一密码标准ＳＨＡ－１，这既是我国也是国际密码学领域取得的一次突破性进展。
     去年８月，王小云率领的科研小组成功破解ＭＤ５，当时ＳＨＡ－１还被国际密码界认为是牢不可破的，今年２月７日，美国国家技术标准局负责人曾发表声明：“ＳＨＡ－１没有被攻破，并且没有足够的理由怀疑它很快被攻破。”但７天后，在美国召开的国际信息安全ＲＳＡ研讨会上，５位国际权威密码专家又重新宣布了王小云的研究结果。
     据悉，目前世界上大多数电子商务和电子政务都通用ＭＤ５和ＳＨＡ－１两个密码系统。相比ＭＤ５而言，ＳＨＡ－１在世界尤其是美国应用更为广泛，保密性能也更好。

aizy_cn

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

　　关键词：碰撞＝漏洞＝别人可以伪造和冒用数字签名。
, \, F( S' m% L1 B+ p( g6 F

　　Hash函数与数字签名（数字手印）
4 Z1 P# u) N) _3 D　　HASH函数，又称杂凑函数，是在信息安全领域有广泛和重要应用的密码算法，它有一种类似于指纹的应用。在网络安全协议中，杂凑函数用来处理电子签名，将冗长的签名文件压缩为一段独特的数字信息，像指纹鉴别身份一样保证原来数字签名文件的合法性和安全性。在前面提到的SHA-1和MD5都是目前最常用的杂凑函数。经过这些算法的处理，原始信息即使只更动一个字母，对应的压缩信息也会变为截然不同的“指纹”，这就保证了经过处理信息的唯一性。为电子商务等提供了数字认证的可能性。
3 R* L& }+ L, T" V　　安全的杂凑函数在设计时必须满足两个要求：其一是寻找两个输入得到相同的输出值在计算上是不可行的，这就是我们通常所说的抗碰撞的；其二是找一个输入，能得到给定的输出在计算上是不可行的，即不可从结果推导出它的初始状态。现在使用的重要计算机安全协议，如SSL，PGP都用杂凑函数来进行签名，一旦找到两个文件可以产生相同的压缩值，就可以伪造签名，给网络安全领域带来巨大隐患。
　　MD5就是这样一个在国内外有着广泛的应用的杂凑函数算法，它曾一度被认为是非常安全的。然而，王小云教授发现，可以很快的找到MD5的“碰撞”，就是两个文件可以产生相同的“指纹”。这意味着，当你在网络上使用电子签名签署一份合同后，还可能找到另外一份具有相同签名但内容迥异的合同，这样两份合同的真伪性便无从辨别。王小云教授的研究成果证实了利用MD5算法的碰撞可以严重威胁信息系统安全，这一发现使目前电子签名的法律效力和技术体系受到挑战。因此，业界专家普林斯顿计算机教授Edward Felten等强烈呼吁信息系统的设计者尽快更换签名算法，而且他们强调这是一个需要立即解决的问题。

+ |5 S( k7 e4 B+ q5 B8 V　　国际讲坛　王氏发现艳惊四座
　　面对Hash函数领域取得的重大研究进展，Crypto 2004 会议总主席StorageTek高级研究员Jim Hughes 17 日早晨表示，此消息太重要了，因此他已筹办该会成立24年来的首次网络广播（Webcast ）。Hughes在会议上宣布：“会中将提出三份探讨杂凑碰撞（hash collisions ）重要的研究报告。”其中一份是王小云等几位中国研究人员的研究发现。17日晚，王小云教授在会上把他们的研究成果做了宣读。这篇由王小云、冯登国、来学嘉、于红波四人共同完成的文章，囊括了对MD5、HAVAL-128、 MD4和RIPEMD四个著名HASH算法的破译结果。在王小云教授仅公布到他们的第三个惊人成果的时候，会场上已经是掌声四起，报告不得不一度中断。报告结束后，所有与会专家对他们的突出工作报以长时的热烈掌声，有些学者甚至起立鼓掌以示他们的祝贺和敬佩。当人们掌声渐息，来学嘉教授又对文章进行了一点颇有趣味的补充说明。由于版本问题，作者在提交会议论文时使用的一组常数和先行标准不同；在会议发现这一问题之后，王小云教授立即改变了那个常数，在很短的时间内就完成了新的数据分析，这段有惊无险的小插曲倒更加证明了他们论文的信服力，攻击方法的有效性，反而凸显了研究工作的成功。
; E$ c0 x8 |( r* J) F　　会议结束时，很多专家围拢到王小云教授身边，既有简短的探讨，又有由衷的祝贺，褒誉之词不绝。包含公钥密码的主要创始人R. L. Rivest和A. Shamir在内的世界顶级的密码学专家也上前表示他们的欣喜和祝贺。
　　国际密码学专家对王小云教授等人的论文给予高度评价。
& ~1 p& E9 F1 V4 ~# R　　MD5的设计者，同时也是国际著名的公钥加密算法标准RSA的第一设计者R．Rivest在邮件中写道：“这些结果无疑给人非常深刻的印象，她应当得到我最热烈的祝贺，当然，我并不希望看到MD5就这样倒下，但人必须尊崇真理。”
　　Francois Grieu这样说：“王小云、冯登国、来学嘉和于红波的最新成果表明他们已经成功破译了MD4、MD5、HAVAL-128、RIPEMD-128。并且有望以更低的复杂度完成对SHA-0的攻击。一些初步的问题已经解决。他们赢得了非常热烈的掌声。”
1 k* o3 L3 r: `3 I　　另一位专家Greg Rose如此评价：“我刚刚听了Joux和王小云的报告，王所使用的技术能在任何初始值下用2^40次hash运算找出SHA-0的碰撞。她在报告中对四种HASH函数都给出了碰撞，她赢得了长时间的起立喝彩，（这在我印象中还是第一次）。…… 她是当今密码学界的巾帼英雄。……（王小云教授的工作）技术虽然没有公开，但结果是无庸质疑的，这种技术确实存在。…… 我坐在Ron Rivest前面，我听到他评论道：‘我们不得不做很多的重新思考了。’”
+ _0 W' T9 u8 c6 w/ j) w
; t1 v9 k- f/ R- K　　石破惊天　MD5堡垒轰然倒塌
3 Z  Z+ F6 l8 K; ?, ~! C# G　　一石击起千层浪，MD5的破译引起了密码学界的激烈反响。专家称这是密码学界近年来“最具实质性的研究进展”，各个密码学相关网站竞相报导这一惊人突破。
- w* z+ z$ T5 f1 s( i) I　　MD5破解专项网站关闭
$ A2 E* H- E' k& I! J/ N3 e　　MD5破解工程权威网站http://www.md5crk.com/ 是为了公开征集专门针对MD5的攻击而设立的，网站于2004年8月17日宣布：“中国研究人员发现了完整MD5算法的碰撞；Wang, Feng, Lai与Yu公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术，在数个小时内就可以找到MD5碰撞。……由于这个里程碑式的发现，MD5CRK项目将在随后48小时内结束”。
: Q1 |" N% P8 g1 G' `　　对此，http://www.readyresponse.org主页专门转载了该报道http://www.aspenleaf.com/distributed/distrib-recent.html和几个其它网站也进行了报道。
　　权威网站相继发表评论或者报告这一重大研究成果
　　经过统计，在论文发布两周之内，已经有近400个网站发布、引用和评论了这一成果。国内的许多新闻网站也以“演算法安全加密功能露出破绽 密码学界一片哗然”为题报道了这一密码学界的重大事件。（报导见http://www.technewsworld.com/perl/board/mboard.pl?board=lnitalkback&thread=895&id=896&display=1&tview=expanded&mview=flat,该消息在各新闻网站上多次转载。）
4 n& i% ?  N/ J+ G6 _9 R. L
$ a' ~& F: U" T' [  K6 \% }　　东方神韵　 MD5终结者来自中国
　　MD5破解工作的主要成员王小云教授是一个瘦弱、矜持的女子，厚厚的镜片透射出双眸中数学的灵光。她于1990年在山东大学师从著名数学家潘承洞教授攻读数论与密码学专业博士，在潘先生、于秀源、展涛等多位著名教授的悉心指导下，她成功将数论知识应用到密码学中，取得了很多突出成果，先后获得863项目资助和国家自然科学基金项目资助，并且获得部级科技进步奖一项，撰写论文二十多篇。王小云教授从上世纪90年代末开始进行HASH函数的研究，她所带领的于红波、王美琴、孙秋梅、冯骐等组成的密码研究小组，同中科院冯登国教授，上海交大来学嘉等知名学者密切协作，经过长期坚持不懈的努力，找到了破解HASH函数的关键技术，成功的破解了MD5和其它几个HASH函数。
& R7 w7 Q8 t$ K/ m% c, k0 Q　　近年来她的工作得到了山东大学和数学院领导的大力支持，特别投资建设了信息安全实验室。山东大学校长展涛教授高度重视王小云教授突出的科研成果。 2004年6月山东大学领导听取王小云教授的工作介绍后，展涛校长亲自签发邀请函邀请国内知名信息安全专家参加2004年7月在威海举办的“山东大学信息安全研究学术研讨会”，数学院院长刘建亚教授组织和主持了会议，会上王小云教授公布了MD5等算法的一系列研究成果，专家们对她的研究成果给予了充分的肯定，对其坚持不懈的科研态度大加赞扬。一位院士说，她的研究水平绝对不比国际上的差。这位院士的结论在时隔一个月之后的国际密码会上得到了验证，国外专家如此强烈的反响表明，我们的工作可以说不但不比国际上的差，而且是在破解HASH函数方面已领先一步。加拿大CertainKey公司早前宣布将给予发现MD5算法第一个碰撞人员一定的奖励，CertainKey的初衷是利用并行计算机通过生日攻击来寻找碰撞，而王小云教授等的攻击相对生日攻击需要更少的计算时间。
! T1 f& r; o. G9 `4 F8 v* x. e
　　数字认证　你的未来不是梦
) W5 T2 q1 E7 E: k2 r$ M+ T　　由于MD5的破译，引发了关于MD5产品是否还能够使用的大辩论。在麻省理工大学Jeffrey I. Schiller教授主持的个人论坛上，许多密码学家在标题为“Bad day at the hash function factory”的辩论中发表了具有价值的意见（http://jis.mit.edu/pipermail/saag/2004q3/000913.html）。这次国际密码学会议的总主席Jimes Hughes发表评论说“我相信这（破解MD5）是真的，并且如果碰撞存在，HMAC也就不再是安全的了，…… 我认为我们应该抛开MD5了。” Hughes建议，程序设计人员最好开始舍弃MD5。他说：“既然现在这种算法的弱点已暴露出来，在有效的攻击发动之前，现在是撤离的时机。”
　　同样，在普林斯顿大学教授Edwards Felton的个人网站（http://www.freedom-to-tinker.com/archives/000664.html）上，也有类似的评论。他说：“留给我们的是什么呢？MD5已经受了重伤；它的应用就要淘汰。SHA-1仍然活着，但也不会很长，必须立即更换SHA-1，但是选用什么样的算法，这需要在密码研究人员达到共识。”
- F9 \7 u; ^, l  S6 O0 ?. O8 I) k" Z　　密码学家Markku-Juhani称“这是HASH函数分析领域激动人心的时刻。（http://www.tcs.hut.fi/~mjos/md5/）”
8 J, I6 \% F) q4 y3 s　　而著名计算机公司SUN的LINUIX专家Val Henson则说：“以前我们说"SHA-1可以放心用，其他的不是不安全就是未知"， 现在我们只能这么总结了："SHA-1不安全，其他的都完了"。
1 H/ @" f" }/ d: z  G　　针对王小云教授等破译的以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）来替代。”
　　详细评论见：http://csrc.nist.gov/hash_standards_comments.pdf
　　2004年8月28日，十届全国人大常委会第十一次会议表决通过了电子签名法。这部法律规定，可靠的电子签名与手写签名或者盖章具有同等的法律效力。电子签名法的通过，标志着我国首部“真正意义上的信息化法律”已正式诞生，将于2005年4月1日起施行。专家认为，这部法律将对我国电子商务、电子政务的发展起到极其重要的促进作用。王小云教授的发现无异于发现了信息化天空的一个惊人黑洞。我们期待着王小云教授和她的团队能够成就“女娲补天”的壮举，为人类的信息化之路保驾护航。