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

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

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

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

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

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

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

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

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