针对HALFLOOP-48的相关调整和相关密钥差分攻击

### 针对 HALFLOOP - 48 的相关调整和相关密钥差分攻击 #### 1. 攻击概述 针对 HALFLOOP - 48 进行了相关调整和相关密钥差分攻击。虽然 8 轮差分的概率略高于临界值，但在全轮攻击中仍能发挥作用。具体攻击情况如下表所示： | 设置 | 轮数 | 数据 | 时间 | 内存 (字节) | 成功概率 | | ---- | ---- | ---- | ---- | ---- | ---- | | 相关调整 | 8 | 2^33.27 | 2^92.71 | 2^36.85 | 90% | | 相关密钥 | 10 | 2^47.34 | 2^123.91 | 2^33.34 | 50% | 由于攻击的复杂度不切实际，这些攻击对 HALFLOOP - 48 不构成真正的安全风险，但仍需谨慎防止滥用，因为研究表明在相关密钥攻击场景中没有安全余量。 #### 2. 预备知识 ##### 2.1 差分密码分析 差分密码分析由 Biham 和 Shamir 首次定义。基本过程是使用由常量差分 Δin 连接的明文对 (P, P ′)，攻击者计算对应密文 (C, C′) 之间的差分，试图检测出非随机出现的差分 Δout，(Δin, Δout) 这对差分称为差分对。差分概率的计算公式为： \[Pr_{E_K}(\Delta_{in}, \Delta_{out}) = \frac{\{x \in F_2^n \mid E_K(x) \oplus E_K(x \oplus \Delta_{in}) = \Delta_{out}\}}{2^n}\] 差分的权重为 \(-\log_2 [Pr_{E_K}(\Delta_{in}, \Delta_{out})]\)。为保证攻击成功，差分攻击中使用的差分概率必须超过 \(2^{1 - n}\)。 通常，评估大规模多轮密码的差分概率以找到有效差分非常具有挑战性，一般通过构建差分特征来定位差分，差分特征会跟踪每一轮后的差分。假设 r 轮加密 \(E_K\) 可表示为 r 个轮函数的组合 \(f_{k_{r - 1}} \circ f_{k_{r - 2}} \circ \cdots \circ f_{k_0}\)，在轮密钥 \(k_0, k_1, \cdots, k_{r - 1}\) 独立且均匀随机的假设下，差分特征的差分概率可计算为： \[Pr_{E_K}(\Delta_0, \Delta_1, \cdots, \Delta_r) = \prod_{i = 0}^{r - 1} Pr_{f_{k_i}}(\Delta_i, \Delta_{i + 1})\] 一个固定差分可能包含大量差分特征，差分的概率可计算为： \[Pr_{E_K}(\Delta_{in}, \Delta_{out}) = \sum_{\Delta_1, \Delta_2, \cdots, \Delta_{r - 1} \in F_2^n} Pr_{E_K}(\Delta_{in}, \Delta_1, \cdots, \Delta_{r - 1}, \Delta_{out})\] 实际中，由于计算资源有限，穷举搜索差分中的所有特征并准确计算其概率是不可能的，常见做法是找到差分中概率较高的差分特征，这些特征概率的总和近似差分的概率。 获得概率为 \(p_0\)（\(p_0 > 2^{1 - n}\)）的 r 轮差分 (\(\Delta_{in}, \Delta_{out}\)) 后，可对 (r + 1) 轮加密 \(\tilde{E}_K = f_{k_r} \circ E_K\) 发起 (r + 1) 轮差分攻击，基本攻击步骤如下： 1. 选择 N 个明文对 (P, P ′)，使 P 和 P ′ 之间的差分为 \(\Delta_{in}\)，查询加密预言机以获得对应的密文对 (C, C′)。 2. 为子密钥 \(k_r\) 的每个可能值 \(k_r^{(i)}\)（\(0 \leq i \leq 2^n - 1\)）创建一个计数器 \(Cnt[k_r^{(i)}]\)。对于每对 (C, C′)，为每个 \(k_r^{(i)}\) 确定 \(f_{k_r^{(i)}}^{-1}(C) \oplus f_{k_r^{(i)}}^{-1}(C′)\) 的值。如果方程 \(f_{k_r^{(i)}}^{-1}(C) \oplus f_{k_r^{(i)}}^{-1}(C′) = \Delta_{out}\) 成立，则将计数器 \(Cnt[k_r^{(i)}]\) 加 1。 3. 如果阈值设置为 τ，只有当计数器值 \(Cnt[k_r^{(i)}]\) 至少为 τ 时，密钥猜测 \(k_r^{(i)}\) 才会被列入候选列表。 差分密码分析作为统计密码分析，总是面临两种错误：正确密钥不在候选列表中的概率记为 α，错误密钥猜测留在候选列表中的概率记为 β，攻击的成功概率 \(P_S\) 等于 \(1 - α\)。当 N 足够大时，α 和 β 可近似计算为： \[\alpha \approx \frac{p_0 \cdot (1 - (\tau - 1)/N)}{p_0 - (\tau - 1)/N} \cdot \sqrt{2 \cdot \pi \cdot (\tau - 1)} \cdot \exp \left(-N \cdot D\left(\frac{\tau - 1}{N} \parallel p_0\right)\right)\] \[\beta \approx \frac{(1 - p) \cdot \sqrt{\tau/N}}{(\tau/N - p) \cdot \sqrt{2 \cdot \pi \cdot N \cdot (1 - \tau/N)}} \cdot \exp \left(-N \cdot D\left(\frac{\tau}{N} \parallel p\right)\right)\] 其中 \(D(p \parallel q) \triangleq p \cdot \ln \left(\frac{p}{q}\right) + (1 - p) \cdot \ln \left(\frac{1 - p}{1 - q}\right)\) 是两个参数分别为 p 和 q 的伯努利分布之间的 Kullback - Leibler 散度。 ##### 2.2 相关密钥和相关调整差分密码分析 传统差分密码分析与相关密钥差分密码分析的区别在于，后者利用不同密钥加密相同或不同明文时的差分传播特性。r 轮相关密钥差分用三元组 (\(\Delta_{in}, \Delta_{out}, \Delta_{key}\)) 表示，其概率计算公式为： \[Pr_{E_K}(\Delta_{in}, \Delta_{out}, \Delta_{key}) = \frac{\{x \in F_2^n \mid E_K(x) \oplus E_{K \oplus \Delta_{key}}(x \oplus \Delta_{in}) = \Delta_{out}\}}{2^n}\] 对于可调整分组密码（如 HALFLOOP - 48），也可进行相关调整差分密码分析。它利用相同密钥和不同调整量加密明文时的差分传播特性，相关调整差分用三元组 (\(\Delta_{in}, \Delta_{out}, \Delta_{tweak}\)) 表示，其中 \(\Delta_{tweak}\) 是调整量之间的差分。与相关密钥差分密码分析相比，相关调整差分密码分析威胁更大，因为调整量的值对攻击者是公开的。 获得概率大于 \(2^{1 - n}\) 的 r 轮相关密钥（或相关调整）差分后，可像传统差分攻击一样进行相关密钥（或相关调整）差分攻击。 ##### 2.3 HALFLOOP - 48 的规范 HALFLOOP 是一个可调整分组密码家族，有三种不同变体。HALFLOOP - 48 使用 48 位块，有 128 位密钥 K 和 64 位调整量 T，许多操作源自 AES。 初始化时，接收到明文 \(m = m[0] \parallel m[1] \parallel \cdots \parallel m[5]\)（其中 \(m[i] \in F_2^8\)，\(0 \leq i \leq 5\)）后，内部状态 IS 设置为： \[IS = \begin{bmatrix} m[0] & m[3] \\ m[1]