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

Abstract

近年来, 基于混合整数线性规划 (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 轮数最长的相关密钥差分特征.

Alternate abstract:

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 MILP-aided 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.