標準中間相遇解釋表明，您可以對重複分組密碼（例如雙 DES（連續執行兩次 DES））執行中間相遇攻擊。

然而，分組密碼本身通常在內部由若干輪組成。是否可以對單個塊加密使用中間相遇攻擊？

換句話說，加密/解密是否會遇到一個共同的中間狀態，讓我們看到 $ \newcommand{\E}{\text{E}} \newcommand{\D}{\text{D}} $ $ C = \E_k(M) = \E_{k’’}(\E_{k’}(M)) $ 和 $ M = \D_k(C) = \D’{k’}(\D’’{k’’}(C)) $ 以便 $ S = \E’{k’}(M) = \D’’{k’’}(C) $ 在哪裡 $ S $ 是中間狀態？

---

相關問題：了解對分組密碼的中間相遇攻擊。

相關 Wikipedia 頁面：Meet-in-the-middle 攻擊以及對 GOST 等多維 Meet-in-the-Middle 攻擊的附加參考。

中間相遇攻擊確實可以用於塊密碼（也可以是散列函式）密碼分析。如問題中所述，這可以追溯到Diffie 和 Hellman 對 DES 的分析。然而，當應用於基元時，通常會使用更複雜的技術。由於圍繞該主題的文獻非常廣泛，因此我不會詳細介紹所有技術，而是嘗試提供主要參考資料。

該答案的前四個部分討論了經典 MITM 攻擊的變體。這些攻擊與您提到的對 2DES 的攻擊最相似。可能經典 MITM 攻擊最有趣的方面是它們的低數據複雜性，這使得它們從實用的角度來看很有吸引力。不過，這也有一些例外（最值得注意的是雙斜肌）。

然而，最後一節認為，一般 MITM 思想在密碼分析中更為普遍。也就是說，許多統計攻擊都補充了一個可以合理地稱為 MITM 步驟的階段。Demirici-Selçuk 攻擊就是一個很好的例子。在這裡，數據要求通常更大。

基本的 MITM 攻擊

經典的 MITM 攻擊很容易：一個人用獨立的密鑰將密碼分成兩部分，比如說 $ K_1 $ 和 $ K_2 $ . 對於每個猜測 $ K_1 $ ，通過正向評估來計算中間狀態。類似地，為每個猜測計算中間狀態 $ K_2 $ 通過向後評估。候選鍵是中間狀態匹配的那些。

這種簡單方法的主要問題是，在幾輪之後，可能必須猜測太多的關鍵位才能獲得中間狀態。（導致時間和記憶體需求激增。）當然，關鍵時間表在這裡起著重要作用。例如，MITM 通常在塊大小較小但密鑰大小較大的塊密碼中很有用。

基本的 MITM 攻擊已應用於 DES 本身（因此不僅僅是 2DES），並且此後引入了一些改進。例如，您可以查看Dunkelman、Sekar 和 Preneel 所著的關於縮減圓 DES 的改進中間相遇攻擊（INDOCRYPT 2007）。那裡使用了一些專門的技巧；下面討論更高級和通用的變體。

3 子集 MITM

Bogdanov 和 Rechberger 在 SAC 2010上介紹了對基本攻擊的共同改進。在這些攻擊中，人們將密碼分成三部分。對於第二部分和第三部分中涉及的關鍵位的每次猜測，都會匹配前向和後向猜測，但這僅基於狀態的一部分（部分匹配）。這使得可以覆蓋中間部分的額外回合。缺點是部分匹配會導致更多的誤報，因此您最終會得到更大的關鍵候選列表。

我在評論中提到的Sasaki 最近對 GIFT 的攻擊就是基於這種 3 子集技術。此外，他還使用了源自對雜湊函式的原像攻擊的“拼接和切割”和“初始結構”技術（見下一節）。這項工作使用 MILP 建模來優化對 GIFT 的此類 MITM 攻擊。我之所以提到它，是因為 GIFT 的簡單結構使其很好地介紹了此類攻擊。

雜湊函式密碼分析的影響

使用 MITM 技術來查找雜湊函式的原像可以追溯到很長一段時間，至少從Lai 和 Massey (EUROCRYPT 1992) 開始（可能更早）。例如，這種技術用於Leurent 對FSE 2008 中的 MD4 的原像攻擊。

不久之後，Aoki 和 Sasaki 提出了一些改進方案。尤其是：

