对基于深度学习的密钥恢复攻击的分析与改进_陈怡.pdf

密码学报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.本文从时间复杂度的角度对该攻击进行分析和改进.发现 Gohr 所提攻击的运行时间主要受解密、访问神经区分器、通过贝叶斯优化推荐密钥等三个操作的影响,后两个操作几乎占据了全部运行时间;Gohr 采用的强化学习机制导致错误密文结构占据了过多计算资源.提出了以下改进:(1)攻击只采用在部分密文比特上建立的神经区分器,并用查找表代替神经区分器,使得攻击运行时可以完全摆脱对神经网络的依赖.(2)放弃强化学习机制,使用新的“Guess-and-Filter”策略.通过贝叶斯优化推荐部分密钥的思想和“Guess-and-Filter”策略有冲突,所以也放弃使用贝叶斯优化.基于上述改进,提出了新的密钥恢复攻击,使得时间复杂度显著降低.为了验证新的密钥恢复攻击在时间复杂度上的优势,在 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.密码学报,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 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 11,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*基金项目:国家重点研发计划(2018YFB0803405,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 adopted 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 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 attacks 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 attack;Speck32/641引言深度学习在计算机视觉1、自然语言处理2等领域已经展示了其优越性.从上个世纪开始,研究者们也在探索深度学习与密码学的结合3.如今,在侧信道分析46中,深度学习已经成为了一个强大的工具.在 2019 年美密会议上,Gohr7针对 Speck32/64 提出了基于残差神经网络8的神经区分器.结合贝叶斯优化,Gohr 进一步提出了基于深度学习的密钥恢复攻击,并成功应用于 11 轮、12 轮 Speck32/64.和传统的密码分析方法对比,除了解密外,这个新攻击包含两个额外操作.第一个操作是把解密的密文对送入神经区分器,获得神经区分器的输出.第二个操作是依赖贝叶斯优化在每一次迭代时推荐一批最有可能是正确密钥的密钥猜测进行验证.此外,Gohr 采用了强化学习机制以便于动态地分配计算资源.攻击时,一次生成一批密文结构用于多次迭代.每一次迭代时,挑选一个最有可能是正确密文结构的密文结构用于验证密钥猜测.一旦达到最大迭代次数,就生成一批新密文结构,重新迭代.不难发现,Gohr 提出的基于深度学习的密钥恢复攻击和经典密码分析方法有很大不同,其时间复杂度也受更多因素影响.基于深度学习的密钥恢复攻击研究近几年取得了一定的发展.首先,Chen 等人发现 Gohr 提出的密钥恢复攻击严重依赖于实际实验,无法用于理论分析.为了解决这个问题,Chen 等人提出了一种神经辅助统计攻击9.并且,在部分密文比特上建立神经区分器的思想首次被引入,用于缩减密钥空间以便降低攻击复杂度.不过,该思想的潜力没有得到充分挖掘,神经辅助统计攻击仍然使用了在完整密文对上建立的神经区分器.其次,Gohr 的密钥恢复攻击可以通过使用前置差分来延长神经区分器,但是要求前置差分中必须存在足够多的中性比特.Bao 等人对中性比特的概念进行扩展,以便于寻找更多的中性比特,这也进一步提升了 Gohr 的密钥恢复攻击的潜力10.2021 年,Benamira 等人在欧密上发表了对神经区分器内在机理的研究,有助于研究者们了解神经区分器捕捉到的与 Speck32/64 的相关知识11.此外,还有一些学者基于提高神经区分器准确率的目标,提出了一系列的改进.这些改进方式包括使用更多的密文对作为输入12、使用更加复杂强大的神经网络10,13.经过调研,我们发现目前还没有研究者专门尝试对 Gohr 提出的密钥恢复攻击进行时间复杂度优化.但是,正如前文所说,Gohr 提出的密钥恢复攻击的时间复杂度受到更多因素影响.对这一攻击的时间复杂度优化有助于进一步了解和挖掘深度学习的潜力,所以本文的目标是优化基于深度学习的密钥恢复攻击的时间复杂度.首先,基于对 11 轮 Speck32/64 的密钥恢复攻击的分析,我们有如下发现:三个核心操作的时间消耗差异巨大.解密的时间大约只占总时间的1.31000,贝叶斯优化推荐密钥的时间大约占总时间的11.55100,访问神经区分器的时间则大约占总时间的88.32100.错误的密文结构占据了大约96.59100的运行时间.基于上述发现,我们提出了如下改进:(1)使用在部分密文比特上建立神经区分器的思想,并充分挖掘这一思想的潜力.具体来说,我们只170Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023采用在部分密文比特上建立的神经区分器,并且要求每个神经区分器的输入空间足够小,然后用查找表存储神经区分器的输入和输出.最后在攻击的时候,访问查找表而不是神经区分器.这一改进极大地减少了获得神经区分器输出的时间消耗.(2)提出了一种新的“Guess-and-Filter”策略,放弃使用强化学习机制.我们发现强化学习机制会导致错误密文结构占据绝大部分运行时间,而“Guess-and-Filter”策略可以及时过滤错误密文结构.这一改进有效地减少了错误密文结构占用的运行时间比例.基于上述改进,本文针对 11 轮、12 轮 Speck32/64 提出了新的基于深度学习的密钥恢复攻击.在新的攻击中,“Guess-and-Filter”策略要求遍历整个密钥空间来判断当前处理的密文结构是否是错误的.所以,通过贝叶斯优化只推荐部分密钥用于测试的思想和新策略不兼容.同时,为了验证改进的积极作用,也需要排除贝叶斯优化的影响.基于以上考虑,新的密钥恢复攻击没有使用贝叶斯优化.表1总结了本文攻击和已知攻击的复杂度对比.当前针对 Speck32/64 的最佳攻击是差分攻击,可以攻击 14 轮.但是对于 11 轮、12 轮 Speck32/64,最优攻击是基于深度学习的密钥恢复攻击.从表1中可知,我们成功地降低了基于深度学习的密钥恢复攻击的复杂度.表 1 密钥恢复攻击总结Table 1Key recovery