Hash Functions: Avalanche and Integrity

in reviewThis lesson is complete and being validated before release - details may still change.

Hash functions

Loading interactive demo…

The top strip is the message, byte by byte; tap a byte to move the tamper there. Each grid shows one word of the padded message passing through the compression function: the word's bits on the top row, the state after each round beneath, the state the next word starts from at the bottom. The left grid is the message as written, the right its copy with one bit flipped, and the bits where the two differ are ringed. The strips beneath hold the state after every word; tap one to show that word.Take the tour, or press and explore. Legend:

The panel beside the stage is the real ToyHash class from the published library executing in your browser, with the current line highlighted.

A 1 bit of the state.
The row being computed, and the state of the block under way.
A bit that differs between the two runs, and the tampered byte.
A finished digest.
Rows the run has not reached yet, ghosted.

digest is the message's digest, tampered the digest of the flipped copy, flipped how many of the 32 digest bits differ, intact whether the two digests match. The block chip only changes which word the grids show.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

What a hash promises. A cryptographic hash $H$ maps any message to a fixed digest, here $32$ bits, in practice $256$ . It is trusted for three things: preimage resistance, given $d$ nobody can find $m$ with $H(m) = d$ ; second-preimage resistance, given $m$ nobody can find $m' \ne m$ with the same digest; collision resistance, nobody can find any pair with one digest. Trying at random, a preimage costs about $2^n$ guesses for an $n$ -bit digest and a collision about $2^{n/2}$ , by the birthday bound: among $k$ random digests the expected number of colliding pairs is $\binom{k}{2} / 2^n$ , which reaches $1$ near $k = 2^{n/2}$ . A $32$ -bit toy falls to $2^{16}$ guesses; $256$ bits do not fall.

Merkle-Damgard. The construction chains a compression function $f$ that takes a state and one block:

s_0 = \text{IV}, \qquad s_{i+1} = f(s_i, b_i), \qquad H(m) = s_k ,

with the padded message cut into blocks $b_0, \ldots, b_{k-1}$ . Merkle and Damgard proved that if $f$ is collision resistant then so is $H$ , provided the padding is suffix free: no padded message is the end of another. Appending the length does it, because two messages of different lengths end in different last blocks. Without it, "a" and "a" followed by a zero byte could pad to the same blocks.

The compression function. The stage's $f$ xors the word into the state, mixes with a Speck round for a few rounds, and adds the incoming state back:

f(s, b) = \text{mix}(s \oplus b) + s .

The feed-forward is the Davies-Meyer shape: without it, $f$ would be a permutation of the state for each block, and a permutation can be run backwards, which would let an attacker choose a digest and work back to a message. The round itself is rotate, add, xor, rotate, xor: addition carries bits upward, rotation moves them across, and xor with a constant breaks symmetry between rounds.

Avalanche. A good hash should behave like a random function, and a random function changes each output bit with probability $1/2$ when any input bit changes, so about half the digest flips. The flipped readout measures it. At one round the flipped bit reaches only the few positions a rotation and a carry can send it; by four rounds every output bit depends on every input bit of the block, and the chaining spreads that dependence to every later block. A hash that fell short here would let an attacker steer the digest.

