The Automatic Search Of Differential Path In MD4

In 2005, Wang et al. successful attack MD4 with a very efficient method, which can find a collision with the complexity significant less than birthday attack.. Wang; s method is a kind of differential attack, but not a traditional XOR differential attack. Wang uses a so called 'module differential' tool, which contain more useful information. More, they attack other Hash functions, like MD5, RIPEMD, HAVAL, using this tool.But Wang et al.'s work is full of mysteries, that they haven't explained how they find the so called 'differential path'. Finding the differential path is a very important part for the differential attacking against MD4, and a lot of researchers have been very interested in the searching for differential path, due to its unpublished. Wang has been supposed that she find the differential path by hand.How to search a differential path is a hot topic. Some researchers focus on the computers, trying to find an automatic way for finding differential paths. Two reasons motivate the automatic search: first, it can find more potential paths in a shorter time, which may contain real worked paths; second, it may be used in researching other hush functions, for that the way is common.Recently a result has been published, but not a real automatic way. In this way, it need some work by hand more or less. This article summarized the Hash function MD4 and the attack against MD4. This article has two major contributions:1. Surveying the automatic searching method and realizing the algorithm by programming, which gives good results for researching this automatic way.2. Improved the automatic search. The new search algorithm can totally find differential path automatically.