对缩减轮数DHA-256的原像与伪碰撞攻击

doi:10.3969/j.issn.1000-436X.2013.06.002

通信学报 ›› 2013, Vol. 34 ›› Issue (6): 8-15.doi: 10.3969/j.issn.1000-436X.2013.06.002

对缩减轮数DHA-256的原像与伪碰撞攻击

邹剑^1,²,吴文玲¹,吴双¹,董乐^1,²

¹ 中国科学院软件研究所可信计算与信息保障实验室，北京 100190
² 中国科学院研究生院，北京 100190

出版日期:2013-06-25 发布日期:2017-07-20
基金资助:
国家重点基础研究发展计划（“973”计划）基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目

Preimage and pseudo collision attacks on round-reduced DHA-256 hash function

Jian ZOU^1,²,Wen-ling WU¹,Shuang WU¹,Le DONG^1,²

¹ TCA,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China
² Graduate University,Chinese Academy of Sciences,Beijing 100190,China

Online:2013-06-25 Published:2017-07-20
Supported by:
The National Basic Research Program of China (973 Program);The National Natural Science Foundation of China;The National Natural Science Foundation of China

摘要/Abstract

摘要：

提出了对DHA-256散列函数37轮的原像攻击以及39轮的伪碰撞攻击。基于中间相遇攻击，利用Biclique方法可以改进之前对DHA-256的原像分析结果，将攻击轮数从原来的35轮提高到了37轮。通过上述方法还可以构造对DHA-256的39轮伪碰撞。最终，以2^255.5的时间复杂度以及2³的空间复杂度构造了对DHA-256的37轮原像，并以2^127.5的时间复杂度以及常数2的空间复杂度构造了对DHA-256的39轮伪碰撞。这是目前对DHA-256最好的原像与碰撞攻击结果。

关键词: DHA-256散列函数, 原像攻击, 伪碰撞攻击, 中间相遇攻击

Abstract:

A preimage attack on DHA-256 hash function reduced to 37-round and a pseudo collision attack on the func-tion reduced to 39-round were proposed respectively.Based on the meet-in-the-middle attack,the Biclique technique was used to improve the preimage attack from 35-round to 37-round.A 39-round pseudo collision was achieved using the Bi-clique technique.Overall,a preimage of DHA-256 was constructed with a complexity of 2^255.5and a memory of 2³.Besides,a pseudo collision of DHA-256 was proposed with a complexity of 2^127.5.These are the best results of preimage and collision attack on DHA-256 hash function.

Key words: DHA-256 hash function, preimage attack, pseudo collision attack, meet-in-the-middle

邹剑,吴文玲,吴双,董乐. 对缩减轮数DHA-256的原像与伪碰撞攻击[J]. 通信学报, 2013, 34(6): 8-15.

Jian ZOU,Wen-ling WU,Shuang WU,Le DONG. Preimage and pseudo collision attacks on round-reduced DHA-256 hash function[J]. Journal on Communications, 2013, 34(6): 8-15.

图/表 11

表1

图1

图2

图3

图4

表2

表3

图5

图6

表4

表5

参考文献 14