Length extension. One thing the construction does not hide: the digest is the final state, so anyone who knows $H(m)$ and the length of $m$ can continue absorbing blocks and compute $H(m \| \text{pad} \| m')$ without knowing $m$ . That is why "hash the secret and the message" is a broken authentication code and HMAC hashes twice; SHA-3's sponge keeps part of its state unexposed to avoid the issue altogether.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

pad appends the length as a whole word, even for an empty message, so the trace always has at least one block and the suffix-free argument holds for every input.
compress ends with (mixed + stateIn) >>> 0, the feed-forward, and the >>> 0 is how JavaScript keeps a 32-bit unsigned result: without it the sum would be a signed number or a double past $2^{32}$ .
The round constant is 0x9e37 * (round + 1) + 0x79b9, masked to sixteen bits: the golden ratio's bits, so that rounds differ and no round maps a zero state to a zero state.
run returns intact: true with no tampered digest when the tamper index is out of range, so the tamper and diff tags are absent from an untouched run rather than emitted with empty data.

Hashing began as a way to file things: a short number computed from a key, used to pick a drawer. Cryptography wanted more, a digest that nobody could match with a second message, and in 1979 Ralph Merkle and Ivan Damgard independently showed how to build one from a compression function on fixed blocks: pad the message, chain the blocks, and the block function's collision resistance carries over to any length. MD5 and SHA-1 followed that design and were broken in the 2000s; SHA-2 still uses it, and the stage is it at toy size.

1979Ralph Merkle and Ivan Damgard - Independently describe the construction that turns a fixed-size compression function into a hash of any length, with the length appended so that no two messages of different lengths can pad alike.source
1991Ron Rivest - Publishes MD5, a 128-bit Merkle-Damgard hash that becomes the default fingerprint for files and passwords for over a decade.source
1995NSA and NIST - Publish SHA-1, 160 bits, the hash behind early TLS, Git, and most signatures of the following twenty years.source
2004Wang Xiaoyun and colleagues - Find collisions in MD5 by hand-tuned differential paths, and in 2005 show SHA-1 is far weaker than its size; both are retired from signatures.source
2015NIST - Standardises SHA-3, the Keccak sponge, a design that absorbs the message into a wide state without Merkle-Damgard chaining, as a hedge against the attacks on the old shape.source
2017Google and CWI Amsterdam - Publish SHAttered, two PDF files with the same SHA-1 digest, after about nine quintillion compressions; browsers stop accepting SHA-1 certificates.source

Used today

Git and content addressing - Every commit, tree, and file in Git is named by the SHA-1 of its contents, so a changed byte anywhere changes every name above it.
Signatures and certificates - A signature is made over the digest of a document rather than the document, which is why a collision in the hash breaks the signature; the signature lesson builds this.
Downloads and passwords - A published digest lets anyone check a download arrived intact, and the next lesson stores passwords as salted, stretched digests so a stolen database does not give them up.

message

flip bit5

rounds4

digest: 43d69476
tampered: a8e3d715
flipped: 17 of 32
intact: no, detected

toy-hash.ts

import type { Tracer } from "../trace";/** The state and every word are 32 bits, so a digest is eight hex digits and a bit row fits a grid. */export const WORD_BITS = 32;export const BLOCK_BYTES = 4;export const DEFAULT_ROUNDS = 4;export const MAX_ROUNDS = 8;/** Messages this short keep the trace to a few blocks per digest. */export const MAX_MESSAGE_BYTES = 32;/** The starting state: the first 32 bits of the fractional part of the square root of 2, as SHA-256 begins. */export const IV = 0x6a09e667;export interface HashDigest {  value: number;  hex: string;  blocks: number;  /** The state after each block, the digest last. */  states: number[];}export interface Avalanche {  hexA: string;  hexB: string;  /** Output bits that differ. */  flipped: number;  of: number;  ratio: number;}export interface HashRun {  original: HashDigest;  /** The digest of the tampered bytes, or null when nothing was tampered. */  tampered: HashDigest | null;  tamperAt: number;  flipBit: number;  avalanche: Avalanche | null;  /** The digest the receiver computes matches the one sent. */  intact: boolean;}const MASK16 = 0xffff;const rotl16 = (half: number, n: number): number => ((half << n) | (half >>> (16 - n))) & MASK16;const rotr16 = (half: number, n: number): number => ((half >>> n) | (half << (16 - n))) & MASK16;/** * A toy cryptographic hash in the Merkle-Damgard shape: the message is * padded with a 1 bit, zeros, and its length, cut into 32-bit words, * and each word is absorbed into a 32-bit state by a compression * function that mixes for a few rounds and adds the previous state * back (Davies-Meyer). The round is Speck's: split the word in two * halves, rotate, add, xor, rotate, xor, with a constant per round, * so one round moves a flipped bit to a few neighbours and four rounds * spread it over the whole word. The digest is the final state. The * properties a real hash is trusted for, that no one can find two * messages with one digest or a message for a given digest, are * beyond a 32-bit toy by design: a few billion guesses find anything. * What it does show is the avalanche, the padding, and why a digest * fingerprints a message. * * Time: O(n) rounds for n message words. Space: O(n) for the padded message. */export class ToyHash {  constructor(    private readonly tracer?: Tracer,    readonly rounds: number = DEFAULT_ROUNDS,  ) {    if (!Number.isInteger(rounds) || rounds < 1 || rounds > MAX_ROUNDS) throw new RangeError(`rounds must be a whole number from 1 to ${MAX_ROUNDS}, got ${rounds}`);  }  /** The low byte of each character. */  static bytes(text: string): number[] {    return Array.from(text, (c) => c.charCodeAt(0) & 0xff);  }  /** Eight hex digits. */  static hex(word: number): string {    return (word >>> 0).toString(16).padStart(8, "0");  }  /** How many bits of a 32-bit word are 1. */  static popcount(word: number): number {    let n = word >>> 0;    let count = 0;    while (n !== 0) {      count += n & 1;      n >>>= 1;    }    return count;  }  /** Merkle-Damgard strengthening: a 1 bit (0x80), zeros to a word boundary, then the length in bytes as a final word. */  pad(bytes: readonly number[]): number[] {    if (bytes.length > MAX_MESSAGE_BYTES) throw new RangeError(`at most ${MAX_MESSAGE_BYTES} bytes, got ${bytes.length}`);    const padded = [...bytes, 0x80];    while (padded.length % BLOCK_BYTES !== 0) padded.push(0);    const length = bytes.length;    padded.push((length >>> 24) & 0xff, (length >>> 16) & 0xff, (length >>> 8) & 0xff, length & 0xff);    // ▸ append a 1 bit, zeros to a word boundary, and the length    this.tracer?.emit("pad", { bytes: bytes.length, padded: padded.length, blocks: padded.length / BLOCK_BYTES, lengthWord: ToyHash.hex(length) });    return padded;  }  /** One block into the state: xor the word in, mix for the rounds, then add the incoming state back. */  compress(state: number, word: number, block: number): number {    const stateIn = state >>> 0;    let x = ((stateIn ^ word) >>> 16) & MASK16;    let leftHalf = ((stateIn ^ word) >>> 16) & MASK16;    let y = (stateIn ^ word) & MASK16;    let rightHalf = (stateIn ^ word) & MASK16;    // ▸ xor the next word into the state and split it in two halves    this.tracer?.emit("absorb", { block, word, wordHex: ToyHash.hex(word), stateIn: ToyHash.hex(stateIn) });    for (let round = 0; round < this.rounds; round++) {      const before = ((x << 16) | y) >>> 0;      const before = ((leftHalf << 16) | rightHalf) >>> 0;      x = ((rotr16(x, 7) + y) & MASK16) ^ ((0x9e37 * (round + 1) + 0x79b9) & MASK16);      leftHalf = ((rotr16(leftHalf, 7) + rightHalf) & MASK16) ^ ((0x9e37 * (round + 1) + 0x79b9) & MASK16);      y = rotl16(y, 2) ^ x;      rightHalf = rotl16(rightHalf, 2) ^ leftHalf;      const after = ((x << 16) | y) >>> 0;      const after = ((leftHalf << 16) | rightHalf) >>> 0;      // ▸ rotate, add, xor, rotate, xor: one round moves a flipped bit a little further      this.tracer?.emit("round", { block, round, before, after });    }    const mixed = ((x << 16) | y) >>> 0;    const mixed = ((leftHalf << 16) | rightHalf) >>> 0;    const stateOut = (mixed + stateIn) >>> 0;    // ▸ add the state the block started from: the next block starts here    this.tracer?.emit("block", { block, stateOut, stateOutHex: ToyHash.hex(stateOut) });    return stateOut;  }  /** The digest of a byte string: pad, then absorb each word in turn. */  digest(bytes: readonly number[]): HashDigest {    const padded = this.pad(bytes);    const states: number[] = [];    let state = IV;    for (let block = 0; block * BLOCK_BYTES < padded.length; block++) {      const at = block * BLOCK_BYTES;      const word = ((padded[at]! << 24) | (padded[at + 1]! << 16) | (padded[at + 2]! << 8) | padded[at + 3]!) >>> 0;      state = this.compress(state, word, block);      states.push(state);    }    const hex = ToyHash.hex(state);    // ▸ the state after the last block is the digest    this.tracer?.emit("digest", { hex, value: state, blocks: states.length });    return { value: state, hex, blocks: states.length, states };  }  /** The digest of a text's bytes. */  hash(text: string): HashDigest {    return this.digest(ToyHash.bytes(text));  }  /** The bytes with one bit of one byte inverted. */  flip(bytes: readonly number[], index: number, bit: number): number[] {    if (index < 0 || index >= bytes.length) throw new RangeError(`no byte at ${index}`);    if (!Number.isInteger(bit) || bit < 0 || bit > 7) throw new RangeError(`a byte has bits 0 to 7, got ${bit}`);    const out = [...bytes];    const before = out[index]!;    out[index] = before ^ (1 << bit);    // ▸ invert one bit of one byte of the message    this.tracer?.emit("tamper", { index, bit, before, after: out[index] });    return out;  }  /** How many of the 32 digest bits two digests differ in. */  compare(a: HashDigest, b: HashDigest): Avalanche {    const flipped = ToyHash.popcount(a.value ^ b.value);    const avalanche = { hexA: a.hex, hexB: b.hex, flipped, of: WORD_BITS, ratio: flipped / WORD_BITS };    // ▸ count the digest bits that changed: about half, if the mixing is good    this.tracer?.emit("diff", avalanche);    return avalanche;  }  /** Digest the text, then invert one bit of one byte if asked (tamperAt below 0 leaves it alone), digest again, and count the difference. */  run(text: string, tamperAt: number, flipBit: number): HashRun {    const bytes = ToyHash.bytes(text);    const original = this.digest(bytes);    if (tamperAt < 0 || tamperAt >= bytes.length) return { original, tampered: null, tamperAt: -1, flipBit, avalanche: null, intact: true };    const tampered = this.digest(this.flip(bytes, tamperAt, flipBit));    const avalanche = this.compare(original, tampered);    return { original, tampered, tamperAt, flipBit, avalanche, intact: tampered.value === original.value };  }}

hex =: 43d69476
flipped =: 17
intact =: no

Digest 43d69476; after one flipped bit, a8e3d715, 17 bits apart. Anyone holding the first digest can see the message was changed.

import type { Tracer } from "../trace";/** The state and every word are 32 bits, so a digest is eight hex digits and a bit row fits a grid. */export const WORD_BITS = 32;export const BLOCK_BYTES = 4;export const DEFAULT_ROUNDS = 4;export const MAX_ROUNDS = 8;/** Messages this short keep the trace to a few blocks per digest. */export const MAX_MESSAGE_BYTES = 32;/** The starting state: the first 32 bits of the fractional part of the square root of 2, as SHA-256 begins. */export const IV = 0x6a09e667;export interface HashDigest { value: number; hex: string; blocks: number; /** The state after each block, the digest last. */ states: number[];}export interface Avalanche { hexA: string; hexB: string; /** Output bits that differ. */ flipped: number; of: number; ratio: number;}export interface HashRun { original: HashDigest; /** The digest of the tampered bytes, or null when nothing was tampered. */ tampered: HashDigest | null; tamperAt: number; flipBit: number; avalanche: Avalanche | null; /** The digest the receiver computes matches the one sent. */ intact: boolean;}const MASK16 = 0xffff;const rotl16 = (half: number, n: number): number => ((half << n) | (half >>> (16 - n))) & MASK16;const rotr16 = (half: number, n: number): number => ((half >>> n) | (half << (16 - n))) & MASK16;/** * A toy cryptographic hash in the Merkle-Damgard shape: the message is * padded with a 1 bit, zeros, and its length, cut into 32-bit words, * and each word is absorbed into a 32-bit state by a compression * function that mixes for a few rounds and adds the previous state * back (Davies-Meyer). The round is Speck's: split the word in two * halves, rotate, add, xor, rotate, xor, with a constant per round, * so one round moves a flipped bit to a few neighbours and four rounds * spread it over the whole word. The digest is the final state. The * properties a real hash is trusted for, that no one can find two * messages with one digest or a message for a given digest, are * beyond a 32-bit toy by design: a few billion guesses find anything. * What it does show is the avalanche, the padding, and why a digest * fingerprints a message. * * Time: O(n) rounds for n message words. Space: O(n) for the padded message. */export class ToyHash { constructor( private readonly tracer?: Tracer, readonly rounds: number = DEFAULT_ROUNDS, ) { if (!Number.isInteger(rounds) || rounds < 1 || rounds > MAX_ROUNDS) throw new RangeError(`rounds must be a whole number from 1 to ${MAX_ROUNDS}, got ${rounds}`); } /** The low byte of each character. */ static bytes(text: string): number[] { return Array.from(text, (c) => c.charCodeAt(0) & 0xff); } /** Eight hex digits. */ static hex(word: number): string { return (word >>> 0).toString(16).padStart(8, "0"); } /** How many bits of a 32-bit word are 1. */ static popcount(word: number): number { let n = word >>> 0; let count = 0; while (n !== 0) { count += n & 1; n >>>= 1; } return count; } /** Merkle-Damgard strengthening: a 1 bit (0x80), zeros to a word boundary, then the length in bytes as a final word. */ pad(bytes: readonly number[]): number[] { if (bytes.length > MAX_MESSAGE_BYTES) throw new RangeError(`at most ${MAX_MESSAGE_BYTES} bytes, got ${bytes.length}`); const padded = [...bytes, 0x80]; while (padded.length % BLOCK_BYTES !== 0) padded.push(0); const length = bytes.length; padded.push((length >>> 24) & 0xff, (length >>> 16) & 0xff, (length >>> 8) & 0xff, length & 0xff); // ▸ append a 1 bit, zeros to a word boundary, and the length this.tracer?.emit("pad", { bytes: bytes.length, padded: padded.length, blocks: padded.length / BLOCK_BYTES, lengthWord: ToyHash.hex(length) }); return padded; } /** One block into the state: xor the word in, mix for the rounds, then add the incoming state back. */ compress(state: number, word: number, block: number): number { const stateIn = state >>> 0; let x = ((stateIn ^ word) >>> 16) & MASK16; let leftHalf = ((stateIn ^ word) >>> 16) & MASK16; let y = (stateIn ^ word) & MASK16; let rightHalf = (stateIn ^ word) & MASK16; // ▸ xor the next word into the state and split it in two halves this.tracer?.emit("absorb", { block, word, wordHex: ToyHash.hex(word), stateIn: ToyHash.hex(stateIn) }); for (let round = 0; round < this.rounds; round++) { const before = ((x << 16) | y) >>> 0; const before = ((leftHalf << 16) | rightHalf) >>> 0; x = ((rotr16(x, 7) + y) & MASK16) ^ ((0x9e37 * (round + 1) + 0x79b9) & MASK16); leftHalf = ((rotr16(leftHalf, 7) + rightHalf) & MASK16) ^ ((0x9e37 * (round + 1) + 0x79b9) & MASK16); y = rotl16(y, 2) ^ x; rightHalf = rotl16(rightHalf, 2) ^ leftHalf; const after = ((x << 16) | y) >>> 0; const after = ((leftHalf << 16) | rightHalf) >>> 0; // ▸ rotate, add, xor, rotate, xor: one round moves a flipped bit a little further this.tracer?.emit("round", { block, round, before, after }); } const mixed = ((x << 16) | y) >>> 0; const mixed = ((leftHalf << 16) | rightHalf) >>> 0; const stateOut = (mixed + stateIn) >>> 0; // ▸ add the state the block started from: the next block starts here this.tracer?.emit("block", { block, stateOut, stateOutHex: ToyHash.hex(stateOut) }); return stateOut; } /** The digest of a byte string: pad, then absorb each word in turn. */ digest(bytes: readonly number[]): HashDigest { const padded = this.pad(bytes); const states: number[] = []; let state = IV; for (let block = 0; block * BLOCK_BYTES < padded.length; block++) { const at = block * BLOCK_BYTES; const word = ((padded[at]! << 24) | (padded[at + 1]! << 16) | (padded[at + 2]! << 8) | padded[at + 3]!) >>> 0; state = this.compress(state, word, block); states.push(state); } const hex = ToyHash.hex(state); // ▸ the state after the last block is the digest this.tracer?.emit("digest", { hex, value: state, blocks: states.length }); return { value: state, hex, blocks: states.length, states }; } /** The digest of a text's bytes. */ hash(text: string): HashDigest { return this.digest(ToyHash.bytes(text)); } /** The bytes with one bit of one byte inverted. */ flip(bytes: readonly number[], index: number, bit: number): number[] { if (index < 0 || index >= bytes.length) throw new RangeError(`no byte at ${index}`); if (!Number.isInteger(bit) || bit < 0 || bit > 7) throw new RangeError(`a byte has bits 0 to 7, got ${bit}`); const out = [...bytes]; const before = out[index]!; out[index] = before ^ (1 << bit); // ▸ invert one bit of one byte of the message this.tracer?.emit("tamper", { index, bit, before, after: out[index] }); return out; } /** How many of the 32 digest bits two digests differ in. */ compare(a: HashDigest, b: HashDigest): Avalanche { const flipped = ToyHash.popcount(a.value ^ b.value); const avalanche = { hexA: a.hex, hexB: b.hex, flipped, of: WORD_BITS, ratio: flipped / WORD_BITS }; // ▸ count the digest bits that changed: about half, if the mixing is good this.tracer?.emit("diff", avalanche); return avalanche; } /** Digest the text, then invert one bit of one byte if asked (tamperAt below 0 leaves it alone), digest again, and count the difference. */ run(text: string, tamperAt: number, flipBit: number): HashRun { const bytes = ToyHash.bytes(text); const original = this.digest(bytes); if (tamperAt < 0 || tamperAt >= bytes.length) return { original, tampered: null, tamperAt: -1, flipBit, avalanche: null, intact: true }; const tampered = this.digest(this.flip(bytes, tamperAt, flipBit)); const avalanche = this.compare(original, tampered); return { original, tampered, tamperAt, flipBit, avalanche, intact: tampered.value === original.value }; }}