A Fast Attack Algorithm on the MD5 Hash Function  

作　　者：王张宜 张焕国 覃中平 孟庆树 

机构地区：[1]School of Computer Science, Wuhan Univ., Wuhan 430072, China [2]School of Software, Huazhong Univ. of Science and Tech., Wuhan 430079

出　　处：《Journal of Shanghai Jiaotong university(Science)》2006年第2期140-145,151,共7页上海交通大学学报（英文版）

基　　金：NationalNaturalScienceFoundationofChina(Nos.90104005,60373087)andPh.D.Pro-gramsFoundationofMinistryofEducationofChina(No.20020486046)

摘　　要：The sufficient conditions for keeping desired differential path of MD5 was discussed. By analyzing the expanding of subtraction difference, differential characters of Boolean functions, and the differential characters of shift rotation, the sufficient conditions for keeping desired differential path could be obtained. From the differential characters of shift rotation, the lacked sufficient conditions were found. Then an algorithm that reduces the number of trials for finding collisions were presented. By restricting search space, search operation can be reduced to 2 34 for the first block and 2 30 for the second block. The whole attack on the MD5 can be accomplished within 20 hours using a PC with 1.6 G CPU.The sufficient conditions for keeping desired differential path of MD5 was discussed. By analyzing the expanding of subtraction difference, differential characters of Boolean functions, and the differential characters of shift rotation, the sufficient conditions for keeping desired differential path could be obtained. From the differential characters of shift rotation, the lacked sufficient conditions were found. Then an algorithm that reduces the number of trials for finding collisions were presented. By restricting search space, search operation can be reduced to 2^34 for the first block and 2^30 for the second block. The whole attack on the MD5 can be accomplished within 20 hours using a PC with 1.6 G CPU.

关 键 词：MD5 differential attacks COLLISION 

分 类 号：TN918.2[电子电信—通信与信息系统]