Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?
$\begingroup$ $\endgroup$
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
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.
$\begingroup$ $\endgroup$
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$.
