# Combining md5 collisions to create more collisions

Given X1 and X2 such that md5(X1) = md5(X2) and Y1 and Y2 such that md5(Y1) = md5(Y2), and knowing the following property of md5:

if md5(a) = md5(b), md5(a|s) = md5(b|s)

is there a way to find Z1, Z2, Z3, and Z4 such that md5(Z1) = md5(Z2) = md5(Z3) = md5(Z4)?

Let $$f$$ be the compression function of a Merkle–Damgård hash function $$\operatorname{MD}_f$$, like MD5. Suppose we have a cheap algorithm $$C(h)$$ which returns message blocks $$m_0 \ne m_1$$ such that $$f(h, m_0) = f(h, m_1)$$. We can use this with the standard initialization vector $$\mathit{iv}$$ to find a two-way collision $$(m_0, m_1) = C(\mathit{iv})$$, so that $$\operatorname{MD}_f(m_0) = f(\mathit{iv}, m_0) = f(\mathit{iv}, m_1) = \operatorname{MD}_f(m_1).$$ Can we use it to find a four-way collision $$(m_0, m_1, m_2, m_3)$$?
Answer: Yes, we can use an algorithm $$C$$ for finding two-way MD collisions to find $$2^n$$-way collisions with only $$n$$ calls to $$C$$.
1. Let $$(b_0, b'_0) = C(\mathit{iv})$$.
• Then $$f(\mathit{iv}, b_0) = f(\mathit{iv}, b'_0)$$.
2. Let $$h_1 = f(\mathit{iv}, b_0) = f(\mathit{iv}, b'_0)$$.
3. Let $$(b_1, b'_1) = C(h_1)$$. That is, use the common hash as a new initialization vector to find a new collision.
• Then $$f(f(\mathit{iv}, b_0), b_1) = f(f(\mathit{iv}, b_0), b'_1))$$, etc., so the messages \begin{align} m_0 &= b_0 \mathbin\| b_1, \\ m_1 &= b'_0 \mathbin\| b_1, \\ m_2 &= b_0 \mathbin\| b'_1, \\ m_3 &= b'_0 \mathbin\| b'_1 \end{align} constitute a four-way collision.