中間相遇攻擊 - MITM¶

概述¶

中間相遇攻擊是一種以空間換取時間的一種攻擊方法，1977年由 Diffie 與 Hellman 提出。從個人角度看，者更多地指一種思想，不僅僅適用於密碼學攻擊，也適用於其他方面，可以降低算法的複雜度。

基本原理如下

假設 E 和 D 分別是加密函數和解密函數，k1 和 k2 分別是兩次加密使用的密鑰，則我們有

$C=E_{k_2}(E_{k_1}(P))$

$P=D_{k_1}(D_{k_2}(C))$

則我們可以推出

$E_{k_1}(P)=D_{k_2}(C)$

那麼，當用戶知道一對明文和密文時

攻擊者可以枚舉所有的 k1，將 P 所有加密後的結果存儲起來，並按照密文的大小進行排序。
攻擊者進一步枚舉所有的k2，將密文 C 進行解密得到 C1，在第一步加密後的結果中搜索 C1，如果搜索到，則我們在一定程度上可以認爲我們找到了正確的 k1 和 k2。
如果覺得第二步中得到的結果不保險，則我們還可以再找一些明密文對進行驗證。

假設 k1 和 k2 的密鑰長度都爲 n，則原先我們暴力枚舉需要 $O(n^2)$ ，現在我們只需要 $O(n log_2n)$ 。

這與 2DES 的中間相遇攻擊類似。