胡 偉 袁超絢 鄭 健 王省欣 李倍倍 唐時(shí)博

(西北工業(yè)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 西安 710072)

1 引言

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

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

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

2 Kyber 算法原理

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

表1 Kyber PKE算法組成

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

Kyber KEM由密鑰生成、加密運(yùn)算和解密運(yùn)算3個(gè)部分組成，密鑰協(xié)商具體流程如圖1所示。

圖1 Kyber KEM 密鑰協(xié)商

圖1展示了通信雙方A, B進(jìn)行密鑰協(xié)商的過(guò)程，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()算法對(duì)密文c的正確性進(jìn)行檢查并生成共享密鑰K。

3 側(cè)信道攻擊模板構(gòu)建

3.1 密文篩選條件

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

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

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

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

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

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

表2 Kyber的選擇密文攻擊表

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

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

圖2 攻擊模板建立流程

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

4 側(cè)信道攻擊方法及框架

4.1 高階選擇密文攻擊

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

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

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

4.2 秘密系數(shù)破解方法

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

在圖3所示的攻擊流程中，通過(guò)計(jì)算目標(biāo)跡與攻擊模板的歐氏距離進(jìn)行匹配。與目標(biāo)跡距離小的模板相關(guān)性高，該模板對(duì)應(yīng)的數(shù)值可認(rèn)定為目標(biāo)跡對(duì)應(yīng)的值，結(jié)合選擇密文攻擊表和高階選擇密文攻擊方法即可破解對(duì)應(yīng)的多項(xiàng)式系數(shù)。

4.3 密鑰恢復(fù)方法

CPAPKE.KeyGen()函數(shù)中，可由多項(xiàng)式s經(jīng)過(guò)相關(guān)變換生成私鑰sk

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

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

對(duì)m′進(jìn)行編碼

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

若攻擊所得私鑰 sk 正 確，此時(shí)的c′應(yīng)和正確密鑰c相等。此時(shí)，進(jìn)行相關(guān)變換可得到共享密鑰K

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

5 實(shí)驗(yàn)與結(jié)果

5.1 實(shí)驗(yàn)設(shè)置

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

表3 測(cè)試案例實(shí)驗(yàn)環(huán)境

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

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

5.2 Kyber512側(cè)信道攻擊

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

表4 Kyber512選擇密文攻擊表

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

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

圖5 Kyber512平均能量跡和興趣點(diǎn)篩選

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

圖6 Kyber512高階選擇密文方法

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

5.3 Kyber768側(cè)信道攻擊

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

表5 Kyber768選擇密文攻擊表

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

圖7 Kyber768平均能量跡和興趣點(diǎn)篩選

使用高階選擇密文方法對(duì)多項(xiàng)式s的系數(shù)進(jìn)行恢復(fù)。當(dāng)η=2時(shí)s的系數(shù)為–2,–1,0,1,2，其概率分別為1/16,4/16,6/16,4/16,1/16，Kyber768高階選擇密文方法如圖8所示。

圖8 Kyber768高階選擇密文方法

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

利用同Kyber512相同的方法，在多項(xiàng)式s的系數(shù)完全恢復(fù)后再利用s對(duì) 私鑰s k進(jìn)行恢復(fù)，之后可再利用私鑰s k 對(duì) 共享秘鑰K進(jìn)行恢復(fù)。

5.4 性能分析

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

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

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

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

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

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

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

6 結(jié)論

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