基于MILP的相关密钥差分分析安全评估算法改进

Improvement of MILP-aided Security Evaluation Algorithm of Related-key Differential Cryptanalysis

近年来,基于混合整数线性规划(MILP)的密码分析方法在对称密码的安全性分析中发挥了重要作用. Zhou等人在FSE 2020上提出了结合分治法,大幅度提高基于MILP的差分和线性特征搜索方法效率.本文将Zhou等人的方法扩展到相关密钥差分特征搜索,提出了一种更高效的基于MILP的相关密钥差分分析安全评估新算法.应用新算法评估了PRESENT-80/128抵抗相关密钥差分分析的安全性,得到了高达15轮的最小活跃S盒数量和高达12轮的最优相关密钥差分特征,并由此得到了迄今最紧的PRESENT-80/128抵抗相关密钥差分分析安全界.找到了一条概率为2^(-62)的15轮PRESENT-80相关密钥差分特征,和一条概率为2-60的16轮PRESENT-128相关密钥差分特征,是目前对于PRESENT-80/128轮数最长的相关密钥差分特征.

In recent years, mixed-integer linear programming(MILP)-aided methods have played an important role in providing security evaluation of symmetric-key primitives. At FSE 2020, Zhou et al. proposed an MILP-aided algorithm that employed a divide-and-conquer approach, significantly improving the search efficiency for differential and linear characteristics. This paper extends Zhou et al.’s method to search for related-key differential characteristics and proposes a more efficient MILPaided algorithm for evaluating the security against related-key differential cryptanalysis. Applying this new algorithm to PRESENT-80/128, the minimum number of active S-boxes of related-key differential characteristics can be obtained for up to 15 rounds and the best related-key differential characteristic can be obtained for up to 12 rounds, from which the tightest security bounds against related-key differential cryptanalysis for PRESENT-80/128 is obtained. Furthermore, related-key differential characteristics of 15-round PRESENT-80 and 16-round PRESENT-128 can be found with probabilities of 2^(-62)and 2-60, respectively.