带消息填充的29步SM3算法原根和伪碰撞攻击

doi:10.3969/j.issn.1000-436x.2014.02.006

通信学报 ›› 2014, Vol. 35 ›› Issue (2): 40-45.doi: 10.3969/j.issn.1000-436x.2014.02.006

带消息填充的29步SM3算法原根和伪碰撞攻击

王高丽,申延召

¹ 东华大学计算机科学与技术学院，上海 201620;
² 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093

出版日期:2014-02-25 发布日期:2017-07-25
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;中央高校基本科研业务费专项基金资助项目;中国科学院信息工程研究所信息安全国家重点实验室开放课题基金资助项目

Preimage and pseudo-collision attacks on 29-step SM3 hash function with padding

Gao-li WANG,Yan-zhao SHEN

¹ School of Computer Science and Technology, Donghua University, Shanghai 201620, China;
² State Key Laboratory of Information Security , Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Online:2014-02-25 Published:2017-07-25
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Fundamental Research Funds for the Central Universities;The Opening Project of State Key Laboratory of Information Security of Institute of Information Engineer-ing of Chinese Academy of Sciences

摘要/Abstract

摘要：

基于中间相遇攻击技术，提出了一种针对密码杂凑函数SM算法的原根攻击和伪碰撞攻击方法，给出了从第1步开始的带消息填充的29步SM3算法的原根攻击和伪碰撞攻击。结果表明：对于29步SM3算法的原根攻击的时间复杂度为2²⁵⁴；对于29步SM3伪碰撞攻击的时间复杂度为2¹²⁵。说明从第1步开始的带消息填充的29步SM3算法不能抵抗原根攻击和伪碰撞攻击。

关键词: 杂凑函数, 原根攻击, 碰撞攻击, 中间相遇攻击, SM3

Abstract:

The security of SM3 hash function was revaluated by using the meet-in-the-middle attack. The preimage and pseudo-collision attack on 29-step SM3 hash function (from the 1-st step) with padding was presented. The time complexities are 2²⁵⁴and 2¹²⁵respectively. Therefore, the 29-step SM3 hash function is not immune to preimage and pseudo-collision attack.

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

王高丽,申延召. 带消息填充的29步SM3算法原根和伪碰撞攻击[J]. 通信学报, 2014, 35(2): 40-45.

Gao-li WANG,Yan-zhao SHEN. Preimage and pseudo-collision attacks on 29-step SM3 hash function with padding[J]. Journal on Communications, 2014, 35(2): 40-45.

图/表 2

参考文献 11

[1]	WANG X , YU H . How to break MD5 and other hash functions[A]. EUROCRYPT 2005[C]. Aarhus, Denmark, 2005. 19-35.
[2]	WANG X , YIN Y , YU H . Finding collisions in the full SHA-1[A]. CRYPTO 2005[C]. Santa Barbara, California, USA, 2005. 17-36.
[3]	DIFFIE W , HELLMAN M . Exhaustive cryptanalysis of the NBS data encryption standard[J]. Computer, 1977,10(6): 74-84.
[4]	AOKI K , SASAKI Y . Preimage attacks on one-block MD4, 63-step MD5 and more[A]. SAC 2008[C]. New Brunswick, Canada 2008. 103-119.
[5]	National Institute of Standards and Technology Announcing request for candidate algorithm nominations for a new cryptographic hash al-gorithm (SHA-3) family[EB/OL]. , 2008.
[6]	SM3 hash function[EB/OL]. , 2010.
[7]	ZOU J , WU W , WU S et al. Preimage attacks on step-reduced SM3 hash function[A]. ICISC 2011[C]. Seoul Korea 2011. 375-390.
[8]	KIRCANSKI A , SHEN Y , WANG G et al. Boomerang and sliderotational analysis of SM3 hash function[A]. SAC 2012[C]. Windsor, Canada 2012. 305-321.
[9]	WANG G , SHEN Y . Preimage and pseudo-collision attacks on stepreduced SM3 hash function[EB/OL]. , 2012.
[10]	MENEZES A J , OORSCHOT P C , VANSTONE S . Handbook of Applied Cryptography[M]. CRC Press, 1996.
[11]	LI J , ISOBE T , SHIBUTANI K . SHIBUTANI K. Converting meetin-the-middle preimage attack into pseudo collision attack: application to SHA-2[A]. FSE 2012[C]. Washington DC, USA, 2012. 264-286.

