What is Merkle-Damgard construction?

The Merkle Damgard construction is a process of making a cryptographic hash function using a one-way compression function. This construction is based on the rule that if the compression function is collision resistance, the hash function will also be collision resistance. Many popular hash functions like MD5, SHA-1, and SHA-2 have been designed using Merkle Damgard construction.

How it works

The process starts with expanding the input message to a length that is multiple of some fixed number of bits. It is necessary because compression function only works on the fixed-length inputs.

Why padding is important?

It is important to carefully select the padding scheme for message length expansion because weak padding can introduce security vulnerability to the function. Padding should be MD-compliant which means it should satisfy following conditions:

• $M$ is a prefix of $Pad(M)$
• If $|M_1|$ $=$ $|M_2|$ then $|Pad(M_1)|$ $=$ $|Pad(M_2)|$
• If $|M_1|$ $\neq$ $|M_2|$, then the last block of $|Pad(M_1)|$ is different from the last block of $|Pad(M_2)|$

For example

In one of the MD-compliant schemes, we use two blocks. The first one is a padding block that contains “1” followed by “0,” and the second one is the message size block.

The input message is divided into fixed-length blocks. The blocks are then processed using a one-way compression function (f) and initial vector (IV). The initial vector is a predefined value that changes in every iteration and, at last, produces the hash. It is further processed using the finalization function which ensures fixed-length output and avalanche effectAn avalanche effect is a property where a slight change in either the key or text causes a significant change in the cipher-text in an encryption algorithm..