Why a Digest Buys Only Half Its Bits

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.

See the relationship before changing it

The figure reads from left to right. The blue card is digest length. The middle card applies the page rule. The green card is collision resistance. Walk the arrows once: set the input, apply the rule, then read the result with its unit.

Walk the arrows. The birthday bound halves the exponent. A longer digest cannot repair a broken hash.

Derive the baseline in four named moves

1. 1

   Name the input. The chapter baseline is 256 bits.

2. 2

   Name the relationship. collision resistance = digest length / 2

3. 3

   Substitute with units. 256 / 2 = 128.00 bits

4. 4

   Read the result. Keep the unit beside the value. Use it only inside the technical boundary on this page.

Predict, then change digest length

Try Predict the direction of collision resistance = digest length / 2. Test another digest length, then compare collision resistance.

Digest length

256 bits

Chapter baseline

Collision resistance

Observe The birthday bound halves the exponent. A longer digest cannot repair a broken hash. Reset digest length to 256 and compare collision resistance.

Explain The birthday bound halves the exponent. A longer digest cannot repair a broken hash.

Check yourself

What should you do before trusting a moved-control result?

Answer: Predict its direction, apply the shown relationship, keep the units, and reset to the worked baseline.

What does this small model leave out?

Answer: Only digest length moves here. Field effects named in the technical boundary stay fixed.

Honesty note. This teaching model changes only digest length. It is not a field prediction.

TryThe 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. Use Check derivation.

ObserveThe displayed ledger resolves n/2, SHA-256, 2^128, 64-bit, 4.3 billion at full precision. This audit shows where the half comes from — why a digest buys only half its bits — and why length cannot rescue a broken algorithm. Check derivation shows this.

ExplainThe 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. Check derivation confirms it.

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.

Technical boundaries
The birthday model deliberately assumes uniformly random independent digest outputs; it does not simulate preimage attacks, protocol misuse, chosen-prefix techniques, truncation formats, or implementation flaws.

Work the audit first, then check the displayed derivation.

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