吳偉彬,劉 哲,楊 昊,張吉鵬

(南京航空航天大學 計算機科學與技術學院,江蘇 南京 211106)

密碼學是網絡安全的基石,目前業(yè)界主流的傳統(tǒng)公鑰密碼算法主要基于大整數分解問題和離散對數問題,但這兩類數學難題都已被Shor 算法在多項式時間內所攻破[1].為了應對量子計算對公鑰密碼算法的威脅,全球的密碼學者都在積極開展后量子密碼算法(post-quantum cryptography,簡稱PQC)的研究.后量子密碼在設計時,設計者必須從理論上證明該算法的安全性,但密碼算法的安全性除了需要證明理論安全以外,還需要考慮算法具體實現上的安全,即物理安全.側信道攻擊能夠利用密碼算法在密碼芯片上運行時泄露出來的側信息,分析并恢復出密鑰或加密信息,是密碼算法物理安全的主要威脅手段.

近些年,已有部分學者針對后量子密碼算法的側信道攻擊與防御開展研究現狀的調研工作,如:2016 年,Bindel 和Buchmann 等人[2]分析了基于格的簽名方案面對多種不同類型(隨機化、歸零和跳過)的一階故障攻擊,并根據對故障攻擊的分析提出了6 種不同類型攻擊相應的防御對策,但該工作的調研只限于故障攻擊;2018 年,Khalid 和Rafferty 等人[3]針對格基密碼方案中的重要組件(錯誤采樣器)進行調查研究,根據各種錯誤采樣器存在的側信道威脅,提出了錯誤采樣器的安全建議,但是,該工作只限于采樣器;2018 年,文獻[4]調查了基于格的側信道攻擊(SCA)方面的相關工作,包括入侵性攻擊和被動攻擊以及已提出的防御對策,但是該工作沒有針對攻擊點和防御代價進行分析;文獻[5]調查了多種后量子密碼方案在不同微控制器的實現效果,包括對公私鑰大小、簽名驗簽時間和加密解密時間等信息的分析,但沒有針對可能存在的側信道攻擊進行調研;又如,2018 年,文獻[6]分析了R-LWE 加密算法抵御故障攻擊的能力,并且根據攻擊點和手段的分析,提出了加強RLWE的防御對策;同年,文獻[7]就基于編碼的后量子密碼方案進行了調研,從理論安全到物理安全都進行了分析;2019 年,文獻[8]調查了基于格的密碼方案的發(fā)展情況,分析和總結了在軟件和硬件中實現格密碼的挑戰(zhàn)與建議;這些調研只針對一類或者其中一個組件進行分析,沒有針對不同類型密碼和不同側信道攻擊手段的安全性進行對比分析,因此本文針對不同類型的后量子密碼系統(tǒng)進行了調研和深入的分析.

本文針對NIST 最新公布的二輪候選后量子密碼算法和中國CACR 公鑰密碼競賽第2 輪入選算法進行了調研,分析了最新的側信道安全研究進展和防御策略,主要工作分為3 點.

(1) 將NIST 第2 輪后量子密碼的不同類型作為研究對象,同時參照中國密碼學會CACR 競賽入選的后量子算法類型,整理與歸納這些密碼現有的側信道安全性水平和可能的防御能力.

(2) 針對現有后量子側信道攻擊方法,匯總不同信道與不同方式的攻擊方法,并按照算法核心算子進行分類,給出攻擊結果的評價指標,從攻擊方法、攻擊點、攻擊評價等多個角度進行側信道攻擊的深入分析.

(3) 針對現有后量子側信道防護方法,整理不同對抗策略的應用方式,調研最易遭受攻擊的核心算子的防護策略以及現有防御策略的代價瓶頸,從安全性和防護代價兩個維度開展分析.

由于提交到NIST 中的基于超奇異同源的后量子密碼算法僅SIKE 一種算法,其研究工作目前甚少,且因為該密碼方案的性能效率較低,目前的主要研究在于加速優(yōu)化實現方面,因此本文沒有編寫關于基于超奇異同源的詳細調研.針對超奇異同源密碼系統(tǒng)的第一個錯誤攻擊是在2017 年由Ti[9]提出來的,它的攻擊方法是通過故障注入將基點變?yōu)殡S機點.在Ti 工作的基礎上,Gelin 和Wesolowski 提出了一種環(huán)中止故障攻擊,它利用了同源計算的迭代結構[10];Koziel 提出了3 種改進的精致能量分析(refined power analysis,簡稱RPA)攻擊[11],它們是基于二次可拓域的零值表示和同源算法,攻擊目標主要在于3 點蒙哥馬利梯度算法.

本文第1 節(jié)簡述后量子密碼的研究背景、安全挑戰(zhàn).第2 節(jié)～第5 節(jié)分別分析基于格、基于編碼、基于哈希、基于多變量的后量子密碼算法的側信道攻擊方法與防御策略.第6 節(jié)進行梳理和總括不同類型的后量子密碼算法的特點、攻擊手段,以及不同攻擊手段的防護策略及其防護策略的代價.最后第7 節(jié)總結全文.

1 背 景

本節(jié)主要包含兩部分:第1 部分講述后量子密碼算法的發(fā)展狀況和研究現狀;第2 部分介紹后量子密碼算法目前主要面臨的側信道攻擊手段.

1.1 后量子密碼算法

為了防止量子計算機部署后對目前的密碼系統(tǒng)造成不可逆轉的傷害,目前各國都在積極地推動后量子密碼算法PQC 標準的制定,最有代表性的是美國NIST 在2015 年開啟后量子密碼算法標準征集項目,2016 年正式開始征集算法,如今已進入第2 輪評選篩選;中國在后量子密碼標準的征集方面也做了不少工作,2019 年中國密碼管理局委托中國密碼學會(CACR)舉辦了后量子密碼算法競賽的征集,這場競賽是中國在后量子密碼算法標準制定的預賽,意味著中國也開始了后量子密碼標準的制定征程.下面分別介紹NIST 和CACR 的具體情況.

(1) 美國NIST 的PQC 征集[12]情況

NIST(National Institute of Standards and Technology)面向全球所有密碼學者征集抗量子密碼算法,以制定下一代公鑰密碼標準,在規(guī)模上,NIST 的PQC 密碼競賽是目前全球影響力最大的密碼標準征集競賽.截止2017年12 月21 日,NIST 公布共接收69 份算法,后來有5 種算法退出評選,因此在一輪評估中實際有效數只有64 份,表1 為美國NIST 后量子密碼征集情況:主要包含了NIST 一輪、二輪共接收算法數量、算法應用類型及困難類型(左邊第1 列)等;算法應用類型中PKE、KEM、SIG 分別代表公鑰加密、密鑰封裝和簽名方案.根據NIST在2020 年7 月22 日關于第3 輪候選算法的最新公布,最終PKE/KEM 候選算法4 個,候選PKE/KEM 算法5 個,最終SIG 算法3 個,候選SIG 算法3 個.

Table 1 The NIST post-quantum cryptography standardization process表1 美國NIST 后量子密碼征集情況

(2) 中國CACR 的PQC 征集[13]情況

表2 給出中國CACR 后量子密碼的征集情況.

Table 2 The CACR post-quantum cryptography design competition表2 中國CACR 后量子密碼征集情況

中國目前尚未向全球征集密碼算法,由CACR 舉辦的密碼競賽只面向國內的密碼學者,下面是CACR 在2019 年舉辦的密碼競賽情況(只關注于公鑰密碼算法,不關注對稱密碼).CACR 共收到38 份,表2 為CACR 一輪、二輪共接收的算法數量、算法應用類型及困難類型(左邊第1 列)等.算法應用類型中PKE、KEM、SIG、AKE分別代表公鑰加密、密鑰封裝、簽名和認證密鑰協(xié)商方案.

由上文NIST 和CACR 的情況可知,后量子密碼從數學難題上可分為基于格、基于編碼、基于哈希、基于多變量和基于超奇異同源等幾種主要的密碼類型.

1.2 側信道攻擊

側信道攻擊從目標密碼系統(tǒng)在平臺運行中獲取側信息,這與其他形式的密碼分析形成了對比,在其他形式的密碼分析中,一般都是攻擊算法及其底層的計算問題.所有的電子設備都會以多種方式泄露信息,側信道攻擊通過來自目標設備泄露的這些信息來查找與密鑰相關的信息,這些可能是設備內部操作的時間或功率軌跡,或者是設備產生的錯誤輸出.側信道攻擊可分為以下幾類:時間攻擊、能量分析攻擊、故障注入攻擊等.

