The birthday attack

The Birthday Attack

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

Reference:

https://danielmiessler.com/study/birthday_attack/