Kyber密碼體制下的抗側信道攻擊方案研究

摘要：隨著量子計算的進步，傳統公鑰密碼體系（如RSA、ECC）面臨被量子計算機破解的風險。為此，NIST自2016年起啟動了抗量子密碼算法（PQC）的標準制定工作，并于2022年選擇了CRYSTALS-Kyber作為公鑰加密密鑰封裝機制（KEM）之一。盡管Kyber在理論上具有很高的安全性，但實際應用中仍需防范側信道攻擊。據此，研究了Kyber算法的掩碼防護方案實現及其性能分析。首先，介紹了Kyber算法的基本原理和其在NIST標準化過程中的重要性。接著，詳細探討了如何將掩碼技術應用于Kyber算法的關鍵步驟，以提高其抗側信道攻擊的能力，并通過實驗評估，對比了掩碼方案與未使用掩碼的Kyber算法在抗側信道攻擊方面的性能差異。最后，總結了Kyber掩碼方案的優勢與局限，并提出了未來的研究方向，強調了掩碼技術在提高Kyber密碼體制下的抗側信道攻擊安全性方面的重要作用，以及進一步優化掩碼方案以適應更多硬件環境的需求。

關鍵詞：密碼學；Kyber；抗側信道攻擊；掩碼算法

中圖分類號：TN918.91 收稿日期：2024-07-15

DOI：10.19999/j.cnki.1004-0226.2024.10.013

1 前言

隨著量子計算技術的快速發展，現有的基于數學難題的公鑰密碼系統，如RSA和橢圓曲線密碼系統等，都面臨著被量子計算機破解的潛在風險。因此，開發一種能夠抵抗量子計算攻擊的后量子密碼學算法成為了一個緊迫的現實任務。Kyber算法作為一種基于模容錯學習問題（Module Learning with Errors，MLWE）的后量子密鑰封裝機制[1]，因其高效性和安全性已被NIST選為后量子密碼標準化算法的最終候選者[2]。

然而，除了量子計算的威脅，側信道攻擊也是密碼系統安全的重要考量因素。側信道攻擊通過分析密碼算法執行過程中的物理特性（如功耗、電磁輻射、執行時間等）來提取敏感信息[3]。為了增強密碼系統的抗側信道攻擊能力，掩碼技術被廣泛研究和應用。掩碼技術通過引入隨機化元素來掩蓋計算過程中的敏感數據，使得即使在側信道泄露的情況下，攻擊者也無法獲取足夠的信息來破解密碼系統[4]。

本文的研究背景植根于當前密碼學領域面臨的兩大挑戰：量子計算機的崛起和側信道攻擊的威脅。筆者通過對Kyber算法實施掩碼技術來提高抗側信道攻擊安全能力，并對其安全性進行深入的理論分析和實驗評估。

2 基礎知識

2.1 MLWE問題

模容錯學習問題（MLWE）是LWE問題的一個推廣。LWE問題主要基于有噪聲情況下解決線性方程組的困難性，而MLWE則將其擴展到了更高維度的多線性空間中，通過引入環結構，增加了計算復雜度，從而增強了安全性。在MLWE中，不再只處理單一的線性變換，而是將問題擴展到mod q的多項式環[Rq]中。其可以表述如下：

環的維度為d，其中[d>1]。選取一個大素數q，再隨機選擇一個秘密多項式[s∈Rq]，s可以看做是一個長度為d的向量，對于每個[i=1，2，…，d]，選取一個隨機矩陣[ai∈Rq]，噪聲分布為x，計算：

[bi=（ai?s+ei） mod q] （1）

式中，[ei∈Rq]是根據噪聲分布x獨立同分布生成的誤差多項式，目標是恢復秘密多項式s。

MLWE問題的困難性在于，即使提供了多個帶有噪聲的多項式方程，準確地恢復出s但在計算上仍然是不可行的，特別是當d和q足夠大的時候。噪聲的存在使得方程的直接求解變得極其困難，因為這需要解決一個高維的最短向量問題，也就是NP難問題。

2.2 掩碼算法