(1) 時間攻擊(timing attack,簡稱TA)[14].密碼設備的運行時間可以構成一個信息通道,為攻擊者提供所涉及的密鑰參數的寶貴信息.在時間攻擊中,攻擊者可以根據密碼設備運算的時間推斷出所執(zhí)行的運算操作,而由這些操作即可推算出所涉及的密鑰的信息.

(2) 能量分析攻擊:密碼設備的功耗可以提供有關發(fā)生的操作和相關參數的大量信息,通過這些功耗信息可以獲取與功耗相關的操作和數據信息.

· 簡單能量分析(simple power analysis,簡稱SPA)[15].簡單能量分析是側信道能量分析攻擊中最簡單的一種攻擊,它記錄密碼系統(tǒng)設備的功率軌跡(也稱為能量跡,能量跡是指在加密操作時的一組功耗測量值),并對其進行檢查,以識別可能用于破解密碼系統(tǒng)和檢索密鑰的可見特征.

· 差分能量分析(differential power analysis,簡稱DPA)[15].比較流行和強大的能量分析攻擊是差分能量分析攻擊.DPA 不需要對加密硬件進行任何形式的物理入侵,它可以由任何對其內部工作方式(即密碼體制)有足夠了解的攻擊者實施,比如:僅了解一些密碼系統(tǒng)的實現過程而不用掌握執(zhí)行密碼算法的密碼芯片內部結構.DPA 攻擊試圖使用密碼系統(tǒng)消耗的功率與輸入數據之間的統(tǒng)計相關性來提取密鑰信息.

· 相關能量分析(correlation power analysis,簡稱CPA)[16].CPA 是基于電路的實際功耗和功耗模型之間的關系,如漢明重量模型與功耗呈線性關系,來進行分析,因為正確密鑰對應操作的功耗與中間值的漢明重量之間的相關系數會達到最大.

· 模板攻擊(template attack,簡稱TA)[17].模板攻擊是一種簡單能量分析攻擊的變體,從理論上講,這是最強的側信道攻擊形式.這種攻擊要求敵手擁有一個完全可以控制的相同設備,以建立各種操作指令的模板.

(3) 故障攻擊(fault attack,簡稱FA)[18].錯誤的計算有時是發(fā)現正確密鑰的最簡單的方法.故障攻擊(有時也稱為故障注入攻擊)是一種更強大的密碼分析技術,其原理是通過篡改設備,在加密操作期間注入一些影響加密操作的物理行為(如注入電磁、時鐘頻率、電壓等),使其執(zhí)行一些錯誤操作,利用錯誤行為的結果泄漏出涉及密鑰的信息.

2 基于格的PQC

2.1 基于格的密碼系統(tǒng)

(1) 格及格的困難問題

格是一種代數結構,n維滿秩格Λ 是Rn上的離散加法子群,具有性質spam(Λ)=Rn,它由一組基B={b0,b1,...,bn}∈Rn×n(稱為格基)生成,n維滿秩格Λ 可以表示為Λ=L(B)={Bx.x∈Zn}.

· 最短向量問題(SVP)的定義:給定格基B={b0,b1,...,bn},目的是在這組基構成的格中找到一個非零的最短向量,即找到一個向量v∈L(B),使得基于SVP 問題演變出近似版本SVPγ,對于γ＞1,給定格基找到一個非零向量v∈L(B),使得對于小的因子γ,近似的γ＞1 更困難,而對于增大的因子γ,近似的SVPγ更容易.

· 最近向量問題(CVP)的定義:給定格基B={b0,b1,...,bn}和目標向量t,目的是在這組基構成的格中找到一個最接近t的向量v∈L(B),即找到一個向量v∈L(B),使得最小.基于CVP 問題演變出近似版本CVPγ,對于γ＞1,給定格基B={b0,b1,...,bn}∈Rn×n,找到一個非零向量v∈L(B),使得其中,dist(t,L(B))為t到格L(B)的距離.

(2) 帶錯誤的學習問題

目前基于格的公鑰密碼算法和密鑰交換協(xié)議絕大部分都是基于2005 年由Regev 提出的帶錯誤的學習問題(learning with error,簡稱LWE)[19]及其變形問題來構造的.它與其他古典的格困難問題(例如SVP 和CVP)相比,LWE 問題已被證明功能更加全面.

LWE 分布的定義為n、q是正整數上的元素,χ是在? 上的一個分布,給定通過均勻隨機選擇以及從分布χ中選取整數錯誤e∈?,LWE 分布As,χ輸出(a,〈a,s〉+emodq)∈一般來說,LWE 問題分兩種.

· 搜索型LWE(search LWE,簡稱sLWE)的定義:令n、m、q是正整數的元素,χs、χe是?上的分布,給定(A,b=As+e),求秘密向量s.其中,矩陣秘密向量錯誤向量

· 判定型LWE(decisional LWE,簡稱dLWE)的定義:令n、m、q為正整數,χs、χe是?上的分布,判定下面兩個分布:D0:(A,b) 和D1:(A,u),其中,

這兩種LWE 在一定程度上是等價的,能求解sLWE 問題的方法也能求解dLWE.對于LWE 問題中的錯誤分布χ,一般都采用離散高斯分布方式.

(3) 格密碼體制分類

所有格基公鑰密碼體制的算法可以分成3 類:標準LWE(learning with error,簡稱LWE)、模LWE(module learning with error,簡稱MLWE)和環(huán)LWE(ring learning with error,簡稱RLWE).關于LWE 問題,上面已有描述;RLWE 是在2010 年由Lyubashevsky 等人[20]提出的,是基于環(huán)上帶錯誤的學習問題,其困難性等價于理想格的SVP 困難問題的最糟糕情形;MLWE 是在2015 年由Langlois 等人[21]提出的基于模上帶錯誤的學習問題,它是LWE 和RLWE 的推廣.總體而言,MLWE 比RLWE 具有更好的安全性能權衡.它們的區(qū)別可簡述為:LWE 的分布樣本分布在?上;而RLWE 的樣本分布在環(huán)上,常用的環(huán)為整數環(huán)對于MLWE 的樣本分布在特殊環(huán)上,常用的有冪次環(huán)(是環(huán)Rq的特殊情形)和安全素數環(huán).

2.2 針對格基PQC的側信道攻擊

(1) 能量分析攻擊

能量分析一直是側信道的主要攻擊手段,近幾年關于格密碼的能量分析攻擊有許多工作,如:2016 年,Pessl針對文獻[22]提出的隨機洗牌策略進行安全分析,然后針對隨機洗牌防護策略的高斯采樣提出了一種新的SPA攻擊[23];2017 年,Huang 等人[24]針對受掩碼保護的格密碼中的核心算子NTT 實施了單能量跡攻擊,是第一個針對格密碼的單能量攻擊,該攻擊適用于大部分格密碼算法;2018 年,Kim 和Hong 針對FrodoKEM 方案中的高斯抽樣提出單能量跡攻擊方案[25],這是首個針對高斯采樣的單能量攻擊;2019 年,文獻[26]的作者Pessl 和Primas等人也針對KYBER 中的NTT 提出了單能量跡攻擊方案,并且還提出了3 種提高攻擊效率和成功率的方法;2020 年,Huang 和Chen 等人[27]針對NTRU Prime 算法中的多項式乘法提出了4 種能量分析方法,主要針對不同版本的NTRU Prime 算法的實現(如:參考實現、優(yōu)化實現和保護實現);2020 年,Ravi 等人[28]針對Round5、LAC、Kyber、Frodo、NewHope 等多種格密碼算法進行了選擇密文攻擊,其主要攻擊目標是糾錯碼和FO 變換.

針對格基PQC 的能量分析攻擊大多基于密鑰系數與功耗之間的關系.下面簡單描述針對格基密碼的側信道攻擊原理及過程.以文獻[28]針對Round5 算法的攻擊方法為例:該方法的攻擊目標是針對XEf 糾錯碼,它們找到XEf 糾錯碼的泄漏點:在XEf 解碼過程中的恢復消息步驟涉及到翻轉比特位置的決策操作,在決策操作中包含了一個多位邏輯運算的計算操作,該操作也是解碼操作決策是否糾錯的最后一步,記該操作為M.M的輸入是寄存器集r的修改形式,標記為re?,經過大量實驗得出:若碼字c合法,則re＇=0;若碼字c帶有一個或多個錯誤位,則re＇≠0.通過收集的電磁波可以很明顯地檢測出c=0 和c=1 兩種情況下內部通用寄存器值的差異(計算時同一時刻的比較).利用上述泄漏點進行攻擊的核心思路是:攻擊者通過精心選擇解密過程的密文,使其產生的碼字可以唯一地識別某個目標密鑰系數的值.攻擊的大概過程是:由這些選定的密文觸發(fā)解封裝操作,隨后使用Welch’s t-test 聚類技術對電磁波進行分析,揭示了密鑰s中某個系數的值.重復這一過程以實現全密鑰的恢復.

