广义Feistel网络相关密钥差分分析：结构弱点与自动搜索实践

广义Feistel网络（GFN）在分组密码设计里是特别常见的一类结构。它不像经典Feistel那样非要等一轮才能扩散到另一边，而是可以通过分支扩展到多路并行，扩散速度、轮函数复用比例、硬件面积都能灵活调节；但换来的是更难保证差分和线性传播的“均匀性”，尤其是涉及密钥分组调度时，容易留下结构性的弱点。我在这类结构上做过很长时间的自动分析，最大的感受是：相关密钥差分特征在GFN里往往不是靠运气搜出来的，而是设计层面某些交互的必然结果。这篇文章适合正在找密码分析方向切入点的人，也适合想给自己设计的GFN变体做安全性评估的工程开发者。下面我会直接用一套可复现的迷你结构，把从建模到实验验证的完整链路讲透。

1. 从结构到攻击：项目核心思路

1.1 广义Feistel网络：为什么会成为攻击目标

经典Feistel网络把输入分成左右两半，一轮里右半边通过轮函数改变左半边，然后再交叉。广义Feistel网络把“两半”推广成 d 个分支，常见的有 Type-1、Type-2、Type-3 等类型，其中工程上最常见的是 Type-2：每一轮用 d/2 个轮函数，分别作用在偶数位分支上，输出异或到旁边分支，再做一次循环移位。分支数一旦大于2，设计自由度立刻变大——每轮用几个轮函数、轮函数放在哪个分支、轮间置换怎么排、小分支宽度取多少，这些都直接影响抗攻击能力。

GFN 的结构决定了它天然适合相关密钥分析，原因有三个。第一，为了硬件实现简单，很多 GFN 的密钥调度只做线性变换，密钥差分可以完全可控。第二，轮函数只更新部分分支，攻击者有更多机会让差分在“未受保护”的分支里游走。第三，分支置换和密钥加法的位置如果匹配不好，会出现“密钥差分吸收状态差分”的现象，相当于一层强非线性被绕过去。这也是为什么许多轻量级设计在单密钥差分分析下表现不错，一放到相关密钥模型下却出现很长的低概率路径——问题往往不在密码主体，而在密钥调度与分支层之间的交互没有设计到位。

需要提醒的是，“广义”不是越广越好。分支太多会导致轮函数覆盖不足，扩散速度下降；分支太少又退化回经典 Feistel。Type-2 四分支是很多实际设计选择的“甜点区”，做分析时也要优先关注这个区域的交互问题。后面我搭建的迷你结构正是这个形态。

1.2 相关密钥模型到底在模拟什么

相关密钥攻击里，攻击者不能直接知道密钥的值，但可以选择两个密钥 K 和 K' 之间的差分 ΔK。这个模型听起来很强，但有现实对应场景：一些密钥更新协议允许相邻会话使用具有固定关系的密钥；某些基于分组密码构造的哈希或认证模式，密钥会被当成输入的一部分，攻击者能控制的部分相当于密钥差分。所以分析结果不能简单归为“模型太强了”，它确实反映了一类真实威胁。

在这个模型下做差分分析，核心目标是寻找一个“相关密钥差分特征”：输入明文差分 ΔP、主密钥差分 ΔK，引导出某一轮之后的中间状态差分或最终密文差分。跟单密钥差分特征相比，多了一个密钥维度的自由度。这个自由度用得好，可以抵消部分状态差分，让原本会激活 S 盒的输入变成差分零。后面我会用具体例子展示这种抵消是怎么发生的。

相关密钥分析的输出一般分两类。一类是区分器：找到概率足够高的特征，让密码的输出分布区别于随机排列。另一类是密钥恢复攻击：用区分器筛出末尾轮密钥候选。无论哪一类，最后都要算数据量、时间量、成功率三个数字，能同时低于某个安全上限才算一条有效的攻击路径。很多刚接触这个方向的人只盯着特征概率，忽略复杂度计算，这是最容易出偏差的地方。

2. 核心细节拆解：从差分传播到特征搜索

2.1 一个具体的GFN更新模型

为了把话说清楚，我在项目里搭建了一个32比特、4分支的迷你 GFN。分支宽度取8比特，这样整轮状态是32比特。轮函数 F 定义为：先与轮密钥异或，再拆成两个4比特并联 S 盒。S 盒用一张固定的4比特置换表。密钥调度是线性的：每一轮子密钥等于主密钥循环移位后再异或轮常数。这样的结构足够小，可以手动跟踪差分，也足够复杂，能展示相关密钥特征的完整搜索过程。

一轮更新的形式如下，输入是 (x0, x1, x2, x3)，轮密钥是 rk0、rk1：

def gf_round(st, rk0, rk1): x0, x1, x2, x3 = st y0 = x1 ^ F(x0, rk0) y1 = x2 y2 = x3 ^ F(x2, rk1) y3 = x0 return (y0, y1, y2, y3)

