This is a quote from a cryptography book called Implementing SSL / TLS Using Cryptography and PKI By Joshua Davies.

MD5 operates on 512-bit(64 byte) blocks of input. Each block is reduced to a 128-bit(16 byte) hash. Obviously, with such a 4:1 ratio of input blocks to output blocks, there will be at least a one in four chance of a collision.

To view, the complete text with the context, please click this link.

I cannot understand how the author concludes that the probability of collision is 1/4. As far as I understand, the probability of collision would depend on the number of messages available.

If there are $2^{128} + 1$ messages or more, then the probability of collision is 1 due to pigeonhole principle. If we have only two messages, then the probability that they collide is only $1/2^{128}$. Then how does the quoted text "Obviously" make sense?

  • 1
    $\begingroup$ The quote seems like bullshit to me, probably beacuse the author is no mathematician and has no trace of stochastic... $\endgroup$ – AlexR Mar 14 '14 at 19:02

Probably the author meant that if there are $N$ messages, and the probability of a collision is $p$, with the reduction with $N$ messages the probability of a collision is $\frac{p}{4}$

Point is, as Steven Stadikni observe, this is not true.

So maybe the author is wrong (he may have overlooked the issue) but without reading the full article is not something I'm comfortable to affirm

  • 2
    $\begingroup$ Except that this isn't true. (Collision probability doesn't in any way, shape or form scale linearly with bit length - it's a function of the size of the sample space.) $\endgroup$ – Steven Stadnicki Mar 14 '14 at 18:59
  • $\begingroup$ @StevenStadnicki true! thank you :) $\endgroup$ – Ant Mar 14 '14 at 23:45
  • $\begingroup$ Please prove this part: "with the reduction with N messages the probability of a collision is p/4". Also, where do you see a reduction of N messages in the problem? If you want to read the full article, click this link. $\endgroup$ – user135464 Mar 15 '14 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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