💻 computer science

Analyzing Linear Layers in Related-Differential Cryptanalysis

本文系统研究了类 AES 密码线性层中相关差分结构的存在性，证明了此类漏洞对于所有非 MDS 矩阵、所有奇数阶对称 MDS 矩阵以及大多数循环矩阵均不可避免，同时给出了 $\mathbb{F}_{2^m}$ 上 $3 \times 3$ MDS 矩阵的完整刻画。

原作者： Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

发布于 2026-05-28

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在建造一个高安全性的金库（一种数字锁）来保护你的秘密。为了确保无人能破解它，你使用一种名为线性层的特殊混合机器。这台机器接收你的数据，将其打乱并扩散，使得输入的微小变化会在输出中引发巨大且混乱的变化。这被称为“扩散”。

数十年来，密码学家一直使用一种名为MDS 矩阵的特定混合机器，因为它被视为完美扩散的“黄金标准”。他们曾认为：“如果我们使用 MDS 矩阵，我们就安全了。”

然而，这篇论文揭示了这种思维中的一个隐藏缺陷。事实证明，即使你的混合机器是“黄金标准”（MDS），它仍可能拥有一个名为相关差分的隐秘弱点。

以下是作者发现的要点，辅以简单的类比：

1. “黄金标准”并不足够

将 MDS 属性视为一种保证：你的混合机器能将一滴墨水扩散到整张纸面上。

旧观念：如果机器能完美地扩散墨水（MDS），它就是安全的。
新发现：作者证明，如果机器未能完美扩散墨水（非 MDS），那么它必然存在隐秘弱点。
类比：想象试图在一个房间里隐藏一条秘密信息。如果房间狭小且杂乱（非 MDS），窃贼很容易找到规律潜入。作者证明，只有在一个完全宽敞、有序的房间（MDS）中，才有可能实现安全。但仅仅拥有宽敞的房间并不能保证安全；房间的形状同样重要。

2. “对称陷阱”

许多混合机器被设计为对称的，意味着如果你将其翻转，它们看起来是一样的（就像蝴蝶）。这种设计很流行，因为它易于构建。

发现：作者发现，如果一个对称机器拥有奇数个部分（如 3x3 或 5x5），它总是存在漏洞。
类比：想象一个有奇数个舞者的舞池。无论他们如何尝试配对，总有一个舞者独自站在中间，形成一个可预测的模式。作者证明，对于任何奇数大小的对称机器，总存在一个“剩余”模式，黑客可以利用它。无论你构建得多么精良，奇数这一事实使其在本质上对这种特定类型的攻击是脆弱的。

3. “循环模式”问题

另一种流行的设计是循环矩阵。想象一条传送带，其齿轮模式在圆圈中重复。这种设计高效且快速。

发现：作者研究了这些循环机器，并发现了一条基于其尺寸（称为 $n$ $n$ ）的规则。
- 如果圆圈的尺寸是 3 的倍数（如 3、6、9）或 4 的倍数（如 4、8、12），它就是脆弱的。
- 事实上，他们证明，除非尺寸是一个非常特定的数字（具体来说，不是距离 12 的倍数相差 2 或 10 的数字），否则该机器就是脆弱的。
类比：想象一个钟面。如果你试图以 3 步或 4 步的步幅绕着钟面行走，你最终会以可预测的方式反复踩到相同的点。作者表明，对于大多数循环设计，黑客可以找到一条穿过齿轮的“捷径”，从而绕过安全机制。

4. 3x3 机器的“完美配方”

最后，作者专注于最小且最常见的尺寸：3x3 矩阵。

问题：此前寻找“安全”3x3 机器的尝试是不完整的。它们提供的配方遗漏了一些成分。
解决方案：作者写下了一份完整的配方，包含15 条具体规则（数学方程）。
类比：想象烘焙蛋糕。以前的厨师说：“不要放盐。”作者则说：“实际上，你必须避免盐、糖、面粉、鸡蛋、牛奶以及另外 11 种特定成分，且需按精确组合避开。”他们提供了一份包含 15 项需避免事项的清单。如果你的 3x3 机器遵循所有 15 条规则，它就是安全的。如果它违反哪怕一条，它就是脆弱的。
结果：他们统计了存在多少种 3x3 机器，以及其中有多少是真正安全的。他们发现，“安全”的机器比我们想象的稀有得多。

核心要点总结

这篇论文就像数字锁的安全检查员。他们告诉我们：

非 MDS 机器绝对不安全。（你必须使用 MDS。）
奇数大小的对称机器绝对不安全。（如果你想要对称性，就不要使用奇数。）
大多数循环机器是不安全的。（除非尺寸非常特定。）
对于 3x3 机器，这是确保你未构建出脆弱锁的精确清单。

作者并没有发明新的锁；他们只是提供了一种更好的方法来检查我们已经在构建的锁是否存在隐藏裂缝。

技术摘要：相关差分密码分析中的线性层分析