下一轮输入就是 (y0, y1, y2, y3)。F 内部先异或轮密钥再做 S 盒，这是整个分析里最关键的设计：差分进入 F 时，实际作用在 S 盒上的是状态差分和轮密钥差分的异或结果。如果两者相等，输入差分变成 0，S 盒完全不活跃。

给定差分，一轮的传播可以这么看：y0 的差分由 x1 的差分和 F(x0) 输出差分异或得到；y1、y3 只是搬运，不消耗活性；y2 的差分由 x3 的差分和 F(x2) 输出差分异或得到。如果某个 S 盒输入差分非零，则它的输出差分会以一定概率出现，这个概率由 S 盒的差分分布表（DDT）给出。把每一轮活跃 S 盒的概率乘起来，就是整条特征的理论概率。分支搬运是概率 1 的，只有 S 盒贡献概率。所以找高概率特征，本质上就是找一条“活跃 S 盒尽量少、且每个活跃 S 盒的差分转移概率尽量高”的路径。

2.2 密钥差分如何“吸收”状态差分

现在到了相关密钥分析最微妙的地方。当 F(x, rk) = S(x ⊕ rk) 时，状态 x 的差分 Δx 和子密钥 rk 的差分 Δrk 分别传进异或门，最终到 S 盒输入的是一个合并差分 Δx ⊕ Δrk。

如果攻击者控制的 ΔK 经过密钥调度之后，恰好让某一轮 Δrk = Δx，那么 S 盒输入差分就是 0。这概率是 1，不需要经过任何 S 盒的概率折扣。这个现象我习惯称为“密钥差分吸收”，也可以理解为：攻击者给密码的两个输入（明文和密钥）分别注入了一致的差分，通过一条“短路”直接穿过非线性层。

用表格举个直观的例子，假设某一轮状态 x0 处差分 α，对应轮密钥差分也为 α：

单密钥场景下，α 进入 S 盒，需要付出差分转移概率；相关密钥场景下，S 盒被完全跳过，相当于这一轮的轮函数对差分路径没有任何阻碍。这条路径就能继续往下延伸。多次吸收可以在不同轮、不同分支上发生，特征的总概率因此显著提高。这也是为什么很多看似扩散良好的 GFN 设计，在单密钥下最优特征概率已经很低，但在相关密钥模型下却能找到长得多的路径。

这里还有一个资源约束问题：吸收不是免费的，它需要消耗密钥差分中的“已知比特资源”。ΔK 一共就那么多比特，想去吸收多少轮的状态差分，取决于密钥调度是否仍然保留这些自由度。如果子密钥之间的线性关系太强，攻击者能控制的模式就会受限；如果调度里加了非线性成分，吸收的约束也会跟着复杂起来。做分析时，先梳理密钥调度的自由度，往往比直接跑搜索更有效。

2.3 特征概率、区分器长度和攻击复杂度

一条相关密钥差分特征用下来，首先要确认它覆盖几轮，这决定了密码器有几轮可以用它做区分。对于一个 R 轮密码，如果用前 r 轮的特征做区分器，那么剩下 R - r 轮用于密钥恢复。区分器概率记为 p，真实密码的匹配概率是 p，随机排列下是 2^{-w}，w 是过滤时所用的匹配比特数。当 p 显著高于随机概率时，通过重复实验可以把正确密钥候选和错误候选区分开。

在相关密钥差分攻击里，数据复杂度的粗略下界是 O(1/p)。但实际工程上不会只取 1/p 这么少，因为要同时筛掉错误密钥。简单估算时，如果你在末轮关心 b 比特密钥，则数据量往往需要放大到 O(2^{b-w}/p) 甚至更多。有些攻击还会用“早夭”技术，一旦某对数据不符合期望就直接丢弃，实际时间成本可以比朴素实现低得多。所以报告复杂度时要写清楚假设模型：数据量、存储量、等价加密次数分别是什么量级。

结合我的迷你 GFN，假设搜索到一条 7 轮的特征，log2(p) = -36，末轮要恢复 6 比特密钥，区分器过滤条件 w = 8。那么数据量取 2^{36} 左右这个量级是保底的，时间量则是数据量乘以每次加密和少量猜测密钥的额外开销。如果你的目标密码总密钥空间是 32 比特，2^{36} 的数据量意味着攻击已经没有实际意义。这个换算在文献阅读里经常被忽略，但实际判断一条攻击“能不能用”时最关键。

3. 实操过程：一次完整的相关密钥分析实验

3.1 搭建目标：可复现的32bit迷你GFN

做分析目标时，我特意避开任何真实算法的实现，只用一个自造结构，避免把特定算法细节和通用结论混淆。完整定义如下：

