---

高阶差分、积分与代数攻击

一、引言：代数视角下的密码分析

• 核心思想：将密码算法（特别是S盒和轮函数）视为多元多项式函数，利用其代数性质（如次数、系数、零点和）进行攻击。
• 与传统统计攻击的区别：不依赖概率偏差，而是利用确定性的代数结构，在特定条件下能以极低数据复杂度成功。

---

二、布尔微分学基础

1. 布尔导数 (Boolean Derivative)

• 对于布尔函数 $f:\{0,1{\}}^n\to \{0,1\}$，关于变量 $x_i$ 的导数定义为：$$\frac{\partial f}{\partial x_i}=f(x_i=0,{\mathbf{x}}_{\setminus i})\oplus f(x_i=1,{\mathbf{x}}_{\setminus i})$$
• 这衡量了当 $x_i$ 翻转时，函数输出是否改变。

2. 高阶差分 (Higher-Order Differential)

• k阶差分：对函数 $f$ 在一个 k 维线性子空间 $V$（由基 ${\mathbf{a}}_1,...,{\mathbf{a}}_k$ 张成）上求和：$${\mathrm{\Delta }}_{{\mathbf{a}}_1,...,{\mathbf{a}}_k}^{(k)}f(\mathbf{x})=\underset{\mathbf{v}\in V}{⨁}f(\mathbf{x}\oplus \mathbf{v})$$
• 关键性质（零和性质）：
  • 如果 $f$ 的代数次数 $\mathrm{deg}(f)<k$，那么其任意 k 阶差分恒等于 0。
  • 这是所有高阶差分攻击的基石。

---

三、高阶差分攻击 (Higher-Order Differential Attack)

1. 攻击原理

• 寻找一个密码算法经过若干轮加密后，其输出函数 $F$ 的代数次数 $\mathrm{deg}(F)$ 仍然较低。
• 选择一个维度 $k=\mathrm{deg}(F)+1$ 的输入明文集合（构成一个仿射子空间）。
• 对该集合的所有明文加密，并计算密文的异或和（即 k 阶差分）。
• 结果：根据零和性质，该和必然为 0。
• 区分器：随机函数产生全零和的概率极低（$2^{-n}$），因此可有效区分密码算法与随机置换。

2. 经典案例：Feistel 结构

• 若轮函数 $f(x)=x^2\mathrm{mod}p$（二次函数），则：
  • 二阶差分 ${\mathrm{\Delta }}_{a,b}^{(2)}f(x)=2ab\mathrm{mod}p$，为常数。
  • 经过3轮后，左分支的差分值恒为 $2ab$，可被利用进行密钥恢复。

---

四、积分攻击 (Integral Attack)

1. 核心概念

• 积分：对于一个多重集 $S$，其积分定义为其中所有元素的异或和：$\underset{y\in S}{⨁}y$。
• 活跃字节 (Active, A)：在明文集中取遍所有可能值的字节。
• 平衡字节 (Balanced, B)：在对应的密文集中，其积分（异或和）为 0 的字节。
• 常数字节 (Constant, C)：在明文/密文集中保持不变的字节。

2. 攻击流程

1. 构造明文集：选择一个明文集，其中部分字节是活跃的（A），其余为常数（C）。
2. 追踪传播：通过分析密码各组件（S盒、MixColumns等）对 A/C/B 属性的传播规律，预测若干轮后哪些输出字节会变成平衡的（B）。
3. 验证：加密所有明文，计算对应密文字节的积分。若结果为 0，则符合预期；否则，可排除错误的密钥猜测。

3. 经典案例：AES

• 4轮积分区分器：1个活跃字节输入 → 4轮后，整个状态都是平衡的（B）。
• 6轮密钥恢复：利用4轮区分器，猜测第5、6轮的部分轮密钥，通过验证平衡性来筛选正确密钥。

4. 积分攻击与高阶差分的关系

• 当明文集是一个线性或仿射子空间时，积分攻击本质上就是高阶差分攻击。
• 包含关系：Cube Attacks ⊂ Higher-Order Differential Attacks ⊂ Integral Attacks

---

五、立方攻击 (Cube Attack)

1. 攻击模型

• 将密码输出表示为一个关于公开变量（通常是明文/IV比特 $v_i$）和秘密变量（密钥比特 $k_j$）的多项式：$$f(\mathbf{v},\mathbf{k})=t_I\cdot p_S({\mathbf{v}}_I,\mathbf{k})+q(\mathbf{v},\mathbf{k})$$
  • $t_I=\prod _{i\in I}{v}_i$ 是一个“立方项”（cube term）。
  • $p_S$ 是超多项式（superpoly），不包含 $t_I$ 中的任何变量。
  • $q$ 是所有不包含完整 $t_I$ 项的剩余部分。

2. 核心技巧

• 立方和 (Cube Sum)：对所有满足 $v_i=0/1$（$i\in I$）且其他公开变量固定的明文进行加密，并将输出异或求和：$$\underset{{\mathbf{v}}_I\in \{0,1{\}}^{|I|}}{⨁}f(\mathbf{v},\mathbf{k})=p_S({\mathbf{v}}_{\setminus I},\mathbf{k})$$
• 效果：神奇地消去了复杂的 $q$ 部分，直接得到一个仅关于密钥和少量公开变量的简单线性（或低次）方程 $p_S$。

3. 应用：Keccak (SHA-3)

• Keccak-f 的 r 轮函数代数次数为 $2^r$。
• 因此，对于一个维度为 $d$ 的立方，如果 $d>2^r$，其立方和恒为 0。
• 利用此性质可以对缩减轮的 Keccak 进行预像攻击和密钥恢复。

