攻擊信封mac

當我閱讀論文時：MDx-MAC and building fast MACs from hash functions

我無法理解對信封方法的攻擊（4.3）。特別是，我不確定連結變數指的是什麼以及必須滿足哪些先決條件才能執行攻擊。

也許更詳細/改寫的解釋可以幫助我理解攻擊的要點。

受到攻擊的 MAC 是由雜湊建構的 $ h $ （假設通過將散列消息拆分為僅處理一次的塊來處理散列消息，就像大多數散列一樣），將密鑰拆分為 $ K_1 $ 和 $ K_2 $ 大小相等。它計算消息的 MAC $ x $ 作為$$ \operatorname{MAC}_{K_1\mathbin|K_2}(x)=h(K_1\mathbin|x\mathbin|K_2) $$

論文中的攻擊恢復了 $ K_1 $ 和 $ K_2 $ 從 oracle 接受計算 MAC，分 3 步

1. 我們對預言機進行線上查詢，直到找到 $ x $ 和 $ x’ $ 具有相同的 MAC，並且由於之前的雜湊狀態衝突而發生這種情況 $ K_2 $ 是散列的。後面的條件可以通過對 oracle 的一些額外查詢來測試。它被選中 $ x=x_1\mathbin|x_2 $ 之間有一個雜湊塊邊界 $ x_1 $ 和 $ x_2 $ ， 和 $ x_1 $ 大到足以發現碰撞，並且 $ x_2 $ 用於測試邊界之前的雜湊衝突，根據標準，如果 $ h(K_1\mathbin|x_1\mathbin|x_2\mathbin|K_2)=h(K_1\mathbin|x_1’\mathbin|x_2\mathbin|K_2) $ 對於一些不同的值 $ x_2 $ ，那麼很可能在邊界之前發生了雜湊狀態衝突。
2. 我們發現 $ K_1 $ 通過離線詳盡搜尋，選擇標準 $ h(K_1\mathbin|x)=h(K_1\mathbin|x’) $ （改變 $ x_2 $ 和/或使用類似於 1 中的第二次碰撞來清除誤報）。
3. 我們發現 $ K_2 $ 通過離線窮舉搜尋，為一些範例計算正確 MAC 的選擇標准保留在步驟 1 中。

對於雜湊 $ s $ 塊邊界處的內部狀態位和 $ k $ 位，第 1 步的成本 $ \mathcal O(2^{s/2}) $ oracle 查詢和步驟 2/3 成本 $ \mathcal O(2^{k/2}) $ 雜湊計算。將 MAC 寬度截斷為 $ s $ 增加了攻擊成本，但不會改變這些漸近性。

如果攻擊是實用的 $ s=64 $ , $ k=128 $ , 並且可以製作 $ 2^{32} $ 甲骨文查詢。

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