ARX结构分组密码积分区分器的自动化搜索

韩亚，王明生

（1. 中国科学院信息工程研究所信息安全国家重点实验室，北京 100093；2. 中国科学院大学网络空间安全学院，北京 100049）

1 引言

2015年，Todo[1]在欧密会首次提出积分可分性质，并利用该性质搜索分组密码积分区分器。同年，Todo[2]在美密会提出了分组密码算法MISTY1的6轮积分区分器，并对全轮MISTY1实施了理论的积分分析。根据可分性质积分传播规则，Todo给出10轮SIMON32的积分区分器，比实际搜索结果少了5轮。Wang等[3]提出了SIMON在原积分区分器的基础上增加一轮而不增加数据复杂度的方法。随后，Todo等[4]根据类 SIMON簇分组密码的结构特征，提出基于比特的可分性质，并搜索得到14轮SIMON32积分区分器。同时，他们通过改进基于比特的可分性质，提出利用三子集描述积分传播过程。利用三子集积分传播特征，他们搜索得到15轮SIMON32积分区分器。针对其他 SIMON簇分组密码算法[5]SIMON48/64/96/128，Todo等仅给出理论的积分区分器上界。

2016年，Xiang等[6]在亚密会上通过学习基于比特的可分性质，提出了一种基于混合线性规划（MILP, mixed integer linear programming）方法的积分区分器自动化搜索算法。该算法可用于搜索类SIMON簇及基于S盒的分组密码算法的积分区分器。针对 SIMON簇分组密码算法 SIMON32/48/64/96/128，他们分别给出了14、16、18、22和26轮积分区分器。但是他们无法给出与实际相符的15轮SIMON32积分区分器。随后，Sun等[7]通过改进Xiang等[6]的方法，提出搜索ARX结构分组密码积分区分器算法。基于比特可分性质，Sun等[7]通过建立积分传播模型并利用混合线性规划求解得到18轮HIGHT[8]积分区分器以及7轮LEA[9]积分区分器。同时，Sun等[7]还第一次给出了TEA[10]、XTEA、KATAN和KTANTAN等ARX结构分组密码算法的积分区分器。……