基于混合整数线性规划的八阵图不可能差分分析

Impossible Differential Cryptanalysis of Eight-Sided Fortress Based on Mixed Integer Linear Programming

八阵图(ESF)是基于LBlock改进的轻量级分组密码,具有优良的软硬件实现效率。针对ESF算法的安全性,该文借助自动化搜索工具,利用不可能差分分析方法,对算法进行安全性评估。首先结合ESF的结构特性和S盒的差分传播特性,建立了基于混合整数线性规划(MILP)的不可能差分搜索模型;其次利用算法S盒的差分传播特性和密钥扩展算法中轮子密钥间的相互关系,基于一条9轮不可能差分区分器,通过向前扩展2轮向后扩展4轮,实现了对ESF算法的15轮密钥恢复攻击。分析结果表明,该攻击的数据复杂度和时间复杂度分别为260.16和267.44,均得到有效降低,且足够抵抗不可能差分分析。

Eight-Sided Fortress(ESF),an improved lightweight block cipher based on LBlock,has excellent software and hardware implementation efficiency.For the security of ESF,with the help of automated search tools,the algorithm is evaluated for security using the impossible differential cryptanalysis.Firstly,an impossible differential search model based on Mixed Integer Linear Programming(MILP)is built by combining the structure of ESF algorithm and the differential propagation of-box.Secondly,based on a 9-round impossible differential distinguisher of ESF,using the differential propagation characteristics of the-box and the relationship of the round subkeys in the key schedule,a 15-round-attack is presented to ESF by adding two rounds in the front and adding four rounds in the end.It is found that the data complexity of plaintexts and time complexity of encryptions of the attack need are and,respectively.The results show that the data complexity and time complexity have been effectively reduced,and the proposed method is able to resist impossible differential cryptanalysis.