Cairn
algorithms · cryptography · O(n) time, one pass over the input, O(1) space beyond it; a fixed 256-bit output for any input size, with no key and no secret anywhere in the computation

↩ back to Cryptography

SHA-256

This category's first two entries, Diffie–Hellman Key Exchange and RSA Encryption, are both built around a trapdoor: a direction that's cheap to compute and a reverse direction that's believed hard — unless you hold a secret key, in which case the reverse becomes cheap too. SHA-256 has no key and no trapdoor at all. It's a cryptographic hash function: one fixed, public, keyless computation that turns any input, from one byte to one terabyte, into exactly 256 bits — deterministic (same input, same output, always), one-way (no known way back from output to input, for anyone, key or no key), and so sensitive to its input that flipping a single bit anywhere changes roughly half the output bits. Merkle Tree already leans on real SHA-256 for every hash in its demo, but reaches for it through the browser's own crypto.subtle — a black box. This page opens that box: the actual bit-rotations, modular additions, and round constants that make up the algorithm, built from nothing but arithmetic, then checked live against the browser's real implementation to prove the two agree.

Try it

Type anything in the box below — the hex digest updates as you type, computed two independent ways: this page's own hand-written implementation (see Reference implementation), and the browser's native crypto.subtle.digest. They're checked against each other on every keystroke.

Click to flip the lowest bit of the last character and see how many of the 256 output bits change.

SHA-256 has no key, but that cuts both ways: anyone who knows the length of a secret prefix — not its contents, just how many bytes long it is — can extend a hash of secret‖message into a valid hash of secret‖message‖forged-data, without ever learning the secret. That's not a bug in this page's implementation; it's a structural property of how SHA-256 (and MD5, and SHA-1) process input in blocks, called a length-extension attack. The demo below runs it for real.

Server-side setup, simulating a naive token = SHA-256(secret ‖ request) scheme: a 32-byte secret (hidden — the attacker below never reads it directly) is prepended to a request string, then hashed.

Attacker's view — knows only the published token above, the request string (it travels in the open), and the secret's length (a common leak: fixed-width keys, a cookie's declared size, a protocol spec). Never sees the secret itself.

Why it works

SHA-256 is a Merkle–Damgård construction. The message is padded — a single 1 bit, then enough 0 bits, then the original message's length as a 64-bit big-endian integer — until its length is a multiple of 512 bits (64 bytes), guaranteeing at least one full block of padding exists even when the message was already block-aligned. The padded message is cut into 512-bit blocks and run one at a time through a compression function that mixes a block into a running 256-bit state (eight 32-bit words, initialized to fixed constants derived from the fractional parts of the square roots of the first eight primes). Each block's 16 words are expanded to 64 via two mixing functions (σ₀, σ₁, each a mix of right-rotations and a right-shift), then fed through 64 rounds that each rotate, XOR, and add (mod 2³²) the eight working variables together with a round constant (the fractional parts of the cube roots of the first 64 primes) and the schedule word for that round. The output state after the last block is the digest — there's no separate "finalize" step with secret material, which is exactly the property the length-extension attack below exploits.

The avalanche effect — flip one input bit, change roughly half the output bits — isn't a separate mechanism, it's what 64 rounds of rotation and mixing do to a single-bit difference: each round spreads that difference into more bit positions than the round before, and by round 64 the influence has saturated the whole 256-bit state. No bit of the output correlates with any single bit of the input in a way that's cheaper to exploit than trying inputs directly — the whole basis for treating the digest as a fingerprint of the message rather than a shuffled copy of it.

Reference implementation

The exact code both demos above call. rotr is a 32-bit right-rotation; everything else follows FIPS 180-4 directly — the padding, the 64-round message schedule expansion, and the compression loop with the standard Ch/Maj choice/majority functions:

const K = [ /* 64 round constants — cube roots of the first 64 primes, fractional part */
  0x428a2f98, 0x71374491, /* … */ 0xbef9a3f7, 0xc67178f2
];
const H0 = [ /* initial state — square roots of the first 8 primes, fractional part */
  0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
  0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
];

function rotr(x, n) { return ((x >>> n) | (x << (32 - n))) >>> 0; }

function processBlocks(padded, H) {           // padded: Uint8Array, length a multiple of 64
  H = H.slice();
  for (let offset = 0; offset < padded.length; offset += 64) {
    const W = new Array(64);
    for (let t = 0; t < 16; t++) W[t] = readUInt32BE(padded, offset + t * 4);
    for (let t = 16; t < 64; t++) {
      const s0 = rotr(W[t-15], 7) ^ rotr(W[t-15], 18) ^ (W[t-15] >>> 3);
      const s1 = rotr(W[t-2], 17) ^ rotr(W[t-2], 19) ^ (W[t-2] >>> 10);
      W[t] = (W[t-16] + s0 + W[t-7] + s1) >>> 0;
    }
    let [a, b, c, d, e, f, g, h] = H;
    for (let t = 0; t < 64; t++) {
      const S1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25);
      const ch = (e & f) ^ (~e & g);
      const temp1 = (h + S1 + ch + K[t] + W[t]) >>> 0;
      const S0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22);
      const maj = (a & b) ^ (a & c) ^ (b & c);
      const temp2 = (S0 + maj) >>> 0;
      h = g; g = f; f = e; e = (d + temp1) >>> 0;
      d = c; c = b; b = a; a = (temp2 + temp1) >>> 0;
    }
    H[0]=(H[0]+a)>>>0; H[1]=(H[1]+b)>>>0; H[2]=(H[2]+c)>>>0; H[3]=(H[3]+d)>>>0;
    H[4]=(H[4]+e)>>>0; H[5]=(H[5]+f)>>>0; H[6]=(H[6]+g)>>>0; H[7]=(H[7]+h)>>>0;
  }
  return H;
}

