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

The Research of Key Technology in Breaking MD5 Hashing Function

陳志順(Chih-Shun Chen)

指導教授 ： 陳俊良

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.10467

摘要

赫序函數將任意長度的資訊壓縮成一固定長度的訊息摘要，產生類似「指紋」的效用，以驗證原始訊息是否遭到更動或防止來源/目的端的否認，其應用涵蓋數位簽章、訊息認證、電子商務、線上金融交易與通行密碼等領域。
現今應用最廣泛的赫序函數是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.

並列關鍵字

Xiaoyun Wang ； MD5 ； hash function ； collision ； Differential Attack

參考文獻

2. Xiaoyun Wang and Hongbo Yu, “How to break ND5 and other hash functions,” EUROCRYPT 2005. LNCS, vol. 3494, Springer, 2005, pp. 19-35.

6. Stallings, W., “Cryptography and Network Security: Principles and Practice,” Third edition, Prentice Hall, 2003.

7. Damgard, I. B., “A design principle for hash functions,” Advance in Cryptology, Crypto’89 Proceedings, Springer-Verlag, 1990.

1. R. Rivest, “The MD5 Message-Digest Algorithm,” Network Working Group, Request for Comments 1321, April 1992.

3. John Black, Martin Cochran and Trevor Highland, “A Study of the MD5 Attacks: Insights and Improvements,” Fast Software Encryption 2006. LNCS, vol. 4047, Springer, 2006, pp. 262-277.