MD5 - Chosen Prefix Collision Attack

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

• 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 ) – Maarten Bodewes Oct 3 '18 at 1:56

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