摘要
通过分析MD5中非线性函数的性质以及模232减差分和异或差分的性质,证明了Liang Jie和Lai Xuejia给出的产生MD5碰撞的充分条件集中的条件是保证第23～62步的差分路径满足的充要条件,给出了保证第63、64步的输出差分满足的充要条件集.利用得到的充要条件集,提出了对MD5的改进的碰撞攻击算法,该算法的平均计算复杂度约为已有碰撞攻击算法的0.7187倍,并通过实验对该算法的改进效果进行了验证.
By analyzing the properties of the nonlinear functions used in MD5 and the differences in terms of XOR and subtraction modulo 2^32, this paper proves that some sufficient conditions presented by Liang Jie and Lai Xuejia are also necessary to guarantee the differential path from the 23rd step to the 62nd step and give a set of necessary and sufficient conditions to guarantee the output differences of the last two steps. Then, according to the set of necessary and sufficient conditions this paper presents an improved collision attack algorithm on MDS. Finally, it analyzes the average computational complexity of the attack algorithm which is 0.718 7 times of that of the previous collision attack algorithms and proves the efficiency of the improved algorithm by computer simulations.
出处
《软件学报》
EI
CSCD
北大核心
2009年第6期1617-1624,共8页
Journal of Software
基金
河南省杰出青年科学基金No.0312001800~~
关键词
MD5
充要条件集
碰撞攻击
差分路径
MD5
a set of necessary and sufficient conditions
collision attack
differential path
