Are there any known MD5 hash collisions of messages of different length?

Question

All the examples of MD5 hash collisions I've come across comprise two different messages (inputs) of the same length. The first and second messages have different values for a number of bits and the resulting MD5's are equal.

Does the theory of finding an MD5 hash collision (exploiting the weakness in the algorithm) prescribe that the lengths of the messages be the same? In other words would the theory be unusable to find a collision of two messages of different length? Has such a collision ever been found?

Answer 1

According to this article, the chosen prefix collision algorithm has been used to

produce two executable files with the same MD5 hash, but different behaviors. Unlike the old method, where the two files could only differ in a few carefully chosen bits, the chosen prefix method allows two completely arbitrary files to have the same MD5 hash, by appending a few thousand bytes at the end of each file.

While the sample files may be of the same length, the authors claim;

Our chosen-prefix collisions have only the requirement that after the collision the files should be exactly equal. Before the collision the two files, for which a collision is to be found, can be anything: our chosen-prefix collision finding method will always produce a collision that can be incorporated into the two files, irrespective of what data is present before the collision.

So yes, there are flaws in MD5 that can find collisions of different lengths.

Answer 2

Proving the existence of two different length plaintexts that collide using MD5 only requires you know that the number of inputs (and number of different lengths of inputs) are far greater than the number of possible outputs.

Given that MD5 can receive inputs of any length and can only output a hash of size 128 bits, that means that for all strings of bytes of any length they must map to the same 2 ^ 128 possible MD5 hashes.

For each input plaintext of length 128, there is guaranteed to be a collision with a plaintext that is of a size less than 128, because if MD5 was a perfect hashing algorithm it would hash each of those 128 bit length plaintexts (Hint: there's 2 ^ 128 of them, same number as possible outputs) to it's own unique hash, but that same set of output hashes must have been used for hashes of size 127 bits or less as well, so there must be a collision somewhere! Given this information we can prove mathematically the existence of two plaintexts of different lengths that have the same hash.