The Birthday Attack: Hash Collisions and Probability

A birthday attack is a cryptographic attack that finds two different inputs producing the same hash value — a collision — using far fewer attempts than intuition suggests. It exploits the birthday paradox: the probability that any two items in a set share a value grows much faster than the probability that a specific item matches a chosen target. For a hash function with an n-bit output, finding a specific preimage takes on the order of 2ⁿ tries, but finding any collision takes only about 2^(n/2). That square-root shortcut is why hash output length matters so much on the Security+ SY0-701 exam (the full SY0-701 study guide shows where cryptographic attacks fit in your prep).

The birthday paradox behind it

The name comes from a classic probability result: in a room of just 23 people, there’s better than a 50% chance that two of them share a birthday. That feels wrong, because people confuse two different questions. The chance that someone shares your specific birthday is low — you’re comparing one date against each other person. But the chance that any two people match counts every possible pair, and 23 people form 253 pairs. It’s the number of comparisons, not the number of people, that drives the probability up.

Hash collisions work identically. Comparing your one target hash against random inputs is slow. But if you generate a large batch of inputs and compare them all against each other, the number of pairs — and therefore the collision probability — explodes. You’re no longer hunting one specific match; you’re waiting for any coincidence in a growing pile.

How the attack works mechanically

The attacker’s goal is any collision, not a match to a predetermined value. A typical run:

1. Generate many variations of a message (whitespace tweaks, synonyms, invisible characters) — often two message families: one benign, one malicious.
2. Hash each variation and store the results.
3. Watch for two inputs that hash to the same value.

Because of the pairwise math, a hash with an n-bit output falls to a collision after roughly 2^(n/2) hashes. Concretely, a 128-bit hash (like MD5’s output) needs only about 2⁶⁴ attempts to collide — feasible for a well-resourced attacker — even though brute-forcing a specific preimage would take 2¹²⁸. This is exactly why MD5 and SHA-1 are deprecated: their outputs are too short (and their internal weaknesses make collisions even cheaper than the birthday bound).

Why a collision is dangerous

The damaging version is the chosen-prefix / collision forgery used against digital signatures. Suppose the attacker crafts two documents — an innocent contract and a fraudulent one — that hash to the same value. They get the victim to digitally sign the innocent document. Because a digital signature is really a signature over the hash, that same signature now validates the fraudulent document too. The attacker has a genuinely signed forgery without ever knowing the signer’s private key. Collisions also undermine certificates — the trust anchor behind certificate-based authentication — as well as software integrity checks and any system that treats “same hash = same file.” A collision-forged certificate is most dangerous when paired with traffic redirection such as DNS poisoning or hijacking, letting an attacker impersonate a site behind a signature that validates.

Preimage resistance vs collision resistance

This is the distinction the exam wants you to hold precisely:

	Preimage resistance	Collision resistance
The hard task	Find an input matching one specific target hash	Find any two inputs with the same hash
Effort for n-bit hash	~2ⁿ	~2^(n/2)
Attack that breaks it	Brute-force / preimage attack	Birthday attack
Everyday analogy	Find someone with your birthday	Find any two people who share a birthday

The birthday attack targets collision resistance specifically. That’s the whole trick: the attacker doesn’t care which value collides, only that two inputs match — and that relaxed goal is quadratically easier.

Defenses

• Use a long hash output. Doubling the digest size squares the birthday work factor. SHA-256 gives ~2¹²⁸ collision resistance — comfortably out of reach. This is the direct countermeasure: pick a hash whose n/2 is still infeasible.
• Use collision-resistant algorithms. Prefer the SHA-2 and SHA-3 families; avoid MD5 and SHA-1, which are broken in practice.
• Salting doesn’t stop birthday attacks on the algorithm — salts defend stored password hashes against precomputed rainbow tables, a different problem. Don’t confuse the two on the exam.

How the SY0-701 exam tests this

• Name the attack from the probability description. A stem explains that finding two inputs sharing a hash needs far fewer attempts than finding one input matching a specific target, and asks which attack this is. The “any two vs one specific” framing is the signature of a birthday attack.
• Connect it to hash length. Questions ask why short-digest hashes (MD5, SHA-1) are unsafe or why moving to SHA-256 helps — because collision resistance is only ~2^(n/2), so bigger n is the fix.
• The signature-forgery scenario. Two documents engineered to share a hash so one signature validates both points to a birthday/collision attack, with the remedy being a stronger, longer hash function.
• Distinguish from siblings. Wrong options usually include brute-force/preimage (matching a specific hash), rainbow tables (precomputed lookups defeated by salting), and downgrade attacks. Reserve “birthday attack” for the find-any-collision case.

The “any two vs one specific” framing only becomes instinct through repetition — drill it with SY0-701 practice questions until the discriminator jumps out on its own.

Quick reference

• Birthday attack = find any two inputs with the same hash, exploiting the birthday paradox.
• The paradox: collision probability rises with the number of pairs, not the number of items — that’s why 23 people suffice for a shared birthday.
• Work factor: ~2^(n/2) to collide an n-bit hash, versus ~2ⁿ for a specific preimage — a square-root shortcut.
• It attacks collision resistance, not preimage resistance.
• Chosen-prefix collisions forge digital signatures: one signature validates two documents that share a hash.
• Defense = longer, stronger digests (SHA-256/SHA-3); MD5 and SHA-1 are deprecated for exactly this reason.
• Salting protects stored password hashes from rainbow tables — it does not stop birthday attacks.