A New Set of Sufficient Conditions for MD5 Collisions

Chen Shi-wei; Jin Chen-hui

doi:10.3724/SP.J.1146.2007.01562

Volume 31 Issue 3

Dec. 2010

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2009 > 31(3): 740-744

Chen Shi-wei, Jin Chen-hui. A New Set of Sufficient Conditions for MD5 Collisions[J]. Journal of Electronics & Information Technology, 2009, 31(3): 740-744. doi: 10.3724/SP.J.1146.2007.01562

Citation:

Chen Shi-wei, Jin Chen-hui. A New Set of Sufficient Conditions for MD5 Collisions[J]. Journal of Electronics & Information Technology, 2009, 31(3): 740-744. doi: 10.3724/SP.J.1146.2007.01562

Chen Shi-wei, Jin Chen-hui. A New Set of Sufficient Conditions for MD5 Collisions[J]. Journal of Electronics & Information Technology, 2009, 31(3): 740-744. doi: 10.3724/SP.J.1146.2007.01562

Citation:

Chen Shi-wei, Jin Chen-hui. A New Set of Sufficient Conditions for MD5 Collisions[J]. Journal of Electronics & Information Technology, 2009, 31(3): 740-744. doi: 10.3724/SP.J.1146.2007.01562

PDF( 199 KB)

A New Set of Sufficient Conditions for MD5 Collisions

doi: 10.3724/SP.J.1146.2007.01562

Received Date: 2007-09-26
Rev Recd Date: 2008-06-27
Publish Date: 2009-03-19

Abstract

Abstract

Wang et al. (2005) proposed a collision attack on MD5 and gave a set of sufficient conditions to yield a MD5 collision. Yuto Nakano et al. (2006) pointed out that there were 16 redundant conditions in Wang et al.s set of sufficient conditions and explained why 14 out of them were redundant. This paper will propose that two of them are not redundant actually and present two new redundant conditions in the set of sufficient conditions presented by Liang Jie and Lai Xuejia in 2005. Additionally, it will show that there is a mistake in Liang Jie and Lai Xuejias collision attack algorithm for the second-block message because they do not consider the dependence in the sufficient conditions, and correct the mistake. Finally, a new set of sufficient conditions is obtained and it could always yield a MD5 collision according to computer simulations.

FullText(HTML)

References(1)

References

Wang Xiaoyun, Feng Dengguo, and Lai Xuejia, et al..Collisions for hash functions MD4, MD5, HAVAL-128 andRIPEMD[EB/OL]. Cryptology ePrint Archive, Report2004/199, 2004.Hawkes, Paddon, and Rose G. Musings on the Wang et al.MD5 collision[EB/OL]. Cryptology ePrint Archive, Report2004/264, 2004.[2]Wang Xiaoyun and Yu Hongbo. How to break MD5 and otherhash functions [C][J].Eurocrypt 05, Berlin.2005, LNCS 3494:19-35[3]Yuto Nakano, Hidenori Kuwakado, and Masakatu Morii.Redundancy of the Wang-Yu sufficient conditions [EB/OL].Cryptology ePrint Archive, Report 2006/406, 2006.[4]Jun Yajima and Takeshi Shimoyama. Wangs sufficientconditions of MD5 are not sufficient [EB/OL]. CryptologyePrint Archive, Report 2005/263, 2005.Liang Jie and Lai Xuejia. Improved collision attack on hashfunction MD5 [EB/OL]. Cryptology ePrint Archive, Report2005/425, 2005.[5]Wang Zhangyi, Zhang Huanguo, and Qin Zhongping, et al.. Afast attack on the MD5 hash function [J]. Journal of ShanghaiJiaotong University, 2006, (2): 140-145.[6]Yu Sasaki, Yusuke Naito, and Jun Yajima, et al.. How toconstruct sufficient condition in searching collisions of MD5[EB/OL]. Cryptology ePrint Archive, Report 2006/074, 2006.[7]Klima. Finding MD5 collisions on a notebook PC usingmultimessage modifications [C]. International ScientificConference Security and Protection of Information, Brno,Czech Republic, May 2005: 53-62.[8]Black J, Cochran M, and Highland T. A study of the MD5attacks: Insights and improvements [C]. Fast SoftwareEncryption 2006, Berlin, 2006, LNCS 4047: 262-277.

Relative Articles

Supplements(0)

Cited By

Proportional views