Cryptographic Attacks

Executive Summary

A birthday attack exploits the mathematical probability that two different inputs to a hash function will produce an identical output — a hash collision. The name derives from the birthday paradox: in a classroom of only 23 students, there is approximately a 50% probability that two students share a birthday. The counterintuitive result arises because the question is not whether any student matches a specific birthday, but whether any two students match each other — a far more likely event. In cryptography, the same probabilistic principle applies to hash functions: it is significantly easier to find any two inputs that collide than to find an input that collides with a specific target hash. This advisory explains the birthday attack mechanism, documents the MD5 algorithm's demonstrated collision vulnerability, and specifies the defense: hash output size.

The Birthday Paradox — Probability Foundation

The key insight is that finding a collision between any two inputs requires far fewer attempts than finding an input that matches a specific target. For a hash with N possible output values, a brute-force collision search requires approximately √N attempts — not N. A 128-bit hash (like MD5) has 2¹²⁸ possible output values, but a birthday attack needs only approximately 2⁶⁴ attempts to find a collision. That is still an enormous number, but it is the square root of the full space — and practical collision attacks against MD5 require far fewer than even 2⁶⁴ attempts due to the algorithm's structural weaknesses.

Hash Collision Defined

A hash collision occurs when two different plaintext inputs produce the exact same hash digest output:

Hash functions are designed to make this computationally infeasible — two different inputs should, with overwhelming probability, produce two entirely different digests. When a collision is found, the hash function's collision resistance property has failed. The security consequence depends on what the hash is being used to verify: for digital signatures, a collision allows an attacker to create a fraudulent document that produces the same signature as a legitimate one.

MD5 — Documented Collision Vulnerability

Recommended Mitigations

• Use hash algorithms with large output sizes: The primary defense against birthday attacks is a sufficiently large hash output. A larger output space increases the number of attempts required to find a collision. SHA-256 (256-bit output) and SHA-3 (configurable output, minimum 224-bit) provide collision resistance adequate for current security requirements. SHA-512 is appropriate for highest-sensitivity applications.
• Retire MD5 and SHA-1 from all security-critical contexts: MD5 and SHA-1 have demonstrated practical collision vulnerabilities and must not be used for digital signatures, certificate issuance validation, or any context where collision resistance is required. Their use in legacy systems should be treated as a critical finding in security assessments.
• Distinguish use cases: MD5 and SHA-1 remain acceptable for non-security integrity verification where both parties are trusted — confirming a file download matches its published checksum, for example. The risk is specifically in security-critical contexts where an attacker could exploit a collision: digital signatures, certificate validation, and password storage.

Incident Overview

In December 2008, a team of researchers from CWI Amsterdam, EPFL, and other institutions demonstrated the most consequential practical exploitation of MD5 hash collisions to date: they created a fraudulent X.509 Certificate Authority certificate that appeared — when verified by the MD5 signature check — to have been legitimately signed by RapidSSL, a trusted commercial Certificate Authority. In reality, RapidSSL had never signed the fraudulent certificate. The certificate had been constructed using MD5 collision techniques to match the hash that RapidSSL did sign on a different, legitimate certificate request.

The attack's significance extends beyond MD5: it demonstrated that a theoretical mathematical weakness in a hash algorithm could be weaponized against the entire public key infrastructure that web browsers use to establish trust in HTTPS connections. A fraudulent CA certificate can issue certificates for any domain — including banking sites, government portals, and any HTTPS site in existence — that would be trusted by all browsers that trusted RapidSSL.

Technical Analysis — How the Forgery Worked

A Certificate Authority signs a certificate by computing a hash of the certificate's content and then encrypting that hash with the CA's private key. Browsers verify a certificate by decrypting this signature with the CA's public key (which is bundled in the browser's trusted root store) and comparing the result against a freshly computed hash of the certificate content. If they match, the certificate is considered valid and CA-signed.

The researchers exploited MD5's collision vulnerability to engineer two different certificate requests that produced the same MD5 hash. They submitted the legitimate-looking certificate request to RapidSSL for signing — a standard domain certificate that RapidSSL would approve. RapidSSL computed the MD5 hash of this certificate and signed it with their private key. The researchers then substituted their fraudulent CA certificate — which had a different content (claiming CA authority over any domain) but the same MD5 hash — into the signature. Because the MD5 hash matched, the RapidSSL signature validated against the fraudulent certificate. Browsers presented it as CA-signed.

The researchers had effectively forged the CA's signature on a document the CA never saw, by exploiting the hash algorithm's collision property.

Why This Was Catastrophic for PKI Trust

Industry Response

