In this section, we show that the iterative nature of hash algorithms based on the Merkle-Damgård construction makes them less resistant than expected to finding multicollisions, namely inputs $x_1\text{,}\dots \text{,}{x}_n$ all with the same hash value. This was pointed out by Joux [Joux], who also gave implications for properties of concatenated hash functions, which we discuss below.

Suppose there are $r$ people and there are $N$ possible birthdays. It can be shown that if $r\approx N^{(k-1)/k}$, then there is a good chance of at least $k$ people having the same birthday. In other words, we expect a $k$-collision. If the output of a hash function is random, then we expect that this estimate holds for $k$-collisions of hash function values. Namely, if a hash function has $n$-bit outputs, hence $N=2^n$ possible values, and if we calculate $r=2^{n(k-1)/k}$ values of the hash function, we expect a $k$-collision. However, in the following, we’ll show that often we can obtain collisions much more easily.

In many hash functions, for example, SHA-256, there is a compression function $f$ that operates on inputs of a fixed length. Also, there is a fixed initial value $IV$. The message is padded to obtain the desired format, then the following steps are performed:

1. Split the message $M$ into blocks $M_1\text{,}{M}_2\text{,}\dots \text{,}{M}_{\ell }$.

2. Let $H_0$ be the initial value $IV$.

3. For $i=1\text{,}2\text{,}\dots \text{,}\ell$, let $H_i=f(H_{i-1}\text{,}{M}_i)$.

4. Let $H(M)=H_{\ell }$.

In SHA-256, the compression function is described in Section 11.4. For each iteration, it takes a 256-bit input from the preceding iteration along with a message block $M_i$ of length 512 and outputs a new string of length 256.

Suppose the output of the function $f$, and therefore also of the hash function $H$, has $n$ bits. A birthday attack can find, in approximately $2^{n/2}$ steps, two blocks $m_0$ and $m_0^{{}^{\prime }}$ such that $f(H_0\text{,}{m}_0)=f(H_0\text{,}{m}_0^{{}^{\prime }})$. Let $h_1=f(H_0\text{,}{m}_0)$. A second birthday attack finds blocks $m_1$ and ${m_1}^{\prime }$ with $f(h_1\text{,}{m}_1)=f(h_1\text{,}{m}_1^{{}^{\prime }})$. Continuing in this manner, we let

and use a birthday attack to find $m_i$ and $m_i^{{}^{\prime }}$ with

This process is continued until we have $t$ pairs of blocks $m_0\text{,}{m}_0^{{}^{\prime }}\text{,}{m}_1\text{,}{m}_1^{{}^{\prime }}\text{,}\dots$, $m_{t-1}\text{,}{m}_{t-1}^{{}^{\prime }}$, where $t$ is some integer to be determined later.

We claim that each of the $2^t$ messages

(all possible combinations with $m_i$ and $m_i^{{}^{\prime }}$) has the same hash value. This is because of the iterative nature of the hash algorithm. At each calculation $h_i=f(m\text{,}{h}_{i-1})$, the same value $h_i$ is obtained whether $m=m_{i-1}$ or $m=m_{i-1}^{\prime }$. Therefore, the output of the function $f$ during each step of the hash algorithm is independent of whether an $m_{i-1}$ or an $m_{i-1}^{\prime }$ is used. Therefore, the final output of the hash algorithm is the same for all messages. We thus have a $2^t$-collision.

This procedure takes approximately $t{2}^{n/2}$ steps and has an expected running time of approximately a constant times $tn{2}^{n/2}$ (see Exercise 13). Let $t=2$, for example. Then it takes only around twice as long to find four messages with same hash value as it took to find two messages with the same hash. If the output of the hash function were truly random, rather than produced, for example, by an iterative algorithm, then the above procedure would not work. The expected time to find four messages with the same hash would then be approximately $2^{3n/4}$, which is much longer than the time it takes to find two colliding messages. Therefore, it is easier to find multicollisions with an iterative hash algorithm.

An interesting consequence of the preceding discussion relates to attempts to improve hash functions by concatenating their outputs. Suppose we have two hash functions $H_1$ and $H_2$. Before [Joux] appeared, the general wisdom was that the concatenation

should be a significantly stronger hash function than either $H_1$ or $H_2$ individually. This would allow people to use somewhat weak hash functions to build much stronger ones. However, it now seems that this is not the case. Suppose the output of $H_i$ has $n_i$ bits. Also, assume that $H_1$ is calculated by an iterative algorithm, as in the preceding discussion. No assumptions are needed for $H_2$. We may even assume that it is a random oracle, in the sense of Section 12.3. In time approximately ${\displaystyle \frac{1}{2}}{n}_2{n}_1{2}^{n_1/2}$, we can find $2^{n_2/2}$ messages that all have the same hash value for $H_1$. We then compute the value of $H_2$ for each of these $2^{n_2/2}$ messages. By the birthday paradox, we expect to find a match among these values of $H_2$. Since these messages all have the same $H_1$ value, we have a collision for $H_1||H_2$. Therefore, in time proportional to ${\displaystyle \frac{1}{2}}{n}_2{n}_1{2}^{n_1/2}+n_2{2}^{n_2/2}$ (we’ll explain this estimate shortly), we expect to be able to find a collision for $H_1||H_2$. This is not much longer than the time a birthday attack takes to find a collision for the longer of $H_1$ and $H_2$, and is much faster than the time $2^{(n_1+n_2)/2}$ that a standard birthday attack would take on this concatenated hash function.

How did we get the estimate ${\displaystyle \frac{1}{2}}{n}_2{n}_1{2}^{n_1/2}+n_2{2}^{n_2/2}$ for the running time? We used ${\displaystyle \frac{1}{2}}{n}_2{n}_1{2}^{n_1/2}$ steps to get the $2^{n_2/2}$ messages with the same $H_1$ value. Each of these messages consisted of $n_2$ blocks of a fixed length. We then evaluated $H_2$ for each of these messages. For almost every hash function, the evaluation time is proportional to the length of the input. Therefore, the evaluation time is proportional to $n_2$ for each of the $2^{n_2/2}$ messages that are given to $H_2$. This gives the term $n_2{2}^{n_2/2}$ in the estimated running time.