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

来源：电子与信息学报杂志2023年第12期北京时间：

作者：杜小妮, 梁丽芳, 贾美纯, 李锴彬

单位：1.西北师范大学数学与统计学院 兰州 7300702.西北师范大学计算机科学与工程学院 兰州 7300703.西北师范大学密码技术与数据分析重点实验室 兰州 7300704.甘肃省数学与统计学基础学科研究中心 兰州 730070

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

关键词：八阵图(ESF), 不可能差分分析, 混合整数线性规划(MILP)

基金资助：国家自然科学基金(62172337)，甘肃省自然科学基金重点项目(23JRRA685)，甘肃省基础研究创新群体项目(23JRRA684)