Why a Digest Buys Only Half Its Bits

Ada re-derives this chapter’s own numbers step by step, at full precision

ADA · CALCULATION AUDIT

Why a Digest Buys Only Half Its Bits

The chapter states one rule it leans on repeatedly: “an n-bit digest offers only about n/2 bits of collision resistance.” That fraction is why SHA-256 gives only 2^128 collision effort, why a 64-bit digest falls in about 4.3 billion tries, and why doubling a digest buys only half as many security bits. This audit shows where the half comes from — why a digest buys only half its bits — and why length cannot rescue a broken algorithm.

Companion to the chapter Hash Functions and Data Integrity — every number here comes from that chapter.

Ada: The chapter states one quantitative rule and then leans on it repeatedly: “an n-bit digest offers only about n/2 bits of collision resistance.” That single fraction is what makes MD5 and SHA-1 unsafe and what “very short digests are unsuitable” really means. Let me show where the half comes from and then price it out.

A collision is any two inputs that share a digest. With an n-bit digest there are 2^n possible outputs, and the birthday argument says you should expect a collision after roughly the square root of that many random inputs:

• Tries for a ~50% collision: sqrt(2^n) = 2^(n/2) (the exact constant is sqrt(2 x ln 2) = 1.1774, which I round away)

So the effort is 2^(n/2), not 2^n — the exponent is halved. Plugging in the chapter’s own families:

• SHA-256: preimage effort 2^256, but collision effort only 2^(256/2) = 2^128
• A truncated 64-bit digest (illustrative): collision effort 2^(64/2) = 2^32 = 4,294,967,296 — about 4.3 billion tries, which ordinary hardware finishes quickly

That 64-bit case is exactly why length matters, and also why length alone cannot save you. Watch what doubling the digest buys: going from a 128-bit to a 256-bit digest lifts collision resistance from 128/2 = 64 bits to 256/2 = 128 bits — you paid for 128 extra output bits and received only 64 extra bits of security.

The design meaning is the chapter’s own warning made precise: because collision resistance is always half the digest length, you defend a signature by choosing an unbroken algorithm, never by stretching the digest of a broken one — a longer MD5 would still collide far below its 2^(n/2) ceiling.

Every number above is taken from the chapter’s own material and re-derived step by step.