产生MD5碰撞的新的充分条件集
doi: 10.3724/SP.J.1146.2007.01562
A New Set of Sufficient Conditions for MD5 Collisions
-
摘要: Wang Xiaoyun等(2005)给出了MD5能产生碰撞的一个充分条件集,并首次成功对MD5进行了碰撞攻击。Yuto Nakano等(2006)指出上述充分条件集中有16个条件是冗余的,并给出了其中14个条件冗余的原因。Liang Jie和Lai Xuejia(2005)指出Wang Xiaoyun等给出的充分条件集并非总能产生碰撞,并增加新的条件使之总能产生碰撞,同时提出了一个新的碰撞攻击算法。本文证明了Yuto Nakano等给出的16个冗余条件中有两个并不冗余,且Liang Jie和Lai Xuejia增加的新条件中有两个是冗余的,指出Liang Jie和Lai Xuejia的碰撞攻击算法在消息修改时忽视了被修改条件之间的制约性,因而未必总能产生碰撞,本文对此进行了修正,给出新的充分条件集,并通过实验验证了该充分条件集总能产生碰撞。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.
-
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.
点击查看大图
计量
- 文章访问数: 3188
- HTML全文浏览量: 77
- PDF下载量: 818
- 被引次数: 0