中途相遇攻擊

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

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

歷史

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

原理

一維中途相遇攻擊

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

${\displaystyle {\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}}}$

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

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

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