對縮減輪數SM3散列函數改進的原像與偽碰撞攻擊

鄒劍，董樂

?

對縮減輪數SM3散列函數改進的原像與偽碰撞攻擊

鄒劍1,2，董樂3

（1. 福州大學數學與計算機科學學院，福建 福州 350108；2. 福州大學網絡系統信息安全重點實驗室，福建 福州 350108；3. 河南師范大學大數據統計分析與優化控制河南工程實驗室，河南 新鄉 453007）

提出了對SM3散列函數32輪的原像攻擊和33輪的偽碰撞攻擊。利用差分中間相遇攻擊與biclique技術改進了對SM3的原像分析結果，將攻擊結果從之前的30輪提高到了32輪。基于上述方法，通過擴展32輪原像攻擊中的差分路徑，對SM3構造了33輪的偽碰撞攻擊。以2254.5的時間復雜度與25的空間復雜度構造了對SM3的32輪原像攻擊，并以2126.7的時間復雜度與23的空間復雜度構造了對SM3的33輪偽碰撞攻擊。

SM3散列函數；原像攻擊；偽碰撞攻擊；差分中間相遇攻擊；biclique

1 引言

散列函數在密碼學中扮演著重要的角色，被廣泛地應用于消息認證等密碼應用中。一般來說，散列函數必須滿足3種安全目標：抗原像攻擊、抗第二原像攻擊和抗碰撞攻擊。

隨著SHA-3競賽的展開，各種新型攻擊方法不斷涌現，如中間相遇攻擊、反彈攻擊等。目前，中間相遇攻擊已經被廣泛地用于求解散列函數的原像值，并已對多個散列函數取得了有效的分析結果，如MD5[1]、Tiger[2]，以及SHA-0和SHA-1[3]。在FSE2012上，Dmitry等[4]提出了biclique方法來改進中間相遇攻擊，并對SHA-256散列算法構造了52輪的原像攻擊。同年，Li等[5]也通過轉化中間相遇攻擊，對散列函數構造了相應的偽碰撞攻擊。隨后，Knellwolf等[6]在Crypto2012上利用差分技術改進了中間相遇攻擊，并給出了對SHA-1散列算法57輪的原像攻擊。

SM3是由王小云等自主設計的散列函數，它于2010年被選為中國商用散列函數標準。SM3的總體設計方案與SHA-256類似。不過SM3采用了更復雜的輪函數，因此，SM3比SHA-256更能抵抗目前已知的攻擊。

本文利用差分中間相遇攻擊等方法改進了對SM3的原像攻擊，把攻擊結果由之前的30輪[7~9]提高到32輪，并利用對SM3的偽原像攻擊構造了對SM3的33輪偽碰撞，如表1所示。

2 SM3散列函數介紹

SM3采用大端設計，并按如下方式生成散列值。

表1 攻擊結果對比

在圖1中，SM3所采用的函數分別為

其中，FF與GG這2個布爾函數在前16輪與后48輪的定義是不同的。

3 預備知識

3.1 切割縫合技術與biclique攻擊方法

切割縫合技術與初始化結構是由Aoki等[10]在攻擊MD4時提出的。切割縫合技術（如圖2所示）是將壓縮函數分割為132，使攻擊者可以從函數中選取一個中間狀態作為計算起始點，并通過反饋操作連接壓縮函數的初始值與目標值。

圖1 SM3步函數

圖2 切割縫合技術

圖3 2維biclique

3.2 差分中間相遇攻擊

5) 使用算法1來求解一個原像。

1[2j]1(⊕2j,2[2j])⊕Δ2;

end for

;

end for

返回⊕1i⊕2j;

end if

end for

3.3 將偽原像攻擊轉化為原像攻擊的一般方法

3.4 中間相遇攻擊轉化為偽碰撞攻擊的一般方法

4 對縮減輪SM3的偽原像與偽碰撞攻擊

本文將對SM3散列函數構造多個改進的原像攻擊與偽碰撞攻擊。首先，本文將展示如何對SM3構造31輪原像攻擊與偽碰撞攻擊；其次，通過將biclique增加一輪，本文能將31輪原像攻擊與偽碰撞攻擊擴展到32輪；最后，通過擴展后向塊差分路徑，進一步將32輪偽碰撞攻擊擴展到了33輪。

在本文原像與偽碰撞攻擊中，本文將采用文獻[8]提到的性質1與部分符號記法。

性質1的證明過程見文獻[8]。

4.1 對31輪SM3的原像與偽碰撞攻擊

圖4 2輪biclique

表2 31輪偽原像攻擊中對F1的差分特征路徑

4.2 對32輪SM3的原像與偽碰撞攻擊

表3 31輪偽原像攻擊中對F2?1的差分特征路徑

