Collisions, birthday attacks and length extension

The birthday bound that makes collisions inevitable, chosen-prefix attacks on MD5 and SHA-1, why length extension works on Merkle-Damgard hashes, and the fixes that exist.

Collisions arrive sooner than intuition suggests

The birthday bound says a collision becomes likely after roughly the square root of the output space. For a 128-bit digest that is about 2 to the 64 operations — far less than the 2 to the 128 a naive reading suggests.

# how many values before a 50 percent collision chance?
import math

def birthday_bound(bits):
    return math.isqrt(2 ** bits) if bits % 2 == 0 else 2 ** ((bits + 1) // 2)

for bits in (64, 128, 160, 256):
    print(bits, f"~2^{birthday_bound(bits).bit_length() - 1}")

Collision and second-preimage attacks

• Collision — two different messages with the same digest. MD5 is trivially broken, SHA-1 is broken in practice.
• Chosen-prefix collision — an attacker picks two different documents that collide, which is enough to forge a certificate or a signed file.
• Second preimage — given a specific message, find another with the same digest. This is harder and SHA-1 is still resistant here.
• Length extension — given a digest and the length of the unknown input, compute a valid digest for the input plus appended data. It affects Merkle-Damgard hashes used as MACs.

# length extension in outline: SHA-256 is vulnerable if used as SHA256(secret || msg)
# an attacker who knows len(secret) and the digest can continue the state
def vulnerable_mac(key, msg):
    return hashlib.sha256(key + msg).hexdigest()     # never do this

# HMAC closes the hole because the key is used twice, outside the message path
def safe_mac(key, msg):
    return hmac.new(key, msg, hashlib.sha256).hexdigest()

# SHA-3 and BLAKE2 are not Merkle-Damgard, so extension does not apply
def modern_mac(key, msg):
    return hashlib.blake2b(msg, key=key[:64], digest_size=32).hexdigest()

What to do about it

1. Stop using MD5 for anything security-relevant, including signatures and integrity checks that an attacker could influence.
2. Treat SHA-1 as retired: migrate to SHA-256 or BLAKE3 in new code, and plan the migration for existing data.
3. Never build a MAC as a hash with a secret prefix or suffix; use HMAC or a keyed mode.
4. Sign the digest, not the raw message, and always verify the signature before trusting the content.
5. Choose 256-bit digests for anything long-lived; 128-bit is no longer comfortable against collision attacks.

# detect retired algorithms in a codebase
grep -rEn "\b(md5|sha1|SHA-1|MD5)\b" --include="*.py" --include="*.js" --include="*.java" .
grep -rn "has_algorithm\|use_algorithm" . | grep -i md5

FAQ

Related

HMAC and keyed hashing Digital signatures and certificates

Last refreshed 2026-09-18.