A birthday attack is a cryptographic attack that exploits the mathematics of the birthday paradox to find hash collisions more efficiently than brute force. The birthday paradox states that in a group of just 23 people, there is a 50 percent probability that two share the same birthday. Applied to cryptography, this means finding two different inputs that produce the same hash output requires far fewer attempts than expected, approximately the square root of the total possible hash values.
The attacker generates a large number of variants of two different messages, one legitimate and one malicious, by making minor modifications that do not change their meaning. For each variant, the attacker computes the hash value. Due to the birthday paradox, a collision between a legitimate variant and a malicious variant is found after approximately 2^(n/2) attempts, where n is the hash output length in bits. For a 128-bit hash like MD5, this means roughly 2^64 operations rather than 2^128. Once a collision is found, the attacker can substitute the malicious message for the legitimate one without changing the hash. This has practical implications for digital signatures, where two documents with the same hash would have the same valid signature.
Birthday attacks were instrumental in the practical deprecation of MD5 and SHA-1 hash functions. Researchers demonstrated real-world SHA-1 collisions in the SHAttered attack, producing two PDF documents with identical SHA-1 hashes but different content. This broke the security assumptions of certificate authorities, code signing, and version control systems that relied on SHA-1. Organizations must use hash functions with sufficient output length, migrate from MD5 and SHA-1 to SHA-256 or SHA-3 for all integrity-critical applications, and ensure digital signature schemes use collision-resistant hash functions.