中途相遇攻击

提示：此条目的主题不是中间人攻击。

中途相遇攻击（英语：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）。