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.

  • 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
    @Lopsy, right, thanks for the explanation.2011-12-29