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