---
title: 'Hash Functions'
source: 'https://academia.sh/en/courses/identity-and-cryptography/hash-functions'
course: 'Identity, Access and Cryptography'
language: en
updated: '2026-09-26T03:02:52+00:00'
license: 'CC BY-SA 4.0'
objectives:
    - "Measures hashing's fixed output length, determinism, and avalanche effect on the same input"
    - 'Searches for the first collision in a truncated output and compares the measured attempt count against the theoretical birthday bound'
    - 'Separates uses that rely on preimage resistance from those that rely on collision resistance, and counts the item that falls at the moment of breaking'
---

# Hash Functions

Measuring collision resistance against the birthday bound: fixed output length, a single-bit input change flipping about half the output bits, the first collision in a truncated output being found — averaged over 32 rounds — at 0.97–1.15 times the theoretical bound, and an n-bit output being bounded by 2^(n/2) tying 12,502 of the 25,242 items in the usage set to collision resistance.

The previous lesson passed over hashing's root in one sentence: two different inputs do not give
the same output. That sentence, as it stands, cannot be true. Hashing's output has a fixed
length, while the number of possible inputs is unlimited; therefore, different inputs that give
the same output certainly exist, and their number is unlimited too. The root is not that a
collision does not exist, but that it cannot be found.

"Cannot be found," though, is a number. This lesson measures that number: at how many bits of
output does the first collision appear in how many attempts, how closely does the measured
value match the theoretical bound, and what happens to the number of attempts needed when the
output length doubles.

## Four Properties, Two Separate Resistances

**CF5:** hashing's output space is finite, its input space unlimited; different inputs that
give the same output certainly exist. The root is not the absence of a collision, but the
search cost being unaffordable.

**CF6:** in an n-bit output, the cost of searching for a collision is upper-bounded by 2^(n/2),
and that bound is independent of the algorithm's internal design; it comes only from the output
length.

The two resistances are distinct from one another. Preimage resistance makes it hard to find
any input that produces a given output; its cost is on the order of 2^n. Collision resistance
makes it hard to find *any two* inputs that give the same output, and its cost is 2^(n/2). The
difference comes from the attacker's freedom in choosing the output: in the first, the target
is fixed; in the second, both inputs are free. That freedom takes the square root of the cost.

```js
// hash/properties.mjs — measures the four properties of hashing: fixed length, determinism, avalanche
// effect, and the theoretical bound the output length brings. The input is a meter reading from the
// fictional regional measurement network. No randomness; every run gives the same numbers.
import { createHash } from "node:crypto";

// CF5: hashing's output space is finite, its input space unlimited; different inputs that give the
//      same output certainly exist. The root is not the absence of a collision, but that it cannot be found.
// CF6: in an n-bit output, the cost of searching for a collision is upper-bounded by 2^(n/2); this
//      bound is independent of the algorithm's internal design, and comes only from the output length.

const READING = "SAY-4417|2026-03-01T06:00Z|41982";
const ALG = ["md5", "sha1", "sha256", "sha512"];
const bitCount = (b) => { let n = 0; for (const x of b) n += (x.toString(2).match(/1/g) || []).length; return n; };
const printRow = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));

const A = [-10, 7, 12, 12, 12];
printRow(A, "algorithm", "bytes", "output bit", "preimage", "collision");
for (const a of ALG) {
  const n = createHash(a).update(READING).digest().length * 8;
  printRow(A, a, n / 8, n, "2^" + n, "2^" + n / 2);
}

console.log("\navalanche effect: one bit of the input is flipped, how many bits change in the output");
const B = [-10, 10, 8, 10, 8, 10];
printRow(B, "algorithm", "flipped", "min", "average", "max", "expected");
for (const a of ALG) {
  const original = createHash(a).update(READING).digest();
  const bit = original.length * 8;
  let lo = Infinity, hi = 0, t = 0, times = 0;
  for (let i = 0; i < READING.length * 8; i++) {
    const g = Buffer.from(READING); g[i >> 3] ^= 1 << (i & 7);
    const y = createHash(a).update(g).digest();
    let f = 0;
    for (let j = 0; j < y.length; j++) f += bitCount(Buffer.from([original[j] ^ y[j]]));
    lo = Math.min(lo, f); hi = Math.max(hi, f); t += f; times++;
  }
  printRow(B, a, times, lo, (t / times).toFixed(1), hi, bit / 2);
}

console.log("\ndoes the same input give the same output:",
  createHash("sha256").update(READING).digest("hex") ===
  createHash("sha256").update(READING).digest("hex") ? "yes" : "no");
```

