四圈HAVAL—128后三圈的碰撞攻擊.pdf

1、近年來(lái)，隨著計(jì)算機(jī)技術(shù)逐步成熟，人類正在步入數(shù)字化時(shí)代。信息化和網(wǎng)絡(luò)化成為世界經(jīng)濟(jì)與社會(huì)發(fā)展的大趨勢(shì)。無(wú)紙化辦公、網(wǎng)上銀行、電子商務(wù)等成為整個(gè)社會(huì)發(fā)展的需要，這也使得數(shù)字簽名等信息安全技術(shù)快速發(fā)展，安全性因素是數(shù)字簽名設(shè)計(jì)重中之重?，F(xiàn)在，HASH函數(shù)廣泛應(yīng)用于數(shù)字簽名、消息鑒別、完整性驗(yàn)證等信息安全領(lǐng)域，被認(rèn)為現(xiàn)代密碼學(xué)的核心技術(shù)之一。鑒于HASH函數(shù)的重要影響力，本文對(duì)HASH函數(shù)的分析做了一些工作。 先前一些密碼學(xué)家對(duì)HAS

2、H函數(shù)的分析做了一些很有意義的工作，H.Dobbertin在Eurocrypto'96的文章中，可以以1/222的概率找到MD4的一個(gè)碰撞。在1993年，BertdenBoer和AntoonBosselaers發(fā)現(xiàn)了MD5的同一消息而不同初始值的一個(gè)偽碰撞，H.Dobbertin[12]發(fā)現(xiàn)了由兩個(gè)不同明文(512比特)和一個(gè)選擇的初始值構(gòu)成的碰撞。在1995年，H.Dobbertin[13]還證明了簡(jiǎn)化到兩輪的RIPEMD不是強(qiáng)無(wú)碰撞

3、的。而更令人興奮的是對(duì)HASH函數(shù)的分析最近取得了實(shí)質(zhì)性突破。來(lái)自山東大學(xué)的王小云教授在2004年的美密會(huì)上宣布利用“比特追蹤法”對(duì)MD5、MD4、MRIPEMD、HAVAL等算法進(jìn)行了成功破譯，其中尤其是對(duì)當(dāng)前的HASH函數(shù)的兩個(gè)標(biāo)準(zhǔn)算法之一的MD5的破譯引起了密碼學(xué)領(lǐng)域極大關(guān)注，同時(shí)在這次會(huì)議上法國(guó)的Joux宣布找到了SHA-0的碰撞[24]，Biham和Chen宣布可以找到一個(gè)簡(jiǎn)化至40輪的SHA-1的碰撞。但是這并未結(jié)束，在20

4、05年2月中旬王小云教授又宣布了對(duì)另一標(biāo)準(zhǔn)算法SHA-1的完全攻擊，將尋找SHA-1的碰撞的概率降至1/269。至此，現(xiàn)實(shí)中廣泛使用的HASH函數(shù)全部被破譯。 HAVAL算法是1992年YuliangZbeng，JosefPieprzyk和JenniferSeberry在澳大利亞密碼會(huì)議上提出了一種HASH函數(shù)，這個(gè)算法是繼MD4、MD5等算法之后的又一個(gè)HASH函數(shù)。算法具有運(yùn)行速度快，使用靈活等優(yōu)點(diǎn)，并且當(dāng)時(shí)它的安全性被認(rèn)為

5、比較高。此后HAVAL算法被廣泛應(yīng)用于信息安全的諸多領(lǐng)域。HAVAL算法是現(xiàn)代密碼學(xué)中很有代表性的一種HASH函數(shù)，按照設(shè)計(jì)技術(shù)，可以將HAVAL歸于MD類的HASH函數(shù)，因此對(duì)于HAVAL的安全性分析具有很重要的研究?jī)r(jià)值。關(guān)于HAVAL算法的分析，至今最好的分析結(jié)果是王小云等在2005年發(fā)表在中國(guó)科學(xué)上的“HAVAL一128的碰撞攻擊”，該文對(duì)三圈HAVAL-128實(shí)施了完全攻擊，并得出一個(gè)很好的結(jié)論：“存在一種攻擊方法，可以在運(yùn)行2

6、7～29次HAVAL-128算法時(shí)間內(nèi)，找到HAVAL-128的一個(gè)碰撞”。由王小云教授對(duì)三圈HAVAL-128算法的破譯方法的啟發(fā)，本文是對(duì)四圈HAVAL-128算法的后三圈進(jìn)行了有效攻擊。 本文首先給出了四圈HAVAL-128各圈的圈函數(shù)的性質(zhì)，這些性質(zhì)將會(huì)應(yīng)用于對(duì)HAVAL算法的分析技術(shù)中，在HAVAL算法的每一圈中，都對(duì)應(yīng)有一個(gè)圈函數(shù)fi(x6，x5，x4，x3，x2，x1，x0)(i=1,2，3,4)，而進(jìn)行這個(gè)圈函數(shù)

7、之前，圈函數(shù)的輸入要先進(jìn)行一下置換變換φi(x6，x5，x4，x3，x2，x1，x0)(i=1,2,3,4)，我們將圈函數(shù)和置換變換復(fù)合后的函數(shù)fi(φ(x6，x5，x4，x3，x2，x1，x0))(i=1,2,3,4)作為新的圈函數(shù)，本文中就是給出了這個(gè)新的圈函數(shù)fi(φ(x6，x5，x4，x3，x2，x1，x0))(i=2,3,4)的一些性質(zhì)，例如在性質(zhì)1中有：f2(φ2(x6，x5，x4，x3，x2，x1，x0))=f2(φ2(x

8、6，x5，x4，x3，x2，x1，(x)0))(→)x1x6+x5=0。 隨后，經(jīng)過(guò)大量的數(shù)據(jù)分析，本文對(duì)四圈HAVAL-128的后三圈實(shí)施了有效的攻擊，得到了下面的結(jié)論。 結(jié)論：存在一種對(duì)于四圈HAVAL-128的后三圈的攻擊方法，可以在29～210次HAVAL運(yùn)算時(shí)間內(nèi)找到一個(gè)四圈HAVAL-128的后三圈的碰撞，如果利用明文修改等技術(shù)可以將這一攻擊時(shí)間縮減至27～28次HAVAL運(yùn)算。 可以將攻擊過(guò)程分為以

9、下幾步： 第一步：首先定義兩個(gè)選擇明文m，m′的差分： 設(shè)：m=(m0，m1，…，m31)，m′=(m0′，m1′，…，m31′)， 它們的差分為： △m=m′-m=(△m0，△m1，△m2，…，△m31)，這里的△mi=mi-mi′(i=0，1，2，…，31)。 第二步：找到一個(gè)部分碰撞，例如第103步到111步的碰撞，在這個(gè)碰撞中只要滿足△m28=210，△m19=-231，△mi=0(i=2

10、3,26,6,30,18,25)就可以通過(guò)一些控制條件把這兩個(gè)變化控制在這8步內(nèi)，而這些控制條件主要是由上一部分給出的四圈HAVAL-128的圈函數(shù)的性質(zhì)推出。 第三步：同第二步類似，在第二、三圈中尋找一個(gè)內(nèi)部碰撞路線，并推出這個(gè)內(nèi)部碰撞所需要的控制條件。這個(gè)碰撞路線是第38步開(kāi)始到第68步結(jié)束，由△m28=210，△m19=-231引起的變化都會(huì)被控制在這個(gè)內(nèi)部碰撞里面，而由△m1=0(0≤i≤31，i≠28,i≠19)知道在