A fast attack on the MD4 hash function

Cryptographic hash functions are important cryptographic primitives and are used extensively in cryptographic applications. One such family of hash functions is the MD4 family. This family includes hash functions such as MD5, SHA-1 and RIPEMD-160. In 1995 an attack on the full compress function of MD4 was presented by Dobbertin. This paper builds on the work presented by Dobbertin. The attack of Dobbertin consists out of two components. The first component requires that a solution to a set of nonlinear equations be found. This paper presents an algorithm which reduces the number of trials required for finding a solution to these nonlinear equations. This algorithm is approximately 64 times faster than the technique proposed by Dobbertin. This implies a significant reduction in the effort required for finding collisions for MD4