中途相遇攻擊

提示：此條目的主題不是中間人攻擊。

中途相遇攻擊（英語：Meet-in-the-middle attack）是密碼學上以空間換時間的一種攻擊。

歷史

這個攻擊方式在1977年就由惠特菲爾德·迪菲（Diffie）與馬丁·赫爾曼（Hellman）提出來。

原理

一維中途相遇攻擊

假設$ENC$是加密函式，$DEC$是解密函式，也就是$ENC^{-1}$，而$k_{1}$與$k_{2}$為兩次加密用的秘鑰，則可以推導出：

${\begin{aligned}C&=ENC_{k_{2}}(ENC_{k_{1}}(P))\\P&=DEC_{k_{1}}(DEC_{k_{2}}(C))\\\Rightarrow ENC_{k_{1}}(P)&=DEC_{k_{2}}(C)\end{aligned}}$

當攻擊者已知明文$P$與密文$C$時，攻擊者可以窮舉所有$k_{1}$的組合，將產生出來的第一層密文$ENC_{k_{1}}(P)$，用大量空間儲存下來。再窮舉所有$k_{2}$的組合，將$DEC_{k_{2}}(C)$的值與前面儲存下來的結果比對，進而得出正確的$k_{1}$與$k_{2}$。

這使得攻擊者計算的量從$k_{1}$與$k_{2}$各自的可能組合數相乘，變成相加。

這也是為什麼三重資料加密演算法（3DES）使用了三把56 bits的秘鑰（168 bits），卻只有兩把秘鑰的強度（112 bits）。

參見

• 暴力破解法
• 三重資料加密演算法
• 資料加密標準