對(duì)4圈雜湊函數(shù)HAVAL-160的一個(gè)攻擊.pdf

1、雜湊函數(shù)是信息安全中一個(gè)非常重要的工具，它對(duì)一個(gè)任意長(zhǎng)度的消息m施加操作，返回一個(gè)固定長(zhǎng)度的雜湊值h(m)，雜湊函數(shù)是公開的，對(duì)處理過(guò)程不用保密。單向雜湊函數(shù)的安全性取決于它的單向性，其輸出不依賴于輸入。雜湊函數(shù)是許多密碼算法和協(xié)議的安全保證，它廣泛用于簽名、群簽名、MAC碼、電子錢幣、比特承諾、電子選舉等。 目前受到人們廣泛關(guān)注和青睞的是標(biāo)準(zhǔn)雜湊函數(shù)，而標(biāo)準(zhǔn)雜湊函數(shù)又可分為兩大家族：MDx家族(MD4、MD5、HAVAL、RI

2、PE-MD、RIPE-MD-160)和SHA家族(SHA-0、SHA-1、SHA-256，384，512)。這些雜湊算法揭示了雜湊函數(shù)主要的設(shè)計(jì)技術(shù)。 目前，標(biāo)準(zhǔn)雜湊函數(shù)的分析技術(shù)已經(jīng)取得了很大的進(jìn)展。HansDobbertin于1996年對(duì)MD4給出了一個(gè)攻擊，可以以2-22找到一個(gè)碰撞；1997年，Kasselman對(duì)MD4給出了一個(gè)更為有效的攻擊。對(duì)于MD5，B.denBoer和A.Basselaersobber找到了MD

3、5的一類偽碰撞——在兩組不同的初始值下得到同一明文的相同的雜湊值；在1996年歐密會(huì)上，Dobbertin給出了MD5的一個(gè)碰撞——在另一初始值下得到兩組不同的報(bào)文；2004年美密會(huì)上，王小云對(duì)MD5的攻擊引起了國(guó)際密碼界的轟動(dòng)，王小云利用比特追蹤法尋找碰撞路線、推出碰撞發(fā)生的必要條件、修改明文提高碰撞發(fā)生的概率可很容易找到一個(gè)碰撞。2003年，B.V.Rompay等對(duì)3圈雜湊函數(shù)HAVAL有一個(gè)攻擊，其計(jì)算復(fù)雜度為229。而王小云于2

4、004年利用破譯MD5的技術(shù)同樣找到了概率為2-7的3圈雜湊函數(shù)HAVAL-128的碰撞。至于SHA家族，2005年一月，王小云對(duì)SHA-1的研究又取得巨大進(jìn)展，其計(jì)算復(fù)雜度少于269雜湊運(yùn)算。 雜湊函數(shù)HAVAL是由Y.Zheng等在Auscrypto'92提出的，該體制可以在3、4或5圈壓縮任意長(zhǎng)度的報(bào)文并輸出長(zhǎng)度為128-比特、160-比特、192-比特或224-比特的雜湊值。 本文利用王小云教授提出的比特追蹤方法