Overview

Building a hash function, especially one that accepts inputs of arbitrary length, seems like a challenging task. In this section, we'll see one approach for constructing hash functions, called the Merkle-Damgård construction. 

Instead of a full-fledged hash function, imagine that we had a collision-resistant function whose inputs were of a single fixed length, but longer than its outputs. In other words, \(h : {0, 1}^{n+t} → {0, 1}^n\) , where \(t > 0\). We call such an h a compression function. This is not compression in the usual sense of the word - we are not concerned about recovering the input from the output. We call it a compression function because it "compresses" its input by t bits (analogous to how a pseudorandom generator "stretches" its input by some amount). 

The following construction is one way to build a full-fledged hash function (supporting inputs of arbitrary length) out of such a compression function: 

Construction 11.2 (Merkle-Damgård) 

Let \(h : {0, 1}^{n+t} → {0, 1}^n\) be a compression function. Then the Merkle-Damgård transformation of \(h\) is \(MD_h : {0, 1}^∗ → {0, 1}^n\), where:

The idea of the Merkle-Damgård construction is to split the input x into blocks of size \(t\). The end of the string is filled out with 0s if necessary. A final block called the "padding block" is added, which encodes the (original) length of \(x\) in binary.

Example 

Suppose we have a compression function \(h : {0, 1}^{48} → {0, 1}^{32}\), so that \(t = 16\). We build a Merkle-Damgård hash function out of this compression function and wish to compute the hash of the following 5-byte (40-bit) string: 

x = 01100011 11001101 01000011 10010111 01010000 

We must first pad x appropriately (MDPAD(X)): 

• Since x is not a multiple of \(t = 16\) bits, we need to add 8 bits to make it so. 
• Since \(|x| = 40\), we need to add an extra 16-bit block that encodes the number 40 in binary (101000). 

After this padding, and splitting the result into blocks of length 16, we have the following: 

\( \underbrace{01100011 \; 11001101}_{x_1} \; \; \underbrace{01000011 \; 10010111}_{x_2} \; \; \underbrace{0101000 \; 000000}_{x_3} \; \; \underbrace{00000000 \; 00101000}_{x_4} \)

The final hash of x is computed as follows:

We are presenting a simplified version, in which \(MD_h\) accepts inputs whose maxi- mum length is \(2^t − 1\) bits (the length of the input must fit into t bits). By using multiple padding blocks (when necessary) and a suitable encoding of the original string length, the construction can be made to accommodate inputs of arbitrary length (see the exercises). 

The value y₀ is called the initialization vector (IV), and it is a hard-coded part of the algorithm. 

As discussed above, we will not be making provable security claims using the library- style definitions. However, we can justify the Merkle-Damgård construction with the following claim: 

Claim 11.3 

Suppose \(h\) is a compression function and \(MD_h\) is the Merkle-Damgård construction applied to \(h\). Given a collision \(x, x′\) in \(MD_h\) , it is easy to find a collision in \(h\). In other words, if it is hard to find a collision in \(h\), then it must also be hard to find a collision in \(MD_h\). 

Proof 

Suppose that \(x, x′\) are a collision under \(MD_h\). Define the values \(x_1, . . . , x_{k+1}\) and \(y_1, . . . , y_{k+1}\) as in the computation of \(MD_h (x)\). Similarly, define \(x′_1, . . . , x′_{k′+1}\) and \(y'_1, . . . , y′_{k′+1}\) as in the computation of \(MD_h (x′)\). Note that, in general, \(k\) may not equal \(k'\). 

Recall that: 

\(MD_h (x) = y_{k+1} = h(y_k ‖ x_{k+1})\)

\(MD_h (x′) = y′_{k′+1} = h(y′_{k′} ‖ x′_{k′+1})\)

Since we are assuming \(MD_h (x) = MD_h (x')\), we have \(y_{k+1} = y′_{k′+1}\). We consider two cases: 

Case 1: If \(|x| \neq |x'|\), then the padding blocks \(x_{k+1}\) and \(x'_{k′+1}\) which encode |x| and |x'| are not equal. Hence we have \(y_k ‖ x_{k+1} \neq y′_{k′} ‖ x'_{k′+1}\), so \(y_k ‖ x_{k+1}\) and \(y′_{k′} ‖ x'_{k′+1}\) are a collision under h and we are done. 

Case 2: If \(|x| = |x'|\), then x and x' are broken into the same number of blocks, so \(k = k'\). Let us work backwards from the final step in the computations of \(MD_h(x)\) and \(MD_h (x')\). We know that: 

\(y_{k+1} = h(y_k ‖ x_{k+1})\)

= 

\(y′_{k+1} = h(y′_k ‖ x'_{k+1})\)

If \(y_k ‖ x_{k+1}\) and \(y′_k ‖ x'_{k+1}\) are not equal, then they are a collision under h and we are done. Otherwise, we can apply the same logic again to \(y_k\) and \(y′_k\) , which are equal by our as- sumption. 

More generally, if \(y_i = y′_i\) , then either \(y_{i−1} ‖ x_i\) and \(y′_{i−1} ‖ x'_i\) are a collision under h (and we say we are "lucky"), or else \(y_{i−1} = y'_{i−1}\) (and we say we are "unlucky"). We start with the premise that \(y_k = y′_k\) . Can we ever get "unlucky" every time, and not encounter a collision when propagating this logic back through the computations of \(MD_h (x)\) and \(MD_h (x')\)? The answer is no, because encountering the unlucky case every time would imply that \(x_i = x'_i\) for all \(i\). That is, \(x = x'\). But this contradicts our original assumption that \(x \neq x'\). Hence we must encounter some "lucky" case and therefore a collision in \(h\).

Source: Mike Rosulek, https://joyofcryptography.com/pdf/chap11.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 License.