Birthday attack/birthday paradox

The birthday-paradox is a phenomenon from the theory of probabilities, where the statistical probabilities of two similar incidents are surprisingly very different.

Usually the following two scenarios are compared to make this evident:

  1. How many people does a host have to invite to his birthday party, that the probability is at least 50% that at least one guest has his birthday at the same day as the host?

  2. How many people must be at the birthday party that the probability is at least 50% that any two guests have birthday at the same day?

Answer: At least 253 people must be there, that the probability is higher than 50%, that the host is not the only birthday celebrant.

On the opposite there are only 23 guests necessary, that the probability is higher than 50%, that two of the guests have the same birthday (which date does not matter).

Because of the big difference between 253 guests in the first scenario and 23 guests in the second scenario, this is called a paradox.

Details how to get to these numbers can be found in Methoden und Werkzeuge für Angriffe auf die digitale Signatur, 2003 by Jan Blumenstein.

Transferring this example to the search for hash value collisions means:

If changes are allowed at both documents instead of keeping one document fixed, then one needs to calculate the hash values of a dramatically less number of changed documents to find 2 documents with the same hash value.

If the initial document isn't allowed to be changed and one uses a 128-bit hash function, then you need to calculate 2127 hash values of changed documents to achieve a probability of 50% to find another document with the same hash value (2127 ~ 1,7 * 1038).

The birthday attack allows you to break 128-bit hash functions after 264 calculations: The changes are made at both documents – analogous to the 2nd example above it doesn't matter, which hash value (birthday) is found. It is only important that they are equal (264 ~ 1,8 * 1019).

Because an effort of 264 calculations is possible using a big number of computers working in parallel, 128-bit hash functions are no more considered to be secure for strong cryptography.

You find further online help here: