破解赫序函數MD5關鍵技術之探究

Abstract

赫序函數將任意長度的資訊壓縮成一固定長度的訊息摘要，產生類似「指紋」的效用，以驗證原始訊息是否遭到更動或防止來源/目的端的否認，其應用涵蓋數位簽章、訊息認證、電子商務、線上金融交易與通行密碼等領域。 現今應用最廣泛的赫序函數是MD5與SHA-1，兩者都是美國國家標準與技術研究院所認可的赫序函數。山東大學的王小雲教授於2004年8月在美洲密碼年會（Crypto’2004）中發表破解MD5報告[2]，又於2005年2月RSA年會由密碼大師A.Shamir宣布找到了SHA-1的安全漏洞，在密碼學及資訊安全界造成了極大的震撼。 王小雲破解MD5係使用差分攻擊法，並提供找到碰撞所需之明文及中間值的差異條件，符合這些條件即可產生碰撞。至於這些碰撞條件是如何建立的？論文中並未說明，目前學界也並未針對此問題加以探討，然這卻是王小雲破解MD5的關鍵技術所在。 在本篇論文中，我們深入研究MD5赫序函數的性質與邏輯，並發現其弱點；然後分析王小雲破解MD5的方法，進而研獲碰撞條件建立的原因，並逐步推導，所獲結果與王小雲的結果幾乎一樣，足資印證我們的論點；最後，我們針對王小雲破解MD5方法提出反制之道，俾供研發新一代更安全的赫序函數參考。

Hash functions are used to compress variable-length message into a fix-length message digest, similar to finger-print, for the purpose of verifying the original message is changed or not and preventing denied by sender or receiver. Hash functions have been applied in digital signature, message authentication, electrical commercial, on-line financial transaction, password and so on. Nowadays the most well-known hash functions are MD5 and SHA-1 which both are ANSI-standards. Professor Xiaoyun Wang of Shandong University, China announced report of breaking MD5[2] in Crypto 2004. Then A.Shamir announced weakness of SHA-1 for Wang in RSA 2005. Both events established milestones in cryptology and information security. To break MD5, Wang makes use of differential attack and offers necessary collision conditions for plain and middle parameter values. As for these conditions, Wang didn’t mention how they were deduced, neither did other scholars. Nevertheless it is the key technology of breaking MD5. In this paper, the algorithm and weakness of MD5 are presented. Then Wang’s method of breaking MD5 and reasons of collision conditions are given. Finally, a solution to resist Wang’s attack is proposed to add to the guidelines of designing more secure next-generation hash functions.