DES 增強的弱點

為了增加通過窮舉搜尋找到密鑰的複雜性，提出了對 DES 的以下密鑰增強。

$$ \text{DES}^V_{k,k_1}(M)=\text{DES}_k(M)\oplus k_1 $$ 鍵的長度在哪裡 $ |k|=56 $ 和 $ |k_1|=64 $ ( $ k_1 $ 具有與塊長度相同的長度）。表明該提議不會增加使用暴力密鑰搜尋破解密碼系統的複雜性。也就是說，展示如何使用以下順序來打破這些方案 $ 2^{56}\ \text{DES} $ 加密/解密。

你可以假設你有適量的明文-密文對， $ C_i=\text{DES}^V_{k,k_1}(M_i) $ .

讓 $ r $ 是索引的對數 $ 1 $ 至 $ r $ .

我定義 $ \forall\ l\in{0,1}^{56},\ i\in{1,\dots,r}:\text{K}(l,i) = \text{DES}_l(M_i)\oplus C_i $ .

我對對手的建議是：

for every l of size 56:
    for i = 1,...,n:
         compute K(l, i)
    if for all i != j : K(l,i) == K(l,j)
         return <l,K(l,1)> as the keys of the cryptosystem

確實，如果在某個迭代中 $ l=k $ 在返回之前，所有 $ \text{K}(l,i) $ 將等於 $ k_1 $ （根據新密碼系統的定義），所以我們將返回 $ k,k_1 $ 作為鑰匙。

但是，我認為對於某些人來說，這是可能的 $ l\neq k $ 這 $ \text{if} $ 在第二 $ \text{for} $ 循環將得到滿足，因為我們只檢查少量消息。在這種情況下，如果我們遇到 $ l $ 見面前 $ k $ 算法的返回將是錯誤的。

問題

是否有可能以給定的複雜性確定性地破解密碼系統，或者我們必須允許一些錯誤機率？

是否有可能以給定的複雜性確定性地破解密碼系統，或者我們必須允許一些錯誤機率？

如果我們將 DES 建模為隨機排列，則總是有一定的機率會導出錯誤的密鑰或找到多個密鑰。

如果我們有 $ n $ 明文/密文對，存在第二個偽密鑰的非零機率恰好將每個明文映射到相應的密文。如果我們的蠻力搜尋在它找到的第一個鍵處停止，它可能會在錯誤的鍵處停止。如果我們的蠻力搜尋繼續尋找它找到的第一個鍵，它會找到第二個（並因此報告多個）。

現在，這種情況發生的實際可能性很小；如果 $ n=2 $ ，那麼你的例子中的機率大約是 $ 2^{-8} $ （很小，但不可忽略），但是如果 $ n=3 $ （“適度”一詞似乎我們至少有這麼多），機率下降到大約 $ 2^{-72} $ .

此外，攻擊者通常不太關心失敗的小機率。當我們保護數據時，我們希望以壓倒性的可能性成功（在這種情況下，是安全的）；但對於攻擊者來說，情況並非如此……

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