Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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