• 在SAC 2008上介紹的拼接和切割技術，適用於 MD4 和 MD5。
• EUROCRYPT 2009的初始結構（作為局部碰撞的概括）。

他們還在CRYPTO 2009上應用這些技術來減少 SHA-0 和 SHA-1 。這裡還有幾個後續工作，比如郭等人的額外改進。與 SHA-2 的應用程序。

一般來說，這種所謂的“拼接和切割框架”導致了對雜湊函式的原像攻擊的重大改進。當然，這些攻擊是關於消息恢復而不是密鑰恢復。然而，相同的原理可以應用於分組密碼。

由Khovratovich、Rechberger 和 Savelieva提出的 biclique是最初為原像攻擊引入的另一種工具。在這些攻擊中，雙組取代了初始結構。Bicliques 也（著名地）用於對全輪 AES 的密鑰恢復攻擊，參見Bogdanov、Khovratovich 和 Rechberger的 ASIACRYPT 論文。

其他變體

其他值得一提的變種是多維 MITM 攻擊（如問題中所述，一些資訊可以在 Wikipedia 上找到）、所有子密鑰恢復和中間篩攻擊。

所有子密鑰恢復攻擊是一種處理更複雜密鑰計劃的方法。這要歸功於磯部和澀谷。

由於Canteaut、Naya-Plasencia 和 Vayssière，CRYPTO 2013，中間篩攻擊是一種通用改進。這個想法是通過一個篩選過程來替換（部分）匹配，該過程丟棄中間 S-box 的無效轉換。中間的 S 盒可以是一個超級盒，因此您可以在許多密碼中獲得例如 2 輪。

MITM 作為一個總體構想（包括 Demirici-Selçuk）

線性和差分密碼分析中使用的第一輪/最後一輪技巧基本上是一種 MITM 攻擊。至少在某些情況下，猜測部分子密鑰的輪數可能非常大，因此基本上將密碼分為三部分，並在中間使案例如線性近似進行匹配。當然，這裡又是一堆專門的技術。

通常，此類攻擊中最重要的部分是找到正確的統計屬性，而不是關鍵猜測部分。這將它們與上述 MITM 攻擊區分開來，因此它們通常不被稱為 MITM 攻擊。

Demirici-Selçuk 攻擊是普遍稱為 MITM 攻擊但不屬於上述章節中描述的 MITM 攻擊之一的攻擊的一個很好的例子。

基本的 DS-MITM 是對基於 5 輪區分器的 AES 的攻擊。請注意，此區分器並不是真正的（簡單）方格攻擊。相反，由於 Gilbert 和 Minier，它是 4 輪區分器的擴展，這反過來又擴展了 3 輪 AES 的經典積分/平方區分器。5 輪區分器通過部分密鑰猜測擴展到 7 或 8 輪。我不會詳細介紹（這應該是一個不同的問題）。

只是為了大致了解這次攻擊的重要性，以下是對該主題的後續研究的簡要時間順序概述：

• Demirici 等人給出了一些改進。在INDOCRYPT 2009上改進了對 AES 的中間相遇攻擊。
• Dunkelman、Keller 和 Shamir在 ASIACRYPT 2010 上介紹了改進的 8 輪 AES 單密鑰攻擊的改進。他們介紹了多集製表、差分列舉（主要改進）和密鑰橋接。
• Derbez、Fouque 和 Jean 在 EUROCRYPT 2013 的改進密鑰恢復攻擊中對單密鑰設置中的縮減輪 AES 進行了進一步改進。
• Derbez 和 Fouque 在 FSE 2013 在Exhausting Demirci-Selcuk Meet-in-the-middle Attacks against Reduced-round AES中的其他改進。
• Li、Jia 和 Wang (FSE 2014)使用依賴於密鑰的篩選來獲得更好的 5 輪區分器（導致 9 輪攻擊的改進）。
• 我知道的最新（從 2016 年開始）改進歸功於Li 和 Lin，並擴展到 10 輪（注意：這是針對 AES-256 的）。

DS-MITM 攻擊也適用於其他密碼。例如，來自 ASIACRYPT 2018 的這篇論文使用約束程式來自動化流程，並將應用程序應用於幾個輕量級密碼。不過，並非所有的擴展（特別是差分列舉）都是自動化的。

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