[1]	AOKI K , SASAKI Y . Preimage attacks on one-block MD4,63-step MD5 and more[A]. Workshop Records of SAC 2008[C]. Sackville,Canada, 2008. 82-98.
[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[A]. ASIACRYPT 2010 LNCS[C]. Singapore, 2010. 56-75.
[3]	AOKI K , SASAKI Y . Preimage attacks on 3,4,and 5-Pass HAVAL[A]. ASIACRYPT 2008 LNCS[C]. Melbourne,Australia, 2008. 253-271.
[4]	ISOBE T , SHIBUTANI K . Preimage attacks on reduced tiger and SHA-2[A]. FSE 2009 LNCS[C]. Leuven,Belgium, 2009. 139-155.
[5]	SASAKI Y , AOKI K . Preimage attacks on step-reduced MD5[A]. ACISP 2008 LNCS[C]. Wollongong,Australia, 2008. 282-296.
[6]	SASAKI Y , AOKI K . Preimage attacks on step-reduced MD5[A]. ACISP 2008 LNCS[C]. Wollongong,Australia, 2008. 282-296.
[7]	LI J , ISOBE T , SHIBUTANI K . Converting meet-in-the-middle preimage attack into pseudo collision attack: application to SHA-2[A]. ACISP 2008 LNCS[C]. Washington DC,USA, 2012. 264-286.
[8]	KHOVRATOVICH D , RECHBERGER C , SAVELIEVA A . Bicliques for preimages: attacks on skein-512 and the SHA-2 family[A]. FSE 2012 LNCS[C]. Washington DC,USA, 2012. 244-263.
[9]	LEE J , CHANG D , KIM H . A new 256-bit hash function DHA-256 enhancing the security of SHA-256[EB/OL].
[10]	IAIK krypto group: preliminary analysis of DHA-256[EB/OL].
[11]	ZHONG J M , LAI X J . Preimage attack on reduced DHA-256[J]. J Inf Sci Eng, 2011,27(4): 1315-1327.
[12]	ALFRED J , MENEZES P C V O , VANSTONE S A . Handbook of Applied Cryptography[M]. CRC Press, 2011.
[13]	DELESCAILLE J P , QUISQUATER J J . How easy is collision search?application to DES[A]. EUROCRYPT 1989 LNCS[C]. Houthalen,Belgium, 1990. 429-434.
[14]	SEDGEWICK R , SZYMANSKI T G , YAO A C . The complexity of finding cycles in periodic functions[J]. SIAM J Comput, 1982,11(2): 376-390.

攻击目标及轮数	攻击类型	时间复杂度	存储复杂度	来源
35轮DHA-256	第一原像	2^248.82	2¹⁶	文献[11]
37轮DHA-256	第一原像	2^255.5	2³	本文第5节
39轮DHA-256	伪碰撞	2^127.5	2	本文第6节

轮数	A	B	C	D	E	F	G	H	W
Z+4									a
Z+5				a				a
Z+6			a	θ			a	θ'
Z+7		a'	θ	λ		a ''	θ'	λ'
Z+8	a'				a ''

轮数	A	B	C	D	E	F	G	H	W
Z+4
Z+5				b'				b ''
Z+6			b'				b ''
Z+7		b				b
Z+8	b				b

R	A	B	C	D	E	F	G	H	W
3									31
4				31				31
5			31	γ			31	γ₁
6		16	γ	ω		1	γ₁	ω₁
7	16	a₁	ω	ω₂	1	γ₂	ω₁	ω₃
8	a₁	ω4	ω2	ω₆	γ₂	ω₅	ω₃	ω₇
9	ω₄				ω₅

对缩减轮数DHA-256的原像与伪碰撞攻击

Preimage and pseudo collision attacks on round-reduced DHA-256 hash function

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 14

相关文章 11

Metrics

推荐阅读 0

[1]	李曼曼, 陈少真. 改进的减轮Kiasu-BC算法的中间相遇攻击[J]. 通信学报, 2022, 43(7): 41-48.
[2]	邹剑,董乐. 对缩减轮数SM3散列函数改进的原像与伪碰撞攻击[J]. 通信学报, 2018, 39(1): 46-55.
[3]	李荣佳,金晨辉. FOX算法的中间相遇攻击[J]. 通信学报, 2016, 37(8): 185-190.
[4]	任炯炯,陈少真. 11轮3D密码算法的中间相遇攻击[J]. 通信学报, 2015, 36(8): 182-191.
[5]	李曼曼,陈少真. 对ARIA算法中间相遇攻击的改进[J]. 通信学报, 2015, 36(3): 89-94.
[6]	郑雅菲，卫宏儒. 分组密码TWIS的三子集中间相遇攻击[J]. 通信学报, 2014, 35(6): 23-184.
[7]	郑雅菲,卫宏儒. 分组密码TWIS的三子集中间相遇攻击[J]. 通信学报, 2014, 35(6): 180-184.
[8]	王高丽1,2，申延召1. 带消息填充的29步SM3算法原根和伪碰撞攻击[J]. 通信学报, 2014, 35(2): 6-45.
[9]	王高丽,申延召. 带消息填充的29步SM3算法原根和伪碰撞攻击[J]. 通信学报, 2014, 35(2): 40-45.
[10]	邹剑1,2，吴文玲1，吴双1，董乐1,2. 对缩减轮数DHA-256的原像与伪碰撞攻击[J]. 通信学报, 2013, 34(6): 2-15.
[11]	董晓丽,胡予濮,陈杰,李顺波,杨旸. 改进的7轮AES-192和8轮AES-256的中间相遇攻击[J]. 通信学报, 2010, 31(9A): 197-201.