SIMON算法的不可能差分分析

密码学报ISSN2095-7025CN10-1195/TNE-mail:[e-mail]search,2015,2(6):505–514©《密码学报》编辑部版权所有.Tel/Fax:[phone]SIMON算法的不可能差分分析*陈展1,王宁21.清华大学计算机系密码理论与技术研究中心,北京1000842.山东大学密码技术与信息安全教育部重点实验室,济南250100通讯作者:陈展,E-mail:[e-mail]摘要:SIMON算法是2013年由NSA提出的一族轻量级分组密码算法,至今已有很多密码学者进行了安全性分析,如线性分析,差分分析,不可能差分和零相关线性hull分析等.SIMON算法根据不同的分组和密钥长度一共提供了10个不同的版本,可以满足不同的安全性需求.在这篇论文中,我们首先利用自动化搜索技术,获得了SIMON32算法最长的不可能差分路径,在此基础上对SIMON算法进行了不可能差分分析.我们给出了19轮SIMON32/64的不可能差分分析的详细过程.在数据收集过程中,我们利用明文差分和第一轮输出差分与密钥无关的特点,使用建立并解方程的方法构造出满足明文和第一轮输出差分条件的明密文对,极大地降低了数据收集过程的计算复杂度.在密钥恢复过程中,采用Wang等提出的动态密钥猜测技术,降低了密钥过滤过程中的计算复杂度,改进了之前SIMON算法的不可能差分结果.关键词:SIMON算法;不可能差分攻击;比特差分;分组密码中图法分类号:TP918文献标识码:ADOI:10.13868/j.cnki.jcr.000097中文引用格式:陈展,王宁.SIMON算法的不可能差分分析[J].密码学报,2015,2(6):505–514.英文引用格式:ChenZ,WangN.Impossibledifferentialcryptanalysisofreduced-roundSIMON[J].JournalofCryptologicResearch,2015,2(6):505–514.ImpossibleDifferentialCryptanalysisofReduced-roundSIMONCHENZhan1,WANGNing21.CenterforCryptologyStudy,DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,China2.KeyLabofCryptographicTechnologyandInformationSecurityMinistryofEducation,ShandongUniversity,Jinan250100,ChinaCorrespondingauthor:CHENZhan,E-mail:[e-mail]:SIMONisalightweightblockcipherintroducedbyNSAandhasattractedlotsofattentioneversinceitspublicationin2013.TherehavebeennumerousattacksonSIMONsuchaslinear,differential,impossibledifferential,andzerocorrelationlinearhullcryptanalysis.TheSIMONfamilyhas10versionsdependingondifferentblocksizesandkeysizestosatisfyvarioussecurityrequirements.Inthispaper,weuseautomatic-searchtechniquetoobtainthelongestimpossibledifferentialpathsofSIMON,andthenweproposeimpossibledifferentialattacks.WegivedetailedprocessofattacksonSIMON32/64.Intheprocessofstructureconstruction,weexploittheconnectionofplaintextandroundoneoutputdifferenceofthefirstround,whichisindependentofkeybits.Bybuildingandsolvingequationsofthesecondroundwegetplaintextpairsthatsatisfythebitconditionsofthefirstroundthusreducethecomplexityofdatacollectingphasegreatly.Inthekeyrecoveryphase,*基金项目:国家自然科学基金重点项目(61133013)收稿日期:2015-04-14定稿日期:2015-12-07506JournalofCryptologicResearch密码学报Vol.2,No.6,Dec.2015weusethedynamickeyguessingtechniqueproposedbyWangcombinedwithbitpropertytoexactlytheexactbitdifferencecondition,andthetimecomplexitycanbereducedandpreviousresultsofimpossibledifferentialattacksonSIOMNareimoroved.Keywords:RSA;exposedleastsignificantbits;Coppersmith’smethod;lattice;LLLalgorithm1引言不可能差分分析是差分分析的一种特殊形式,它是一种十分有效地分析方法,被广泛运用到分组密码的分析中,如AES[1,2]、CLEFIA[3]等.其昀初由Biham[4,5]和Knudsen[6]独立提出,核心思想是,探索分组密码的特定输入差分和输出差分的不兼容性,用中间相错法连接概率为1的两条差分路径,在中间得到矛盾,找到一些概率为零的差分路线.凡是导致这些差分路线的密钥,都为错误密钥,从而可以排除错误密钥,得到正确密钥.寻找不可能差分的自动化搜索方法有很多,如矩阵方法[7],自动化搜索方法[8]等.SIMON[9]是美国国家安全局(NSA)于2013年提出的一族分组密码算法.其设计思路是使之在硬件和软件方面都有较高的效能[10].SIMON算法采用的是Feistel结构,根据不同的分组长度和密钥长度给出了10个版本.SIMON自诞生之日起,已经吸引了很多密码分析者的目光,关于SIMON的分析有很多,如差分分析[11–14],线性分析[15–17],不可能差分和零相关线性hull分析[15,18]等.2013年,Alkhzaimi和Lauridsen[17]等人提出了SIMON32、SIMON48、SIMON64、SIMON96和SIMON128的16轮、18轮、24轮、29轮和40轮的差分分析,同时也提出了14轮、15轮、16轮、19轮和22轮的不可能差分分析.Alizadeh等人[19]提出了线性分析,攻击了12、15、19、28和35轮.随后,该作者又改进了此结果,提出了13、15、19、28和35轮的线性分析[15].并用不可能差分分析了14轮SIMON32/64和22轮SIMON128/256.Abed等人[12]用线性、差分、不可能差分等分析了SIMON算法,2014年在文献[20]中改进了结果,五种分组长度的不可能差分攻击轮数分别是13轮、15轮、17轮、20轮和25轮.差分分析为18轮、19轮、26轮、35轮和46轮.线性分析为11轮、14轮、16轮、20轮和23轮.2014年Biryukov等人[13]使用差分分析攻击了19轮的SIMON32/64、20轮的SIMON48和26轮的SIMON64.Wang等人提出了对SIMON的积分攻击、线性攻击和不可能差分攻击[18],其中使用不可能差分分析攻击了18轮的SIMON32和19轮的SIMON48,零相关线性攻击是20轮SIMON32和21轮SIMON48,积分攻击为21轮SIMON32.Wang等人[10]对SIMON进行了差分分析,攻击了21轮的SIMON32/64、23轮的SIMON48/72、24轮的SIMON48/96、28轮的SIMON64/96、29轮的SIMON64/128、49轮的SIMON128/128和SIMON128/192、50轮的SIMON128/256.Boura等人[3]给出了SIMON所有版本的不可能差分攻击.2015年,Chen等人[21]给出了SIMON的线性核分析,攻击了23轮Simon32/64、24轮Simon48/72、25轮Simon48/96、30轮Simon64/96、31轮Simon64/128、37轮Simon96/96、38轮Simon96/144、49轮Simon128/128、51轮Simon128/192和53轮Simon128/256,这是目前针对SIMON算法昀好的攻击结果.本文的贡献是,结合自动化搜索方法[8]和中间相错技术及SIMON算法中比特与运算的差分特性,搜索出了SIMON算法昀长的不可能差分路径,并在此基础上进行了不可能差分攻击.在数据收集过程中,我们利用明文和第一轮输出的差分与密钥无关的特点,建立明文和第一轮输出的比特方程组,通过解方程构造满足部分差分条件的明密文对,极大地优化了数据收集过程的计算复杂度.在密钥恢复过程中,利用比特与运算的差分性质,提前过滤掉不满足差分条件的对.并且利用文献[10]中提出的动态密钥猜测技术,给出了比特差分条件的精确计算,减小了所要猜测的密钥空间,从而降低攻击的复杂度,改进了之前的不可能差分结果.本文的结构安排如下:第2节简要地描述了SIMON算法和使用的符号标记.第3节给出不可能差分分析中使用到的与运算的比特差分性质.第4节给出SIMON32的19轮不可能差分分析的详细过程.第5节对比了之前不可能差分的攻击结果,得出结论.陈展等:SIMON算法的不可能差分分析5072SIMON算法描述SIMON分组密码算法采用Feistel结构,分组长度为2n,16,24,32,48,64n,密钥长度为mn,2,3,4m,通常记作SIMON2nmn.SIMON的所有10个版本和对应的轮数见表1.表1SIMON的10个版本Table1The10versionsofSIMON分组长度(2n)密钥长度(mn)轮数分组长度(2n)密钥长度(mn)轮数32643296961445254487296363612812819225668697264961284244我们列出如下一些记法:,,21,0,,1iXnnn:第1i轮的输入,,21iLnn:第1i轮的输入的左半部分,,1iRnn:第1i轮的输入的右半部分,,1iknn:第1i轮的子密钥iX:两个输入iX和iX的差分Xr:X左循环移位r比特:比特异或运算:比特与运算%:模运算SIMON的轮函数为:182,Fxxxx明文记做00,,LR经过第1i轮,,iiLR被如下替换为11,iiLR:1,iiiiLFLRk1,iiRL昀后一轮的输出,rrNNLR即为密文.SIMON的密钥生成算法生成rN个子密钥01,,.rNkk具体过程根据m的值有所不同.前m个子