对基于深度学习的密钥恢复攻击的分析与改进  

Analysis and Improvements of Deep Learning-based Key Recovery Attack

作　　者：陈怡 申焱天 于红波[1,2] CHEN Yi;SHEN Yan-Tian;YU Hong-Bo(Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China;Zhongguancun Laboratory,Beijing 100084,China)

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]中关村实验室,北京100084

出　　处：《密码学报》2023年第1期168-180,共13页Journal of Cryptologic Research

基　　金：国家重点研发计划(2018YFB0803405,2017YFA0303903)。

摘　　要：在2019年美密会议上,Gohr提出了第一个基于深度学习的密钥恢复攻击,并应用于11轮、12轮Speck32/64.本文从时间复杂度的角度对该攻击进行分析和改进.发现Gohr所提攻击的运行时间主要受解密、访问神经区分器、通过贝叶斯优化推荐密钥等三个操作的影响,后两个操作几乎占据了全部运行时间;Gohr采用的强化学习机制导致错误密文结构占据了过多计算资源.提出了以下改进:(1)攻击只采用在部分密文比特上建立的神经区分器,并用查找表代替神经区分器,使得攻击运行时可以完全摆脱对神经网络的依赖.(2)放弃强化学习机制,使用新的“Guess-and-Filter”策略.通过贝叶斯优化推荐部分密钥的思想和“Guess-and-Filter”策略有冲突,所以也放弃使用贝叶斯优化.基于上述改进,提出了新的密钥恢复攻击,使得时间复杂度显著降低.为了验证新的密钥恢复攻击在时间复杂度上的优势,在11轮、12轮Speck32/64上进行了实际密钥恢复攻击,时间复杂度分别为2^(26.68)和2^(32.25).与已有的最优攻击相比,复杂度分别减少为原来的1/2^(11.32)和1/2^(11.1).此前没有研究从运行时间角度分析对基于深度学习的密钥恢复攻击,本文工作有助于推动基于深度学习的密码分析的研究.At CRYPTO 2019,Gohr proposed the first deep learning-based key recovery attack and applied to 11,12 rounds of Speck32/64 respectively.This paper presents some analysis on the attack and proposes some improvements.First,it is found that the runtime of the attack is mainly affected by three operations:decryption,accessing neural distinguishers and recommending key guess via Bayesian optimization.The last two operations consume almost all the runtime.Moreover,the reinforcement learning mechanism adopted by Gohr makes wrong ciphertext structures which wastes much computation resource.In order to reduce the time complexity,this paper proposes the following improvements:(1)the attack only adopts neural distinguishers that are built on few ciphertext bits,and these neural distinguishers are replaced with lookup tables during the attack;(2)the reinforcement learning mechanism is discarded,and a new Guess-and-Filter strategy is proposed.The Bayesian optimization is also not adopted because it is not necessary for the new strategy.Based on these improvements,new deep learning-based key recovery attacks on 11/12 round Speck32/64 are proposed.The time complexities for the proposed attacks are 2^(26.68)and 2^(32.25)respectively.Compared with the time complexity of the best-known attacks,the time complexity of the improved attacks is reduced by a factor of 2^(11.32)/2^(11.1).

关 键 词：深度学习 密钥恢复攻击 Speck32/64 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]