格基PQC 的能量分析攻擊成功率大部分都超過90%,且分析時間也較短.如在上述文獻[24]中,無論針對無掩碼的NTT,還是帶掩碼防護的NTT,其攻擊結果都顯示:當噪聲小于0.4 時,兩者的成功率基本上都能維持在80%～95%之間.文獻[26]提出了一種利用Belief Propagation 方法改善的單能量攻擊,針對恒定時間實現但無掩碼的NTT 實現,改良后的攻擊方案可以在噪聲的漢明重量為1.5 的條件下,其成功率維持在90%以上(對于基礎版的攻擊方案,當最高噪聲的漢明重量大于0.9 時,其成功率驟降);而針對帶掩碼實現的NTT,單獨使用belief propagation 方法的攻擊成功率依然很低(當噪聲漢明重量為0.9 以上時,成功率小于40%),不過,針對掩碼實現的NTT 應用了一種其他方法,使得在漢明重量小于0.3 時,成功率依然接近1,針對采用Lazy Reduction 實現的NTT,它們的攻擊在噪聲漢明重量小于1.3 時,成功率保持在90%以上;文獻[28]針對Round5 的攻擊大概需要978 條能量跡,成功率為99%,一次完整的攻擊迭代需要95s(包括10s 的預處理時間),3 輪總共270s,即4.5 分鐘完成密鑰恢復;針對LAC128 的選擇密文攻擊,需要2×512=1024 條能量跡,平均成功率為98%,一次迭代用時約525s(8.75 分鐘),完整密鑰恢復用時為1 490s(3 次重復用時≈25 分鐘);針對Kebey512 的FO 變換的攻擊大概需要5×256×2=2560 個能量跡(n=256,k=2)就能檢索出完整密鑰,在約3 次攻擊的重復操作情況下,恢復出完整密鑰的平均成功率約為99%,一次完整的重復攻擊(包括能量跡獲取)大約需要230s,因此,密鑰的完全恢復可以在650s 內完成(在10.83 分鐘內進行3 次迭代).

(2) 故障攻擊

故障攻擊是一種強有力的攻擊手段,也一直備受關注,針對格密碼的故障攻擊一直處于熱潮.如2018 年Bruinderink 和Pessl 等人[29]針對qTESLA、Dilithium 兩種密碼算法提出了差分故障攻擊;2019 年,Ravi 和Roy等人[30]針對NewHope、KYBER、Frodo 等多個不同密碼方案中高斯分布/中心二項式的nonce 隨機種子提出了故障攻擊方案;McCarthy 和Howe 等人[31]針對FALCON 密碼算法提出了故障攻擊方案;Valencia 等人在文獻[32]中提出針對后量子密碼的故障敏感度分析,攻擊點在于乘法器、加法器,其原理是利用了設備處理的數據與設備對故障的敏感性之間的相關性.

針對格密碼的故障攻擊一般在密碼算法運行時注入故障誘導隨機種子nonce 復用,從而促使算法計算出錯誤結果.下面簡述一下其中的故障攻擊原理[30],以NewHope KEM 方案中密鑰生成過程為例,構成公鑰的主要元素b是由密鑰s和錯誤e經過多項式乘法得到(在NTT 域上的運算),生成s和e采樣的唯一區(qū)別是nonce 的不同(即:noiseseed 都一樣,s的nonce 為0,e的nonce 為1).假設加密方案中Ring-LWE 的實例為b=a×s+e∈Rq,上面的方程是環(huán)上的一個由n個方程(2n個未知數)所構成的線性方程組(每個多項式都有n個系數,s、e為未知量,因此有2n個未知量).因此,當攻擊者注入故障(利用電磁故障注入讓nonce 跳過更新,保持原來的值)使得s和e都使用同一個種子,也就是nonce 一樣,那么上面方程就變成b=a×s+s∈Rq,這個有缺陷的LWE 實例是一個由n個方程(n個未知數)所構成的線性方程組(每個多項式都有n個系數),因此這可以使用高斯消元法很簡單地求解出私鑰s.

故障攻擊的攻擊效果主要取決于注入的故障數和注入成功率.如在文獻[29]中,在Keccak-f 最后一次(下面記為1P)和倒數第2 次(下面記為2P)調用的平均注射故障數為39 和93;而在矩陣A的生成、隨機種子采樣(1P/2P)、多項式乘法和哈希等不同地方注入故障的成功率分別為54.4%、24.8%/23.9%、25%～90%、91%.文獻[30]實現了精確地注入故障,即百分百成功,因此其復雜度可以轉換為注入故障數,在FRODO 和NEWHOPE兩種方案中,恢復密鑰和消息分別只需注入1 個故障;而對于MLWE 類型的密碼方案(如Kyber 和Dilithium)所需要的故障的數量為矩陣A的維度.

(3) 其他攻擊

能量分析攻擊和故障攻擊是針對格的側信道攻擊的兩種主要攻擊手段,但也存在其他類型的側信道攻擊手段,如時間攻擊、冷啟動攻擊等.2018 年,Albrecht 和Deo 等人[33]針對Kyber 和Newhope 中的NTT 進行了冷啟動攻擊(cold boot attacks);2019 年,D’Anvers 和Tiepelt 等人[34]針對LAC、Ramstake 兩種算法的糾錯碼提出了時間攻擊方案;Espitau 和Fouque 等人[35]針對BLISS 方案中的拒絕采樣、高斯采樣、多項式乘法等多個核心算子進行攻擊.

針對格密碼的時間攻擊的效率較高,而其他類型攻擊的效果與攻擊方法和攻擊點相關.如文獻[34]針對LAC 中的糾錯碼進行時間攻擊需要大約2 400 個能量跡,在2 分鐘內可恢復全部密鑰(在Intel(R) Core(TM)i5-6500 CPU,3.20GHz 平臺下).文獻[35]的攻擊效果雖然針對拒絕采樣的攻擊效率較低,n=256 和n=512 的BLISS 算法中拒絕采樣的攻擊時間分別為17 個小時(247個時鐘周期)和38 天(253個時鐘周期),但對于高斯采樣,恢復出完整密鑰的成功率為95%,針對多項式乘法,當噪聲標準差在3.0 及以下時,單解的平均時間在10ms 以下.

綜上所述,格密碼中涉及密鑰相關的核心操作主要有多項式乘法、NTT(用于加速多項式乘法操作的一種方法)、高斯分布采樣、中心二項式采樣、糾錯碼以及易受故障攻擊的隨機種子產生過程,在這些核心操作計算過程中,均會涉及到私鑰或消息等關鍵信息.在不同格基密碼方案中,多項式乘法操作和NTT 操作不一定是共存的,如LAC 只有稀疏多項式乘法;在基于格的qTESLA 簽名方案中,稀疏多項式乘法和NTT 都存在.而高斯分布采樣和中心二項式采樣用于密鑰多項式、噪聲多項式的產生,高斯分布采樣相對于中心二項式采樣精度更高,但較耗時,因此,除格基簽名方案以外,其他密碼方案基本都采用了中心二項式采樣來替代高斯分布;糾錯碼用于降低格基密碼的解密錯誤失敗率.圖1 所示為格基后量子密碼的近3 年攻擊分析圖,從圖中可以清楚地看到,針對后量子密碼的主要攻擊手段為故障攻擊和能量分析攻擊,從攻擊點來說,主要分布在格密碼的各個核心算子,包括NTT、多項式乘法、糾錯碼、隨機種子等.

Fig.1 Side-channel attack analysis of lattice-based PQC圖1 格基PQC 的側信道攻擊分析圖

2.3 側信道防御策略

隱藏、掩碼和檢測技術是預防側信道攻擊的有效防御策略,下面簡述近幾年的防御策略研究工作,分別對能量分析、故障攻擊和時間攻擊的防御工作進行介紹.

(1) 能量分析的防御工作

針對能量分析的防護手段主要是隨機化和掩碼.如在2014 年,Roy 等人[36]針對高斯采樣提出了隨機洗牌的防御策略;在2018 年,Oder 等人[37]提出一種掩碼實現的二項式采樣器,該采樣器可用于隨機錯誤變量e的生成;在2019 年,Pessl 和Primas 等人[26]針對NTT 進行能量分析攻擊,然后推薦使用隨機洗牌的方法作為防護對策;而在掩碼防御策略上,2015 年,Reparaz 等人[38]提出布爾掩碼的RLWE 解密實現;在2016 年,他們又使用加性掩蔽來確保RLWE 實現[39]的安全性,同時指出該掩蔽方案可通用于其他加法同態(tài)的加密方案;又如2018 年,Barthe 等人[40]利用算術掩碼與布爾掩碼的轉換技術提出了一種可證明的任意階安全采樣器,并且實現了帶掩碼的GLP 方案.