圖5 3輪biclique

表4 32輪偽原像攻擊中對F1的差分特征路徑

表5 32輪偽原像攻擊中對F2?1的差分特征路徑

4.3 對33輪SM3的偽碰撞攻擊

5 結束語

本文發現要對SM3構造原像攻擊是比較困難的，這是因為：1) SM3采用了復雜的步函數；2) SM3的消息填充算法限制了線性空間1和2的取值范圍。不過相比于中間相遇攻擊，本文發現差分中間相遇攻擊更適合用來構造對SM3的原像攻擊，這主要是由于SM3采用了線性化的消息擴展算法。利用差分中間相遇、切割縫合技術與biclique方法，提出了對SM3的32輪原像攻擊，以及33輪的偽碰撞攻擊。在本文之前，對SM3最好的原像結果只有30輪，而最好的偽碰撞攻擊只有32輪。

[1] SASAKI Y, AOKI K. Preimage attacks on step-reduced MD5[C]//The 13th Information Security and Privacy Australasian Conference. 2008: 282-296.

[2] GUO J, LING S, RRCHBERGER C. Advanced meet-in-the-middle preimage attacks: first results on full Tiger, and improved results on MD4 and SHA-2[C]//The 16th International Conference on the Theory and Application of Cryptology and Information Security. 2010: 56-75.

[3] CANNIERE D C, RECHBERGER C. Preimages for reduced SHA-0 and SHA-1[C]//The 28th Annual International Cryptology Conference, 2008: 179-202.

[4] KHOVRATOVICH D, RECHBERGER C, SAVELIEVA A. Bicliques for preimages: attacks on skein-512 and the SHA-2 family[C]//The 19th Fast Software Encryption International Workshop. 2012: 244-263.

[5] LI J, ISOBE T, SHIBUTANI K. Converting meet-in-the-middle preimage attack into pseudo collision attack: application to SHA-2[C]// The 19th Fast Software Encryption International Workshop. 2012: 264-286.

[6] KNELLWOLF S, KHOVRATOVICH D. New preimage attacks against reduced SHA-1[C]//The Advances in Cryptology 32nd Annual Cryptology Conference.2012: 367-383.

[7] ZOU J, WU W. L, WU S, et al. Preimage attacks on step-reduced sm3 hash function[C]//The 14th Information Security and Cryptology International Conference. 2011: 375-390.

[8] WANG G L, SHEN Y Z: Preimage and pseudo-collision attacks on step-reduced SM3 hash function[J]. Inf Process Lett, 2013, 113(8): 301-306.

[9] MENDEL F, NAD T, SCHLAFER M. Finding collisions for round-reduced SM3[C]//The Cryptographers' Track at the {RSA} Conference 2013. 2013: 174-188.

[10] AOKI K, SASAKI Y. Preimage attacks on one-block MD4, 63-step MD5 and more[S]//Workshop Records of SAC 2008. 2008: 82-98.

[11] PAUL C O A, MENEZES J, SCOTT A. Vanstone. handbook of applied cryptography[M]. CRC Press, 1996.

Improved preimage and pseudo-collision eattacks on SM3 hash function

ZOU Jian1, 2, DONG Le3

1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China 2. Key Lab of Information Security of Network Systems, Fuzhou University, Fuzhou 350108, China 3. Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang 453007, China

A preimage attack on 32-step SM3 hash function and a pseudo-collision attack on 33-step SM3 hash function respectively were shown. 32-step preimage attack was based on the differential meet-in-the-middle and biclique technique, while the previously known best preimage attack on SM3 was only 30-step. The 33-step pseudo-collision attack was constructed by using the same techniques. The preimage attack on 32-step SM3 can be computed with a complexity of 2254.5, and a memory of 25. Furthermore, The pseudo-preimage and pseudo-collision attacks on 33-step SM3 by extending the differential characteristic of the 32-step preimage attack were present. The pseudo-collision attack on 33-step SM3 can be computed with a complexity of 2126.7, and a memory of 23.

SM3 hash function, preimage attack, pseudo-collision attack, differential meet-in-the-middle, biclique

TP309

A

10.11959/j.issn.1000-436x.2018011

鄒劍（1985-），男，福建福州人，博士，福州大學講師，主要研究方向為散列函數和分組密碼的分析。

董樂（1980-），男，河南新鄉人，博士，河南師范大學副教授，主要研究方向為散列函數和分組密碼的分析。

2017-03-09；

2017-11-13

福建省中青年教師教育科研基金資助項目（No.JAT170097）；福州大學科研啟動基金資助項目（No.510150）

: The Education and Research Projects for Young Teachers in Fujian Province (No.JAT170097), The Research Startup Project of Fuzhou University (No.510150)