MD4和MD5碰撞攻擊之研究

Abstract

王小雲等人在密碼會議EuroCrypt2005 上發表他們對MD4 和MD5 的碰撞攻擊演算法。之後許多研究者根據他們的結果並相繼提出他們 對於碰撞攻擊演算法的改進。其中大部分研究者著重在如何讓訊息修 改演算法更有效率。在本篇論文中，我們改進了訊息修改演算法。對 於MD5，我們提出一些訊息修改的方法，能滿足第一個回合的一個充 分條件和第二個回合的五個充分條件。對於MD4，我們修正了之前MD4 碰撞攻擊演算法的一些錯誤。同時我們實作了對於MD4 和MD5 的碰撞 攻擊演算法。我們對於MD5 的碰撞攻擊演算法的實作平均大約需要 1.75 個小時去找出一組碰撞的訊息。根據我們的實驗，我們的實作 能在12 個小時內找到一組碰撞的訊息之機率為1。

In EuroCrypt2005, Wang et al. publish their collision searching algorithms for MD4 and MD5. Many researchers follow their results and publish their improvements on the collision searching algorithms. Many of them focus on how to do the message modification efficiently. In this thesis, we improve the message modification techniques. We use our message modification methods to satisfy 1 sufficient condition in the first iteration and 5 sufficient conditions in the second iteration for MD5. For MD4 collision searching algorithm, we correct the errors in the previous results. We implement the collision searching algorithm for both MD4 and MD5. Our implementation of the MD5 collision searching algorithm takes about 1.75 hours to give a collision pair in average. The successful probability to find the collision pair in 12 hours is 1 according to our experiments.