hash - Is there an MD5 Fixed Point where md5(x) == x?

Question

Is there a fixed point in the MD5 transformation, i.e. does there exist x such that md5(x) == x?

Answer 1

Since an MD5 sum is 128 bits long, any fixed point would necessarily also have to be 128 bits long. Assuming that the MD5 sum of any string is uniformly distributed over all possible sums, then the probability that any given 128-bit string is a fixed point is ¹/_2¹²⁸.

Thus, the probability that no 128-bit string is a fixed point is (1 ? ¹/_2¹²⁸)²¹²⁸, so the probability that there is a fixed point is 1 ? (1 ? ¹/_2¹²⁸)²¹²⁸.

Since the limit as n goes to infinity of (1 ? ¹/_n)ⁿ is ¹/_e, and 2¹²⁸ is most certainly a very large number, this probability is almost exactly 1 ? ¹/_e ≈ 63.21%.

Of course, there is no randomness actually involved – either there is a fixed point or there isn't. But, we can be 63.21% confident that there is a fixed point. (Also, notice that this number does not depend on the size of the keyspace – if MD5 sums were 32 bits or 1024 bits, the answer would be the same, so long as it's larger than about 4 or 5 bits).