Set of Necessary and Sufficient Conditions in Collision Attacks on MD5
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [17]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    By analyzing the properties of the nonlinear functions used in MD5 and the differences in terms of XOR and subtraction modulo 232, 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 MD5. 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.

    Reference
    [1] den Boer B, Bosselaers A. Collisions for the compression function of MD5. In: Proc. of the Advances in Cryptology, Eurocrypt 1993. Springer-Verlag, 1994.
    [2] Dobbertin H. Cryptanalysis of MD5 compress. In: Proc. of the Presented at the Rump Session of Eurocrypt 1996. 1996.
    [3] Wang XY, Feng DG, Lai XJ, Yu HB. Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD. Report, 2004/199, Cryptology ePrint Archive, 2004.
    [4] Hawkes P, Paddon M, Rose GG. Musings on the Wang et al. MD5 collision. Report, 2004/264, Cryptology ePrint Archive, 2004.
    [5] Wang XY, Yu HB. How to break MD5 and other hash functions. In: Proc. of the Eurocrypt 2005. LNCS 3494, Berlin: Springer-Verlag, 2005. 19-35.
    [6] Yajima J, Shimoyama T. Wang's sufficient conditions of MD5 are not sufficient. Report, 2005/263, Cryptology ePrint Archive, 2005.
    [7] Nakano Y, Kuwakado H, Morii M. Redundancy of the Wang-Yu sufficient conditions. Report, 2006/406, Cryptology ePrint Archive, 2006.
    [8] Sasaki Y, Naito Y, Yajima J, Shimoyama T, Kunihiro N, Ohta K. How to construct sufficient condition in searching collisions of MD5. Report, 2006/074, Cryptology ePrint Archive, 2006.
    [9] Liang J, Lai XJ. Improved collision attack on hash function MD5. Report, 2005/425, Cryptology ePrint Archive, 2005.
    [10] Wang ZY, Zhang HG, Qin ZP, Meng QS. A fast attack on the MD5 hash function. Journal of Shanghai Jiaotong University, 2006, E-11(2):140-145.
    [11] Stevens M. Fast collision attack on MD5. Report, 2006/104, Cryptology ePrint Archive, 2006.
    [12] Klima V. Finding MD5 collisions on a notebook PC using multi-message modifications. Report, 2005/102, Cryptology ePrint Archive, 2005.
    [13] Sasaki Y, Naito Y, Kunihiro N, Ohta K. Improved collision attack on MD5. Report, 2005/400, Cryptology ePrint Archive, 2005.
    [14] Klima V. Tunnels in hash functions: MD5 collisions within a minute. Report, 2006/105, Cryptology ePrint Archive, 2006.
    [15] Gregory H. Further musings on the Wang et al. MD5 collision: Improvements and corrections on the work of Hawkes, Paddon, and Rose. Report, 2007/375, Cryptology ePrint Archive, 2007.
    [16] Cui GH, Zhou RH, Su L. Research on the analysis of the MD5 resistibility. Computer Engineering and Science, 2007,29(1):45-48 (in Chinese with English abstract). 附中文参考文献:
    [16] 崔国华,周荣华,粟栗.关于MD5强度分析的研究.计算机工程与科学,2007,29(1):45-48.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

陈士伟,金晨辉. MD5碰撞攻击中的充要条件集.软件学报,2009,20(6):1617-1624

Copy
Share
Article Metrics
  • Abstract:5340
  • PDF: 7208
  • HTML: 0
  • Cited by: 0
History
  • Received:October 24,2007
  • Revised:April 02,2008
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063