Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$. –  Alex Becker Dec 28 '11 at 23:32
4  
See also: stackoverflow.com/questions/235785/… –  t.b. Dec 29 '11 at 0:02

1 Answer 1

up vote 8 down vote accepted

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.