```
algorithm   bytes  output bit    preimage   collision
md5            16         128       2^128        2^64
sha1           20         160       2^160        2^80
sha256         32         256       2^256       2^128
sha512         64         512       2^512       2^256

avalanche effect: one bit of the input is flipped, how many bits change in the output
algorithm    flipped     min   average     max  expected
md5              256      50      64.1      78        64
sha1             256      62      79.7     100        80
sha256           256     110     128.8     149       128
sha512           256     219     256.4     288       256

does the same input give the same output: yes
```

The avalanche-effect table measures that hashing leaves no structural trace between input and
output. When a single bit of the input is flipped, SHA-256's output changes by an average of
128.8 bits — about half of 256 bits. The lowest measurement is 110, the highest 149; for all
four algorithms, the average settles at half the output's bits. That half ratio is the sign
that the output behaves as if independent of the input. In encoding, a one-bit input change
would touch only that region of the output; here, both the location and the amount of change
are unrelated to the input.

Determinism together with the avalanche effect is what turns hashing into a fingerprint.
Without determinism, two digests of the same data could not be compared; without the avalanche
effect, similar data would produce similar digests, and whoever looked at the digest could
infer part of the data. Together, the two make it possible to answer the question "is it the
same" without holding the data itself.

The two columns on the right, though, are this lesson's real subject. Every algorithm's
collision bound is the square root of its preimage bound: a 128-bit output is bounded to 2^64,
a 160-bit output to 2^80, a 256-bit output to 2^128. This number has nothing to do with the
algorithm's quality — it has to do with the output length itself, and it is the same even for a
flawless hash function.

## Measuring the Birthday Bound

The theoretical bound is a measurable claim. The unit below takes only the first n bits of the
SHA-256 output and searches for the first collision on this output that **it itself
truncated**. What is measured is not the algorithm; it is the bound that the output length brings.
For each output size, thirty-two independent rounds are run and averaged, because a single
round's result swings across a wide band.

```js
// hash/collision.mjs — measuring collision resistance against the birthday bound. The first n bits of
// the SHA-256 output are taken, and the first collision is searched for on this output that we
// ourselves truncated. What is measured is not the algorithm itself, but the bound that the output
// length brings. Inputs are generated with a counter; no randomness, every run gives the same numbers.
import { createHash } from "node:crypto";

// CF7: the expected number of attempts until the first collision in an n-bit output is 1.2533 *
//      2^(n/2); when the output length doubles, the expected number of attempts grows by its square.

const truncate = (m, bit) => {                 // first `bit` bits of the SHA-256 output
  const h = createHash("sha256").update(m).digest();
  let v = 0n;
  for (let i = 0; i < 8; i++) v = (v << 8n) | BigInt(h[i]);
  return (v >> BigInt(64 - bit)).toString(16);
};
const firstCollision = (bit, round) => {       // `round` gives a different input sequence each round
  const seen = new Map();
  for (let i = 0; ; i++) {
    const m = `t${round}-olcum-${i}`, k = truncate(m, bit);
    if (seen.has(k)) return i + 1;
    seen.set(k, m);
  }
};
const ROUNDS = 32;                             // independent round count for each output size
const printRow = (g, ...s) => console.log(s.map((v, i) =>
  (g[i] < 0 ? String(v).padEnd(-g[i]) : String(v).padStart(g[i]))).join(""));
const G = [7, 18, 13, 11, 8, 10, 10];
printRow(G, "output", "possible outputs", "theoretical", "measured", "ratio", "earliest", "latest");
for (const bit of [8, 12, 16, 20, 24, 28, 32]) {
  let total = 0, lo = Infinity, hi = 0;
  for (let j = 0; j < ROUNDS; j++) {
    const d = firstCollision(bit, j);
    total += d; lo = Math.min(lo, d); hi = Math.max(hi, d);
  }
  const avg = total / ROUNDS, theory = 1.2533 * 2 ** (bit / 2);
  printRow(G, bit + " bit", (2 ** bit).toLocaleString("en-US"), theory.toFixed(0),
      avg.toFixed(0), (avg / theory).toFixed(2), lo, hi);
}
```

