為 4DES 執行 MitM 所需的加密操作數
假設使用 4 個不同的 56 位密鑰應用 DES 4 次（ $ k_1 $ 至 $ k_4 $ ）。通過使用中間相遇攻擊，已知明文攻擊所需的密碼操作數是多少？
給出的答案：
對於每一對 $ k_1 $ 和 $ k_2 $ ，我們需要 2 次加密和 2 次解密。共有 $ 2^{112} $ 對。所以需要的總數是 $ 2^{114} $ 密碼操作。
我不明白為什麼每對密鑰都有 4 個操作。我認為攻擊的每一半都需要（ $ 2^{56*2} = 2^{112} $ ) 操作，所以總數應該只有 ( $ 2^{112} * 2 = 2^{113} $ ) 操作。我在這裡做錯了什麼？
在 MitM for 2DES 中，在製表階段，我們計算並保持 $ 2^{56} $ 64 位值及其相關鍵，然後在搜尋階段我們計算 $ 2^{56} $ 64 位值並在表中搜尋這些值。大約有一次命中 $ 2^{64-56}=2^8=256 $ 搜尋，那是關於 $ 2^{56-8}=2^{48} $ 命中，除了一個以外都是假命中。我們需要通過一些額外的 DES 操作來消除錯誤命中：通常是兩個，測試額外的明文/密文對²。此外，已經獲得了 64 位值的一小部分 $ k>1 $ 在第一階段，當我們在搜尋中命中其中一個時，消除錯誤命中所需的 DES 操作數為 $ 1+k $ . 所有這些細節都使 DES 操作的數量比基數增加了不到 1% $ 2^{57} $ （用於完整搜尋，或 $ 3\times2^{55} $ 平均而言），有些展覽忽略了這個細節³。
但是如果我們通過預計算為 4DES 實現 MitM $ 2^{112} $ 64 位值，每個 64 位值將獲得平均值 $ 2^{112-64}=2^{48} $ 次，因此在搜尋階段，我們會被誤擊淹沒：而不是罕見的（在 256 次搜尋中出現一次），這將是常態，消除誤擊需要平均 $ 1+2^{48} $ 額外的 DES。這是不合理的額外工作量。
攻擊 4DES 的一個簡單方法是使用普通的 MitM 塊密碼 2BIG 進行攻擊，其中 BIG 是一個塊密碼，其密鑰大小和塊大小是普通 DES 的兩倍（即 112 位密鑰和 128 位塊大小）通過對 128 位塊的每個 64 位一半應用 2DES 和 112 位密鑰獲得，需要兩次 DES 操作。理論上，MitM 將突破 2BIG $ 2^{113} $ BIG 的評估（用於完整搜尋），因此大約 $ 2^{114} $ DES的評估。
¹ 假設我們在製表階段保留了所有相應的鍵，如果我們想確保找到解決方案，這是必需的。
² 當我們得到第二個明文/密文對的確認時，大多數情況下我們找到了正確的 56 位密鑰對。但相反的可能性仍然約為 $ 2^{-16} $ ，因此我們希望使用第三個明文/密文對進行額外檢查，代價是 2 DES 操作。
³ 房間裡有一頭大象：即使針對 2DES，更針對 4DES，基本 MiTM 需要如此多的 RAM 和 RAM 訪問，DES 操作的成本相對而言可以忽略不計。