Classical MITM

在 Hellman 的文章Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard中给出了中间相遇攻击的基本概念。

首先需要意识到，中间相遇攻击也是穷举，但是结合了 TMTO 的思想，通过建表存一部分值，穷搜另一部分值来达到比穷举攻击更好的效益。

经典MITM： 有迭代的分组密码，分组长度为 $nn$ ，子密钥可独立的分为 $K_1\mathrm{\mid }\mathrm{\mid }{K}_{2}K\_1||K\_2$

MITM stage

1. 任取明密文对 $(P,C)(P,C)$ ，将密钥做以下划分：
   前向轮密钥记为 $K_{1}K\_1$ ，后向轮密钥记为 $K_{2}K\_2$
2. 用前向的密钥对明文加密得到中间值 $UU$ ；同样的，用后向的密钥对密文解密得到中间值 $VV$
3. 匹配中间值，判断 $U\stackrel{?}{}VU\backslash overset\{?\}\{=\}V$ 如果是，则将使用的密钥（全部bit）存入候选密钥表中，否则丢弃（在该过程中，可能会有一些随机值也能够匹配）

Testing stage

再次任选明密文对 $(P_1,C_1)(P\_1,C\_1)$ 并对候选密钥表进行二次筛查，重复步该过程直至候选密钥表中仅剩 1 个密钥，即为正确密钥。

NOTE：

1. 以上过程如果能够保证前向和后向密钥能够覆盖全密钥空间，则在匹配到 $U=VU=V$ 时即可能得到正确密钥，但不能保证随机值导致的误报不会出现（这里总可能数为 $2^{\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid }}2^\{|K\_1|+|K\_2|\}$ ，但匹配的长度为 $2^{n}2^\{n\}$，明显 $\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid }>n|K\_1|+|K\_2|\; >\; n$（安全标准），所以产生的中间值肯定会有很多误报）假设这里能够此处匹配到的概率是 $2^{-n}2^\{-n\}$ ，而全可能密钥数为 $2^{\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid }}2^\{|K\_1|+|K\_2|\}$ ，所以筛选留下的密钥数为 $2^{\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid }-n}2^\{|K\_1|+|K\_2|-n\}$，这需要在后续的测试阶段不断筛选；
2. 能够使用经典中间相遇攻击的前提是子密钥的独立性。

复杂度分析

时间复杂度：将更大的密钥拿来查询（内存比时间更贵），所以时间复杂度为：

空间复杂度：将更小的密钥拿来查询，所以空间复杂度为：

数据复杂度：留下的候选密钥 $\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid }-nbits|K\_1|+|K\_2|-n\backslash \; bits$ 而对每个新的明密文对， 理想情况下会筛掉 $nbitsn\backslash \; bits$ ，所以数据复杂度为：

（这里没有考虑建表和查表的时间，后面也不会考虑，如果考虑，通过较优化的算法如快速排序，二分查找之类，建表并排序的时间大概为 $2^{log(min(2^{K_1},2^{K_2}))}2^\{log(min(2^\{K\_1\},2^\{K\_2\}))\}$，查表时间大概为 $2^{log(max(2^{K_1},2^{K_2}))}2^\{log(max(2^\{K\_1\},2^\{K\_2\}))\}$）