不同防護手段的防護代價和防護效果差距較大,掩碼的安全性更高,但代價高于其他防護策略.在文獻[37]中,通過加隱藏策略來保護錯誤多項式的采樣,根據實驗結果分析,CCA-2 安全的解密過程一共增加了226 476個時鐘周期(無掩碼版本),其中沒有使用隱藏策略時需要消耗4 416 918 個時鐘周期數;而在掩碼實現的采樣器中,增加隱藏策略的保護采樣器在解密過程中一共增加了305 887 個時鐘周期,其中沒有使用隱藏策略時所耗時鐘周期數為25 334 493(隱藏技術增加了1.21%的代價).文獻[38]采用并行掩碼譯碼器只需要1/2×n×N個周期,如在n=256,N=16的情況下,掩碼解碼器需要2 048 個周期,而整個掩碼解密操作總共需要7 478 個周期,無保護的解密操作大概需要2 800 個周期,掩碼加密的時鐘周期同比增長率為167%.2016 年,Reparaz 等人[39]與他們在2015 年的相關工作[38]進行了對比,在對前兩步的等式可以采用離線計算方式以及在實現的便捷性(如:采用掩碼表實現)上得到了改進.文獻[40]所提出的掩碼方案與無防護的實現方案相比,在d-probing 模型中,當d=2,3,4,5,6 時,耗時分別為8.15、16.4、393.5、62.1、111(s),分別同比增長15、30、73、115、206 倍(其中,無保護實現的耗時為0.540s).

(2) 故障攻擊的防御工作

對于故障攻擊的防護手段主要是隨機化和增加故障監(jiān)測機制.如在2016 年,Bindel 等人[2]討論了各種故障攻擊方案及對策,然后提出了應對隨機化故障的對策.包括增加輸入密鑰的大小和計算多項式的逆;Espitau 等人[41]提出了幾種可能的故障攻擊,并討論了減輕這些攻擊的可能對策;2018 年,Bruinderink 等人[29]提出了3 種針對故障攻擊的通用對策:a) 簽名的重新計算;b) 簽名后再進行驗證簽名;c) 在簽名時增加隨機性;2019 年,Howe等人[42]針對故障攻擊也提出了3 種不同的對策:a) 低代價對策:計算寄存器相同值的重復次數;b) 檢驗輸出分布的均值與方差;c) 進行卡方檢驗.

不同防護機制的有效防護點和所需代價有一定的差別.如在文獻[5]提出的3 種方案中,簽名的重新計算方案無法保護生成矩陣的種子產生過程;而簽名后進行驗證簽名方案不能保護隨機種子采樣;但在簽名時增加隨機性這種方案可以做到他文中所有攻擊點的保護.文獻[7]提出的3 種防御策略分別對應低代價、標準、高代價這3 個版本,低代價的防御策略需要36 個Slices(額外增加了8%的代價,在無保護的高斯采樣中需要33 個Slices),標準防御策略需要55 個Slices(額外增加了44%),而高代價的防御策略雖然安全性上較高但非常影響性能,該策略額外增加了126 個Slices(額外增加了3.8 倍).

(3) 時間攻擊的防御工作

針對時間攻擊的防御對策主要是算法的恒定時間實現,從而減少運行時間維度泄露的信息.針對時間攻擊常利用的攻擊點,主要有以下研究工作:2016 年,Khalid 和Howe 等人[43]提出了基于FPGA 的適用于大范圍離散高斯采樣器的恒定時間硬件實現;2017 年,Micciancio 和Michael 也提出了高斯采樣的恒定時間實現方案[44],他們的思想是將標準差較小的樣本與標準差較大的樣本相結合;2018 年,Karmakar 等人[45]也提出了新的高斯采樣恒定時間實現方案,它們將采樣器的輸出值表示為輸入位的布爾函數,從而實現了完全恒定時間的采樣算法;但是高斯采樣在性能上表現不佳,這一缺點一直是高斯采樣的短板,為了彌補這一缺陷,2019 年,Karmakar 等人[46]利用優(yōu)化了的位切片,實現了加速采樣;除了高斯采樣外,在其他核心算子的防御策略上也有部分研究工作,如2019 年,Barthe 等人[47]針對BLISS 簽名算法提出了抗時間攻擊的防御方案;2019 年,Walters 和Roy 實現了恒定時間的BCH 糾錯碼[48],并應用于LAC.

針對格密碼核心算子的恒定時間實現的代價都小于0.5 倍這一特性,有些恒定實現的性能還比非恒定時間實現的版本要高.文獻[47]利用SUPERCOP 測試工具得出:無論在低四分位數、中位數和高四分位數的開銷均在220 個時鐘周期左右(基本與非恒定時間實現的原BLISS 算法的性能一致),而對于Dilithium 算法中恒定時間實現的高斯采樣參考實現版本的性能最高比他們的實現慢5.8 倍(需要1 526 個時鐘周期),Dilithium 算法的恒定時間高斯采樣的AVX2 實現除低四分位采樣會比他們的實現快之外,中位數和高四分位數性能比他們的實現都要慢0.5 倍～1 倍.文獻[45]提出來的恒定時間高斯采樣算法的效率遠高于恒定時間的CDT 高斯采樣算法,如:在不包含偽隨機數發(fā)生器時,要產生64 個高斯樣本,CDT 算法大概需要28 231 個時鐘周期(精度參數λ=128),而他們的高斯采樣算法只需要11 814 個時鐘周期,同比減少了58%,并且,他們還實現了SIMD 版本的采樣器,產生256 個樣本只需要19 605 個周期(精度參數λ=128).文獻[46]利用位切片來提升高斯采樣的效率,與最快的非恒定時間實現的CDT 算法相比,他們的算法在最差情況下性能下降33%(最快非恒定時間的字節(jié)掃描CDT 算法每秒可以簽名10 327 次,他們的算法在同安全級別下每秒可簽名7 025 次);與普通的非恒定時間CDT采樣算法相比,最差情況下,性能下降13%;但與恒定時間的線性搜索CDT 算法相比,他們的性能可以提升15%以上;與上述工作[45]相比,他們在標準差為6.155 43 時,性能提升了11%;但在標準差為2 時,該算法的性能最高可以提升37%.

根據上述不同側信道攻擊手段的防御策略和攻擊點,梳理出一幅分析圖,如圖2 所示,從近幾年格密碼的防護分析圖中可以清楚地看到,單獨針對NTT 和糾錯碼的防護工作較少;針對高斯采樣的防護工作最為豐富,從時間攻擊到故障攻擊,再到能量分析攻擊的防護策略均有較多的研究工作;同時也有許多針對整個密碼方案(如加解密或者簽名)以實現防護策略的研究.

Fig.2 Side-channel defense analysis of lattice-based PQC圖2 格基PQC 的側信道防御分析圖

3 基于編碼的PQC

3.1 基于編碼的密碼系統(tǒng)

McEliece 于1978 年推出了第一個基于編碼的密碼系統(tǒng)[49].該系統(tǒng)不是基于數論原語,而是來自編碼理論的難題.它的安全性依賴于兩個問題:(a) 校驗子解碼問題的難度;(b) 區(qū)分二進制Goppa 碼和隨機線性碼的難度.與其他PKC 相比,McEliece 的方案具有這樣一個優(yōu)勢:加密和解密的復雜度和對稱密碼一樣,具有非常高效的性能[50].此外,解決校驗解碼問題的最佳攻擊是碼長指數型,所以McEliece 方案具有較高的潛在優(yōu)勢.

(1) 編碼的基本原理

本節(jié)主要簡述如何利用編碼理論為PKC 提供有效的解決方案,即簡述編碼的基本原理.若需要了解更多編碼理論,可參考文獻[51].

(a) 循環(huán)矩陣(circulant matrix):令向量則向量v生成的循環(huán)矩陣為rot(v)=所以兩個向量u,v∈R的乘積rot(·) 可以表示為rot(u)T=v·u.

(b) 線性編碼(linear code):[n,k]-線性碼C表示一個長度為n、維數為k的線性碼,則[n,k]-線性碼C是k維R上的一個子空間,我們將C的元素稱為碼字.線性碼的目的是檢測和糾正錯誤.

(c) 對偶碼(dual code):碼字C的對偶C⊥是指的向量子空間的正交補空間.

(d) 矩陣生成器(generator matrix):如果滿足碼字則稱G是[n,k]-線性碼C的矩陣生成器.

