Merkle-Damgård construction

Merkle-Damgård construction

A compression function accepts two inputs: a chaining variable and a block of message. Let f:{0,1}^b \times {0,1}^n → {0,1}^n be a compression function which takes a b-bit message block and an n-bit chaining value. Let h:{0,1}^* → {0,1}^n be a MD construction built by iterating the compression function f in order to process a message of arbitrary length. A message M to be processed using h is always padded in a manner such that the length of the padded message is a multiple of the block length b of f. Bit-length b corresponds to input length of desired compression function f. The padding is done by adding after the last bit of the last message block a single 1-bit followed by the necessary number of 0-bits. Let |M| be a binary representation of the length of the message M. The binary encoding of the message length is also be added to complete the padding. This is called a Merkle-Damgård strengthening.Then input M subsequently divided into t blocks, each of bit-length b. The hash function h can then be described as follows:

\left.\begin{array}{l}H_0=I V \\H_i=f\left(H_{i-1}, M_i\right), i=1 \ldots t, \\h(M)=H_t\end{array}\right\}

Where f is the compression function of h, H_i is the intermediate chaining variable between stage i-1 and stage i, and H0 is a pre-defined starting value or the initial value IV. The block diagram of the iterative hash function using the compression function is shown in the Figure 3. The computation of the hash value is dependent on the chaining variable. At the start of hashing, this chaining variable has a fixed initial value which is specified as part of the algorithm.

Figure 4. Detailed view of Merkle-Damgård construction

Figure 4. Detailed view of Merkle-Damgård construction

This process continues recursively, with the chaining variable being updated under the action of different part of the message, until the entire message has been used. The final value of the chaining variable is then output as the hash value corresponding to that message. One of its distinctive features is that it promotes the collision resistance and preimage resistance of the compression function to the full hash function: for instance, a collision on the compression function can be deduced efficiently from a collision on the full hash function. The inclusion of the length at the end of the message is important for this situation, and is also important for preventing a number of attacks, including long-message attacks. 

Merkle-Damgård construction proves that the security of hash function relies on the security of the compression function. Thus, in order to build a collision resistant hash function, it is sufficient to design a collision resistant compression function. Recent results, however, highlight some intrinsic limitations of the MD approach. This includes being vulnerable to multicollision attacks, long second preimages attacks, and herding attack. Figure 4 shows detailed view of MD construction.

Source: Harshvardhan Tiwari, https://www.researchgate.net/figure/Merkle-Damgard-construction-A-compression-function-accepts-two-inputs-a-chaining_fig3_322094216
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.
Back to '2.3: Merkle-Damgard Construction'