陳俊良Chen, Chuen-Liang臺灣大學:資訊工程學研究所陳志順Chen, Chih-ShunChih-ShunChen2010-06-092018-07-052010-06-092018-07-052009U0001-2001200921182700http://ntur.lib.ntu.edu.tw//handle/246246/185366赫序函數將任意長度的資訊壓縮成一固定長度的訊息摘要，產生類似「指紋」的效用，以驗證原始訊息是否遭到更動或防止來源/目的端的否認，其應用涵蓋數位簽章、訊息認證、電子商務、線上金融交易與通行密碼等領域。今應用最廣泛的赫序函數是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.owadays 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.o 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.n 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.口試委員會審定書 ………………………………… i謝 ………………………………………………… ii文摘要 ……………………………………………iii文摘要 …………………………………………… v一章 MD5赫序函數簡介 1 第一節 赫序函數的簡介 1 第二節 MD5的背景說明 2 第三節 MD5的函數邏輯 3二章 如何找出MD5的碰撞 13 第一節 生日攻擊法 13 第二節 中間相遇攻擊法 13 第三節 差分分析法 14 第四節 王小雲MD5碰撞方法 14三章 王小雲破解MD5關鍵技術的突破 17 第一節 王小雲破解MD5的關鍵技術 17 第二節 推導論文表3、4第1、2回合的條件 19 第三節 推導論文表3、4第3、4回合的條件 27 第四節 推導論文表5、6及兩個BLOCKS的碰撞 37四章 MD5被王小雲破解之弱點與反制之道 41五章 結論 44考文獻 461020680 bytesapplication/pdfen-US赫序函數雜湊函數王小雲碰撞破解差分攻擊Xiaoyun WangMD5hash functioncollisionDifferential Attackthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/185366/1/ntu-98-P93922006-1.pdf