Gulfstream: 7 March 2004

Project to find two strings with the same MD5 hash, I think. This is quite irresponsibly described, because they give the impression that internet commerce is doomed if a collision is found; it’s not. (About cryptographic hash functions: a hash function has the form y = f(x). That is, the function is given some number (x) as input (or file; files can be considered to be one big long number), and it returns some other number (y) as output. In the case of the MD5 hash function, the number returned is always 128 bits (about 30 digits) long. Cryptographic hash functions are supposed to have the feature that given y, you can’t figure out what x might have been. (Compare to y = f(x) = x + 1; with this function you can easily determine x if given y.) Because the number returned is 30 digits, and there’s very many more numbers more than 30 digits long, the MD5 hash function must produce collisions. This project is effectively trying to find two numbers that have the same hash value, which is not the same as being able to efficiently find x given y.)