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

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 211106)

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

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

本文針對(duì)NIST 最新公布的二輪候選后量子密碼算法和中國(guó)CACR 公鑰密碼競(jìng)賽第2 輪入選算法進(jìn)行了調(diào)研,分析了最新的側(cè)信道安全研究進(jìn)展和防御策略,主要工作分為3 點(diǎn).

(1) 將NIST 第2 輪后量子密碼的不同類型作為研究對(duì)象,同時(shí)參照中國(guó)密碼學(xué)會(huì)CACR 競(jìng)賽入選的后量子算法類型,整理與歸納這些密碼現(xiàn)有的側(cè)信道安全性水平和可能的防御能力.

(2) 針對(duì)現(xiàn)有后量子側(cè)信道攻擊方法,匯總不同信道與不同方式的攻擊方法,并按照算法核心算子進(jìn)行分類,給出攻擊結(jié)果的評(píng)價(jià)指標(biāo),從攻擊方法、攻擊點(diǎn)、攻擊評(píng)價(jià)等多個(gè)角度進(jìn)行側(cè)信道攻擊的深入分析.

(3) 針對(duì)現(xiàn)有后量子側(cè)信道防護(hù)方法,整理不同對(duì)抗策略的應(yīng)用方式,調(diào)研最易遭受攻擊的核心算子的防護(hù)策略以及現(xiàn)有防御策略的代價(jià)瓶頸,從安全性和防護(hù)代價(jià)兩個(gè)維度開(kāi)展分析.

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

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

1 背 景

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

1.1 后量子密碼算法

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

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

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

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

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

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

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

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

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

1.2 側(cè)信道攻擊

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

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

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

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

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

· 相關(guān)能量分析(correlation power analysis,簡(jiǎn)稱CPA)[16].CPA 是基于電路的實(shí)際功耗和功耗模型之間的關(guān)系,如漢明重量模型與功耗呈線性關(guān)系,來(lái)進(jìn)行分析,因?yàn)檎_密鑰對(duì)應(yīng)操作的功耗與中間值的漢明重量之間的相關(guān)系數(shù)會(huì)達(dá)到最大.

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

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

2 基于格的PQC

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

(1) 格及格的困難問(wèn)題

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

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

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

(2) 帶錯(cuò)誤的學(xué)習(xí)問(wèn)題

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

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

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

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

這兩種LWE 在一定程度上是等價(jià)的,能求解sLWE 問(wèn)題的方法也能求解dLWE.對(duì)于LWE 問(wèn)題中的錯(cuò)誤分布χ,一般都采用離散高斯分布方式.

(3) 格密碼體制分類

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

2.2 針對(duì)格基PQC的側(cè)信道攻擊

(1) 能量分析攻擊

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

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

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

(2) 故障攻擊

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

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

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

(3) 其他攻擊

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

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

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

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

2.3 側(cè)信道防御策略

隱藏、掩碼和檢測(cè)技術(shù)是預(yù)防側(cè)信道攻擊的有效防御策略,下面簡(jiǎn)述近幾年的防御策略研究工作,分別對(duì)能量分析、故障攻擊和時(shí)間攻擊的防御工作進(jìn)行介紹.

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

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

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

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

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

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

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

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

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

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

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

3 基于編碼的PQC

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

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

(1) 編碼的基本原理

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

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

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

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

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

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

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

(2) 困難問(wèn)題

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

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

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

下面是校驗(yàn)子解碼問(wèn)題的兩個(gè)變種:搜索型SDP 和決策性SDP.

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

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

3.2 針對(duì)編碼PQC的側(cè)信道攻擊

(1) 能量分析攻擊

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

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

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

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

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

時(shí)間攻擊最主要的原理是非恒定時(shí)間實(shí)現(xiàn)的算法會(huì)因操作不同的數(shù)據(jù)而泄露出關(guān)鍵信息.下面舉例說(shuō)明針對(duì)非恒定時(shí)間的HQC 攻擊方法[60].整個(gè)攻擊方案分為兩步:頻譜恢復(fù)和密鑰重構(gòu).頻譜恢復(fù)是使用時(shí)間信息的部分.為了方便描述其過(guò)程,這里假設(shè)Alice 是持有密鑰的目標(biāo)設(shè)備.下面是頻譜恢復(fù)的大概過(guò)程.

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

2) 因?yàn)樗忻芪亩际枪粽弋a(chǎn)生的,因此攻擊者知道r1和r2.攻擊者利用頻譜恢復(fù)算法迭代地構(gòu)建兩個(gè)數(shù)組Tx和Ty,使得Tx[d](Ty[d])是d在r2(r1)頻譜內(nèi)的解密時(shí)間的平均值.

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

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

密鑰重構(gòu)是利用上面獲得的信息來(lái)計(jì)算私鑰中的y:由上述步驟得到集合D和在頻譜內(nèi)的距離k,然后再利用密鑰重構(gòu)算法恢復(fù)出y,對(duì)于這一算法此處不再詳述,因?yàn)樵撍惴ㄊ荊uo 等人[28]提出的密鑰重構(gòu)算法的一個(gè)簡(jiǎn)單擴(kuò)展版.

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

3.3 側(cè)信道防御策略

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

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

4 基于哈希的PQC

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

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

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

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

* ?1:待簽名消息的字(大小為ω)的字?jǐn)?shù)量;

* ?2:簽名算法中校驗(yàn)值(大小為ω)的字?jǐn)?shù)量.

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

簽名后的長(zhǎng)度為?=?1+?2,ω和W的關(guān)系是ω=2W.其中,

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

4.2 針對(duì)哈希PQC的側(cè)信道攻擊

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

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

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

4.3 側(cè)信道防御策略

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

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

5 基于多變量的PQC

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

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

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

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

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

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

5.2 針對(duì)多變量PQC的側(cè)信道攻擊

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

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

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

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

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

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

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

5.3 側(cè)信道防御策略

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

6 討 論

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

6.1 后量子密碼的特性

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

6.2 針對(duì)不同類型后量子密碼的側(cè)信道攻擊與防御

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

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

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

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

6.3 后量子密碼未來(lái)可能的威脅和防御對(duì)策

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

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

6.4 現(xiàn)存問(wèn)題及未來(lái)前景展望

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

7 總結(jié)

本文針對(duì)最新的后量子密碼方案的側(cè)信道攻擊與防御進(jìn)行了調(diào)研,通過(guò)分析針對(duì)各類后量子密碼側(cè)信道的攻擊與防御策略,從攻擊方法、攻擊點(diǎn)、攻擊評(píng)價(jià)等多方面對(duì)不同后量子密碼算法進(jìn)行了側(cè)信道攻擊的深入分析,并從安全性和防護(hù)代價(jià)兩個(gè)維度對(duì)側(cè)信道防御策略進(jìn)行了論述,總結(jié)了針對(duì)不同類型后量子密碼的攻擊點(diǎn),以及不同攻擊類型的防護(hù)手段及代價(jià),最后討論了后量子密碼未來(lái)可能的側(cè)信道攻擊、解決方案,并對(duì)未來(lái)的前景進(jìn)行了展望.