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