為什麼類似於 CBC-MAC 的散列函式不是抗衝突的？
我正在閱讀 Mike Rosulek 的書*The Joy of Cryptography*。
在閱讀第 11 章的雜湊函式時，我發現了一個非常有趣的練習。有人對如何證明這一點有想法嗎？
有關問題的完整詳細資訊，請參閱下圖。
- 碰撞攻擊
碰撞攻擊意味著我們需要找到兩個不同的消息 $ m \neq m’ $ 這樣 $ H(m) = H(m’) $ . 我們可以根據需要自由選擇消息。這表明它的成本為 $ \mathcal{O}(2^{n/2}) $ - 以 50% 的機率進行安全構造的生日攻擊。
接收任意消息 $ m $ 大小至少兩個塊 $ m = x_1 \mathbin|x_2 $ . 然後我們有
$$ H^*(m) = H\big(H(x_1) \oplus x_2\big) $$
現在構造一條新消息 $ m’ $ 通過修改 $ m $ $$ m’ = H(x_1) \oplus x_2 $$這可以構造，因為散列是免費的。現在我們有
$$ H^*(m’) = H\big(H(x_1) \oplus x_2\big) $$這裡註意 $ m \neq m’ $ 自從$$ \big(x_1 \mathbin|x_2 \big)\neq \big( H(x_1) \oplus x_2\big) $$
自從我們開始我們選擇的消息以來，這個過程就進行了碰撞攻擊。
- 具有衝突的大小相等的消息
上面的結構使用了一個簡單的修改，需要一個塊更小的消息來發現衝突。我們可以對大小相等的消息進行沖突嗎？是的，我們可以通過這些步驟；
考慮 $ m = x_1 \mathbin|x_2 $ 然後我們有
$$ H^*(m) = H\big(H(x_1) \oplus x_2\big) $$
現在構造 $ m’= x_3 \mathbin| a $ 比
$$ H^*(m’) = H\big(H(x_3) \oplus a\big) $$
要發生碰撞，我們需要$$ H(x_1) \oplus x_2 = H(x_3) \oplus a $$用簡單的算術 $ \oplus $
$$ a = H(x_3) \oplus H(x_1) \oplus x_2 $$
現在 $ m’ = x_3 \mathbin| \big( H(x_3) \oplus H(x_1) \oplus x_2 \big) $
然後
$$ \begin{align} H^(m’) &= H\big(H(x_3) \oplus a\big)\ & = H\big(H(x_3) \oplus \big( H(x_3) \oplus H(x_1) \oplus x_2 \big) \big)\ & = H\big( H(x_1) \oplus x_2\big) = H^(m)\ \end{align} $$
- 第二次預映像攻擊
在這種情況下是第二次原像攻擊；我們得到一個雜湊值 $ h $ 和輸入消息 $ m $ 這樣 $ h = H^*(m) $ . 如果給定 $ m $ 至少有兩個塊，而不是簡單的碰撞攻擊變體將起作用，只是我們不選擇 $ m $ …