Page 413 - 《软件学报》2024年第4期

黄明 等: 分组密码复杂线性层可分性传播的 MILP 刻画方法 1991

{0,16}, Θ ZR = {1,2,14,15}, Θ HZ = {3,4,...,13}, 并将
模型: 根据线性层矩阵输入可分性汉明重量的不同进行分类
Θ ZR 继续分为 Θ ZR 0 = {1}, Θ ZR 1 = {2},Θ ZR 2 = {14},Θ ZR 3 = {15} 这 4 种情况, 对集合 {0,16}, 使用约束条件 w(u) = w(v)
表示可分性的传播, 对集合 {3,4,...,13}, 则使用约束不等式集 L HZ 表示可分性的传播, 对集合 {1},{2},{14},{15} 则
HZ 方法构建可分性传
分别使用约束不等式集 L ZR 1 , L ZR 2 , L ZR 14 , L ZR 15 表示可分性的传播, 其中 L HZ 表示使用
播的不等式, L ZR 1 , L ZR 2 , L ZR 14 , L ZR 15 分别表示使用 ZR 方法构建输入可分性汉明重量为 1, 2, 14, 15 时可分性传
播的不等式.
在文献 [16] 中, 作者利用代数次数估计的方法评估 Saturnin 算法抗积分分析的能力, 当初始可分性为 253 比
特活跃时, Saturnin 算法存在 8 轮的积分区分器. 而如果只使用 ZR 方法对 Saturnin 算法线性层可分性传播进行建
模, 8 轮线性层需要的不等式数量为 65535×16×8 = 8388480 个, 这比 uBlock128 算法需要的数量更多, 在内存为
256 GB 的工作站中也会发生内存溢出无法求解的情况. 然而, 利用本文技术构建 MILP 建模可以在个人笔记本 16 GB
内存上得到活跃比特更少且轮数更长的 9 轮积分区分器:
( ) 9轮 ( )
20
C A 236 → B 256 .
4 总 结

本文提出了一种基于动态选取策略构建 MILP 模型的新技术, 并结合比特可分性理论构建了更加精确且实用
的可分性传播模型. 该技术的优势是可以对点集进行分类描述, 打破传统 MILP 模型的约束条件需要满足全部点
集的局限. 例如对特定百万量级甚至更高量级的点用较少的不等式精确刻画比较困难, 因此可以根据特定需求对
点进行分类, 对每类较少的点进行不等式刻画. 基于上述思想, 本文将线性层的输入可分性按照汉明重量的不同进

行划分, 并当输入可分性汉明重量趋近于 n/2 时, 采用 ZR 方法刻画线性层的可分性传播; 否则, 采用 HZ 方法刻
画线性层的可分性传播. 为了验证该技术的有效性, 本文将该技术应用于 uBlock 和 Saturnin 算法. 实验结果表明:
该技术可以搜索到 uBlock 和 Saturnin 算法当前最优的积分区分器, 且均比之前最优积分区分器多一轮. 同时, 该
技术的思想可以应用于分析分组密码的其他密码性质, 如何利用该思想改进分组密码的其他分析技术可能是未来
的一个研究方向.

References:
[1] Knudsen L, Wagner D. Integral cryptanalysis. In: Proc. of the 9th Int’l Workshop on Fast Software Encryption. Leuven: Springer, 2002.
112–127. [doi: 10.1007/3-540-45661-9_9]
[2] Todo Y. Structural evaluation by generalized integral property. In: Proc. of the 34th Annual Int’l Conf. on the Theory and Applications of
Cryptographic Techniques. Sofia: Springer, 2015. 287–314. [doi: 10.1007/978-3-662-46800-5_12]
[3] Todo Y. Integral cryptanalysis on full MISTY1. In: Proc. of the 35th Annual Cryptology Conf. Santa Barbara: Springer, 2015. 413–432.
[doi: 10.1007/978-3-662-47989-6_20]
[4] Sun B, Hai X, Zhang WY, Cheng L, Yang ZC. New observation on division property. Science China Information Sciences, 2017, 60(9):
098102. [doi: 10.1007/s11432-015-0376-x]
[5] Todo Y, Morii M. Bit-based division property and application to SIMON family. In: Proc. of the 23rd Int’l Conf. on Fast Software
Encryption. Bochum: Springer, 2016. 357–377. [doi: 10.1007/978-3-662-52993-5_18]
[6] Mouha N, Wang QJ, Gu DW, Preneel B. Differential and linear cryptanalysis using mixed-integer linear programming. In: Proc. of the
7th Int’l Conf. on Information Security and Cryptology. Beijing: Springer, 2012. 57–76. [doi: 10.1007/978-3-642-34704-7_5]
[7] Sun SW, Hu L, Wang P, Qiao KX, Ma XS, Song L. Automatic security evaluation and (related-key) differential characteristic search:
Application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Proc. of the 20th Int’l Conf. on the Theory
and Application of Cryptology and Information Security. Springer, 2014. 158–178. [doi: 10.1007/978-3-662-45611-8_9]
[8] Xiang ZJ, Zhang WT, Bao ZZ, Lin DD. Applying MILP method to searching integral distinguishers based on division property for 6
lightweight block ciphers. In: Proc. of the 22nd Int’l Conf. on the Theory and Application of Cryptology and Information Security. Hanoi:
Springer, 2016. 648–678. [doi: 10.1007/978-3-662-53887-6_24]
[9] Sun L, Wang W, Wang MQ. MILP-aided bit-based division property for primitives with non-bit-permutation linear layers. IET
Information Security, 2020, 14(1): 12–20. [doi: 10.1049/iet-ifs.2018.5283]