The SHA Family, in depth: SHA-256 from scratch, Merkle-Damgard and length extension, the fall of SHA-1, the SHA-3 sponge and choosing a hash

What a cryptographic hash promises

A cryptographic hash maps any input to a fixed-size digest and should behave like a random function. Three properties follow. Preimage resistance: given a digest, finding any input with that digest costs about 2ⁿ work for an n-bit hash. Second-preimage resistance: given one input, finding a different one with the same digest also costs about 2ⁿ. Collision resistance: finding any two inputs with the same digest costs about 2^n/2, because of the birthday bound: among 2^n/2 random digests a repeat is likely.

Collision resistance is the property that breaks first, and it is the one signatures rely on: if an attacker can make two documents with the same hash, a signature on the harmless one is valid on the harmful one. That is why a 160-bit hash offers only 80-bit collision security, below modern targets.

Quantum computers change the arithmetic less than people fear. Grover's algorithm would cut preimage search for an n-bit hash to roughly 2^n/2 quantum operations, so SHA-256 keeps about 128-bit preimage security, and no known quantum attack makes collisions practical. Moving to longer digests, such as SHA-384, is a reasonable hedge for long-lived data, but there is no need to abandon SHA-2.

Merkle-Damgard and the padding rule

SHA-1 and SHA-2 use the Merkle-Damgard construction. Pad the message to a whole number of blocks, start from a fixed initial state, and feed blocks one at a time through a compression function that mixes the block into the state. The final state is the digest. If the compression function resists collisions, so does the whole hash, which is why the padding includes the message length.

SHA-256 padding, worked for the 3-byte message 'abc': append the byte 0x80 (a single 1 bit then zeros), then zero bytes until the length is 56 mod 64, then the message length in bits, 24, as a 64-bit big-endian integer. That fills exactly one 64-byte block: 3 message bytes, 0x80, 52 zero bytes and 8 length bytes.

SHA-256 from scratch

Inside, SHA-256 keeps eight 32-bit words. Each 64-byte block is expanded into a schedule of 64 words, and 64 rounds mix them in using additions modulo 2³², rotations, and two bitwise functions: Ch chooses bits from f or g depending on e, and Maj takes the majority of a, b and c. The round constants are the first 32 bits of the fractional parts of the cube roots of the first 64 primes, and the initial state comes from square roots of the first 8: 'nothing up my sleeve' numbers.

import hashlib, struct

K = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
     0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
     0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
     0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
     0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
     0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
     0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
     0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]
H0 = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]
M = 0xFFFFFFFF

def rotr(x, n):
    return ((x >> n) | (x << (32 - n))) & M

def pad(msg):
    zeros = (55 - len(msg)) % 64
    return msg + b"\x80" + b"\x00" * zeros + struct.pack(">Q", 8 * len(msg))

def compress(h, block):
    w = list(struct.unpack(">16I", block))
    for t in range(16, 64):
        s0 = rotr(w[t-15], 7) ^ rotr(w[t-15], 18) ^ (w[t-15] >> 3)
        s1 = rotr(w[t-2], 17) ^ rotr(w[t-2], 19) ^ (w[t-2] >> 10)
        w.append((w[t-16] + s0 + w[t-7] + s1) & M)
    a, b, c, d, e, f, g, hh = h
    for t in range(64):
        t1 = (hh + (rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25))
              + ((e & f) ^ (~e & g)) + K[t] + w[t]) & M
        t2 = ((rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22))
              + ((a & b) ^ (a & c) ^ (b & c))) & M
        a, b, c, d, e, f, g, hh = (t1 + t2) & M, a, b, c, (d + t1) & M, e, f, g
    return [(x + y) & M for x, y in zip(h, [a, b, c, d, e, f, g, hh])]

def sha256(msg):
    h, data = H0, pad(msg)
    for i in range(0, len(data), 64):
        h = compress(h, data[i:i + 64])
    return "".join(f"{x:08x}" for x in h)

for m in [b"", b"abc", b"a" * 1000]:
    assert sha256(m) == hashlib.sha256(m).hexdigest()
print(sha256(b"abc"))  # ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

The final line prints the standard test vector for 'abc'. This code is for understanding only: it is slow and makes no attempt at constant-time behaviour. Use hashlib or your platform's crypto library in real systems.

Length extension, and why HMAC exists

Because the digest is the full chaining state, anyone who knows SHA-256(secret || msg) and the length of the secret can compute SHA-256(secret || msg || glue || extra) without knowing the secret. The 'glue' is the padding the original message received. The attacker loads the digest as the state and keeps compressing. With the compress and pad functions above, the attack is a dozen lines, and it works against the real hashlib output.

A classic victim is an API that signs requests as sha256(key + query). An attacker who sees one signed amount=10&to=alice can append &to=mallory, and a parser that keeps the last duplicate parameter now pays Mallory with a valid tag. Using the functions above:

import os
secret = os.urandom(16)                      # unknown to the attacker
msg = b"amount=10&to=alice"
tag = hashlib.sha256(secret + msg).hexdigest()

