摘要
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的碰撞攻击算法在消息修改时忽视了被修改条件之间的制约性,因而未必总能产生碰撞,本文对此进行了修正,给出新的充分条件集,并通过实验验证了该充分条件集总能产生碰撞。
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 twonew 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 Xuejia＇s 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.
出处
《电子与信息学报》
EI
CSCD
北大核心
2009年第3期740-744,共5页
Journal of Electronics & Information Technology
基金
河南省杰出青年科学基金(0312001800)资助课题
关键词
保密通信
MD5
碰撞攻击
充分条件集
冗余性
制约性
Secret communication
MD5
Collision attack
A set of sufficient conditions
Redundancy
Dependence
