ACT、TED算法基于MILP搜索的积分分析

Integral Analysis of ACT、TED Algorithm Based on MILP

ACT和TED算法是近年来相继被提出的,分别基于SPN结构和Feistel结构而设计的两种轻量级分组密码算法.本文根据这两种算法不同的结构特性,分别构建了相关的基于比特可分性的MILP模型,并调用求解工具Gurobi对MILP模型进行求解.实验结果表明:ACT和TED算法都存在8、9、10轮积分区分器,另外TED算法还存在7轮积分区分器.根据所搜索到的积分区分器,实现了两种算法的11轮密钥恢复攻击方案.利用ACT算法的9轮积分区分器向后扩展2轮进行11轮的密钥恢复攻击时,攻击数据复杂度为2^(36.39),时间复杂度为2^(36.39)次11轮加密,存储复杂度为2^(20).利用TED算法的8轮积分区分器向后扩展3轮进行11轮的密钥恢复攻击时,数据复杂度为2^(60.81),时间复杂度为2^(109.54)次11轮加密,存储复杂度为2^(59).

The ACT and TED algorithms are two lightweight block cipher algorithms that have been proposed in recent year.which are designed based on the SPN structure and the Feistel structure respectively.According to the different structural characteristics of the two algorithms,this paper constructs related MILP models based on bit separability,and calls the solving tool Gurobi to solve the MILP model.The experimental results show that both ACT and TED algorithms have 8,9,10 rounds of integral distinguisher,and TED algorithm also has 7 rounds of integral distinguisher.According to the searched points discriminator,11 rounds of key recovery attack schemes of two algorithms are realized.When using the 9-round integrator discriminator of the ACT algorithm to extend backward by 2 rounds for 11 rounds of key recovery attacks,the data complexity is 2^(36.39),the time complexity is about encrypt for 11-round with 2^(36.39) times and the storage complexity is about 2^(20).When the 8-round integrator discriminator of the TED algorithm is used to extend backward 3 rounds for 11 rounds of key recovery attacks,the data complexity is 2^(60.81),the time complexity is about encrypt for 11-round with 2^(109.54) times and the storage complexity is about 2^(59).