function sha256Hex(messageBytes) {
  return processBlocks(padMessage(messageBytes, messageBytes.length * 8), H0)
    .map(x => (x >>> 0).toString(16).padStart(8, '0')).join('');
}

Verified against four of the standard published test vectors before it ever ran in the demo above — SHA-256("") is e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855, and SHA-256("abc") is ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad, both matching this exact implementation and Node's own crypto.createHash('sha256') exactly, along with every block- boundary edge case from 55 to 65 input bytes (where the padding's extra block either is or isn't needed) and a multi-byte UTF-8 string.

Pitfalls

Length extension is structural, not a bug — demonstrated live above, not just asserted. Because the digest is the final internal state with no secret-dependent finishing step, anyone who knows a hash H = SHA-256(secret‖message) and the byte-length of secret can seed a fresh compression run with H's own 8 words as if they were a starting state, feed it the standard padding SHA-256 would have appended after secret‖message followed by whatever extra bytes they want, and get out a value that is provably SHA-256(secret‖message‖glue‖extra) — without ever reading secret. The demo's forged token and the real, directly-computed SHA-256(secret‖message‖glue‖extra) (revealed only so the match can be checked, exactly the way RSA Encryption's page reveals its private exponent only for display, never to Eve) are always identical. This is exactly why SHA-256(secret‖message) is an unsafe way to authenticate a message: real systems use HMAC, a nested construction built specifically to block this attack — the genuinely different construction this page's "Why it works" section deliberately stops short of.

Fast is a feature for integrity, a liability for secrets. SHA-256 is designed to hash gigabytes quickly — exactly what Merkle Tree needs for checking large datasets haven't been tampered with. That same speed makes it a bad fit for hashing anything an attacker might try to guess, like a password: a bare SHA-256 lets an attacker test billions of candidate passwords per second on ordinary hardware, since each guess costs one fast hash and nothing more. There's no salt in the construction either — the same password always produces the same digest, which is what makes precomputed rainbow-table lookups work at all. Real password storage uses deliberately slow, salted key-derivation functions — bcrypt, Argon2, or PBKDF2 — that cost milliseconds per guess instead of nanoseconds, a difference of six orders of magnitude that turns a feasible attack back into an infeasible one. All three are named here for the same reason; PBKDF2's own page chains this page's own HMAC-SHA256 and measures the slowdown live, and bcrypt rebuilds a few kilobytes of internal state from scratch on every guess instead. Argon2 itself remains unbuilt here, though the hash function it uses internally, BLAKE2b, now is.

Complexity

Time: O(n) — one pass over the padded input, a fixed amount of work (64 rounds of constant-time bit operations) per 512-bit block. Space: O(1) beyond the input itself: an 8-word running state and a 64-word message schedule per block, both reused block to block, regardless of how long the message is. Security: finding any input that hashes to a given 256-bit output (preimage resistance) has no known method faster than roughly 2²⁵⁶ guesses; finding any two inputs that collide with each other (collision resistance) is cheaper by the birthday bound, around 2¹²⁸ — the same square-root relationship Lower Bounds derives for the general birthday-paradox argument. Cryptanalysis has found real weaknesses in reduced-round variants of the compression function (fewer than the full 64 rounds), but no attack against full SHA-256 beats generic brute force as of this writing — unlike factoring or the discrete log, which RSA and Diffie–Hellman both rest on, there isn't even a believed-hard mathematical problem underneath SHA-256's security — just the absence, so far, of any shortcut through this specific sequence of bit operations.