山大視點::>山東大學(xué)新聞思政網(wǎng)<::

lfcperliab 2011-07-20

展開全文

密碼學(xué)領(lǐng)域重大發(fā)現(xiàn)：山東大學(xué)王小云教授成功破解MD5

2004-09-04 09:39

　?。郾菊居崳?004年8月17日的美國加州圣巴巴拉，正在召開的國際密碼學(xué)會議（Crypto’2004）安排了三場關(guān)于雜湊函數(shù)的特別報告。在國際著名密碼學(xué)家Eli Biham和Antoine Joux相繼做了對SHA-1的分析與給出SHA-0的一個碰撞之后，來自山東大學(xué)的王小云教授做了破譯MD5、HAVAL-128、 MD4和RIPEMD算法的報告。在會場上，當她公布了MD系列算法的破解結(jié)果之后，報告被激動的掌聲打斷。王小云教授的報告轟動了全場，得到了與會專家的贊嘆。報告結(jié)束時，與會者長時間熱烈鼓掌，部分學(xué)者起立鼓掌致敬，這在密碼學(xué)會議上是少見的盛況。王小云教授的報告緣何引起如此大的反響？因為她的研究成果作為密碼學(xué)領(lǐng)域的重大發(fā)現(xiàn)宣告了固若金湯的世界通行密碼標準MD５的堡壘轟然倒塌，引發(fā)了密碼學(xué)界的軒然大波。會議總結(jié)報告這樣寫道：“我們該怎么辦？MD5被重創(chuàng)了；它即將從應(yīng)用中淘汰。SHA-1仍然活著，但也見到了它的末日。現(xiàn)在就得開始更換SHA-1了。”

     關(guān)鍵詞：碰撞＝漏洞＝別人可以偽造和冒用數(shù)字簽名。
     Hash函數(shù)與數(shù)字簽名（數(shù)字手?。?br>     HASH函數(shù)，又稱雜湊函數(shù)，是在信息安全領(lǐng)域有廣泛和重要應(yīng)用的密碼算法，它有一種類似于指紋的應(yīng)用。在網(wǎng)絡(luò)安全協(xié)議中，雜湊函數(shù)用來處理電子簽名，將冗長的簽名文件壓縮為一段獨特的數(shù)字信息，像指紋鑒別身份一樣保證原來數(shù)字簽名文件的合法性和安全性。在前面提到的SHA-1和MD5都是目前最常用的雜湊函數(shù)。經(jīng)過這些算法的處理，原始信息即使只更動一個字母，對應(yīng)的壓縮信息也會變?yōu)榻厝徊煌?#8220;指紋”，這就保證了經(jīng)過處理信息的唯一性。為電子商務(wù)等提供了數(shù)字認證的可能性。
     安全的雜湊函數(shù)在設(shè)計時必須滿足兩個要求：其一是尋找兩個輸入得到相同的輸出值在計算上是不可行的，這就是我們通常所說的抗碰撞的；其二是找一個輸入，能得到給定的輸出在計算上是不可行的，即不可從結(jié)果推導(dǎo)出它的初始狀態(tài)?，F(xiàn)在使用的重要計算機安全協(xié)議，如SSL，PGP都用雜湊函數(shù)來進行簽名，一旦找到兩個文件可以產(chǎn)生相同的壓縮值，就可以偽造簽名，給網(wǎng)絡(luò)安全領(lǐng)域帶來巨大隱患。
     MD5就是這樣一個在國內(nèi)外有著廣泛的應(yīng)用的雜湊函數(shù)算法，它曾一度被認為是非常安全的。然而，王小云教授發(fā)現(xiàn)，可以很快的找到MD5的“碰撞”，就是兩個文件可以產(chǎn)生相同的“指紋”。這意味著，當你在網(wǎng)絡(luò)上使用電子簽名簽署一份合同后，還可能找到另外一份具有相同簽名但內(nèi)容迥異的合同，這樣兩份合同的真?zhèn)涡员銦o從辨別。王小云教授的研究成果證實了利用MD5算法的碰撞可以嚴重威脅信息系統(tǒng)安全，這一發(fā)現(xiàn)使目前電子簽名的法律效力和技術(shù)體系受到挑戰(zhàn)。因此，業(yè)界專家普林斯頓計算機教授Edward Felten等強烈呼吁信息系統(tǒng)的設(shè)計者盡快更換簽名算法，而且他們強調(diào)這是一個需要立即解決的問題。

     國際講壇　王氏發(fā)現(xiàn)艷驚四座
     面對Hash函數(shù)領(lǐng)域取得的重大研究進展，Crypto 2004 會議總主席StorageTek高級研究員Jim Hughes 17 日早晨表示，此消息太重要了，因此他已籌辦該會成立24年來的首次網(wǎng)絡(luò)廣播（Webcast ）。Hughes在會議上宣布：“會中將提出三份探討雜湊碰撞（hash collisions ）重要的研究報告。”其中一份是王小云等幾位中國研究人員的研究發(fā)現(xiàn)。17日晚，王小云教授在會上把他們的研究成果做了宣讀。這篇由王小云、馮登國、來學(xué)嘉、于紅波四人共同完成的文章，囊括了對MD5、HAVAL-128、 MD4和RIPEMD四個著名HASH算法的破譯結(jié)果。在王小云教授僅公布到他們的第三個驚人成果的時候，會場上已經(jīng)是掌聲四起，報告不得不一度中斷。報告結(jié)束后，所有與會專家對他們的突出工作報以長時的熱烈掌聲，有些學(xué)者甚至起立鼓掌以示他們的祝賀和敬佩。當人們掌聲漸息，來學(xué)嘉教授又對文章進行了一點頗有趣味的補充說明。由于版本問題，作者在提交會議論文時使用的一組常數(shù)和先行標準不同；在會議發(fā)現(xiàn)這一問題之后，王小云教授立即改變了那個常數(shù)，在很短的時間內(nèi)就完成了新的數(shù)據(jù)分析，這段有驚無險的小插曲倒更加證明了他們論文的信服力，攻擊方法的有效性，反而凸顯了研究工作的成功。
     會議結(jié)束時，很多專家圍攏到王小云教授身邊，既有簡短的探討，又有由衷的祝賀，褒譽之詞不絕。包含公鑰密碼的主要創(chuàng)始人R. L. Rivest和A. Shamir在內(nèi)的世界頂級的密碼學(xué)專家也上前表示他們的欣喜和祝賀。
     國際密碼學(xué)專家對王小云教授等人的論文給予高度評價。
     MD5的設(shè)計者，同時也是國際著名的公鑰加密算法標準RSA的第一設(shè)計者R．Rivest在郵件中寫道：“這些結(jié)果無疑給人非常深刻的印象，她應(yīng)當?shù)玫轿易顭崃业淖ＹR，當然，我并不希望看到MD5就這樣倒下，但人必須尊崇真理。”
     Francois Grieu這樣說：“王小云、馮登國、來學(xué)嘉和于紅波的最新成果表明他們已經(jīng)成功破譯了MD4、MD5、HAVAL-128、RIPEMD-128。并且有望以更低的復(fù)雜度完成對SHA-0的攻擊。一些初步的問題已經(jīng)解決。他們贏得了非常熱烈的掌聲。”
     另一位專家Greg Rose如此評價：“我剛剛聽了Joux和王小云的報告，王所使用的技術(shù)能在任何初始值下用2^40次hash運算找出SHA-0的碰撞。她在報告中對四種HASH函數(shù)都給出了碰撞，她贏得了長時間的起立喝彩，（這在我印象中還是第一次）。…… 她是當今密碼學(xué)界的巾幗英雄。……（王小云教授的工作）技術(shù)雖然沒有公開，但結(jié)果是無庸質(zhì)疑的，這種技術(shù)確實存在。…… 我坐在Ron Rivest前面，我聽到他評論道：‘我們不得不做很多的重新思考了。’”

     石破驚天　MD5堡壘轟然倒塌
     一石擊起千層浪，MD5的破譯引起了密碼學(xué)界的激烈反響。專家稱這是密碼學(xué)界近年來“最具實質(zhì)性的研究進展”，各個密碼學(xué)相關(guān)網(wǎng)站競相報導(dǎo)這一驚人突破。
     MD5破解專項網(wǎng)站關(guān)閉
     MD5破解工程權(quán)威網(wǎng)站http://www./ 是為了公開征集專門針對MD5的攻擊而設(shè)立的，網(wǎng)站于2004年8月17日宣布：“中國研究人員發(fā)現(xiàn)了完整MD5算法的碰撞；Wang, Feng, Lai與Yu公布了MD5、MD4、HAVAL-128、RIPEMD-128幾個 Hash函數(shù)的碰撞。這是近年來密碼學(xué)領(lǐng)域最具實質(zhì)性的研究進展。使用他們的技術(shù)，在數(shù)個小時內(nèi)就可以找到MD5碰撞。……由于這個里程碑式的發(fā)現(xiàn)，MD5CRK項目將在隨后48小時內(nèi)結(jié)束”。
     對此，http://www.主頁專門轉(zhuǎn)載了該報道http://www./distributed/distrib-recent.html和幾個其它網(wǎng)站也進行了報道。
     權(quán)威網(wǎng)站相繼發(fā)表評論或者報告這一重大研究成果
     經(jīng)過統(tǒng)計，在論文發(fā)布兩周之內(nèi)，已經(jīng)有近400個網(wǎng)站發(fā)布、引用和評論了這一成果。國內(nèi)的許多新聞網(wǎng)站也以“演算法安全加密功能露出破綻密碼學(xué)界一片嘩然”為題報道了這一密碼學(xué)界的重大事件。（報導(dǎo)見http://www./perl/board/mboard.pl?board=lnitalkback&thread=895&id=896&display=1&tview=expanded&mview=flat,該消息在各新聞網(wǎng)站上多次轉(zhuǎn)載。）

     東方神韻　 MD5終結(jié)者來自中國
     MD5破解工作的主要成員王小云教授是一個瘦弱、矜持的女子，厚厚的鏡片透射出雙眸中數(shù)學(xué)的靈光。她于1990年在山東大學(xué)師從著名數(shù)學(xué)家潘承洞教授攻讀數(shù)論與密碼學(xué)專業(yè)博士，在潘先生、于秀源、展?jié)榷辔恢淌诘南ば闹笇?dǎo)下，她成功將數(shù)論知識應(yīng)用到密碼學(xué)中，取得了很多突出成果，先后獲得863項目資助和國家自然科學(xué)基金項目資助，并且獲得部級科技進步獎一項，撰寫論文二十多篇。王小云教授從上世紀90年代末開始進行HASH函數(shù)的研究，她所帶領(lǐng)的于紅波、王美琴、孫秋梅、馮騏等組成的密碼研究小組，同中科院馮登國教授，上海交大來學(xué)嘉等知名學(xué)者密切協(xié)作，經(jīng)過長期堅持不懈的努力，找到了破解HASH函數(shù)的關(guān)鍵技術(shù)，成功的破解了MD5和其它幾個HASH函數(shù)。
     近年來她的工作得到了山東大學(xué)和數(shù)學(xué)院領(lǐng)導(dǎo)的大力支持，特別投資建設(shè)了信息安全實驗室。山東大學(xué)校長展?jié)淌诟叨戎匾曂跣≡平淌谕怀龅目蒲谐晒?2004年6月山東大學(xué)領(lǐng)導(dǎo)聽取王小云教授的工作介紹后，展?jié)ｉL親自簽發(fā)邀請函邀請國內(nèi)知名信息安全專家參加2004年7月在威海舉辦的“山東大學(xué)信息安全研究學(xué)術(shù)研討會”，數(shù)學(xué)院院長劉建亞教授組織和主持了會議，會上王小云教授公布了MD5等算法的一系列研究成果，專家們對她的研究成果給予了充分的肯定，對其堅持不懈的科研態(tài)度大加贊揚。一位院士說，她的研究水平絕對不比國際上的差。這位院士的結(jié)論在時隔一個月之后的國際密碼會上得到了驗證，國外專家如此強烈的反響表明，我們的工作可以說不但不比國際上的差，而且是在破解HASH函數(shù)方面已領(lǐng)先一步。加拿大CertainKey公司早前宣布將給予發(fā)現(xiàn)MD5算法第一個碰撞人員一定的獎勵，CertainKey的初衷是利用并行計算機通過生日攻擊來尋找碰撞，而王小云教授等的攻擊相對生日攻擊需要更少的計算時間。

     數(shù)字認證　你的未來不是夢
     由于MD5的破譯，引發(fā)了關(guān)于MD5產(chǎn)品是否還能夠使用的大辯論。在麻省理工大學(xué)Jeffrey I. Schiller教授主持的個人論壇上，許多密碼學(xué)家在標題為“Bad day at the hash function factory”的辯論中發(fā)表了具有價值的意見（http://jis./pipermail/saag/2004q3/000913.html）。這次國際密碼學(xué)會議的總主席Jimes Hughes發(fā)表評論說“我相信這（破解MD5）是真的，并且如果碰撞存在，HMAC也就不再是安全的了，…… 我認為我們應(yīng)該拋開MD5了。” Hughes建議，程序設(shè)計人員最好開始舍棄MD5。他說：“既然現(xiàn)在這種算法的弱點已暴露出來，在有效的攻擊發(fā)動之前，現(xiàn)在是撤離的時機。”
     同樣，在普林斯頓大學(xué)教授Edwards Felton的個人網(wǎng)站（http://www./archives/000664.html）上，也有類似的評論。他說：“留給我們的是什么呢？MD5已經(jīng)受了重傷；它的應(yīng)用就要淘汰。SHA-1仍然活著，但也不會很長，必須立即更換SHA-1，但是選用什么樣的算法，這需要在密碼研究人員達到共識。”
     密碼學(xué)家Markku-Juhani稱“這是HASH函數(shù)分析領(lǐng)域激動人心的時刻。（http://www.tcs./~mjos/md5/）”
     而著名計算機公司SUN的LINUIX專家Val Henson則說：“以前我們說"SHA-1可以放心用，其他的不是不安全就是未知"，現(xiàn)在我們只能這么總結(jié)了："SHA-1不安全，其他的都完了"。
     針對王小云教授等破譯的以MD5為代表的Hash函數(shù)算法的報告，美國國家技術(shù)與標準局（NIST）于2004年8月24日發(fā)表專門評論，評論的主要內(nèi)容為：“在最近的國際密碼學(xué)會議（Crypto 2004）上，研究人員宣布他們發(fā)現(xiàn)了破解數(shù)種HASH算法的方法，其中包括MD4，MD5，HAVAL-128，RIPEMD還有 SHA-0。分析表明，于1994年替代SHA-0成為聯(lián)邦信息處理標準的SHA-1的減弱條件的變種算法能夠被破解；但完整的SHA-1并沒有被破解，也沒有找到SHA-1的碰撞。研究結(jié)果說明SHA-1的安全性暫時沒有問題，但隨著技術(shù)的發(fā)展，技術(shù)與標準局計劃在2010年之前逐步淘汰SHA-1，換用其他更長更安全的算法（如SHA-224、SHA-256、SHA-384和SHA-512）來替代。”
     詳細評論見：http://csrc./hash_standards_comments.pdf
     2004年8月28日，十屆全國人大常委會第十一次會議表決通過了電子簽名法。這部法律規(guī)定，可靠的電子簽名與手寫簽名或者蓋章具有同等的法律效力。電子簽名法的通過，標志著我國首部“真正意義上的信息化法律”已正式誕生，將于2005年4月1日起施行。專家認為，這部法律將對我國電子商務(wù)、電子政務(wù)的發(fā)展起到極其重要的促進作用。王小云教授的發(fā)現(xiàn)無異于發(fā)現(xiàn)了信息化天空的一個驚人黑洞。我們期待著王小云教授和她的團隊能夠成就“女媧補天”的壯舉，為人類的信息化之路保駕護航。