胡 偉 袁超絢 鄭 健 王省欣 李倍倍 唐時博

(西北工業(yè)大學網絡空間安全學院 西安 710072)

1 引言

公鑰密碼的安全性受到量子計算的嚴峻威脅，為此，基于數學困難問題設計的抗量子計算機攻擊的后量子密碼算法研究受到廣泛關注。美國國家標準技術研究所(National Institute of Standards and Technology, NIST)和中國密碼學會(Chinese Association for Cryptologic Research, CACR)針對后量子密碼進行了系統的研究。后量子密碼可分為基于格、基于多變量、基于編碼、基于超奇異同源、基于哈希等[1]幾種主要類型。其中，構建基于格理論數學困難問題之上的格基后量子密碼算法在安全性、密鑰尺寸、性能上達到了更好的平衡，是公認最有前景的后量子密碼算法之一。雖然格基后量子密碼在理論上可抵抗量子計算機攻擊，但在算法執(zhí)行時仍易受到側信道攻擊。

近年來，已有學者對格基后量子密碼算法的側信道攻擊展開了研究。2017年，Primas等人[2]對受到掩碼保護的格密碼進行了單能量跡攻擊，其攻擊點為數論變換(Number Theoretic Transforms,NTT)。2018年，Kim等人[3]則對Frodo算法的密鑰封裝機制(Key Encapsulation Mechanism, KEM)進行了單能量跡攻擊。2019年，Ding等人[4]和B?etu等人[5]提出了一種選擇密文攻擊方法，該方法基于冗余的消息編碼和密文壓縮功能以及大跨度的秘密系數；Pessl等人[6]對Kyber算法加密變換中的NTT變換進行了單能量跡攻擊。2020年，Ravi等人[7]針對Kyber等多種格密碼算法進行了選擇密文攻擊，他們的攻擊點選擇為糾錯碼和FO(Fujisaki-Okamoto)變換；Amiet等人[8]針對NewHope算法提出了一種單能量跡消息恢復方法，將一條攻擊能量跡劃分為32個分段，再分別進行模板匹配；Ravi等人[9]將側信道攻擊目標定為存儲在內存中的解密消息，利用解密消息1次存儲1 bit的特點對解密消息進行恢復。2021年，Ngo等人[10]基于深度學習技術提出了對受到1階掩碼保護的Saber密碼算法的側信道攻擊；同年Ngo等人[11]又對受到1階掩碼和洗牌技術保護的Saber KEM的軟件實現進行了安全性分析。2022年，Xu等人[12]對Kyber算法使用選定密文進行電磁(Electro Magnetic, EM)側信道攻擊；Tanaka等人[13]針對后量子KEM提出了一種高效的側信道輔助密鑰恢復明文檢查攻擊(Key-Recovery Plaintext-Checking Attack, KR-PCA)，成功實現了密鑰恢復。2023年，Bock等人[14]提出一種新的模板攻擊，能夠直接從解封裝過程的多項式乘法中恢復Kyber的密鑰；Guo等人[15]提出了一種針對不可區(qū)分選擇密文 (INDistinguishability-Chosen Ciphertext Attack, IND-CCA)安全后量子加密方案的密鑰側信道恢復攻擊，并對Kyber768的掩碼實現進行了攻擊。

本文利用秘密多項式系數與能耗的相關性建立了針對格基后量子密碼(Post-Quantum Cryptography, PQC)的側信道攻擊框架，提出一種高階選擇密文側信道攻擊方法，實現了對Kyber算法的側信道攻擊分析。與現有針對Kyber的選擇密文側信道攻擊[7]相比，本文提出的攻擊方法，有效降低了選擇密文攻擊所使用的密文條數，破解Kyber512和Kyber768密鑰所需密文條數分別降低了58.48%和47.5%，表明了高階選擇密文攻擊方法的可行性和有效性。

2 Kyber 算法原理

Kyber的安全性基于求解模誤差學習問題(Module Learning With Errors, MLWE)的困難性，利用非對稱思想實現加密算法和密鑰封裝協商機制。Kyber公鑰加密方案(Public Key Encryption,PKE)處于不可區(qū)分選擇明文攻擊(INDistinguishability-Chosen Plaintext Attack, IND-CPA)安全級別。該方案主要包含密鑰生成、加密和解密算法，算法細節(jié)如表1所示。

表1 Kyber PKE算法組成

密鑰封裝協商是基于Kyber PKE來實現通信雙方的密鑰協商，通過FO變換來構造IND-CCA2安全KEM，稱為Kyber KEM。理論上，FO變換有助于保護KEM免受選擇密文攻擊，FO變換主要涉及解密后的重新加密，能夠檢測到無效或惡意形成的密文，并在檢測時返回失敗，但是任何加密算法在真實設備上實現時都會通過側信道泄露出有關中間值的信息，本文的攻擊目標選定在FO變換，本文的攻擊同樣適用于那些沒有使用糾錯碼的格基密碼方案，如NewHope, Frodo, Saber等。

