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

1、雜湊函數(shù)是信息安全中一個非常重要的工具，它對一個任意長度的消息m施加操作，返回一個固定長度的雜湊值h(m)，雜湊函數(shù)是公開的，對處理過程不用保密。單向雜湊函數(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è)計技術(shù)。 目前，標(biāo)準(zhǔn)雜湊函數(shù)的分析技術(shù)已經(jīng)取得了很大的進展。HansDobbertin于1996年對MD4給出了一個攻擊，可以以2-22找到一個碰撞；1997年，Kasselman對MD4給出了一個更為有效的攻擊。對于MD5，B.denBoer和A.Basselaersobber找到了MD

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

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