在密碼學和計算機科學中，掩碼算法是一種重要的安全防護措施，它主要用于保護數據處理過程中的敏感信息，尤其是加密算法的內部狀態以及密鑰。掩碼算法的實現主要基于“秘密分享”思想，即將一個秘密（比如一個密鑰）分割成多個子秘密，單個子秘密的擁有者無法通過該子秘密分析出原秘密，但當這些子秘密以特殊方式組合時可以恢復出原始秘密[5]。也就是說，掩碼算法通常會將敏感數據分割成多個部分（通常稱為“shares”），再引用不同的隨機值（也稱為掩碼或mask）對每個部分進行按位異或等操作，從而模糊側信道信息與真實數據之間的聯系，以防止直接暴露原始數據。這種方法可以顯著降低側信道攻擊的風險[6]。側信道攻擊是指通過分析密碼算法執行過程中的物理特性（如功耗、電磁輻射、執行時間、聲音、溫度變化等）來提取敏感信息的攻擊方式[7]。這些物理特性通常是算法執行的副產品，與實際的計算邏輯無關，但卻可以反向推斷出關于具體加密操作的信息。

掩碼算法按照運算方式來講，通常分為布爾掩碼與加性掩碼：

布爾掩碼（Boolean Masking）：假設有一個原始數據向量[D=d1，d2，…，dn]，想對其進行加密以保護數據的隱私。為此，引入一個隨機生成的布爾掩碼向量[M=m1，m2，…，mn]，其中[mi]是與[di]相異或的掩碼值。應用布爾掩碼的加密過程可以用以下公式表示：

[E=（DM） mod q] （2）

這里的[E=e1，e2，…，en]是加密后的數據向量，每個元素[ei=di°mi]，運算符[°]表示異或操作。

解密過程則是簡單的逆運算：

[D=（EM） mod q] （3）

通過這種方式，布爾掩碼提供了數據保護，同時允許在特定條件下（知道掩碼值）恢復出原始數據。

加性掩碼（Additive Masking）：加性掩碼又稱算術掩碼，與布爾掩碼類似，只是將布爾掩碼中的異或操作換成了加法運算。

即應用加性掩碼進行的加密操作可以用以下公式表示：

[E=（D+M） mod q] （4）

解密過程則是從加密數據中減去原來的掩碼值：

[D=（E?M） mod q] （5）

總的來說，掩碼技術的核心目的是通過增加計算過程中的復雜性和不確定性，使得攻擊者即使能夠獲取到某些中間結果或觀測到系統的行為變化，也無法直接利用這些信息還原出敏感數據，從而提高了系統的整體安全性。

2.3 Welch's t-test

Welch's t-test，也被稱為Welch's t檢驗或不等方差t檢驗，是一種用于比較兩個獨立樣本均值是否存在顯著差異的統計方法，尤其適用于兩組樣本方差不相等的情況[8]。

在進行兩獨立樣本均值差異檢驗時，若直接使用Student's t-test，通常要求兩組數據不僅來自正態分布，而且方差相等。然而，在現實研究中，兩組數據的方差往往不相等，此時使用Student's t-test可能導致檢驗結果不可靠，犯一類或二類錯誤的風險增加[9]。Welch's t-test通過放松方差相等的假設，提供了更合適的解決方案。

Welch's t-test的計算步驟如下：

首先，分別計算兩組樣本的平均值[（x1，x2）]和樣本方差[（s21，s22）]。由于假設方差不等，Welch's t-test采用兩組樣本方差的無偏估計來代替總體方差，有時還會對小樣本進行校正。接著，基于兩組樣本的均值差、各自樣本方差的估計以及樣本大小計算t值。公式如下：

[t=x1?x2s21n1+s22n2] （6）

式中，[n1]和[n2]分別是兩組樣本的大小。

與Student's t-test不同，Welch's t-test的自由度（下文用F表示）不是簡單地基于樣本大小，而是通過Satterthwaite近似法得到，該方法考慮到方差的不確定性：

[F≈s21n1+s22n22s41n21n1?1+s42n22n2?1] （7）

實際應用中，這個自由度經常進行近似計算，以簡化過程。

接著，使用得到的t統計量和自由度查找t分布表或使用統計軟件計算相應的p值，以判斷兩組均值差異的顯著性。

最后，如果p值小于預設的顯著性水平（一般設為0.05），則拒絕原假設，即認為兩組均值存在顯著差異；如果p值大于顯著性水平，則接受原假設，即認為沒有足夠證據表明兩組均值有顯著差異。

3 Kyber掩碼方案

3.1 Kyber算法分析

基于MLWE問題構造的Kyber算法作為當前KEM的標準，其安全性主要依賴于解決MLWE問題的困難性。這里本文先簡單介紹一下Kyber算法的基本步驟，其主要分為兩個部分：密鑰生成、封裝與解封裝。

