# Are there MD5 collisions for inputs of different length?

There are many examples of MD5 collisions (some of them can be found here Are there two known strings which have the same MD5 hash value?). But as far as I know two inputs should have the same length to have the same MD5 (or same hash in general). Is it correct? Is there any proof of that?

Or otherwise examples of inputs of different lengths with the same MD5?

• Those collisions exist, but I'm not sure if we know how to find them. Merkle-damgaard includes the message length in the last block, which prevents us from turning a simple chosen-prefix collision into a collision of different length messages. Oct 7, 2015 at 10:31
• Take $2^{128}+1$ messages of different size, then compute their MD5 ilage. You will have a collision, and colliding messages have different size. (When one needs to check such a property, one may find useful the Pigeonhole principle Oct 7, 2015 at 11:49
• @ddddavidee: MD5 has an input length constraint of max $2^{64}-1$ bits. You can't have $2^{128}+1$ unique MD5 inputs each with a unique length. Oct 7, 2015 at 12:34
• According to this tools.ietf.org/html/rfc1321, one can have a larger input. (cf. 3.2 Step 2. Append Length) Oct 7, 2015 at 12:41
• Much easier would, of course, be calculating them for messages of different lengths below one block. After $2^{64}$ such messages you'd expect to find collisions and each would likely be between two different sized messages, so you would only need to go a small factor over the birthday bound.
– otus
Oct 7, 2015 at 12:43

So the problem with different-size MD5 collisions is that our collision-finding tools aren't yet powerful enough to find them efficiently.

First we need to understand the rough idea of how MD5 works, using the Merkle–Damgård construction where essentially you keep some state $$s$$ and some current input block $$m$$, combine them with a compression-function and use the output as new state $$s$$, with the last state effectively being the output.

Now what our current techniques can achieve is that given (arbitrary) states $$s_1\neq s_2$$, they can find a sequence of message blocks $$(m_1,m_1',\ldots)$$ and $$(m_2,m_2',\ldots)$$ that when fed into the hash function will yield the updated states to be the same $$s_1'=s_2'$$ (this is called a "chosen-prefix collision attack").

The problem is, that after $$s_1',s_2'$$ the messages need to be equal (including length) to preserve the collision or you'll have to re-unite the states again if you feed different messages again. This is a problem because MD5 appends the length of the processed message to the message just before feeding of to the final compression function call. In particular that means that when you use different-length messages your last blocks will differ and as it is the last block you can't just feed message blocks to make up for this difference again.

In theory you could try to defy this problem by either finding a collision on the compression function that involves this little control on the last few bytes, but practically it appears nobody has done this (yet).

However, if you are looking for a brute-force collision, which would entail about $$2^{64}$$ expected work and $$2^{128}+1$$ worst-case work, you can just have a 128-bit counter $$\mathbb i$$ and continually hash $$\mathbb i$$ and $$\mathbb i\|\mathbb i$$, looking for hashes which appear in both sets. Any such entry, which is guaranteed to exist after $$\mathbb i$$ cycled through its whole range will be a different-length collision.

TLDR: No. As far as I know, MD5 collisions with messages of differing length have not been found. Finding such collision would certainly be feasible by brute force, and perhaps by adaptation of existing attacks.

When we take a random function with 128-bit outputs, hash $$2^{64}$$ inputs of one length, and $$2^{64}$$ inputs of another length, we expect a collision with probability $$>63\%$$. Under that plausible model for MD5, it's thus likely there is a collision between messages of 8 bytes and 9 bytes that we can find by hashing all 8-byte messages, and less than 1/256 of the 9-byte messages. We heuristically expect many collisions for larger messages.

But to my knowledge, there is no known much better method to generate two messages of different size with the same MD5 hash. And in practice we'd need a little more hashes to conserve memory and allow for parallelization, like $$2^{66}$$ hashes. That is feasible, but still sizable effort: with GPUs hashing at 40 GH/s, we are talking ≈100 GPU⋅year. And I don't know this effort was done.

We can't trivially adapt the existing attacks finding MD5 collisions at low cost. Problem is, MD5 uses the Merkle Damgård construction, in which the last hashed padded message block includes the message size and a padding, causing at least 2 bits at heavily constrained locations to differ for messages of different size, and constraining several other bits of these two last message blocks. For example if we try to find collision between 2-blocks messages, one message of length 123 bytes and 122 bytes, the last three 32-bit words of the padded messages must be

80xxxxxx 000003D8 00000000 (for the 123-byte message)
0080xxxx 000003D0 00000000 (for the 122-byte message)


That breaks any collision we might have in earlier blocks with high probability, unless taken into account by the very attack creating the collision. And as far as I know the necessary adaptation of the existing attacks has not been done. it's needed to live with ≈80 imposed bits, including at least 2 prescribed ones imposed to different values in the two blocks. That's non-trivial.

If we really wanted to search two such messages by brute force, we could use a generic method of collision search. In principle, we would define

$$\begin{array}{rl} F:\{0,1\}^{128}&\to\{0,1\}^{128}\\ x&\mapsto\begin{cases}\operatorname{MD5}(x)&\text{ if the last bit of }x\text{ is }0\\ \operatorname{MD5}(x\|\mathtt{0x42})&\text{ if the last bit of }x\text{ is }1\\ \end{cases}\end{array}$$

Now we take a random starting point, and iterate, until finding a collision, perhaps using Floyd's cycle finding. There's a 50% chance this collision is for inputs with differing last bit, which leads to two messages of different length (16 and 17 bytes) and the same hash.

With some adaptation, we can distribute the search among several machines or parallel GPU threads. See Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999 (free access).

The number of inputs for MD5 hashing are far greater than number of outputs. It takes input of any length and generates a hash as output of size 128 bits, that means that for all the string of bytes of any length they must map to the same 2 ^ 128 possible MD5 hashes.

This implies that 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.

• I don't think your argument that "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" is sound. For a counterexample, we could easily e.g. define an MD5* hash function that was the same as normal MD5, except that the last bit of the output is set to 0 if the input is less than 128 bits long, and to 1 if the input is 128 bits or longer. Jun 1, 2019 at 0:48
• More generally, we could consider a really awful hash function the just returned the bit length of its input modulo $2^{128}$. While such a silly hash would have lots of easily findable collisions, no two inputs of different length would collide as long as both were less than $2^{128}$ bits long. This counterexample shows that there's no general way to prove the existence of collisions between inputs of different (reasonable) length for an arbitrary hash function without making at least some assumptions about how the hash function works. Jun 1, 2019 at 1:01