针对RSA-CRT的深度学习侧信道攻击

RSA-CRT算法是使用中国剩余定理加速模幂运算的RSA算法，可大幅度降级计算时间。随着基于深度学习的侧信道分析技术的发展，DL-SCA越来越多的应用在恢复密码算法的密钥中。在公钥密码算法的DL-SCA中，研究主要集中于从能量或电磁波形中恢复更准确地估计秘密指数。

Kotaro Saito等人在2022年顶级学术期刊TCHES上，针对采用固定窗口模幂运算的RSA-CRT软件实现，提出了一种基于深度学习的侧信道攻击，还提出了一种适用于从秘密指数中存在错误分布的部分密钥泄露攻击，从而利用侧信息完全恢复RSA-CRT的密钥。

开源密码库GnuTLS及其后台Nettle需要调用Gnu MP来执行任意精度的运算，因此直接受到Gnu MP漏洞的影响。此外，OpenSSL、Botan和Libgcrypt开源密码库也可通过本篇论文提出的方案对RSA-CRT算法的模幂指数进行恢复。

方案一 基于深度学习的RSA-CRT算法侧信道攻击

利用虚拟加载的固定窗口模幂运算

RSA-CRT算法的效率取决于模幂运算的速度，一些开源密码库的模幂运算实现采用窗口取幂（即固定或滑动窗口取幂）。固定窗口求幂是最快的恒定时间模求幂算法。从左到右固定窗口模幂运算如下图算法1所示。其中，底数为c，指数l位用d表示，模数为N，窗口大小为w。如1-4行代码所示，首先预计算被乘数c₀、c₁...c₂^w_-1。算法第10-12行的循环进行平方计算，循环结束后进行乘操作，需要使用预计算得到的c₀、c₁...c₂^w_-1。

图1 固定窗口模幂运算过程

在固定窗口算法中，平方-乘运算序列不依赖于指数，因此SPA/SEM原则上无法获得有关秘密指数的任何信息。由于其恒定时间特性和高性能，许多开源实现都采用固定窗口求幂。

但由于计算过程中预计算被乘数c₀、c₁...c₂^w_-1，使用时直接读取到内存，因此可利用缓存攻击恢复c_i，进而得到i恢复完整密钥。为了防止缓存攻击，一些固定的窗口求幂的实现使用了虚拟加载，即对于每次乘法操作，所有被乘数都加载到内存，然后仅保留真实的被乘数，而其他被乘数作为伪加载被丢弃。这种虚拟加载方案对所有操作数执行加载操作，因此可以抵抗缓存攻击。

真相只有一个：使用深度学习区分真实/虚拟加载

使用虚拟加载的固定窗口求幂中，被乘数的加载按照从c₀到c₂^w_-1的确定顺序进行。对于指数中某一窗口值b，在第b次加载时为真实加载，并且所有剩余加载都是虚拟加载。因此，对于一个窗口而言，如果攻击者能够从加载的侧信息中区分真实/虚拟加载，则攻击者可以得知窗口值b。据此，本论文使用了区分真实加载和虚拟加载的2分类神经网络。

令β∈{0,1}为标签，其中β=1表示真实加载，β=0表示虚拟加载。并令q(β|X;θ)为网络输出，含义为真实/虚拟加载的概率，X表示加载过程中的侧信息，本论文主要使用加载过程中的电磁泄漏，θ是网络的超参数。主要关注q(1|X;θ)的取值，即当前加载为真实加载的概率。某个窗口的32次加载过程侧信息及其训练结果如下图所示，i=13时为真实加载，其概率为0.9，则此窗口值为13。依次恢复每个窗口的窗口值，将其转换为二进制序列即可完整恢复秘密指数。

图2 基于DL-SCA的秘密指数恢复示例

经过实验，该方案主要采用卷积神经网络，由6个卷积层和2个全连接的层组成，损失函数为二元交叉熵，学习率为0.00005，batch size为2000，1024位和2048位RSA-CRT的epoch分别为25和5。实验结果总结如下表所示，使用Gnu-MP库实现RSA-CRT算法，电磁波形中区分真实加载和虚拟加载的准确率分别为0.9994和0.9966，其窗口值预测准确率分别为99.80%和99.86%。此外，评估了单条波形攻击中包括多少错误估计（即，分别对1024位和2048位RSA-CRT的一次模幂操作预测128和205个窗口值）。单条波形攻击分别包含不超过2个或3个窗口值估计错误。

