对缩减轮数SM3散列函数改进的原像与伪碰撞攻击
2018-03-14邹剑董乐
邹剑，董乐
对缩减轮数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)