The demonstration triggered immediate action across the industry. Certificate Authorities rapidly migrated from MD5 to SHA-1 and SHA-256 for certificate signing. Browser vendors updated their trust stores and CA/Browser Forum policies were strengthened to require SHA-256 as the minimum for certificate signing. The incident permanently retired MD5 from any PKI context and accelerated the deprecation of SHA-1 (which was itself deprecated by 2017 following the SHAttered collision demonstration).

Recommended Mitigations

• SHA-256 minimum for all certificate signing: No X.509 certificate — end-entity or CA — should be signed using MD5 or SHA-1. Audit all certificates in use; replace any still signed with MD5 or SHA-1 as an emergency action. Modern CAs issue SHA-256 by default; no configuration action is required for new certificates from current providers.
• Certificate Transparency (CT) monitoring: The CA/Browser Forum's Certificate Transparency requirement mandates that all publicly-trusted certificates be logged in public append-only CT logs. Monitoring CT logs for unexpected certificates issued for your domains provides early warning of fraudulent certificate issuance — whether through hash collisions or compromised CAs.
• Certificate pinning for high-value services: HPKP (now deprecated) and its successors limit which certificates a browser will accept for a specific domain, independent of which CA signed them. Internal services can use custom trust stores that exclude CAs not relevant to their deployment.

Executive Summary

A downgrade attack does not break an encryption algorithm — it prevents strong encryption from being used in the first place. By interfering with protocol negotiation, an on-path attacker forces two communicating parties to use a weaker protocol version than either would choose voluntarily. Once on a weaker protocol, the attacker can either read traffic directly (if the downgrade achieved unencrypted HTTP) or exploit known vulnerabilities in the weaker protocol (as with SSL 3.0 in the POODLE attack). This advisory covers two downgrade attack variants: SSL stripping, which forces HTTP instead of HTTPS, and POODLE (2014), which forced TLS clients to fall back to SSL 3.0.

SSL Stripping — Step-by-Step Protocol Downgrade

SSL stripping is an on-path attack that intercepts the protocol negotiation phase of an HTTPS connection. It exploits the common user behavior of initiating connections with HTTP (e.g., typing example.com rather than https://example.com) and intercepting the server's redirect to HTTPS before it reaches the client.

The result: the victim communicates with the attacker over unencrypted HTTP throughout the session. The attacker communicates with the server over encrypted HTTPS. Every byte the victim sends — credentials, session tokens, financial data — is transmitted in plaintext to the attacker. The server's logs show a legitimate HTTPS connection from a trusted IP.

POODLE — Padding Oracle On Downgraded Legacy Encryption (2014)

POODLE, disclosed in October 2014 by Google researchers, is a more sophisticated downgrade attack that targets the TLS version negotiation process rather than the HTTP/HTTPS distinction. Modern clients and servers negotiate the highest mutually supported TLS version — TLS 1.2 or 1.3 in current deployments. POODLE exploited the fact that many servers still advertised SSL 3.0 as a supported fallback for compatibility with old clients.

The critical insight about POODLE: SSL 3.0 itself was already known to be cryptographically weak before POODLE. POODLE demonstrated a practical attack against it. The downgrade was the prerequisite — getting the client onto SSL 3.0 was necessary before the padding oracle exploitation could begin. Without the downgrade, modern TLS would have been used and the padding oracle technique would not apply.

Recommended Mitigations

• HTTP Strict Transport Security (HSTS): The primary defense against SSL stripping. An HSTS header instructs browsers to always connect to the domain over HTTPS, refusing HTTP connections entirely — including on the initial request. Once a browser has seen the HSTS header for a domain, it will not send the initial HTTP request that SSL stripping requires. HSTS preloading goes further: major browsers ship with a preloaded list of HSTS domains, protecting even first-time visitors before they've seen the header.
• Disable SSL 3.0 and legacy TLS versions: Remove SSL 3.0, TLS 1.0, and TLS 1.1 from all server configurations. Modern TLS 1.2 and TLS 1.3 do not have the padding oracle vulnerabilities that POODLE exploited. If all servers refuse to negotiate legacy protocols, downgrade attacks have no target to fall back to.
• TLS_FALLBACK_SCSV: A TLS extension that signals "this is a fallback connection" — if the server supports a higher protocol version than the client claims, it should abort the connection rather than proceed with the downgraded version. Prevents version downgrade even when legacy protocol support cannot be immediately removed.
• End-to-end HTTPS with no HTTP fallback: Configure web servers to refuse all HTTP connections (or redirect immediately with a 301 and add HSTS) rather than serving any content over HTTP. An attacker cannot strip HTTPS if the server never serves HTTP responses that the attacker can relay to the victim.