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.
Aliases (3)
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 NERFINISHED → |
| 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
→
Ralph Merkle NERFINISHED → |
| 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
→
|
Referenced by (5)
| Subject (surface form when different) | Predicate |
|---|---|
|
Ralph Merkle
("Merkle–Damgård hash construction")
→
Ronald L. Rivest ("MD5") → |
notableWork |
|
Ralph Merkle
→
|
hasConceptNamedAfter |
|
Ralph Merkle
→
|
knownFor |
|
Merkle–Damgård construction
("Merkle–Damgård strengthening")
→
|
typicalPadding |