Birthday & Collision Attacks

In a group of 23 people, the probability that two share a birthday exceeds 50%. With 70 people, it exceeds 99.9%. Mathematically: in a set of size N, collision probability exceeds 50% after ~√N samples. This is the birthday bound.

For an n-bit hash function: a collision (H(m1) = H(m2), m1 ≠ m2) can be found with ~2^{n/2} random trials. For SHA-256 (256-bit), collision requires ~2^{128} work — computationally infeasible. For MD5 (128-bit), ~2^{64} — borderline feasible.

Generic collision finding: generate 2^{n/2} random messages, compute hashes, sort by hash value, find duplicates. Memory O(2^{n/2}). Rho algorithm (Floyd's cycle finding) reduces memory to O(1) at same time cost. van Oorschot-Wiener parallel collision search reduces time with hardware.

MD5 practical collisions found by Wang et al. (2004) using differential cryptanalysis — not the birthday attack. Two different 1024-bit messages with identical MD5 hash in seconds. Hertzbleed/chosen-prefix collisions enable certificate collisions. MD5 is completely broken for collision resistance.

More powerful: given two arbitrary prefixes P1, P2, find suffixes S1, S2 such that H(P1||S1) = H(P2||S2). Stevens et al. (2017) found chosen-prefix MD5 collisions. Used to create a malicious CA certificate with a valid MD5 signature. Retired MD5 from certificate use.

Google's SHAttered (2017): first practical SHA-1 collision. Two different PDF files with the same SHA-1 hash. Required 2^{63.1} SHA-1 compressions — equivalent to 6,500 CPU years and 110 GPU years. Cost ~$110,000. Browsers deprecated SHA-1 certificates in 2017.

For Merkle-Damgard hash functions (MD5, SHA-1, SHA-2): if you know H(m), you can compute H(m||padding||m') without knowing m. This breaks MAC constructions like H(secret||message). Fix: use HMAC (which uses inner and outer padding) or SHA-3 (sponge construction, immune to length extension).

Collision resistance: find any two distinct messages with same hash (2^{n/2} effort). Second pre-image resistance: given m, find m' ≠ m with same hash (2^n effort). Pre-image resistance: find any message for a given hash (2^n effort). Collision is always weakest.

If MAC uses a collision-vulnerable hash: an attacker who can find collisions in H may forge MACs. HMAC-MD5 is considered safe despite MD5 collisions because HMAC's construction requires pre-image attacks, not just collisions. But migrate away from HMAC-MD5 for new systems.

Joux (2004): for Merkle-Damgard hashes, finding 2^k-way collisions (2^k messages with same hash) requires only k times the work of finding a single collision, not k times. This compounds vulnerabilities in concatenated hashes (H1(m)||H2(m) is not as strong as you'd think).

Use SHA-256 or SHA-3 for collision-resistant hashing. Avoid MD5 and SHA-1 for any security purpose. For MACs: HMAC-SHA-256 or HMAC-SHA-3. For password hashing: Argon2 (not SHA-2 directly). Always use SHA-3 when length-extension resistance is required.

Approximately how many hash evaluations are needed to find a collision in an n-bit hash function?

Birthday attack finds hash collisions in 2^{n/2} work. MD5 has practical chosen-prefix collisions; SHA-1 was broken in 2017. Length extension attacks break naive H(key||msg) MACs. Use SHA-256 or SHA-3; use HMAC for message authentication. Next: meet-in-the-middle attacks.