# Does reducing 512-bit blocks to 128-bit hashes lead to 1/4 chance of collision?

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?

• The quote seems like bullshit to me, probably beacuse the author is no mathematician and has no trace of stochastic... – 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}$