基于MILP对轻量级密码算法FBC-128的差分分析  

MILP-Based Differential Cryptanalysis of the FBC-128 Lightweight Cipher

作　　者：赵琪 樊婷 韦永壮[1] ZHAO Qi;FAN Ting;WEI Yong-zhuang(Guangxi Key Laboratory of Cryptography and Information Security,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China)

机构地区：[1]桂林电子科技大学广西密码学与信息安全重点实验室,广西桂林541004

出　　处：《电子学报》2024年第6期1896-1902,共7页Acta Electronica Sinica

基　　金：国家自然科学基金(No.62162016);广西自然科学基金创新研究团队项目(No.2019GXNSFGA245004)。

摘　　要：FBC(Feistel-based Block Cipher)是入围全国密码算法设计竞赛第二轮的轻量级分组密码.由于它具备算法结构简洁、安全性高及软硬件实现性能卓越等优点,备受业界广泛关注.FBC密码算法的数据分组长度和密钥长度至少为128比特,记为FBC-128.目前对FBC-128算法差分攻击的最好结果是12轮,时间复杂度为293.41次加密,数据复杂度为2122个选择明文对.然而,FBC算法是否存在更长的差分区分器,能否对其进行更高轮数的密钥恢复攻击仍有待解决.本文基于混合整数线性规划(MILP)的自动化搜索方法,提出了“分段统计法”来求解FBC-128的差分特征.实验测试结果表明:FBC-128存在15轮差分区分器,其概率为2-121.然后将其向后扩展1轮,对16轮FBC-128算法发起密钥恢复攻击,其数据复杂度为2121个选择明文数据量,时间复杂度为292.68次加密.与已有结果相比,差分区分器和密钥恢复攻击都提升了4轮,并且所需的数据复杂度和时间复杂度更低.FBC(Feistel-based Block Cipher)is a lightweight block cipher selected in the second round of the National Cryptographic Algorithm Design Competition.It has many advantages such as simple algorithm structure,high security and excellent implementation performance,and has attracted much attention in the industry.The block size and key length of FBC are at least 128 bits,denoted as FBC-128.At present,the best result of differential attack on FBC-128 is 12-round.The time complexity is 293.41 encryptions,and the data complexity is 2122 chosen-plaintexts.However,it is still to be solved whether there is a longer differential distinguisher and higher rounds of key recovery attack on FBC.In this paper,a segmental statistical method is proposed to search the differential characteristic of FBC-128 based on the mixed-integer linear programming technology.The results show that FBC-128 exists15-round differential distinguisher with probability 2-121.Then,we extend it backward by one round,and launch a key recovery attack on 16-round FBC-128.The data complexity is 2121 chosen-plaintexts,and the time complexity is 292.68 encryptions.Compared with the existing results,the differential distinguisher and key recovery attacks are increased by 4 rounds with lower data and time complexity.

关 键 词：自动化分析 混合整数线性规划 分组密码算法 差分区分器 密钥恢复攻击 FBC算法 

分 类 号：TN918[电子电信—通信与信息系统]