王小云破解兩大算法
數(shù)字加密大廈將傾
如果說MD5和SHA-1是當今各種信息安全體系所依賴的大廈基石，那么現(xiàn)在，這些大廈的基礎已經(jīng)出現(xiàn)了很大的裂縫，甚至，有崩塌的危險。
全球?qū)W界震驚，美國軍方網(wǎng)絡在內(nèi)的重大安全體系人人自危……
在8個月以前，人們還以為在全球廣泛應用的MD5和SHA-1都是值得信任的安全的數(shù)字簽名算法；8個月后的今天，曾經(jīng)值得信賴的數(shù)字簽名體系，令人震驚的兩次“碰撞”將這兩種應用最廣的簽名加密算法都逼上了絕路。
MD5和SHA-1這兩種應用最為廣泛的數(shù)字簽名加密算法都被山東大學的數(shù)學教授王小云破解，業(yè)界感到震驚的同時，也開始對今天廣泛應用的數(shù)字簽名算法體系進行反思，我國于2005年4月1日開始實施的《電子簽名法》也開始承受各種壓力。
兩次“碰撞”驚世界
在參加過2004年國際密碼學會議（Crypto’2004）的專家們看來，“一覺醒來，一切都變了”。來自中國山東大學的王小云教授在Crypto’2004上做的破譯MD5、HAVAL-128、MD4和RIPEMD算法的報告，令在場的國際頂尖密碼學專家都為之震驚。該次會議的總結(jié)報告中這樣寫道：“我們該怎么辦？MD5被重創(chuàng)了，它即將從應用中淘汰。SHA-1仍然活著，但也見到了它的末日。現(xiàn)在就得開始更換SHA-1了。”
MD5算法是1991年發(fā)布的一項數(shù)字簽名加密算法，它當時解決了MD4算法的安全性缺陷，成為應用非常廣泛的一種算法。作為Hash函數(shù)的一個應用實例，MD5本身也存在漏洞，但在十多年的研究及應用過程中，人們一直沒有找到能夠在可接受的時間及計算能力范圍內(nèi)迅速破解該算法的技術(shù)，因而這種理論上的瑕疵并沒有影響MD5的應用。事實上，以MD5為應用代表的Hash函數(shù)的研究在國際密碼學界早已不是熱門，因而，王小云在“Crypto’2004”上發(fā)布的報告令整個密碼學界醍醐灌頂，國際同行們開始研究王小云的理論，希望能沿著這條新路找到更多寶藏。
在MD5被王小云踩在腳下之后，世界密碼學界仍然認為SHA-1是安全的算法。2005年2月7日，美國國家標準技術(shù)研究院（NIST）對外宣稱，SHA-1還沒有被攻破，并且也沒有足夠的理由懷疑它會很快被攻破。僅在一周之后，王小云教授再度令世界密碼學界大跌眼鏡——SHA-1也被她“碰撞”了。
SHA-1的應用范圍或許比MD5更加廣泛，其安全性較MD5要高出很多。SHA-1是美國國家標準技術(shù)研究院（NIST）與美國國家安全局（NSA）共同設計的，一些重要的場合都選擇SHA-1來做數(shù)字簽名。美國政府更是早在1994年就開始采用了SHA-1算法。因此，SHA-1被破的消息一經(jīng)傳出，在國際社會的反響甚至超出半年前MD5被破時的情景。NIST表示，為配合先進的計算機技術(shù)，美國政府5年內(nèi)將不再使用SHA-1，并計劃在2010年前改用先進的SHA-224、SHA-256、SHA-384及SHA-512的數(shù)字簽名加密算法。
在我國，MD5和SHA-1也是在實際應用中最廣泛的兩種數(shù)字簽名算法，包括網(wǎng)上銀行等金融業(yè)務在內(nèi)的很多數(shù)字簽名都采用SHA-1或MD5算法。在《電子簽名法》實施后，數(shù)字簽名算法的可靠性將提升到可影響司法取證結(jié)果的高度。
王小云教授取得的成果之所以能引起全球密碼學界的廣泛關(guān)注，一方面是由于在實用密碼體系中MD5和SHA-1確實是應用最為廣泛的極為重要的兩個算法，因而這個成果具有難以估量的實際意義；另一方面則是因為她發(fā)明了一種可以迅速而有效地驗證一系列Hash函數(shù)算法健壯性的工具，從而令Hash函數(shù)的一些隱含弱點更快地暴露在人們眼前，這在學術(shù)研究上具有更大的理論價值。
Hash函數(shù)遇窘境
Hash函數(shù)又稱雜湊函數(shù)，用于摘要算法，它是將不定長的明文信息經(jīng)過復雜的運算得到一個定長的數(shù)值，這就是“簽名”。摘要算法與一般的對稱或非對稱加密算法不同，它并不用于防止信息被竊取，而是用于證明原文的完整性和準確性，也就是說，數(shù)字簽名主要是用于防止信息被篡改。
由于Hash函數(shù)產(chǎn)生定長的數(shù)字簽名，其結(jié)果是個有限的集合，而待簽名的明文信息可以是計算機網(wǎng)絡上傳輸?shù)娜我庑畔ⅲ簿褪钦f，明文信息是一個無限集合，兩個集合之間其實無法構(gòu)成一一對應的關(guān)系，總會有多個明文信息產(chǎn)生相同的數(shù)字簽名的情況發(fā)生，這就是所謂的“碰撞”。不過Hash函數(shù)的可靠性在概率上仍可以算法的健壯性來保證，數(shù)字簽名類似指紋，只要選擇足夠安全的算法，產(chǎn)生碰撞的概率就會足夠小，可令現(xiàn)代最先進的計算設備也找不出“碰撞”，這樣算法就不會被破解了。
MD5和SHA-1就曾經(jīng)被認為是足夠安全的Hash算法。雖然早在1994年就有研究報告指出，如果用運算能力最強的機器，平均用24天就可能找到一個MD5的碰撞，但這個方法的效率和成本在現(xiàn)實中并不具備實際的意義。王小云在接受本報記者獨家采訪時透露，她獨創(chuàng)的“模差分”算法可以用一般性能的計算機在兩個小時內(nèi)就找到MD5的碰撞，已經(jīng)為實際應用提供了可能。
記者與一位曾經(jīng)是國內(nèi)頂級黑客的信息安全界的朋友探討過王小云教授取得的這兩項成果，這位朋友私下告訴記者，其實國內(nèi)的黑客們很早就注意到王小云教授的研究成果了，他們認為，王小云的工作更重要的意義在于證明了MD5和SHA-1等一系列Hash值的分布是有明顯規(guī)律的，這就從理論上將以往常用的窮舉式試驗攻擊的難度降低到難以想像的地步，“現(xiàn)在是兩個小時，我相信肯定有高手已經(jīng)在研究如何優(yōu)化利用王小云的成果了，實際應用中的破解是遲早的事兒”。
事實上，最近已有外電報道稱國際密碼專家Lenstra利用王小云教授的方法，偽造了符合X.509標準的數(shù)字證書，這說明MD5的破解已經(jīng)不只是理論上的成果。同時，王小云教授對本報記者表示，現(xiàn)在媒體報道中提及的SHA-1碰撞在理論上雖然被破譯，但“離實際應用還有一段距離，這個具體的時間還不好說，雖然MD5的碰撞從理論到實際應用只用了半年時間，可是SHA-1的算法要比MD5復雜很多，沒有發(fā)生的事情誰也不好講，我只能說我們已經(jīng)掌握了比以往更強大的研究工具，因而研究的進展會加快很多。”
王小云教授在接受采訪時還表示，其實對于HAVAL-128、MD4和RIPEMD等算法的破解也是非常重要的成果，只是媒體在炒作中往往忽略了這些細節(jié)，“如果沒有MD5和SHA-1的破解，像HAVAL-128、RIPEMD這些算法的研究結(jié)果也是非常重要的，雖然MD4很早就被MD5替換了，但是今天我們掌握的方法可以比以往更迅速地找到‘碰撞’，這套方法是最重要的，這比找到某一兩個算法的碰撞更為重要。”
在王小云教授看來，Hash函數(shù)遇到這樣的“裂縫”事件倒也未必是壞事，“現(xiàn)在最重要的工作是應該盡快設計出更安全的算法，而這項工作在很大程度上也取決于我們掌握的評估工具”，王小云告訴記者，“模差分”方法正是這樣一套完備的算法研究與評估的工具。
數(shù)字簽名待拷問
對于王小云教授來說，無論破解現(xiàn)有的算法還是設計新的算法，都只是理論上的一種研究；但是對其他人來講，王小云教授給出的“碰撞”早已超出了兩篇論文的沖擊。
2005年4月1日，也就是記者截稿的這一天，《電子簽名法》在我國開始正式實施，這部法律規(guī)定，可靠的電子簽名與手寫簽名或蓋章具有同等的法律效力，而面對這種關(guān)鍵的數(shù)字簽名算法產(chǎn)生的新問題，電子簽名法的實施將面臨一次考驗。
早在去年8月王小云教授公布MD5碰撞的研究成果時，中國金融認證中心（CFCA）就在其網(wǎng)站上發(fā)布了一份聲明，該聲明稱：“CFCA在建立之初，已經(jīng)對MD5以及其他算法進行了安全性評估。因此，在CFCA提供的應用產(chǎn)品和服務中，并沒有采用MD5等不安全的算法，而是采用了安全的SHA-1算法，用戶可以放心地使用；CFCA提供的安全應用工具包默認使用的哈希算法也是SHA-1算法，考慮到工具包對其他應用的互操作性要求，工具包也提供了MD5算法，如果用戶在使用工具包進行開發(fā)時，不使用默認的算法而采用了MD5算法，請立即修改自己的程序，采用默認的SHA-1算法，以避免MD5的缺陷產(chǎn)生的影響。”這份聲明至今還掛在CFCA的網(wǎng)站上，但聲明中提到的“安全的SHA-1算法”顯然已被王小云教授的最新研究成果證明是和“曾經(jīng)安全的MD5”一樣不再值得人們信賴了。
不過，王小云教授也表示，現(xiàn)在對SHA-1的研究仍是理論破解，并未像MD5那樣已經(jīng)有實際應用的例子，所以人們還沒有必要對銀行存款之類的安全問題產(chǎn)生太多的擔心。但沒有立即的威脅出現(xiàn)并不表示會一直太平無事，對于有關(guān)部門來說，確實該考慮提前將SHA-1換成更安全的算法了。
對于SHA-1碰撞的實際意義，王小云教授的合作者，參與過SHA-1算法研究的尹依群博士曾在美國接受媒體采訪時透露，現(xiàn)在使用王小云教授的方法，要找到SHA-1的一個碰撞，需要的計算能力大約相當于用5萬臺超級計算機工作100年，這已經(jīng)超出了現(xiàn)有計算資源的能力范圍。同時，尹博士也指出，這并不能排除近期內(nèi)SHA-1快速找到實際碰撞的可能性，她也認為盡快將SHA-1更換到更安全的算法是很有必要的。
隨著王小云教授的研究成果被越來越多的人所了解，業(yè)界對于MD5和SHA-1在數(shù)字簽名中的應用開始逐漸分化成兩種態(tài)度。
來自學術(shù)界的研究人員多認為MD5和SHA-1的安全性既然已經(jīng)無法在技術(shù)上絕對保證，那么在實際的應用中就應該盡可能地考慮到算法漏洞的影響，至少在法律上，這些已經(jīng)被證明不夠安全的算法不應該再作為數(shù)字簽名的法律依據(jù)。
而企業(yè)面對的問題就沒有那么單純，如果這些算法必須更換，那就意味著對部分產(chǎn)品的前期投入成為浪費，尤其是芯片級的固件，加密算法一經(jīng)寫入就很難更改，產(chǎn)品的生命周期隨著所采用的加密算法的失效將走到盡頭。所以對于這些企業(yè)來說，更換算法就意味著更換產(chǎn)品，隨之而來的就是成本的增加；不更換算法，產(chǎn)品就要在未來承受未知的安全風險，一旦出現(xiàn)問題，后果更為嚴重。
某信息安全企業(yè)的技術(shù)總監(jiān)告訴記者，既然王小云教授的研究成果從理論到實際上都撼動了Hash函數(shù)這個數(shù)字簽名算法的根基，現(xiàn)在留給業(yè)界的將是看起來矛盾重重的混亂局面，“包括我們在內(nèi)的很多廠商都要盡快考慮更換算法的問題，尤其是在數(shù)字簽名中應用了MD5算法的產(chǎn)品，升級已勢在必行。雖然沒有哪家企業(yè)愿意對外公開這種影響，但這個工作大家都必須盡快著手去做了。”
鏈接一
國際頂尖密碼學專家對王小云研究成果的評價
Ronald L.Rivest（2002年圖靈獎獲得者，RSA密碼發(fā)明人之一，MD5的創(chuàng)造者，世界最權(quán)威的密碼學專家之一）：
我的研究方向之一是“Hash函數(shù)”，這種函數(shù)是目前許多密碼系統(tǒng)應用的核心。我曾經(jīng)設計過一些Hash函數(shù)，其中的MD5由于擁有優(yōu)越的高效及安全性能，得到了普遍的認可和廣泛的應用。盡管有人曾發(fā)現(xiàn)MD5函數(shù)的某些方面存在著安全隱患，但一直以來，MD5都無法被破解。此外，還有許多其他的密碼Hash函數(shù)（如SHA-1，RIPEMD等）情況也類似。
然而令人驚異的是，在王小云教授的帶領(lǐng)下，MD5函數(shù)和其他一些Hash函數(shù)在近期都被破解了。MD5函數(shù)十幾年來經(jīng)受住了眾多密碼學專家的攻擊，而王小云教授卻成功地破解了它，這實在是一種令人印象極深的卓越成就，是高水平的世界級研究成果。這些結(jié)果無疑給人非常深刻的印象，她應當?shù)玫轿易顭崃业淖ＹR。當然，我并不希望看到MD5就這樣倒下，但人必須尊重真理。
Adi Shamir（2002年圖靈獎獲得者，RSA密碼發(fā)明人之一，SSSS的創(chuàng)造者）：
關(guān)于王小云教授所做的工作，我想強調(diào)的是她所研究的Hash函數(shù)是近15年來密碼研究學中最不活躍的領(lǐng)域。所有主要的Hash函數(shù)早在1980年代末或1990年代初就已經(jīng)被發(fā)展和定型，并且后來幾乎也沒有再出現(xiàn)有過關(guān)其安全性的研究成果。而王教授的研究以獨特的方式打破了這種沉悶的局面，并對該領(lǐng)域的理論研究和實際應用產(chǎn)生了極大的影響。特別是一些被廣泛應用的Hash函數(shù)，如MD5，將不會再被使用。而未來的Hash函數(shù)將會以新的設計原則來發(fā)展。
鏈接二
MD5和SHA-1算法
■ 林居
MD5和SHA-1都屬于散列（Hash）算法，其作用是可以將不定長的信息（原文）經(jīng)過處理后得到一個定長的摘要信息串，對同樣的原文用同樣的散列算法進行處理，每次得到的信息摘要串相同。Hash算法是單向的，一旦數(shù)據(jù)被轉(zhuǎn)換，就無法再以確定的方法獲得其原始值。事實上，在絕大多數(shù)情況下，原文的長度都超過摘要信息串的長度，因此，在散列計算過程中，原文的信息被部分丟失，這使得原文無法從摘要信息重構(gòu)。散列算法的這種不可逆特征使其很適合被用來確認原文（例如公文）的完整性，因而被廣泛用于數(shù)字簽名的場合。
如果除了原文之外，對于另外一段不同的信息進行相同散列算法，得到的摘要信息與原文的摘要信息相同，則稱之為碰撞，散列算法通?？梢员ＷC碰撞也很難根據(jù)摘要被求出。
MD5（RFC1321）誕生于1991年，全稱是“Message-Digest Algorithm（信息摘要算法）5”，由MIT的計算機安全實驗室和RSA安全公司共同提出，之前已經(jīng)有MD2、MD3和MD4幾種算法。MD5克服了MD4的缺陷，生成128bit的摘要信息串，出現(xiàn)之后迅速成為主流算法，并在1992年被收錄到RFC中。
SHA誕生于1993年，全稱是安全散列算法（Secure Hash Algorithm），由美國國家安全局（NSA）設計，之后被美國標準與技術(shù)研究院（NIST）收錄到美國的聯(lián)邦信息處理標準（FIPS）中，成為美國國家標準，SHA（后來被稱做SHA-0）于1995被SHA-1（RFC3174）替代。SHA-1生成長度為160bit的摘要信息串，雖然之后又出現(xiàn)了SHA-224、SHA-256、SHA-384和SHA-512等被統(tǒng)稱為“SHA-2”的系列算法，但仍以SHA-1為主流。
MD5和SHA-1是當前應用最為廣泛的兩種散列算法。常見的Unix系統(tǒng)口令以及多數(shù)論壇/社區(qū)系統(tǒng)的口令都是經(jīng)MD5處理后保存其摘要信息串，在互聯(lián)網(wǎng)上，很多文件在開放下載的同時都提供一個MD5的信息摘要，使下載方（通過MD5摘要計算）能夠確認所下載的文件與原文件一致，以此來防止文件被篡改。
MD5和SHA-1還常被用來與公鑰技術(shù)結(jié)合來創(chuàng)建數(shù)字簽名。當前幾乎所有主要的信息安全協(xié)議中都使用了SHA-1或MD5，包括SSL（HTTPS就是SSL的一種應用）、TLS、PGP、SSH、S/MIME和IPSec，因此可以說SHA-1和MD5是當前信息安全的重要基礎之一。
不過，從技術(shù)上講，MD5和SHA-1的碰撞可在短時間內(nèi)被求解出并不意味著兩種算法完全失效。例如，對于公文的數(shù)字簽名來說，尋找到碰撞與尋找到有特定含義的碰撞之間仍有很大的差距，而后者才會使偽造數(shù)字公文成為現(xiàn)實。但無論如何，王小云教授所掌握的方法已經(jīng)為短時間內(nèi)尋找到MD5或SHA-1的碰撞成為可能，這足以使經(jīng)過MD5或SHA-1處理的數(shù)字簽名再也難以成為法律認可的依據(jù)。
