MD5-Hash函數(shù)的安全性分析.pdf

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

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

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

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