Merkle-Damgård Transform

Introduction

In practice, it is easier to construct hashing algorithms which operate on relatively small, fixed input lengths, whilst still keeping the output length even smaller ($l_{\text{out}}$ is still less than $l_{\text{in}}$). But hash functions are usually used on much larger inputs - for example, creating checksums for integrity verification of files. The Merkle-Damgård transform allows us to turn such a hash function, which operates on small fixed input lengths, into a hash function which operates on inputs of arbitrary lengths.

The Merkle-Damgård Construction

In particular, given a compression function $H^{\prime }(\text{input}:\text{str}[\text{const }{l}_{\text{in}}])\to \text{str}[\text{const }l]$ which works with inputs of a “small”, fixed input length $l_{\text{in}}$ and has outputs with length $l$, the Merkle-Damgård transform allows us to use $H^{\prime }$ to a construct a hash function $H(\text{input}:\text{str}[l_{\text{m}}])\to \text{str}[\text{const }l]$ which takes messages of arbitrary length, denoted by $l_{\text{m}}$, and produces digests of the same output length $l$ as $H^{\prime }$.

The construction is similar to a block cipher in the sense that the message $m$ is chopped up into blocks. In contrast to block ciphers, however, this is done rather differently. Each block has length $l_{\text{in}}$ (since each block will be input into $H^{\prime }$), but it is not comprised entirely of message bits. Instead, each block contains $l_{\text{mb}}$ message bits and the other $l_t$ bits ($l_t=l_{\text{in}}-l_{\text{mb}}$) represent the so-called chaining variable for the current block.

This means that the message $m$ needs to be chopped up into $q$ message fragments ${\mu }_1,{\mu }_2,...,{\mu }_q$, all of length $l_{\text{mb}}$. If the message length $l_m$ is not a multiple of $l_{\text{mb}}$, then the message is padded by appending a 1 to it and then appending 0s until the message length is short of a multiple of the fragment length $l_{\text{mb}}$ by exactly the number of bits $l_e$ needed to encode the message length $l_m$. The total length of the padding (including the 1, the 0s and the encoding of the message length) is denoted by $l_{\text{pad}}=1+\text{count}(0)+l_e$.

When the message length $l_m$ is a multiple of the fragment length $l_{\text{mb}}$, padding still needs to be added. In a particular, an additional padding block is appended to the message, following the exact same procedure as before. The padding block begins with a $1$ and is followed by $0$s - the last $l_e$ bits of the padding block again encode the message length $l_m$.

NOTE

The number of bits reserved for encoding the message length $l_{mb}$ is fixed for a given Merkle-Damgård construction. Usually $l_e$ is 64 bits, resulting in a maximum message length of $2^{64}-1$, which is quite a reasonable limit.

After padding, the actual hash algorithm begins by appending an initialisation vector (IV) of length $l$ to the first message fragment ${\mu }_1$. The IV is always a constant which is pre-defined in the specification of the Merkle-Damgård construction.

EXAMPLE

The SHA256 hash function uses the following 256-bit IV (the value is in hex):

$$IV:=\text{0x6A09E667BB67AE853C6EF372A54FF53A510E527F9B05688C1F83D9AB5BE0CD19}$$

This initialisation vector serves as the initial chaining variable $t_1$. The concatenation ${\mu }_1||IV$ of the first message block ${\mu }_1$ with the IV is passed to the compression function $H^{\prime }$, whose output becomes the next chaining variable. In general, the $i$-th iteration takes the $i$-th message block ${\mu }_i$ and appends to it the chaining variable $t_i$. The chaining variable $t_i$ for the current stage is simply the output of $H^{\prime }$ from the previous iteration. The final output, i.e. the hash generated by the Merkle-Damgård function $H$, is the final chaining variable.

Security of Merkle-Damgård Constructions

The reason why the Merkle-Damgård transform is used ubiquitously is the fact that it preserves collision resistance.

Theorem: Merkle-Damgård Collision Resistance

If the compression function $H^{\prime }$ is collision resistant, then so is the Merkle-Damgård function $H$.

PROOF

Suppose, towards contradiction that there is an efficient collision finder $\mathcal{A}$ which can find a collision in $H$ with non-negligible probability. Let $x$ and $x^{\prime }$ be two inputs of lengths $L$ and $L^{\prime }$, respectively, such that $H(x)=H(x^{\prime })$. Let $x_1,x_2,...,x_q$ be the $q$ blocks which $x$ is divided into, and, let $x_1^{\prime },x_2^{\prime },...,x_{q^{\prime }}^{\prime }$ be the $q^{\prime }$ blocks which $x^{\prime }$ is divided into. Similarly, let $t_1,t_2,...,t_q,t_{q+1}$ and $t_1^{\prime },t_2^{\prime },...,t_{q^{\prime }}^{\prime },t_{q^{\prime }+1}^{\prime }$ be the chaining variables used at each iteration of the hashing of $x$ and $x^{\prime }$, respectively (remember that the chaining variables $t_{q+1}$ and $t_{q^{\prime }+1}^{\prime }$ are also the output of $H$).

Case 1: If the two inputs have different lengths, i.e. $L\ne L^{\prime }$, then the hash $H(x)$ is $t_{q+1}:=H^{\prime }(x_q||t_q)$ and the hash $H(x^{\prime })$ is $t_{q^{\prime }+1}^{\prime }:=H^{\prime }(x_q^{\prime }||t_{q^{\prime }}^{\prime })$. However, $H(x)=H(x^{\prime })$ means that $H^{\prime }(x_q||t_q)=H^{\prime }(x_q^{\prime }||t_{q^{\prime }}^{\prime })$ which is a contradiction because $L\ne L^{\prime }$ and so $x_q\ne x_{q^{\prime }}^{\prime }$ (remember that the length is appended to the message when padding) - we have found two different inputs which cause a collision in the collision resistant $H^{\prime }$.

Case 2: If the two inputs have the same length, i.e. $L=L^{\prime }$, then they are also divided into the same number of blocks $q=q^{\prime }$. Let $I_i:=x_i||t_i$ denote the $i$-th input passed to $H^{\prime }$ when computing $H(x)$, and let $I_i^{\prime }:=x_i^{\prime }||t_i^{\prime }$ denote the $i$-th input passed to $H^{\prime }$ when computing $H(x^{\prime })$. Additionally, we will denote the output of $H(x)$ as $I_{q+1}:=t_{q+1}$, and we will denote the output of $H(x^{\prime })$ as $I_{q^{\prime }+1}^{\prime }:=t_{q^{\prime }+1}^{\prime }$.

Now, $H(x)=H(x^{\prime })$ and so $I_{q+1}=t_{q+1}=I_{q^{\prime }+1}^{\prime }=t_{q^{\prime }+1}^{\prime }$. This can only happen if $I_q=I_{q^{\prime }}^{\prime }$ or if $(I_q,I_{q^{\prime }}^{\prime })$ is a collision pair for $H^{\prime }$ and the same logic propagates backwards - in general, $H^{\prime }(I_i)=H^{\prime }(I_i^{\prime })$ can be true only if $I_i=I_i^{\prime }$ or if $(I_i,I_{i^{\prime }}^{\prime })$ is a collision pair for $H^{\prime }$. The inputs $x,x^{\prime }$ are a collision pair for $H$ which means that $x\ne x^{\prime }$ and so there must be some index $j$ for which $x_j\ne x_j^{\prime }$ which means for sure that $I_j\ne I_j^{\prime }$ and so $(I_j,I_j^{\prime })$ turn out to be a collision in $H^{\prime }$, which is a contradiction.