Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?


Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its compression function has a known collision.

Consider SHA-256. Note its round function $F:\{0,1\}^{256}\times\{0,1\}^{512}\to\{0,1\}^{256}$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^{256},0^{512})$ is defined to be $F(0^{256},1^{512})$.

$F'$ has a known collision, yet the variant of SHA-256 using $F'$ is collision resistant, because we can't find a way to bring the state of SHA-256 to all-zero, which would essentially be a preimage attack.


For a very realistic example, see the analysis contained in Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV by Black, Rogaway, and Shrimpton.

They explore all the ways of building a Merkle-Damgaard hash function with an ideal cipher as the underlying compression function, finally classifying which are secure and which are not.

Interestingly, they find a category of constructions with the property you mention:

... group-2 schemes ... are collision resistant even though their compression functions are not.

As an example, their $H_{13}$ uses $f(h_i, m_i) = E_{h_i \oplus m_i}(m_i)$ as the compression function. Although this round function leads to a secure MD hash function, by itself it is not even one-way. To find a preimage of $y$, first choose arbitrary $k$, then compute $m : = E^{-1}_k(y)$ and $h := m \oplus k$. Then $(h,m)$ is a preimage of $y$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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