(e) 奇偶校驗矩陣(parity-check matrix):給定一個[n,k]-線性碼n,若滿足或因此,C的一個校驗矩陣H就是C⊥的一個(n-k)×n的生成矩陣.

(g) 最短距離(minimum distance):令C是R上的[n,k]-線性碼,ω是R的范數.那么C的最短距離為d=(目前基于編碼的后量子密碼算法使用的距離為漢明距離或秩距離).

(2) 困難問題

基于編碼的密碼系統(tǒng)的困難問題大多都基于解碼問題的變體,它包括尋找與給定向量最接近的碼字.而當處理線性碼時,接收向量的校驗子與接收向量這兩者的解碼問題一樣,因此下面只簡述校驗子解碼(syndrome decoding,簡稱SD).

(a) 校驗子分布(SD distribution):對于正整數n、k、w的SD(n,k,w)分布為:隨機挑選和滿足ω(x)=w的,然后輸出(H,σ(x)=HxT).

(b) 校驗子解碼問題(syndrome decoding problem,簡稱SDP):已知矩陣和一個整數w＞0,求一個距離ω(x)小于w的向量使得HxT=s.注:表示所有在上的(n-k)×n矩陣.

下面是校驗子解碼問題的兩個變種:搜索型SDP 和決策性SDP.

(c) 搜索型SDP(search SD problem):給定求向量使得HxT=yT且ω(x)=w.

(d) 決策型SDP(decision SD problem):給定判斷(H,yT) 是否滿足SD (n ,k ,w) 分布,或者均勻分布于

3.2 針對編碼PQC的側信道攻擊

(1) 能量分析攻擊

本節(jié)簡述近幾年能量分析對編碼PQC 的影響.Von 等人[52]在2014 年提出了基于QC-MDPC McEliece 密碼系統(tǒng)的簡單能量攻擊,實現了消息恢復攻擊和私鑰恢復攻擊.他們根據在密鑰生成時是否執(zhí)行條件轉移指令,可以觀察到不同的功耗模式,依此得出密鑰的相關信息.然后,他們還為此提出了一個使用ARM Thumb-2 匯編語言的恒定時間實現的防御對策,更具體地說,他們采用了掩碼方案,該掩碼值要么是0,要么所有的位都是1,并采用邏輯AND 指令來選擇要使用的數據,最終實現抵御攻擊.Chen 等人[53]在2015 年提出了針對QC-MDPC McEliece 密碼系統(tǒng)的水平差分能量攻擊,它在解密時通過選擇密文進行DPA 攻擊,從而實現密鑰恢復.同時還提出了一個基于布爾掩碼的閾值實現的防御對策[54].在2016 年,Chou 提出了一種基于QC-MDPC 編碼的恒定時間實現[55],以抵御定時攻擊.隨后,在2017 年,Rossi 等人[56]在CHES 2017 上表示這種對策容易受到差分功率分析(DPA)的攻擊,但是他們所提出的DPA 仍然不能完全恢復密鑰,需要進一步求解線性方程才能獲得完整的密鑰信息.因此,在2019 年,Sim 等人[57]提出了一種能夠完全恢復密鑰的多能量跡攻擊,與Rossi 等人的攻擊相比,該攻擊使用多個能量跡來恢復整個密鑰,解決了需要額外求解線性方程的問題.

針對基于編碼的后量子密碼算法的能量分析可通過校驗子H的相關計算作為攻擊點.如文獻[56]的攻擊思路.Rossi 等人提出的DPA 攻擊主要攻擊點為比特翻轉函數.它的泄露點在于其中,是私鑰.由解密算法可知,v=(c|0),因此,該結果可以表示為因為該公式中的乘法可以通過計算旋轉(即XOR 操作)后的密文來實現,并且在循環(huán)中,每個旋轉后的向量在計算時存儲到臨時內存位置,本輪XOR 結果為即前一次迭代的XOR 結果作為本次迭代XOR 操作的一部分.因此通過側通道分析模型假設設備的功耗取決于存儲在內存中的每個旋轉向量的最左位(位位置0)是0 還是1.注:c的第xi位被旋轉到第0 位,并被旋轉到第1 位,然后先利用中間值Si把能量跡T分成兩個集合(對應于0 和1),然后計算這兩個集合的均值并得到差異曲線,若在不同的地方有大的尖峰,表明有信息泄露,即窮搜64 種可能的xi.到此只能恢復出H0,完整私鑰為H=H0|H1.下面簡述如何利用H0恢復出完整密鑰,因為公鑰設Q=P-1,那么Q利用H可表示為矩陣H0和H1可以用矩陣的第1行h0和h1分別表示,因此可表示為其中,Q可計算得到,且h0已知,因此利用線性方程可以解出h1.

較短時間和少量的能量跡即可滿足針對基于編碼的能量分析.文獻[56]提出的DPA 攻擊,可以實現100%的攻擊成功率,并且在性能上恢復完整密鑰最多不超過10 000 次迭代.在時間上,當搜索空間長度為8 時,128bit 安全大概需要2s;當搜索空間長度為16 時,攻擊128bit 安全大概需要4 分鐘,迭代長度意味著DPA 分析的精度.文獻[57]提出的多能量跡攻擊結果表明,該攻擊方法在32bit 處理器上大約只需50 條能量跡即可滿足攻擊80bit安全的校驗子計算.

(2) 時間攻擊及其他攻擊

2008 年,Strenzke 等人[58]針對使用Goppa 編碼的McEliece 解密過程提出了時間攻擊,在2018 年,Eaton 和Lequesne 等人在文獻[59]中提出針對后量子密碼算法QC-MDPC 方案進行時間攻擊,引入了稀疏向量的距離譜的概念,并證明了距離譜足以恢復出向量,他們的思路是通過觀察許多錯誤的明文,恢復出QC-MDPC 密鑰的距離譜;Paiva 和Terada 在文獻[60]中針對非恒定時間實現的HQC 方案也提出了時間攻擊方法,攻擊的原理是非恒定時間實現的HQC 的解密時間取決于BCH 糾錯碼中的錯誤數量;根據非恒定時間實現的BCH 糾錯碼來實現時間攻擊的還有2019 年由Wafo-Tapa 等人[61]針對HQC 提出的選擇密文時間攻擊方案,該方案利用了解碼錯誤的權重與BCH 碼解碼算法的運行時間之間的相關性;2020 年3 月,Danner 和Kreuzer 也提出了針對使用二進制不可約的Goppa 碼的故障攻擊[62],該攻擊可在25 分鐘內攻破最高級別的安全參數.

時間攻擊最主要的原理是非恒定時間實現的算法會因操作不同的數據而泄露出關鍵信息.下面舉例說明針對非恒定時間的HQC 攻擊方法[60].整個攻擊方案分為兩步:頻譜恢復和密鑰重構.頻譜恢復是使用時間信息的部分.為了方便描述其過程,這里假設Alice 是持有密鑰的目標設備.下面是頻譜恢復的大概過程.

1) 攻擊者發(fā)送許多合法密文給Alice,然后記錄Alice 對每條密文解密的時間信息.

2) 因為所有密文都是攻擊者產生的,因此攻擊者知道r1和r2.攻擊者利用頻譜恢復算法迭代地構建兩個數組Tx和Ty,使得Tx[d](Ty[d])是d在r2(r1)頻譜內的解密時間的平均值.

3) 獲得最短距離k:Ty[k]為數組中最小值.

4) 利用Paiva 等人提出的BuildD 算法,從Ty中分離出不在x頻譜內的距離集合D.

密鑰重構是利用上面獲得的信息來計算私鑰中的y:由上述步驟得到集合D和在頻譜內的距離k,然后再利用密鑰重構算法恢復出y,對于這一算法此處不再詳述,因為該算法是Guo 等人[28]提出的密鑰重構算法的一個簡單擴展版.

針對編碼的后量子密碼算法的時間攻擊所需解密次數較多,而故障攻擊的注入成功率遠低于一些針對格密碼的故障攻擊的成功率.文獻[60]指出,針對非恒定時間BCH 糾錯碼的時間攻擊大約需要4 億次解密才可能實現密鑰重建,若解密次數在6 億次以上,則幾乎光譜之外的所有距離都能被正確識別.文獻[61]共發(fā)動了1 000次攻擊,結果顯示,大概有88%的成功率,在復雜度上,針對128bit、192bit、256bit 這3 個不同的安全級別HQC的攻擊,所需要的解碼數分別為5 441、5 852、6 631.文獻[62]針對Goppa 碼的故障攻擊,注入故障的成功率在50%以下,并且,隨著算法安全級別的提高,他們的注入故障成功率也會明顯下降;在攻擊所需消耗時間方面,對于128bit 安全級別的攻擊大概需要170s;針對192bit 安全級別的攻擊大概需要566s,對于最高安全級別的攻擊也只需1 451s(約25 分鐘).

