- Unsupervised Learning
- Posts
- The Birthday Attack
The Birthday Attack
The birthday attack is a statistical phenomenon relevant to informationsecuritythat makes the brute forcing of one-wayhasheseasier. It’s based off of the birthday paradox, which states that inorder for there to be a 50% chance that someone in a given room sharesyour birthday, you need 253 people in the room.
If, however, you are looking for a greater than 50% chance that anytwo people in the room have the same birthday, you only need 23people.
This works because the matches are based on pairs. If I choose myself asone side of the pair, then I need a full 253 people to get to the magicnumber of 253 pairs. In other words, it’s me combined with 253 otherpeople to make up all 253 sets.
But if I am only concerned with matches and not necessarily someonematching me, then we only need 23 people in the room. Why? Because itonly takes 23 people to form 253 pairs when cross-matched with eachother.
So the number 253 doesn’t change. That’s still the number of pairsrequired to reach a 50% chance of a birthday match within the room. Theonly question is whether each person is able to link with every otherperson. If so you only need 23 people; if not, and you’re comparing onlyto a single birthday, you need 253 people.
This applies to finding collisions in hashing algorithms because it’smuch harder to find something that collides with a given hash thanit is to find any two inputs that hash to the same value.:
[ Updated: August 2008 ]