• 分支数 d = 4，分支宽度 w = 8，总状态 32 比特。
• S 盒 SBOX4 是一张 4 比特静态置换表。
• 轮函数 F 输入 8 比特：先异或 8 比特轮密钥，再拆成高低两个 4 比特分别过 SBOX4，最后拼成 8 比特输出。
• 轮密钥生成：主密钥 32 比特记为 K；第 t 轮的两个 8 比特子密钥分别由主密钥循环移位 t 个 4 比特后的低 8 位和高 8 位，再异或固定轮常数得到。

这套参数下，一轮 F 容易手算，也方便用脚本枚举 DDT。代码实现很直接：

SBOX4 = [12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2] def F(x, rk): v = x ^ rk return (SBOX4[v >> 4] << 4) | SBOX4[v & 0xF] def gf_round(st, rk0, rk1): x0, x1, x2, x3 = st y0 = x1 ^ F(x0, rk0) y1 = x2 y2 = x3 ^ F(x2, rk1) y3 = x0 return (y0, y1, y2, y3)

密钥调度的差分传播完全是线性的，所以给定 ΔK，每一轮 Δrk0、Δrk1 都能直接算出来，不需要概率。这意味着相关密钥差分特征建模时，密钥差分是“确定性资产”，专门用来做吸收。我建议读者给这个结构加一个命令行参数控制轮数，写成类似 test_vector_gfn(R, deltaK, deltaP) 的形式。你会很快发现，构造一条 4 轮的相关密钥差分路径，手工配平并不难；难的是在全部分支上搜索出全局最优路径。这也是为什么要进入自动建模。

3.2 自动搜索相关密钥差分特征：建模逻辑与关键步骤

搜索特征最常用的办法是 MILP/SAT 自动建模。思路是：把密码每一轮的差分传播关系转成约束，让求解器在所有满足关系的路径里，找活跃 S 盒最少或概率最大的一条。

建模时可以把密码操作分解成三种节点：搬运、异或、S 盒。搬运直接给等式；异或用比特级奇偶约束；S 盒枚举 DDT 允许对，并用指示变量选择。下面是核心逻辑的伪代码，真正的 API 请按你选用的求解器调整：

# 变量：x[t][i] 是第t轮第i个分支的8bit差分值 # key[t][0], key[t][1] 由 ΔK 线性算出，可直接填入 # 搬运分支 for t in range(R): model.AddEqual(x[t+1][1], x[t][2]) model.AddEqual(x[t+1][3], x[t][0]) # F 节点：两个4bit并联S盒 for t in range(R): # F(x0, rk0) ，输入差分 = x[t][0] ^ key[t][0] f_in0 = Xor(x[t][0], key[t][0]) f_out0 = SboxLayerDiff(f_in0) # 由DDT允许对决定 # y0 = x1 ^ F0 ，差分传播：x[t+1][0] ^ x[t][1] == f_out0 model.AddXor(x[t+1][0], x[t][1], f_out0) # F(x2, rk1) f_in1 = Xor(x[t][2], key[t][1]) f_out1 = SboxLayerDiff(f_in1) model.AddXor(x[t+1][2], x[t][3], f_out1)

这里有一个容易误踩的点：MILP 本身不直接支持 Xor，需要把每个 8 比特差分拆成 8 个布尔变量，然后把异或关系转成三个布尔变量的奇偶校验线性不等式。S 盒约束也要把 DDT 里非零的（输入差分、输出差分）对枚举出来，每个对分配一个指示变量，并约束恰好选中一个。这些都属于实现细节，但决定了模型能不能在合理时间内求解。

目标函数优先选“最小化活跃 S 盒数量”。给每个 S 盒节点加一个布尔变量表示是否活跃，最小化这些变量的和。得到最少活跃数量后，再固定活跃 S 盒数量，最大化路径概率。由于我的 S 盒只有 4 比特，DDT 表很小，可以直接在每个允许对上用概率对数求和，一步到位最大化 log2(p)。对于更大的 S 盒，分两步更稳妥。

搜索策略上，我的经验是先固定几组有代表性的 ΔK（比如只差分主密钥一个比特、两个相邻比特），分别搜索，再看哪些 ΔK 能让特征最长。这样搜索空间小很多，也更容易理解结构上发生了什么。如果一开始就把 ΔK 所有模式都放进模型，求解器大概率会陷入巨大的搜索空间，几小时跑不出结果。

3.3 验证搜索结果：理论特征不等于真实概率

搜索出来一条特征后，我不会直接拿去算复杂度，而是先做三件事。

第一，把特征转成标准形式，逐轮检查是否满足密码的差分更新。这一步等于用特征里的中间差分值重放一遍密码过程。第二，用模拟实验统计实际概率。写一个函数，随机生成大量满足 ΔP 和 ΔK 的明文、密钥对，加密两条记录下来，比较密文是否满足特征末轮的输出差分。第三，对比理论值和实验值，两者差异通常意味着特征簇或多条特征合并，需要进一步分析。