3.1.1 密鑰生成

首先確定算法所需要的參數，包括模數q、多項式度數（使用多項式的最大次數）n、每個向量的維度（即每個向量包含幾個多項式）k、控制小系數的范圍[η1、η2]（[η1]控制s、e和r的系數范圍，[η2]控制[e1、e2]的系數范圍）、控制多少（u，v）被壓縮的[du和dv]，以及解密出現錯誤的概率[δ]。不同標準的Kyber算法參數總結如表1所示。

密鑰生成階段會生成一個私鑰s，一個公鑰（A，b）。對于私鑰，需要先生成一個大矩陣A，A中的元素都來自于特定的環[Rq]，也就是說要對矩陣A中的元素進行模q運算，通常使用拒絕采樣技術來保證矩陣的質量，進而保證隨機性，再根據其生成一個私鑰s。而公鑰包含兩個部分，分別是隨機矩陣A和多項式向量b，其中[b=A?s+e]，這里e是一個帶有噪音的向量，用來提高安全性。整個算法過程都建立在MLWE問題上，即已知（A，b）求解s，這對于量子計算機來講也是一個難以解決的問題。

3.1.2 封裝與解封裝

在Kyber中，多項式環一般為[Rq=Zqx/xn+1]，其中q=3 329，n=256。并且每一個多項式都滿足[fx=a0+a1x+…+an?1xn?1∈Rq]、每一個系數滿足[ai∈Zq0≤i≤n?1]，其中[Zq]表示模q的整數環，所有的多項式加法和乘法的結果都需要對多項式[xn+1]進行約簡。

在Kyber中，不同的k值代表著不同級別的安全性。目前，在安全防護能力方面，Kyber算法共有3種等級分類，即k分別取值為2、3、4時的Kyber-512、Kyber-768和Kyber-1024，分別與NIST定義的3種安全級別1（AES-128）、3（AES-192）和5（AES-256）相對應。

這里，首先定義兩個主要函數[Comqx，d]和[Decqx，d]。

定義Compress函數：[Zq→Z2d]。

[Comqx，d=（2d/q）x（mod 2d）] （8）

定義Decompress函數：[Z2d]→[Zq]。

[Decqx，d=（q/2d）x] （9）

上述Compress和Decompress函數中的輸入x均從[Zq]中選取，參數d指的是[du]或[dv]。在表2的封裝與解封裝算法中，[←]表示隨機選擇操作，角標[T]表示矩陣的轉置，G和H表示對應的哈希函數，KDF表示密鑰派生函數。Kyber算法通過使用FO變換（Fujisaki Okamoto Transform）將CPA（選擇明文攻擊）安全的公鑰加密技術轉換為CCA（選擇密文攻擊）安全的密鑰封裝機制。在CCAKEM.Encaps中，使用加密算法CPA.Enc來生成密文[c1]和[c2]，其中可以通過修改[Comqx，d]和[Decqx，d]函數中用到的參數[du]和[dv]來達到不同的安全級別。

3.2 實驗方案

帶掩碼的中心二項抽樣（Masked Centered Binomial Distribution，MCBD）是一種應用于密碼學中的技術，這里本方案將其應用于Kyber，用于增強側信道攻擊的防御能力。中心二項分布抽樣是Kyber密碼系統中的一個重要步驟，它用來生成具有特定統計特性的隨機數，這些隨機數對于保513614fd62c3e69f83a2a312873626cf證密鑰交換協議的安全性至關重要。

為了使用隨機種子作為輸入從中心二項分布進行確定性采樣，Kyber指定使用SHA-3（SHAKE）作為偽隨機函數（PRF）來生成足夠多的隨機位。對于掩碼實現，隨機種子以布爾掩碼的形式給出，使用Keccak的一階掩碼對其進行加密處理。這樣，即使是在側信道攻擊的環境下，帶掩碼的中心二項抽樣也能安全地生成所需的隨機樣本，進而保障了整個加密過程的安全性。

掩碼技術主要是將敏感變量與隨機掩碼進行特定運算，以此來混淆真實數據的蹤跡，避免被硬件信息泄露。這些掩碼會隨著運算一起傳播，并在適當的時候去除，以回復原始數據。

因此，方案還需要將掩碼技術添加到Kyber算法的重要數學運算中。根據對Kyber算法代碼的嚴格審計，方案主要是對以下8個關鍵函數增添了掩碼技術的改進。

