Introduction

Every time your browser validates a download, a password manager stores a credential, or a blockchain commits a block, it calls a hash function — an algorithm that crushes an arbitrarily long message down to a fixed-length digest. SHA-256 produces 256 bits whether the input is a single byte or the entire text of Wikipedia.

That sounds magical. How do you accept any length of input but always produce the same length of output? The answer, published independently by Ralph Merkle (1979) and Ivan Damgård (1989), is disarmingly simple: break the message into fixed-size blocks and chain them through a small, fixed-length compression function.

The Merkle–Damgård construction does not invent new mathematics — it is an architecture. Given a compression function ff that takes a fixed-size chaining value and a fixed-size block and produces a new chaining value, the construction shows how to build a full hash function from it. The proof of security is elegant: if the compression function is collision-resistant, so is the resulting hash.

That elegant proof, however, comes with a hidden trap — the length-extension attack — which SHA-3 was specifically designed to avoid. Understanding Merkle–Damgård means understanding both the insight and the flaw.

Watch the Chain Build

Type a message below, then click Hash it to see the Merkle–Damgård construction in action. The message is padded and split into 8-character blocks; each block is combined with the running chaining value through a toy compression function.

<div class="controls">
  <label for="msg">Message:</label>
  <input id="msg" type="text" value="Hello, world!" autocomplete="off" />
  <button id="hashBtn" type="button">Hash it</button>
  <button id="resetBtn" type="button" class="ghost">Clear</button>
</div>
<div id="chain" class="chain"></div>
<div id="digest-row" class="digest-row hidden">
  <span class="digest-label">Digest:</span>
  <span id="digest-val" class="digest-val"></span>
</div>
<hr class="divider" />
<div class="ext-section">
  <div class="ext-title">Length-Extension Attack</div>
  <p class="ext-desc">
    An attacker who knows only the <b>digest</b> and the <b>original message length</b> can compute a valid hash for <em>message ‖ padding ‖ extra</em> — without knowing the message.
  </p>
  <label for="extra">Extra data to append:</label>
  <input id="extra" type="text" value="&admin=true" autocomplete="off" />
  <button id="extBtn" type="button" class="ext-btn">Run length-extension attack</button>
  <div id="ext-result" class="ext-result hidden"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { font-weight: 600; white-space: nowrap; }