问题陈述
在基于 SPN 的分组密码（如 AES）中，线性扩散层通常使用最大距离可分（MDS）矩阵来实现，以确保最优的分支数并抵御经典差分密码分析和线性密码分析。然而，Daemen 和 Rijmen（2009）以及 Bardeh 和 Rijmen（2022）的最新研究表明，MDS 矩阵仍可能表现出“相关差分”结构。这些结构允许构建相关差分特征，从而被用于攻击，例如针对 AES-128 的 7 轮密钥恢复攻击。虽然先前的研究已在特定实例中识别出相关差分（例如 4×4 循环矩阵、3×3 对合矩阵），但对于哪些线性层结构本质上能避免或允许这些差分，尚缺乏系统性的理解。本文研究了有限域上线性层避免相关差分的条件，旨在识别本质上能抵御此类特定密码分析向量的矩阵类别。

方法论
作者采用基于特征为 2 的有限域（ $\mathbb{F}_{2^m}$ ）的理论代数方法。方法论包括：

定义相关差分：利用 Daemen 和 Rijmen 的定义，若输入对 $(u, v)$ 和输出对 $(Mu, Mv) $满足对所有坐标$ x_i \cdot y_i \cdot (x_i \oplus y_i) = 0 $的条件，则两个差分$ (u, Mu) $和$ (v, Mv)$ 是“相关”的。
结构分析：研究矩阵属性（MDS 状态、对称性、循环结构）与非平凡相关差分对存在性之间的关系。
多项式分解：对于循环矩阵，作者将矩阵运算映射到商环 $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$ 中的多项式乘法。他们基于指数的模运算（模 2、3 和 4）分解变换多项式，以构建产生相关输出差分的特定输入差分对。
逐例枚举：对于 $3 \times 3$ 情况，作者利用任意 MDS 矩阵分解为代表形式 $M = D_1 M_1 D_2$ （其中 $D_i$ 为对角矩阵， $M_1$ 为特定代表）的方法。他们系统地分析了输入差分三元组 $(u, v, u \oplus v)$ 的所有可能汉明权重模式，以推导出不存在相关差分的必要且充分的代数条件。

主要贡献与结果

MDS 性质的必要性：
本文证明了 MDS 性质是避免相关差分的必要条件。具体而言，定理 2 表明，每个非 MDS 矩阵都至少允许一对非平凡的相关差分。这将具有抵御能力的线性层的搜索空间严格缩小至 MDS 矩阵类别。
对称矩阵的脆弱性：
作者确立了奇数维度下的对称性是一种固有脆弱性。定理 4 证明，每个奇数阶对称 MDS 矩阵都允许相关差分。这一结果排除了一大类构造，包括基于 Type 2 Cauchy 的 MDS 矩阵和奇数阶左循环矩阵（推论 2 和 3），因为它们本质上是对称的，因而存在脆弱性。
循环矩阵的脆弱性：
本文对循环矩阵提供了全面的刻画。通过分析矩阵阶数 $n$ 的模性质，作者在定理 5 中证明，当 $n \not\equiv \pm 2 \pmod{12}$ 时，阶数为 $n$ 的循环 MDS 矩阵允许相关差分。这推广了此前针对 $3 \times 3$ 和 $4 \times 4$ 情况的发现，识别出了一大类存在脆弱性的阶数。
$3 \times 3$ 矩阵的完整刻画：
重新审视 $3 \times 3$ 情况，作者推导出了完整的代数刻画。定理 7 提供了一组明确的 15 个必要且充分的多项式约束，作用于代表 $3 \times 3$ MDS 矩阵的参数。如果满足这 15 个条件中的任何一个，该矩阵就允许相关差分；如果都不满足，则该矩阵具有抵御能力。
- 本文指出，先前的刻画（例如 Otal 等人提出的）是不完整的。
- 利用这一刻画，作者计算了各种有限域（ $\mathbb{F}_{2^m}$ ）上不存在相关差分的 $3 \times 3$ MDS 矩阵的确切数量，证明了具有抵御能力的矩阵集合是所有 MDS 矩阵的严格子集（表 I）。

意义与主张
本文声称对抵御相关差分密码分析的结构先决条件进行了系统性调查。其主要意义在于：

确立界限：证明仅凭 MDS 性质不足以实现抵御，而特定的结构属性（奇数阶对称性、特定的循环阶数）则保证存在脆弱性。
细化设计标准：为 $3 \times 3$ 矩阵提供了一组具体、可验证的 15 个代数约束，使设计者能够在此维度上彻底验证或构建具有抵御能力的矩阵。
指导未来构造：通过指出非 MDS 矩阵本质上存在脆弱性，且许多常见的对称构造均失败，该工作引导未来的研究转向构造既不对称（或是偶数阶对称）又满足为抵御而推导出的特定代数约束的 MDS 矩阵。

作者总结道，虽然 $3 \times 3$ 情况已得到完整刻画，但将这些结果扩展到 $4 \times 4$ 矩阵，以及构造无相关差分的轻量级、高效 MDS 矩阵，仍然是未解决的挑战。他们还指出，循环矩阵中未解决的案例（即 $n \equiv \pm 2 \pmod{12}$ 的情况）构成了未来证明的一个猜想。