Introduction to Cryptography with Coding Theory, 3rd Edition

12.2 Multicollisions

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 ...