MITM variant No.TwO (3 subset)

从经典的 MITM 考虑，如果子密钥不能独立，那么建表和穷举部分都无法独立进行，参考文章A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN 和文章Three-Subset Meet-in-the-Middle Attack on Reduced XTEA 了解使用 3 子集来构造具有独立性的子密钥集合，并结合穷举和经典 MITM 来进行中间相遇攻击。 术语解释：

$K=k_{\mathrm{\ell }-1}{k}_{\mathrm{\ell }-2}\dots k_1{k}_0\text{ be the }\mathrm{\ell }\text{-bit key. }K=k\_\{\backslash ell-1\}\; k\_\{\backslash ell-2\}\; \backslash ldots\; k\_\{1\}\; k\_\{0\}\; \backslash text\; \{\; be\; the\; \}\; \backslash ell\; \backslash text\; \{-bit\; key.\; \}$

$K_1=\{k_i:k_i\text{ used by }{\phi }_{1,\alpha }\}K\_\{1\}=\backslash left\backslash \{k\_\{i\}:\; k\_\{i\}\; \backslash text\; \{\; used\; by\; \}\; \backslash varphi\_\{1,\; \backslash alpha\}\backslash right\backslash \}$

$K_2=\{k_i:k_i\text{ used by }{\phi }_{R-\beta +1,R}\}K\_\{2\}=\backslash left\backslash \{k\_\{i\}:\; k\_\{i\}\; \backslash text\; \{\; used\; by\; \}\; \backslash varphi\_\{R-\backslash beta+1,\; R\}\backslash right\backslash \}$

$A_0=K_1\cap K_{2}A\_\{0\}=K\_\{1\}\; \backslash cap\; K\_\{2\}$是在前向 $\alpha \backslash alpha$ 和后向 $\beta \backslash beta$ 都使用的密钥 比特

$K=K_1\cup K_{2}K\; =\; K\_1\; \backslash cup\; K\_2$

NOTE:明确一点：$K,K_{i}K,K\_i$ 是以密钥个为单位，$AiAi$ 以比特为单位；

$A_1=K_1\mathrm{\backslash }{K}_1\cap K_2\text{ and }{A}_2=K_2\mathrm{\backslash }{K}_1\cap K_{2}A\_\{1\}=K\_\{1\}\; \backslash backslash\; K\_\{1\}\; \backslash cap\; K\_\{2\}\; \backslash text\; \{\; and\; \}\; A\_\{2\}=K\_\{2\}\; \backslash backslash\; K\_\{1\}\; \backslash cap\; K\_\{2\}$ 就比较好理解，这里 \ 表示除去而非经典数学的除法。例如：

密钥总位数为 $32bits32\backslash \; bits$;相关部分为 $\mathrm{\mid }{A}_0\mathrm{\mid }=21bits|A\_0|\; =\; 21\backslash \; bits$ 那么 $\mathrm{\mid }{A}_1\mathrm{\mid }=\mathrm{\mid }{A}_2\mathrm{\mid }=11bits|A\_1|=|A\_2|=11\backslash \; bits$

3-subset MITM： 有迭代的分组密码，分组长度为 $nn$ ，子密钥不独立的分为 $K_1,K_{2}K\_1,K\_2$，有 $A_{0}bitsA\_0\backslash \; bits$ 为公用密钥，$A_1=K_1\mathrm{\backslash }{K}_1\cap K_{2}bits\text{ and }{A}_2=K_2\mathrm{\backslash }{K}_1\cap K_{2}bitsA\_\{1\}=K\_\{1\}\; \backslash backslash\; K\_\{1\}\; \backslash cap\; K\_\{2\}\backslash \; bits\backslash \; \backslash text\; \{\; and\; \}\backslash \; A\_\{2\}=K\_\{2\}\; \backslash backslash\; K\_\{1\}\; \backslash cap\; K\_\{2\}\backslash \; bits$

MITM stage

对任意一个明密文对 $(P,C)(P,C)$

1. 穷举所有 $A_{0}bitsA\_0\backslash \; bits$ ，并对每一种 $A_{0}A\_0$ 情况，进行步骤 2. 3.；
2. 将 $A_{0}A\_0$ 与 $A_{1}A\_1$ 拼接获得 $K_{1}K\_1$，前向加密得到中间值 $UU$，将所有 $UU$ 存入表 $TT$;
3. 将 $A_{0}A\_0$ 与 $A_{2}A\_2$ 拼接获得 $K_{2}K\_2$，向后解密得到中间值 $VV$，将所有 $VV$ 与表 $TT$ 中所有值进行匹配（不一定匹配中间值的全部比特），匹配到的值存入候选密钥表 $T_{vc}T\_\{vc\}$ 中;

Testing Stage

和经典 MITM 相同，再任选不同的明密文对，对表 $T_{vc}T\_\{vc\}$ 进行筛查，直到仅留下 1 个密钥。这里使用的明密文对数量和 $\mathrm{\mid }{A}_0\mathrm{\mid }|A\_0|$ 有关，显然是成反比的。

复杂度分析

不考虑并行明密文对，这里的 $A_0,A_1,A_{2}A\_0,A\_1,A\_2$ 表示密钥的长度$\mathrm{（}bits)（bits)$：

时间复杂度：建表时间 $2^{A_0}\ast 2^{A_1}2^\{A\_0\}*2^\{A\_1\}$ ，匹配时间 $2^{A_0}\ast 2^{A_2}2^\{A\_0\}*2^\{A\_2\}$ ，总时间：

空间复杂度：

数据复杂度：假设中间值匹配的位数为 ，则留下的候选密钥为 $A_0(A_1+A_2)-mbitsA\_0(A\_1+A\_2)\; -\; m\backslash \; bits$，所以测试需要的明密文对为：