基于MILP的轻量级密码算法ACE的差分分析  

Differential analysis of lightweight cipher algorithm ACE based on MILP

作　　者：刘帅[1] 关杰[1] 胡斌[1] 马宿东 LIU Shuai;GUAN Jie;HU Bin;MA Sudong(School of Cryptography Engineering,Information Engineering University,Zhengzhou 450001,China)

机构地区：[1]信息工程大学密码工程学院,河南郑州450001

出　　处：《通信学报》2023年第1期39-48,共10页Journal on Communications

基　　金：国家自然科学基金资助项目(No.61802437,No.62102448)。

摘　　要：研究了轻量级密码算法ACE的差分性质。首先定义了n维环形与门组合,充分分析了该结构中与门之间的相互关系,仅利用O(n)个表达式给出其精确的MILP差分刻画,将ACE算法中的非线性操作转化为32维环形与门组合,从而给出了ACE算法的MILP差分模型。其次根据MILP模型求解器Gurobi的求解特点,给出了快速求解ACE的MILP差分模型的方法。对于3~6步的ACE置换,得到了最优差分链,利用多差分技术给出了更高概率的差分对应,从而给出了ACE置换为3步的认证加密算法ACE-Aε-128的差分伪造攻击与哈希算法ACE-H-256的差分碰撞攻击,成功概率为2^(-90.52),并证明了4步ACE置换达到了128bit的差分安全边界。实际上,n维环形与门组合的MILP差分刻画具有更多的应用场景,可应用于SIMON、Simeck等密码算法的分析中。The differential property of the lightweight cipher algorithm ACE was researched. n-dimension ring AND-gate combination was defined and its differential property was described accurately by only O(n) expressions with the MILP method by analyzing the relationship among AND gates. The nonlinear operation of ACE was transformed to the 32-dimension ring AND-gate combination and the MILP differential model of ACE was proposed. According to the characteristics of Gurobi solver, a model for fast solving the MILP differential model of ACE was given. For ACE permutation with 3 to 6 steps, the optimal differential characteristic was obtained and its probability was improved by multi-difference technique. The differential forge attack on authenticated encryption algorithm ACE-Aε-128 and the differential collision attack on hash algorithm ACE-H-256 was given with 3-step ACE permutation, and the success probability was 2^(-90.52). And it was proved that the 4-steps ACE permutation arrived the differential security bound of 128 bit. Actually, the MILP differential description of ring AND-gate combination can be applied on more cipher algorithms, such as SIMON, Simeck.

关 键 词：轻量级密码算法 混合整数线性规划 环形与门组合 差分分析 

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