针对KNOT-AEAD家族全体成员的条件立方体攻击

### 针对 KNOT - AEAD 家族全体成员的条件立方体攻击 #### 1. 背景介绍 在安全信息系统中，保障源数据的机密性以及加密/解密数据的完整性至关重要。传统上，源数据通过诸如分组密码之类的加密方案处理，而加密/解密数据则通过消息认证码（MAC）进行验证。近年来，一种名为带关联数据的认证加密（AEAD）的新型对称密钥原语崭露头角。AEAD 原语能够同时提供机密性和完整性，避免了分别使用加密和认证算法所导致的性能损失，因此其设计和密码分析吸引了众多密码学家的关注。 KNOT - AEAD 是 KNOT 套件中的 AEAD 算法，由 Zhang 等人设计，是美国国家标准与技术研究院（NIST）轻量级密码标准化过程第二轮的 32 个候选算法之一。KNOT - AEAD 家族有四个成员，它们在密钥大小、速率和内部状态大小上存在差异。此前已有一些关于 KNOT 安全性的研究，但从代数攻击（如立方体类攻击）的角度对 KNOT - AEAD 进行的第三方密码分析尚属空白。因此，评估 KNOT - AEAD 家族在初始化阶段抵御立方体类攻击的安全性具有重要意义。 #### 2. 预备知识 - **符号说明**： - 设 \(F_2\) 表示包含两个元素（0 和 1）的有限域，\(a \in F_2^n\) 是一个 \(n\) 位向量，其中 \(a_i\) 表示 \(a\) 的第 \(i\) 位。 - 单位向量（第 \(i\) 个元素为 1，其余为 0）记为 \(e_i\)。 - \(n\) 位全 0 向量记为 \(0_n\)，全 1 向量记为 \(1_n\)。 - 两个向量 \(a \in F_2^n\) 和 \(b \in F_2^m\) 的连接记为 \(a \parallel b\)。 - **基于除法性质的代数度评估**： - **除法性质**：2015 年，Todo 提出了一种广义积分性质——除法性质，用于为分组密码寻找更长的积分区分器。随后，Todo 和 Morii 将其扩展为更精确的变体，如二子集和三子集基于位的除法性质。2016 年，Xiang 等人首次采用混合整数线性规划（MILP）进一步拓展了除法性质的应用。 - **使用 MILP 基于除法性质的度评估**：对于迭代密码，设 \(s^r = (s^r_{m - 1}, \ldots, s^r_0)\) 表示第 \(r\) 轮的内部状态，\((a^0_{m - 1}, \ldots, a^0_0) \to \cdots \to (a^r_{m - 1}, \ldots, a^r_0)\) 表示一个 \(r\) 轮的除法轨迹。为了评估 \(s^r_i\) 相对于 \((s^0_i)\) 的代数度，引入一个 MILP 模型 \(M\) 来描述 \(r\) 轮加密过程中的除法性质传播。将 \((a^r_{m - 1}, \ldots, a^r_0)\) 固定为 \(e_i\)，并最大化目标函数 \(\sum_{j = 0}^{m - 1} a^0_j\)。MILP 求解器（如 Gurobi）返回的 \(M\) 的解被视为 \(s^r_i\) 的估计度，具体过程如算法 1 所示。 ```plaintext 算法 1. 基于除法性质的代数度评估 要求：描述 r 轮密码除法性质传播的模型 M，以及输出位索引 i。 确保：固定输出位置的代数度 d。 1: M.obj ← maximize {a0_0 + · · · + a0_m−1}; // 设置 M 的目标函数 2: M.con ← ar_i = 1; 3: M.con ← ∑j ar_j = 0 对于所有 j ∈ {0, 1, ..., m − 1} \ {i}; // 关注输出的第 i 位，因此让其他位的除法性质为 0 4: M.optimize(); // 使用 GUROBI 优化求解模型 M 5: obj = M.getObjective(); 6: d = obj.getValue(); // 获取模型 M 的解 7: return d ``` - **条件立方体攻击**： - 假设 \(f(x, v)\) 是一个定义在变量 \(x = (x_{m - 1}, \ldots, x_0)\) 和 \(v = (v_{n - 1}, \ldots, v_0)\) 上的布尔函数。给定一组变量 \(I = \{v_{i_1}, v_{i_2}, \ldots, v_{i_{|I|}}\} \subset \{v_0, \ldots, v_{n - 1}\}\)（称为立方体集），记单项式 \(v_{i_1}v_{i_2} \cdots v_{i_{|I|}}\) 为 \(t_I\)。则 \(f(x, v)\) 可重写为 \(f(x, v) = t_I \cdot p_{S(I)} + q(x, v)\)，其中 \(p_{S(I)}\) 称为超多项式，不包含 \(I\) 中的任何变量，\(q(x, v)\) 至少缺少 \(I\) 中的一个变量。立方体集 \(I\) 定义了一个 \(|I|\) 维空间 \(C_I\)（称为立方体），其中包含 \(2^{|I|}\) 个向量，我们为 \(I\) 中的变量赋予所有可能的 0/1 值组合，并将 \(\{v_0, \ldots, v_{n - 1}\} \setminus I\) 中的其余变量固定为常数值。 - 条件立方体攻击由 Huang 等人在 2017 年提出，旨在对一系列密钥位或与密钥位相关的方程（统称为条件方程）施加条件，然后检测立方体和的非随机性以恢复部分密钥位。该攻击分为两个阶段： - **预处理阶段**：攻击者需要准备一组条件方程和一个立方体集，使得当条件方程成立时，相应的立方体和始终为 0，否则未知，即构造如下区分器： \[ \sum_{v \in C_I} f(x, v) = \begin{cases} 0, & \text{如果条件方程成立}\\ \text{未知}, & \text{否则} \end{cases} \] - **在线阶段**：此时密码的密钥未知但固定，攻击者可以选择公共变量的值并获取相应的输出。通过使用准备好的条件立方体集计算立方体和，然后根据立方体和的性质判断条件方程是否成立，从而恢复条件方程中包含的部分密钥位。 - **KNOT - AEAD 家族**： - **KNOT 置换**：KNO