What is the MD5 collision with the smallest input values? 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)$
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 &lt; 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.)