輕量級認證加密算法Spook的相關能量分析

潘 力,韋永壯

(桂林電子科技大學廣西密碼學與信息安全重點實驗室,廣西 桂林 541004)

1 引言

1999年,Kocher等人[1]利用密碼芯片的功耗依賴于其所處理的數據或所執行的操作關系,提出了差分能量分析(Differential Power Analysis,DPA)方法。本質上,DPA[2]利用了一個基本事實:密碼設備的能量消耗依賴于算法執行過程中所處理的中間值(中間狀態)。此后,各種側信道分析被相繼提出,如相關能量分析(Correlation Power Analysis,CPA)[3]、互信息分析(Mutual Information Analysis, MIA)[4]等。2015 年,王等人[5]提出了改進的相關能量分析方案 SGA-CPA。2019 年,烏等人[6]提出了針對一種基于 SM3 算法的消息驗證碼的CPA攻擊。陳等人[7]提出了針對 SM4 的混合智能側信道分析攻擊方法。王等人[8]提出了新的改進的相關能量分析方案MS-CPA。2020年,龔等人[9]使用CPA攻擊了美國國家標準與技術研究院(National Institute of Stand-ards and Technology, NIST)征集的輕量級加密算法中的第二輪候選算法WAGE。2021年,王等人[10]提出了相關能量分析中的后向檢錯方案,提高了相關能量分析的準確率。同年,王等[11]提出了一種基于遺傳算法的高效的CPA框架。CPA與其它分析方法相比,其核心思想在于計算算法的假設功耗與真實功耗的相關性,從而恢復出敏感信息;而DPA則是根據某個中間值的某一比特將能量跡簡單分組,對泄露信息的利用率較低。同其它分析方法相比,CPA分析效率更高,因此對密碼算法的威脅更大,文獻[12]也佐證了這一觀點。

近些年來,在一些新興領域[13](例如傳感器網絡、醫療保健、分布式控制系統、物聯網、信息物理系統等)資源高度受限的設備[14]需要相互連接,協同完成某些工作[15]。由于當前的大多數加密算法都是為桌面/服務器環境設計的,這些算法大多不適合資源受限設備。因此,NIST于2015年面向全球啟動輕量級加密算法的征集工作。2020年, 來自魯汶大學、德國波鴻魯爾大學及法國國家計算機科學與控制研究所的密碼專家聯合設計出一種新的輕量級認證加密算法Spook[16],它是NIST第二輪候選算法之一。與之前的算法不同,Spook基于雙工海綿結構[17],包含Clyde-128和Shadow-512兩個大部件。Spook將防泄露操作模式[18]與比特切片技術[19]相結合,以實現高效和低延遲。目前,針對Spook的傳統數學分析[20]已經取得一些進展,但Spook能否抵抗側信道攻擊,特別是其抵御CPA攻擊的能力還有待進一步地評估。

本文根據Spook加密算法的結構和特點,設計了針對Spook算法的CPA攻擊方法。實驗結果表明,Clyde-128部件對于CPA攻擊具有脆弱性;Shadow-512部件具備抵抗側信道攻擊的能力,但攻擊此部件仍可恢復部分敏感信息,并可進一步恢復出相應明文。實驗還表明:相比S盒采用查表操作,當S盒采用切片技術時, Spook密碼算法抵御CPA攻擊的能力稍有提升。

2 Spook算法描述

2020年,密碼學者Francesco、Gregor、Gaёtan等人基于海綿結構設計了Spook加密算法,這是一種輕量級的認證加密算法,特別適合在資源受限設備上部署使用。Spook由兩個主要部件構成,分別是Clyde-128和Shadow-128,其中Shadow-512可以看作是Clyde-128的多重復用,均包含非線性替換、L盒、輪常量加。此外Shadow-512還包含混淆層。根據π部件內部狀態的大小和單/多用戶的不同可將其分為4種版本,分別記為:Spook128mu384、Spook128mu512、Spook128su384、Spook128su512。對于Spook128mu512和Spook128su512,密鑰做了一些處理,但沒有改變算法的安全強度。在算法內部,明文data和關聯數據AD總長度不超過256比特,被分成i塊,前i-1塊長度為128比特,最后一塊長度不超過128比特。密鑰K長度為128比特。一次性隨機變量vector長度為128比特。填充數據fill則根據實際需要確定填充長度。為方便起見,此處只討論Spook128su384加密算法(下文簡稱Spook)的安全性。Spook算法結構如圖1所示,加密過程如下:

