How to find collisions in a secret-prefix Merkle–Damgård given an adversary that can choose the IV?

Question

I am given the following Merkle–Damgård construction:

Let $f \colon (\{0,1\}^n \times \{0,1\}^b) \to \{0,1\}^n$ be a compression function. Fix a string $\mathrm{IV}\in\{0,1\}^n$, and for $M \in (\{0,1\}^b)^+$ define $H(\mathrm{IV},M)$ as follows. Parse $M=M_1 || \cdots || M_\ell$, let $h_0 = \mathrm{IV}$, and let $h_i = f(h_{i-1},M_i)$ for $i=1,2,\cdots,\ell$. Then $H(\mathrm{IV},M) = h_\ell$. (Note that this does not mean that all imputs to $H$ have to be the same length.)

I'm also given an algorithm C that takes in a value for any IV, and outputs some messages $X,X’$ such that $H(IV,X)=H(IV,X’)$.

Lastly, I'm given access to a secret-key function $F_K(\cdot)=H(K,\cdot)$.

Using C, how can I find a pair of messages $M,M’$ such that $F_K(M)=F_K(M’)$?

---

---

I've looked at the proof for Merkle–Damgård constructions and understand that since $H$ is broken, the underlying compressing function f must be broken. What I don't understand is how we could possibly come up with such an M and M' with no knowledge of the IV?

I know that it is not important to know the IV to create a forgery for this construction, but I'm being asked to produce a collision; not a forgery.

I've been struggling with this problem for quite a while, and would love some help on where to start.

Answer 1

Algorithm C would give you the answer directly, except it needs an IV to start off with, and you don't initially know that. Here's some hints:

• The IV you give algorithm C needn't be the secret IV $K$; instead, it can be the intermediate state of some message

• So, how could you use your access to function $F_K$ to find the intermediate state in some message?

Answer 2

Note your description does not include merkel damgard strengthening, or any finalization phase. This makes our lives rather easy. Hash any messsage with secret key. Use the output as the IV for compression function to create two suffixes. If we append these two suffixes to the orignal arbitrary message we will get a collision on the secret key hash.