# str = md5( str ), String equals hash value of the string

Is there a way to prove that a 32-byte string exist (or not) for which the MD5 hash function result is equal to the string itself ?

str = md5( str )


Or can one say something about the probability of such a collision.

-
Not one that doesn't rely on specific properties of md5, I think. We can't used a simple fixed-point trick since in the 1-bit case we could have a function $f(0) = 1,f(1)=0$. –  Alex Becker Dec 28 '11 at 23:32

A str as you describe would be called a "fixed point", and it is certainly possible and even probable that one exists in MD5, but none is known.

Since md5 outputs 128-bits, we limit our domain to 128-bits for this discussion. Consider each point in this domain, and imagine that md5 is a random function (a reasonable heuristic assumption), then for a single point we have a $1/2^{128}$ chance that it is fixed. By linearity of expectation, we have that the expected number of fixed points in md5 is 1.

The probability of a fixed point is 1 minus the probability of none:

$$1 - \Big(\frac{2^{128}-1}{2^{128}}\Big)^{2^{128}} \approx 1 - 1/e \approx 0.632$$

-
If the probability is that high, shouldn't it be easy to find an example by searching or even random sampling? –  lhf Dec 29 '11 at 0:19
.632 is the probability that, of all 2^128 strings, at least one works; not the probability that any individual string works. If you search at random, it'll take quite a while to even scratch a dent into the space. –  Lopsy Dec 29 '11 at 0:32
@Lopsy, right, thanks for the explanation. –  lhf Dec 29 '11 at 1:17