關于MD5算法破解對實際應用影響的讨論

關于MD5算法破解對實際應用影響的讨論

國家資訊中心資訊安全研究與服務中心　

李丹

北京天威誠信電子商務服務有限公司　龍毅宏

摘要：

在2004國際密碼學會議（Crypto’2004）上，

王

小雲

教授公布了破解MD5算法的研究成果，引起了密碼學界轟動，國内有些媒體甚至認為這一破解會導緻數字簽名安全大廈的轟然倒塌，那麼，實際情況究竟是怎樣的呢？本文就MD5算法破解對實際應用的影響進行分析讨論，回答了這個問題。

正文：

在2004年8月17日美國加州聖巴巴拉召開的國際密碼學會議（Crypto’2004）上，來自中國山東大學的王小雲教授做了破解MD5算法的報告。當她公布了她的研究結果之後，會場上響起激動的掌聲。王小雲教授的報告轟動了全場，得到了與會專家的贊歎。國内有些媒體甚至認為這一破解會導緻數字簽名安全大廈的轟然倒塌。那麼，實際應用的情況究竟是怎樣的呢？

    MD5是一種雜湊演算法(Hash function)，又稱為雜湊演算法、消息摘要算法，它的作用是擷取數字資訊的特征(我們有時稱之為“資訊指紋)。一個任意長度的任意數字資訊，通過雜湊演算法運算後，會産生一串固定長度(比如160bit)的數字資訊，稱為散列值(或哈希值、消息摘要)。安全的雜湊演算法有這樣的特點：

⑴ 兩個不同數字資訊産生同樣的散列值的機率是非常小的(小到現實中幾乎無法發生)；

⑵ 僅從散列值無法演推出原資訊；

⑶ 原資訊的微小改變，哪怕隻改變一位(bit)，将導緻散列值的很大變化。

數字簽名要使用散列值。MD5是一種常用雜湊演算法，另外目前常用的雜湊演算法還有SHA-1。兩個不同的數字資訊産生相同的散列值就是人們所說的“散列值碰撞“。雜湊演算法是一個将無窮維空間的資訊映射到有限維空間的變換，學過數學的人都知道這不是一個一一對應的變換。實際上一個散列值可能對應有無窮多個數字資訊，換言之，會有無窮多個數字資訊産生同樣一個散列值。這點是研究密碼的人衆所周知的，而不像有些媒體所說的那樣，散列值是唯一的。

一個安全雜湊演算法的安全性是基于這樣的假設，知道一個資訊A的散列值H，很難找到，或者從H倒推出另一個資訊B具有同樣的散列值H。中國學者的發現是這樣的，對于MD5雜湊演算法，針對某些資訊集合，找到了一種方法，當我們知道它的散列值H時，能推出一個資訊資料B具有同樣的MD5散列H。需要強調的是，王小雲教授的破解算法是一個機率性的破解算法，隻對部分資訊集合适用。這當然是密碼學界的一個重大發現，這說明了MD5不像我們原先認為的那樣安全。但是，這個研究發現的實際影響要遠遠小于它的理論意義。這可以從以下幾方面加以說明。

根據MD5破解算法，對一個資訊A及其散列值H，我們有可能推出另一個資訊B，它的MD5散列值也是H 。現在的問題是，如果A是一個符合預先約定格式的、有一定語義的資訊，那麼演推出的資訊B将不是一個符合約定格式、有語義的資訊。比如說，A是一個甚于Word文檔的、有語義的電子合同，而B卻不可能是一個剛好符合Word格式的文檔，隻能是一堆亂碼，也就是說，B不可能是一個有效的、有意義的并且符合僞造者期望的電子合同。再比如說，A是一個符合X509格式的數字證書，那麼我們推出的B不可能剛好也是一個符合X509格式而且是僞造者希望的數字證書。

還有我們知道，電子合同是需要雙方、甚至多方電子簽名的。對于雙方簽名，這相當于我們先産生A的散列值H1，然後對A和H1合起來的資訊進一步産生散列值H2。我們目前的研究發現還無法找到一個方法，推出一個資訊B剛好産生同樣的H1和H2。（這個B是一定存在的!隻是目前不知道怎樣找!)

其次，MD5被破解了，我們現在還有SHA-1等其他雜湊演算法，以後還可以有新的、更安全的雜湊演算法。

總之，這裡MD5算法的破解對實際應用的沖擊要遠遠小于它的理論意義，不會造成PKI、數字簽 名安全體系的崩潰，這也是為什麼MD5雜湊演算法的破解并沒有造成密碼界、PKI行業的恐慌的原因。當然，我們也為中國人在密碼學上取得的傑出成就起立鼓掌。

參考文獻

【1】       2004國際密碼學會議（Crypto’2004）破譯MD5、HAVAL-128、 MD4和RIPEMD算法的報告　王小雲等

【2】       應用密碼學，Bruce Schneier著，吳世忠等譯。