3.3 側信道防御策略

近幾年,由于編碼PQC 的側信道防護工作相對格密碼較少,因此這里不再細分攻擊類型的防護策略.在2008 年發(fā)表的文獻[58]中,從密文排列角度出發(fā),提出了一種對高速緩存的時間攻擊,之后,Strenzke 等人又提出了一種基于地址掩蔽的對策,但隨后在2016 年,該對策遭到Petrvalsky 等人[63]提出的DPA 的攻擊.而第一個基于準循環(huán)低密度校驗碼(QC-MDPC)的能量分析是在2015 年,由Chen 等人[53]提出,該攻擊針對的是在硬件實現上為QC-MDPC 碼校驗子計算(利用了選擇單密文攻擊).之后,Chen 等人為此提出了一個對策[54],使用與校驗矩陣大小相同的布爾掩蔽;同年,他們繼續(xù)針對原來的對策方案進行了擴展[64],主要包括在密鑰和校驗子上應用掩蔽的對策,Chen 等人通過在校驗子的計算和解碼部分使用閾值來避免一階側通道攻擊.2016 年,Chou 等人提出了一種基于準循環(huán)低密度校驗(QC-MDPC)的基于密碼的固定時間實現[55],以抵御時間攻擊,但于2017 年,該方案受到了Rossi 等人提出的差分功率分析的攻擊[56],該攻擊方案利用了校驗子的計算不是以向量矩陣積的形式進行而是以排他或旋轉之間的形式來描述校驗矩陣這一特征,因此相應的對策是在進行校驗子計算之前用隨機碼字對密文進行掩碼,這是之前在2016 年由Petrvalsky 等人提出的保護對策[63],該方法利用線性碼的特性,不需要大量的隨機比特,有利于低成本的嵌入式設備.2019 年,Wafo-Tapa 等人[61]針對采用非恒定時間實現的BCH 糾錯碼的HQC 提出的選擇密文時間攻擊方案,提出了恒定時間實現的BCH 糾錯碼;2020 年,Danner 和Kreuzer[62]針對使用二進制不可約的Goppa 碼提出了故障攻擊,之后又提出了兩種防御策略,其一是通過檢查解碼后輸出值的權重來發(fā)現故障注入;其二是給出檢測故障注入的另一種方法——重新加密輸出.

針對基于編碼的掩碼實現效率較低,所需額外開銷較大這一問題,文獻[54]對校驗矩陣實現了掩碼防護,該掩碼防護對策與無保護方案相比,總體上增加了8 倍的資源;在Flip-Flops(FFs)、Look-Up Tables(LUTs)、Slices等方面分別為3 045、4 672、1 549,而無保護方案分別為412、568、148,同比增長了7.4 倍、8.2 倍、10.5 倍.

4 基于哈希的PQC

4.1 基于哈希的密碼系統(tǒng)

基于哈希(散列)的密碼方案是后量子密碼學中重要的一類,它以僅使用密碼哈希函數創(chuàng)建數字簽名而聞名.進入NIST 二輪的哈希密碼方案只有SPHINCS+簽名方案.這種方案的主要優(yōu)點是其安全性僅依賴于泛型哈希函數的某些加密屬性.因此,如果所選的哈希函數在將來被攻破,則可用新的哈希函數替換被攻破的哈希函數.下面對如何基于哈希構造數字簽名作一簡單介紹.

最早利用哈希函數構建的數字簽名算法是Lamport 在1979 年提出來的[65],但是,該算法容易被使用兩個已正確的簽名偽造出另一個偽簽名,且該算法的簽名和密鑰都太大,因此,受Lamport 啟發(fā),Merkle 根據Winternitz的一個猜想提出了一個一次性簽名WOTS(Winternitz-one-time signature)[66],它由3 個值參數化.

*ω:WOTS 使用的字的大小;

* ?1:待簽名消息的字(大小為ω)的字數量;

* ?2:簽名算法中校驗值(大小為ω)的字數量.

給定一個安全級別參數n、哈希函數和一個隨機位掩碼集合則鏈接函數(chaining function)的ci(x,r)定義為

簽名后的長度為?=?1+?2,ω和W的關系是ω=2W.其中,

在Lamport 提出簽名方案40 年后,出現了第一個后量子簽名方案——XMSS 方案[67],但是由于XMSS 簽名方案是一種有狀態(tài)的簽名方案,也恰恰是因為這一缺陷,使得它不滿足 NIST 對簽名方案的標準定義;而后,Daniel 等人提出了無狀態(tài)的基于哈希的簽名方案——SPHINCS,SPHINCS 方案里用了許多XMSS 的組件,但為了消除狀態(tài),使用了較大的密鑰和簽名;進入NIST 二輪候選的SPHINCS+簽名方案與SPHINCS 類似,是Daniel 等人基于SPHINCS 進行了修改和改善的方案,提高了安全性和魯棒性,但都使用上述的WOTS 基礎概念,而WOTS 與密鑰長度和安全級別息息相關,如SPHINCS-256 的參數為:安全級別n=256,字大小ω=24=16bit;消息字數量 ?1=64,校驗碼字數量 ?2=3;SPHINCS+簽名方案對上述WOTS 參數進行輕微的修改和定制,命名為WOTS+.在WOTS+中,主要定義了兩個參數n和ω.在WOTS+中,ω={4,16,256},是安全參數,影響著消息、私鑰、公鑰的長度,簽名后的長度?=?1+?2也有所變化,長度如下:鏈接函數的作用是利用WOTS+和公鑰來計算每輪迭代,即計算哈希鏈.

4.2 針對哈希PQC的側信道攻擊

近年來,基于哈希的后量子密碼算法的側信道攻擊研究工作較少,因此這里不再細分攻擊類型.2017 年,Genêt 在其碩士論文[68]中提出了針對SPHINCS 算法的簡單能量攻擊、差分能量攻擊和故障攻擊方法;2018 年,Castelnovi 等人[69]首次提出了針對SPHINCS、GRAVITY-SPHINCS 和SPHINCS+等算法的底層框架的故障攻擊,它允許創(chuàng)建適用于所有NIST 一輪候選算法(XMSS、LMS、SPHINCS+和Gravity-SPHINCS)的通用簽名偽造.同年,Genêt 等人[70]針對SPHINCS 密碼算法也提出了故障攻擊方案,并且在文獻[71]中針對SHA-2 和BLAKE-256 兩種哈希算法提出了差分能量攻擊方案,且將該攻擊應用于XMSS、BLAKE、SPHINCS 等方案.

針對基于哈希的后量子密碼的故障攻擊主要目的是迫使底層OTS 被重用.下面簡述文獻[70]中的攻擊方法.首先,攻擊者必須能夠對消息M進行簽名以獲得有效的簽名.如果重新簽名相同的消息M,該方案將生成相同的簽名以及完全相同的超樹路徑.但是,如果在構造任何子樹(非樹根)0≤i＜d-1的過程中發(fā)生錯誤,算法將輸出不同的簽名.對已知子樹的簽名進行偽造.對M的簽名進行剪修偽造,只需修改某個子樹,其他部分均為原來正確的子樹.如圖3 所示(圖3 來源于文獻[70]):左邊的圖片顯示了一個消息M正在與一個SPHINCS 超樹簽名,而高亮顯示的子樹正在受到攻擊.在右側,超樹在這個子樹處被切割,并與一個偽造子樹的分支進行嫁接,這一步是使用注入電壓故障的方式來讓底層的FTS 得到重用,從而實現對任意消息M＇進行簽名.最后,當故障攻擊迫使底層的OTS(FTS)被重用時,利用Genêt 等人提出的處理算法來識別錯誤簽名中的WOTS 密鑰值(使用WOTS 實例的公鑰,可以通過猜測損壞的子樹根的所有塊來識別密鑰值).

基于哈希的后量子密碼算法的側信道攻擊可通過少量錯誤簽名即可完成簽名偽造.文獻[69]的實驗結果表明,僅需要收集3 條錯誤簽名就可以實現GRAVITY-SPHINCS 的偽造簽名,而偽造代價是大約220個哈希計算.同時,如果擁有更多的錯誤簽名數量,那么所消耗的計算代價將會更低.如當擁有10 個時,所需代價僅為25.5個哈希計算,而當擁有20 個時,僅需4 個哈希計算.文獻[70]指出,若給定8 個錯誤簽名,攻擊者就可以在64 次嘗試內擁有超過30%的偽造成功率;如果給定15 個錯誤簽名,那么攻擊者可以在35 次嘗試內即可擁有超過90%的偽造成功率.文獻[71]所做的差分能量分析共需要收集10 000 條能量跡,猜測計算值的空間大概為216.

