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.

  • 0
    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$.2011-12-28
  • 4
    See also: http://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x2011-12-29

1 Answers 1

10

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

  • 0
    If the probability is that high, shouldn't it be easy to find an example by searching or even random sampling?2011-12-29
  • 6
    .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.2011-12-29
  • 0
    @Lopsy, right, thanks for the explanation.2011-12-29