```
 output  possible outputs  theoretical   measured   ratio  earliest    latest
  8 bit               256           20         21    1.03         7        48
 12 bit             4,096           80         92    1.15        28       188
 16 bit            65,536          321        368    1.15        91       675
 20 bit         1,048,576         1283       1397    1.09       127      3395
 24 bit        16,777,216         5134       4986    0.97      1630     11910
 28 bit       268,435,456        20534      21479    1.05      2771     48277
 32 bit     4,294,967,296        82136      86497    1.05     10808    167350
```

In all seven rows, the measured value stays between 0.97 and 1.15 times the theoretical bound.
This is proof that the formula is not an approximation but a measurable estimate. The truncated
output is not a real cracking attempt; the discarded bits of the SHA-256 output keep getting
computed, and the search runs only over the n bits kept on hand. What is measured is the bound
that those n bits carry.

The real result is in comparing the second and fourth columns. The 32-bit output has more than
four billion possible values; the first collision is found in an average of 86,497 attempts.
The ratio is roughly one **in** fifty thousand. Intuition fails here: it seems like the
collision should get harder as the space grows, but what is being sought is not landing on a
specific value — it is *any two* attempts landing on each other, and as the number of attempts
grows, the number of pairs grows quadratically.

It is possible to confirm this quadratic growth with the table's numbers. In 86,497 attempts,
the number of pairs that can be compared against each other is 86,497 × 86,496 / 2, which is
roughly 3.74 billion; the 32-bit output space carries 4.29 billion values. The two numbers
arriving at the same order of magnitude is the moment a collision is expected. What is sought
is not the number of attempts approaching the output space — it is the **number of pairs**
approaching it, and the number of pairs grows with the square of the number of attempts. The
entire birthday bound follows from this single observation.

The last two columns show the width of the band. For 32 bits, the earliest collision was found
on attempt 10,808, the latest on attempt 167,350 — a fifteen-fold difference. The average
matches theory, but a single run does not. This is why security bounds are written not against
the average but against the **earliest** case: a defense has to hold in every run, not half of
them.

The row-to-row progression is countable too. When the output goes from 16 to 32 bits, the
number of possible outputs goes from 65,536 to over four billion — its square; the measured
number of attempts goes from 368 to 86,497, roughly the same ratio. Each bit added to the
output multiplies the needed number of attempts by only 1.41. Adding eight bits brings a
sixteen-fold increase, adding sixty-four bits brings a four-billion-fold increase. That is the
root: collision resistance gives security bits equal to **half** the output length, and that
ratio cannot be changed by any design.

## The Cost of Truncation

Per the course's security rule, the measurement above was not run against a real algorithm but
against an output **we truncated ourselves**. This truncation is not just a measurement trick;
it is a decision genuinely encountered in setup. To save space in a log line or a database
column, not the entire digest but only its first few bytes is stored, and this is often assumed
to be just a storage choice.