1)vector、fill和主密鑰K進入加密函數E,生成長度為128比特的種子密鑰seed;

2)seed、vector、fill進入置換部件π更新,并吸收關聯數據AD,之后進入置換部件π更新并得到更新后的中間狀態state0。此時明文data未參與運算,其它參數固定不變時,state0保持不變,長度為384比特;

3)state0分塊加密明文data,得到對應的密文cipher。在每次加密明文塊得到密文塊之后,中間狀態state都會經過π被更新,這樣做起到了一次一密的作用。每次運算只加密長度為128比特的明文,當data最后一塊長度不足128 比特時,用0填充。

4)在加密完所有明文之后,更新后的中間狀態state1與K經過E得到標簽tag。tag由state1[0]與state1[1]和主密鑰K經過E生成。

2.1 Clyde-128

加密函數E由Clyde-128構成,用于生成seed或tag。Clyde-128示意圖如圖2所示。

圖2 Clyde-128示意圖

2.2 Shadow-512

置換部件π由Shadow-512構成,用于更新Spook的內部中間狀態,它為Spook提供了一種防泄漏操作模式。Shadow-512示意圖如圖3所示。

圖3 Shadow-512

從圖3可以看出,Shadow-512部件的內部狀態state為384比特,被分成3組,每組長度為128比特。在加密明文時,state前128比特與第一塊明文data[0]運算,然后state進入π更新,更新后的state中間128比特與第二塊明文data[1]運算。由于明文長度不超過256比特,因此state最后一塊128比特狀態值不與明文做任何運算。

2.3 半字節代換

半字節代換是一個非線性變換操作,其將內部狀態中的每一個半個字節替換為另一個半個字節。Spook使用4比特密碼S盒,即4比特輸入得到4比特輸出,如表1所示。S盒的代數正規型見式(1)

表1 Spook算法S盒

y[1]=(x[0]?x[1])⊕x[2]

y[0]=(x[3]?x[0])⊕x[1]

y[3]=(y[1]?x[3])⊕x[0]

y[2]=(y[0]?y[1])⊕x[3]

(1)

式中,0表示低位,3表示高位,?表示與運算,⊕表示異或運算。5.2節S盒采用比特切片技術實現時需要參考式(1)。

2.4 L盒

使用L盒是為了在有限的實現成本下獲得更好的分支數量,提高抵抗線性和差分攻擊的能力。此L盒有16個分支,意味著S盒的位數必須是偶數。它的計算公式如式(2)所示。

(a,b)=L′(x,y)

(2)

其中,x、y表示32比特長的數,circ表示第一行用十六進制表示的循環矩陣。

2.5 混淆層

Spook算法的混淆層使用的是Midori[21]加密算法的混淆層,它基于近似MDS 4×4矩陣D,定義如(3)所示

(3)

它有4個分支,可以使用較為簡單的電路實現。

2.6 輪常量

輪常量由4位線性反饋移位寄存器(Linear Feedback Shift Register, LFSR)生成,具體數值如表2所示。

表2 Spook算法L盒

3 相關能量分析與數據預處理

加密設備在運行過程中會通過側信道泄露多種信息,如時間序列[22]、功耗[23]、電磁輻射[24]等。CPA是功耗攻擊的一種常見方法,攻擊的目標是設備對明文進行加密(解密)運算時泄露的功耗信息,并基于這些信息恢復出需要的敏感信息。值得注意的是,CPA攻擊需要采集較多功耗數據,且數據整體需滿足正態分布。下面簡要介紹CPA攻擊的基本思想。

3.1 相關能量分析流程

相關能量分析[3]大致可分為以下4個步驟:

