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