KATAN族密码的立方攻击和积分攻击_张贵显.pdf
《KATAN族密码的立方攻击和积分攻击_张贵显.pdf》由会员分享,可在线阅读,更多相关《KATAN族密码的立方攻击和积分攻击_张贵显.pdf(14页珍藏版)》请在咨信网上搜索。
1、密码学报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
2、族密码进行了立方攻击和积分攻击.具体来说,针对 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/
3、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.00
4、0600英文引用格式: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 Un
5、iversity,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 lon
6、ger-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 KATA
7、N48,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
8、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
9、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
10、/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 年欧密会上提出的密码分析方法.立方攻击的基本思想就是将输出比特写成公
11、开变元和秘密变元的多项式形式,然后选定一些公开变元作为立方变元,固定除立方变元以外的公开变元,立方变元取遍所有可能取值构成的集合 CI,将 CI中的所有数据加密求和,同时其和能表达成秘密变元的多项式(被称作“超级多项式”),最后通过求解秘密变元的多项式方程组获取秘密变元的取值.积分攻击2是由 Knudsen 等人在总结 Square 攻击3、Saturation 攻击4和 Multiset 攻击5的基础上提出的一种密码分析方法.积分攻击的最主要的环节是寻找积分区分器.比特可分性6由 Todo等人在 2016 年 FSE 会议上首次提出,其主要包括二子集比特可分性和三子集比特可分性,是寻找积分区
12、分器最强大的工具之一.比特可分性可以将密码学组件更多的代数信息考虑到积分区分器的构造中,更精确地刻画密码算法的积分特征,从而可以构造更好的积分区分器.在 2017 年美密会上,Todo 等人7首次将二子集可分性与立方攻击结合并将它应用在 TRIVIUM、Grain-128a 等密码算法上,取得了当时最好的攻击结果.在 2019 年亚密会上,Wang 等人8提出了三子集可分性的自动化搜索算法,有效解决了三子集可分性的自动化搜索问题.他们将三子集可分性与立方攻击结合成功恢复了 TRIVIUM 的更高轮数的超级多项式.在此基础上,Hao 等人9于 2020 年欧密会上提出无未知集合的三子集可分性和“
13、特定位置可分性不做设定”的搜索策略,并将它应用到 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 的积分性质进行评估,分
14、别得到了 101/84/72.3 轮的积分区分器,改进了已有的积分区分器结果.2020 年,Zahra 等人13首次将二子集可分性应用到 KATAN 族密码的立方攻击中,将超级多项式的恢复问题转化为布尔函数可满足性问题(SAT 问题),并用 SAT 求解器求解,分别给出了 90/50 轮的 KATAN32/48 的立方攻击结果.然而Zahra 等人的方法只能考察小立方阶的情况,限制了立方攻击的效果,所以他们对 KATAN48 的攻击效果提升并不明显,对 KATAN64 并未给出立方攻击结果.基于以上研究现状,本文重新对 KATAN 密码抵抗立方攻击和积分攻击的能力进行评估.本文具体的研究工作如
15、下:(1)给出 KATAN 族密码的改进的立方攻击结果.首先将 KATAN 密码的加密算法和密钥生成算法看成一个整体,将密钥看成内部状态的一部分,从而可以利用无未知集合三子集可分性恢复超级多项式,然后给出了刻画其三子集可分性传播的 MILP 模型,最终利用 Gurobi 求解器进行求解恢复超级多项式.具体来说,针对 KATAN32,最多可以恢复 102 轮的超级多项式,但是只能恢复一个超级多项式.为了降低立方攻击的时间复杂度,尝试减少轮数以恢复更多的超级多项式.当减少至 95 轮时,可以恢复 9 个超级多项式.同理,针对 85 轮的 KATAN48,恢复了 1 个超级多项式;针对 77 轮的
16、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轮和
17、35 轮.针对 KATAN64,给出了 73 轮的立方攻击,时间复杂度为 279,比已有最好的立方攻击的结果提升了 43 轮.详细攻击结果对比见表1.表 1 KATAN 族密码攻击结果对比Table 1Summary results of attacks on KATAN family ciphers算法攻击方法轮数时间复杂度数据复杂度存储复杂度文献KATAN32立方攻击60239230.3-1490277232-1395271232-本文102279231-本文积分攻击125279.3231231本文KATAN48立方攻击40249225.9-1450256234.3-1377265.624
18、8-本文85279247-本文积分攻击100279.2247247本文KATAN64立方攻击30235220.7-1473279263-本文积分攻击81279.1263263本文(2)给出 KATAN 族密码的积分攻击结果.当超级多项式退化为常数时,便得到了积分区分器.因此,本文的方法同样可以寻找 KATAN 的积分区分器.针对 KATAN32/48,分别得到了 101/84 轮的积分区分器,与之前最好的积分区分器一致;针对 KATAN64,得到了 73 轮的积分区分器,比之前最好的72.3 轮略有改进.当轮数继续增加时,超级多项式将是关于密钥的非常值多项式.因此,与文献 11,12不同,对于
19、 KATAN32/48/64 来说,当分别固定输入可分性为 inI31/inI47/inI63时,本文的方法可以证明102/85/73.3 轮不存在区分器.利用得到的积分区分器,分别对 125/100/81 轮的 KATAN32/48/64 密码进行积分攻击,时间复杂度分别为 279.3/279.2/279.1.2基础知识2.1符号说明令 n 和 m 分别表示对称密码的秘密变元数目和公开变元数目,I 0,1,m 1,那么 inI表示F2上的 n+m 维向量,定义如下:inIi=|1,如果 i I0,如果 i 0,1,m 1I,如果 i/0,1,m 1,其中,0 i n+m 1,*表示不做设定,
20、即可能有 0 和 1 两种取值.令 Ii(0 i m 1)为集合0,1,m 1i.令 outj(0 j m 1)为第 j 个分量为 1 其余分量为 0 的 n+m 维单位向量.张贵显 等:KATAN 族密码的立方攻击和积分攻击3752.2立方攻击令 k Fn2和 x Fm2分别表示 n 个秘密变元和 m 个公开变元,那么对称密码体制可以表示成f(k,x),其中 f 表示一个输入为 n+m 比特,输出为若干比特的多项式函数.在分组密码中,k 表示密钥,x 表示明文.令 I=i0,i1,i|I|1 0,1,m 1 为选定的立方变元的下标集合,那么,f(k,x)可以唯一表示为:f(k,x)=tI p
21、(k,x)+q(k,x),其中 tI=xi0 xi1x|I|1,多项式 p(k,x)不包含 xi0,xi1,xi|I|1 中任何变元,q(k,x)中的任一单项至少不包含 xi1,xi2,xi|I|中一个变元.那么,p(k,x)称为集合 I 在 f(k,x)中的超级多项式.CI为 xi0,xi1,xi|I|1 中变元取遍所有可能取值而其它公开变元固定为 0 构成的立方集合,则有:xCIf(k,x)=xCItI p(k,x)+xCIq(k,x)=p(k,x).立方攻击包含两个阶段:线下预处理阶段和线上阶段.线下阶段是选定合适的集合 I 然后恢复相应的超级多项式;线上阶段通过求解获得的超级多项式方程
22、组从而获得密钥信息.关于立方攻击更加详尽的过程可参考文献 1.2.3可分性本节只对涉及到的三子集可分性和无未知集合三子集可分性进行简要介绍.无未知集合三子集可分性的传播法则及 MILP 模型见附录 1 和附录 2.定义 1(三子集可分性6)令 X 为 Fm2上一个集合,即对任意的 x X,均有 x Fm2,对于 m 维比特向量空间 Fm2的两个子集 K 和 L,若集合 X 满足以下条件:xXxu=|不确定,如果存在 k K 满足 u k1,如果上一种情况不满足且存在 L 满足 u=0,其他情况,则称集合 X 满足三子集可分性 D1mK,L.定义 2(无未知集合的三子集可分性9)令 X 为 Fm
23、2上一个集合,即对任意的 x X,均有 x Fm2,对于 m 维比特向量空间 Fm2的子集 L,若集合 X 满足以下条件:xXx=1,如果 L 存在奇数个 0,其他情况,则称集合 X 满足无未知集合的三子集可分性 T1mL.定义 3(三子集可分性链9)对于 r 轮密码算法 E,令其初始的三子集可分性向量集合为 T1mL0,第 i轮轮函数输出的三子集可分性为 T1mLi.那么当考虑三子集可分性传播 def=L0 L1 Lr时,对于任意一个向量 i+1 Li+1,必然存在一个向量 i Li可以通过三子集可分性传播法则产生 i+1.从而对于(0,1,r)L0L1Lr,如果所有 i,i 0,1,r 1
24、 均能通过三子集可分性传播法则产生 i+1,便称(0 1 r)为一条 r 轮三子集可分链.2.4KATAN 密码介绍KATAN 族密码10是由 De Cannire 等人在 2009 年 CHES 会议上提出来的轻量级分组密码算法,根据分组规模可分为 KATAN32、KATAN48、KATAN64,它们的迭代轮数均为 254 轮,密钥均为 80 比特.如图1所示,对于 KATAN32,明文被加载进两个线性反馈移位寄存器 L1 和 L2,在每一轮加密中,线性反馈移位寄存器 L1 和 L2 均向高位移动一位,然后两个非线性函数 fa和 fb产生的更新比特分别载入两个移位寄存器的最低位,在迭代 25
25、4 轮之后移位寄存器 L1 和 L2 中的数据便是密文.两个非线性函数376Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023fa和 fb定义如下:fa(L1)=L1x1 L1x2 (L1x3 L1x4)(L1x5 IR)ka,fb(L2)=L2y1 L2y2 (L2y3 L2y4)(L2y5 L2y6)kb.其中 IR 是轮常数(如果 IR 为 0,L1x5 不参与更新;如果 IR 为 1,L1x5 参与更新.IR 取值见表2),ka和 kb是密钥比特.图 1 KATAN 族密码算法的函数结构Figure 1 Outline o
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- KATAN 密码 立方 攻击 积分 张贵显
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。