---

六、划分性质 (Division Property)

1. 动机

• 传统的 A/B/C 分类过于粗糙，无法精确刻画介于 "ALL" 和 "BALANCE" 之间的状态。
• 划分性质提供了一种更精细的工具来追踪积分/高阶差分属性的传播。

2. 核心定义

• 使用位积函数 ${\pi }_{\mathbf{u}}(\mathbf{x})=\prod _{i=0}^{n-1}{x}_i^{u_i}$ 来评估一个集合 $X$ 的奇偶性。
• 划分性质 $D_k^n$：描述了对于所有汉明重量 $wt(\mathbf{u})<k$ 的 $\mathbf{u}$，其对应的位积函数在集合 $X$ 上的异或和均为 0。
• 传播规则：可以为 S 盒、线性层等组件建立精确的划分性质传播表，从而自动化地搜索积分区分器。

---

七、插值攻击 (Interpolation Attack)

1. 基本思想

• 将整个密码（或其一部分）视为一个从明文到密文的黑盒函数 $F$。
• 如果 $F$ 可以被一个低次多项式 $P$ 精确表示（即 $P(p)=c$ 对所有 $(p,c)$ 成立），那么可以用拉格朗日插值法从少量已知明密文对中重构出 $P$。
• 一旦得到 $P$，就可以利用其代数结构（如特定系数与密钥的关系）来恢复密钥。

2. 拉格朗日插值

• 要唯一确定一个次数不超过 $N$ 的多项式，需要 $N+1$ 个点。
• 例如，KN 密码的3轮输出函数次数为 $3^{3-2}=3$，因此只需 4 个明密文对即可插值得到该多项式。

3. 高级变种：结合 MitM

• 对于更多轮的密码，可以将其分为前后两段。
• 分别假设前后段的输出多项式次数为 $N_1$ 和 $N_2$。
• 在中间状态进行匹配，将总复杂度从 $2^{N_1+N_2}$ 降低到约 $(N_1+N_2)\cdot 2^{\text{密钥长度}/2}$。

---

复习题与答案

题目 1：解释高阶差分攻击中的“零和性质”，并说明它如何用于构建区分器。

答： 零和性质指出，任何代数次数小于 k 的布尔函数，其 k 阶差分恒等于 0。 攻击者利用这一点：

1. 分析目标密码，确定经过 r 轮后输出函数 $F$ 的次数 $\mathrm{deg}(F)=d$。
2. 选择一个维度为 $k=d+1$ 的明文集（如一个 $k$-维超立方体）。
3. 加密该集合中所有明文，并计算密文的异或和（即 k 阶差分）。
4. 根据零和性质，这个和必定为 0。
5. 而对于一个真正的随机函数，其输出和为 0 的概率仅为 $2^{-n}$（n 为块长）。因此，观察到全零和就能以极高置信度将密码与随机函数区分开。

---

题目 2：立方攻击的关键步骤是什么？为什么立方和能简化问题？

答： 关键步骤如下：

1. 识别立方变量：选择一组公开变量 $I=\{v_{i_1},...,v_{i_t}\}$ 作为立方变量。
2. 执行立方和：固定所有其他公开变量，让立方变量遍历所有 $2^t$ 种可能，收集对应的输出并计算它们的异或和。
3. 获得超多项式：立方和的结果恰好等于与该立方项相关联的超多项式 $p_S$，它只依赖于密钥和未被选入立方的公开变量。
4. 求解密钥：重复此过程以获得多个关于密钥的（通常是线性的）方程，然后求解这些方程来恢复密钥。

立方和之所以能简化问题，是因为在异或操作下，所有不包含完整立方项 $t_I$ 的单项式都会被成对抵消（因为它们在立方变量的不同赋值下出现偶数次），最终只剩下乘以了 $t_I$ 的那部分，即超多项式 $p_S$。

---

题目 3：比较积分攻击和高阶差分攻击的异同。

答： 相同点：

• 两者都依赖于对一个精心构造的明文集的输出进行求和（异或）。
• 核心理论基础都是零和性质，即低次函数在高维空间上的和为零。
• 最终目的都是构建区分器或进行密钥恢复。

不同点：

• 明文集构造：
  • 高阶差分攻击严格要求明文集是一个线性或仿射子空间。
  • 积分攻击的明文集构造更灵活，可以是任意满足“某些位置取遍所有值”的集合（例如，在AES中，一个字节取遍0-255，而不管其他字节）。
• 适用范围：
  • 高阶差分是积分攻击的一个特例。所有高阶差分攻击都可以看作积分攻击，但反之不成立。
  • 积分攻击的概念更宽泛，尤其适用于像AES这样具有强扩散层（MixColumns）的SPN结构密码。

---

题目 4：为什么插值攻击对轮函数代数次数增长缓慢的密码（如PURE/KN密码）特别有效？

答： 插值攻击的有效性直接取决于目标函数的代数次数。

• 对于一个次数为 $d$ 的函数，只需要 $d+1$ 个点就可以通过插值完全重构它。
• PURE/KN 密码使用的是幂函数型S盒（如 $x^3$），其代数次数很低（例如3）。
• 在 Feistel 结构中，输出的代数次数随着轮数 $r$ 的增加而多项式级增长（例如 $\mathrm{deg}\approx 3^{r-2}$），而不是指数级爆炸。
• 因此，即使经过多轮（如6轮），其整体函数的次数仍然可控（例如 $3^4=81$），只需要几十个明密文对就能完成插值，从而使得攻击非常高效。而对于代数次数快速增长的密码，所需的数据量会迅速变得不切实际。