Hash函數(shù)RIPEMD-128和HMAC-MD4的安全性分析.pdf

1、目前，我們生活在信息社會里。隨著信息和通信技術(shù)的不斷發(fā)展，這些技術(shù)正日益走入越來越多人的生活。這些發(fā)展和應(yīng)用給我們帶來了實質(zhì)性的利益，但是同時也帶了諸多危害，它使我們的私人信息易于泄露，身份被他人盜用以及數(shù)據(jù)被他人篡改．為了避免這些危害，我們需要建立和發(fā)展值得信賴的信息體制。這些可信賴的體制及建立它們的基石是密碼學(xué)研究的主要課題． 密碼學(xué)[1]是研究數(shù)學(xué)技術(shù)及相關(guān)的保密性、數(shù)據(jù)完整性、實體認(rèn)證、數(shù)據(jù)源認(rèn)證等信息安全各領(lǐng)域的綜合性

2、的學(xué)科。它運用了數(shù)論、概率論、統(tǒng)計學(xué)、組合學(xué)等數(shù)學(xué)知識，并涉及信息論、計算復(fù)雜性、編碼理論等學(xué)科知識．它不僅為信息安全提供服務(wù)和途徑，而且還帶來了一系列技術(shù)革新。 Hash函數(shù)在現(xiàn)代密碼學(xué)中起著重要的作用。它可以將任意長度的輸入壓縮為固定長度的值，輸出值我們稱為Hash值。根據(jù)其定義和性質(zhì)，Hash函數(shù)可用于保證數(shù)據(jù)完整性和實體認(rèn)證，同時也是多種密碼體制和協(xié)議的安全保障，例如數(shù)字簽名、消息認(rèn)證碼等。Hash函數(shù)用于數(shù)據(jù)簽名可帶來

3、諸多好處：可破壞數(shù)字簽名方案的某種數(shù)學(xué)結(jié)構(gòu)；可提高數(shù)字簽名速度；無需泄露簽名所對應(yīng)的消息；可將簽名變換和加密變換分開。 目前，標(biāo)準(zhǔn)的Hash函數(shù)分為兩大類：MDx系列(MD4[11]，MD5[2]，HAVAL[12]，RIPEMD[13]，RIPEMD-128[6]，R[PEMD-160[6]等)和SHA系列(sHA-O[14]，SHA-1[3]，SHA-256，384，512[15]等)．這些Hash算法體現(xiàn)了Hash函數(shù)的設(shè)

4、計技術(shù)。MD4算法是較早出現(xiàn)的Hash函數(shù)算法，它使用了基本的算術(shù)和布爾運算，其設(shè)計原則采用了迭代結(jié)構(gòu)[30，43]的思想。在MD4算法公布后，許多}lash函數(shù)算法相繼提出來，包括MD5、HAVAL、RIPEMD、RIPEMD-128、RIPEMD-160、SHA-0和SHA-1等，它們的大多數(shù)算法也是基于MD4算法的設(shè)計原則．RIPEMD算法是歐洲計劃RIPE[13]的組成部分．RIPEMD-128算法是1996年由Hans Dob

5、bertin，Antoon Bosselaers和Bart Preneel提出來的，用于替代RIPEMD算法，其輸出Hash值為128比特．該算法由兩個平行獨立的操作部分組成，我們分別稱為左路和右路，兩部分都由四圈組成，每圈都包括一個圈函數(shù)，每個圈函數(shù)有不同的函數(shù)特性，用于以后的攻擊中。兩部分操作的輸出結(jié)果進行運算用于生成Hash函數(shù)值．通常，我們討論Hash函數(shù)的安全性，其包括三個特性，分別是抗原根性、抗第二原根性和抗碰撞性．所以對于

6、不同特性在分析中存在多種不同的攻擊方法。在近十幾年里，對于Hash函數(shù)的分析取得了一些進展．生日攻擊是一般的攻擊方法，其名字來源于“生日問題”，可用于任何類型的Hash函數(shù)，其復(fù)雜性依賴于Hash值的長度。1996年，H.Dobbertin[16]給出了一個對MD4算法全算法攻擊，該攻擊以2-<'22>的概率找到一個碰撞。1998年，H.Dobbertin[17]證明了MD4算法的前兩圈不是單向函數(shù)，這一結(jié)論意味著對于尋找原根和第二原根

7、存在有效的攻擊。對于RIPEMD算法，H.Dobbertin[18]可以以2<'31>的復(fù)雜性找到兩圈RIPEMD的碰撞。 隨著MDx系列Hash函數(shù)的發(fā)展，對于這些函數(shù)的安全性分析也不斷增加。B．den Boer和A.Bosselaers[19]找到了針對MD5算法的一種偽碰撞，即同一明文在不同初始值下的Hash函數(shù)值相同．在1996年歐洲密碼大會上，H.Dobbertin[20]公開了另一種形式的偽碰撞，即在兩個不同的初始值

8、下的不同消息的一個碰撞。在1998年國際密碼大會上，F(xiàn).Chalbaud和A．Joux[21]證明了用差分攻擊方法可以以2-<'61>的概率找到SHA-0的一個碰撞。2003年亞密會上，B．V．Rompay[22]等人給出了以2-<'29>的概率針對HAVAL-128算法的碰撞攻擊。 一些針對Hash函數(shù)的強力有效的攻擊方法及結(jié)果出現(xiàn)在2004年。Eli Biham和Rafi[23]提出了對SHA-0算法的幾乎碰撞。A.Joux