1)選定算法運行過程中的某個中間值。這個中間值通常由一個函數func(p,guesskey)生成,p多為明文(密文),guesskey為猜測密鑰;

2)采集加密算法在設備上運行時的真實功耗數據;

3)計算假設功耗。根據猜測密鑰guesskey,計算與之對應的中間值,并將中間值通過功耗模型映射為假設功耗;

4)計算不同猜測密鑰對應的假設功耗與真實功耗的相關性。相關性計算式如式(4)

(4)

圖4 CPA攻擊流程圖

3.2 功耗模型

對于在軟件平臺實現的加密算法,一般選用漢明重量模型刻畫動態能量消耗。原因在于微控制器采用了預充電總線,在向總線發送被操作數之前,所有總線都會被置為1[25]。設某一時刻i的功耗用T[i]表示,功耗T[i]與中間值x[i]的線性關系[26]可以表示成

T[i]=μHW(x[i])+b+noise

(5)

其中,μ表示漢明重量HW(x[i])與功耗T[i]之間的之間的常量比率,b表示電路中的靜態能量消耗,noise表示隨機噪聲。

3.3 泄露檢測

為了快速評估Spook算法是否存在可被利用的側信息泄露及其泄露區間,引入泄露檢測技術。2011年,Gilbert等人[27]將t-test用于側信道信息的泄露評估上,并對AES算法進行了泄露檢測。2013年,Becker等人[28]進一步完善了該方法,并重新命名為TVLA(Test Vector Leakage Assessment)。在實際應用中,為了減少誤差,需要對對一定數量的固定明文和隨機明文進行交替加密,并采集相應的功耗曲線,用獲得的兩組功耗曲線進行t-test。其中,t統計量計算公式如式(6)

(6)

3.4 數據預處理

在CPA中,計算相關系數尤其耗時。當單條功耗曲線的采樣點數越多,相應的攻擊時間越長。因此在分析功耗曲線之前,有必要壓縮曲線。文獻[29]通過傅里葉變換將時域信號轉換為頻域信號分析,但該方法的效果取決于信息泄露和噪聲的頻譜特征。文獻[25]中提出了諸如最大值整合、原始值整合等方法處理一個時鐘周期內的點,以實現壓縮曲線的目的。在機器學習領域有許多降維方法,包括主成分分析(Principal Component Analysis, PCA)[30]等。將主成分分析方法引入功耗曲線的預處理階段,用于提取功耗中的主要信息,實現曲線的壓縮。

設采集到的功耗曲線組成矩陣T。其中包括n條功耗曲線,每條曲線包含m個采樣點,則T為

(7)

PCA處理步驟如下:

2)計算Cov的特征值λ1,λ2,…,λm和對應的單位特征向量

(8)

P1=e1,1T1+e2,1T2+…em,1Tm

P2=e1,2T1+e2,2T2+…em,2Tm

? ?

Pm=e1,2T1+e2,nT2+…em,nTm

(9)

使用主成分分析處理功耗曲線在于壓縮曲線,預處理后的維度k(k≤m),即每條曲線的點數應盡可能少,同時包含盡可能多的信息。k可通過損失率確定,設損失率為β,則有

(10)

損失率通常限定在0.15以內。在實驗中選擇損失率為0.05。

4 針對Spook加密算法的相關能量分析

本節將介紹Spook算法的Clyde-128和Shadow-512部件的攻擊細節。第一部分攻擊Clyde-128期望恢復算法加密用的主密鑰K。設計者聲稱Shadow-512部件為加密算法提供了防泄露操作模式[16],可以抵抗側信道攻擊。第二部分攻擊Shadow-512部件,驗證其是否可以抵抗CPA攻擊。

4.1 攻擊Clyde-128

從算法結構可以看出,在生成seed的部分,Clyde-128會用到vector、fill和主密鑰K。通過固定明文,并更改vector的方式恢復出主密鑰K。在Clyde-128內部,K先與vector異或得到128比特狀態值,而后按圖5所示生成種子密鑰seed。

圖5 Clyde-128攻擊點

