中間相遇的成功機率
在 Bruce Schneier 的 Apllied Crypto 的第 358 頁中，在解釋中間相遇攻擊時，他指出成功機率為 «1 in $ 2^{2m - 2n} $ » 有兩個明文/密文對，和 «1 in $ 2^{3m - 2n} $ » 如果使用一對額外的 pt/ct 對。 $ n $ 是密鑰長度，並且 $ m $ 塊長度。
我的問題是：不應該 $ m $ 和 $ n $ 被逆轉？即«1英寸 $ 2^{2n - 2m} $ » 和 «1 英寸 $ 2^{2n - 3m} $ »? 如書中所述，當使用 3 對時，我們會獲得較低的成功機率，如 «1 in $ 2^{2m - 2n} $ » 的機率大於 «1 in $ 2^{3m - 2n} $ “ （因為 $ 2^{3m - 2n} $ > $ 2^{2m - 2n} $ ).
或者有什麼我沒有看到的明顯的東西？
在句子中，«1 in的*“成功機率”* $ 2^{2m - 2n} $ » 或 «1 英寸 $ 2^{3m - 2n} $ » 確實是找到密鑰的機率的近似值，而實際上另一個密鑰恰好給出與 2 或 3 個塊的真實密鑰相同的結果。
應該改為*“錯誤地得出成功的機率”；或“誤報機率”*。
我們得到兩個明文/密文對 $ (P_1, C_1) $ 和 $ (P_2, C_2) $ 和 $ E_{k_1^}(P_i) = D_{k_2^}(C_i) $ 真正的關鍵在哪裡 $ k^* = (k_1^, k_2^) $ . 假設密鑰是 $ n $ 位長，塊是 $ b $ 位長。（施奈爾使用 $ m $ 對於塊大小，但由於混淆了最小值，我無法保持這些字母筆直，所以我將使用更明智的字母 $ b $ 塊大小。）
讓我們建模 $ k_i^* $ 作為獨立的統一隨機位串，因為這是明智的使用者選擇它們的方式。為簡單起見，讓我們建模 $ E_{k_1} $ 和 $ D_{k_2} $ 作為獨立的均勻隨機函式。顯然這個模型是錯誤的，因為它們都是排列，如果 $ k_1 = k_2 $ 那麼他們不能獨立，但是 $ \Pr[k_1 = k_2] = 1/2^n $ 所以這個事件只發生在很小的一部分時間裡，而且所有的模型都是錯誤的——有些只是有用的。
假設我們找到一個候選鍵 $ k = (k_1, k_2) $ 這樣 $ E_{k_1}(P_1) = D_{k_2}(C_1) $ . 發生的機率是多少 $ k = k^* $ 考慮到這一點——也就是說，在我們找到匹配的候選者的情況下，我們找到真正密鑰的機率是多少？
先驗的 $ \Pr[k = k^] = 2^{-2n} $ 因為真正的鑰匙 $ k^ $ 均勻分佈在 $ 2^{2n} $ 可能性。顯然，如果 $ k = k^* $ ， 然後 $ E_{k_1}(P_1) = D_{k_2}(C_1) $ 有機率 $ 1 $ ; 而如果 $ k \ne k^* $ ，則在獨立均勻隨機函式模型中為 $ E $ 和 $ D $ ， 我們有 $ E_{k_1}(P_1) = D_{k_2}(C_1) $ 有機率 $ 2^{-b} $ . 無條件機率_ $ E_{k_1}(P_1) = D_{k_2}(C_1) $ 是
$$ \begin{align*} \Pr&\bigl[E_{k_1}(P_1) = D_{k_2}(C_2)\bigr] \ &= \Pr[E_{k_1}(P_1) = D_{k_2}(C_2) \bigm| k = k^\bigr] \Pr[k = k^] \ &\qquad + \Pr[E_{k_1}(P_1) = D_{k_2}(C_2) \bigm| k \ne k^\bigr] \Pr[k \ne k^] \ &= 2^{-2n} + 2^{-b} (1 - 2^{-2n}). \end{align*} $$
因此，根據貝氏規則，在與已知明文/密文對匹配的情況下，密鑰正確的條件機率為
$$ \begin{align*} \Pr&\bigl[k = k^* \bigm| E_{k_1}(P_1) = D_{k_2}(C_1)\bigr] \ &= \Pr[k = k^] \frac{\Pr\bigl[E_{k_1}(P_1) = D_{k_2}(C_2) \bigm| k = k^\bigr]} {\Pr\bigl[E_{k_1}(P_1) = D_{k_2}(C_2)\bigr]} \ &= 2^{-2n} \frac{1} {2^{-2n} + 2^{-b}(1 - 2^{-2n})} \ &= \frac{1}{1 + 2^{-b} (2^{2n} - 1)} \ &= \frac{2^b}{2^b + 2^{2n} - 1}. \end{align*} $$
為了 $ b \ll 2n $ , 這大概是 $ 2^{b - 2n} $ . 為了 $ b = 2n $ , 這大概是 $ 1/2 $ . 為了 $ b \gg 2n $ , 這大概是 $ 1 $ .
如果我們也確認怎麼辦 $ E_{k_1}(P_2) = D_{k_2}(C_2) $ ? 然後大致就好像塊大小是 $ 2b $ 代替 $ b $ 在上述分析中，因為我們正在考慮是否 $ E’{k_1}(P_1, P_2) = D’{k_2}(C_1, C_2) $ 在哪裡 $ E’{k_1}(P_1, P_2) = \bigl(E{k_1}(P_1), E_{k_1}(P_2)\bigr) $ 同樣對於 $ D’ $ . 在這種情況下，真陽性的條件機率約為 $ 2^{2b - 2n} $ ， 或者 $ 2^{3b - 2n} $ 三個塊，以此類推，直到塊的總大小達到組合密鑰的大小，此時機率迅速收斂到 $ 1 $ .
總之，我認為 Schneier 混淆了“成功機率”（更好地命名為“真正的肯定機率”）的含義是正確的：它應該是 $ 2^{2m - 2n} $ , $ 2^{3m - 2n} $ 等，不 $ 1 $ 在 $ 2^{2m - 2n} $ , $ 1 $ 在 $ 2^{3m - 2n} $ 等，其中 $ m $ 是容易混淆的塊大小。
這是一本充滿嚴重智力傷害的書中的一個小錯誤。