Collisions for the compression function of MD5

At Crypto’ 91 Ronald L. Rivest introduced the MD5 Message Digest Algorithm as a strengthened version of MD4, differing from it on six points. Four changes are due to the two existing attacks on the two round versions of MD4. The other two changes should additionally strengthen MD5. However both these changes cannot be described as well-considered. One of them results in an approximate relation between any four consecutive additive constants. The other allows to create collisions for the compression function of MD5. In this paper an algorithm is described that finds such collisions.A C program implementing the algorithm establishes a work load of finding about 216 collisions for the first two rounds of the MD5 compression function to find a collision for the entire four round function. On a 33MHz 80386 based PC the mean run time of this program is about 4 minutes.