Merkle–Damgård construction

E99142

The Merkle–Damgård construction is a fundamental method for building collision-resistant cryptographic hash functions from fixed-size compression functions, used in many classic hash algorithms like MD5 and SHA-1.

AI illustration

How this image was made

AI-generated illustration of Merkle–Damgård construction

This AI-generated illustration was produced by black-forest-labs/FLUX.2-dev (1024x1024) from a prompt written by openai/gpt-oss-120b from the entity's label + description.

Prompt

Generate an image of the Merkle–Damgård construction (The Merkle–Damgård construction is a fundamental method for building collision-resistant cryptographic hash functions from fixed-size compression functions, used in many classic hash algorithms like MD5 and SHA-1.)

All labels observed (7)

How this entity was disambiguated

Statements (46)

Predicate Object
instanceOf cryptographic construction ⓘ
hash function design paradigm ⓘ
appliesTo arbitrary-length messages ⓘ
assumes compression function is collision-resistant ⓘ
basedOn fixed-length compression function ⓘ
computes chaining value for each message block ⓘ
contrastWith HAIFA construction ⓘ
sponge construction ⓘ
wide-pipe construction ⓘ
domain information security ⓘ
theoretical computer science ⓘ
field cryptographic hash functions ⓘ
cryptography ⓘ
finalStep output last chaining value as hash ⓘ
formalizedIn Damgård 1989 paper ⓘ
Merkle 1989 paper ⓘ
goal provable security reduction from hash to compression function ⓘ
hasPart compression function ⓘ
initialization vector ⓘ
iterative chaining process ⓘ
padding scheme ⓘ
implies hash function is collision-resistant if compression function is collision-resistant ⓘ
independentlyProposedBy Ivan Damgård ⓘ
Ralph Merkle ⓘ
influenced design of many classic hash standards ⓘ
inspired later domain-extension constructions for hash functions ⓘ
limitation does not inherently provide indifferentiability from a random oracle ⓘ
Merkle–Damgård strengthening padding that appends message length ⓘ
namedAfter Ivan Damgård ⓘ
linked to: Eli Biham

Ralph Merkle ⓘ
output fixed-length hash value ⓘ
property length extension property ⓘ
requires collision-resistant padding ⓘ
publicly known initialization vector ⓘ
securityModel black-box model of compression function ⓘ
typicalPadding Merkle–Damgård strengthening ⓘ
use building collision-resistant hash functions ⓘ
usedIn HAVAL ⓘ
MD5 ⓘ
RIPEMD-160 ⓘ
SHA-0 ⓘ
SHA-1 ⓘ
SHA-2 ⓘ
usesInput message blocks of fixed size ⓘ
vulnerableTo length extension attacks ⓘ
yearProposed late 1970s ⓘ

How these facts were elicited

Referenced by (14)

Full triples — surface form annotated when it differs from this entity's canonical label.

Ralph Merkle → knownFor → Merkle–Damgård construction ⓘ
Ralph Merkle → notableWork → Merkle–Damgård hash construction ⓘ
linked to: Merkle–Damgård construction
Ralph Merkle → hasConceptNamedAfter → Merkle–Damgård construction ⓘ
Ronald L. Rivest → notableWork → MD5 ⓘ
linked to: Merkle–Damgård construction
Merkle–Damgård construction → typicalPadding → Merkle–Damgård strengthening ⓘ
linked to: Merkle–Damgård construction
MD5 → follows → Merkle–Damgård construction ⓘ
SHA-256 → category → Merkle–Damgård construction ⓘ
RIPEMD-160 → compressionFunctionStructure → Merkle–Damgård ⓘ
linked to: Merkle–Damgård construction
SHA-0 → usesConstruction → Merkle–Damgård construction ⓘ
SHA-2 → basedOn → Merkle–Damgård construction ⓘ
Damgård 1989 paper → mainTopic → Merkle–Damgård construction ⓘ
Damgård 1989 paper → relatedTo → Merkle–Damgård paradigm ⓘ
linked to: Merkle–Damgård construction
SHA-1 → usesConstruction → Merkle–Damgård construction ⓘ
Whirlpool → paddingScheme → Merkle–Damgård-style padding ⓘ
subject linked to: Whirlpool hash function
linked to: Merkle–Damgård construction