3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Alex Becker Dec 28 '11 at 23:32
  • 4
    $\begingroup$ See also: stackoverflow.com/questions/235785/… $\endgroup$ – t.b. Dec 29 '11 at 0:02
10
$\begingroup$

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 $$

$\endgroup$
  • $\begingroup$ If the probability is that high, shouldn't it be easy to find an example by searching or even random sampling? $\endgroup$ – lhf Dec 29 '11 at 0:19
  • 6
    $\begingroup$ .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. $\endgroup$ – Lopsy Dec 29 '11 at 0:32
  • $\begingroup$ @Lopsy, right, thanks for the explanation. $\endgroup$ – lhf Dec 29 '11 at 1:17

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.