# Attacker knows msg, tag and len(secret) == 16
glue = pad(secret + msg)[16 + len(msg):]     # padding bytes only; computable from lengths
extra = b"&to=mallory"
state = [int(tag[i:i + 8], 16) for i in range(0, 64, 8)]
total = 16 + len(msg) + len(glue) + len(extra)
tail = extra + b"\x80" + b"\x00" * ((55 - total) % 64) + struct.pack(">Q", 8 * total)
for i in range(0, len(tail), 64):
    state = compress(state, tail[i:i + 64])
forged = "".join(f"{x:08x}" for x in state)

assert forged == hashlib.sha256(secret + msg + glue + extra).hexdigest()

The attacker calls pad here only for convenience: the glue depends on lengths alone, never on the secret's bytes. Three fixes, in order of preference:

• Use HMAC-SHA-256. HMAC hashes twice with derived inner and outer keys, so the visible output is not a state an attacker can continue from.
• Use a truncated variant such as SHA-512/256 or SHA-384, where the attacker sees only part of the state. SHA-224 truncates just 32 bits, so it offers little protection here.
• Use SHA-3 or a keyed construction built for it, such as KMAC. The sponge never outputs its capacity.

The fall of SHA-1

SHA-1 is the cautionary tale. Theoretical collision attacks well below the 2⁸⁰ birthday bound appeared in 2005. In 2017 the SHAttered team from CWI Amsterdam and Google published two different PDF files with the same SHA-1 digest. In 2020 Leurent and Peyrin published a chosen-prefix collision, the more dangerous kind, where the attacker picks both starting documents, and used it to forge a PGP key certification. NIST has announced that SHA-1 should be phased out completely by the end of 2030.

Git shows how hard migration is. It identifies objects by SHA-1, so after SHAttered it adopted collision detection that rejects inputs carrying the known attack's fingerprints, and it added a SHA-256 object format, which stopped being labelled experimental in Git 2.42 while SHA-1 stayed the default. Interoperability between the two formats is the slow part: every tool that assumes a 40-character hex ID must change. The lesson for your own systems is to make the hash algorithm an explicit, versioned field from day one, as multihash and the sha256- prefix in subresource integrity do.

SHA-3: the sponge construction

SHA-3 is the Keccak sponge, chosen by public competition and standardised in FIPS 202 in 2015. Its state is 1600 bits. A message is padded and absorbed r bits at a time, XORed into the 'rate' part of the state, with the Keccak-f permutation of 24 rounds applied after each block. Output is squeezed from the rate. The remaining c bits, the capacity, are never input directly or output, and security against generic attacks is about c/2 bits. SHA3-256 uses c = 512, so r = 1088 bits, 136 bytes per block.

Two practical details trip people up. First, the SHAKE functions are extendable-output: SHAKE256 can produce 32 bytes or 32 kilobytes, which is useful for key derivation and for post-quantum schemes that need long pseudorandom streams. Second, the 'Keccak-256' used by Ethereum is the pre-standard padding, not SHA3-256. FIPS 202 added domain-separation bits, so the two give different digests for the same input. Test against vectors from the standard you actually need.

Choosing a hash

Performance is rarely the deciding factor, but it is worth knowing. On 64-bit CPUs without SHA instructions, SHA-512 often runs faster than SHA-256 because it processes 128-byte blocks with 64-bit words. Many x86 and Arm CPUs accelerate SHA-256 in hardware, which reverses that. Measure on your platform with openssl speed sha256 sha512 before optimising.

Signature schemes are where your choice is usually made for you: Ed25519 hashes with SHA-512, while ECDSA and RSA-PSS take a SHA-2 size as a parameter. Merkle trees build on whichever hash you pick, and inherit its collision resistance.

Failure modes

• hash(key + msg) as a MAC. Length extension; use HMAC.
• Comparing digests with ==. Early-exit comparison leaks timing; use hmac.compare_digest.
• Ambiguous concatenation. hash("ab" + "c") equals hash("a" + "bc"). Length-prefix or encode fields before hashing.
• Fast hashes for passwords. A GPU tries billions of SHA-256 guesses per second.
• SHA-1 left in certificate, signature or deduplication paths. Chosen-prefix collisions make these forgeable.
• Hard-coded algorithm. Without a version field, migration means a flag day.

Trade-offs

SHA-256 wins on support and speed: every library has it and many CPUs accelerate it, but you must remember HMAC wherever a key is involved. SHA-512/256 gives the same digest size with built-in length-extension resistance, at the cost of patchier library and hardware support. SHA-3 buys design diversity, so a future SHA-2 break does not take it down too, but it has less hardware acceleration and is slower in software on many platforms. Longer digests raise security margins and also the size of every identifier, index entry and URL that carries them. An algorithm-version field costs a few bytes per record; leaving it out costs a flag-day migration later, as Git found. Compliance can decide for you: FIPS-validated environments allow only approved functions and implementations, so check before choosing anything outside SHA-2 and SHA-3.

What to do next

1. Grep your code and configs for SHA-1 and MD5 and list each use as integrity, authentication, signature or identifier.
2. Replace any hash(key + data) construction with HMAC-SHA-256 and constant-time comparison.
3. Add an explicit algorithm identifier next to every stored digest.
4. Run the SHA-256 implementation above and step through one round to see Ch, Maj and the rotations at work.
5. Pick SHA-256 by default, SHAKE256 for variable output, and SHA3-256 where you want design diversity.
6. Check test vectors from FIPS 180-4 and FIPS 202 in your build so a wrong library or Keccak variant fails fast.