Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 4 down vote favorite

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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.