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

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

longer than the previous optimal integral distinguisher.
Key words: mixed integer linear programming (MILP); division property; linear layer; Hamming weight; integral distinguisher

随着计算机和网络技术的飞速发展, 世界已进入信息化时代. 在信息的传播过程中, 如何确保数据的安全是密
码学领域的一个重要研究方向. 分组密码具有加解密速度快、结构简单等特点, 被广泛地应用于数据加密、消息
鉴别、消息认证及密钥管理. 另一方面, 分组密码的使用离不开对密码算法广泛的安全性分析. 积分攻击 [1] 是
Knudsen 等人于 2002 年提出的一种选择明文攻击, 该攻击方法的核心步骤是构造密码算法的积分区分器, 通过上
[2]
述积分区分器可以将密码算法和随机置换进行区分, 从而进行密钥恢复攻击. 可分性 (division property) 是 Todo
在 EUROCRYPT 2015 上提出一种广义积分性质, 利用可分性可以对密码算法积分性质进行更加精确的刻画, 其
中一个显著的应用是首次在理论上对 MISTY1 算法进行了全轮攻击 [3] , 随后, Sun 等人给出了具体可分性集合大
小的下界 [4] . 可分性最初被提出之时, Todo 仅给出了基于字的可分性刻画 [2] . 为了更加精确地刻画积分性质, Todo
[5]
等人在 FSE 2016 提出基于比特的可分性 (bit-based division property) , 然而上述方法受限于复杂度只能用于不超
过 32 比特的分组密码.
混合整数线性规划 (mixed integer linear programming, MILP) 是一种在线性约束条件下求解线性目标函数的
数学问题. 2011 年 Mouha 等人 [6] 将 MILP 应用于搜索分组密码算法差分和线性活跃 S 盒数量的下界. 随后, Sun
等人 [7] 在 ASIACRYPT 2014 上进行了更加深入的研究, 并提出利用 MILP 求解基于比特密码算法的活跃 S 盒下
界. Xiang 等人 [8] 在 ASIACRYPT 2016 首次将 MILP 应用于可分性传播的刻画, 并借用 MILP 求解器有效地搜索
分组长度大于 32 比特且线性层为比特置换结构密码算法的积分区分器. 随后, 通过 MILP 模型搜索具有复杂线性
层分组密码的积分区分器成为重要的研究方向.
目前, 利用 MILP 模型搜索复杂线性层密码算法积分区分器的方法主要有如下 4 种.
Sun 等人 [9] 的方法 (记为 SW 方法): 给定一个矩阵 M ∈ F n×n , Sun 等人提出任意的线性变换均可以用一系列复
2
制和异或操作进行建模. 该方法可以应用于任何复杂的线性层, 但是它会引入大量无效的可分迹, 从而导致输出比
特更快地失去平衡. 因此, 该方法可能无法得到最优的积分区分器.
Zhang 等人 [10] 的方法 (记为 ZR 方法): 给定一个可逆矩阵 M ∈ F n×n , Zhang 等人通过研究发现矩阵 M 的有效可
2
分迹与 M 可逆子矩阵之间具有一一对应的关系. 因此, 作者将刻画线性层比特可分性的传播转化为刻画可逆子矩
阵. 该方法可以完全精确地刻画线性层的可分性传播, 但是它仅可以应用于二元矩阵.
ElSheikh 等人 [11] 的方法 (记为 EY 方法): 给定一个可逆矩阵 M ∈ F n×n , ElSheikh 等人在 ZR 方法的基础上通过
2
输入可分性搜索使得对应子矩阵为满秩的输出可分性, 从而获得有效的可分迹. 在上述过程中, 由于需要确定线性
层的输入可分性, 因此随着加密轮数的增加, 其线性层输入可分性的数量会非常庞大, 从而导致上述过程难以实
现. 因此, 作者仅将该思路应用于密码算法的第 1 轮加密, 而其他轮数则仍然使用 SW 方法.
Hong 等人 [12] 的方法 (记为 HZ 方法): 给定一个可逆矩阵 M ∈ F n×n , Hong 等人利用线性层优化实现算法获得
2
矩阵 M 的优化实现, 随后根据可分性的传播规则对矩阵 M 的优化实现进行建模, 从而更加精确地刻画矩阵 M 的
可分性传播. 该方法尽管可以应用于任意复杂的线性层, 但是它只能删除 SW 方法引入的部分无效可分迹.
针对上述几种方法存在的局限性, 本文进一步研究复杂线性层可分性传播的刻画方法, 并提出一种新的动态
选取可分性传播的技术, 该技术根据输入可分性的汉明重量选取不同的刻画方法, 进而达到模型精确程度和求解
M ∈ F n×n wt(u) = i (1 ⩽ i ⩽ n−1), 那么使
效率之间的折中. 对一个复杂线性层矩阵 , 如果其输入可分性的汉明重量
2
i
i
用 ZR 方法精确刻画矩阵 M 所有输入可分性汉明重量为 i 的可分性的传播需要的不等式数量 = C . 当 的
n
#L ZR i
取值趋近于 n/2 时, #L ZR i 的值将趋于最大值; 相反地, 当 i 的取值趋近于 1 或 n−1 时, #L ZR i 的值将趋于最小值.
受启发于上述思想, 本文将输入可分性按汉明重量的不同进行分类, 并采用不同的方法刻画不同汉明重量下的可
分性传播, 即在输入可分性汉明重量趋于 n/2 时, 采用 HZ 方法画线性层的可分性传播; 否则, 采用 ZR 方法刻画
HZ 方法, 该技术可以更加精确地刻画线性层的可分性传播;
线性层的可分性传播. 相比于 SW 方法、 EY 方法和
相比于 ZR 方法, 该技术可以应用于任意复杂的线性层. 为了体现本文技术的有效性, 我们将该技术应用于搜索