線上性或差分密碼分析中攻擊 3DES 的複雜性是多少？
我知道 3DES 不易受到 DC 、 LC 的攻擊。但這是因為攻擊需要太多的輸入\輸出對嗎？還是因為不可能？（即需要超過 2^64 對）
“不易受攻擊”不是我要描述的方式，但我的理解是現有的對 DES 的攻擊不能直接不適用於 3DES。
目前，針對單個 DES 的最佳攻擊是線性攻擊，它需要 $ 2^{43} $ 明文-密文對，時間複雜度介於 $ 2^{39} $ 和 $ 2^{43} $ 操作。
線性密碼分析通過嘗試用一些線性函式來近似密碼的功能來工作，例如“如果我將所有輸入和輸出位插入我發現的這個多項式，我可以確定密鑰的第 26 位的值有信心72%”。給定這樣的近似值，可以訪問足夠多的明文和單個密鑰的相應密文的攻擊者可能能夠恢復整個密鑰，或者足夠的密鑰以對其餘密鑰進行暴力破解。
包括 DES 在內的許多分組密碼都通過 S-box 引入了非線性。雖然可能（甚至微不足道）產生單輪分組密碼的線性近似值，但對於大量輪次這樣做變得更加困難。假設一個好的設計，當你添加更多輪次時，函式可能的內部狀態數量會增加，而線性近似的統計顯著性會降低。這增加了您需要的明文-密文對和操作的數量，通常使其比暴力攻擊更不可行。
差分密碼分析以類似的方式工作。通過觀察輸入的變化如何通過每一輪傳播到輸出，有可能辨識出洩露有關輪密鑰資訊的行為。例如，可以選擇一對相似的消息值 $ m_1 $ 和 $ m_2 $ ，然後比較 $ m_1 \oplus m_2 $ 和 $ f_r(m_1, k_r) \oplus f_r(m_2, k_r) $ ， 在哪裡 $ f_r $ 和 $ k_r $ 分別是輪函式和輪鍵。每個單獨回合的統計分析，與它們對輸入微小變化的反應有關，可以結合在一起，以展示可用於確定完整密碼版本中回合密鑰值資訊的屬性，或在減少輪次的變體中（儘管這不會構成中斷）。
這裡要記住的是，諸如此類的攻擊依賴於攻擊者可以訪問大量明文及其相關密文以獲取他們希望恢復的密鑰。移除這種能力，或者充分抑制它，使得即使是平庸的密碼也很難找到實際的攻擊。
現在，這裡要回答的重要問題如下：是否可以重建對單個 DES 的現有攻擊，使其能夠針對 3DES 起作用，其中攻擊者只能訪問針對整個加密過程的預言機？（即攻擊者不知道 3DES 中中間步驟的值）。答案基本上是否定的。由於攻擊需要攻擊者知道每個DES 操作的大量明文-密文對，但在這種情況下攻擊者不知道 3DES 操作的中間值，因此原始攻擊不再直接相關 - 它不是不可能只“進行三次攻擊”。
相反，必須針對 3DES 制定新的攻擊，使用與先前攻擊相同的觀察作為建構塊，但將它們應用於完整的 3DES 操作。3DES 可以被認為是 DES 的 48 輪變體，因為每一輪 DES 都是相同的（除了密鑰調度，但這與 LC 和 DC 攻擊無關）。現在這意味著針對 3DES 的全輪攻擊需要所有 48 輪的線性近似，或者可以在整個 48 輪中關聯的差分屬性。這是非常困難的——比針對單個 DES 本身要困難得多。
針對三重加密的“典型”攻擊就是所謂的中間相遇攻擊。在這種針對 3DES 的攻擊中，我們分別處理每個 DES 操作，並攻擊單個明文-密文對。首先，我們對所有可能的密文進行解密操作 $ 2^{56} $ 密鑰，並將生成的解密塊儲存在列表中。這需要 $ 2^{56} \times 64 $ 位空間，或 512 PB。接下來，我們針對每個可能的密鑰對明文執行前兩次 DES 加密操作（即暴力破解整個 112 位密鑰空間），直到我們得到與先前計算的列表中的條目匹配的輸出。一旦找到匹配項，我們就知道我們找到了正確的密鑰。本次攻擊的時間複雜度為 $ 2^{112} + 2^{56} $ , 可以近似為 $ 2^{112} $ 由於指數的巨大差異。
這個基本思想已經針對 DES 進行了一些改進——最著名的攻擊需要 $ 2^{32} $ 已知明文， $ 2^{113} $ 操作（包括 $ 2^{90} $ DES 加密和其餘更快的操作），以及 $ 2^{88} $ 記憶。雖然從數字上講，這比直接中間相遇有更多的操作，但這些操作中的很大一部分在實踐中要快得多。因此，操作數量本身並不能說明實際計算成本的全部情況，並且攻擊比天真的中間相遇更快。