Fingerprints for Data

Hash functions and the birthday attack

An interactive lesson with 7 steps, about 6 minutes: you predict, drag and solve, with instant feedback on every answer. It runs in your browser and needs JavaScript.

What you’ll learn

• Hashes are short, fixed-length fingerprints of data.
• Collisions must exist (pigeonhole), but should be infeasible to find.
• The birthday attack finds collisions in about $\sqrt{N}$ tries, so hashes need long outputs.

Steps

1. A digital fingerprint
2. The avalanche
3. Collisions must exist
4. Salt
5. The birthday attack
6. Birthdays for hashes
7. Brute-forcing a collision