Overview
Merkle-Damgard construction processes padded blocks sequentially, feeding each chaining value into the next compression step.
CoreSource checked
Merkle-Damgard Construction
Builds a hash function by chaining a compression function over message blocks.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Cryptography
- Difficulty
- Advanced
- Family
- Hash Construction
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
compression functionchaining valuemessage paddingblock processingmisuse resistanceparameter validation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use when protecting messages needs compression function.
- Use when the input matches the assumptions behind hash Construction.
When Not to Use
- Avoid when a well-reviewed library already provides the primitive for production use.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Builds a hash function by chaining a compression function over message blocks
- Uses compression function and chaining value to guide the work.
- Produces ciphertext, digest, proof, or derived key.
Use Cases
- Protecting messages
- Authenticating data
- Deriving or managing cryptographic material
Inputs
- Secret key or public parameters
- Message or secret data
- Nonce, salt, or context where needed
Outputs
- Ciphertext, digest, proof, or derived key
Key Formulas (1)
Chaining update
Hi = compress(H_{i−1}, blocki)
H_i = compress(H_{i-1}, block_i)Updates the hash state one message block at a time.
Pseudocode
- 1.Validate keys, nonces, salts, group parameters, and input ranges
- 2.Apply the primitive's block, hash, group, or reduction operation
- 3.Combine intermediate values exactly as the construction specifies
- 4.Return the protected value, proof, signature, derived key, or verification result
Canonical Example
- Input
- message = 'pay 10' with configured keys, nonces, or public parameters
- Output
- Ciphertext, digest, proof, or derived key
- Explanation
- Merkle-Damgard Construction applies compression function to produce ciphertext, digest, proof, or derived key.
Implementation Notes
- Use constant-time library implementations for real systems instead of hand-written primitives.
- Keep the compression function step separate enough to test independently.
- Use reviewed libraries and protocol specifications for production security-sensitive code.
Common Pitfalls
- Reusing nonces, salts, pads, or domain parameters can destroy the intended security property.
- Test edge cases, not only clean examples.
- Treating educational pseudocode as production crypto can hide nonce, parameter, and side-channel requirements.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the major cryptographic rounds or data dependencies without exposing secrets.
Step 1 of 4: Validate keys, nonces, salts, group parameters, and input ranges
cryptography-mechanismNotes
Merkle-Damgard hashes need careful padding and can have length-extension behavior unless the construction or use accounts for it.
Sources (1)
What each reference supports for this entry.
Handbook of Applied Cryptography
BookReference text for classical cryptographic constructions, block ciphers, hash constructions, and security properties.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toMerkle Tree
Tree hashing organizes hash combinations differently from a linear Merkle-Damgard chain.
GeneralizesSHA-256
SHA-256 is an example of a Merkle-Damgard-style hash construction.
Related Algorithms
Tags
CryptographyHash FunctionSecurityClassic