a.poly_invntt（）→masked_poly_invntt（）。

b.poly_sub（）→masked_poly_sub（）。

c.poly_basemul（）→masked_poly_basemul（）。

d.poly_tomsg（）→masked_poly_tomsg（）。

e.poly_frommsg（）→masked_poly_frommsg（）。

f.poly_reduce（）→masked_poly_reduce（）。

g.poly_compress（）→masked_poly_compress（）。

h.cbd（）→masked_cbd（）。

4 實驗結果與分析

4.1 測試環境

本次方案安全性測試主要使用基于Qt實現的電磁波形采集平臺，采集電磁波形，再使用t檢驗對Kyber掩碼方案進行抗側信道攻擊的安全性評估。

測試環境如圖1所示。主要使用STM32F103開發板的串口通信模塊與Qt上位機進行交互。完成代碼的燒錄，與上位機通信進而調用其上Kyber算法。測試過程中Qt程序主機作為上位機與STM32F407G開發板進行交互，其中STM32F103開發板載CH340用于將USB接口轉換為串口（UART）接口的應用中，主要用于連接計算機與STM32F407G開發板之間的通信。STM32F407G開發板上運行Kyber算法。

EM5030系列近場探頭用來收集Cortex-M4芯片運行Kyber算法時的電磁輻射信號。探頭內的天線處于發射天線的電磁場范圍內時，它會感應到電磁場的變化，并將其轉換為電信號。EM5030系列探頭具有寬頻帶和高靈敏度的特點，能夠有效地接收來自被測設備的電磁信號，并將其傳輸到前置放大器進行后續處理。它們通常具有不同的設計和頻率范圍，可以適應本次安全性測試中的測量需求。

圖1中Pico觸發器的主要功能是接收觸發信號，進而將信號傳輸給示波器，開啟波形的采集。Picoscope 3203D示波器的分辨率為8bits at 1GS/s，帶寬為50 MHz，存儲深度為64 MS。

EM5030系列前置放大器具有高增益和低噪聲特性，能夠有效地放大接收到的信號，并提供清晰的測量結果。在本次測試中，前置放大器用于放大EM5030系列近場探頭接收到的微弱信號，以便更好地進行測量和分析。其主要作用是提高信號的靈敏度和可靠性，并降低噪聲干擾對測量結果的影響。

4.2 測試結果分析

圖2和圖3分別是對poly_basemul（）函數和masked_poly_basemul（）函數運算過程采集的電磁輻射信號波形圖。

圖4是未加掩碼的poly_basemul（）函數的TVLA圖。一般認為t值超過4.5的點就是興趣點，也就是存在信息泄露風險的點。經觀察可得，該圖中存在大量興趣點，即未加掩碼的poly_basemul（）函數運算過程中存在信息泄露風險，也就是說可以通過TVLA對側信道采集的波形分析來獲取秘密信息。

圖5是添加了掩碼的masked_poly_basemul（）函數的TVLA圖。經觀察可得，圖中t值都小于4.5，即未檢測到存在秘密信息泄露風險，也就是說無法通過TVLA對側信道采集的波形分析來獲取masked_poly_basemul（）函數運算過程中的秘密信息。

圖6和圖7分別是對poly_compress（）函數和masked_poly_compress（）函數運算過程采集的電磁輻射信號波形圖。

圖8是未加掩碼的poly_compress（）函數的TVLA圖。經觀察可得，側信道攻擊者可以通過TVLA對側信道采集的波形分析來獲取秘密信息。

圖9是添加了掩碼的masked_poly_compress（）函數的TVLA圖。經觀察可得，圖中t值基本都小于4.5，無法通過TVLA對側信道采集的波形分析來獲取masked_poly_compress（）函數運算過程中的秘密信息。

綜上所述，添加了掩碼之后的關鍵函數已經無法再通過TVLA對側信道采集的波形分析來獲取運算過程中的秘密信息，也就是說該Kyber掩碼方案已經具有較強的抗側信道攻擊安全性。

5 總結與展望

5.1 主要研究成果

本文主要針對后量子密碼領域中的Kyber算法，提出并實現了一種一階掩碼方案，旨在顯著提升其在物理安全層面的防御能力，尤其是針對日益嚴峻的側信道攻擊威脅。通過深入分析Kyber算法的運算流程與潛在的側信道泄漏點，本文設計了一套高效且針對性強的掩碼機制，成功將一階掩碼技術融入算法的核心計算環節，有效抑制了敏感數據處理過程中泄露的信息量，從而加強了算法的整體安全性。