在實驗過程中,攻擊點選在密碼S盒的輸出位,將S盒輸出值通過漢明重量模型映射為假設功耗,并與采集到的真實功耗求解相關性,恢復出K(具體攻擊實驗過程采用3.1節所述步驟)。

4.2 攻擊Shadow-512

如第2節所述,當AD、K、vector固定不變時,state0始終不變。此后state0的前128比特state0[0]參與到data[0]的運算中并得到密文cipher[0]。接著state0進入部件π被更新,記為Updatestate0[1]。Updatestate0[1]與data[1]運算得到密文cipher[1]。在分析時,由于需要明文參與運算,選擇在每次Shadow-512內部狀態第一次過S盒時作為攻擊點,如圖6所示。

圖6 Shadow-512攻擊點

設通過混淆層前的中間狀態值為:Dpre[0]、Dpre[1]、Dpre[2],通過混淆層后的中間狀態值為:Dafter[0]、Dafter[1]、Dafter[2]?；煜龑影慈缦路绞礁?/p>

Dafter[0]=Dpre[0]⊕Dpre[1]⊕Dpre[2]

Dafter[1]=Dpre[0]⊕Dpre[2]

Dafter[2]=Dpre[0]⊕Dpre[1]

(11)

由于不能完全掌握通過混淆層之前的中間狀態值,無法進行后續的密鑰恢復操作。因此,攻擊Shadow-512部件,只能恢復出與K相關的前128比特中間狀態值(具體攻擊實驗過程采用3.1節所述步驟)。

5 測試結果與分析

實驗環境如表3所示:

表3 實驗環境

在實驗中,為了使分析更簡便,在執行加密算法時,AD為固定的256比特數據,K為固定的128比特數據,具體參數如下

K=0x000102…0d0e0f,AD=0x00…00

根據算法結構和密鑰,可以計算出明文參與前的中間狀態state0的前128比特為:

state0=0xC2B5BBE3E0CCF2F799CBE5C444F427EA

5.1 S盒查表

算法實現時,S盒首先采用查表方式,每個數據的高四位和低四位依次通過S盒。采集Spook功耗數據,如圖7所示。

圖7 Spook功耗(S盒查表)

圖7中,橫軸表示采樣時刻,縱軸表示功耗值,每條曲線145個點。對采集到的功耗數據進行泄露評估,評估結果見圖8。

圖8 Spook t-test結果(S盒查表)

圖8中,橫軸表示采樣時刻,縱軸表示t值。上圖表明,加密算法大致在[0:20000]以及[850000:1450000]區間存在信息泄露。

5.1.1 Clyde-128攻擊結果

由5.1節中的t-test結果可知,結合算法結構,區間[0:20000]即為Clyde-128產生的泄露。采集789條功耗曲線,經過預處理后,單條曲線的點數從20000降至29,成功恢復出Spook加密所用的密鑰K。具體結果見圖9:

圖9 Clyde-128攻擊結果(S盒查表)

可知,S盒采用查表方式時,Clyde-128部件面對CPA具有脆弱性,也即此時Spook算法面對CPA具有脆弱性。

5.1.2 Shadow-512攻擊結果

由5.1節中的t-test結果可知,在區間[850000:1450000],Shadow-512部件存在側信息泄露。在實際分析時,采集5萬條功耗曲線。根據算法結構,每條能量跡截取區間[900000:1000000],即10萬個點。經過預處理后,每條曲線僅有1100個點。通過分析處理后的功耗數據,得到圖10?？芍?對Shadow-512的攻擊完全恢復了state0的前128比特敏感信息。根據恢復出的敏感信息,當明文長度不超過128比特時,可以計算出密文對應的明文,但無法得到認證用的標簽。

圖10 Shadow-512攻擊結果(S盒查表)

5.2 S盒切片

前面的討論中S盒均使用查表的方式,而作為對比實驗,本小節采用比特切片技術實現密碼S盒層,并再次檢驗Spook算法的安全性。設S盒輸入為Sin,輸入數據為in,in為16個8比特的數,S盒輸出數據為Sout,具體切片過程見式(12)和(13)