input { flex: 1; min-width: 140px; padding: .35rem .6rem; border: 1px solid #bbb; border-radius: 6px; font-size: 14px; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border-radius: 6px; cursor: pointer; border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
button.ext-btn { background: #9b2226; border-color: #9b2226; color: #fff; margin-top: .4rem; }
.chain { display: flex; flex-wrap: wrap; align-items: center; gap: 4px; margin: .5rem 0; }
.block { display: flex; flex-direction: column; align-items: center; gap: 2px; }
.block-label { font-size: 10px; color: #666; }
.block-box { width: 72px; min-height: 40px; display: flex; align-items: center; justify-content: center;
             border-radius: 7px; font: 700 11px ui-monospace, monospace; padding: 4px 3px; text-align: center; word-break: break-all; }
.iv-box { background: #e8f4f8; border: 1.5px solid #90cce8; color: #1d6a8a; }
.state-box { background: #eef1f8; border: 1.5px dashed #6c8ebf; color: #2d4585; }
.data-box { background: #fff3cd; border: 1.5px solid #ffc107; color: #664d03; }
.final-box { background: #d1e7dd; border: 2px solid #198754; color: #0a3622; font-size: 10px; }
.arrow { font-size: 18px; color: #888; align-self: center; margin-bottom: 14px; }
.compress { display: flex; flex-direction: column; align-items: center; gap: 2px; margin-bottom: 14px; }
.compress-fn { background: #f0e6ff; border: 1.5px solid #9b59b6; color: #5b2c8c;
               font: 700 11px ui-monospace; padding: 3px 7px; border-radius: 5px; white-space: nowrap; }
.step-row { display: flex; align-items: flex-end; gap: 4px; }
.digest-row { display: flex; align-items: center; gap: .6rem; margin: .4rem 0 .6rem; }
.digest-label { font-weight: 700; color: #0a3622; }
.digest-val { font: 700 13px ui-monospace; background: #d1e7dd; border: 2px solid #198754;
              color: #0a3622; padding: 3px 8px; border-radius: 6px; word-break: break-all; }
.hidden { display: none; }
.divider { border: none; border-top: 1px solid #ddd; margin: .8rem 0; }
.ext-section { background: #fff5f5; border: 1.5px solid #f5a0a0; border-radius: 8px; padding: .7rem .9rem; }
.ext-title { font-weight: 700; color: #9b2226; margin-bottom: .3rem; font-size: 1rem; }
.ext-desc { font-size: 12.5px; color: #444; margin: 0 0 .5rem; line-height: 1.45; }
.ext-result { margin-top: .6rem; font-size: 12.5px; line-height: 1.55; }
.ext-result .mono { font: 700 11px ui-monospace; background: #fce8e8; padding: 2px 5px; border-radius: 4px; word-break: break-all; }
.ext-result .ok { color: #0a7d33; font-weight: 700; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Toy Merkle-Damgard construction for demonstration purposes.
// Uses a simple (non-cryptographic) compression function that is deterministic
// and visually trackable. Real SHA-256 uses the same chaining architecture.

const BLOCK_SIZE = 8; // characters per block (toy block size)
const IV = 0x5A4B3C2D; // arbitrary initialization vector (32-bit)
const MOD = 0x100000000; // 2^32

// Toy compression function: f(state, block) -> new_state
// Uses mixing shifts similar in spirit to real hash compression rounds.
function compress(state, blockStr) {
  let h = state >>> 0;
  for (let i = 0; i < blockStr.length; i++) {
    const c = blockStr.charCodeAt(i);
    h = (Math.imul((h ^ c), 0x9e3779b9) + ((h << 6) | (h >>> 26))) >>> 0;
    h = (h ^ (h >>> 16)) >>> 0;
  }
  // Mix in block length as extra diffusion
  h = (Math.imul(h ^ blockStr.length, 0x85ebca6b)) >>> 0;
  h = (h ^ (h >>> 13)) >>> 0;
  return h;
}

function toHex(n) {
  return ('00000000' + (n >>> 0).toString(16)).slice(-8);
}

// Merkle-Damgard padding: append 0x80, then zero bytes, then 8-byte length
// Here simplified to character-level for the toy version.
function padMessage(msg) {
  const bytes = [];
  for (let i = 0; i < msg.length; i++) bytes.push(msg.charCodeAt(i));
  bytes.push(0x80);
  // Pad to multiple of BLOCK_SIZE (in bytes)
  while ((bytes.length % BLOCK_SIZE) !== (BLOCK_SIZE - 1)) bytes.push(0x00);
  // Append 1-byte length indicator (toy: just the length mod 256)
  bytes.push(msg.length & 0xff);
  return bytes;
}

function bytesToBlocks(bytes) {
  const blocks = [];
  for (let i = 0; i < bytes.length; i += BLOCK_SIZE) {
    const chunk = bytes.slice(i, i + BLOCK_SIZE);
    blocks.push(chunk);
  }
  return blocks;
}

function blockToDisplayStr(chunk) {
  return chunk.map(b => {
    if (b >= 0x20 && b < 0x7f) return String.fromCharCode(b);
    return '·';
  }).join('');
}

function hashBlocks(blocks, startState) {
  let state = startState >>> 0;
  const states = [state];
  for (const chunk of blocks) {
    const blockStr = chunk.map(b => String.fromCharCode(b)).join('');
    state = compress(state, blockStr);
    states.push(state);
  }
  return states;
}

function renderChain(blocks, states, highlightFinal) {
  const chain = document.getElementById('chain');
  chain.innerHTML = '';

  function makeBlock(label, text, cls) {
    const wrap = document.createElement('div');
    wrap.className = 'block';
    const lbl = document.createElement('div');
    lbl.className = 'block-label';
    lbl.textContent = label;
    const box = document.createElement('div');
    box.className = 'block-box ' + cls;
    box.textContent = text;
    wrap.appendChild(lbl);
    wrap.appendChild(box);
    return wrap;
  }

  function makeArrow() {
    const d = document.createElement('div');
    d.className = 'arrow';
    d.textContent = '→';
    return d;
  }

  // IV block
  chain.appendChild(makeBlock('IV', toHex(states[0]), 'iv-box'));

  for (let i = 0; i < blocks.length; i++) {
    const chunk = blocks[i];
    const displayStr = blockToDisplayStr(chunk);

    // Step: arrow + compress(state, block) -> new state
    const stepRow = document.createElement('div');
    stepRow.className = 'step-row';

    // arrow into compress
    chain.appendChild(makeArrow());

    // data block (above the fn box would be ideal, but inline for simplicity)
    const compressWrap = document.createElement('div');
    compressWrap.className = 'compress';
    const dataBox = makeBlock(fmt('block %i%%v%', { i: i, v: 1 }), displayStr, 'data-box');
    const fnBox = document.createElement('div');
    fnBox.className = 'compress-fn';
    fnBox.textContent = 'f( state, block )';
    compressWrap.appendChild(dataBox);
    compressWrap.appendChild(fnBox);
    chain.appendChild(compressWrap);

    chain.appendChild(makeArrow());

    // new state
    const isFinal = (i === blocks.length - 1);
    const stateBox = makeBlock(isFinal ? 'digest' : fmt('state %i%%v%', { i: i, v: 1 }),
      toHex(states[i + 1]),
      isFinal && highlightFinal ? 'final-box' : 'state-box');
    chain.appendChild(stateBox);
  }
}

let lastMsg = '';
let lastDigest = 0;
let lastBlocks = [];
let lastPaddedLen = 0;

function runHash() {
  const msg = document.getElementById('msg').value;
  lastMsg = msg;
  const bytes = padMessage(msg);
  lastPaddedLen = bytes.length;
  const blocks = bytesToBlocks(bytes);
  lastBlocks = blocks;
  const states = hashBlocks(blocks, IV);
  lastDigest = states[states.length - 1];

  renderChain(blocks, states, true);

  const digestRow = document.getElementById('digest-row');
  document.getElementById('digest-val').textContent = toHex(lastDigest);
  digestRow.classList.remove('hidden');

  document.getElementById('ext-result').classList.add('hidden');
}

function runExtension() {
  if (!lastMsg && lastDigest === 0) {
    alert('Hash a message first!');
    return;
  }
  const extra = document.getElementById('extra').value;
  if (!extra) { alert('Enter extra data to append.'); return; }

  // The attacker knows: digest (= internal state after hashing msg+padding)
  // and the padded length of the original message.
  // They resume the chain from state=digest, feeding extra data.

  const extraBytes = [];
  for (let i = 0; i < extra.length; i++) extraBytes.push(extra.charCodeAt(i));
  // Pad the extra data
  const paddedExtra = padMessage(extra);
  const extraBlocks = bytesToBlocks(paddedExtra);
  const statesExt = hashBlocks(extraBlocks, lastDigest);
  const extDigest = statesExt[statesExt.length - 1];

  // Now verify: compute honest hash of (originalBytes + padding + extraBytes + padding)
  const origBytes = padMessage(lastMsg);
  const combined = [...origBytes, ...paddedExtra];
  const combinedBlocks = bytesToBlocks(combined);
  const statesCombined = hashBlocks(combinedBlocks, IV);
  const honestDigest = statesCombined[statesCombined.length - 1];

  const match = extDigest === honestDigest;

  const extResult = document.getElementById('ext-result');
  extResult.classList.remove('hidden');
  extResult.innerHTML =
    fmt('<b>Attacker starts from digest</b> <span class="mono">%toHex%</span>, appends <span class="mono">%extra%</span>.<br>Extended digest: <span class="mono">%toHex2%</span><br>Honest digest of (msg ‖ pad ‖ extra): <span class="mono">%toHex3%</span><br>%v%', { toHex: toHex(lastDigest), extra: extra, toHex2: toHex(extDigest), toHex3: toHex(honestDigest), v: match
      ? '<span class="ok">✓ They match! The attacker forged a valid hash without knowing the original message.</span>'
      : '<span style="color:#9b2226">✗ Mismatch (implementation error — check padding).</span>' });

  // Log for node verification
  console.log('lengthExt:orig=' + toHex(lastDigest) + ' ext=' + toHex(extDigest) + ' honest=' + toHex(honestDigest) + ' match=' + match);
}

document.getElementById('hashBtn').addEventListener('click', runHash);
document.getElementById('resetBtn').addEventListener('click', () => {
  document.getElementById('msg').value = '';
  document.getElementById('chain').innerHTML = '';
  document.getElementById('digest-row').classList.add('hidden');
  document.getElementById('ext-result').classList.add('hidden');
  lastMsg = ''; lastDigest = 0; lastBlocks = []; lastPaddedLen = 0;
});
document.getElementById('extBtn').addEventListener('click', runExtension);

// Auto-hash on load
runHash();
Result
Console

Notice the structure: the IV (initialization vector) starts the chain, each block updates it, and the final value is the digest. Now try the Length-extension attack: the demo shows how an attacker who only knows the final digest and the message length can compute a valid hash for message + padding + extra_data — without knowing what the original message said.

The Real Complexity

The construction comes with a security reduction — a mathematical proof that any collision in the hash function implies a collision in the underlying compression function. In other words:

  • Collision resistance is inherited. If you trust ff, you can trust the full hash.
  • Preimage resistance is also inherited under similar assumptions.

But the design has a structural weakness that no compression-function improvement can fix.

The length-extension attack (proven by Merkle and Damgård themselves): if you know H(m) and the length of mm, you can compute H(m ‖ padding ‖ extra) for any extra — without knowing mm itself. This is because after hashing mm, the internal chaining state is exactly H(m). You simply resume the chain from there.

  • Impact: web APIs that compute HMAC = H(secret ‖ message) naively can be forged. An attacker appends data and produces a valid tag.
  • Broken algorithms: MD5 and SHA-1 are also Merkle–Damgård and equally vulnerable. SHA-256 shares the weakness.
  • Fix 1 — HMAC: compute H(key ⊕ opad ‖ H(key ⊕ ipad ‖ message)) — double hashing breaks the extension path. Standardized in RFC 2104.
  • Fix 2 — SHA-3 (Keccak): uses a sponge construction instead of Merkle–Damgård. The internal state is larger than the output, so the final state is never fully exposed — length extension is impossible by design.

The classification is solved: the construction is fully analyzed, its security is proven conditional on the compression function, and its vulnerability is precisely characterized. See also the related factoring article for how hardness assumptions underpin cryptographic security.

Where It Matters

Virtually every piece of software that performs integrity verification or authentication touches Merkle–Damgård:

  • SHA-256 and SHA-512: the workhorses of TLS, code-signing certificates, and Bitcoin proof-of-work all use Merkle–Damgård with the SHA-2 compression function.
  • MD5 and SHA-1: both Merkle–Damgård designs, now broken for collision resistance (MD5 in 2004, SHA-1 collisions demonstrated in 2017) but still found in legacy systems.
  • HMAC: the standard MAC primitive pairs Merkle–Damgård with a double-hashing envelope to defeat length extension. HMAC-SHA-256 secures JWTs, OAuth signatures, and API authentication.
  • Git commit IDs: historically SHA-1, now migrating to SHA-256 — each commit hash is a Merkle–Damgård digest of the commit contents.
  • Password hashing: bcrypt, scrypt, and Argon2 use Merkle–Damgård internally as a building block for their memory-hard functions.
  • Digital signatures: RSA-PSS and ECDSA sign the hash of a document, not the document itself — the hash is always Merkle–Damgård or its successor.

Understanding the construction lets you reason about which uses are safe (collision-resistance-only tasks like content addressing) and which require the extra protection of HMAC or a sponge (secret-prefix MACs, APIs). See also discrete logarithm for the algebraic hardness that underpins the signature schemes built on top.

Conclusion

Merkle–Damgård is one of those ideas so simple it looks inevitable: chain blocks through a small function, start from a public IV, prove the security reduces to the compression function. That recipe produced SHA-256 and underlies an enormous fraction of the internet's security infrastructure.

Yet the very simplicity that makes the construction elegant is what causes the length-extension flaw. The final chaining state is the hash — and that means anyone who knows the hash can continue the chain. HMAC papers over the crack; SHA-3's sponge eliminates it by design.

The story of Merkle–Damgård is a reminder that cryptographic constructions carry their design assumptions for decades. Choosing an architecture is choosing which attacks you are immune to and which you must defend against forever.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/merkle-damgard/Content licensed under CC BY-NC 4.0.