對 DES-X 的選擇明文攻擊2642642^{64}運營
這是 P. Rogaway 的引述，DESX 的安全性
“DESX 對密鑰搜尋的有效密鑰長度至少為 55 + 63 - lg(m) 位”
其中 m 是選擇的明文/密文對的數量。
那麼我怎樣才能大致攻擊 DES-X $ 2^{64} $ DES 操作假設我們有無限的儲存空間？
我知道一個簡單的詳盡的關鍵搜尋（〜 $ 2^{120} $ DES 操作）可以優化為 $ 2^{118} $ DES 操作由關鍵互補屬性。
如果我們有更多的明文/密文對，這個屬性有什麼幫助？
如果我們有 $ 2^{64} $ $ (p,c) $ 對，我們如何使用它來恢復所有 3 個密鑰？我只能想到使用 2 $ (p,c) $ 對擺脫 $ k_2 $ 通過簡單地對它們進行異或。
我將問題視為：所有明文/密文對 $ (p,c=\operatorname{DESX}(p)) $ 手頭，我們如何有效地找到DESX密鑰 $ (K_1,K_2,K_3) $ ?
主要思想是觀察（獨立於 DES 互補屬性），對於任何固定的 $ \delta\ne0 $ , $ \operatorname{DESX}(p)\oplus\text{DESX}(p\oplus \delta) $ 火柴 $ \text{DES}{K_2}(0)\oplus\text{DES}{K_2}(\delta) $ 什麼時候 $ p=K_1 $ ，但很少有其他值。我們可以計算第二個數量作為候選的函式 $ K_2 $ , 並蒐索哪個 $ p=K_1 $ 匹配明文/密文對（按順序排列），然後檢查該猜測是否正確。
DES 互補屬性指出 $ \operatorname{DES}{\overline K}(\overline p)=\overline{\operatorname{DES}K(p)} $ . 這建議優先使用 $ \delta=\overline0 $ ，這有助於 $ \operatorname{DES}{K_2}(0)\oplus\operatorname{DES}{K_2}(\overline 0)=\operatorname{DES}\overline{K_2}(0)\oplus\operatorname{DES}\overline{K_2}(\overline 0) $ .
攻擊將因此進行：
計算¹所有 $ \Delta(p)=\operatorname{DESX}(p)\oplus\text{DESX}(\overline p) $ 為了 $ p $ 清除其高位，並在資料結構中跟踪它們，從而可以有效地搜尋 $ p $ 產生一個給定的 $ \Delta(p) $ . 平均有 $ 1 $ 這樣的64位 $ p $ 對於每個 64 位 $ \Delta $ ，並且始終是偶數，因為 $ \Delta(p)=\Delta(\overline p) $ .
為了 $ K_2 $ 高位清零，其他 $ 55 $ 重要位按順序變化：
計算² $ \Delta=\operatorname{DES}{K_2}(0)\oplus\operatorname{DES}{K_2}(\overline 0) $ .
如果一個 $ p $ 火柴 $ \Delta $ （有機率 $ \approx1-e^{-1/2}\approx39% $ ):
計算² $ \Delta_1=\operatorname{DES}{K_2}(0)\oplus\operatorname{DES}{K_2}(1) $ .
對於每個候選人 $ p $ 和 $ \Delta(p)=\Delta $ （我們的資料結構列出了那些高位清晰的，我們補充得到它們）：
測試¹如果 $ \operatorname{DESX}(p)\oplus\text{DESX}(p\oplus1)=\Delta_1 $ . 當這種情況成立時（這是非常罕見的）：
- 測試¹ , ² 如果 $ \operatorname{DESX}(p)\oplus\text{DESX}(p\oplus2)=\operatorname{DES}{K_2}(0)\oplus\operatorname{DES}{K_2}(2) $ . 當這種情況成立時，我們幾乎可以肯定擁有³權利 $ K_2 $ 和 $ K_1=p $ . 匹配的 $ K_3 $ 是 $ \operatorname{DESX}(p)\oplus\operatorname{DES}_{K_2}(0) $ .
預期計算成本為 $ \approx(3-e^{-1/2}),2^{54}\approx0.6\times2^{56} $ DES 操作，忽略記憶體和記憶體訪問（在實踐中可能占主導地位）。DES 互補屬性通過允許限制為 $ K_2 $ 高位清零。
¹ 使用我們的 $ (p,c) $ 對。
² 使用DES引擎。
³ 在我們找不到的極性範圍內，因為 DES 互補屬性意味著 DESX 密鑰 $ (\overline{K_1},\overline{K_2},\overline{K_3}) $ 相當於 $ (K_1,K_2,K_3) $ .