9、[25]給出了一個由4個明文構(gòu)成的SHA-O的碰撞．這些結(jié)果中，最為顯著的是在2004年國際密碼學(xué)大會上，王小云[7，8，9，10]等人宣布的對于一系列Hash函數(shù)的碰撞結(jié)果，包括MD4、MD5、HlAVAL-128和RIPEMD算法，其可以找到MD4和RIPEMD算法碰撞的復(fù)雜性分別低于2<'8>和2<'18>。同時，王小云提出了一套新的針對MDx系列的Hash函數(shù)的分析技術(shù)，給出了得到滿足差分路線的充分條件的方法，以及如何使用明文修

10、改技術(shù)來提高碰撞攻擊的成功概率。隨后，在2005年，王小云等使用此技術(shù)對MD5、SHA-0、SHA-1算法進行攻擊，取得了較好的結(jié)果，并證明這些技術(shù)對于Hash函數(shù)分析是十分有效的。此攻擊方法還可以用于MD4算法的第二原根攻擊[26]，以及HMAC和NMAC的偽造攻擊及部分密鑰恢復(fù)攻擊[28]．差分分析是由E.Biham和A．Shamir[34]于1990年提出的，它是針對對稱密碼體制(分組密碼、流密碼、Hash函數(shù)和MlAC算法)的選

11、擇明文(或選擇密文)攻擊最有效的方法之一．它的主要思想是通過分析特定明文差分對對結(jié)果密文差分的影響來獲得可能性最大的密鑰。王小云等基于差分分析的思想，采用不同于傳統(tǒng)異或差分的模減差分(H.Dobbertin也采用過此類差分[16，20，18])，提出了一系列對標(biāo)準(zhǔn)Hash函數(shù)算法MD4，RLPEMD，HAVAL，MD5，SHA0，SHAl[7，8，9，10]的攻擊。在王小云等人的方法中，經(jīng)過對Hash函數(shù)算法的的明文差分通過每輪圈函數(shù)的

12、整數(shù)模減差分和異或差分的分析，得到差分特征，以得到更多的信息來尋找碰撞． 在本文中，我們詳細(xì)介紹了Hash函數(shù)，包括Hash函數(shù)的基本定義、性質(zhì)、設(shè)計原則、應(yīng)用以及針對Hash函數(shù)的攻擊方法等基本知識。本文的主要工作分為兩部分．一是給出了針對RIPEMD-128算法后三圈的碰撞攻擊．另一個是對HMAC-MD4內(nèi)部函數(shù)的安全性分析．這兩部分中的攻擊都采用王小云等提出的對于國際通用標(biāo)準(zhǔn)Hash函數(shù)的攻擊方法． 在第四章中，我

13、們定義整數(shù)模減差分為：對于兩個輸入X和X<'′>，△X=X<'′>-X。在此攻擊中，我們采用的差分是帶正負(fù)標(biāo)記的整數(shù)模2<'32>的模差分和異或差分．其中，我們用帶正負(fù)標(biāo)記的比特位置來標(biāo)記異或差分，對于X中比特值為0的比特位不帶標(biāo)記，X中比特為值1的定義為負(fù)標(biāo)記。例如，對于差分-2<'23>，[24，25，26，27，28，-29]表示整數(shù)模減差分X<'′>-X=-2<'23>，其中比特進位從第24比特到第29比特。X中第24比特到第2

14、8比特值為0，第29比特值為1，而對于X’，第24比特到第28比特值為1，第29比特值為0。異或差分就是這些由比特進位帶來的差分． 對算法的攻擊過程包括以下三步： 第一步選擇滿足后三圈RIPEMD-128算法的明文差分由于RIPEMD-128算法是由兩部分平行且獨立的操作組成的，所以選擇明文差分，使其同時滿足兩部分操作以產(chǎn)生差分路線是比較困難的。通過分析明文分組在兩部分中每圈中位置，以及非線性圈函數(shù)的性質(zhì)，并考慮明文修改

15、技術(shù)的操作特點，我們選擇兩比特的明文差分如下：△H<,0>=0 △H=0，△M=M<'1>-M=(△mo，△m<,1>..，△m<,15>)，對應(yīng)的輸出差分為：△m<,1>=2<'31>; △m<'14>=2<'23>，△m<,i>=0，0≤i≤15，i≠1，14．△<,α>=△cc+△ddd=0．△b=△dd+△aaa=0，△c=△aa+△bbb=(2<'31>+2<'31>)mod 2<'32>=0，△d=△bb+△ccc=0．我們

16、可以分別得到RIPEMD-128算法后三圈兩部分操作的差分路線。 根據(jù)算法中布爾函數(shù)的性質(zhì)和差分特性，我們將得到滿足差分特征的碰撞路線充分條件，這個過程在我們的攻擊中也是至關(guān)重要的．它與碰撞路線是密切相關(guān)的，若充分條件中有矛盾出現(xiàn)，不能滿足滿分特征，則表明碰撞路線是錯誤的，不能產(chǎn)生碰撞。 第三步對于明文M，通過簡單明文修改技術(shù)，可以減少第一圈的充分條件，再通過高級明文修改技術(shù)，可以減少更多條件，并保證差分路線正確，且條件

17、不產(chǎn)生矛盾，可將充分條件分別降為19和36個，總計55個。 根據(jù)以上的攻擊過程，我們可以以2-<'55>的碰撞概率，找到后三圈RIPEMD-128算法的碰撞，低于生日攻擊的2-<'64>的碰撞概率。由于RIPEMD-128算法的由兩條平行的操作組成，且其圈函數(shù)不同于其他標(biāo)準(zhǔn)Hash函數(shù)算法，所以找到該算法的碰撞路線及其滿足給路線的充分條件都是比較困難的，本文中給出的攻擊結(jié)果是首次對RIPEMD-128算法后三圈攻擊的結(jié)果。