5
$\begingroup$

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$?

Improve this question
$\endgroup$
1
  • $\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 ♦
    Commented Oct 3, 2018 at 1:56

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ so... it's nearly bruteforce $\endgroup$
    – Pacerier
    Commented Jul 23, 2020 at 10:26
  • 1
    $\begingroup$ @Pacerier far from the brute-force. $\endgroup$
    – kelalaka
    Commented Jul 23, 2020 at 19:31

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.