KATAN族密码的立方攻击和积分攻击_张贵显.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(2):372385密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618KATAN 族密码的立方攻击和积分攻击*张贵显,胡 斌信息工程大学 密码工程学院,郑州 450001通信作者:张贵显,E-mail:摘要:为了重新评估 KATAN 族密码抵抗立方攻击和积分攻击的安全性,利用无未知集合三子集可分性结合混合整数线性规划(MILP)搜索工具,恢复了更长轮数的超级多项式并且搜索得到了积分区分器,进而对 KATAN 族密码进行了立方攻击和积分攻击.具体来说,针对 KATAN32,给出了 102 轮和 95 轮的立方攻击,时间复杂度分别是 279和 271;针对 KATAN48,给出了 85 轮和 77 轮的立方攻击,时间复杂度分别是 279和 265.6;针对 KATAN64,给出了 73 轮的立方攻击,时间复杂度为 279.将 KATAN32/48/64的已有最好的立方攻击结果分别提升了 12/35/43 轮.当超级多项式退化为常数,便得到了积分区分器.因此,所提算法也可以搜索积分区分器.针对 KATAN32/48/64 的积分区分器分别可达到 101 轮、84 轮、73轮,从而可以对 125/100/81 轮的 KATAN32/48/64 进行积分攻击,时间复杂度分别为 279.3/279.2/279.1.结果表明,针对超过 102/85/73 轮的 KATAN32/48/64 并不存在有效的立方攻击结果,超过 125/100/81轮的 KATAN32/48/64 也不存在有效的积分攻击结果.关键词:密码分析;立方攻击;积分攻击;三子集可分性中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000600中文引用格式:张贵显,胡斌.KATAN 族密码的立方攻击和积分攻击J.密码学报,2023,10(2):372385.DOI:10.13868/ki.jcr.000600英文引用格式:ZHANG G X,HU B.Cube attacks and integral attacks on KATAN family ciphersJ.Journalof Cryptologic Research,2023,10(2):372385.DOI:10.13868/ki.jcr.000600Cube Attacks and Integral Attacks on KATAN Family CiphersZHANG Gui-Xian,HU BinCollege of Cryptography Engineering,Information Engineering University,Zhengzhou 450001,ChinaCorresponding author:ZHANG Gui-Xian,E-mail:Abstract:In order to reevaluate the security of KATAN against cube attack and integral attack,using three-subset division property without unknown subset combined with mixed integer linear pro-gramming(MILP)search tool,the longer-round superpolys and integral distinguishers are obtained,sothat cube attacks and integral attacks on KATAN family ciphers can be carried out.Specifically,withrespect to KATAN32,102-round and 95-round cube attacks are given,and the time complexities are279and 271respectively.With respect to KATAN48,85-round and 77-round cube attacks are given,and the time complexities are 279and 265.6respectively.With respect to KATAN64,73-round cubeattack is given,and the time complexity is 279.This paper improves the best cube attack results for*基金项目:国家自然科学基金(62102448)Foundation:National Natural Science Foundation of China(62102448)收稿日期:2022-02-07定稿日期:2022-05-09张贵显 等:KATAN 族密码的立方攻击和积分攻击373KATAN32/48/64 by 12/35/43 rounds respectively.If the superpoly is degenerated to be a constant,anintegral distinguisher can be obtained.The proposed algorithms can also search integral distinguishers.The integral distinguishers for KATAN32/48/64 can reach 101/84/73 rounds respectively.Therefore,125-/100-/81-round integral attacks on KATAN32/48/64 can be conducted respectively.The timecomplexities are 279.3,279.2and 279.1respectively.The analysis results show that there are no effectivecube attacks on KATAN32/48/64 with more than 102/85/73 rounds respectively,and there are noeffective integral attacks on KATAN32/48/64 with more than 125/100/81 rounds respectively.Key words:cryptanalysis;cube attack;integral attack;three-subset division property1引言立方攻击1是由 Dinur 等人在 2009 年欧密会上提出的密码分析方法.立方攻击的基本思想就是将输出比特写成公开变元和秘密变元的多项式形式,然后选定一些公开变元作为立方变元,固定除立方变元以外的公开变元,立方变元取遍所有可能取值构成的集合 CI,将 CI中的所有数据加密求和,同时其和能表达成秘密变元的多项式(被称作“超级多项式”),最后通过求解秘密变元的多项式方程组获取秘密变元的取值.积分攻击2是由 Knudsen 等人在总结 Square 攻击3、Saturation 攻击4和 Multiset 攻击5的基础上提出的一种密码分析方法.积分攻击的最主要的环节是寻找积分区分器.比特可分性6由 Todo等人在 2016 年 FSE 会议上首次提出,其主要包括二子集比特可分性和三子集比特可分性,是寻找积分区分器最强大的工具之一.比特可分性可以将密码学组件更多的代数信息考虑到积分区分器的构造中,更精确地刻画密码算法的积分特征,从而可以构造更好的积分区分器.在 2017 年美密会上,Todo 等人7首次将二子集可分性与立方攻击结合并将它应用在 TRIVIUM、Grain-128a 等密码算法上,取得了当时最好的攻击结果.在 2019 年亚密会上,Wang 等人8提出了三子集可分性的自动化搜索算法,有效解决了三子集可分性的自动化搜索问题.他们将三子集可分性与立方攻击结合成功恢复了 TRIVIUM 的更高轮数的超级多项式.在此基础上,Hao 等人9于 2020 年欧密会上提出无未知集合的三子集可分性和“特定位置可分性不做设定”的搜索策略,并将它应用到 TRIVIUM、Grain-128AEAD 等密码算法上,得到了目前最好的立方攻击结果.KATAN 族密码10是由 De Cannire 等人在 2009 年 CHES 会议上提出.算法提出后,密码学界对KATAN 抵抗已知攻击的能力做了评估,包括抵抗积分攻击、立方攻击的能力.2016 年,Sun 等人11利用二子集可分性对 KATAN32/48/64 的积分性质进行评估,分别得到 99/63.5/72.3 轮的积分区分器.在CT-RSA 2019 上,Hu 等人12提出简化的三子集可分性并对 KATAN32/48/64 的积分性质进行评估,分别得到了 101/84/72.3 轮的积分区分器,改进了已有的积分区分器结果.2020 年,Zahra 等人13首次将二子集可分性应用到 KATAN 族密码的立方攻击中,将超级多项式的恢复问题转化为布尔函数可满足性问题(SAT 问题),并用 SAT 求解器求解,分别给出了 90/50 轮的 KATAN32/48 的立方攻击结果.然而Zahra 等人的方法只能考察小立方阶的情况,限制了立方攻击的效果,所以他们对 KATAN48 的攻击效果提升并不明显,对 KATAN64 并未给出立方攻击结果.基于以上研究现状,本文重新对 KATAN 密码抵抗立方攻击和积分攻击的能力进行评估.本文具体的研究工作如下:(1)给出 KATAN 族密码的改进的立方攻击结果.首先将 KATAN 密码的加密算法和密钥生成算法看成一个整体,将密钥看成内部状态的一部分,从而可以利用无未知集合三子集可分性恢复超级多项式,然后给出了刻画其三子集可分性传播的 MILP 模型,最终利用 Gurobi 求解器进行求解恢复超级多项式.具体来说,针对 KATAN32,最多可以恢复 102 轮的超级多项式,但是只能恢复一个超级多项式.为了降低立方攻击的时间复杂度,尝试减少轮数以恢复更多的超级多项式.当减少至 95 轮时,可以恢复 9 个超级多项式.同理,针对 85 轮的 KATAN48,恢复了 1 个超级多项式;针对 77 轮的 KATAN48,可以恢复15 个超级多项式.针对 73 轮的 KATAN64,恢复了 2 个超级多项式.因此,可以利用这些超级多项式对KATAN 族密码进行立方攻击.针对 KATAN32,分别给出了 102 轮和 95 轮的立方攻击,攻击时间复杂374Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023度分别是 279和 271,比已有最好的立方攻击的结果分别提升了 5 轮和 12 轮.针对 KATAN48,给出了85 轮和 77 轮的立方攻击,时间复杂度分别是 279和 265.6,比已有最好的立方攻击的结果分别提升了 27轮和 35 轮.针对 KATAN64,给出了 73 轮的立方攻击,时间复杂度为 279,比已有最好的立方攻击的结果提升了 43 轮.详细攻击结果对比见表1.表 1 KATAN 族密码攻击结果对比Table 1Summary results of attacks on KATAN family ciphers算法攻击方法轮数时间复杂度数据复杂度存储复杂度文献KATAN32立方攻击60239230.3-14