4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.
  4. Lather, rinse, repeat for as many distinct collisions as you want.

This family of attacks, and their impact on concatenating hash functions, is described in more detail in Antoine Joux, ‘Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions’, in Matt Franklin, ed., Advances in Cryptology—CRYPTO 2004, Springer LNCS 3152, pp. 306–316.

$\endgroup$

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.