I recently got a question that I’ld like to share here, since answers might be useful (or at least interesting) for people diving into Merkle-Damgård hash constructions for the first time.

We know that the Merkle-Damgård hash function is based on a fixed size $\{0,1\}^{m+t} \rightarrow \{0,1\}^m$ compression function.

Why can an arbitrary compression function mapping $\{0,1\}^{m+2^m} \rightarrow \{0,1\}^m$ not seriously be considered collision resistant?


1 Answer 1


There are two cases. In the first case, $m$ is very small, and in such a case you can find collisions by the birthday paradox. In the second case, $m$ is not very small, and $2^m$ is too large to be considered feasible. This argument is obvious in the concrete setting (consider $m=64$; this is ridiculously small and collisions can be found in just $2^{32}$ time, but a message of $2^{64}$ size is not feasible).

Asymptotically, the same argument can be made. In order for the function to be collision resistant, you must have $m=\omega(\log n)$, where $n$ is the security parameter. This is necessary since otherwise $\sqrt{2^m} = \sqrt{n}$ which is very small (in particular, it's polynomial). Otherwise, just to be concrete, consider $m=\log n\log\log n$. In this case $2^m = 2^{\log n\log\log n} = n^{\log n}$, which is not polynomial. However, this means that it's not possible to run the function with an input of length $2^m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.