6
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – CodesInChaos Oct 7 '15 at 10:31
  • 3
    $\begingroup$ 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 $\endgroup$ – ddddavidee Oct 7 '15 at 11:49
  • 2
    $\begingroup$ @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. $\endgroup$ – Henrick Hellström Oct 7 '15 at 12:34
  • 1
    $\begingroup$ According to this tools.ietf.org/html/rfc1321, one can have a larger input. (cf. 3.2 Step 2. Append Length) $\endgroup$ – ddddavidee Oct 7 '15 at 12:41
  • 1
    $\begingroup$ 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. $\endgroup$ – otus Oct 7 '15 at 12:43
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Jun 1 at 0:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Ilmari Karonen Jun 1 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.