# Pseudo preimage for a hash made from a cipher

Consider the Miyaguchi–Preneel construction:

$H_0 = E(0,m_0) \oplus m_0$ (0 here means a vector filled with zeros)

$H_1 = E(H_0,m_1) \oplus H_0 \oplus m_1$

where $E(K,M)$ is a block cipher (for example AES), $m_0, m_1$ are messages. What's the best way to find messages $m_0$, $m_1$, such that $H_1$ will have a given prefix? $prefix(H_1, len(P)) = P$? Is there a faster way than birthday paradox?

-
The standard attack would be to try random or incremental $m_1$ until an $H_1$ matches the criteria; this has cost $o(2^{len(P)})$ encryptions (with the same key $H_0$). I do not even see how the birthday "paradox" helps in this (partial) preimage attack. –  fgrieu Jul 25 '12 at 17:41

This problem reduces to a standard preimage attack: if the solution can be found faster than with $2^l$ trials, then a full preimage can be found faster than $2^n$. The latter problem is considered difficult for iterated hash functions based on the Miyaguchi-Preneel construction, as the latter is difficult even when the IV is not fixed.