The birthday attack is a statistical phenomenon relevant to information security that makes the brute forcing of one-way hashes easier. It’s based off of the birthday paradox, which states that in order for there to be a 50% chance that someone in a given room shares your birthday, you need 253 people in the room.

If, however, you are looking for a greater than 50% chance that any two people in the room have the same birthday, you only need 23 people.

This works because the matches are based on pairs. If I choose myself as one side of the pair, then I need a full 253 people to get to the magic number of 253 pairs. In other words, it’s me combined with 253 other people to make up all 253 sets.

But if I am only concerned with matches and not necessarily someone matching me, then we only need 23 people in the room. Why? Because it only takes 23 people to form 253 pairs when cross-matched with each other.

So the number 253 doesn’t change. That’s still the number of pairs required to reach a 50% chance of a birthday match within the room. The only question is whether each person is able to link with every other person. If so you only need 23 people; if not, and you’re comparing only to a single birthday, you need 253 people.

This applies to finding collisions in hashing algorithms because it’s much harder to find something that collides with a given hash than it is to find any two inputs that hash to the same value.

[ Updated: August 2008 ]