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