MD5 - Chosen Prefix Collision Attack

Question

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

kelalaka · Answer

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

Chosen-prefix collisions for MD5 and applications,  2012.

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_1mathbin|s_1) = text{MD5} (m_2mathbin|s_2)$$
They also gave examples for colliding documents, software integrity checking, etc ...

MD5 - Chosen Prefix Collision Attack

One Answer

Add your own answers!

Ask a Question