wrkspc.io

← code

hash collision

Real SHA-256, truncated short, colliding in seconds — a demonstration of why hash outputs are as long as they are.

hash sizebits
attempts0
expected5,134
search space2^24 = 16,777,216

the tick marks the expected number of attempts

what that costs as the hash gets longer

Each bar is the expected number of hashes to find a collision, on a logarithmic scale — so the straight line is the point. Every extra 2 bits doubles the work. Times are estimated at 150,000 hashes/sec (a typical rate; run a search above to use your own).

16
2^82 ms
32
2^16437 ms
40
2^207.0 seconds
64
2^328.0 hours
128
2^643.9 million years
160
2^8019 × the age of the universe
256
2^1285.2 × 10^15 × the age of the universe

why collisions exist

A cryptographic hash function squeezes an input of any size down to a fixed number of bits. Since there are more possible inputs than outputs, collisions — two inputs with the same digest — must exist; that part is just the pigeonhole principle and no amount of cleverness avoids it. The security property is not that collisions don't exist. It is that nobody can find one.

real sha-256

The hash above is genuinely SHA-256, implemented from scratch here rather than called from a library, and its output is then thrown away down to the handful of leading bits you choose. That truncation is the whole trick: everything that makes collisions hard to find is a consequence of the output being long, so shortening it puts a real cryptographic hash into a range where a laptop finishes the job before you finish reading this sentence.

the birthday bound

The number of attempts it takes is the surprising part. Guessing a specific hash output takes about 2n2^{n} tries, but finding any two inputs that merely match each other takes only about 2n/22^{n/2} — the square root. The expected number of attempts before a repeat appears in a space of N=2nN = 2^{n} values is

π2 N  =  π2⋅2n/2  ≈  1.2533⋅2n/2\sqrt{\frac{\pi}{2}\,N} \;=\; \sqrt{\frac{\pi}{2}} \cdot 2^{n/2} \;\approx\; 1.2533 \cdot 2^{n/2}

which is the number the expected column above is showing. This is the birthday problem: in a room of 23 people there is a coin-flip chance two share a birthday, even though there are 365 days, because what matters is not the number of people but the number of pairs of them,

(232)  =  23⋅222  =  253\binom{23}{2} \;=\; \frac{23 \cdot 22}{2} \;=\; 253

and 253 chances against 365 days is a fair bet. Pairs grow as (m2)≈m2/2\binom{m}{2} \approx m^2/2, quadratically in the number of attempts, so the useful comparisons pile up far faster than the guesses do. Every attempt in the search above is checked against every attempt before it, which is exactly that count.

why hashes are long

That square root is why hash lengths look so extravagant. An n-bit hash only buys n/2 bits of collision resistance, so the output has to be twice as long as the security level you actually want — 256 bits of hash for 128 bits of strength. It is also why every extra 2 bits doubles the attacker's work, and why the gap between something you can break over lunch and something nobody will ever break is only a few dozen bits wide.

broken in practice

This is not hypothetical. A birthday attack is exactly the procedure running above, and the bound it sets is what retired real hash functions. MD5 produces 128 bits, putting it within reach at 264; a distributed project was organised in 2004 to demonstrate exactly that. SHA-1 produces 160 bits, so its birthday bound sits at 280 — and in 2017 CWI and Google announced SHAttered, two different PDF files with the same SHA-1 digest, found in about 263 evaluations by exploiting structural weaknesses to beat that bound by a factor of roughly 100,000. Note which number did the damage: even a flawless 160-bit hash would only ever have offered 80 bits of collision resistance. The weaknesses shortened the timeline; the output length set the ceiling.

a related point

The vigenère cipher demo makes a related point from the other direction: there the attack works because the key repeats, and the fix is a key as long as the message. Here the attack works because the output is short, and the fix is an output long enough that 2n/2 is a number the universe does not have time for.

view source
import { useEffect, useRef, useState } from 'react';

