中间相遇攻击 - MITM¶

概述¶

中间相遇攻击是一种以空间换取时间的一种攻击方法，1977年由 Diffie 与 Hellman 提出。从个人角度看，者更多地指一种思想，不仅仅适用于密码学攻击，也适用于其他方面，可以降低算法的复杂度。

基本原理如下

假设 E 和 D 分别是加密函数和解密函数，k1 和 k2 分别是两次加密使用的密钥，则我们有

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

$P=D_{k_2}(D_{k_1}(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 的中间相遇攻击类似。