How do I calculate the likelyhood of a collision using md5?

Question

I have keys that can vary in length between 1 and 256 characters*; how can I calculate the probability that any two keys will collide when using md5 (baring a brute force solution of trying each key)?

* the character set is restricted to [a-z.-]

Answer 1

Check out the birthday problem. It is exactly what you are looking for.

Answer 2

Take a look at the birthday paradox, which will help you analyse this. In short, since MD5 is a 128bit hash, you need 2⁶⁴ items before the probably of a collision rises to 50%. There's an assumption there that MD5 is distributed evenly over that 128bit space, which I would believe it doesn't do, but gets close.

If you want to get an idea of how those numbers rack up against your key space, let's assume all your keys are 256 chars, you have 26²⁵⁶ possible keys, or 2¹⁰²³, and of course you have a 100% chance of collision after 2¹²⁸ keys :)