// ---------- SHA-256 ----------
// The round constants are the first 32 bits of the fractional parts of the
// cube roots of the first 64 primes; the initial state is the same for the
// square roots of the first 8. Computing them from that definition rather
// than pasting a table means a typo can't quietly produce something that
// isn't SHA-256. Verified standalone against Node's own crypto across the
// empty string, every length from 1 to 200 (which covers the padding
// boundaries), and 2000 random inputs before being ported here.
function firstPrimes(count: number): number[] {
  const out: number[] = [];
  for (let n = 2; out.length < count; n++) {
    let prime = true;
    for (let d = 2; d * d <= n; d++) {
      if (n % d === 0) {
        prime = false;
        break;
      }
    }
    if (prime) out.push(n);
  }
  return out;
}

const fracBits = (x: number) => Math.floor((x - Math.floor(x)) * 2 ** 32) >>> 0;

const K = firstPrimes(64).map((p) => fracBits(Math.cbrt(p)));
const H_INIT = firstPrimes(8).map((p) => fracBits(Math.sqrt(p)));

const rotr = (x: number, n: number) => ((x >>> n) | (x << (32 - n))) >>> 0;

// Scratch buffers reused across calls -- this runs millions of times and
// allocating per hash dominates the cost otherwise.
const W = new Uint32Array(64);
const BLOCK = new Uint8Array(128);
const BLOCK_DV = new DataView(BLOCK.buffer);
const OUT = new Uint32Array(8);

// Inputs here are always short ASCII, so the whole message fits in the
// 128-byte scratch block and no chunk loop over separate buffers is needed.
function sha256Short(str: string): Uint32Array {
  const len = str.length;
  for (let i = 0; i < len; i++) BLOCK[i] = str.charCodeAt(i) & 0xff;
  const total = ((len + 9 + 63) >> 6) << 6;
  BLOCK[len] = 0x80;
  for (let i = len + 1; i < total; i++) BLOCK[i] = 0;
  BLOCK_DV.setUint32(total - 4, len * 8, false);

  OUT.set(H_INIT);
  for (let off = 0; off < total; off += 64) {
    for (let i = 0; i < 16; i++) W[i] = BLOCK_DV.getUint32(off + i * 4, false);
    for (let i = 16; i < 64; i++) {
      const a15 = W[i - 15];
      const a2 = W[i - 2];
      const s0 = rotr(a15, 7) ^ rotr(a15, 18) ^ (a15 >>> 3);
      const s1 = rotr(a2, 17) ^ rotr(a2, 19) ^ (a2 >>> 10);
      W[i] = (W[i - 16] + s0 + W[i - 7] + s1) >>> 0;
    }
    let a = OUT[0],
      b = OUT[1],
      c = OUT[2],
      d = OUT[3];
    let e = OUT[4],
      f = OUT[5],
      g = OUT[6],
      h = OUT[7];
    for (let i = 0; i < 64; i++) {
      const S1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25);
      const t1 = (h + S1 + ((e & f) ^ (~e & g)) + K[i] + W[i]) >>> 0;
      const S0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22);
      const t2 = (S0 + ((a & b) ^ (a & c) ^ (b & c))) >>> 0;
      h = g;
      g = f;
      f = e;
      e = (d + t1) >>> 0;
      d = c;
      c = b;
      b = a;
      a = (t1 + t2) >>> 0;
    }
    OUT[0] = (OUT[0] + a) >>> 0;
    OUT[1] = (OUT[1] + b) >>> 0;
    OUT[2] = (OUT[2] + c) >>> 0;
    OUT[3] = (OUT[3] + d) >>> 0;
    OUT[4] = (OUT[4] + e) >>> 0;
    OUT[5] = (OUT[5] + f) >>> 0;
    OUT[6] = (OUT[6] + g) >>> 0;
    OUT[7] = (OUT[7] + h) >>> 0;
  }
  return OUT;
}

function sha256Hex(str: string): string {
  const h = sha256Short(str);
  let out = '';
  for (let i = 0; i < 8; i++) out += h[i].toString(16).padStart(8, '0');
  return out;
}

// Keep the leading `bits` bits of the digest -- the leading hex characters,
// since every width offered here is a multiple of 4.
function truncate(h: Uint32Array, bits: number): number {
  if (bits <= 32) return h[0] >>> (32 - bits);
  const extra = bits - 32;
  return h[0] * 2 ** extra + (h[1] >>> (32 - extra));
}

