Search tools and guides ⌘K

VI · Cryptographic foundations

Birthday attack

What it is

Finding any collision in an n-bit hash takes ~2^(n/2) operations, not 2^n.

Where it lives

Hash function security, why 128-bit MAC tags are the modern minimum.

The key insight

SHA-1 is 160 bits → 80 bits of resistance → broken in 2017. SHA-256 → 128 bits → safe past 2050.

More in Cryptographic foundations

One-way functions f(x) is easy to compute, f⁻¹(y) is computationally infeasible. The con… Discrete log Given g and gˣ mod p, find x. Believed hard for primes ~2048-bit; very… AEAD Authenticated Encryption with Associated Data. One operation provides …

Across the foundations

VII Approximation algorithms Computational complexity VII Reductions Computational complexity VIII Central Limit Theorem Statistics & inference VIII Hypothesis testing & p-values Statistics & inference VIII Confidence intervals Statistics & inference VIII Power & sample size Statistics & inference IX Eigenvalues & eigenvectors Linear algebra IX Singular Value Decomposition Linear algebra

← All foundations