MITM variant No.ThreE (All Subkey Recovery)

原始文章： All Subkeys Recovery Attack on Block Ciphers: Extending Meet-in-the-Middle Approach

从经典中间相遇攻击而来，考虑到经典中间相遇攻击的局限性：

1. 需要子密钥相互独立，不独立情况见 “MITM variant No.TwO (3 subset)” 部分

2. 由于密钥编排算法的限制，可能无法在仅获得部分子密钥的情况下获取主密钥

ASR 攻击注意针对第 2 个局限进行改进，即试图使用中间相遇的思想来恢复全部子密钥，从而忽略密钥编排算法的影响，如果密钥编排可逆，也可以利用所有子密钥恢复主密钥。

ASR attack

假设分组密码分组长度为 $nn$ ，加密函数为 $EE$ ，有 $RR$ 轮，且每轮使用不同的加密子密钥，子密钥不需要全部独立（但需要有部分独立的情况存在）

MITM stage

1. 攻击者确定中间碰撞状态 $S(s-bits)S\backslash \; (s-bits)$ ；这个过程并不能独立后面的步骤，和 $K_1,K_{2}K\_1,K\_2$ 的选取有很大关系

   状态 $SS$ 可以从两个方向计算得来，即 $S=F_1(P,K_1)=F_2^{-1}(C,K_2)S=F\_\{1\}(P,K\_1)\; =\; F\_2^\{-1\}(C,K\_2)$ ，其中 $F_1,F_{2}F\_1,F\_2$ 分别是前向和后向的（部分）加密函数

   但并不是仅有 $K_1,K_{2}K\_1,K\_2$ 就可以从明文加密到密文，还有剩余没有用上的密钥 $K_{3}K\_3$ ，所以有 $\mid {\mathcal{K}}_{(1)}\mid +\mid {\mathcal{K}}_{(2)}\mid +\mid {\mathcal{K}}_{(3)}\mid =R\cdot \mathrm{\ell }\backslash left|\backslash mathcal\{K\}\_\{(1)\}\backslash right|+\backslash left|\backslash mathcal\{K\}\_\{(2)\}\backslash right|+\backslash left|\backslash mathcal\{K\}\_\{(3)\}\backslash right|=R\; \backslash cdot\; \backslash ell$

   对于此处的 $K_1,K_{2}K\_1,K\_2$ ，需要能够保证 $F_1(P,K_1)=F_2^{-1}(C,K_2)F\_\{1\}(P,K\_1)\; =\; F\_2^\{-1\}(C,K\_2)$ 的计算是独立的；

2. 将 $min(K_1,K_2)min(K\_1,K\_2)$ 得到的 $(P\mathrm{/}C,S)(P/C,S)$ 拿来存表，而另一部分用来做匹配，如果能够在状态 $SS$ 匹配到，即 $S=F_1(P,K_1)=F_2^{-1}(C,K_2)S=F\_\{1\}(P,K\_1)\; =\; F\_2^\{-1\}(C,K\_2)$ ，则将使用的密钥 $K_1,K_{2}K\_1,K\_2$ 加入候选密钥表；

3. 考虑到并行操作，可以对多个明密文对并行操作进行步骤 2.

Test Stage

同样的，使用不同明密文对测试，但测试的不是是否能够从明文加密到密文，因为整个过程没有考虑 $K_{3}K\_3$ ，而是测试使用不同的明密文能否找到状态 $SS$ 的匹配 ？ 是这样吗？？

NOTE

1. 在步骤 2. 有 $2^{-s}2^\{-s\}$ 的概率在状态 $SS$ 匹配到，而总可能密钥数为 $2^{R\ast l}2^\{R*l\}$ 所以留下的候选密钥为 $2^{R\ast l-s}2^\{R*l-s\}$ 个，而并行使用 N 个明密文对留下的候选密钥就为 $2^{R\ast l-N\ast s}2^\{R*l-N*s\}$ 个；

2. 这里可以并行使用的明密文对数量 N 为，需要有一定的限制：

   $2^{R\ast l-N\ast s}\le 2^{R\ast l-(\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid })}2^\{R*l-N*s\}\; \backslash leq\; 2^\{R*l-(|K\_1|+|K\_2|)\}$ 即 $N\le (\mathrm{\mid }{K}_1\mathrm{\mid }+\mathrm{\mid }{K}_2\mathrm{\mid })\mathrm{/}sN\backslash leq(|K\_1|+|K\_2|)/s$，如果不满足，则意味着使用 $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 }}2^\{|K\_1|+|K\_2|\}$ 个密钥，这是不合理的；

复杂度分析

• 时间复杂度：选 $\mathrm{\mid }{K}_1\mathrm{\mid },\mathrm{\mid }{K}_2\mathrm{\mid }|K\_1|,|K\_2|$ 更大的用来做匹配，对 N 个明密文对，就需要 $\max (2^{\mid {\mathcal{K}}_{(1)}\mid },2^{\mid {\mathcal{K}}_{(2)}\mid })\times N\backslash max\; \backslash left(2^\{\backslash left|\backslash mathcal\{K\}\_\{(1)\}\backslash right|\},\; 2^\{\backslash left|\backslash mathcal\{K\}\_\{(2)\}\backslash right|\}\backslash right)\; \backslash times\; N$ 的计算，而对剩余的密钥 $K_{3}K\_3$ 就需要穷举，需要 $2^{R\cdot \mathrm{\ell }-N\cdot s}2^\{R\; \backslash cdot\; \backslash ell-N\; \backslash cdot\; s\}$ 的计算，所以总时间复杂度为：

• 空间复杂度：选 $\mathrm{\mid }{K}_1\mathrm{\mid },\mathrm{\mid }{K}_2\mathrm{\mid }|K\_1|,|K\_2|$ 更小的用来建表，对 N 个明密文对，总空间复杂度为：

• 数据复杂度：并行 N 个不同的明密文对，在测试阶段，留下密钥 $R\ast l-N\ast sR*l-N*s$ bits，因为分组长度为 n ，所以每个新的明密文对可以筛掉 n bits（注意这个过程：$P\to E_k\to CP\; \backslash rightarrow\; E\_k\; \backslash rightarrow\; C$ ，这里的 ${}_k\_k$ 会遍历所有留下的候选密钥，而理论上会有 n 个被筛掉）所以需要进行 $\lceil (R\cdot \mathrm{\ell }-N\cdot s)\mathrm{/}n\rceil \backslash lceil(R\; \backslash cdot\; \backslash ell-N\; \backslash cdot\; s)\; /\; n\backslash rceil$ 次筛查，数据复杂度为：