Kyber KEM由密鑰生成、加密運算和解密運算3個部分組成，密鑰協商具體流程如圖1所示。

圖1 Kyber KEM 密鑰協商

圖1展示了通信雙方A, B進行密鑰協商的過程，A利用Kyber.CCAKEM.KeyGen()算法生成公鑰pk和私鑰 sk ， 并將公鑰p k 發(fā)給B。B基于公鑰p k利用Kyber.CCAKEM.Enc()算法生成密文c和共享密鑰K，B將密文c發(fā)送給A，將共享密鑰K保留。A在收到B發(fā)送的密文c后使用Kyber.CCAKEM.Enc()算法對密文c的正確性進行檢查并生成共享密鑰K。

3 側信道攻擊模板構建

3.1 密文篩選條件

算法1展示了基于中間變量(u,v,s)完成解密的方法。解碼密文c得到多項式系數(u,v)，解碼私鑰sk得 到秘密多項式s的系數，通過Poly_to_Msg即可獲得信息m′?？梢姡兞?u,v)決定了密文c，(s k,c)唯一確定了信息m′，而s k又與s直接相關，這為實現對Kyber的側信道攻擊分析提供理論依據。

令ku=u[0],kv=v[0]，u和v的其他系數為0。則消息m′可由式(1)按比特位進行解密

根據式(1)，消息m′僅 依賴于s[0]，因此可通過篩選ku和kv使 得消息m′和s[0]滿足式(2)

因此，攻擊者可通過選擇(ku,kv) 生成密文c，使解密消息m′=0 或m′=1， 進而唯一確定s[0]的值。類似地，攻擊者通過改變u中非0系數的位置，將ku的 值依次賦給u[0],u[1], ···,u[n-1]，同時將此時多項式的其他系數賦為0。按對應順序恢復s[0],-s[n-1],-s[n-2], ···, -s[2],-s[1] 后可獲得私鑰s k。

算法1 Kyber.CPAPKE.Dec(sk, c)

在Kyber.CPAPKE.KeyGen()算法中，多項式s的系數由一個中心二項分布函數CBDη產生。而s的每一個系數的范圍在[-η,η]之 間，其中η=2或η=3 。 經多次實驗搜索(ku,kv) ，使得s∈[-η,η]時對應的解密信息m′=0或m′=1，如表2所示。攻擊者可利用表2中的密文條件實現對Kyber的側信道攻擊。

表2 Kyber的選擇密文攻擊表

3.2 創(chuàng)建攻擊模板

構建選擇密文攻擊表和創(chuàng)建攻擊模板的前提是攻擊者已知密碼算法的實現細節(jié)，通過選擇密文、執(zhí)行算法、采集能量跡來建立模板和選擇密文攻擊表。攻擊者首先選擇(ku,kv) 生成密文c，在此密文條件下，解密信息m′=0 或m′=1，再根據解密信息m′的 值和多項式s的系數的值確定選擇密文攻擊表，同時在執(zhí)行Kyber的密鑰解封裝過程中，分別采集m′=0 和m′=1兩種情況下的能耗曲線以創(chuàng)建攻擊模板。攻擊模板構建流程如圖2所示，通過對采集的能量跡進行去噪和興趣點篩選，得到m′=0和m′=1的模板跡。

圖2 攻擊模板建立流程

建立攻擊模板時，需對采集到的能量跡進行分組，按組計算平均能量跡，以降低噪聲。最后采用測試矢量泄漏評估(Test Vector Leakage Assessment,TVLA)方法篩選興趣點。

4 側信道攻擊方法及框架

4.1 高階選擇密文攻擊

模板匹配時，普通選擇密文方法[7]需要2η+1條密文來破解多項式s的系數。本文首次提出了高階選擇密文攻擊方法，基于密文特點，對密文進行選擇，縮小多項式s系數的候選值范圍；再次挑選密文使得候選值不斷縮小，直至候選值唯一，具體流程如圖3所示。

圖3 高階選擇密文攻擊分析流程圖

經η個選擇密文的能量跡完成模板匹配后，若多項式s的系數唯一，則說明攻擊成功。若系數不唯一，則可將s的范圍縮小到N個候選值集合中，第i個候選值集合的階數用ni表示，則每個集合最多再需分析ni-1條密文即可確定密鑰信息，可顯著降低攻擊所需要的密文條數。

4.2 秘密系數破解方法

攻擊者可以選擇輸入密碼設備的密文，運行Kyber密鑰解封裝模塊并采集能量跡，利用選擇密文攻擊表中的(ku,kv) 成密文c；攻擊者可通過輸入不同的密文c獲取對應能量跡，將能量跡與攻擊模板進行匹配，并對照選擇密文攻擊表分析多項式s的系數。

