DES Bruteforce 攻擊和誤報密鑰

我已經讀過，如果密鑰空間大於塊空間，蠻力攻擊（無論使用哪種塊密碼）都可能導致誤報。我很清楚這是由於鴿子洞原理（如果我有比可用塊更多的鍵，我遲早會為同一個映射使用兩個不同的鍵）。

我的問題是，如果密鑰空間約為 $ 2^{56} $ 塊空間是 $ 2^{64} $ .

我對這些前提的期望是，給定明文和所有可能的密鑰，並非所有可能的密文都會得到解決。

我的問題是，如果密鑰空間約為 $ 2^{56} $ 塊空間是 $ 2^{64} $

讓我們假設攻擊者有一個明文/密文對，即兩個八字節值 $ P, C $ 和 $ C = \text{DES}_k(P) $ ， 在哪裡 $ k $ 是正確的未知密鑰。

然後，讓我們考慮值 $ \text{DES}_{k’}(P) $ ; 那裡 $ k’ $ 範圍超過 $ 2^{56}-1 $ 可能不正確的鍵。如果我們用不正確的密鑰將 DES 建模為隨機排列，那麼我們得到的是一個列表 $ 2^{56}-1 $ 隨機 8 字節值，每個值都有一個 $ 2^{-64} $ 恰好發生的機率 $ C $ .

因此，期望值的倍數 $ C $ 出現在該列表上的是 $ (2^{56}-1)2^{-64} \approx 2^{-8} $ （以及該值的機率 $ C $ 在列表中至少出現一次是小一點）。

因此，確實存在蠻力搜尋會找到兩個鍵的非平凡機率。正確的鑰匙 $ k $ , 和另一個鍵 $ k’ $ 恰好映射 $ P $ 至 $ C $ .

當然，在實踐中，我們永遠不會真正只得到一個明文塊和一個密文塊；我們通常會得到額外的密文塊，至少會嘗試解密，看看它們是否有意義；這將使我們能夠區分正確的密鑰和任何不正確的密鑰。

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