4.3 側信道防御策略

基于哈希的后量子密碼的側信道防御策略研究工作主要如下:2018 年,Kannwischer 等人在文獻[71]中通過對基于狀態(tài)哈希的XMSS、SPHINCS 等簽名方案進行分析,提出了一種基于SHA2 的偽隨機數發(fā)生器的新型差分能量分析方法,并建議使用隱藏技術來作為抵御策略,利用對混合過程的隱藏來減少相關性,使得它們的執(zhí)行順序隨機排列,迫使攻擊者對收集到的能量跡進行同步對齊,從而增加了DPA 的復雜性.而在文獻[69]中,Castelnovi 等人針對SPHINCS 提出了故障攻擊,并且也指出可使簽名計算冗余,使攻擊復雜化,但這種方式會帶來巨大的開銷(時間和空間上).他們還推薦了一種有效的對策:以某種方式將超樹的不同層連接起來,如此,計算樹的錯誤將導致一個無效的簽名,即一個與公鑰不同的根值.除此之外,文獻[72]也提出了一種特殊的重新計算方法,旨在避免Merkle 樹中的錯誤,稱為交換節(jié)點(RESN)的重新計算,可以實現故障檢測.

故障檢測技術是基于哈希的后量子密碼算法應對故障攻擊的高效防御策略.文獻[72]提出了一種故障檢測策略以抵御故障攻擊,目的是檢測出錯誤計算從而避免簽名偽造,根據其作者的實現結果可知,針對BLAKE 方案,所付出的代價在面積開銷和吞吐量上分別下降為33.1%和14.5%;針對SPONGENT 的幾個變種方案,在面積開銷方面都額外增加了22%～24%不等,吞吐量最少時增加了8.3%.

5 基于多變量的PQC

5.1 基于多變量的密碼系統(tǒng)

基于多變量的密碼系統(tǒng)的數學難題是求解一個有限域上的非線性多變量方程式組.通常,多變量密碼系統(tǒng)的性能較優(yōu),不需要過多的計算資源,這使其對低成本設備中的應用程序具有吸引力.在多變量密碼系統(tǒng)中,HFE(hidden field equations cryptosystem)[73]和UOV(unbalanced Oil-and-Vinegar)[74]簽名方案是較早的、研究較多的以及最為廣泛的兩種密碼系統(tǒng).最早的多變量公鑰密碼系統(tǒng)是由Matsumoto 與Imai 在1988 年提出來的MI(Matsumoto-Imai)加密算法[75],不過后來Patarin[76]攻破了MI 加密算法.之后,研究學者們繼續(xù)對MI 密碼進行研究改進,目前主要使用的多變量簽名方案是HFE 和UOV 的變種,如NIST 二輪中的LUOV 方案是UOV 的變種,而NIST 二輪中GeMSS 簽名方案是HFE 的變種.自從1997 年Patarin[77]提出“UOV 方案”后,UOV 已成功地經受住了近20 年密碼分析的檢驗.該方案簡單,簽名小,速度快,因此,目前許多基于多變量的密碼系統(tǒng)均采用該方案或基于該方案進行改善和變種,但UOV 也存在一定的缺點,主要缺點是其公鑰非常大.下面簡述UOV 的基本原理.

UOV 簽名方案需要使用單向函數(即不可逆映射)作為限門函數.由n個變量m個方程組成的多變量二次方程式P=(p(1),...,p(m))可表示如下:

上面的限門函數P可以分解為P=F?T,其中,T為可逆線性映射函數,F是可逆二次映射函數,如下:設n變量的m可逆二次映射為,也稱為中心映射.令V={1,...,v},O={v+1,...,n},其中,則n個變量的多元二項式方程F=(f(1),...,f(m))定義為

其中,x=(x1,...,x n),k=1,...,o,n=v+o,m=0,o變量稱為油變量,v稱為醋變量.

下面簡單描述如何利用F、T來計算恢復P.即給定自變量x,目標求因變量y,使得P(y)=x.首先,F是可逆二次函數,通過計算F(y＇)=x,求出y＇,然后通過線性映射T,計算y=T-1(y＇),從而可以得出P(y)=x.為了減少密鑰大小,一般地,在設計方案時,只保存私鑰種子和公鑰種子,而不存儲整個F和T,這些種子的字節(jié)數少,占用空間小,在需要使用公私鑰時,再重新調用相應的公私鑰對生成函數即可.

5.2 針對多變量PQC的側信道攻擊

近幾年來,基于多變量PQC 的側信道攻擊工作較少,主要為能量分析和故障攻擊.在2018 年,Park 和Shim等人[78]針對基于多變量的 Rainbow 方案提出了相關能量攻擊方案,利用等效密鑰可以完全恢復出完整密鑰;2019 年,Kr?mer 等人[79]針對UOV 和Rainbow 算法提出了故障攻擊方案;2020 年,Shim 等人[80]又針對Rainbow 算法提出了新的故障攻擊方案,目的是誘導簽名中使用的隨機醋變量發(fā)生故障,其故障模型根據醋值的泄漏類型分為3 種情況:重復使用、泄露和置零,并且證明了UOV 的等價密鑰在多項式時間內可完全恢復.

下面簡述針對基于多變量的后量子密碼的相關能量分析原理.以文獻[78]為例,該方案使用了等價密鑰的概念,這里簡單描述等價密鑰的概念:設GLm(Fq)在Fq上的m維的線性群找到兩個線性可逆映射,Σ∈GLm(Fq),?∈GLn(Fq),滿足P=S?F?T=S?Σ-1? (Σ?F? Ω)?Ω-1?T.令S＇=S?Σ-1,F＇=F,T＇=?-1?T,則稱(S＇,F＇,T＇)為等價密鑰.Park 等人提出的攻擊點是以矩陣向量積運算的位置為目標,最后恢復出密鑰仿射映射S、T、F.攻擊原理和步驟大致如下.

控制向量X的所有元素來恢復仿射映射S,就可以使用中間結果來獲得矩陣A第i行的所有元素.獲得S后需要繼續(xù)恢復T＇,這里可以利用簽名中最后一步的矩陣向量乘積:計算除此之外,還需要用到等價密鑰的概念.假設等價密鑰的矩陣向量乘積如圖4 所示(圖4 來源于文獻[78]),可以清晰地看到:

因此可以利用矩陣A的第v1+o1+1 行到n行恢復出A2,利用下面的中間值來恢復Guess·xk,v1+o1+1≤k≤n.

Fig.4 Matrix-vector product using the equivalent key圖4 矩陣A 的等價密鑰圖

得到A2后,再利用等式其中,表示子矩陣A2的第(i,j)個元素.這里,利用與A1相乘,然后利用中間值得到A1的所有元素,再根據S,T?即可輕松利用線性多項式求解T和F.

基于多變量PAC 的側信道攻擊效果較好,具有較高的成功率.文獻[78]中,只用30 個能量跡就可恢復出正確密鑰;文獻[79]中,針對Rainbow 方案的不同安全級別的參數,其成功率均在89%～93%;在特殊情況下,如在矩陣A是可逆的情況下,在固定醋變量時,對于有限域F16、F31、F256,其成功率分別達到93.3%、96.6%、99.6%.

5.3 側信道防御策略

抵御能量分析最常用的對策是在算法增加隱藏或掩碼技術.針對基于哈希的密碼算法的防護近幾年的工作較少,有一部分原因在于哈希簽名方案的安全性,在很大程度上依賴于所選取的哈希函數,因此,單獨針對簽名方案的攻擊與防御較少.在文獻[78]中,作者除了提出等價密鑰的CPA 攻擊外,還推薦在實現中使用隨機仿射映射以抵御CPA 攻擊,如虛擬操作的隨機插入和操作的變換是一種常用的隱藏技術,并且,作者還推薦了另一種方法——對隨機數使用邏輯屏蔽的方法.在防御代價上,文獻[65]使用消息隨機化得到的矩陣向量與一般矩陣向量乘積相比,需要額外使用2n個乘法和1 個求逆(n為矩陣維度),無防護算法需要n2個乘法和加法,因此從總體來看,這種防護策略所帶來的額外開銷較少.

6 討 論

本節(jié)我們對不同類型的后量子密碼方案的特點以及它們的攻擊點和防護策略進行總結,討論未來可能的威脅和防御策略,并對未來的前景加以展望.

6.1 后量子密碼的特性

