Improved Meaningful Collision Attacks On MD4

The analysis of hash functions has made great progress.Recently,the collision attacks on hash functions have practical applications,such as the forgery of digital certificate,signatures and so on.MD4 was a widely used hash function.In 1996 Dobbertin proposed a meaningful collision case of MD4.The collision is based on the ASCII encoding and contains 16 random characters.In 2009,Jia and Wang presented a meaningful collision case of MD4 which contained 14 meaningless characters at the end of the text.This attack is based on Latin-1 encoding.Because MD4 is still being used in some areas that require higher computational efficiency,it is necessary to make a deep research on the meaningful collision attack of MD4.Based on Yu and Wang's differential path on MD4 published at CANS 2005,we present two meaningful collision instances for MD4 with eight random characters.One of which is a meaningful collision based on GBK encoding and the other is a meaningful collision based on UTF-8 encoding.Finally,we construct a collision of single-block executable Python script file instance.Our main contribution contains increasing the efficiency of constructing meaningful collisions of MD4,and reducing the number of random characters.Therefore,the collisions can express more semantics.Another advantage of our approach is the construction of a meaningful collision of MD4 is not limited by the encoding format.Moreover,we can use a random collision to a control command(such as the "If-Then-Else" command),then we can get two different documents that have the same hash value,such as certificate forgery,PS file Word,PDF etc..We can construct meaningful collision of MD4 in GBK,ASCII,UTF-8 and other encoding formats.In the process of constructing meaningful collisions,we propose a method to determine whether the sufficient conditions of the second round can be modified.Then,12 sufficient conditions can be filtered.Finally,we modified the following 7 conditions:a5,6=b4,6,a5,13=0,a5,18=b4,18,a5,29=b4,29,d5,6=0,d5,13=b4,13,c5,18=a5,18.The time complexity of constructing the meaningful collision of MD4 is within 231 MD4 operations.In order to further decrease the time of constructing collisions,we use random numbers and interrupt jumps in the programming phase.The experient shows that a meaningful collision can be obtained by using a single-core Pentium4 2.3GHZ CPU PC within one hour.Recently,the P2P protocol e D2 k is still using MD4 algorithm to check files.We upload executable python scripts to the e D2 k server to get two files sharing the same addresses.Therefore,we carry out a fake attack of e D2 k protocol.