Sin[0]=in[3]‖in[2]‖in[1]‖in[0]

Sin[1]=in[7]‖in[6]‖in[5]‖in[4]

Sin[2]=in[11]‖in[10]‖in[9]‖in[8]

Sin[3]=in[15]‖in[14]‖in[13]‖in[12]

(12)

經過S盒如下

Sout[0]=(Sin[0]?Sin[1])⊕Sin[2]

Sout[1]=(Sin[3]?Sin[0])⊕Sin[1]

Sout[2]=(Sout[1]?Sin[3])⊕Sin[0]

Sout[3]=(Sout[0]?Sout[1])⊕Sin[3]

(13)

式(12)、(13)中,0表示低位,3表示高位,?表示與運算,⊕表示異或運算。將S盒用切片技術實現后,重新采集算法的功耗信息。如圖11所示。

圖11 Spook功耗(S盒切片)

圖11中,橫軸表示采樣時刻,縱軸表示功耗值,每條曲線44萬個點。從圖7和圖11的對比中可以明確的是,使用切片技術之后,整個算法的運行速度提高。相應的t-test結果見圖12。

圖12 Spook t-test結果(S盒切片)

5.2.1 Clyde-128攻擊結果

由5.2節中的t-test結果可知,結合算法結構,區間[0:18000]即為Clyde-128產生的泄露。采集5萬條功耗曲線,經過預處理后,單條曲線的點數從18000降至96,恢復出的結果見圖13。

圖13 Clyde-128攻擊結果(S盒切片)

根據結果可知,對Clyde-128的攻擊總計恢復出44比特與密鑰相關的敏感信息。

5.2.2 Shadow-512攻擊結果

由5.2節中的t-test結果可知,在區間[260000: 440000]Shadow-512部件存在側信息泄露。在實際分析時,根據算法結構,每條能量跡截取區間[250000:300000]即5萬個。經過預處理后,每條曲線僅有630個點。通過分析預處理后的功耗數據,具體結果見圖14。

圖14中,橫軸表示恢復出來的密鑰,縱軸表示密鑰對應的相關系數。根據結果可知,針對Shadow-512的攻擊總計恢復出16比特與密鑰相關的敏感信息。

5.1節和5.2節的對比實驗具體情況如表4和表5。

實驗表明通過使用多個S盒并行運算的比特切片技術提高了CPA攻擊的難度,但并不能提供絕對的安全性。原因在于,S盒采用查找表實現時,加密數據依次輸入S盒,并得到相應的輸出值,每次只有半字節數據產生功耗,分析采集到的功耗時,采用經典CPA的“分而治之”思想就可以恢復出敏感信息。S盒采用切片技術實現時,算法使用32個并行運算的S盒,這32個S盒的功耗會彼此影響,當采用經典CPA分析時,效率變低。

此外,將5.1.1節與文獻[9]和文獻[31]中類似結構的算法在攻擊復雜度方面做了一個直觀的對比,具體見表6。

表6 類似算法結構攻擊復雜度對比

加密算法在不同的設備上執行加密運算時,由于實現方式和設備的差異,導致側信息的泄露的情況不完全相同,因此攻擊效果也不完全一樣,此處只與文獻[9]和[31]做了一個橫向比較。同時,通過引入PCA對功耗曲線進行預處理,較好的壓縮了曲線,提高了攻擊效率。

6 結束語

本文分析了Spook算法抵御CPA的能力,即主要考察了Clyde-128和Shadow-512部件對于CPA攻擊的安全性。在ARM開發板上的研究結果表明:采用CPA攻擊其Clyde-128部件可在很短時間內恢復出加密用的主密鑰;而當攻擊其Shadow-512部件則可恢復出與密鑰相關的前128比特中間狀態;通過利用恢復出的中間狀態和密文值,可捕獲到明文的前128比特信息。此外還發現:當S盒采用比特切片技術,即通過使用32個S盒并行運算,能少許提升CPA攻擊的成本,但仍無法完全抵御該攻擊。下一步的研究可以考慮Spook密碼算法的高效的掩碼防護方法。