组合md5冲突来创建更多的冲突

Question

给定X1和X2，使得md5(X1) = md5(X2)，Y1和Y2使md5(Y1) = md5(Y2)，并且知道md5的以下属性：

设md5(a) = md5(b)，md5(a=S)=md5(b=S)

是否有找到Z1、Z2、Z3和Z4的方法，使md5(Z1) = md5(Z2) = md5(Z3) = md5(Z4)？

Answer 1

设f是Merkle哈希函数\operatorname{MD}_f的压缩函数，如MD5。假设我们有一个廉价的算法C(h)，它返回消息块m_0 \ne m_1，从而使f(h, m_0) = f(h, m_1)。我们可以在标准初始化向量\mathit{iv}中使用它来找到双向碰撞(m_0, m_1) = C(\mathit{iv})，那么\operatorname{MD}_f(m_0) = f(\mathit{iv}, m_0) = f(\mathit{iv}, m_1) = \operatorname{MD}_f(m_1).我们能用它找到一个四向碰撞(m_0, m_1, m_2, m_3)吗？

回答:是的，我们可以使用一种算法C来查找双向MD碰撞，以找到2^n-way冲突，而只使用对C.

的n调用。

1. 让(b_0, b'_0) = C(\mathit{iv})。
   • 然后是f(\mathit{iv}, b_0) = f(\mathit{iv}, b'_0)。

2. 让h_1 = f(\mathit{iv}, b_0) = f(\mathit{iv}, b'_0)。
3. 让(b_1, b'_1) = C(h_1)。也就是说，使用公共哈希作为新的初始化向量来查找新的冲突。
   • 然后是f(f(\mathit{iv}, b_0), b_1) = f(f(\mathit{iv}, b_0), b'_1))等，所以\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}的消息构成了一个四位一体的碰撞.

4. 泡沫，漂洗，重复多次不同的碰撞，你想要的。

这一系列攻击及其对连接散列函数的影响在Antoine，迭代散列函数中的多解.“级联结构的应用”，马特·富兰克林编，“密码学进展-密码学进展”，2004年年，斯普林格LNCS 3152，第306至316页中有更详细的描述。