流密码Cube攻击中的密钥过滤技术与实现依赖分析

### 流密码Cube攻击中的密钥过滤技术与实现依赖分析 #### 1. 基于查表的密钥过滤技术 在识别满足 $p_I(x, IV) = \theta$ 的 $x_c$ 时，需要参考 $p_I$ 的真值表 $T_I$，其大小为 $2^{|J|}$，且需进行 $2^{|J|}$ 次查表操作来确定 $x[J]$ 的候选值。对于大规模超多项式（$J = [0, n)$），可采用一些技巧避免存储和遍历整个 $T_I$。 - **基于不相交集的密钥过滤**：对于多项式 $p(x)$ 中的变量，若在所有单项式中 $x_i$ 和 $x_j$ （$0 \leq i \neq j < n$） 从不相乘，则称它们不相交。若变量子集 $D$ 中任意变量对都不相交，则称 $D$ 为不相交集。给定不相交集 $D = \{x_0, x_1, \cdots, x_{\ell - 1}\}$，其余密钥变量集合为 $\overline{D} = \{x_0, x_1, \cdots, x_{n - 1}\} \setminus D$，超多项式可重写为线性组合： $p(x) = x_0 \cdot p_0(D) + x_1 \cdot p_1(D) + \cdots + x_{\ell - 1} \cdot p_{\ell - 1}(D) + p_{\ell}(D)$ 其中 $p(D)$ 仅包含 $D$ 中的变量，通常比 $p(x)$ 简单。这样，$p(x)$ 的大真值表可由 $p_0(D), p_1(D), \cdots, p_{\ell - 1}(D)$ 和 $p_{\ell}(D)$ 对应的子表替代。在密钥过滤阶段，猜测不相交集中的比特并依次参考相应子表。 - **多超多项式扩展与改进**：基于单个超多项式的密钥过滤过程可轻松扩展到多个超多项式。除了基于不相交集的密钥过滤方法，还有改进方法，即猜测一些密钥比特简化大规模超多项式，并动态构建真值表进行密钥过滤。所有真值表均使用 Möbius 变换技术构建，对于 $n$ 变量的布尔函数，Möbius 变换算法可通过 $n \cdot 2^{n - 1}$ 次异或操作构建其真值表。 #### 2. Kreyvium 的新攻击方法 目前，流密码的 Cube 攻击主要有两种策略： |策略|特点| | ---- | ---- | |大规模超多项式策略|使用低维立方体，但超多项式通常复杂| |传统策略|使用高维立方体以获取与极少数密钥比特相关的低次超多项式| 新的 898 -、899 - 和 900 - 轮 Kreyvium 的 Cube 攻击采用传统策略，具体构建立方体的步骤如下： - 由于 Kreyvium 的密钥和 IV 长度均为 128 位，选择最大可能的立方体维度 $|I| = m - 2 = 126$。 - 选择立方体索引以降低超多项式的次数，使用基于二子集划分性质的次数评估技术自然评估。 - 找到低次超多项式的立方体后，可直接使用相关方法恢复超多项式。 ##### 2.1 898 - 轮 Kreyvium 的新结果 对于 898 - 轮 Kreyvium，有许多 126 维的简单超多项式立方体。随机选取几个 126 维立方体，进行次数评估，选择次数最低的立方体。经多次试验，找到两个立方体 $I_0$ 和 $I_1$，次数评估分别为 2 和 3。 - $I_0 = [0, 127] \setminus \{5, 56\}$，其超多项式 $p_{I_0}(x, 0)$ 为： $p_{I_0}(x, 0) = x_{11} + x_{13} + x_{28} + x_{37} + x_{38} + x_{39} + x_{53} + x_{53}x_{54} + x_{55} + x_{62}x_{63} + x_{70} + x_{72} + x_{87} + x_{97} + x_{98} + x_{112} + x_{54}x_{112} + x_{113} + x_{53}x_{113} + x_{112}x_{113} + x_{114} + x_{123}$ - $I_1 = [0, 127] \setminus \{38, 86\}$，其超多项式 $p_{I_1}(x, 0)$ 见附录 A.2 中的式 (7)。 ##### 2.2 899 - 轮 Kreyvium 的新结果 按 898 - 轮的步骤，希望找到 126 维且超多项式次数较低（如 2 或 3）的立方体。但直接对 899 - 轮 Kreyvium 操作时，发现 126 维立方体中低次超多项式很少。因此采用新方法： 1. 对所有 127 维立方体进行次数评估，为进一步排除找到合适的索引。对于所有 $I_{\lambda} = [0, 127] \setminus \{\lambda\}$（$\lambda = 0, \cdots, 127$），使用基于传统划分性质的次数评估获取其超多项式的次数上界 $deg(p_{I_{\lambda}})$。仅 13 个 $\lambda$ 满足 $deg(p_{I_{\lambda}}) \leq 3$，将这些 $\lambda$ 存储在集合 $\Lambda$ 中： $\Lambda = \{ \lambda \in [0, 127] : deg(p_{I_{\lambda}}) \leq 3 \} = \{28, 29, 41, 47, 48, 49, 52, 55, 60, 61, 70, 74, 75, 79\}$ 2. 构建 126 维立方体 $I = [0, 127] \setminus \{29, 47\}$，次数评估 $deg(p_I) = 3$，使用相关方法恢复超多项式 $p_I$，其代数正规型（ANF）为： $p_I(x, 0) = x_2 + x_3 + x_8 + x_{10} + x_{11} + x_{10}x_{11} + x_{15} + x_{18} + x_{19} + x_{20} + x_6x_{20} + x_{21} + x_{24} + x_{28} + x_{29} + x_6x_{30} + x_{28}x_{34} + x_{20}x_{37} + x_{30}x_{37} + x_{34}x_{37} + x_{24}x_{38} + x_{39} + x_{20}x_{40} + x_{30}x_{40} + x_{41} + x_{28}x_{44} + x_{37}x_{44} + x_{45} + x_{51} + x_{52} + x_{39}x_{52} + x_{51}x_{52} + x_{34}x_{53} + x_{44}x_{53} + x_{34}x_{54} + x_{38}x_{54} + x_{44}x_{54} + x_{52}x_{54} + x_{34}x_{53}x_{54} + x_{44}x_{53}x_{54} + x_{34}x_{55} + x_{44}x_{55} + x_{20}x_{56} + x_{30}x_{56} + x_{62} + x_{54}x_{62} + x_{61}x_{62} + x_{63} + x_{34}x_{62}x_{63} + x_{44}x_{62}x_{63} + x_{34}x_{64} + x_{44}x_{64} + x_{63}x_{64} + x_{24}x_{63}x_{64} + x_{20}x_{65} + x_{24}x_{65} + x_{30}x_{65} + x_{20}x_{66} + x_{30}x_{66} + x_{66}x_{67} + x_{68} + x_{71} + x_{70}x_{71} + x_{72} + x_{74} + x_{77} + x_{78} + x_{77}x_{78} + x_{39}x_{77}x_{78} + x_{39}x_{79} + x_{80} +