基于混合整数线性规划的MORUS初始化阶段的差分分析.pdf
《基于混合整数线性规划的MORUS初始化阶段的差分分析.pdf》由会员分享,可在线阅读,更多相关《基于混合整数线性规划的MORUS初始化阶段的差分分析.pdf(9页珍藏版)》请在咨信网上搜索。
1、基于混合整数线性规划的MORUS初始化阶段的差分分析刘 帅*关 杰 胡 斌 马宿东(战略支援部队信息工程大学 郑州 450001)IV摘 要:认证加密算法 MORUS是凯撒(CAESAR)竞赛的优胜算法,抗差分分析性能是衡量认证加密算法安全性的重要指标之一。该文研究了MORUS算法初始化阶段的差分性质,首先给出了一个差分推导规则,可以快速获得一条概率较大的差分链。在此基础上利用混合整数线性规划(MILP)自动搜索技术求解更优的差分链。为了提高搜索速度,结合MORUS初始化阶段的结构特点给出了分而治之策略。根据的重量、取值将MILP模型划分为多个子模型并证明了部分子模型的等价性,大大缩减了模型的
2、求解时间,得到了MORUS初始化阶段16步状态更新的最优差分链。最后给出了简化版MORUS的差分-区分攻击,该文的结果较之前的工作有较大的提升。关键词:认证加密算法;MORUS;混合整数线性规划自动搜索;差分分析中图分类号:TN918.1文献标识码:A文章编号:1009-5896(2023)07-2537-09DOI:10.11999/JEIT220735Differential Analysis of the Initialization of MORUS Based onMixed-Integer Linear ProgrammingLIU Shuai GUAN Jie HU Bin MA
3、 Sudong(SSF PLA Information Engineering University,Zhengzhou 450001,China)IVAbstract:The authenticated encryption algorithm MORUS is one of the finalists of Competition onAuthenticated Encryption:Security,Apllicability,and Robustness(CAESAR).The ability to resist differentialanalysis is one of the i
4、mportant indicators to evaluate the security of authenticated encryption algorithm.Thedifferential property of the initialization of MORUS is researched in this paper.Firstly,a differential deductionrule is proposed to give fast a differential characteristic with a relatively high probability.Based
5、on this,abetter differential characteristic is given by using Mixed-Integer Linear Programming(MILP).To improve theefficiency of solving the MILP model,a Divide-and-Conquer approach is showed.According to the weight andvalue of,the MILP model is divided to many sub-models.The most sub-models are pro
6、ved to beequivalent,and this reduces dramatically the time to solve the model.The best differential characteristics aregiven with 1 to 6 state update functions in the initialization of MORUS.Finally,the differential-distinguishattack on the simplified versions of MORUS is showed.This paper improves
7、the result of the previous relatedwork.Key words:Authenticated encryption algorithm;MORUS;Mixed-Integer Linear Programming(MILP)automatic search;Differential analysis 1 引言EDKNAMCT认证加密算法广泛应用于各类安全系统中1,是一类兼具消息认证与数据加密功能的密码算法。认证加密算法一般包括加密算法 与解密算法。加密算法输入密钥、Nonce、相关数据、明文,输出密文、认证码(C,T)=E(K,N,A,M)(1)DKNACTM解
8、密算法输入密钥、Nonce、相关数据、密文、认证码,认证通过时输出明文,否则输出D(K,N,A,C,T)M,(2)2014年,国际密码研究协会发起凯撒(Com-petition on Authenticated Encryption:Security,Apllicability,and Robustness,CAESAR)竞赛2,面向全球密码工作者征集认证加密算法,最终于2018年公布了7个优胜算法,包括MORUS,ACORN,AEGIS,Ascon,COLM,Deoxys,OCB。收稿日期:2022-06-06;改回日期:2022-08-03;网络出版:2022-08-08*通信作者:刘帅基
9、金项目:国家自然科学基金(61802437,62102448)Foundation Items:The National Natural Science Foundation ofChina(61802437,62102448)第45卷第7期电 子 与 信 息 学 报Vol.45No.72023年7月Journal of Electronics&Information TechnologyJul.20232018年,美国国家标准与技术研究院(National In-stitute of Standards and Technology,NIST)发起征集兼具认证与加密功能的轻量级密码算法的进程
10、3,并于2021年公布了10个优胜算法。随着各种新型认证加密算法的提出,其安全性研究成为当前的热点问题47。以往的安全分析往往依赖手工推导,1994年,Matsui8提出了分支定界搜索算法来搜索最优差分链,这是一种强有力的分析工具,拉开了自动化分析密码算法安全性的序幕912。2014年,Sun等人13建立混合整数线性规划(Mixed-Integer Linear Pro-gramming,MILP)模型刻画密码算法的差分性质,并利用Gurobi求解器求解MILP模型,以此来搜索最优差分链。为了提高MILP模型的求解速度,Zhou等人14针对沙盒置换网络(Sbox PermutationNet,
11、SPN)结构的分组密码算法提出了分而治之策略,有效地提高了差分线性链的搜索效率。作为CAESAR竞赛的优胜算法之一,认证加密算法MORUS由Wu等人15设计提出,遵循了流密码算法的设计思路,根据参数设置分为3个版本MORUS-640-128,MORUS-1280-128,MORUS-1280-256。自提出以来,MORUS的安全性分析得到了广泛的研究,张沛等人16从完全性和差分扩散性两个角度对MORUS-640的初始化阶段进行了研究,给出了MORUS初始化阶段的差分推导规则,并对简化版MORUS进行了差分-区分攻击,施泰荣等人17结合中间相遇思想研究了MORUS算法在故障模型中的差分性质。现有
12、工作对MORUS算法的差分分析仍有较大改进空间,本文主要基于MILP自动搜索技术研究了MORUS算法初始化阶段的差分性质。首先给出一个改进的差分推导规则,相较张沛等人16的工作,IV在初始化阶段步数较大时可以找到更好的差分链。进而,给出了刻画MORUS初始化阶段差分性质的MILP模型,当初始化阶段步数较大时,MILP模型无法在有限时间内求解,本文针对MORUS初始化阶段的结构特点给出了分而治之策略,根据的重量及取值,将MILP模型划分为多个子模型,并证明了其中大部分模型具有等价性,不需要对这一部分子模型进行求解,从而得到了初始化阶段16步状态更新的最优差分链。最后,根据得到的差分链给出了MOR
13、US的差分-区分攻击。之前的工作16,17只分析了MORUS-640的差分性质,本文对MORUS的所有版本均给出了差分分析结果,且较之前的结果有较大提升。2 认证加密算法MORUSMORUS算法15包括3种参数设置:MORUS-640-128,MORUS-1280-128,MORUS-1280-256,表1给出了MORUS的具体参数设置。下文用MORUS-640指代MORUS-640-128,用MORUS-1280指代MORUS-1280-128与MORUS-1280-256。在具体介绍MORUS算法之前,先给出符号说明如表2所示。x bit(x=128,256)X=X1|X2|X3|X4Xi
14、y bit(y=32,64)Rot_x_y(X,b)=(X1 b)|(X2 b)|(X3 b)|(X4 b)对于块,其中是字,。表 1 MORUS的参数设置(bit)参数MORUS-640-128 MORUS-1280-128 MORUS-1280-256密钥长度128128256IV长度128128128状态大小64012801280认证码长度128128128表 2 符号说明符号说明逐比特异或;&逐比特与;循环左移;0ll bit 0;1ll bit 1;const000|01|01|02|03|05|08|0d|15|22|37|59|90|e9|79|62;const1db|3d|18
15、|55|6d|c2|2f|f1|20|11|31|42|73|b5|28|dd;Sii第 步输入状态;Si,jij第 步第 轮输入状态;Si,jkSi,jk第 个bit块,对于MORUS-640,每个状态包含5个128 bit块,对于MORUS-1280,每个状态包含5个256 bit块;Si,jk,lSi,jkl的第 bit。2538电 子 与 信 息 学 报第 45 卷Si+1=StateUpdate(Si,mi)MORUS的状态更新函数为,状态更新函数包括5轮子函数,图1给出了其具体结构。bi,wi(i=0,1,2,3,4)表3给出了状态更新函数中的取值。n=128,256完整的MORU
16、S加密算法包括4个阶段:初始化阶段、相关数据处理阶段、明文处理阶段、认证码生成阶段,下面给出MORUS-5n算法的具体描述:KIVS0(1)初始化阶段。装填密钥与得到初始状态,对于MORUS-640,令S0,00=IV,S0,01=K,S0,02=1128,S0,03=const0,S0,04=const1(3)KIV完成与的装填后,初始化状态经过16步状态更新函数Si+1=StateUpdate(Si,0),i=0,1,.,15(4)最后进行密钥加S16,01=S16,01 K(5)ADunAD AD0|AD1|.|ADu1(2)相关数据处理阶段。相关数据被分割成个 bit块,并参与接下来的
17、状态更新S17+i=StateUpdate(S16+i,ADi),i=0,1,.,u 1(6)PvnP P0|P1|.|Pv1i=0,1,.,v 1(3)明文处理阶段。明文 被分割成 个 bit块,进行加密与状态更新:对于 Ci=Pi S16+u+i,0(S16+u+i,1 w2)(S16+u+i,2&S16+u+i,3)(7)S17+u+i=StateUpdate(S16+u+i,Pi)(8)L1L2|AD|P|tmp=L1|L2|0n128S16+u+v,4=S16+u+v,4 S16+u+v,0(4)认证码生成阶段。令,分别为相关数据长度与明文长度的64 bit二进制表示,令,继续进行状
18、态更新S17+u+v+i=StateUpdate(S16+u+v+i,tmp),i=0,1,.,9(9)产生认证码T=S26+u+v,0(S26+u+v,1 w2)(S26+u+v,2&S26+u+v,3)(10)3 MORUS的差分推导规则y=x1&x2x1x2本节针对MORUS算法初始化阶段给出差分推导规则,意在寻找概率较高的差分链。MORUS算法中唯一的非线性操作是逐比特与运算,对于与运算,假设输入变量差分为,,则输出差为y=(x1&x2)(x1 x1)&(x2 x2)=x1x2 x2x1 x1x2(11)表 3 循环常数MORUS-640MORUS-1280MORUS-640MORUS
19、-1280b0513w03264b13146w164128b2738w296192b3227w364128b4134w43264 图 1 MORUS的状态更新函数第7期刘 帅等:基于混合整数线性规划的MORUS初始化阶段的差分分析2539根据输入差分的不同,划分为以下4种情况:x1=0 x2=0y=0(1),,则;x1=0 x2=1y=x1(2),,则;x1=1 x2=0y=x2(3),,则;x1=1 x2=1y=x1 x2 1(4),,则。yyy1/21/2从情况(2)情况(4)中可以看到的取值是与输入变量的值有关的,当输入变量的值已知时,的值以概率1确定,当输入变量的值未知时,以概率取0,
20、以概率取1(事实上,MORUS初始化阶段仅第1步中的部分内部状态是已知的)。据此,本文将以上情况分为两类:yA:以概率1取定值;y1/21/2B:以概率取0,以概率取1。Si,jkSi,jk|Si,jk|对于MORUS状态更新函数中的任意内部状态差分,本文称中bit 1的数量为该内部状态差分的重量,记为。直观地,在差分推导过程中,为了提高差分链的概率,希望内部状态差分的重量尽可能小。为了方便描述本文暂时忽略所有移位操作,这对分析不会产生任何实质影响。iYi,0l=Si,00,l Si,01,l&Si,02,l Si,03,lYi,0lYi,0lYi,0l Si,22,l Si,23,l&Si,
21、24,lYi,0l&Si,34,lYi,0l&Si,41,lSi,22,l=1Si,23,l=Si,24,l=0Yi,0l=1Si,32,lSi,34,l=0Si,41,l=0Yi,0l=1Si,34,l=Si,41,l=1Yi,0l=1Si,22,l=Si,34,l=Si,41,l=1Si,23,l=Si,24,l=0Yi,0l=1首先看第 步状态更新函数中第1轮的与门,为了研究其输出差分的取值将会产生的影响,观察直接参与的所有运算:1个异或,2个与门,。如果,,令可以降低的重量,这个非0差分产生了“好的影响”。当或者时,使得上面两个与门变成了活跃的,但当时,这两个与门必然是活跃的,则对这两
22、个与门的活跃性不会产生实质性影响。综上当,时,将会产生“好的影响”,由此给出了如下差分推导规则:Yi,0l(1)当与门属于A类情况时,可以唯一确定;Si,22,l=Si,34,l=Si,41,l=1Si,23,l=Si,24,l=0Yi,0l=1Yi,0l=0(2)当与门属于B类情况时,如果满足条件:且,则令,否则令。i对于第 步状态更新函数中其他轮的与门同样如此,由此得到了状态更新函数完整的差分推导规则。本文需要确定初始状态的差分便可以进行差分S0,02S0,03S0,04S0,01S0,00IVIVIVIVS0,00S0,30,l&S0,34,lS0,30,l=S0,00,lS0,34,l
23、S0,30,l=S0,00,l=1S0,34,l=1(S0,30,l&S0,34,l)=1S0,34,l=0(S0,30,l&S0,34,l)=0S0,00S0,00(l)(l 0,1,.,127)l推导,MORUS的初始化阶段的初始状态中,是已知常数,差分固定为0,是密钥,在实际攻击中无法控制但可以进行多次加密,差分同样固定为0。只与有关,由于是已知的,可以选择的值,根据经验的重量为1时,更有可能得到好的差分链,此时的值有128种可能。来看第1步状态更新函数第4轮的与门,其中,的值是已知的,当时,如果,,产生了一个非0差分,如果,,这表明了中1的位置对差分传递是有影响的,据此给出了的候选集合
24、。令表示一个128 bit块,其第 bit为1,其余bit为0。S0,00对于MORUS-640,的候选集合为(l)|l 0,1,.,127:S0,34,l=0(12)S0,00对于MORUS-1280,的候选集合为(l)|0128|l 0,1,.,127:S0,34,l=0(13)加入移位操作,上面的分析仍然可行,在实际攻击中,把所有操作都考虑在内。表3给出了利用该差分推导规则得到的较高的差分转移概率。222823012455本文将表4与现有最好的结果进行对比,文献16中给出了MORUS-640状态更新步数为5,6,7时的差分转移概率分别为,,当步数为5,7时,找到了概率更高的差分链,步数为
25、6时,差分转移概率相同。另外,文献16中并未给出MORUS-1280的结果。4 MORUS的MILP差分分析第3节的差分推导规则只能保证找到的差分链中活跃与门数量尽可能少,采用的是局部最优的思想。本节给出了MORUS的MILP差分自动搜索方法,以第3节的结果为基础,利用分而治之思想,搜索全局最优的差分链。MORUS的状态更新函数包括5轮子函数,本节将状态更新以轮为单位,例如,进行16轮状态更新就是进行3.2步状态更新函数。S0,0=(S0,00,S0,01,S0,02,S0,03,S0,04)根据MORUS算法初始化阶段的初始状态装填,可以得到初始状态差分如表5所示。对于初始化阶段的前4轮状态
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 混合 整数 线性规划 MORUS 初始化 阶段 分析
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。