结合EDCA和CPA的容错双向选择攻击.pdf
《结合EDCA和CPA的容错双向选择攻击.pdf》由会员分享,可在线阅读,更多相关《结合EDCA和CPA的容错双向选择攻击.pdf(12页珍藏版)》请在咨信网上搜索。
1、计算机科学与探索Journal of Frontiers of Computer Science and Technology1673-9418/2023/17(09)-2229-12doi:10.3778/j.issn.1673-9418.2206108结合EDCA和CPA的容错双向选择攻击张美玲1,2,尚利蓉1,2+,郑东1,21.西安邮电大学 网络空间安全学院,西安 7101212.西安邮电大学 陕西省无线网络安全技术国家工程实验室,西安 710121+通信作者 E-mail:摘要:当所设计的攻击方案带有容错功能时,往往需要在非常大的候选空间中挑出正确的密钥。如何有效地实现这个目标是侧信
2、道攻击中非常重要且具有挑战性的问题。针对这一问题,以AES-128为目标研究了结合欧式距离增强碰撞攻击(EDCA)和相关能量分析攻击(CPA)的容错双向选择攻击。为了提高碰撞检测的成功率,提出了EDCA,与传统的相关增强碰撞攻击(CCA)相比,EDCA利用欧式距离来区分两组能量迹之间的相似性,其碰撞检测的成功率更高,从而使优化更加实用和有意义。除此之外,结合EDCA和CPA,将密钥以及对应的碰撞对做分组处理,然后进行双向筛选,得到最优的碰撞链,大大减少了候选空间,从而降低了密钥枚举的复杂性,有效地恢复密钥。实验结果表明,在低信噪比SNR=-3 dB和SNR=-6 dB的条件下,设置碰撞对的阈值
3、Th=5,所提出的方案在3 000条能量迹时成功率达到98.78%和80.25%,均优于现有方案。关键词:AES-128;碰撞攻击;欧式距离增强碰撞攻击(EDCA);相关能量分析攻击(CPA);双向选择文献标志码:A中图分类号:TP309.7Fault-Tolerant Bidirectional Choice Attack Combining EDCA and CPAZHANG Meiling1,2,SHANG Lirong1,2+,ZHENG Dong1,21.School of Cyberspace Security,Xi an University of Posts and Telec
4、ommunications,Xi an 710121,China2.Shaanxi Province Wireless Network Security Technology National Engineering Laboratory,Xi an University of Postsand Telecommunications,Xi an 710121,ChinaAbstract:When the designed attack scheme is fault-tolerant,it is often necessary to pick out the correct key in av
5、ery large candidate space.How to effectively achieve this goal is a very important and challenging problem in side-channel attacks.Aiming at this problem,a fault-tolerant bidirectional choice attack combining EDCA(Euclideandistance enhanced collision attack)and CPA(correlation power analysis)is stud
6、ied with AES-128 as the target.Firstly,in order to improve the success rate of collision detection,the EDCA is proposed.Compared with correlationenhanced collision attack(CCA),EDCA utilizes the Euclidean distance to distinguish the similarity between twosets of energy traces.Its collision detection
7、has a higher success rate,making the optimization more practical andmeaningful.In addition,combined with EDCA and CPA,the keys and the corresponding collision pairs are grouped,and then bidirectional screening is performed to obtain the optimal collision chain,which greatly reduces thecandidate spac
8、e and reduces the complexity of key enumeration,effectively recovering the key.Experimental resultsshow that,under the conditions of low signal-to-noise ratioSNR=-3 dBandSNR=-6 dB,setting the threshold of基金项目:国家自然科学基金(62072369);陕西省重点研发计划(2021ZDLGY06-04)。This work was supported by the National Natura
9、l Science Foundation of China(62072369),and the Key Research and DevelopmentProgram of Shaanxi Province(2021ZDLGY06-04).收稿日期:2022-06-28修回日期:2022-08-15Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(9)随着物联网、移动互联网的快速发展,密码学已广泛应用于各种硬件设备中,然而,当加密算法在硬件设备上实现时,密钥信息通过操作时间1、功耗2-3、电磁辐射4和光
10、子发射5等侧信道信息泄露,敌手可以收集和利用这些泄露来恢复密钥信息,这些攻击被称为侧信道攻击。侧信道攻击可通过分治攻击和分析攻击来执行,分治攻击如相关能量分析攻击(correlationpower analysis,CPA)6和模板攻击(template attack,TA)7,将整个密钥划分为若干个子密钥,并逐个进行破解,然后,攻击者通过密钥枚举8-10重新组合子密钥的候选。分析攻击如碰撞攻击,通过求解方程组来恢复完整密钥,与分治攻击相比,它利用了更多的泄露信息,但更复杂。碰撞攻击是能量分析攻击的主要研究方向之一,Schramm 等人在 2003 年首次提出了针对 DES(data encr
11、yption standard)算法的碰撞攻击11。后来,类似的想法被应用于破解 AES(advanced encryptionstandard),提出了针对 AES 列变换输入字节的碰撞检测12。2007年,Bogdanov扩展了碰撞的含义,提出了对AES的线性碰撞攻击13,并在文献14中对碰撞攻击进行了一些改进。2018年,Yuan等人15提出了一种基于双距离投票检测的多比特碰撞攻击,并改进了容错机制,提高了攻击效率。2019年,Zheng等人16提出了假设检验法,针对AES密码算法第一轮加密,能够以较高的概率检测出碰撞。Ding等人17提出了随机重用掩码 AES算法的 S盒自适应选择明文
12、碰撞攻击;2021年,郑东等人针对重用掩码,提出了一种改进的基于AES的选择明文碰撞攻击18。为了提高攻击的效率,研究者将碰撞攻击与分治攻击结合,使用碰撞信息来优化分治攻击,这种组合攻击可以划分为模板类和非模板类,常见的模板类攻击是将 CPA 与 CCA(correlation enhanced collisionattack)进行结合19,非模板类攻击是将 TA 与 MDCA(Minkowski distance enhanced collision attack)结合20。模板类攻击的想法由 Bogdanov等人在文献19中首次提出,他们将 CPA 与 CCA 相结合,提出了一个名为测试链
13、(test of chain,TC)的实用方案,试图找到从第一个子密钥顺序关联到最后一个子密钥的长链,并指出这种结合方法的攻击效率要高于独立的CPA 或者 CCA,但在基于 TC 的组合攻击中,一旦测试链上的一条路径出现错误,将导致整条路径错误,最终密钥恢复失败。2014年,Wang等人21提出了另一种名为容错链(fault tolerant chain,FTC)的密钥恢复方案,旨在发现第一个子密钥与其余 15个子密钥之间的碰撞,由于碰撞信息的利用不足,只能通过传统的密钥枚举来恢复,这也使得后期的密钥恢复非常耗时。2019年,Ou等人22提出了组碰撞攻击(group colli-sion at
14、tack,GCA),也是基于 CPA 和 CCA 的组合攻击。GCA将AES-128算法的全密钥空间划分为包含4个子密钥的8个大“组”,并利用尽可能多的碰撞在每个组内构建子链,它从短链连续拼接成长链。与TC 和 FTC 中的 15对碰撞相比,GCA 利用了 32对碰撞。然而,CCA的性能远远低于CPA,其检测出正确碰撞对的概率较低,任何一个碰撞值超出给定的阈值,都可能导致密钥恢复失败,因此,其成功率相对较低。分治攻击与分析攻击结合时会出现以下四种情况:(1)正确的密钥在密钥候选的阈值区间内;(2)正确的密钥超出密钥候选的阈值区间;(3)正确的碰撞对在碰撞对候选的阈值区间内;(4)正确的碰撞对超
15、出碰撞对候选的阈值区间。以上提到的三种攻击方案TC、FTC、GCA和本文方案都是以容错的方式将情况(2)和(4)分别归约到情况(1)和(3),而所谓的容错也就是增大阈值区间,因此剩下的问题就是如何有效地解决情况(1)和(3)。本文研究了结合欧式距离增强碰撞攻击(Eucli-dean distance enhanced collision attack,EDCA)和 CPA的容错双向选择攻击。首先对 CCA做了改进,研究了EDCA,实验结果表明,在不同信噪比的情况下,其检测到正确碰撞对的概率远远高于 CCA,提高了攻击的成功率。除此之外,本文结合 EDCA和 CPA,对密钥以及对应的碰撞对做分组
16、处理,然后进行双向筛选和拼接,最终得到16个密钥字节的完整碰撞链,大大减少了候选空间,使得密钥恢复更容易,提高了攻击的效率。collision pair being 5,the success rate of the proposed scheme reaches 98.78%and 80.25%when there are 3000energy traces,both of which are better than the existing schemes.Key words:AES-128;collision attack;Euclidean distance enhanced coll
17、ision attack(EDCA);correlation power analysis(CPA);bidirectional choice2230张美玲 等:结合EDCA和CPA的容错双向选择攻击1预备知识1.1目标算法AES在本文中,主要针对AES-128算法23进行密钥的恢复,并使用以下符号来表示AES的变量,16个字节的明文和密钥分别表示为P=p1,p2,p16和K=k1,k2,k16,第一轮的 16个 S盒操作记为S1,S2,S16,并将它们的输入表示为xi=piki(1 i 16)。加密N次时,对应的明文和能量迹分别表示为P=P1,P2,PN和T=T1,T2,TN,由于 16个
18、S盒操作是按顺序进行的,一条能量迹可以分成 16 段,第i个 S 盒对应的能量迹段表示为Ti=ti,1,ti,2,ti,l(1 i 16),其中l表示提取到的能量迹的采样点数。在本文的攻击中使用了平均能量迹,记为-T=-T1,-T2,-T16。1.2汉明重量和欧式距离在加密算法中,汉明重量用于计算数据中逻辑值为“1”的比特个数,令数据x的汉明重量表示为Hw(x),x1和x2之间的汉明距离定义为HD(x1,x2),则有HD(x1,x2)=Hw(x1x2)。对采集到的能量迹做对齐处理后,与S盒相关的l个采样点假设基于汉明重量模型7,则能量迹上每个采样点的数学表达式为:t(n)q=sqHw(x(n)
19、i)+q+rq(1 q l)(1)其中,x(n)i表示第n个明文中第i个S盒的输入,sq表示标量系数,q表示消耗常量,rq表示能量迹在采样点q处的噪声,服从正态分布rq N(,2q)。为了检测两个S盒是否发生了碰撞,常使用目标密码算法在执行过程中泄露的侧信道信息来确定两个 S盒对应的能量迹是否有足够的相似性。给定两个S盒相关的能量迹段:Ti=(ti,1,ti,2,ti,l)IRlTj=(tj,1,tj,2,tj,l)IRl(2)让Ti和Tj对应一对未知输入xi和xj的 S 盒执行,若xi=xj,则意味着Ti和Tj有相似的能量消耗,这两条能量迹可以看作l维欧几里德空间IRl中的两个向量,它们之间
20、的相似性可通过最小二乘法(leastsquares method,LSM),即欧式距离24来定义:ED(Ti,Tj)=q=1l(ti,q-tj,q)2(3)其中,ti,q是第i个S盒所对应的能量迹的第q个采样点的采样值,l是能量迹中的采样点个数。令AED(xi,xj)表示当Si和Sj的两个输入值分别为xi和xj时的平均欧氏距离,在实际中,通常使用AED(xi,xj)来逼近ED(Ti,Tj)的数学期望,即:AED(xi,xj)=1Nn=1Nq=1l(t(n)i,q-t(n)j,q)2(4)1.3相关增强碰撞攻击相关增强碰撞攻击(CCA)是 Moradi 等人25在2010年提出的一种重要的碰撞检
21、测技术,该方法比较两个不同S盒对应的两组能量迹之间的相关系数,而不是检测两个单一的能量迹之间的碰撞。以AES-128 算法的第一轮中第一个和第二个 S 盒的碰撞为例:在线阶段,攻击者获得N个随机明文对应的N条能量迹;离线阶段,攻击者根据16个S盒的操作将能量迹划分为16段,并做对齐处理,分别取第一个S盒和第二个S盒对应的能量迹,CCA根据它们的明文字节值将对应的能量迹分为256类,计算每个类的平均功耗向量-Tj(j=1,2),并在猜测的1,2下计算它们之间的相关系数:(1,2)(-T1,-T1,22)|=0,1,255(5)若1,2=k1k2,则相关系数(1,2)达到一个最大值,否则,它的相关
22、系数很低。这种相关增强技术利用相关系数来区分猜测的碰撞值是否正确,可以通过测试几个相关系数最高的候选来增加找到正确碰撞的概率,但是这种方法需要计算每个猜测值1,2下的相关系数,并将相关系数降序排列,最终考虑最高的几个相关系数,因此实现效率较低。2结合EDCA和CPA的容错双向选择攻击本文研究的组合攻击是针对非模板类的,并具备容错功能,即正确的子密钥和碰撞对都在阈值区间内。在低信噪比的条件下,执行CPA后,正确的密钥排名往往比较靠后,设置一个合理的阈值Thk使得正确的密钥在阈值排名内,此时恢复完整密钥需要遍历的次数为Th16k,计算复杂度高,而本章提出的结合EDCA和CPA的容错双向选择攻击可以
23、大大减少候选空间,从而显著降低了密钥枚举的复杂性,有效地恢复密钥。2.1EDCA的基本原理本文 1.3 节提到的相关增强碰撞攻击(CCA)可以检测包含两个字节位置的所有可能碰撞,其主要用到了皮尔逊相关系数来计算两组能量迹之间的相关性,只利用到了能量迹上一个样本点的泄露信息,最大的相关系数对应正确的碰撞值,但其检测出正2231Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(9)确碰撞对的概率较低。因此,为了增加检测出正确碰撞对的概率,并提高碰撞检测的成功率,本文对CCA 做了改进,提出了一种欧氏距离增强
24、碰撞攻击(EDCA)。与CCA不同的是,EDCA利用欧氏距离来区分两组能量迹之间的相似性,利用了能量迹上所有样本点的泄露信息来判断猜测的碰撞值是否正确,具体攻击流程在算法 1中给出,它包括了在线和离线两个阶段(以计算*1,2为例)。算法1 欧氏距离增强碰撞攻击Online Stage:1.P=(P1,P2,PN)RandomPlaintexts()2.T=(T1,T2,TN)AcquireTraces(P)3.Tn1|n=1,2,N,Tn2|n=1,2,NInterceptTraces(T)Offline Stage:1.-Tm1|m=0,1,255AverageTraces(Tn1|n=1,
25、2,N)2.-Tm2|m=0,1,255AverageTraces(Tn2|n=1,2,N)3.for each guess 0,1,255do4.ED AED(-Tp11,-Tp12|p1=0,1,255)5.end6.returnarg minED(-Tp11,-Tp1+2)(1)在线阶段(online stage):攻击者随机选择N个明文P=(P1,P2,PN),每个明文包含 16 个字节(RandomPlaintexts),然后进行能量迹的采集,得到N条能量迹T=(T1,T2,TN)(AcquireTraces)。对能量迹做预处理后,截取前两个S盒对应的能量迹段分别为Tn1|n=1,2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 结合 EDCA CPA 容错 双向选择 攻击
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。