表1 实验结果

方案二 针对RSA-CRT算法的部分密钥泄露攻击

RSA算法部分密钥泄露攻击

RSA算法的部分密钥泄露攻击是一种从部分密钥位恢复整个密钥的算法，最早由Heninger–Shacham于2009年提出。已知50%的密钥即可使用部分密钥泄露攻击恢复完整密钥。根据RSA-CRT算法原理有以下公式：

ed_p=1+k_p(p-1)

ed_q=1+k_q(q-1)

e=2¹⁶+1,k_p,k_q是数量级为2¹⁶的整数，可以通过遍历得到，因此认为这两个值是已知的。设a[λ]为整数a的第λ位，a^(λ)为a二进制表示的后λ位，τ(a)为a二进制表示末尾有几个0。

根据算法原理有如下公式：

据此，定义Slice[λ]为如下格式：

其中，四元组每一项的取值为0或1。Slice[0]可由已知信息确定，根据公式（10）-（12），若Slice[λ-1],Slice[λ-2],…,Slice[0]确定，则Slice[λ]取值有两个解，即Slice可构成二叉树。结合已泄露的部分密钥，通过对二叉树的深度优先遍历可恢复完整密钥。

Slice二叉树

基于优先级队列的部分密钥泄露攻击

Heninger和Shacham提出的部分密钥泄露攻击不适用于泄露的密钥位存在错误的情况下恢复完整密钥，而使用论文提出的DL-SCA方案不能保证恢复的密钥位准确率为100%。因此本篇论文作者提出了基于优先级队列的部分密钥泄露攻击方案。

方案主要思想是将一个窗口内的Slice看作一个整体，用下面的形式表示：

其含义为第0位到第位范围内的密钥搜索路径。优先级计算基于匹配度I_λ-w，如下列公式：

（1）优先考虑当Slice^(λ-w+1,λ)、Slice^{(λ-2w+1,λ-w)}和 Slice^{(λ-3w+1,λ-2w)}连续3个窗口范围内d_p,d_q都正确的情况。

（2）连续3个窗口范围内d_p,d_q都不正确的情况应降低优先级。

（3）连续4个窗口范围内d_p,d_q都正确的情况，应比连续3个窗口正确的优先级更高。

三条优先级规则分别对应下列公式：

因此，优先级计算公式如下，C越小则表示优先级越高：

C₀=0

C_λ=C_λ-w+(2-I_λ-w)+h₁+h₂+h₃

根据上述优先级规则计算每个窗口大小范围内的优先级，可构造优先级队列。从密钥最低位开始，遍历Slice^(λ-w+1,λ)。最初入队的为第一个窗口范围内的候选Slice，由于队列中元素均带有优先级，因此每次出队的为优先级最高的Slice，即为最有可能是正确密钥的Slice，下次入队的Slice，为出队的Slice的候选。具体算法描述如下所示。

图3 基于优先级队列的部分密钥泄露攻击算法

针对1024bit和2048bit RSA-CRT算法的部分密钥泄露攻击实验结果箱线图如下所示。随着泄露的部分密钥错误窗口值越多，恢复完整密钥所需时间和队列长度越长。但第一个方案的实验结果可达到一次模幂运算的窗口值恢复不超过3个错误，因此结合部分密钥泄露攻击对剩余窗口值进行恢复的时间和空间开销可以容忍。

图4 1024bit RSA-CRT算法密钥恢复结果

图5 2048bit RSA-CRT算法密钥恢复结果

总结

论文作者提出了适用于软件实现RSA-CRT的DL-SCA和基于优先级队列的部分密钥泄露攻击。所提出的DL-SCA在使用固定窗口的方法下区分被乘数的真实/虚拟加载，以高精度地恢复指数的值。所提出的部分密钥泄露攻击适用于固定窗口模幂运算的场景，通过使用启发式和与泄露指数的匹配数量克服了传统算法的局限性。

参考资料

[1]Saito K, Ito A, Ueno R, et al. One Truth Prevails: A Deep-learning Based Single-Trace Power Analysis on RSA–CRT with Windowed Exponentiation[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022: 490-526.