collision attack for the hash function extended md4

ISCAS OpenIR

	collision attack for the hash function extended md4
	Wang Gaoli
	2011
会议名称	13th International Conference on Information and Communications Security, ICICS 2011
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
页码	228-241
会议日期	November 2
会议地点	Beijing, China
收录类别	EI
ISSN	0302-9743
ISBN	9783642252426
部门归属	(1) School of Computer Science and Technology Donghua University Shanghai 201620 China; (2) State Key Laboratory of Information Security Institute of Software Chinese Academy of Sciences Beijing 100049 China
摘要	Extended MD4 is a hash function proposed by Rivest in 1990 with a 256-bit hash value. The compression function consists of two different and independent parallel lines called Left Line and Right Line, and each line has 48 steps. The initial values of Left Line and Right Line are denoted by IV0 and IV1 respectively. Dobbertin proposed a collision attack for the compression function of Extended MD4 with a complexity of about 2⁴⁰ under the condition that the value for IV0 = IV1 is prescribed. In this paper, we gave a collision attack on the full Extended MD4 with a complexity of about 2³⁷. Firstly, we propose a collision differential path for both lines by choosing a proper message difference, and deduce a set of sufficient conditions that ensure the differential path hold. Then by using some precise message modification techniques to improve the success probability of the attack, we find two-block collisions of Extended MD4 with less than 2³⁷ computations. This work provides a new reference to the collision analysis of other hash functions such as RIPEMD-160 etc. which consist of two lines. © 2011 Springer-Verlag.; Extended MD4 is a hash function proposed by Rivest in 1990 with a 256-bit hash value. The compression function consists of two different and independent parallel lines called Left Line and Right Line, and each line has 48 steps. The initial values of Left Line and Right Line are denoted by IV0 and IV1 respectively. Dobbertin proposed a collision attack for the compression function of Extended MD4 with a complexity of about 2⁴⁰ under the condition that the value for IV0 = IV1 is prescribed. In this paper, we gave a collision attack on the full Extended MD4 with a complexity of about 2³⁷. Firstly, we propose a collision differential path for both lines by choosing a proper message difference, and deduce a set of sufficient conditions that ensure the differential path hold. Then by using some precise message modification techniques to improve the success probability of the attack, we find two-block collisions of Extended MD4 with less than 2³⁷ computations. This work provides a new reference to the collision analysis of other hash functions such as RIPEMD-160 etc. which consist of two lines. © 2011 Springer-Verlag.
关键词	Hash Functions
主办者	National Natural Science Foundation of China (NNSFC); The Microsoft Corporation; Beijing Tip Technology Corporation; Trusted Computing Group (TCG)
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/16222
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Wang Gaoli. collision attack for the hash function extended md4[C],2011:228-241.