攻击类型	步数	是否填充	复杂度	起始步数	文献
原根攻击	28	是	2^241.5	1	[7]
	30	是	2²⁴⁹	7	[7]
	29	否	2²⁴⁵	1	[9]
	30	否	2^251.1	1	[9]
	29	是	2²⁵⁴	1	本文
伪碰撞攻击	29	否	2¹²²	1	[9]
	30	否	2^125.1	1	[9]
	31	否	2¹²²	1	[9]
	32	否	2^125.1	1	[9]
	29	是	2¹²⁵	1	本文
飞来去器攻击	32	否	2^14.4	1	[8]
	33	否	2^32.4	1	[8]
	34	否	2^53.1	1	[8]
	35	否	2^117.1	1	[8]

[1]	李曼曼, 陈少真. 改进的减轮Kiasu-BC算法的中间相遇攻击[J]. 通信学报, 2022, 43(7): 41-48.
[2]	邹剑,董乐. 对缩减轮数SM3散列函数改进的原像与伪碰撞攻击[J]. 通信学报, 2018, 39(1): 46-55.
[3]	杜之波,吴震,王敏,饶金涛. 基于SM3的动态令牌的能量分析攻击方法[J]. 通信学报, 2017, 38(3): 65-72.
[4]	吴震,王敏,饶金涛,杜之波,王胜,张凌浩. 针对基于SM3的HMAC的互信息能量分析攻击[J]. 通信学报, 2016, 37(Z1): 57-62.
[5]	陈士伟,金晨辉. 对联接杂凑函数的“特洛伊”消息攻击[J]. 通信学报, 2016, 37(8): 45-50.
[6]	李荣佳,金晨辉. FOX算法的中间相遇攻击[J]. 通信学报, 2016, 37(8): 185-190.
[7]	杜之波,吴震,王敏,饶金涛. 针对基于SM3的HMAC的能量分析攻击方法[J]. 通信学报, 2016, 37(5): 38-43.
[8]	任炯炯,陈少真. 11轮3D密码算法的中间相遇攻击[J]. 通信学报, 2015, 36(8): 182-191.
[9]	李曼曼,陈少真. 对ARIA算法中间相遇攻击的改进[J]. 通信学报, 2015, 36(3): 89-94.
[10]	郑雅菲,卫宏儒. 分组密码TWIS的三子集中间相遇攻击[J]. 通信学报, 2014, 35(6): 180-184.
[11]	郑雅菲，卫宏儒. 分组密码TWIS的三子集中间相遇攻击[J]. 通信学报, 2014, 35(6): 23-184.
[12]	王高丽1,2，申延召1. 带消息填充的29步SM3算法原根和伪碰撞攻击[J]. 通信学报, 2014, 35(2): 6-45.
[13]	邹剑1,2，吴文玲1，吴双1，董乐1,2. 对缩减轮数DHA-256的原像与伪碰撞攻击[J]. 通信学报, 2013, 34(6): 2-15.
[14]	邹剑,吴文玲,吴双,董乐. 对缩减轮数DHA-256的原像与伪碰撞攻击[J]. 通信学报, 2013, 34(6): 8-15.
[15]	董晓丽,胡予濮,陈杰,李顺波,杨旸. 改进的7轮AES-192和8轮AES-256的中间相遇攻击[J]. 通信学报, 2010, 31(9A): 197-201.

带消息填充的29步SM3算法原根和伪碰撞攻击

Preimage and pseudo-collision attacks on 29-step SM3 hash function with padding

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 11

相关文章 15

Metrics

推荐阅读 0