在圖3所示的攻擊流程中，通過計算目標跡與攻擊模板的歐氏距離進行匹配。與目標跡距離小的模板相關性高，該模板對應的數值可認定為目標跡對應的值，結合選擇密文攻擊表和高階選擇密文攻擊方法即可破解對應的多項式系數。

4.3 密鑰恢復方法

CPAPKE.KeyGen()函數中，可由多項式s經過相關變換生成私鑰sk

其中，q為算法參數，NTT()函數為數論變換函數，Encode12()函數為編碼函數，可以將多項式系數轉化為字節(jié)流。這些參數和函數均為已知，因此在破解多項式s系數后可以得到私鑰s k。

在算法Kyber.CCAKEM.Dec()中利用攻擊得到的私鑰s k 對 正確密文c解密得到m′

對m′進行編碼

其中h=H(pk)，G和H為哈希函數。使用公鑰加密m′獲 得密文c′

若攻擊所得私鑰 sk 正 確，此時的c′應和正確密鑰c相等。此時，進行相關變換可得到共享密鑰K

其中KDF為一種哈希函數。上述由私鑰s k得到共享密鑰K的變換過程中所需要的參數和函數均為已知，因此可由私鑰s k 破解出共享密鑰K。

5 實驗與結果

5.1 實驗設置

實驗環(huán)境如表3所示。使用C語言在stm32開發(fā)板上實現Kyber密鑰協商算法，使用Pico示波器采集能量跡，使用python對能量跡進行分析，實現高階選擇密文側信道攻擊。

表3 測試案例實驗環(huán)境

高階選擇密文攻擊分析流程如圖4所示，首先需根據Kyber512和Kyber768算法原理，篩選符合條件的密文c使得運行解封裝函數時中間值m′=0和m′=1， 分別采集密文解密時的能量跡，建立m′=0和m′=1的攻擊模板。然后，采集目標跡，根據目標跡與模板的匹配程度，破解秘密多項式s的系數，使用密鑰生成算法Kyber.CPAPKE.KeyGen()恢復私鑰s k， 最后利用得到的s k恢 復共享密鑰K。

圖4 高階選擇密文攻擊分析流程

5.2 Kyber512側信道攻擊

在對Kyber512進行側信道攻擊時首先選擇特定的密文構建選擇密文攻擊表。Kyber512中變量η=3 ， 因此多項式s的系數為–3～3。文獻[7]的攻擊方案，需要7種密文才能破解Kyber512的所有多項式系數，本文對其進行了優(yōu)化僅需要6種，Kyber512選擇密文攻擊表如表4所示。

表4 Kyber512選擇密文攻擊表

采集Kyber512解密過程中運行哈希函數G時的能量跡。使用兩組密文數據，在m′=0 和m′=1的情況下，分別采集10 000條能量跡；對這兩組能量跡按每200條取平均后轉換為50條平均能量跡作為模板。取平均能量跡降低了噪聲的影響，使構建的攻擊模板更加精確，有利于提高攻擊結果的準確性。

篩選興趣點時需對比m′=0 和m′=1的平均能量跡。如圖5(a)所示，紅色為m′=0時哈希函數G的能量跡；藍色為m′=1時哈希函數G的能量跡。使用TVLA方法對比兩組平均能量跡的差異，如圖5(b)所示，設置閾值為4，選擇TVLA值大于4或小于–4的點作為興趣點，建立m′=0和m′=1的模板。

圖5 Kyber512平均能量跡和興趣點篩選

攻擊者可選擇密文輸入，運行Kyber512密鑰協商算法的解密函數，無需獲知密碼算法實現細節(jié)。使用高階選擇密文方法恢復多項式s所有的系數。Kyber算法中多項式s的每個系數由中心二項分布函數CBDη產生。當η=3時 ，s的系數為–3,–2,–1,0,1,2,3，其概率分別為1/64, 6/64, 15/64, 20/64,15/64, 6/64, 1/64。當使用高階選擇密文方法有策略地對密文進行選擇時，對于出現頻率高的系數應盡可能使用更少的密文，Kyber512高階選擇密文方法如圖6所示。

圖6 Kyber512高階選擇密文方法

對于多項式s，首先使用(3 120, 2 380)和(3 120,1 130)構建密文進行攻擊，根據m′的值可以將其分為3個集合，即(–3, –2, –1),(0)和(1, 2, 3)。再對集合(–3, –2, –1)和(1, 2, 3)加以區(qū)分，直至破解出系數值。由圖6可知當系數為0時需要2條密文，當系數為–1和1時需要3條密文，當系數為–3,–2,2,3時需要4條密文。系數出現的頻率越高攻擊所需的密文越少，可利用這一特性降低所需的密文數量。在破解出多項式s的所有多項式系數后，可再根據4.3節(jié)介紹的密鑰恢復算法得到私鑰s k和 共享密鑰K。

