約減輪Hash函數(shù)HAS-160、RIPEMD-160和SM3的原像攻擊.pdf

1、Hash函數(shù)是現(xiàn)代密碼學(xué)的重要組成部分，它能夠?qū)⑷我忾L度的消息壓縮成固定長度的Hash值，被廣泛應(yīng)用于多種密碼協(xié)議中，如數(shù)字簽名，數(shù)據(jù)完整性保護和消息認證碼等。作為一個安全的Hash函數(shù)，需要至少滿足3個基本安全屬性，分別是抗碰撞攻擊、抗原像攻擊和抗第二原像攻擊。隨著一系列國際Hash標(biāo)準算法在碰撞攻擊方面的突破，原像攻擊也受到眾多密碼學(xué)家的重視。中間相遇攻擊在2008年被引入到Hash函數(shù)的原像攻擊中，成為原像攻擊的基本方法之一。隨后

2、，又有很多技術(shù)被融入到中間相遇攻擊中，如分段-鏈接技術(shù)、部分匹配技術(shù)、完全二分結(jié)構(gòu)體技術(shù)和初始結(jié)構(gòu)體技術(shù)等。但是基于中間相遇的原像攻擊的復(fù)雜度一般都很高，接近于暴力搜索的復(fù)雜度。同時Hash函數(shù)通常都包含消息擴展過程，這使構(gòu)造全部輪數(shù)的原像攻擊的難度增加?；谏鲜鲈?，Hash函數(shù)的原像攻擊主要有兩個方向，一個是如何提高攻擊的輪數(shù)，另一個是如何降低攻擊的復(fù)雜度。
　　本文分析了韓國Hash標(biāo)準算法HAS-160、ISO/IEC10

3、118-3Hash標(biāo)準算法RIPEMD-160和我國Hash標(biāo)準算法SM3密碼雜湊算法的安全性。它們均采用Merkle-Damg(a)rd結(jié)構(gòu)，消息分組長度512比特。Hash值長度分別為160比特、160比特和256比特。本文取得了三個重要成果:第一給出了HAS-160的71輪偽原像攻擊和71輪原像攻擊;第二給出了RIPEMD-160的31輪到35輪原像攻擊;第三給出了SM3密碼雜湊算法的29輪和30輪原像攻擊。就攻擊輪數(shù)而言，所有結(jié)

4、果均為當(dāng)前最好的原像攻擊。
　　HAS-160的偽原像和原像攻擊
　　HAS-160于2000年被提出，結(jié)構(gòu)與SHA-1相似，并在韓國得到了廣泛應(yīng)用。HAS-160的輪數(shù)最多的原像攻擊是Hong等人給出的從第1輪開始的67輪原像攻擊和從第13輪開始的68輪原像攻擊。對HAS-160的分析主要考慮如何提高原像攻擊的輪數(shù)。本文構(gòu)造了HAS-160的6輪完全二分結(jié)構(gòu)體，結(jié)合差分中間相遇攻擊給出了從第1輪開始的復(fù)雜度為2158.12

5、的71輪HAS-160的偽原像攻擊，將從第1輪開始的偽原像攻擊的輪數(shù)由67輪提高到71輪。但是該攻擊使用了消息填充所需的比特，不能滿足消息填充。通過調(diào)整壓縮函數(shù)的劃分形式以及線性空間的組合方式，改變完全二分結(jié)構(gòu)體的位置，避開了消息填充對線性空間的影響，將偽原像攻擊中線性空間所占的消息字由7個降低到4個，維數(shù)由3增加到5，提高了差分路線的概率，給出了從第7輪開始的71輪原像攻擊，其復(fù)雜度為2158.97。該結(jié)果將從中間輪開始的原像攻擊的輪

6、數(shù)由68輪提高到71輪。這是目前HAS-160的輪數(shù)最多的原像攻擊。
　　RIPEMD-160的原像攻擊
　　RIPEMD-160是RIPEMD的增強版本，該算法于1996年由Dobbertin，Bossselaers和Preneel提出，是ISO/IEC10118-3Hash標(biāo)準算法之一。它的壓縮函數(shù)采用雙分支結(jié)構(gòu)，增加了分段-鏈接的難度。目前，RIPEMD-160還沒有從第1輪開始的原像攻擊，從中間輪開始的輪數(shù)最多的原像

7、攻擊是Ohtahara等人給出的31輪結(jié)果。為了增加分析的輪數(shù)，將初始值作為完全二分結(jié)構(gòu)體的內(nèi)部變量，匹配選在右支的最后一輪的輸出變量上。通過搜索線性空間的位置，使初始值的低比特盡量保持不變，構(gòu)造了3.5輪的完全二分結(jié)構(gòu)體。使用差分中間相遇攻擊給出了從第1輪開始的31輪到34輪RIPEMD-160的原像攻擊，復(fù)雜度分別為2157.97、2157.75、2158.80和2158.91。這是首個從第1輪開始的RIPEMD-160的原像攻擊結(jié)

8、果。將線性空間選在同一個消息字內(nèi)部，給出了從第2輪開始的35輪RIPEMD-160的原像攻擊，復(fù)雜度為2159.38，這是目前RIPEMD-160的輪數(shù)最多的原像攻擊。該結(jié)果將從中間輪開始的原像攻擊的輪數(shù)由31輪提高到35輪。
　　SM3密碼雜湊算法的原像攻擊
　　SM3密碼雜湊算法由王小云教授等人設(shè)計，整體結(jié)構(gòu)和SHA-2相似，增加了雙字介入等屬性來提高其安全性。由于SM3密碼雜湊算法的前16輪采用全異或的布爾函數(shù)，構(gòu)造從