我正在嘗試解決一個交給我的問題。我遇到的問題是我缺少一些解決它的部分。

我遇到了一個 Oracle，它使用以下函式對可以是任意長度的輸入執行 MAC。我需要偽造一條消息，該消息必須與 Oracle 計算的消息相匹配。

$ o_1 = E(k, d_1) $

$ o_2 = E(k, o_1 \oplus d_2) $

…

$ o_N = E(k, o_{N-1} \oplus d_N) $

所以 $ MAC(k, d) = o_1 \oplus o_2 \oplus … \oplus o_N $

在哪裡 $ d_X $ 是消息的塊大小部分（例如：消息是 32 位長 = 4 x 8 位塊）。

為了偽造消息，Oracle 提供了 2 種方法：

$ mac0(n) $ -> 執行 $ MAC(k,msg) $ 與 msg = nxd （其中 d 是一個 8 位塊全零，n 是塊的數量要求）

$ mac3(input) $ -> 執行 $ MAC(k, d) $ 對於任何輸入（如果輸入大於 3 個塊，則將其截斷為 3 個塊；如果較小，則用零填充其餘部分，直到輸入為 3 個塊長）。

在範例中，我將使用 32 位長輸入（4 個塊）。

我目前做的第一件事是我將 mac3 與第一個塊一起使用，這將導致 $ o_3 $ . 我，然後，異或 $ o_3 $ 與最後一個塊（ $ d_4 $ ) 並通過發送結果 $ mac3 $ 再次。當與 Oracle 的實際結果進行比較時，我發現它並不相等。

所以這就是我卡住的地方..根據我的理解，這可能是由於填充 $ mac3 $ 因為輸入不是 3 塊長。這是我不知道如何解決的部分。有沒有辦法恢復結果以找到實際的偽造消息？

還有其他想法嗎？

比方說 $ b $ 是我們的塊大小。我們可以很容易地看到，如果消息有大小 $ b $ , 以下成立 $ MAC(k, d) = E(k, d) $ . 所以，讓我們首先嘗試為單個塊消息解決這個問題（我們稱之為 $ p $ ).

一條阻止消息

目標是計算 $ E(k, p) $ , 因為那是 $ MAC(k, p) $ .

消息必須通過 $ E $ 在某一點。唯一可以接收消息的函式是 $ mac3 $ （相比之下， $ mac0 $ 需要一個數字）。問題是 $ mac3 $ 恰好需要 3 個輸入塊。所以，我們的一個塊消息 $ p $ 必須以某種方式擴展為三塊消息。如果我們將消息塊放在 3 個塊的開頭，第一次呼叫 $ E $ 會產生 $ o_1 $ 這將在第二次和第三次呼叫中被破壞 $ E $ . 我們不能那樣做。

如果我們放置消息塊會發生什麼 $ p $ 在 3 塊輸入的末尾 $ mac3 $ ? 這 $ o_3 $ 其中包含我們消息塊的加密 $ p $ 只會被異或，但不會再次加密。我們有一個贏家，因為很容易反轉 XOR，因為我們不需要密鑰。

讓我們回顧一下 XOR 的工作方式：如果 $ x \oplus y = z $ 然後 $ x \oplus z = y $ . 還， $ x \oplus x = 0 $ 和 $ x \oplus x \oplus y = y $ . 我們將需要它。

回到我們的問題。我們可以控制 $ o_3 = E(k, o_2 \oplus d_3) $ 如果我們可以控制，成為我們一個塊消息的 MAC $ o_2 $ . 這是哪裡 $ mac0 $ 進來。

如果我們將 3 塊消息設置為 $ 0^b | 0^b | p $ 在哪裡 $ | $ 意味著連接和 $ x^b $ 重複的意思 $ x $ $ b $ 次？

$ o_1 = E(k, 0^b) $

$ o_2 = E(k, o_1 \oplus 0^b) = E(k, o_1) $

$ o_3 = E(k, o_2 \oplus p) $

$ m = o_1 \oplus o_2 \oplus o_3 $

我們知道 $ o_1 = mac0(1) $ ，但這還不足以控制 $ o_2 $ ，因為我們不知道密鑰 $ k $ . 究竟是什麼 $ mac0(2) $ 然後？…

$ o_{1,m2} = E(k, 0^b) = o_1 $

$ o_{2,m2} = E(k, o_{1,m2} \oplus 0^b) = E(k, o_{1,m2}) = o_2 $

$ m_{m2} = o_{1,m2} \oplus o_{2,m2} = o_1 \oplus o_2 $

由此，我們可以計算 $ o_2 $ :

$$ o_2 = o_1 \oplus m_{m2} = mac0(1) \oplus mac0(2) $$ 好的，現在我們控制 $ o_2 $ . 我們還是要計算 $ E(k, p) $ . 所以讓我們設置 $ d_3 = o_2 \oplus p $ . 這將導致

$$ o_3 = E(k, o_2 \oplus d_3) = E(k, o_2 \oplus o_2 \oplus p) = E(k, p) $$ 好的，現在我們快到了。最終的 MAC 是 $ m = o_1 \oplus o_2 \oplus o_3 $ . 既然我們已經知道 $ o_1 $ 和 $ o_2 $ 從以前開始，我們有

$$ m = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus p\right) \oplus mac0(2) = E(k, p) $$ 多塊消息

最後一個公式包含如何 $ E(k, p) $ 可以為任何單塊消息計算 $ p $ . 這可用於計算中間值 $ o_x $ 如果是複合消息。

比方說，我們的資訊是

$$ d = d_1 | d_2 | … | d_N $$ 那麼最終的MAC可以計算為

$ o_1 = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus d_1\right) \oplus mac0(2) $

$ o_2 = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus o_1 \oplus d_2\right) \oplus mac0(2) $

$ … $

$ o_N = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus o_{N-1} \oplus d_N\right) \oplus mac0(2) $

$ m = o_1 \oplus o_2 \oplus … \oplus o_N $

這是（未經測試的）Java 程式碼。

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