对基于深度学习的密钥恢复攻击的分析与改进_陈怡.pdf
《对基于深度学习的密钥恢复攻击的分析与改进_陈怡.pdf》由会员分享,可在线阅读,更多相关《对基于深度学习的密钥恢复攻击的分析与改进_陈怡.pdf(13页珍藏版)》请在咨信网上搜索。
1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):168180密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618对基于深度学习的密钥恢复攻击的分析与改进*陈 怡1,申焱天1,于红波1,21.清华大学 计算机科学与技术系,北京 1000842.中关村实验室,北京 100084通信作者:于红波,E-mail:摘要:在 2019 年美密会议上,Gohr 提出了第一个基于深度学习的密钥恢复攻击,并应用于 11 轮、12轮 Speck32/64.本文从时间复杂
2、度的角度对该攻击进行分析和改进.发现 Gohr 所提攻击的运行时间主要受解密、访问神经区分器、通过贝叶斯优化推荐密钥等三个操作的影响,后两个操作几乎占据了全部运行时间;Gohr 采用的强化学习机制导致错误密文结构占据了过多计算资源.提出了以下改进:(1)攻击只采用在部分密文比特上建立的神经区分器,并用查找表代替神经区分器,使得攻击运行时可以完全摆脱对神经网络的依赖.(2)放弃强化学习机制,使用新的“Guess-and-Filter”策略.通过贝叶斯优化推荐部分密钥的思想和“Guess-and-Filter”策略有冲突,所以也放弃使用贝叶斯优化.基于上述改进,提出了新的密钥恢复攻击,使得时间复杂
3、度显著降低.为了验证新的密钥恢复攻击在时间复杂度上的优势,在 11 轮、12 轮 Speck32/64 上进行了实际密钥恢复攻击,时间复杂度分别为 226.68和 232.25.与已有的最优攻击相比,复杂度分别减少为原来的 1/211.32和 1/211.1.此前没有研究从运行时间角度分析对基于深度学习的密钥恢复攻击,本文工作有助于推动基于深度学习的密码分析的研究.关键词:深度学习;密钥恢复攻击;Speck32/64中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000587中文引用格式:陈怡,申焱天,于红波.对基于深度学习的密钥恢复攻击的分析与改进J.密码学报
4、,2023,10(1):168180.DOI:10.13868/ki.jcr.000587英文引用格式:CHEN Y,SHEN Y T,YU H B.Analysis and improvements of deep learning-based keyrecovery attackJ.Journal of Cryptologic Research,2023,10(1):168180.DOI:10.13868/ki.jcr.000587Analysis and Improvements of Deep Learning-based Key RecoveryAttackCHEN Yi1,SHEN
5、 Yan-Tian1,YU Hong-Bo1,21.Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China2.Zhongguancun Laboratory,Beijing 100084,ChinaCorresponding author:YU Hong-Bo,E-mail:Abstract:At CRYPTO 2019,Gohr proposed the first deep learning-based key recovery attackand applied to 1
6、1,12 rounds of Speck32/64 respectively.This paper presents some analysis on theattack and proposes some improvements.First,it is found that the runtime of the attack is mainlyaffected by three operations:decryption,accessing neural distinguishers and recommending key guess*基金项目:国家重点研发计划(2018YFB08034
7、05,2017YFA0303903)Foundation:National Key Research and Development Program of China(2018YFB0803405,2017YFA0303903)收稿日期:2022-01-24定稿日期:2022-03-24陈怡 等:对基于深度学习的密钥恢复攻击的分析与改进169via Bayesian optimization.The last two operations consume almost all the runtime.Moreover,thereinforcement learning mechanism ad
8、opted by Gohr makes wrong ciphertext structures which wastesmuch computation resource.In order to reduce the time complexity,this paper proposes the followingimprovements:(1)the attack only adopts neural distinguishers that are built on few ciphertext bits,andthese neural distinguishers are replaced
9、 with lookup tables during the attack;(2)the reinforcementlearning mechanism is discarded,and a new Guess-and-Filter strategy is proposed.The Bayesianoptimization is also not adopted because it is not necessary for the new strategy.Based on theseimprovements,new deep learning-based key recovery atta
10、cks on 11/12 round Speck32/64 are proposed.The time complexities for the proposed attacks are 226.68and 232.25respectively.Compared with thetime complexity of the best-known attacks,the time complexity of the improved attacks is reduced bya factor of 211.32/211.1.Key words:deep learning;key recovery
11、 attack;Speck32/641引言深度学习在计算机视觉1、自然语言处理2等领域已经展示了其优越性.从上个世纪开始,研究者们也在探索深度学习与密码学的结合3.如今,在侧信道分析46中,深度学习已经成为了一个强大的工具.在 2019 年美密会议上,Gohr7针对 Speck32/64 提出了基于残差神经网络8的神经区分器.结合贝叶斯优化,Gohr 进一步提出了基于深度学习的密钥恢复攻击,并成功应用于 11 轮、12 轮 Speck32/64.和传统的密码分析方法对比,除了解密外,这个新攻击包含两个额外操作.第一个操作是把解密的密文对送入神经区分器,获得神经区分器的输出.第二个操作是依赖贝叶
12、斯优化在每一次迭代时推荐一批最有可能是正确密钥的密钥猜测进行验证.此外,Gohr 采用了强化学习机制以便于动态地分配计算资源.攻击时,一次生成一批密文结构用于多次迭代.每一次迭代时,挑选一个最有可能是正确密文结构的密文结构用于验证密钥猜测.一旦达到最大迭代次数,就生成一批新密文结构,重新迭代.不难发现,Gohr 提出的基于深度学习的密钥恢复攻击和经典密码分析方法有很大不同,其时间复杂度也受更多因素影响.基于深度学习的密钥恢复攻击研究近几年取得了一定的发展.首先,Chen 等人发现 Gohr 提出的密钥恢复攻击严重依赖于实际实验,无法用于理论分析.为了解决这个问题,Chen 等人提出了一种神经辅
13、助统计攻击9.并且,在部分密文比特上建立神经区分器的思想首次被引入,用于缩减密钥空间以便降低攻击复杂度.不过,该思想的潜力没有得到充分挖掘,神经辅助统计攻击仍然使用了在完整密文对上建立的神经区分器.其次,Gohr 的密钥恢复攻击可以通过使用前置差分来延长神经区分器,但是要求前置差分中必须存在足够多的中性比特.Bao 等人对中性比特的概念进行扩展,以便于寻找更多的中性比特,这也进一步提升了 Gohr 的密钥恢复攻击的潜力10.2021 年,Benamira 等人在欧密上发表了对神经区分器内在机理的研究,有助于研究者们了解神经区分器捕捉到的与 Speck32/64 的相关知识11.此外,还有一些学
14、者基于提高神经区分器准确率的目标,提出了一系列的改进.这些改进方式包括使用更多的密文对作为输入12、使用更加复杂强大的神经网络10,13.经过调研,我们发现目前还没有研究者专门尝试对 Gohr 提出的密钥恢复攻击进行时间复杂度优化.但是,正如前文所说,Gohr 提出的密钥恢复攻击的时间复杂度受到更多因素影响.对这一攻击的时间复杂度优化有助于进一步了解和挖掘深度学习的潜力,所以本文的目标是优化基于深度学习的密钥恢复攻击的时间复杂度.首先,基于对 11 轮 Speck32/64 的密钥恢复攻击的分析,我们有如下发现:三个核心操作的时间消耗差异巨大.解密的时间大约只占总时间的1.31000,贝叶斯优
15、化推荐密钥的时间大约占总时间的11.55100,访问神经区分器的时间则大约占总时间的88.32100.错误的密文结构占据了大约96.59100的运行时间.基于上述发现,我们提出了如下改进:(1)使用在部分密文比特上建立神经区分器的思想,并充分挖掘这一思想的潜力.具体来说,我们只170Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023采用在部分密文比特上建立的神经区分器,并且要求每个神经区分器的输入空间足够小,然后用查找表存储神经区分器的输入和输出.最后在攻击的时候,访问查找表而不是神经区分器.这一改进极大地减少了获得神经区分器输出
16、的时间消耗.(2)提出了一种新的“Guess-and-Filter”策略,放弃使用强化学习机制.我们发现强化学习机制会导致错误密文结构占据绝大部分运行时间,而“Guess-and-Filter”策略可以及时过滤错误密文结构.这一改进有效地减少了错误密文结构占用的运行时间比例.基于上述改进,本文针对 11 轮、12 轮 Speck32/64 提出了新的基于深度学习的密钥恢复攻击.在新的攻击中,“Guess-and-Filter”策略要求遍历整个密钥空间来判断当前处理的密文结构是否是错误的.所以,通过贝叶斯优化只推荐部分密钥用于测试的思想和新策略不兼容.同时,为了验证改进的积极作用,也需要排除贝叶
17、斯优化的影响.基于以上考虑,新的密钥恢复攻击没有使用贝叶斯优化.表1总结了本文攻击和已知攻击的复杂度对比.当前针对 Speck32/64 的最佳攻击是差分攻击,可以攻击 14 轮.但是对于 11 轮、12 轮 Speck32/64,最优攻击是基于深度学习的密钥恢复攻击.从表1中可知,我们成功地降低了基于深度学习的密钥恢复攻击的复杂度.表 1 密钥恢复攻击总结Table 1Key recovery attack summary轮数时间数据存储成功率弱密钥设定来源112462142221No14238213.6218.950.52No7228215.7227.60.75No本文226.68217.
18、7227.60.99No本文122512192221No14243.4222.97224.990.4No7244.89222.00218.950.86No10243.35218.58222.580.81263弱密钥10232.25220.97227.60.74263弱密钥本文文章接下来的结构:第2节介绍预备知识和相关工作,第3节介绍对基于深度学习的密钥恢复攻击的分析,第4节介绍改进的具体细节,第5节介绍改进的攻击,第6节会在相同的攻击设定下比较和分析不同的密钥恢复攻击,第7节总结和讨论.实验代码已经开源,可从 https:/ CPU 1.6 GHz,8 GB 内存.2.2基本符号异或模加&与循
19、环右移循环左移a b比特串 a 和 b 连接bi比特串 b 的第 i 个比特.下标 0 在最右边i1 i2从 i1到 i2的所有数字陈怡 等:对基于深度学习的密钥恢复攻击的分析与改进1712.3Speck32/642013 年,美国国家安全局(NSA)提出了轻量级的 ARX 分组密码系列 Speck15.Speck32/64 是其中一个版本,分组大小是 32 比特,密钥是 64 比特,一共包含 22 轮加密.对于 Speck32/64,用 li ri表示第 i 轮的状态,其中 li,ri分别是左半部分的 16 比特、右半部分的16 比特.运行 Speck32/64 之前,用明文 P 初始化 l
20、0 r0.Speck32/64 的轮函数是li+1=(li 7)ri)ski,ri+1=(ri 2)li+1,(1)其中 ski代表第 i 轮的轮密钥.对于 h 轮的 Speck32/64,输出的密文 C 是 lh rh.2.4差分分析差分分析16研究的是加密过程中差分的传播特性.考虑一个加密算法 f:Fm2 Fm2.用 P,分别表示明文、明文差分、密文差分.差分分析关注的是差分的传播概率:Pr()=P|f(P)f(P )=2m.(2)如果该概率大于 2m,攻击者可以用差分 攻击这个密码.2.5中性比特考虑一个加密函数 f:Fm2 Fm2和一个差分 .Biham 等人发现明文一些比特的值不影响
21、差分传播.具体来说,对于任何符合上述差分的明文对(P,P ),如果同时翻转 P 和 P 的第 i 比特,并且得到的密文对差分仍然是,那么比特 i 就是一个中性比特17.Bao10等人提出了一个新的概念:simultaneous-neutral bit-sets(SNBS).给定一个包含 d 比特的比特集合 i1,i2,id,对于任意符合上述差分的明文对(P,P ),如果同时翻转 P 和 P 的 d个比特,得到的密文差分仍然是,那么 i1,i2,id 就是一个 SNBS.本文接下来把中性比特、SNBS 统称为中性比特.如果一个明文对符合给定的一个差分,我们就可以用该明文对和 k 个中性比特生成
22、2k个符合给定差分的明文对.2.6Gohr 的 2019 年美密工作回顾本小节简要回顾 Gohr 在 2019 年美密会议上提出的神经区分器和密钥恢复攻击7.2.6.1神经区分器为了建立一个针对 h 轮 Speck32/64 的神经区分器 ND,需要生成一个训练集和一个测试集.训练集、测试集的生成方式相同:(1)选择一个明文差分;(2)使用一个随机数生成器生成均匀分布的 M 个明文对(Pi,0,Pi,1=Pi,0)和一个标签数组 Yi,i 1,M.如果 Yi=0,我们就重新生成一个随机明文代替 Pi,1.(3)所有的明文对加密 h 轮,得到密文对.这样一来,我们就生成了一个包含 M 个密文对和
23、标签的数据集.下一步是在训练集上训练一个设计好的神经网络.网络的输入是密文对,输出是一个 0 到 1 之间的分数 Z.如果 Z 0.5,代表输入的密文对的标签是 1,否则就是 0.最后一步是在测试集上测试神经网络的准确率.如果测试集上的准确率超过 0.5,该神经网络就是一个有效的神经区分器 ND.本文中,我们用 NDh表示针对 h 轮 Speck32/64 的神经区分器.令 =0 x0040/0 x0000,Gohr 训练了针对 5 8 轮 Speck32/64 的神经区分器.基于 ND6和 ND7,Gohr 提出了对 11 轮 Speck32/64 的密钥恢复攻击.2.6.2基于深度学习的密
24、钥恢复攻击为了攻击 11 轮 Speck32/64,Gohr 在 ND7前面接了一个通过概率为 26的 2 轮差分(0 x211,0 xa04)(0 x40,0 x0).由于 Speck 在第一个模加运算前没有白化密钥,所以可以再往上免费扩一轮,具体操作是把 0 当作轮密钥解密一轮,由此便得到了一个 10 轮的区分器.172Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023基于这个 10 轮区分器,对 11 轮 Speck32/64 的密钥恢复攻击如下:(1)随机生成一个伪明文对(P0,P1=P0),其中 =(0 x0211,0
25、x0a04).(2)用 k 个中性比特基于上述伪明文对生成一个伪明文结构,并用 0 作为轮密钥解密一轮.之后再加密 11 轮,收集生成的密文结构.(3)对第 11 轮轮密钥的每一个候选者 kg11:(a)用 kg11对密文结构解密一轮,解密后的伪密文对送入 ND7,收集输出分数 Zi,i 1,2k.(b)使用以下公式计算 kg11的排名分数:v=2ki=1log2(Zi1 Zi).(3)(c)如果 v 超过一个阈值 c1,遍历第 10 轮轮密钥的所有候选者 kg10:i.用 kg10对上述解密后的伪密文结构继续解密一轮,解密的伪密文对送入 ND6,收集神经区分器输出,并用公式(3)计算 kg1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 深度 学习 密钥 恢复 攻击 分析 改进 陈怡
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。