const BIT_WIDTHS = [8, 12, 16, 20, 24, 28, 32, 36, 40];

// Expected attempts before a repeat in a space of 2^bits values is
// sqrt(pi/2 * 2^bits) -- confirmed standalone against measured averages over
// hundreds of trials at 12, 16, 20 and 24 bits, all within 2.4%.
const expectedAttempts = (bits: number) => Math.sqrt((Math.PI / 2) * 2 ** bits);

const CHUNK = 15000;
// Don't quote a measured hash rate until this many hashes have been timed.
const RATE_SAMPLE_MIN = 150000;

interface Found {
  bits: number;
  attempts: number;
  ms: number;
  a: string;
  b: string;
  hexA: string;
  hexB: string;
}

function formatBig(n: number): string {
  if (n < 1e6) return Math.round(n).toLocaleString();
  if (n < 1e15) return Math.round(n).toLocaleString();
  return n.toExponential(1).replace('e+', ' × 10^');
}

function formatDuration(seconds: number): string {
  if (seconds < 0.001) return 'under 1 ms';
  if (seconds < 1) return `${Math.max(1, Math.round(seconds * 1000))} ms`;
  if (seconds < 90) return `${seconds.toFixed(1)} seconds`;
  const minutes = seconds / 60;
  if (minutes < 90) return `${minutes.toFixed(1)} minutes`;
  const hours = minutes / 60;
  if (hours < 48) return `${hours.toFixed(1)} hours`;
  const days = hours / 24;
  if (days < 730) return `${days.toFixed(0)} days`;
  const years = days / 365.25;
  if (years < 1e6) return `${Math.round(years).toLocaleString()} years`;
  if (years < 1e9) return `${(years / 1e6).toFixed(1)} million years`;
  if (years < 1e12) return `${(years / 1e9).toFixed(1)} billion years`;
  return `${(years / 1e9).toExponential(1).replace('e+', ' × 10^')} billion years`;
}

// "18×" reads better than "1.8 × 10^1 ×" for the small multiples.
function formatMultiple(n: number): string {
  if (n < 1000) return Math.round(n).toLocaleString();
  return n.toExponential(1).replace('e+', ' × 10^');
}

// Widths worth putting on the scaling chart: the ones you can actually run
// here, then the real-world sizes.
const CHART_BITS = [16, 32, 40, 64, 128, 160, 256];
const AGE_OF_UNIVERSE_YEARS = 1.38e10;

