How to find collisions in a secret-prefix Merkle–Damgård given an adversary that can choose the IV? 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.
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?