對(duì)縮減輪數(shù)SM3散列函數(shù)改進(jìn)的原像與偽碰撞攻擊

鄒劍，董樂

?

對(duì)縮減輪數(shù)SM3散列函數(shù)改進(jìn)的原像與偽碰撞攻擊

鄒劍1,2，董樂3

（1. 福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108；2. 福州大學(xué)網(wǎng)絡(luò)系統(tǒng)信息安全重點(diǎn)實(shí)驗(yàn)室，福建 福州 350108；3. 河南師范大學(xué)大數(shù)據(jù)統(tǒng)計(jì)分析與優(yōu)化控制河南工程實(shí)驗(yàn)室，河南 新鄉(xiāng) 453007）

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

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

1 引言

散列函數(shù)在密碼學(xué)中扮演著重要的角色，被廣泛地應(yīng)用于消息認(rèn)證等密碼應(yīng)用中。一般來說，散列函數(shù)必須滿足3種安全目標(biāo)：抗原像攻擊、抗第二原像攻擊和抗碰撞攻擊。

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

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

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

2 SM3散列函數(shù)介紹

SM3采用大端設(shè)計(jì)，并按如下方式生成散列值。

表1 攻擊結(jié)果對(duì)比

在圖1中，SM3所采用的函數(shù)分別為

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

3 預(yù)備知識(shí)

3.1 切割縫合技術(shù)與biclique攻擊方法

切割縫合技術(shù)與初始化結(jié)構(gòu)是由Aoki等[10]在攻擊MD4時(shí)提出的。切割縫合技術(shù)（如圖2所示）是將壓縮函數(shù)分割為132，使攻擊者可以從函數(shù)中選取一個(gè)中間狀態(tài)作為計(jì)算起始點(diǎn)，并通過反饋操作連接壓縮函數(shù)的初始值與目標(biāo)值。

圖1 SM3步函數(shù)

圖2 切割縫合技術(shù)

圖3 2維biclique

3.2 差分中間相遇攻擊

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

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

end for

;

end for

返回⊕1i⊕2j;

end if

end for

3.3 將偽原像攻擊轉(zhuǎn)化為原像攻擊的一般方法

3.4 中間相遇攻擊轉(zhuǎn)化為偽碰撞攻擊的一般方法

4 對(duì)縮減輪SM3的偽原像與偽碰撞攻擊

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

在本文原像與偽碰撞攻擊中，本文將采用文獻(xiàn)[8]提到的性質(zhì)1與部分符號(hào)記法。

性質(zhì)1的證明過程見文獻(xiàn)[8]。

4.1 對(duì)31輪SM3的原像與偽碰撞攻擊

圖4 2輪biclique

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

4.2 對(duì)32輪SM3的原像與偽碰撞攻擊

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

圖5 3輪biclique

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

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

4.3 對(duì)33輪SM3的偽碰撞攻擊

5 結(jié)束語

本文發(fā)現(xiàn)要對(duì)SM3構(gòu)造原像攻擊是比較困難的，這是因?yàn)椋?) SM3采用了復(fù)雜的步函數(shù)；2) SM3的消息填充算法限制了線性空間1和2的取值范圍。不過相比于中間相遇攻擊，本文發(fā)現(xiàn)差分中間相遇攻擊更適合用來構(gòu)造對(duì)SM3的原像攻擊，這主要是由于SM3采用了線性化的消息擴(kuò)展算法。利用差分中間相遇、切割縫合技術(shù)與biclique方法，提出了對(duì)SM3的32輪原像攻擊，以及33輪的偽碰撞攻擊。在本文之前，對(duì)SM3最好的原像結(jié)果只有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-），男，福建福州人，博士，福州大學(xué)講師，主要研究方向?yàn)樯⒘泻瘮?shù)和分組密碼的分析。

董樂（1980-），男，河南新鄉(xiāng)人，博士，河南師范大學(xué)副教授，主要研究方向?yàn)樯⒘泻瘮?shù)和分組密碼的分析。

2017-03-09；

2017-11-13

福建省中青年教師教育科研基金資助項(xiàng)目（No.JAT170097）；福州大學(xué)科研啟動(dòng)基金資助項(xiàng)目（No.510150）

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