后量子密碼系統(tǒng)主要基于以下幾種不同的數學難題:基于格、基于編碼、基于多變量、基于哈希、基于超奇異同源等難題,其中,基于格的后量子密碼系統(tǒng)在性能上擁有很好的優(yōu)勢,部分原因得益于其使用了NTT,降低了計算復雜度;基于編碼的后量子密碼系統(tǒng)也是一類比較有競爭力的密碼系統(tǒng),其在性能上擁有很好的表現,而且基于編碼的密碼系統(tǒng)因底層基于糾錯碼,因此本身擁有很好的糾錯能力;基于超奇異同源的密碼系統(tǒng)具有公鑰尺寸小的特點,這有利于應用在嵌入式和物聯網等資源受限的芯片中,但目前在性能上遠不如其他類型的公鑰密碼系統(tǒng);基于多變量密碼系統(tǒng)主要用于簽名方案(NIST 二輪4 個,CACR 無),因為這類簽名方案要求的硬件資源非常少,簽名速度快,所以很適合用于低功耗設備,比如智能卡、RFID 芯片等;基于哈希的密碼系統(tǒng)與其他密碼系統(tǒng)相比,這種方案的主要優(yōu)點是其安全性僅依賴于泛型哈希函數的某些加密屬性,因此,如果所選的哈希函數將來被破壞掉,則可以很容易地用新的哈希結構替換它們.另外,近年來總體研究方向更偏向于基于格和基于編碼,根據本文調研近幾年的數據來看,格基密碼系統(tǒng)是目前研究數量最多、成果最多(主要是指在性能優(yōu)化以及安全實現方面),編碼密碼系統(tǒng)次之,這兩類密碼系統(tǒng)均主要用于公鑰加密/密鑰封裝.

6.2 針對不同類型后量子密碼的側信道攻擊與防御

(1) 側信道攻擊對后量子密碼算法的安全性具有較大影響.在基于格方面,側信道攻擊主要從采樣器(離散、中心二項式、拒絕等)、NTT、多項式乘法、糾錯碼等幾個核心部位進行攻擊,值得注意的是,多項式乘法、NTT 和采樣器是被攻擊比較多的部位;在基于編碼方面,側信道攻擊主要從糾錯碼、校驗子計算、稀疏矩陣的計算以及解密過程等部位進行攻擊,其中,校驗子計算和糾錯碼是被核心攻擊的部位,而且主要攻擊手段是時間攻擊;在基于哈希方面,側信道攻擊主要是以底層的HORST 和偽隨機發(fā)生器作為攻擊點;基于多變量的主要攻擊點在于矩陣向量乘積;最后在基于超奇異同源方面,本文沒有細述,但根據我們查閱的數據來看,主要攻擊點有蒙哥馬利梯度算法.對攻擊點情況的總結見表3.

Table 3 The attack point of different cryptosystems表3 不同類型密碼系統(tǒng)的攻擊點

(2) 在防護方面,針對能量分析攻擊主要存在的攻擊點應加以防護,而防護主要有兩種手段:隱藏(隨機化)和掩碼.根據防護策略的代價數據,掩碼的代價相對隱藏技術會高一些,如針對校驗矩陣的掩碼對策的代價與無保護方案相比,大概增加了8 倍的資源,而使用消息隨機化得到的矩陣向量與一般矩陣向量乘積相比,需要額外使用2n個乘法和1 個求逆,所需代價不到1 倍;而時間攻擊的最好防護手段是采用恒定時間實現;故障攻擊的防護策略是故障檢測.根據本文對所調研的文獻工作進行統(tǒng)計,匯總成表4,其中,2x代表增加2 倍的代價(這里,代價以性能為主).通常,密碼系統(tǒng)的防護可以分成3 類:應對能量分析的防護、時間攻擊的防護和故障攻擊的防護.時間攻擊的防護主要采用恒定時間實現,即將算法進行恒定時間實現或接近恒定時間實現(多次執(zhí)行同一算法的時間幾乎一樣);而能量分析最常用的防護策略有兩種:隨機化和掩碼方案,其中,隨機化在理論上只是增加攻擊難度(這種難度很高,但非完全不能攻破),掩碼方案可有效抵御(n階掩碼抵御n階攻擊);對于故障攻擊的防護方法為故障檢測和隨機化.

Table 4 Counter measures and its costs of different attacks表4 不同攻擊類型的防護手段及代價

6.3 后量子密碼未來可能的威脅和防御對策

(1) 未來可能潛在的側信道攻擊:未來可能的側信道攻擊可能來自兩個方面,一方面來自目前已存在的側信道攻擊的新型混合攻擊,上文已列出主要的經典側信道攻擊手段,可考慮混合多種上述攻擊方法,結合多種手段、側信息和分析方法可能發(fā)掘出新的混合攻擊方式,再利用人工智能、AI 等手段,縮短分析時間,以提高攻擊效率;另一方面來自于挖掘新的側信息資源,比如在一些新的硬件平臺上(Intel PT/TSX/MPX/CAT 等和ARM v8架構的ARM Cotex A77/A78 等平臺)會有新的硬件特性,這些新特性可能存在新的側信息泄露.

(2) 可能的防御方案:目前已有許多文章給出了防御側信道攻擊的手段,見表4,對應不同的側信道攻擊手段采用相應的防護策略,一般來說,可以分成以下兩個方面的解決方案:a) 軟件方面:這里主要為源碼層次的解決方案,可以多采用一些系統(tǒng)特性來預防和檢測攻擊,如:隨機化技術、時間異常檢測技術、檢測可疑異常和中斷等,同時采用并行技術,減少單一數據的側信息泄露,增加噪聲,以達到分析攻擊的難度.b) 硬件層面:首先硬件層面的優(yōu)化實現本身的工程量大,復雜度高,對應的優(yōu)化實現解決方案也一直處于探索階段.在此基礎上,側信道防護策略必將增加額外的資源消耗和設計難度,因此,本文推薦一種可能的解決方案:采用軟/硬件協(xié)同方式進行實現,將耗時關鍵的核心算子使用硬件加速實現,其余部分使用軟件實現,既保證了高效性,又降低了復雜度和工程量.另外,硬件實現雖然復雜度高,但目前也有一些全硬件實現的解決方案,因此可以參考目前已有的解決方案進而加以改善.

6.4 現存問題及未來前景展望

最后,我們對后量子密碼存在的問題和未來的前景展望給出簡單論述.目前,后量子存在的問題主要體現在性能、攻擊、防御這3 個方面,當然也存在其他因素,比如公鑰尺寸大小、解密錯誤率等,這些因素都會影響算法標準的制定,但是性能和安全性是標準最核心的評價因素,比如,超奇異同源密碼具有良好的公鑰尺寸小的特點,但性能過低,相對于格密碼,超奇異同源的性能會比最快的密碼方案慢千倍之多,因此性能成為了超奇異同源密碼最主要的瓶頸.NIST 第2 輪中,也重點評比了性能和安全性,根據NIST 官方的數據,目前加密方案中,綜合性能、參數、公鑰尺寸等因素,格密碼具有最高的評價;在公鑰大小、密文大小方面,超奇異同源最優(yōu);在性能方面,格密碼最優(yōu),編碼次之.而簽名方案中,簽名字節(jié)最小的是多變量,格密碼排在中等;性能上,多變量和格密碼較優(yōu);綜合來看,多變量的簽名方案綜合評分最高,格密碼次之.對于后量子密碼未來的前景展望,由于量子計算機的研究不斷地取得進展,傳統(tǒng)的公鑰密碼算法領域將都會被后量子密碼所取代,并且,在新型產業(yè),如物聯網、5G、衛(wèi)星通信、軍事國防、區(qū)塊鏈、數字貨幣、數字簽名等領域都是后量子密碼廣泛應用的領域,也是亟需安全可靠的后量子密碼來保障數據安全的領域.同時,后量子密碼也衍生出新的研究領域,如同態(tài)加密、基于屬性加密等,這些領域也是目前比較熱門的研究領域.未來后量子密碼的應用,無論是用于上述新興產業(yè)領域還是其衍生領域,側信道分析都是后量子密碼的安全門關,在應用于這些領域之前,都會對于后量子密碼進行側信道安全測評,因此,側信道安全分析和測評會是未來后量子密碼重點研究的關鍵點.為了使用上述產業(yè)領域,多平臺的側信道分析和測評會是未來后量子密碼的側信道分析中必要的解決方案.

7 總結

本文針對最新的后量子密碼方案的側信道攻擊與防御進行了調研,通過分析針對各類后量子密碼側信道的攻擊與防御策略,從攻擊方法、攻擊點、攻擊評價等多方面對不同后量子密碼算法進行了側信道攻擊的深入分析,并從安全性和防護代價兩個維度對側信道防御策略進行了論述,總結了針對不同類型后量子密碼的攻擊點,以及不同攻擊類型的防護手段及代價,最后討論了后量子密碼未來可能的側信道攻擊、解決方案,并對未來的前景進行了展望.