針對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.