數(shù)字加密大廈將傾

Joshua 2006-01-19

展開全文

王小云破解兩大算法
數(shù)字加密大廈將傾

　　如果說MD5和SHA-1是當(dāng)今各種信息安全體系所依賴的大廈基石，那么現(xiàn)在，這些大廈的基礎(chǔ)已經(jīng)出現(xiàn)了很大的裂縫，甚至，有崩塌的危險(xiǎn)。

     全球?qū)W界震驚，美國軍方網(wǎng)絡(luò)在內(nèi)的重大安全體系人人自危……

     在8個(gè)月以前，人們還以為在全球廣泛應(yīng)用的MD5和SHA-1都是值得信任的安全的數(shù)字簽名算法；8個(gè)月后的今天，曾經(jīng)值得信賴的數(shù)字簽名體系，令人震驚的兩次“碰撞”將這兩種應(yīng)用最廣的簽名加密算法都逼上了絕路。

     MD5和SHA-1這兩種應(yīng)用最為廣泛的數(shù)字簽名加密算法都被山東大學(xué)的數(shù)學(xué)教授王小云破解，業(yè)界感到震驚的同時(shí)，也開始對今天廣泛應(yīng)用的數(shù)字簽名算法體系進(jìn)行反思，我國于2005年4月1日開始實(shí)施的《電子簽名法》也開始承受各種壓力。
     兩次“碰撞”驚世界

     在參加過2004年國際密碼學(xué)會議（Crypto’2004）的專家們看來，“一覺醒來，一切都變了”。來自中國山東大學(xué)的王小云教授在Crypto’2004上做的破譯MD5、HAVAL-128、MD4和RIPEMD算法的報(bào)告，令在場的國際頂尖密碼學(xué)專家都為之震驚。該次會議的總結(jié)報(bào)告中這樣寫道：“我們該怎么辦？MD5被重創(chuàng)了，它即將從應(yīng)用中淘汰。SHA-1仍然活著，但也見到了它的末日?，F(xiàn)在就得開始更換SHA-1了。”

     MD5算法是1991年發(fā)布的一項(xiàng)數(shù)字簽名加密算法，它當(dāng)時(shí)解決了MD4算法的安全性缺陷，成為應(yīng)用非常廣泛的一種算法。作為Hash函數(shù)的一個(gè)應(yīng)用實(shí)例，MD5本身也存在漏洞，但在十多年的研究及應(yīng)用過程中，人們一直沒有找到能夠在可接受的時(shí)間及計(jì)算能力范圍內(nèi)迅速破解該算法的技術(shù)，因而這種理論上的瑕疵并沒有影響MD5的應(yīng)用。事實(shí)上，以MD5為應(yīng)用代表的Hash函數(shù)的研究在國際密碼學(xué)界早已不是熱門，因而，王小云在“Crypto’2004”上發(fā)布的報(bào)告令整個(gè)密碼學(xué)界醍醐灌頂，國際同行們開始研究王小云的理論，希望能沿著這條新路找到更多寶藏。

     在MD5被王小云踩在腳下之后，世界密碼學(xué)界仍然認(rèn)為SHA-1是安全的算法。2005年2月7日，美國國家標(biāo)準(zhǔn)技術(shù)研究院（NIST）對外宣稱，SHA-1還沒有被攻破，并且也沒有足夠的理由懷疑它會很快被攻破。僅在一周之后，王小云教授再度令世界密碼學(xué)界大跌眼鏡——SHA-1也被她“碰撞”了。

     SHA-1的應(yīng)用范圍或許比MD5更加廣泛，其安全性較MD5要高出很多。SHA-1是美國國家標(biāo)準(zhǔn)技術(shù)研究院（NIST）與美國國家安全局（NSA）共同設(shè)計(jì)的，一些重要的場合都選擇SHA-1來做數(shù)字簽名。美國政府更是早在1994年就開始采用了SHA-1算法。因此，SHA-1被破的消息一經(jīng)傳出，在國際社會的反響甚至超出半年前MD5被破時(shí)的情景。NIST表示，為配合先進(jìn)的計(jì)算機(jī)技術(shù)，美國政府5年內(nèi)將不再使用SHA-1，并計(jì)劃在2010年前改用先進(jìn)的SHA-224、SHA-256、SHA-384及SHA-512的數(shù)字簽名加密算法。

     在我國，MD5和SHA-1也是在實(shí)際應(yīng)用中最廣泛的兩種數(shù)字簽名算法，包括網(wǎng)上銀行等金融業(yè)務(wù)在內(nèi)的很多數(shù)字簽名都采用SHA-1或MD5算法。在《電子簽名法》實(shí)施后，數(shù)字簽名算法的可靠性將提升到可影響司法取證結(jié)果的高度。

     王小云教授取得的成果之所以能引起全球密碼學(xué)界的廣泛關(guān)注，一方面是由于在實(shí)用密碼體系中MD5和SHA-1確實(shí)是應(yīng)用最為廣泛的極為重要的兩個(gè)算法，因而這個(gè)成果具有難以估量的實(shí)際意義；另一方面則是因?yàn)樗l(fā)明了一種可以迅速而有效地驗(yàn)證一系列Hash函數(shù)算法健壯性的工具，從而令Hash函數(shù)的一些隱含弱點(diǎn)更快地暴露在人們眼前，這在學(xué)術(shù)研究上具有更大的理論價(jià)值。

     Hash函數(shù)遇窘境

     Hash函數(shù)又稱雜湊函數(shù)，用于摘要算法，它是將不定長的明文信息經(jīng)過復(fù)雜的運(yùn)算得到一個(gè)定長的數(shù)值，這就是“簽名”。摘要算法與一般的對稱或非對稱加密算法不同，它并不用于防止信息被竊取，而是用于證明原文的完整性和準(zhǔn)確性，也就是說，數(shù)字簽名主要是用于防止信息被篡改。

     由于Hash函數(shù)產(chǎn)生定長的數(shù)字簽名，其結(jié)果是個(gè)有限的集合，而待簽名的明文信息可以是計(jì)算機(jī)網(wǎng)絡(luò)上傳輸?shù)娜我庑畔?，也就是說，明文信息是一個(gè)無限集合，兩個(gè)集合之間其實(shí)無法構(gòu)成一一對應(yīng)的關(guān)系，總會有多個(gè)明文信息產(chǎn)生相同的數(shù)字簽名的情況發(fā)生，這就是所謂的“碰撞”。不過Hash函數(shù)的可靠性在概率上仍可以算法的健壯性來保證，數(shù)字簽名類似指紋，只要選擇足夠安全的算法，產(chǎn)生碰撞的概率就會足夠小，可令現(xiàn)代最先進(jìn)的計(jì)算設(shè)備也找不出“碰撞”，這樣算法就不會被破解了。

     MD5和SHA-1就曾經(jīng)被認(rèn)為是足夠安全的Hash算法。雖然早在1994年就有研究報(bào)告指出，如果用運(yùn)算能力最強(qiáng)的機(jī)器，平均用24天就可能找到一個(gè)MD5的碰撞，但這個(gè)方法的效率和成本在現(xiàn)實(shí)中并不具備實(shí)際的意義。王小云在接受本報(bào)記者獨(dú)家采訪時(shí)透露，她獨(dú)創(chuàng)的“模差分”算法可以用一般性能的計(jì)算機(jī)在兩個(gè)小時(shí)內(nèi)就找到MD5的碰撞，已經(jīng)為實(shí)際應(yīng)用提供了可能。

     記者與一位曾經(jīng)是國內(nèi)頂級黑客的信息安全界的朋友探討過王小云教授取得的這兩項(xiàng)成果，這位朋友私下告訴記者，其實(shí)國內(nèi)的黑客們很早就注意到王小云教授的研究成果了，他們認(rèn)為，王小云的工作更重要的意義在于證明了MD5和SHA-1等一系列Hash值的分布是有明顯規(guī)律的，這就從理論上將以往常用的窮舉式試驗(yàn)攻擊的難度降低到難以想像的地步，“現(xiàn)在是兩個(gè)小時(shí)，我相信肯定有高手已經(jīng)在研究如何優(yōu)化利用王小云的成果了，實(shí)際應(yīng)用中的破解是遲早的事兒”。

     事實(shí)上，最近已有外電報(bào)道稱國際密碼專家Lenstra利用王小云教授的方法，偽造了符合X.509標(biāo)準(zhǔn)的數(shù)字證書，這說明MD5的破解已經(jīng)不只是理論上的成果。同時(shí)，王小云教授對本報(bào)記者表示，現(xiàn)在媒體報(bào)道中提及的SHA-1碰撞在理論上雖然被破譯，但“離實(shí)際應(yīng)用還有一段距離，這個(gè)具體的時(shí)間還不好說，雖然MD5的碰撞從理論到實(shí)際應(yīng)用只用了半年時(shí)間，可是SHA-1的算法要比MD5復(fù)雜很多，沒有發(fā)生的事情誰也不好講，我只能說我們已經(jīng)掌握了比以往更強(qiáng)大的研究工具，因而研究的進(jìn)展會加快很多。”

     王小云教授在接受采訪時(shí)還表示，其實(shí)對于HAVAL-128、MD4和RIPEMD等算法的破解也是非常重要的成果，只是媒體在炒作中往往忽略了這些細(xì)節(jié)，“如果沒有MD5和SHA-1的破解，像HAVAL-128、RIPEMD這些算法的研究結(jié)果也是非常重要的，雖然MD4很早就被MD5替換了，但是今天我們掌握的方法可以比以往更迅速地找到‘碰撞’，這套方法是最重要的，這比找到某一兩個(gè)算法的碰撞更為重要。”

     在王小云教授看來，Hash函數(shù)遇到這樣的“裂縫”事件倒也未必是壞事，“現(xiàn)在最重要的工作是應(yīng)該盡快設(shè)計(jì)出更安全的算法，而這項(xiàng)工作在很大程度上也取決于我們掌握的評估工具”，王小云告訴記者，“模差分”方法正是這樣一套完備的算法研究與評估的工具。
     數(shù)字簽名待拷問

     對于王小云教授來說，無論破解現(xiàn)有的算法還是設(shè)計(jì)新的算法，都只是理論上的一種研究；但是對其他人來講，王小云教授給出的“碰撞”早已超出了兩篇論文的沖擊。

     2005年4月1日，也就是記者截稿的這一天，《電子簽名法》在我國開始正式實(shí)施，這部法律規(guī)定，可靠的電子簽名與手寫簽名或蓋章具有同等的法律效力，而面對這種關(guān)鍵的數(shù)字簽名算法產(chǎn)生的新問題，電子簽名法的實(shí)施將面臨一次考驗(yàn)。

     早在去年8月王小云教授公布MD5碰撞的研究成果時(shí)，中國金融認(rèn)證中心（CFCA）就在其網(wǎng)站上發(fā)布了一份聲明，該聲明稱：“CFCA在建立之初，已經(jīng)對MD5以及其他算法進(jìn)行了安全性評估。因此，在CFCA提供的應(yīng)用產(chǎn)品和服務(wù)中，并沒有采用MD5等不安全的算法，而是采用了安全的SHA-1算法，用戶可以放心地使用；CFCA提供的安全應(yīng)用工具包默認(rèn)使用的哈希算法也是SHA-1算法，考慮到工具包對其他應(yīng)用的互操作性要求，工具包也提供了MD5算法，如果用戶在使用工具包進(jìn)行開發(fā)時(shí)，不使用默認(rèn)的算法而采用了MD5算法，請立即修改自己的程序，采用默認(rèn)的SHA-1算法，以避免MD5的缺陷產(chǎn)生的影響。”這份聲明至今還掛在CFCA的網(wǎng)站上，但聲明中提到的“安全的SHA-1算法”顯然已被王小云教授的最新研究成果證明是和“曾經(jīng)安全的MD5”一樣不再值得人們信賴了。

     不過，王小云教授也表示，現(xiàn)在對SHA-1的研究仍是理論破解，并未像MD5那樣已經(jīng)有實(shí)際應(yīng)用的例子，所以人們還沒有必要對銀行存款之類的安全問題產(chǎn)生太多的擔(dān)心。但沒有立即的威脅出現(xiàn)并不表示會一直太平無事，對于有關(guān)部門來說，確實(shí)該考慮提前將SHA-1換成更安全的算法了。

     對于SHA-1碰撞的實(shí)際意義，王小云教授的合作者，參與過SHA-1算法研究的尹依群博士曾在美國接受媒體采訪時(shí)透露，現(xiàn)在使用王小云教授的方法，要找到SHA-1的一個(gè)碰撞，需要的計(jì)算能力大約相當(dāng)于用5萬臺超級計(jì)算機(jī)工作100年，這已經(jīng)超出了現(xiàn)有計(jì)算資源的能力范圍。同時(shí)，尹博士也指出，這并不能排除近期內(nèi)SHA-1快速找到實(shí)際碰撞的可能性，她也認(rèn)為盡快將SHA-1更換到更安全的算法是很有必要的。

     隨著王小云教授的研究成果被越來越多的人所了解，業(yè)界對于MD5和SHA-1在數(shù)字簽名中的應(yīng)用開始逐漸分化成兩種態(tài)度。

     來自學(xué)術(shù)界的研究人員多認(rèn)為MD5和SHA-1的安全性既然已經(jīng)無法在技術(shù)上絕對保證，那么在實(shí)際的應(yīng)用中就應(yīng)該盡可能地考慮到算法漏洞的影響，至少在法律上，這些已經(jīng)被證明不夠安全的算法不應(yīng)該再作為數(shù)字簽名的法律依據(jù)。

     而企業(yè)面對的問題就沒有那么單純，如果這些算法必須更換，那就意味著對部分產(chǎn)品的前期投入成為浪費(fèi)，尤其是芯片級的固件，加密算法一經(jīng)寫入就很難更改，產(chǎn)品的生命周期隨著所采用的加密算法的失效將走到盡頭。所以對于這些企業(yè)來說，更換算法就意味著更換產(chǎn)品，隨之而來的就是成本的增加；不更換算法，產(chǎn)品就要在未來承受未知的安全風(fēng)險(xiǎn)，一旦出現(xiàn)問題，后果更為嚴(yán)重。

     某信息安全企業(yè)的技術(shù)總監(jiān)告訴記者，既然王小云教授的研究成果從理論到實(shí)際上都撼動了Hash函數(shù)這個(gè)數(shù)字簽名算法的根基，現(xiàn)在留給業(yè)界的將是看起來矛盾重重的混亂局面，“包括我們在內(nèi)的很多廠商都要盡快考慮更換算法的問題，尤其是在數(shù)字簽名中應(yīng)用了MD5算法的產(chǎn)品，升級已勢在必行。雖然沒有哪家企業(yè)愿意對外公開這種影響，但這個(gè)工作大家都必須盡快著手去做了。”

     鏈接一

     國際頂尖密碼學(xué)專家對王小云研究成果的評價(jià)

     Ronald L.Rivest（2002年圖靈獎獲得者，RSA密碼發(fā)明人之一，MD5的創(chuàng)造者，世界最權(quán)威的密碼學(xué)專家之一）：

     我的研究方向之一是“Hash函數(shù)”，這種函數(shù)是目前許多密碼系統(tǒng)應(yīng)用的核心。我曾經(jīng)設(shè)計(jì)過一些Hash函數(shù)，其中的MD5由于擁有優(yōu)越的高效及安全性能，得到了普遍的認(rèn)可和廣泛的應(yīng)用。盡管有人曾發(fā)現(xiàn)MD5函數(shù)的某些方面存在著安全隱患，但一直以來，MD5都無法被破解。此外，還有許多其他的密碼Hash函數(shù)（如SHA-1，RIPEMD等）情況也類似。

     然而令人驚異的是，在王小云教授的帶領(lǐng)下，MD5函數(shù)和其他一些Hash函數(shù)在近期都被破解了。MD5函數(shù)十幾年來經(jīng)受住了眾多密碼學(xué)專家的攻擊，而王小云教授卻成功地破解了它，這實(shí)在是一種令人印象極深的卓越成就，是高水平的世界級研究成果。這些結(jié)果無疑給人非常深刻的印象，她應(yīng)當(dāng)?shù)玫轿易顭崃业淖ＹR。當(dāng)然，我并不希望看到MD5就這樣倒下，但人必須尊重真理。

     Adi Shamir（2002年圖靈獎獲得者，RSA密碼發(fā)明人之一，SSSS的創(chuàng)造者）：

     關(guān)于王小云教授所做的工作，我想強(qiáng)調(diào)的是她所研究的Hash函數(shù)是近15年來密碼研究學(xué)中最不活躍的領(lǐng)域。所有主要的Hash函數(shù)早在1980年代末或1990年代初就已經(jīng)被發(fā)展和定型，并且后來幾乎也沒有再出現(xiàn)有過關(guān)其安全性的研究成果。而王教授的研究以獨(dú)特的方式打破了這種沉悶的局面，并對該領(lǐng)域的理論研究和實(shí)際應(yīng)用產(chǎn)生了極大的影響。特別是一些被廣泛應(yīng)用的Hash函數(shù)，如MD5，將不會再被使用。而未來的Hash函數(shù)將會以新的設(shè)計(jì)原則來發(fā)展。

     鏈接二

     MD5和SHA-1算法

     ■ 林居

     MD5和SHA-1都屬于散列（Hash）算法，其作用是可以將不定長的信息（原文）經(jīng)過處理后得到一個(gè)定長的摘要信息串，對同樣的原文用同樣的散列算法進(jìn)行處理，每次得到的信息摘要串相同。Hash算法是單向的，一旦數(shù)據(jù)被轉(zhuǎn)換，就無法再以確定的方法獲得其原始值。事實(shí)上，在絕大多數(shù)情況下，原文的長度都超過摘要信息串的長度，因此，在散列計(jì)算過程中，原文的信息被部分丟失，這使得原文無法從摘要信息重構(gòu)。散列算法的這種不可逆特征使其很適合被用來確認(rèn)原文（例如公文）的完整性，因而被廣泛用于數(shù)字簽名的場合。

     如果除了原文之外，對于另外一段不同的信息進(jìn)行相同散列算法，得到的摘要信息與原文的摘要信息相同，則稱之為碰撞，散列算法通?？梢员ＷC碰撞也很難根據(jù)摘要被求出。

     MD5（RFC1321）誕生于1991年，全稱是“Message-Digest Algorithm（信息摘要算法）5”，由MIT的計(jì)算機(jī)安全實(shí)驗(yàn)室和RSA安全公司共同提出，之前已經(jīng)有MD2、MD3和MD4幾種算法。MD5克服了MD4的缺陷，生成128bit的摘要信息串，出現(xiàn)之后迅速成為主流算法，并在1992年被收錄到RFC中。

     SHA誕生于1993年，全稱是安全散列算法（Secure Hash Algorithm），由美國國家安全局（NSA）設(shè)計(jì)，之后被美國標(biāo)準(zhǔn)與技術(shù)研究院（NIST）收錄到美國的聯(lián)邦信息處理標(biāo)準(zhǔn)（FIPS）中，成為美國國家標(biāo)準(zhǔn)，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是當(dāng)前應(yīng)用最為廣泛的兩種散列算法。常見的Unix系統(tǒng)口令以及多數(shù)論壇/社區(qū)系統(tǒng)的口令都是經(jīng)MD5處理后保存其摘要信息串，在互聯(lián)網(wǎng)上，很多文件在開放下載的同時(shí)都提供一個(gè)MD5的信息摘要，使下載方（通過MD5摘要計(jì)算）能夠確認(rèn)所下載的文件與原文件一致，以此來防止文件被篡改。

     MD5和SHA-1還常被用來與公鑰技術(shù)結(jié)合來創(chuàng)建數(shù)字簽名。當(dāng)前幾乎所有主要的信息安全協(xié)議中都使用了SHA-1或MD5，包括SSL（HTTPS就是SSL的一種應(yīng)用）、TLS、PGP、SSH、S/MIME和IPSec，因此可以說SHA-1和MD5是當(dāng)前信息安全的重要基礎(chǔ)之一。

     不過，從技術(shù)上講，MD5和SHA-1的碰撞可在短時(shí)間內(nèi)被求解出并不意味著兩種算法完全失效。例如，對于公文的數(shù)字簽名來說，尋找到碰撞與尋找到有特定含義的碰撞之間仍有很大的差距，而后者才會使偽造數(shù)字公文成為現(xiàn)實(shí)。但無論如何，王小云教授所掌握的方法已經(jīng)為短時(shí)間內(nèi)尋找到MD5或SHA-1的碰撞成為可能，這足以使經(jīng)過MD5或SHA-1處理的數(shù)字簽名再也難以成為法律認(rèn)可的依據(jù)。

本站是提供個(gè)人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自： Joshua > 《理論》

舉報(bào)/認(rèn)領(lǐng)