5.3 Kyber768側信道攻擊

類似地選擇特定密文構建選擇密文攻擊表。Kyber768中的變量η=2， 因此s的系數為–2～2。文獻[7]的攻擊方案，需要5種密文才能破解Kyber768的所有多項式系數，本文僅需要4種密文，Kyber768選擇密文攻擊表如表5所示。

表5 Kyber768選擇密文攻擊表

Kyber768算法攻擊的能量跡采集方法、平均能量跡計算方法以及興趣點篩選方法均與Kyber512算法攻擊過程類似。如圖7(a)所示，紅色為m′=0時哈希函數G的平均能量跡，藍色為m′=1時哈希函數G的平均能量跡。如圖7(b)所示，設置閾值為2，選擇能量跡中TVLA值大于2或小于–2的點作為興趣點。

圖7 Kyber768平均能量跡和興趣點篩選

使用高階選擇密文方法對多項式s的系數進行恢復。當η=2時s的系數為–2,–1,0,1,2，其概率分別為1/16,4/16,6/16,4/16,1/16，Kyber768高階選擇密文方法如圖8所示。

圖8 Kyber768高階選擇密文方法

對于多項式的一個系數s首先使用(10,740)和(10,2 400)構建密文進行攻擊，根據m′的值可以將其分為3個集合分別是(–2, –1),(0),(1, 2)。之后再使用(110, 530)和(110, 2 610)分別對集合(–2, –1)和(1,2)加以區(qū)分。由圖8可知當系數為0時需要2條密文，當系數為–2,–1,1,2時分別需要3條密文。

利用同Kyber512相同的方法，在多項式s的系數完全恢復后再利用s對 私鑰s k進行恢復，之后可再利用私鑰s k 對 共享秘鑰K進行恢復。

5.4 性能分析

本文成功建立了針對格基PQC的側信道攻擊框架，并首次提出了一種高階密文選擇方法，在攻擊過程中通過利用密文的特點，改變選擇密文的方式可以極大減少攻擊過程所需要的密文。以Kyber512和Kyber768算法為例，成功恢復出兩種密碼算法的多項式s的系數，以及加密私鑰s k和共享密鑰K，驗證了該方法的可行性和有效性。

另外，本文所提方法在攻擊所針對的密碼算法數量、攻擊成功率、攻擊所用密文數量等方面均有優(yōu)勢。

在攻擊所針對的密碼算法方面，本文的攻擊方法不僅可以對Kyber進行攻擊，還可以對NewHope,Frodo, Saber等多種不使用糾錯碼的格基后量子密碼進行攻擊，攻擊覆蓋面較廣。

在攻擊成功率方面，本文方法對Kyber512和Kyber768的攻擊成功率均可達到99%。 表6展示了不同方案攻擊的密碼算法及成功率。

表6 不同方案攻擊的密碼算法及成功率

在攻擊所使用密文數量方面，本文對于文獻[7]中的方法進行了改進，可以使用更少的密文恢復出多項式s的系數。文獻[7]、文獻[9]和文獻[13]均對Kyber512進行了側信道攻擊。攻擊s的所有位置，文獻[7]中的方法需要3 584條密文，本文中所提出的高階選擇密文攻擊方法僅需1 488條密文，降低了約58.48%。文獻[9]針對Kyber512進行攻擊需要128 000條密文。文獻[13]針對Kyber512進行攻擊需要1 728條密文。文獻[7]、文獻[13]均對Kyber768進行了側信道攻擊。攻擊s的所有位置，文獻[7]中的方法需要3 840條密文，本文中所提高階選擇密文攻擊方法僅需2 016條密文，降低約47.5%。文獻[13]針對Kyber768進行攻擊需要3 456條密文。文獻[6]和文獻[14]對Kyber進行了單能量跡側信道攻擊，在此不做對比。圖9(a)和圖9(b)分別展示了不同方案攻擊Kyber512和Kyber768使用的密文數。

圖9 不同方案攻擊Kyber使用的密文數柱形圖

6 結論

本文建立了一種針對格基PQC的側信道攻擊框架，并提出了高階選擇密文側信道攻擊方法。與文獻[7]的選擇密文攻擊方法相比，本方法恢復Kyber512和Kyber768的密鑰所需密文數分別降低了58.48%和47.5%，攻擊成功率均達到99%。通過將本文方法應用于NewHope, Frodo, Saber等多種格基后量子密碼算法，驗證了本文所提方法在適用密碼算法數量、攻擊成功率、攻擊所需密文數量等方面均有顯著優(yōu)勢，能夠為評估后量子密碼算法實現側信道安全風險提供支撐。