Merkle–Damgård construction

As explained in Hacking Cryptography

A hash function built by repeatedly applying a compression function to message blocks in the Merkle–Damgård construction.

Merkle–Damgård is an iterative design for hash functions. It splits input into equal-length blocks, pads the final block, and feeds each block plus the previous state into a compression function. After the last block, the resulting state is the hash digest. section 6.3.1 section 6.5

Figure 6.5 The Merkle–Damgård construction for hash functions

Follow the chaining value from one message block to the next: each compression step combines the current block with the prior state, producing the state for the next step. section 6.3.1

This design underlies MD5, SHA-1, and SHA-2. MD5 and SHA-1 have practical collision attacks that outperform brute-force birthday attacks; SHA-256 and SHA-512 remain collision-resistant as described here, but their construction still permits length extension. section 6.3 section 6.3.1

Its critical consequence is that the digest exposes the complete final internal state. Given H(A), an attacker can resume hashing and calculate a digest for A with appended data B without knowing A. Padding and the original message length let the resumed computation align with the original block sequence. section 7.3.2 section 6.5

Length-extending a secret-prefix MAC

A bank API authenticates a transaction as SHA-256(secret || parameters). An attacker who knows a valid request, its digest, and the original length can add padding and new parameters, initialize SHA-256 from the old digest, and produce a valid MAC for the extended request. Secret-prefix MACs built with Merkle–Damgård hashes are therefore unsafe against this attack. section 7.3 section 7.3.2

Figure 7.9 Because the internal state of the hash function is available to the attacker in the digest, the hash calculation can be “resumed.”

The diagram captures why extension works: the published digest is sufficient state to continue the block-by-block calculation with attacker-controlled input. section 7.3.2

For designs requiring resistance to this weakness, distinguish Merkle–Damgård hashes from SHA-3’s sponge construction: SHA-3 was standardized later and avoids the length-extension weakness associated with older designs. section 6.3 section 6.3.2

How Hacking Cryptography covers it

How deep it goes

Traces padding, chained compression, exposed final state, and a SHA-256 length-extension exploit without detailing compression-function internals.

Examples

Demonstrates chained message blocks and a forged bank transaction request that extends a SHA-256 secret-prefix MAC.

What you can do after

Evaluate/understand why a published Merkle–Damgård digest can enable extension of secret-prefix MAC inputs.

How it connects

Connects compression functions, hash digests, collision resistance, length-extension attacks, secret-prefix MACs, SHA-2, SHA-3, and sponge construction.

liveBookmanning.com

Read Hacking Cryptography on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Real-World CryptographyThe Merkle–Damgård construction builds an arbitrary-length hash function by iteratively applying a fixed-size compression function to padded message blocks.

Compare how 2 books explain Merkle–Damgård construction →

Related concepts

• SHA-2includes · SHA-2 is a standardized family of cryptographic hash algorithms that produces fixed-length digests, including SHA-224, SHA-256, SHA-384, and SHA-512.
• md5implemented by · MD5 is a cryptographic hash algorithm that produces a 128-bit message digest and is considered insecure because practical collision attacks exist.
• SHA-1implemented by · SHA-1 is a cryptographic hash algorithm that produces a 160-bit digest and is no longer considered collision-resistant because practical collision attacks exist.
• sponge constructioncontrasts with · A sponge construction absorbs input into a state through repeated permutation applications and squeezes output from that state, supporting outputs of arbitrary length.
• compression functionuses · A compression function is a function that transforms input information into a shorter or fixed-size representation.

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.