export default function HashCollision() {
  const [bits, setBits] = useState(24);
  const [attempts, setAttempts] = useState(0);
  const [running, setRunning] = useState(false);
  const [found, setFound] = useState<Found | null>(null);
  const [log, setLog] = useState<Found[]>([]);
  const [rate, setRate] = useState<number | null>(null);

  const rafRef = useRef<number | null>(null);
  const stateRef = useRef<{
    seen: Map<number, number>;
    i: number;
    started: number;
    seed: number;
  } | null>(null);

  useEffect(() => {
    return () => {
      if (rafRef.current !== null) cancelAnimationFrame(rafRef.current);
    };
  }, []);

  const stop = () => {
    if (rafRef.current !== null) cancelAnimationFrame(rafRef.current);
    rafRef.current = null;
    setRunning(false);
  };

  const reset = () => {
    stop();
    stateRef.current = null;
    setAttempts(0);
    setFound(null);
  };

  // Throughput is accumulated across every search in the session, timing only
  // the hashing loops themselves (not the gaps between animation frames), and
  // is only surfaced once there's a big enough sample to mean anything -- a
  // rate read off a single 30ms run is mostly JIT warm-up and timer noise.
  const benchRef = useRef({ hashes: 0, ms: 0 });
  const recordRate = (hashes: number, ms: number) => {
    const b = benchRef.current;
    b.hashes += hashes;
    b.ms += ms;
    if (b.hashes >= RATE_SAMPLE_MIN && b.ms > 0) {
      setRate(Math.round(b.hashes / (b.ms / 1000)));
    }
  };

  const start = () => {
    stop();
    setFound(null);
    setAttempts(0);
    const seed = Math.floor(Math.random() * 1e9);
    stateRef.current = {
      seen: new Map(),
      i: 0,
      started: performance.now(),
      seed,
    };
    setRunning(true);

    const tick = () => {
      const st = stateRef.current;
      if (!st) return;
      const end = st.i + CHUNK;
      const chunkStart = performance.now();
      const chunkFrom = st.i;
      for (; st.i < end; st.i++) {
        const input = `${st.seed}-${st.i}`;
        const t = truncate(sha256Short(input), bits);
        const prev = st.seen.get(t);
        if (prev !== undefined) {
          const a = `${st.seed}-${prev}`;
          const ms = performance.now() - st.started;
          const result: Found = {
            bits,
            attempts: st.i + 1,
            ms,
            a,
            b: input,
            hexA: sha256Hex(a),
            hexB: sha256Hex(input),
          };
          setAttempts(st.i + 1);
          setFound(result);
          setLog((prevLog) => [result, ...prevLog].slice(0, 12));
          recordRate(st.i + 1 - chunkFrom, performance.now() - chunkStart);
          stateRef.current = null;
          setRunning(false);
          rafRef.current = null;
          return;
        }
        st.seen.set(t, st.i);
      }
      recordRate(CHUNK, performance.now() - chunkStart);
      setAttempts(st.i);
      rafRef.current = requestAnimationFrame(tick);
    };
    rafRef.current = requestAnimationFrame(tick);
  };

  const expected = expectedAttempts(bits);
  const progress = Math.min(1, attempts / (expected * 2));
  const hexChars = bits / 4;

  // Everything in the extrapolation panel is derived from the rate this
  // browser actually measured, not a number typed in here.
  const effectiveRate = rate ?? 150000;

  return (
    <div className="hash-collision">
      <div className="controls">
        <span className="group-label">hash size</span>
        {BIT_WIDTHS.map((b) => (
          <button
            key={b}
            type="button"
            className={b === bits ? 'active' : ''}
            onClick={() => {
              reset();
              setBits(b);
            }}
            disabled={running}
          >
            {b}
          </button>
        ))}
        <span className="unit">bits</span>
      </div>

      <div className="controls">
        <button type="button" onClick={start} disabled={running}>
          find collision
        </button>
        <button type="button" onClick={stop} disabled={!running}>
          stop
        </button>
        <button type="button" onClick={reset} disabled={running}>
          reset
        </button>
        {bits >= 36 && !found && (
          <span className="warn">
            ~{Math.round(expectedAttempts(bits) / 1000).toLocaleString()}k
            hashes to store and search
          </span>
        )}
      </div>

      <div className="readout">
        <div className="stat">
          <span className="stat-label">attempts</span>
          <span className="stat-value">{attempts.toLocaleString()}</span>
        </div>
        <div className="stat">
          <span className="stat-label">expected</span>
          <span className="stat-value muted-value">
            {Math.round(expected).toLocaleString()}
          </span>
        </div>
        <div className="stat">
          <span className="stat-label">search space</span>
          <span className="stat-value muted-value">
            2^{bits} = {formatBig(2 ** bits)}
          </span>
        </div>
      </div>

      <div className="bar-track">
        <div className="bar-fill" style={{ width: `${progress * 100}%` }} />
        <div className="bar-marker" style={{ left: '50%' }} />
      </div>
      <p className="bar-note">the tick marks the expected number of attempts</p>

      {found && (
        <div className="result">
          <p className="result-head">
            collision after <strong>{found.attempts.toLocaleString()}</strong>{' '}
            attempts, in {(found.ms / 1000).toFixed(2)}s
          </p>
          <div className="digests">
            {[
              [found.a, found.hexA],
              [found.b, found.hexB],
            ].map(([label, hex]) => (
              <div className="digest-row" key={label}>
                <span className="digest-input">{label}</span>
                <span className="digest-hex">
                  <span className="hex-match">{hex.slice(0, hexChars)}</span>
                  <span className="hex-rest">{hex.slice(hexChars, 40)}…</span>
                </span>
              </div>
            ))}
          </div>
          <p className="result-note">
            Two different inputs, the same first {bits} bits, completely
            different digests after that. Truncating the hash is what created
            the collision — the full SHA-256 of these two strings does not
            collide, and nobody has ever found a pair that does.
          </p>
        </div>
      )}

      {log.length > 0 && (
        <div className="log">
          <div className="log-head">
            <span>bits</span>
            <span>expected</span>
            <span>actual</span>
            <span>time</span>
          </div>
          {log.map((r, i) => (
            <div className="log-row" key={i}>
              <span>{r.bits}</span>
              <span className="muted-value">
                {Math.round(expectedAttempts(r.bits)).toLocaleString()}
              </span>
              <span>{r.attempts.toLocaleString()}</span>
              <span className="muted-value">{(r.ms / 1000).toFixed(2)}s</span>
            </div>
          ))}
        </div>
      )}

      <div className="scaling">
        <h3>what that costs as the hash gets longer</h3>
        <p className="scaling-note">
          Each bar is the expected number of hashes to find a collision, on a
          logarithmic scale — so the straight line is the point. Every extra
          <strong> 2 bits</strong> doubles the work. Times are estimated at{' '}
          <strong>{effectiveRate.toLocaleString()}</strong> hashes/sec
          {rate === null
            ? ' (a typical rate; run a search above to use your own)'
            : ', measured just now in this browser'}
          .
        </p>
        <div className="chart">
          {CHART_BITS.map((b) => {
            const att = 2 ** (b / 2);
            const secs = att / effectiveRate;
            const years = secs / (365.25 * 24 * 3600);
            const reachable = b <= 40;
            return (
              <div className="chart-row" key={b}>
                <span className="chart-bits">{b}</span>
                <div className="chart-bar-track">
                  <div
                    className={reachable ? 'chart-bar reachable' : 'chart-bar'}
                    style={{ width: `${(b / 2 / 128) * 100}%` }}
                  />
                </div>
                <span className="chart-att">2^{b / 2}</span>
                <span className="chart-time">
                  {years > AGE_OF_UNIVERSE_YEARS
                    ? `${formatMultiple(years / AGE_OF_UNIVERSE_YEARS)} × the age of the universe`
                    : formatDuration(secs)}
                </span>
              </div>
            );
          })}
        </div>
      </div>

      <style>{`
        .hash-collision {
          border: 1px solid #2a2d31;
          background: #0e1113;
          padding: 1.25rem 1rem;
        }
        .hash-collision .controls {
          display: flex;
          flex-wrap: wrap;
          align-items: center;
          gap: 0.4rem;
          margin-bottom: 0.75rem;
        }
        .hash-collision .group-label {
          color: var(--muted);
          font-size: 0.75rem;
          text-transform: uppercase;
          letter-spacing: 0.04em;
          margin-right: 0.35rem;
        }
        .hash-collision .unit {
          color: var(--muted);
          font-size: 0.75rem;
          margin-left: 0.15rem;
        }
        .hash-collision button {
          font-family: inherit;
          font-size: 0.75rem;
          color: #8a8f98;
          background: rgba(0, 0, 0, 0.4);
          border: 1px solid #2a2d31;
          padding: 0.25rem 0.6rem;
          cursor: pointer;
        }
        .hash-collision button:hover:not(:disabled) {
          color: #e6e6e6;
        }
        .hash-collision button:disabled {
          opacity: 0.4;
          cursor: default;
        }
        .hash-collision button.active {
          color: #0b0d0f;
          background: var(--accent);
          border-color: var(--accent);
        }
        .hash-collision .warn {
          color: var(--muted);
          font-size: 0.75rem;
        }
        .hash-collision .readout {
          display: flex;
          flex-wrap: wrap;
          gap: 1.75rem;
          margin: 1.1rem 0 0.6rem;
        }
        .hash-collision .stat {
          display: flex;
          flex-direction: column;
          gap: 0.15rem;
        }
        .hash-collision .stat-label {
          color: var(--muted);
          font-size: 0.7rem;
          text-transform: uppercase;
          letter-spacing: 0.04em;
        }
        .hash-collision .stat-value {
          font-size: 1.05rem;
          color: var(--accent);
        }
        .hash-collision .muted-value {
          color: var(--muted);
          font-size: 0.9rem;
        }
        .hash-collision .bar-track {
          position: relative;
          height: 6px;
          background: rgba(0, 0, 0, 0.5);
          border: 1px solid #2a2d31;
          overflow: hidden;
        }
        .hash-collision .bar-fill {
          height: 100%;
          background: var(--accent);
          opacity: 0.7;
        }
        .hash-collision .bar-marker {
          position: absolute;
          top: 0;
          bottom: 0;
          width: 1px;
          background: #e6e6e6;
          opacity: 0.6;
        }
        .hash-collision .bar-note {
          color: var(--muted);
          font-size: 0.7rem;
          margin: 0.35rem 0 0;
        }
        .hash-collision .result {
          margin-top: 1.25rem;
          padding-top: 1rem;
          border-top: 1px solid #2a2d31;
        }
        .hash-collision .result-head {
          font-size: 0.85rem;
          color: var(--muted);
          margin: 0 0 0.75rem;
        }
        .hash-collision .result-head strong {
          color: var(--accent);
          font-weight: normal;
        }
        .hash-collision .digests {
          display: flex;
          flex-direction: column;
          gap: 0.4rem;
          overflow-x: auto;
        }
        .hash-collision .digest-row {
          display: flex;
          gap: 0.9rem;
          align-items: baseline;
          font-size: 0.8rem;
          white-space: nowrap;
        }
        .hash-collision .digest-input {
          color: var(--muted);
          min-width: 9rem;
        }
        .hash-collision .hex-match {
          color: #0b0d0f;
          background: var(--accent);
          padding: 0.05rem 0.1rem;
        }
        .hash-collision .hex-rest {
          color: #6f757d;
        }
        .hash-collision .result-note {
          color: var(--muted);
          font-size: 0.8rem;
          margin: 0.9rem 0 0;
        }
        .hash-collision .log {
          margin-top: 1.25rem;
          padding-top: 1rem;
          border-top: 1px solid #2a2d31;
          font-size: 0.78rem;
        }
        .hash-collision .log-head,
        .hash-collision .log-row {
          display: grid;
          grid-template-columns: 3rem 1fr 1fr 4rem;
          gap: 0.5rem;
        }
        .hash-collision .log-head {
          color: var(--muted);
          text-transform: uppercase;
          font-size: 0.68rem;
          letter-spacing: 0.04em;
          padding-bottom: 0.35rem;
          border-bottom: 1px solid #2a2d31;
        }
        .hash-collision .log-row {
          padding: 0.25rem 0;
        }
        .hash-collision .scaling {
          margin-top: 1.5rem;
          padding-top: 1rem;
          border-top: 1px solid #2a2d31;
        }
        .hash-collision .scaling h3 {
          font-size: 0.85rem;
          font-weight: normal;
          color: var(--fg);
          margin: 0 0 0.4rem;
        }
        .hash-collision .scaling-note {
          color: var(--muted);
          font-size: 0.8rem;
          margin: 0 0 1rem;
        }
        .hash-collision .scaling-note strong {
          color: var(--fg);
          font-weight: normal;
        }
        .hash-collision .chart {
          display: flex;
          flex-direction: column;
          gap: 0.45rem;
        }
        .hash-collision .chart-row {
          display: grid;
          grid-template-columns: 2.5rem 1fr 3.5rem auto;
          gap: 0.6rem;
          align-items: center;
          font-size: 0.75rem;
          color: var(--muted);
        }
        .hash-collision .chart-bits {
          text-align: right;
          color: var(--fg);
        }
        .hash-collision .chart-bar-track {
          background: rgba(0, 0, 0, 0.4);
          height: 10px;
          border: 1px solid #2a2d31;
        }
        .hash-collision .chart-bar {
          height: 100%;
          background: #3a3f45;
        }
        .hash-collision .chart-bar.reachable {
          background: var(--accent);
        }
        .hash-collision .chart-att {
          color: var(--fg);
        }
        @media (max-width: 30rem) {
          .hash-collision .chart-row {
            grid-template-columns: 2.2rem 1fr 3.2rem;
          }
          .hash-collision .chart-time {
            grid-column: 2 / -1;
          }
          .hash-collision .digest-input {
            min-width: 7rem;
          }
        }
      `}</style>
    </div>
  );
}