What is the Merkle-Damgard construction?

The Merkle-Damgard construction is a cryptographic method used to build collision-resistant hash functions from collision-resistant one-way compression functions. It works by padding messages to a fixed block size, processing them sequentially through an initialization vector and a compression function, and applying length padding. This structural design was independently proven sound by Ralph Merkle and Ivan Damgard and became the foundation for popular hash algorithms like MD5, SHA-1, and SHA-2.

What we know

• The Merkle-Damgard construction builds collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. [1, 2]
• Ralph Merkle described the construction in his 1979 Ph.D. thesis, and both Merkle and Ivan Damgard independently proved that the structure is sound if an appropriate padding scheme is used. [2]
• The algorithm pads the input to a multiple of a fixed number, splits it into fixed-size blocks, and processes them one at a time using a compression function combined with the previous output. [2]
• To secure the construction, messages are padded using length padding, also known as Merkle-Damgard strengthening, which encodes the length of the original message. [2]

Where to go next

• a case in pointWhich hash algorithms use the Merkle-Damgard construction?
• how it workedHow does a one-way compression function operate inside a hash function?
• what caused itWhat is length padding and why is it required for cryptographic security?
• whoHow does Ralph Merkle's work extend into public-key cryptography?
• the bigger pictureWhat is a cryptographic hash function?
• an unexpected connectionHow does a pioneer of cryptographic hashing connect to the field of cryonics?Ralph Merkle, the co-inventor of the Merkle-Damgard construction, also serves on the board of directors of the Alcor Life Extension Foundation and writes about molecular nanotechnology and cryonics.

Sources

• [1]Merkle–Damgård construction (Wikidata Q1757463) · CC0 1.0
• [2]Merkle–Damgård construction · CC BY-SA 4.0
• [3]Ralph Merkle · CC BY-SA 4.0
• [4]Cryptographic hash function · CC BY-SA 4.0
• [5]Ivan Damgård · CC BY-SA 4.0