抗碰撞函式 H’ = h1(h2()) 的組合是否抗碰撞？
假設有兩個抗碰撞雜湊函式 $ h_1 $ 和 $ h_2 $ 輸出大小為 $ n_1 $ 和 $ n_2 $ 分別。
是 $ H’(x) = h_1(h_2(x)) $ 對不同關係的抗碰撞 $ n_1 $ 和 $ n_2 $ ?
在過去的幾天裡，這一直讓我和我的同事們感到難以置信，因為兩種不同的方法相互矛盾：
第一種方法：
基於碰撞阻力的定義 $ H’ $ 有一個輸出 $ n_1 $ 長度，所以如果我們能找到比 $ \mathcal O(2^{n_1/2}) $ 它不耐碰撞。
我們想要$$ \mathcal O(2^{n_2/2}) < \mathcal O(2^{n_1/2}) \implies \ldots \implies n_2 < n_1 $$
因此，如果 $ n_2 < n_1, H’ $ 不是抗碰撞的，在其他情況下它是
第二種方法：
讓我們假設 $ H’ $ 不耐碰撞。
那麼存在不同的 $ x_1 $ 和 $ x_2 $ 以便 $ H’(x_1) = H’(x_2) $ IE $ h_1(h_2(x_1)) = h_1(h_2(x_2)) $
如果發生這種情況 $ h_2(x_1) = h_2(x_2) $ ， 但 $ h_2 $ 耐碰撞
它也可能發生，如果 $ h_1(A) = h_1(B) $ 在哪裡 $ A = h_2(x_1) $ 和 $ B = h_2(x_2) $ 但 $ h_1 $ 是抗碰撞的。
我們已經證明 $ H’ $ 是抗碰撞的和的關係 $ n_1 $ 和 $ n_2 $ 沒關係。
我有機會問我的教授，他期待第一個解決方案，因為第二個假設 $ n_1 = n_2 $ （我仍然不知道為什麼或在哪裡這樣做）。
他還解釋說：
- 一個 $ n_2 $ 1000 位，然後轉換為 $ n_1 $ 2 位被認為是抗衝突的，因為您利用了 2 位提供的完全安全性，即您獲得了您“支付”的 2 位的所有值。
- 相反一個 $ n_2 $ 然後轉換為 500 位 $ n_1 $ 1000 位不被認為是抗衝突的，因為您“支付”了 1000 位的安全性並且只使用了 500。
這確實幫助我以直覺和合乎邏輯的方式理解了這個概念。
在過去的幾天裡，這一直讓我和我的同事們感到難以置信，因為兩種不同的方法相互矛盾
原因是這兩種方法假設了“防碰撞”的不同定義。這兩個定義不等價；也就是說，我們可以找到滿足一個定義而不是另一個定義的函式。
第一次嘗試使用定義’沒有碰撞發現附加需要更少的 $ \mathcal{O}(2^{n/2}) $ 操作；因為 $ n $ 已修復，我們將其用作“攻擊發生”的簡寫 $ c2^{n/2} $ 操作，對於一些 $ c $ 與 1 相差不遠，以及一些合理的操作定義（在本例中為雜湊函式評估）。
這個定義的問題在於它導致了一些荒謬的結論，例如，截斷為 8 位的 SHA-256 按這個定義是“抗碰撞”的。在另一個方向上，來自 SHAKE-256 的 1kbyte 輸出不是“抗碰撞”，因為您可以找到的碰撞遠少於 $ 2^{8192/2} $ 雜湊評估。
相比之下，方法 2 使用定義“如果我們找不到衝突，雜湊函式是抗衝突的”。正式表達這個有點棘手（因為，只要允許輸入比輸出長，肯定會有衝突，我們只是不知道它們是什麼），也因為這與計算資源有關我們有（現在，截斷為 200 位的 SHA-256 是抗碰撞的；隨著我們獲得更多的計算能力，可能不會在 20 年後）；另一方面，它更接近於我們所擁有的“防碰撞”的直覺概念。
有了這個定義，方法 2 可以改寫為“如果我們假設 $ H’ $ 不抗碰撞，那麼我們知道 $ x \ne y $ 和 $ H’(x) = H’(y) $ . 然後要麼 $ h_2(x) = h_2(y) $ （因此 $ h_2 $ 不抗碰撞，因為我們知道碰撞），或 $ h_2(x) \ne h_2(y) $ , 在這種情況下我們有 $ h_1(u) = h_1(v) $ 為了 $ u = h_2(x), v = h_2(y), u \ne v $ （因此 $ h_1 $ 不抗碰撞，因為我們知道碰撞）。