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 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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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