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?

  • 3
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Jul 25, 2012 at 17:41

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.