# Compression function is not collision resistant but Merkle-Damgard is collision resistant

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