針對Kyber算法中的關鍵運算，如NTT變換、多項式乘法等，本文設計并實現了有效的掩碼生成與融合策略。該方案利用隨機掩碼覆蓋了運算中的中間結果，確保了算法執行過程中的信息泄露最小化，同時保持了算法的正確執行。

本文還針對該方案進行了側信道攻擊的測試向量泄漏評估實驗。實驗結果顯示，加入掩碼后的Kyber算法在側信道攻擊下的信息泄漏顯著減少，驗證了掩碼方案的有效性。

本文通過為Kyber算法添加掩碼方案，有效地提升了其在實際部署中抵御側信道攻擊的能力，不僅鞏固了Kyber作為后量子密碼標準算法的地位，也為后量子密碼技術在物理安全領域的廣泛應用提供了一定的參考。

5.2 研究方向

盡管本文成功實現了Kyber算法的一階掩碼方案，并在一定程度上驗證了其對抗側信道攻擊的有效性，但仍存在幾個值得進一步探索的方向。

a.高階掩碼技術的應用：雖然本實驗已經成功實施了一階掩碼方案，但面對日益復雜的側信道攻擊技術，探索二階乃至更高階掩碼技術的集成與優化成為必然趨勢。研究應聚焦于如何高效地生成和管理高階掩碼，同時減少計算和存儲開銷，確保算法的實時性和資源效率。高階掩碼技術相比一階掩碼，提供了更高級別的安全性，能有效防御更廣泛的側信道攻擊，尤其是那些能夠利用更高階統計信息的復雜攻擊。

b.跨平臺適應性研究：為了使Kyber掩碼方案能夠在多樣化的硬件環境中廣泛應用，確保掩碼機制的泛用性和實用性，適配與優化工作至關重要，尤其是在資源受限的環境下。未來研究可以開發一套通用的接口和編譯指導原則，確保掩碼代碼能夠容易地在不同的處理器架構（如x86、ARM等）和操作系統之間移植。并且針對特定硬件特性設計對應運算加速方案，利用并行處理能力提升加解密速度。

通過這些研究，不僅能夠擴大Kyber掩碼方案的應用范圍，還能提升其在各類硬件平臺上的執行效率和能源效率，增強其實用價值和市場競爭力。

參考文獻：

[1]Lu X，Liu Y，Zhang Z，et al.Lac：Practical ring-lwe based public-key encryption with byte-level modulus[J].Cryptology ePrint Archive，2018.

[2]Seo S，Kim H.Portable and Efficient Implementation of CRYSTALS-Kyber Based on WebAssembly[J].Computer Systems Science and Engineering，2023，46（2）：2091-2107.

[3]Rajendran G，Ravi P，D’Anvers J P，et al.Pushing the limits of generic side-channel attacks on lwe-based kems-parallel pc oracle attacks on kyber kem and beyond[C]//IACR Transactions on Cryptographic Hardware and Embedded Systems，2023：418-446.

[4]Minkyu S，Junyeon L，Taeweon S，et al.RT-Sniper：A Low-Overhead Defense Mechanism Pinpointing Cache Side-Channel Attacks[J].Electronics，2021，10（22）：2748-2748.

[5]Ngo K，Dubrova E，Guo Q，et al.A side-channel attack on a masked ind-cca secure saberkem implementation[C]//IACR Transactions on Cryptographic Hardware and Embedded Systems，2021：676-707.

[6]EMPIRE TECHNOLOGY DEVELOPMENT LLC：Patent Issued for Detection of Side Channel Attacks between Virtual Machines （USPTO 9438624）[J].Journal of Engineering，2016.

[7]Marie D，Dani?l L，Christophe L.Why Psychologists Should by Default Use Welch’s t-test Instead of Student’s t-test[J].International Review of Social Psychology，2017，30（1）：92-98.

[8]Radha P A.Modeling Volatility under Normal and Student-t Distributional Assumptions（A Case Study of the Kenyan Exchange Rates）[J].American Journal of Applied Mathematics and Statistics，2014，2（4）：179-184.

[9]He S，Li H，Li F，et al.A lightweight hardware implementation of CRYSTALS-Kyber[J].Journal of Information and Intelligence， 2024，2（2）：167-176.

作者簡介：

肖旭，女，1992年生，工程師，研究方向為整車測試。