A cryptographic attack on a one-way function (e.g, a
secure hash.) The attack is named after the statistical property of birthday duplication - you only need 23 people to have a larger than 50% chance that they are born on the same day of the year.
This is due to the fact that each time you adding one person to the set of people you are looking for duplicates in, you are looking for duplicates against all the people already in the set, not just one of them.
The same technique can be used to look for conflicts in one-way functions. Instead of taking one output of the one-way function, you create or aquire a set of values (let's call this a) that have a some property, and then create another set of other values that have different properties (let's call this b), and try to find any value that is in both a and b. This is a much smaller problem that finding a value that match a particular value in a.
The properties in a and b might for instance be
- ... a contains secure hashes of an innocent message and b contains one of a less innocent message, so the attacker can substitute the messages at a later date.
- ... a is the password hashes of a system the attacker wants to get an account on, and b is a set of password hashes that the attacker knows the passwords for.
- ... a is the set of public keys from a Discrete Logarithms based cryptosystem where g and p are static, while b is the set of g^e mod p functions that the attacker knows e for.
Resistance against this attack is why the Unix password hashes use a salt.