結合md5碰撞產生更多碰撞

給定 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)？

令為 Merkle–Damgård 散列函式的壓縮函式，如 MD5。假設我們有一個廉價算法，它返回消息塊使得。我們可以將它與標準初始化向量一起使用來找到雙向碰撞，因此 我們可以用它找到四向碰撞嗎？[Math Processing Error] $ f $ $ \operatorname{MD}_f $ $ C(h) $ $ m_0 \ne m_1 $ $ f(h, m_0) = f(h, m_1) $ [Math Processing Error] $ \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) $ 回答：是的，我們可以使用算法來查找雙向 MD 衝突，以查找路衝突，只需次呼叫。[Math Processing Error] $ C $ [Math Processing Error] $ 2^n $ [Math Processing Error] $ n $ [Math Processing Error] $ C $

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)) $ [Math Processing Error]$$ \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 Joux, ‘Multicollisions in Iterated Hash Functions中更詳細地描述了這一系列攻擊及其對連接散列函式的影響。Application to Cascaded Constructions’，Matt Franklin 編輯，密碼學進展—CRYPTO 2004，Springer LNCS 3152，第 306-316 頁。

引用自：https://crypto.stackexchange.com/questions/29537