What is the MD5 collision with the smallest input values?

Question

I am interested in MD5 collisions for small input messages.

The collision examples given at http://www.mscs.dal.ca/~selinger/md5collision/ show two different strings, where only a tiny amount of data has been changed to give the same md5, but it feels more like just changing values that are not factored into the calculation. I've yet to come across an example where two seemingly random things reach the same value. I did try a small script to find out, but obviously it didn't get anywhere near far enough.

One formalisation of my question would be:

What is the minimal $b\in\mathbb N$ such that there exists $a\in[0,b)$ with $\mathbf{MD5}(a)=\mathbf{MD5}(b)$

Answer 1

To answer your question, we must first state that for an integer $x$, we define MD5($x$) to be the MD5 hash of the encoding of $x$ as a sequence of bits. Indeed, MD5 expects a sequence of bits as input, not an integer. We should choose a conventional encoding; I select big-endian. Thus, integer $44$ encodes as a sequence of 6 bits: 101100. One may note that by doing so, I miss on half of possible MD5 inputs: indeed, when converting an integer to its minimal-length big-endian unsigned encoding, the first bit is always a '1'.

Though the encoding is not important for the discussion below, it impacts the value of $b$ that you are looking for. Indeed, each encoding will yield another $b$.

---

Since MD5 has a $128$-bit output, it can have (at most) $2^{128}$ distinct outputs. If I take the integers $0$ to $2^{128}$ (inclusive), then I have $2^{128}+1$: it is thus mathematically guaranteed that at least two of them hash to the same value. In other words, it is proven that there exist integer values $a$ and $b$ such that $0 \leq a < b \leq 2^{128}$ and MD5($a$) = MD5($b$).

The actual minimal value of $b$ is not known. However, it is expected that the minimal $b$ is around $2^{64}$. This comes from the so-called birthday problem: if I take at random $n$ value within a set of size $N$, then I will pick one that I already picked previously when $n$ reached $\sqrt{N}$ or so.

To obtain $b$, one would have to, indeed, generate MD5($x$) for all values of $x$, beginning with $0$, until we get a value that we already had. The expected cost for the MD5 is high: $2^{64}$ is within reach of technology, but not of a home computer. On a quad-core x86, one may expect about $2^{26}$ MD5 evaluations per second; with a good GPU, you could reach $2^{33}$ per second (this guy claims a bit more than $2^{36}$, but that's with 8 GPU). You'd still need about 60 years to reach $2^{64}$. Another issue, which may become quite a problem in the long run, is how to detect that you did obtain twice the same hash output: $2^{64}$ 16-byte results will not fit in RAM... In fact, this search problem is likely to be a bigger issue than just computing all the MD5.

(There are nifty collision-search algorithms which need very little RAM, but I am not sure they could be applied to the exact problem you stated, in which you do not look for just a collision, but for the minimal $b$ value.)

Answer 2

For the smallest in theory based on a heuristic argument, see this other answer.

For two concrete examples with 512-bit messages, much more than minimum but half the size of the example linked to in the question

1. 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2
   and the (different by two bits)
   4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2
   both have MD5 hash
   008ee33a9d58b51cfeb425b0959121c9
2. 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef
   and the (different by two other bits)
   0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef
   both have MD5 hash
   cee9a457e790cf20d4bdaa6d69f01e41

Example 1. is straight from Marc Stevens: Single-block collision for MD5, 2012; he explains his method, with source code (alternate link to the paper).

Example 2. is adapted from Tao Xie and Dengguo Feng: Construct MD5 Collisions Using Just A Single Block Of Message, 2010.

---

The question asks for the smallest integer, but does not prescribe the mapping of integer to message, in particular endianness. In the above, I have used octet-strings, where every pair of hex characters encodes an octet in big-endian convention, which is customary; and each 4 consecutive octets forms a 32-bit word in little-endian convention, as is mandatory in MD5.

Given the definition of MD5, the most natural mapping of integer to message for MD5 seems to be in binary as a bit-string with little-endian convention. Sometime the padding allows to trim one bit: the second example has its high-order nibble (the but-last hexadecimal character) of e_(hex)=1110_(bin) which allows trimming to 110_(bin)=6_(hex), the padding will restore that; but in the first example, if we trimmed a_(hex)=1010_(bin) to 10_(bin), padding would change that to 0110_(bin)=6_(hex), and poof goes the collision.

Thus the current champion in the integer-as-little-endian-bitstring category is derived from the second example, which allows to build a 511-bit number with big-endian value
6fd18d5a8fd75920a4341f7d6d658673490786bbcd..556165300e and another smaller number
6fd18d5a8fd75920a4341f7d6d658673490786bbc5..556165300e having the same hash (but not the hash given above, because the second block of the padded message is changed).

Perhaps the crown can get back to the first example's family simply by running Marc Stevens's code and keeping the best value found.