The number shows this is not a storage choice. If the first 64 bits of a 256-bit output are
kept, the collision bound drops from 2^128 to 2^32. That is exactly what is measured in the
table's last row: for a 32-bit output, the first collision was found in an average of 86,497
attempts. For a 64-bit output, the same formula gives roughly 5.4 billion attempts — it looks
like a large number, but it is work an ordinary machine can do on the order of hours.
Truncation's cost is not linear: discarding half the output leaves not half the security but its
**square root**.

Truncation does not produce the same result in every use. For a matching field in a log, 64 bits
might be enough, because what is sought there is not two records giving the same digest, but
tracking a specific record. In an integrity check, though, the same truncation directly breaks
the root. The criterion fits in one sentence: if the claim a field carries rests on collision
resistance, the output is not truncated.

## Which Use Depends on Which Resistance

The cost of a broken root is the number of items tied to that root. In the fictional regional
measurement network, hashing is used in five separate places, and the five do not rest on the same
resistance.

| Use | Resistance relied on | Item | If collision resistance drops |
|---|---|---|---|
| Device firmware integrity digest | collision | 12,400 | falls |
| Serial number digest in the log | preimage | 12,400 | stands |
| Digest signed between branches | collision | 6 | falls |
| Field crew password record | preimage | 340 | stands |
| Backup file fingerprint | collision | 96 | falls |

Of the twenty-five thousand two hundred forty-two items, 12,502 are tied to collision
resistance, 12,740 to preimage resistance. The distinction is sharp: when collision resistance
drops, two different device firmwares that produce the same digest become producible, and the
integrity check accepts both. In the password record, though, the attacker holds a fixed target
output and has to search for an input that lands on it; this is a preimage problem, and
collision resistance dropping does not make it any easier.

MD5 and SHA-1 are concrete examples of this distinction. Both are open specifications, both are
still computable, and neither has had its preimage resistance broken. The reason they were
deprecated lies on the collision side: the 2^64 and 2^80 bounds dropped to a reachable order of
magnitude, and structural weaknesses led to going even below those bounds. The result is that
the table's two columns are affected separately — a password record and an integrity digest
produced with these algorithms do not carry the same urgency.

The cost of renewal is the third column, and it is counted item by item. For firmware digests,
renewal is a single batch operation: 12,400 digests are recomputed, and the number of items
touched by hand is zero. For backup file fingerprints, it is different — the original digest of
the 96 backups sits in old records, and matching it to the new one is done by hand. For the
digest signed between branches, it is not just the digest that is renewed but the signature too;
six separate approval steps are needed for six branches, and transfers cannot be verified during
the renewal window. The same root breaking costs zero, 96, and 6 items by hand across the three
uses; what determines the item count is not how many records are affected, but how many records
**need a human decision to be renewed**.

## Summary

- Because hashing's output space is finite, a collision certainly exists; the trust root is not
  the absence of a collision, but the search cost being unaffordable.
- When a single bit of the input is flipped, about half the output bits change: for SHA-256,
  the measured average is 128.8 out of 256 bits.
- The expected number of attempts until the first collision in an n-bit output is on the order
  of 2^(n/2); across seven separate output sizes, the measured value came out at 0.97–1.15
  times the theoretical bound.
- The average matches theory, but a single run does not: at 32 bits, the earliest collision is
  at attempt 10,808, the latest at attempt 167,350; the security bound is written against the
  earliest case.
- Collision resistance gives security bits equal to half the output length; of the fictional
  network's 25,242 items, 12,502 are tied to this resistance, 12,740 to preimage resistance.

## Next Step

The cost measured in this lesson rested on the assumption that the attacker has **no
information at all**: inputs were generated by a counter, and every attempt was equally likely.
When it comes to passwords, this assumption falls apart. Strings that people choose are not
evenly distributed across the possible input space; a candidate list of a few hundred million
covers a computable portion of the space. In that case, the 2^256 preimage bound carries no
weight at all, because the search is not done over the whole space but inside the list. The next
lesson measures two separate defenses against this situation: the work factor, which raises the
unit cost of every attempt, and salt, which multiplies a rainbow table by the number of
records. Both have their own bound, and that bound is countable.