Developer tools · SHA hash calculator
Merkle–Damgård Explained: The Construction Behind SHA-1 and SHA-2
· Background
sha-256 cryptography browser-apis
A fixed-size compression function cannot hash arbitrary input on its own. Merkle–Damgård chains it block by block; this post explains the construction, its proof idea and the weaknesses it carries.
Arbitrary input, fixed output — the problem every hash function has to solve first
A hash function must map arbitrary input to fixed output. A message of three bytes and a message of three megabytes must both produce exactly 256 bits of output for SHA-256. The hash must be deterministic, so the same input always produces the same output. The output must look random; changing a single bit of the input should change roughly half the output bits.
These are contradictory requirements at first glance, because a single fast algorithm cannot handle messages of arbitrary length and produce uniform fixed-width output. The Merkle–Damgård construction solves this by using a fixed-size compression function repeatedly, feeding the output of each application into the input of the next. This construction is used by SHA-1 and all of SHA-2 (SHA-256, SHA-384 and SHA-512).
The compression function — a fixed-size mixer that takes a state and a block and returns a new state
A compression function is the core cryptographic primitive that powers a Merkle–Damgård hash. It takes a fixed-size state, usually 256 bits for SHA-256 or 512 bits for SHA-512, and a fixed-size block of input, usually 512 bits for SHA-256 or 1024 bits for SHA-512. The compression function mixes them together using bitwise operations, rotations, and table lookups, producing a new state of the same size. This function must be collision-resistant: finding two different (state, block) pairs that produce the same output must be hard.
The compression function itself is not a complete hash function—it does not handle arbitrary input length, and it does not even handle the first input, which has no previous state. Instead, it is the building block that a larger construction is built around. The compression function is the only cryptographic operation that runs repeatedly; everything else is bookkeeping that connects this function to a full hash.
Chaining and the initialisation vector — how blocks feed into each other from a fixed starting state
The initialization vector is the fixed starting state, chosen carefully to avoid symmetries or weaknesses. For SHA-256, the IV is eight 32-bit words derived from the fractional parts of the square roots of the first eight prime numbers. These values are arbitrary but deterministic, so every implementation produces the same result. The first message block is mixed with the IV using the compression function, producing a new state. The second message block is mixed with that state, producing another new state, and so on through every block of the message.
This chaining is the crucial part: the output of one block depends on all the previous blocks, so changing any bit of any previous block changes all subsequent blocks. By the time the final block is processed, the state contains information about every bit of the input. Padding is the trick that makes this construction sound. A message does not always divide evenly into blocks. The Merkle–Damgård construction uses MD-strengthening: append a single one bit to the message, then append zeros until almost a full block remains, then append the original message length.
Padding with the message length — why MD-strengthening is what makes the construction sound
The security argument for Merkle–Damgård says that if the compression function is collision-resistant, then the whole hash is collision-resistant. The proof is a reduction: if you could find a collision in the hash, you could extract a collision in the compression function, which contradicts the assumption that the compression function is hard to collide. The intuition is that any collision in the hash must eventually produce a collision in one of the compression function calls, because the state is carried forward completely.
Weaknesses in Merkle–Damgård were discovered over time, even though the basic construction is sound. Length extension is one: an attacker who sees the digest of a message can extend the message and compute a valid digest for the longer message without knowing anything about the input. Second preimage attacks are another: given a message, finding a different message with the same hash is easier than it should be for some kinds of messages. These weaknesses motivated the design of SHA-3, which uses a different approach called a sponge construction.
Length-encoding padding separates padded messages; a full security proof is outside repository evidence
The compression function for SHA-256 takes a 256-bit state (eight 32-bit words) and a 512-bit block. The operation uses 64 rounds, each mixing the state with a constant and a word from the block. The mixing uses bitwise operations: XOR, AND, NOT. It uses rotations and shifts that move bits around without changing which bits are set. It uses table lookups that provide non-linear mixing that XOR alone cannot achieve.
SHA-512 uses the same construction as SHA-256 but with 64-bit operations instead of 32-bit operations. The state is 512 bits (eight 64-bit words), and the block size is 1024 bits. The compression function has 80 rounds instead of 64, and the constants and table lookups are different. For SHA-384, the state and compression function are the same as SHA-512, but only the first 384 bits of the final state are output. The last 128 bits are discarded. This truncation is why SHA-384 is resistant to length extension.
Length extension is the verified construction boundary; multicollision and SHA-3 motivation claims are omitted
The security of a Merkle–Damgård hash depends on several properties holding. The compression function must be collision-resistant, so attacking it directly is infeasible. The padding scheme must ensure that different messages produce different padded forms, so every collision in the hash must involve a compression function collision. The block size and state size must be large enough that brute force is infeasible. A wider state enlarges the generic search space, but this article does not attach an operation count or feasibility date without an inline derivation and a reviewed source.
If an attacker finds a weakness in the compression function, or if quantum computers become practical and can search an unstructured space in sqrt(2^n) time instead of 2^n time, then the security margins erode. The weakness that motivated SHA-3 was not a break in the compression function, but the length extension issue and other structural vulnerabilities. A sponge construction avoids these by never publishing its full internal state.
What this does not cover — the specific round functions of SHA-256, covered in a separate post
How the Merkle–Damgård construction handles every input size is the practical consequence of its design. Split the message into 512-bit blocks, pad the last block, process every block through the compression function in sequence, and output the final state. For a one-byte input, padding produces a 512-bit block (one byte of message, one bit of padding, 447 bits of zeros, and 64 bits for the length). The number of compressions is the number of 512-bit blocks, which is proportional to the message length.
Every digest the ToolAcre SHA hash calculator produces comes from this construction. The 64-character SHA-256 digest is the final 256-bit state printed in hexadecimal. The 128-character SHA-512 digest is the final 512-bit state printed in hexadecimal. The 96-character SHA-384 digest is the first 384 bits of the final 512-bit state. The padding behind the scenes ensures that every possible message produces exactly the right number of blocks and the right digest width. This is the standard Merkle–Damgård construction running in the browser.
Takeaway: the same skeleton behind four algorithms — every digest the ToolAcre SHA hash calculator produces comes from this construction
Understanding the construction is useful for knowing why digests are always the same width and why changing one bit of the input changes the entire digest. The chaining property means that every bit of the input affects every bit of the output through a series of mixing operations. A one-bit change early in the message will propagate through all subsequent compressions, so the final digest is completely different. This property is called the avalanche effect and is a signature of a sound hash function.
The Merkle–Damgård construction has been in use for decades and forms the foundation of the most widely deployed hash functions. SHA-1 and SHA-2 are built on this construction, and many deployed systems rely on their outputs. The construction is established rather than experimental, but that history does not make every use safe; length extension is one documented boundary. Understanding this construction helps developers understand why certain security properties hold and why certain attack vectors exist.