/ THE IDEA
A good cryptographic hash changes unpredictably when the input changes. Given only the hash, finding an input that produces it should require impractical work. Collision resistance means an attacker should also struggle to construct two different inputs with the same hash. The birthday effect makes collisions arrive sooner than simple intuition suggests: for a b-bit output, the rough collision scale is around 2 raised to b/2 random inputs, not 2 raised to b.
THE FORMAL IDEA
collision scale ≈ 2^(b/2)
| b = number of bits in the hash output | | the exponent b/2 comes from comparing every input with many others | | scale describes probability, not a guaranteed collision point |
|
RUN THE TINY EXAMPLE
Shrink the hash to eight bits
8 bits give only 2⁸ = 256 possible fingerprints Around 19 random inputs already give roughly even odds of a repeat 256-bit hashes push that birthday scale to about 2¹²⁸ attempts
|
Real secure hashes use huge output spaces so an inevitable mathematical fact becomes a physically impractical attack.
/ SO WHAT?
This explains why obsolete hash algorithms are retired and why shortening a digest reduces security. It also separates two questions: finding any colliding pair is easier than finding a second file matching one specific trusted file.
ONE CAVEAT |
| A fast general hash is not sufficient password storage. Password systems need a unique salt and a deliberately slow, memory-hard password hashing function so guesses remain expensive. |
KEEP THIS
Hash collisions must exist; cryptographic design makes finding a useful one take absurd amounts of work.
|
NEXT: The part of quantum mechanics that acts like waves
|