对缩减轮数SM3散列函数改进的原像与伪碰撞攻击

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

通信学报 ›› 2018, Vol. 39 ›› Issue (1): 46-55.doi: 10.11959/j.issn.1000-436x.2018011

对缩减轮数SM3散列函数改进的原像与伪碰撞攻击

邹剑^1,²,董乐³

¹ 福州大学数学与计算机科学学院，福建福州 350108
² 福州大学网络系统信息安全重点实验室，福建福州 350108
³ 河南师范大学大数据统计分析与优化控制河南工程实验室，河南新乡 453007

修回日期:2017-11-13 出版日期:2018-01-01 发布日期:2018-02-07
作者简介:邹剑（1985-），男，福建福州人，博士，福州大学讲师，主要研究方向为散列函数和分组密码的分析。|董乐（1980-），男，河南新乡人，博士，河南师范大学副教授，主要研究方向为散列函数和分组密码的分析。
基金资助:
福建省中青年教师教育科研基金资助项目(JAT170097);福州大学科研启动基金资助项目(510150)

Improved preimage and pseudo-collision attacks on SM3 hash function

Jian ZOU^1,²,Le DONG³

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

Revised:2017-11-13 Online:2018-01-01 Published:2018-02-07
Supported by:
The Education and Research Projects for Young Teachers in Fujian Province(JAT170097);The Research Startup Project of Fuzhou University(510150)

摘要/Abstract

摘要：

提出了对SM3散列函数32轮的原像攻击和33轮的伪碰撞攻击。利用差分中间相遇攻击与biclique技术改进了对SM3的原像分析结果，将攻击结果从之前的30轮提高到了32轮。基于上述方法，通过扩展32轮原像攻击中的差分路径，对SM3构造了33轮的伪碰撞攻击。以2^254.5的时间复杂度与2⁵的空间复杂度构造了对SM3的32轮原像攻击，并以2^126.7的时间复杂度与2³的空间复杂度构造了对SM3的33轮伪碰撞攻击。

关键词: SM3散列函数, 原像攻击, 伪碰撞攻击, 差分中间相遇攻击, biclique

Abstract:

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 2^254.5,and a memory of 2⁵.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 2^126.7,and a memory of 2³.

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

中图分类号:

TP309

邹剑,董乐. 对缩减轮数SM3散列函数改进的原像与伪碰撞攻击[J]. 通信学报, 2018, 39(1): 46-55.

Jian ZOU,Le DONG. Improved preimage and pseudo-collision attacks on SM3 hash function[J]. Journal on Communications, 2018, 39(1): 46-55.

图/表 10

表1

图1

图2

图3

图4

表2

表3

图5

表4

表5

参考文献 11

[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.

攻击目标及轮数	攻击类型	时间复杂度	存储复杂度	文献
30轮SM3（从第7轮开始）	原像攻击	2 ²⁴⁹	2 ¹⁶	文献[7]
30轮SM3（从第1轮开始）	原像攻击	2 ^251.1	2⁶	文献[8]
31轮SM3（从第2轮开始）	原像攻击	2 ^252.4	2 ¹⁰	本文
32轮SM3（从第4轮开始）	原像攻击	2 ^254.5	2⁵	本文
20轮SM3（从第1轮开始）	碰撞攻击	实际可行	实际可行	文献[9]
24轮SM3（从第1轮开始）	伪碰撞攻击	实际可行	实际可行	文献[9]
32轮SM3（从第1轮开始）	伪碰撞攻击	2 ^125.1	2⁶	文献[8]
33轮SM3（从第3轮开始）	伪碰撞攻击	2 ^126.7	2³	本文

差分				步函数
差分	18	…	28	29	30	31	32
ΔW	0	…	0	0	0	0	0
ΔW '	0	…	0	Δ₁	0	0	?
ΔA	0	…	0	?	?	?	?
ΔB	0	…	0	0	?	?	?
ΔC	0	…	0	0	0	?	?
ΔD	0	…	0	0	0	0	?
ΔE	0	…	0	0	?	?	?
ΔF	0	…	0	0	0	?	?
ΔG	0	…	0	0	0	0	?
ΔH	0	…	0	0	0	0	0
概率	1	…	1	1	1	1	1

差分				步函数
差分	15	…	5		4	3	2
ΔW	0	…	0		Δ₂	0	0
ΔW '	0	…	0		Δ₂	0	0
ΔA	0	…	0		0	0	0
ΔB	0	…	0		0	0	Δ₄
ΔC	0	…	0		0	Δ₃	Δ₃
ΔD	0	…	0		Δ₃	Δ₃	Δ₄
ΔE	0	…	0		0	0	0
ΔF	0	…	0		0	0	Δ₅
ΔG	0	…	0		0	Δ₃	Δ₃
ΔH	0	…	0		Δ₃	Δ₃	Δ₆
概率	1	…	1		1	1	1?2^?2

差分				步函数
差分	21	…	31	32	33	34	35
ΔW	0	…	0	0	0	0	0
ΔW '	0	…	0	Δ₇	0	0	?
ΔA	0	…	0	?	?	?	?
ΔB	0	…	0	0	?	?	?
ΔC	0	…	0	0	0	?	?
ΔD	0	…	0	0	0	0	?
ΔE	0	…	0	0	?	?	?
ΔF	0	…	0	0	0	?	?
ΔG	0	…	0	0	0	0	?
ΔH	0	…	0	0	0	0	0
概率	1	…	1	1	1	1	1

差分				步函数
差分	17	…	7		6	5	4
ΔW	0	…	0		Δ₈	0	0
ΔW '	0	…	0		Δ₈	0	0
ΔA	0	…	0		0	0	0
ΔB	0	…	0		0	0	Δ₁₀
ΔC	0	…	0		0	Δ₉	Δ₉
ΔD	0	…	0		Δ₉	Δ₉	Δ₁₀
ΔE	0	…	0		0	0	0
ΔF	0	…	0		0	0	Δ₁₁
ΔG	0	…	0		0	Δ₉	Δ₉
ΔH	0	…	0		Δ₉	Δ₉	Δ₁₁
概率	1	…	1		1	1	1

对缩减轮数SM3散列函数改进的原像与伪碰撞攻击

Improved preimage and pseudo-collision attacks on SM3 hash function

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 11

相关文章 3

Metrics

推荐阅读 0

[1]	崔杰,左海风,仲红. 对轻量级分组密码I-PRESENT-80和I-PRESENT-128的biclique攻击[J]. 通信学报, 2017, 38(11): 13-23.
[2]	邹剑1,2，吴文玲1，吴双1，董乐1,2. 对缩减轮数DHA-256的原像与伪碰撞攻击[J]. 通信学报, 2013, 34(6): 2-15.
[3]	邹剑,吴文玲,吴双,董乐. 对缩减轮数DHA-256的原像与伪碰撞攻击[J]. 通信学报, 2013, 34(6): 8-15.