為什麼海綿構造的通用碰撞發現攻擊的複雜度為 O(min(2^(-n/2) , 2^(-c/2)))？

我正在嘗試了解用於創建散列函式和對其進行一般攻擊的海綿函式。

我正在尋找導致碰撞發現攻擊的場景 $ O(\min(2^{-n/2} , 2^{-c/2})) $ 時間複雜度，其中 $ n $ 是海綿輸出長度（雜湊輸出長度）和 $ c $ 是海綿狀態的容量長度。

我知道 $ 2^{-n/2} $ 來自對輸出的傳統生日攻擊，但攻擊場景是什麼？ $ 2^{-c/2} $ 複雜？

表示內部海綿狀態 $$ S = R\mathbin|C, $$ 在哪裡 $ C $ 有大小 $ c $ - 容量。

每次迭代一個長度的消息塊 $ |R| $ 異或成 $ R $ 然後是排列 $ P $ 被申請;被應用。因此，如果我們在 $ C $ （可以在 $ 2^{c/2} $ 基本生日攻擊的步驟），我們可以取消任何差異 $ R $ 通過注入適當的消息對。

因此，如果 $ (M_1,M_2) $ 產生零差異 $ C $ 和區別 $ \Delta R $ 在 $ R $ ， 這對 $$ (M_1\mathbin|X,M_2\mathbin|(X\oplus \Delta R)) $$ 是完整功能的碰撞對 $ F $ 對於任何 $ X $ .

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