MD5-Hash函數的安全性分析.pdf

1、Hash函數是信息安全與密碼學領域中一個非常重要的基本工具。近幾年關于Hash函數的碰撞攻擊取得了舉世注目的成果。我國學者王小云等提出的基于模減的差分分析方法有效地攻破了MD4, MD5, RIPMD,HAVAL和SHA-0等一系列Hash函數，其攻擊算法復雜度都低于次壓縮函數運算，在一般的個人電腦上運算都可以找到碰撞實例。本文正是針對MD5-Hash函數的碰撞攻擊做進一步分析的最新研究成果。 基于王小云等在2005年歐密會上發(fā)

2、表的關于MD5-Hash函數的2-block 的碰撞差分鏈，本文給出了一種快速攻擊MD5-Hash函數的算法。研究發(fā)現，在王小云等發(fā)表的關于MD5-Hash函數碰撞攻擊的文章里給出的保持MD5碰撞差分鏈的導出條件不是充分的即這些條件不足以保持碰撞差分鏈，并且一些導出條件可以放寬從而擴大碰撞集合；為了給出一個充分的條件集合，本文研究了二進制加法進位的特性，通過反饋計算導出了一些附加條件，從而第一次給出了關于MD5-Hash函數的碰撞差分鏈

3、的充分條件集合。還特別證明了保持這條差分鏈的第一個block差分鏈成立的4個新添加的附加條件：a2,27 = 0, a2,29 = 0, a2,30 = 0 和 a2,31 = 0 是充分必要條件。在這基礎上，總結了推導Hash函數的模減碰撞差分鏈的充分條件集合的一般方法。基于充分條件集合，本文還改進了MD5的碰撞攻擊搜索算法，使得其計算復雜度比原來的算法降低了至少16倍; 在Pentium4 1.70GHZ CPU 的個人電腦上實驗，

4、該攻擊算法可以在5個小時內找到碰撞實例。 進一步的，本文從Dobbertin 95年歐密會時給出的關于MD5 Hash函數的半自由起始碰撞攻擊的一個碰撞實例出發(fā)，按照模減差分分析方法推導出了一條1-block 的MD5模減碰撞差分鏈。雖然目前還不能夠根據這條碰撞差分鏈構造出高效的攻擊算法，但是它至少說明了模減差分分析方法在分析Hash函數方面是非常有效的。 本文最后討論MD結構的致命缺陷，基于這一缺陷甚至可以構造出在實際