Given 2 messages $m_1$ and $m_2$, in a chosen prefix attack, we want to find $s_1$ and $s_2$ such that:

$\text{MD5}(m_1 || s_1) = \text{MD5}(m_2 || s_2)$

Are $s_1$ and $s_2$ found by brute force or are there some rule(s) to construct $s_1$ and $s_2$ based on $m_1$ and $m_2$?

  • $\begingroup$ Generally for these kind of attacks the $m$ and $s$ input consist of one or more blocks. The size of these blocks is determined by the internal block size of the cipher, which, for MD5, is 512 bit. Brute forcing a 512 bit block would take $2^{512} / 2 = 2^{511}$ tries on average. That's a calculation that will never finish (even if we take into account that it takes a very long time for black holes to vaporize due to Hawking radiation :P ) $\endgroup$ – Maarten Bodewes Oct 3 '18 at 1:56

The answer is due to the Stevens et. al's work ;

They showed that, with an approximately $2^{39}$ calls to the MD5 compression function, it is possible, for any chosen $m_1$ and $m_2$, to construct $s_1$ and $s_2$ such that $$\text{MD5} (m_1\mathbin\|s_1) = \text{MD5} (m_2\mathbin\|s_2)$$

They also gave examples for colliding documents, software integrity checking, etc ...

  • $\begingroup$ so... it's nearly bruteforce $\endgroup$ – Pacerier Jul 23 '20 at 10:26
  • 1
    $\begingroup$ @Pacerier far from the brute-force. $\endgroup$ – kelalaka Jul 23 '20 at 19:31

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.