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

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

Journal on Communications ›› 2014, Vol. 35 ›› Issue (2): 40-45.doi: 10.3969/j.issn.1000-436x.2014.02.006

• academic paper • Previous Articles Next Articles

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

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

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.

Figures/Tables 2

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

Metrics

Recommended 0

No Suggested Reading articles found!

攻击类型	步数	是否填充	复杂度	起始步数	文献
原根攻击	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]	Manman LI, Shaozhen CHEN. Improved meet-in-the-middle attack on reduced-round Kiasu-BC algorithm [J]. Journal on Communications, 2022, 43(7): 41-48.
[2]	Xiaoyan ZHANG, Zhihao LIU, Xiaofeng DU, Tianbo LU. Research on a real-time receiving scheme of streaming data [J]. Journal on Communications, 2022, 43(4): 154-163.
[3]	Anqi YIN, Yuanbo GUO, Ding WANG, Tongzhou QU, Lin CHEN. Provably secure quantum resistance two-server password-authenticated key exchange protocol [J]. Journal on Communications, 2022, 43(3): 14-29.
[4]	Jian ZOU,Le DONG. Improved preimage and pseudo-collision attacks on SM3 hash function [J]. Journal on Communications, 2018, 39(1): 46-55.
[5]	Zhi-bo DU,Zhen WU,Min WANG,Jin-tao RAO. Power analysis attack of dynamic password token based on SM3 [J]. Journal on Communications, 2017, 38(3): 65-72.
[6]	Zhen WU,Min WANG,Jin-tao RAO,Zhi-bo DU,Sheng WANG,Ling-hao ZHANG. Mutual information power analysis attack of HMAC based on SM3 [J]. Journal on Communications, 2016, 37(Z1): 57-62.
[7]	Shi-Wei CHEN,INChen-Hui J. Trojan message attack on the concatenated hash functions [J]. Journal on Communications, 2016, 37(8): 45-50.
[8]	IRong-jia L,INChen-hui J. Meet-in-the-middle attacks on FOX block cipher [J]. Journal on Communications, 2016, 37(8): 185-190.
[9]	Zhi-bo DU,Zhen WU,Min WANG,Jin-tao RAO. Power analysis attack of HMAC based on SM3 [J]. Journal on Communications, 2016, 37(5): 38-43.
[10]	Jiong-jiong REN,Shao-zhen CHEN. Meet-in-the-middle attack on 11-round 3D cipher [J]. Journal on Communications, 2015, 36(8): 182-191.
[11]	Man-man LI,Shao-zhen CHEN. Improved meet-in-the-middle attack on ARIA cipher [J]. Journal on Communications, 2015, 36(3): 89-94.
[12]	Ping ZHANG,Yan-bing LIU,Jing YU,Jian-long TAN. HashTrie:a space-efficient multiple string matching algorithm [J]. Journal on Communications, 2015, 36(10): 172-180.
[13]	Ya-fei ZHENG,Hong-ru WEI. 3-subset meet-in-the-middle attack on block cipher TWIS [J]. Journal on Communications, 2014, 35(6): 180-184.
[14]	. 3-subset meet-in-the-middle attack on block cipher TWIS [J]. Journal on Communications, 2014, 35(6): 23-184.
[15]	. Preimage and pseudo-collision attacks on 29-step SM3 hash function with padding [J]. Journal on Communications, 2014, 35(2): 6-45.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 11

Related Articles 15

Metrics

Recommended 0