A New Herding Attack on Hash Functions with Strengthening Merkle-Damagard (MD) Construction

Chen  Shi-Wei; Jin  Chen-Hui

doi:10.3724/SP.J.1146.2009.01313

Volume 32 Issue 8

Sep. 2010

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2010 > 32(8): 1953-1955

Chen Shi-Wei, Jin Chen-Hui. A New Herding Attack on Hash Functions with Strengthening Merkle-Damagard (MD) Construction[J]. Journal of Electronics & Information Technology, 2010, 32(8): 1953-1955. doi: 10.3724/SP.J.1146.2009.01313

Citation:

Chen Shi-Wei, Jin Chen-Hui. A New Herding Attack on Hash Functions with Strengthening Merkle-Damagard (MD) Construction[J]. Journal of Electronics & Information Technology, 2010, 32(8): 1953-1955. doi: 10.3724/SP.J.1146.2009.01313

Citation:

PDF( 176 KB)

A New Herding Attack on Hash Functions with Strengthening Merkle-Damagard (MD) Construction

doi: 10.3724/SP.J.1146.2009.01313 cstr: 32379.14.SP.J.1146.2009.01313

Received Date: 2009-10-09
Rev Recd Date: 2010-02-09
Publish Date: 2010-08-19

Abstract

Abstract

This paper constructs a diamond structure multicollision with2k initial values and variant lengths, which is used to propose a new chosen target forced prefix preimage attack (herding attack) on hash functions with Strengthening Merkle-Damagard (SMD) construction to find a preimage with 2k+3 blocks. Since the number of the chaining values available in herding attack is increased, the computational complexity of herding attack is reduced toO(2n-k/3+2n/2+k+2) fromO(2n-2(k+1)+2n/2+k+5/2) for kn/4-1.05.
- Cryptography,
- Hash functions,
- SMD construction,
- Preimage attack,
- Herding attack,
- Multicollision

FullText(HTML)

References(1)

References

Wang X Y, Feng D G, and Lai X J, et al.. Collisions for hashfunctions MD4, MD5, HAVAL-128 and RIPEMD[EB/OL].Cryptology ePrint Archive, Report 2004/199, 2004.[2]Wang X Y and Yu H B. How to break MD5 and other hashfunctions [C][J].Eurocrypt 05, Berlin.2005, LNCS 3494:19-35[3]Yu S, Yusuke N, and Jun Y, et al.. How to construct sufficientcondition in searching collisions of MD5 [EB/OL].Cryptology ePrint Archive, Report 2006/074, 2006.[4]Xie T, Feng D G, and Liu F B. A new collision differential forMD5 with its full differential path[EB/OL]. CryptologyePrint Archive, Report 2008/230, 2008.[5]Chen S W and Jin C H. An improved collision attack on MD5algorithm[C]. Third SKLOIS Conference, Inscrypt 2007,Xining, China, August 31- September 5, 2007, Lecture Notesin Computer Science, 2007, Vol. 4990: 343-357.[6]陈士伟, 金晨辉. MD5 碰撞攻击的多重消息修改技术研究. 通信学报, 2009, 30(8): 89-95.Chen S W and Jin C H. Research on the multi-messagemodification techniques on MD5[J]. Journal onCommunications, 2009, 30(8): 89-95.[7]Joux A. Multicollisions in Iterated hash functions[C].CRYPTO 2004, Berlin: Springer- Verlag, 2004. LNCS: 3152,306-316.[8]Kelsey J and Schneier B. Second preimages on n-bit hashfunctions for much less than 2n work[C]. Eurocrypt 2005,Berlin: Springer-Verlag, 2005, LNCS 3494: 19-35.[9]Kelsey J and Kohno T. Herding hash functions and theNostradamus attacl[C]. Eurocrypt 2006, Berlin: Springer-Verlag, 2006, LNCS 4004: 183-200.

Relative Articles

Supplements(0)

Cited By

Proportional views