Merkle–Damgård construction

E99142
cryptographic construction hash function design paradigm

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.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (5)

Label Occurrences
Merkle–Damgård construction canonical 4
MD5 1
Merkle–Damgård 1

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 Eli Biham ⓘ
surface form: Ivan Damgård

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 construction self-linksurface differs ⓘ
surface form: 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 ⓘ

Referenced by (8)

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 construction ⓘ
this entity surface form: Merkle–Damgård hash construction
Ralph Merkle → hasConceptNamedAfter → Merkle–Damgård construction ⓘ
Ronald L. Rivest → notableWork → Merkle–Damgård construction ⓘ
this entity surface form: MD5
Merkle–Damgård construction → typicalPadding → Merkle–Damgård construction self-linksurface differs ⓘ
this entity surface form: Merkle–Damgård strengthening
MD5 → follows → Merkle–Damgård construction ⓘ
SHA-256 → category → Merkle–Damgård construction ⓘ
RIPEMD-160 → compressionFunctionStructure → Merkle–Damgård construction ⓘ
this entity surface form: Merkle–Damgård