中途相遇攻击

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

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

参见

• 暴力破解法
• 三重资料加密算法
• 资料加密标准