下面是我在这套迷你 GFN 上拿到的一组典型结果（示意数据，用来展示趋势，不代表任何公开算法）：

现象非常典型：轮数短的时候单条特征主导；轮数变长，特征之间的相互干扰显现，实验概率会比单条特征稍高或稍低。如果实验概率比理论低，通常是你搜索的特征在中间轮存在数条可替换路径，但它们在末轮差分上有部分抵消；如果比理论高，则是多条路径在末轮汇成同一个差分值，发生了“特征簇”的合并效应。做攻击规划时，应该优先按特征簇的总概率来算，不能只看搜索器弹出的单条最优特征。

4. 常见问题与排查技巧实录

4.1 建模时最容易踩的五个坑

• 零差分平凡解。求解器很容易找一条所有差分全为 0 的路径。需要在约束里加上明文差分、密钥差分、末轮中间状态差分三者至少一个非零，而且最好分别加非零约束，否则“从中间某轮开始全零”的伪路径也会进入最优解。
• 密钥轮次错位。主密钥差分子密钥产生是逐轮的，我见过最多的问题是把第 t 轮的轮密钥差分直接当成第 t+1 轮的，导致吸收条件错位，特征算出来根本走不通。建议把密钥调度脚本单独运行、单独打印，再和状态特征对照。
• DDT 枚举集写错形式。有些建模工具里，S 盒约束写成“输入输出差分只能是 DDT 里非零的列表”，这没问题；但如果你误用等式约束，等于把 S 盒差分的多值性压成单值，会漏掉大量特征。
• 分支索引写错。GFN 的分支置换每轮都在变，多跑几轮后特别容易把 y1/y3 的位置搞混。我的做法是画一个简单的轮状态表，把每轮每个分支的表达式列出来，再照着写约束。
• 活跃 S 盒计数和概率目标混在一起。如果只最大化概率，求解器可能挑选一条活跃 S 盒很多但每个概率都不低的路径，这条路径往往不是真实最优。先最小化活跃数量，再固定数量找最大概率，结果更可控。

4.2 不要把特征概率直接当成攻击复杂度

搜索环节拿到 p 之后，很多人会直接说“数据复杂度等于 1/p”，这个说法过于乐观。实际攻击复杂度受几个因素影响：一是特征概率低于区分随机排列所需的信噪比时，错误密钥候选的噪声会淹没正确候选；二是密钥恢复轮里要猜的密钥比特越多，候选数越大；三是过滤条件如果太宽，实验重复次数会增加。

我的习惯是写一个小的攻击复杂度模拟器，把特征概率、过滤宽度、密钥猜测数、密码轮数填进去，生成三条曲线的交点，用那个数据点对外报告复杂度，而不是用单行公式计算。另外，相关密钥矩形攻击比单条特征复杂度更低，但分析流程更复杂，要分别考虑上半特征和下半特征。如果你搜索到的单条特征已经接近阈值，值得再试试两条短特征拼接的矩形攻击，经常会得到更好结果。

4.3 给新手的实验路线建议

做这个方向，我比较推荐一条路走下来。先手工构造一个 3 轮或 4 轮的 GFN 差分路径，哪怕用暴力枚举都行，目标是建立“差分如何流过分支”的肌肉记忆。然后写脚本枚举 DDT，手动验证一轮的概率。接着上自动搜索工具，用同样的目标结构搜索到比手工更长的路径。最后尝试改参数——分支数、置换方式、S 盒、密钥调度的线性层，观察特征长度和概率怎么变。整个过程做完，你对 GFN 和自动化搜索的理解会扎实很多。

如果你想做点自己的小创新，最容易出成果的方向是研究不同的轮间分支置换对相关密钥特征的影响。因为 GFN 的置换矩阵决定了差分传播的周期，而置换变了，密钥差分的吸收位置也会跟着变。搜索一组置换，比较最小活跃 S 盒数量曲线，这个小实验就能支撑一篇不错的分析报告。

做这类分析做久了，我的体会是：广义 Feistel 网络的相关密钥分析，难点其实不在工具，而在于理解一条特征为什么会存在。很多特征并不是密码强度不够，而是密钥调度和分支置换在某个轮次上的交互，恰好给攻击者留了一个洞。分析者需要做的，就是把这个洞准确地描述成一条路径，然后算清楚它通往哪里。我自己会在每次实验后保留一套标准脚本模板，把轮函数、S 盒、密钥调度、搜索约束都参数化，换一个新 GFN 变体只需要改配置和 DDT，这让后续分析省掉大量重复劳动。如果你也准备长期在这个方向积累，建议尽早建立自己的分析流水线，而不是每次从零开始写脚本。