Page 396 - 《软件学报》2026年第5期

张语晗 等: 对缩减轮 SPECK 改进的差分-线性分析 2275

distinguisher for SPECK32 and a 12-round differential-linear distinguisher for SPECK48. Both outperform the best-known differential-
linear distinguishers for these ciphers.
Key words: cryptanalysis; symmetric cipher; differential-linear cryptanalysis; SPECK; block cipher

ARX 结构的密码算法是对称密码算法中非常重要的一类密码算法. ARX 结构组成简单, 仅包含模加 (与/或)、
循环移位和异或这 3 个基本操作; 易于实现, 在现在的大多数计算平台中, 如 X86、ARM、8-bit 微处理器等, 都支
持模加 (与/或)、移位和异或操作, 仅需要较少的代码量就可以对基于 ARX 构造的算法进行实现; 性能优越, 无论
是在软件平台还是硬件平台, 基于 ARX 构造的算法都表现良好. 结构简单、易于实现、软硬件性能优越等优点使
[1]
得 ARX 结构的密码算法受到广大密码设计者的青睐. ARX 结构被广泛应用于分组密码的设计中, 如 TEA 、
[3]
[5]
[4]
[2]
[6]
SPECK 、HIGHT 、LEA 、CHAM 、SPARX 等.
差分-线性分析是由 Langford 等人 [7] 提出的一种组合类分析方法. 假设算法 E 可以被分解为 E 0 和 E 1 两部分,
即 E = E 1 ◦ E 0 , 组合 E 0 部分一条高概率的差分和 E 1 部分一条高相关性的线性逼近可以得到算法 E 的一个有效的
差分-线性区分器. 差分-线性分析被用于许多分组密码算法的攻击中, 特别地, 对 Serpent 和 ICEPOLE 等算法的最
好的攻击是基于差分-线性分析的. 值得强调的是, Langford 等人的差分-线性分析框架依赖于两个假设: E 0 和 E 1
E 0 的输出差分的随机性假设. 在后续的研究中, 许多学者指出上述两个假设在实际情况中并
部分的独立性假设和
不一定是满足的. Biham 等人 [8] 指出 E 0 输出差分的随机性假设在实际情况下并非一定满足. Blondeau 等人 [9]
进行深入研究, 给出了只满足 E 0 和 E 1 部分是独立的情况下差分-线性逼近相关性的精确计算公式.
关于 E 0 和 E 1 部分的依赖性问题, Bar-On 等人 [10] 将 boomerang 攻击中的 sandwich 框架的思想 [11] 应用于差分-
线性分析框架中, 给出了 DLCT 框架来计算差分-线性逼近的相关性, 该框架考虑了 E 0 和 E 1 之间的依赖性. DLCT
框架基于差分线性连接表 (DLCT), 在该框架中密码算法 E 可以被分解为 E 0 、E m 、E 1 这 3 部分, 即 E = E 1 ◦ E m ◦ E 0 .
组合 E 0 部分一条高概率的差分, E m 部分一条高相关性的差分-线性逼近和 E 1 部分一条高相关性的线性逼近可以
得到算法 E 的一个有效的差分-线性区分器. E m 部分差分-线性逼近的相关性借助 DLCT 表或者实验方法来计算
得到.
ARX 类密码算法的差分-线性分析是密码分析的研究热点. 近些年来有许多相关的工作被提出. 最近, Bellini
等人 [12] 将混合整数线性规划 (MILP) 和混合整数二次约束规划 (MIQCP) 技术引入到 ARX 算法的差分-线性区分
器搜索中并应用于 SPECK 算法. 但是该方法存在一些限制, 一方面是在差分-线性区分器搜索的建模中存在一些
近似导致建模是粗糙的; 另一方面, 受求解效率的影响, 该方法只能应用于分组长度较小的算法中, 如 SPECK32.
Chen 等人 [13] 给出了一个新的搜索 ARX 类密码算法差分-线性区分器的方法, 应用于 SPECK 和 LEA 中, 得到了许
多更好的区分器.
本文贡献如下. 对 ARX 类分组密码算法的差分-线性区分器搜索算法进行研究. 首先, 通过计算 SPECK32/64
在不同随机密钥下的差分-线性逼近的实际相关性, 进一步展示了样本量的选择跟实验测量的相关性的大小之间
的关系. 然后, 结合高相关性的差分-线性逼近中差分部分和线性部分的特点, 我们给出了一个改进的差分-线性区
分器搜索算法. 区别于传统的差分-线性区分器搜索算法, 我们从高概率的差分特征和线性特征出发, 然后实验测
量中间部分差分-线性逼近的相关性, 搜索到了一些新的区分器. 具体地, 将所提差分-线性区分器搜索算法应用于
SPECK 中, 得到了 SPECK32 的 11 轮差分-线性区分器和 SPECK48 的 12 轮差分-线性区分器 (表 1 展示了与已有
差分-线性区分器的结果对比). 这些区分器都优于 SPECK 已知最好的差分-线性区分器.

表 1 差分-线性区分器结果对比

算法 轮数 相关性 参考文献
SPECK32 10 2 −12 [12]
SPECK32 10 2 −11.58 [13]
SPECK32 11 2 −15.78 第3.2节
SPECK48 11 2 −17.55 [13]
SPECK48 12 2 −22.96 第3.2节