李新超,鐘衛(wèi)東,劉明明,李 棟

(武警工程大學(xué) a.網(wǎng)絡(luò)與信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室; b.密碼工程學(xué)院,西安 710086)

0 概述

SM4是我國自行設(shè)計(jì)的分組密碼標(biāo)準(zhǔn),2012年由國家密碼管理局發(fā)布,采用非平衡Feistel結(jié)構(gòu),加密算法與密鑰擴(kuò)展算法均采用32輪非線性迭代結(jié)構(gòu),具有較高的安全性[1]。自1999年Kocher利用差分功耗分析(Differential Power Analysis,DPA)攻擊成功破解DES算法之后,各種已知的密碼算法包括SM4都面臨著巨大的威脅,如何抵御DPA攻擊成為密碼學(xué)研究的一大熱點(diǎn)。

2007年,文獻(xiàn)[2]通過對(duì)SM4算法進(jìn)行分析,成功得到了S盒的代數(shù)表達(dá)式,為SM4算法的進(jìn)一步研究奠定了基礎(chǔ)。2008年,文獻(xiàn)[3]對(duì)SM4算法進(jìn)行了DPA攻擊,證明了SM4算法面對(duì)DPA攻擊的脆弱性,同年又提出了一種能夠抵御DPA攻擊的安全掩碼方案及其VLSI實(shí)現(xiàn),進(jìn)行對(duì)掩碼防御DPA攻擊的新嘗試[4]。2014年,文獻(xiàn)[5]提出了在復(fù)合域求逆中對(duì)S盒進(jìn)行掩碼來抵御DPA的方法,并進(jìn)行了實(shí)驗(yàn)驗(yàn)證。該方法加快S盒中求逆的運(yùn)算速度,降低了消耗,并通過添加掩碼,增強(qiáng)了抵抗DPA攻擊的能力,但效果仍不明顯。由于SM4算法脫胎于AES算法,兩者具有相似的S盒結(jié)構(gòu),對(duì)AES的DPA攻擊同樣給SM4算法造成了威脅。為了抵御DPA攻擊,2006年,文獻(xiàn)[6]提出了基于秘密共享抵抗DPA攻擊的思想,開創(chuàng)了抵御DPA攻擊的新思路,并為共享S盒的實(shí)現(xiàn)提供了理論依據(jù)。2011年,文獻(xiàn)[7]提出了高效S盒的硬件實(shí)現(xiàn),并將秘密共享思想應(yīng)用于AES的S盒,提高了AES抵抗一階DPA攻擊的水平。2014年,文獻(xiàn)[8]基于秘密共享思想及復(fù)合域求逆方法對(duì)共享S盒的分組情況進(jìn)行了研究,并提出了針對(duì)AES算法的共享實(shí)現(xiàn)方案。

針對(duì)SM4算法如何有效防御DPA攻擊問題,本文根據(jù)SM4算法S盒的特點(diǎn),在對(duì)Bilgin的共享S盒分組實(shí)現(xiàn)方案進(jìn)行分析研究的基礎(chǔ)上,結(jié)合文獻(xiàn)[5]的工作,構(gòu)造了一個(gè)適用于SM4算法的低功耗共享S盒。

1 相關(guān)知識(shí)

1.1 S盒

S盒作為SM4算法唯一的非線性部分,是評(píng)估SM4算法安全性的關(guān)鍵。2007年,文獻(xiàn)[2]通過對(duì)SM4算法S盒的研究,成功獲得了S盒的代數(shù)表達(dá)式,并給出了相關(guān)參數(shù)的具體值。通過實(shí)驗(yàn)驗(yàn)證發(fā)現(xiàn),該表達(dá)式及相關(guān)參數(shù)值能夠滿足所有的S盒取值。

代數(shù)表達(dá)式為:

S(x)=I(x·A1+C1)·A2+C2

(1)

不可約多項(xiàng)式為:

f(x)=x8+x7+x6+x5+x4+x2+1

(2)

循環(huán)矩陣為:

(3)

行向量為:

(4)

由于AES算法S盒與SM4的S盒具有相似的求逆部分,因此可在SM4的S盒中引入復(fù)合域方法求逆,提高運(yùn)算速度,降低功耗。SM4算法S盒復(fù)合域求逆過程如圖1所示。

1.2 差分功耗分析

差分功耗分析是一種典型的側(cè)信道攻擊,也是最流行的能量分析攻擊,其基本原理是利用了密碼設(shè)備的瞬時(shí)能量消耗與設(shè)備處理的數(shù)據(jù)和執(zhí)行的操作之間的關(guān)聯(lián)性[9]。通過使用特殊的電子測量儀和數(shù)學(xué)統(tǒng)計(jì)技術(shù),可以檢測和分析CMOS芯片在執(zhí)行不同的指令時(shí)產(chǎn)生的功率消耗,從而獲得芯片中與密鑰有關(guān)的重要信息。DPA攻擊的目標(biāo)是密碼設(shè)備對(duì)大量不同數(shù)據(jù)分組進(jìn)行加解密操作時(shí)記錄的能量軌跡,使用這些軌跡來分析固定時(shí)刻設(shè)備的能量消耗,并將能量消耗視作被處理數(shù)據(jù)的函數(shù),從而恢復(fù)出密碼設(shè)備中的密鑰,因此攻擊者不必了解要攻擊設(shè)備的具體信息[10]。DPA 攻擊通常包括以下4個(gè)步驟:

步驟1選擇密碼設(shè)備執(zhí)行算法的某個(gè)中間值D,構(gòu)造差分函數(shù)D(m,k),其中,m為已知的非常量數(shù)據(jù),k為待猜測的子密鑰。

步驟2對(duì)密碼設(shè)備輸入大量不同數(shù)據(jù),測量能量消耗軌跡mi及ti。

步驟3猜測子密鑰k,計(jì)算假設(shè)中間值,按照選定模型將中間值映射為能量消耗值,將軌跡ti分類,與實(shí)際能量跡比對(duì),計(jì)算平均功耗軌跡t,并與分類的軌跡進(jìn)行差分運(yùn)算,公式如下:

(5)

分析差分結(jié)果,若出現(xiàn)明顯尖峰則猜測正確,否則重復(fù)步驟3。

步驟4通過上述步驟猜測得到全部子密鑰,計(jì)算恢復(fù)密碼設(shè)備的密鑰。

1.3 秘密共享抵抗功耗攻擊原理

文獻(xiàn)[11]提出秘密共享的概念,并給出了(k,n)門限秘密共享方案。其基本思想是把一個(gè)完整的秘密分成若干份分給n個(gè)參與者,只有參與者達(dá)到k個(gè)或k個(gè)以上才可以重構(gòu)這個(gè)秘密,k稱為方案的門限值。下面介紹秘密共享如何抵御DPA攻擊[6]。

(6)

(7)

(8)

定義z=L(x)為域GF(2m)上的線性變換,將x和z分成n份單獨(dú)處理,即zi=L(xi),0≤i

(9)

該線性變換面對(duì)側(cè)信道攻擊時(shí)不會(huì)泄露任何信息,稱為安全電路,其特征是任意輸出的一份zi只與xi有關(guān),同理,多個(gè)輸入時(shí)有z=LL(x,y,…),zi只與(xi,yi…)有關(guān)?？紤]到線性變換與非線性變換具有相似的特征,可構(gòu)造非線性變換的安全電路。若對(duì)變換z=LL(x,y,…)來說,zi不完全取決于(xi,yi…)的值,則zi與x,y,…不相關(guān),zi的計(jì)算也不會(huì)泄露關(guān)于x,y,… 的信息,通過附加條件,可確保zi與z不相關(guān)。

定義z=N(x,y,…)為域GF(2m)上的非線性變換,函數(shù)f1,f2,…,fn需滿足以下3個(gè)性質(zhì):

性質(zhì)1(不完整性) 每個(gè)函數(shù)至少獨(dú)立于輸入變量x,y,…的一份:

z1=f1(x2,x3,…,xn,y2,y3,…,yn,…)

(10)

z2=f2(x1,x3,…,xn,y1,y3,…,yn,…)

(11)

?

zn=fn(x1,x3,…,xn-1,y1,y3,…,yn-1,…)

(12)

性質(zhì)2(正確性)n份輸出之和等于正確的輸出:

(13)

性質(zhì)3(均勻性) 若所有輸入x,y,… 和輸入分組xi,yi,…滿足條件2,且條件概率:

(14)

是一個(gè)常量,則稱z=N(x,y,…)滿足均勻性。

由于前一階段的輸出是下一階段的輸入,性質(zhì)3確保了數(shù)據(jù)在處理過程中能保持同步。

定理1滿足性質(zhì)1和性質(zhì)2的非線性變換,若有s個(gè)變量,其最小分組數(shù)n滿足:

n≥1+s

(15)

這表明要實(shí)現(xiàn)一個(gè)非線性變換至少需要分成3組[12]。由于并非所有變量都相互獨(dú)立,還可能存在其他需要更少分組的解決方法,據(jù)此推論:

推論1域GF(2m)上的非線性變換,若具有u個(gè)變量,則最大分組數(shù)n滿足:

n=1+2mu

(16)

定理2在一個(gè)電路實(shí)現(xiàn)中,若一組函數(shù)滿足性質(zhì)1和性質(zhì)2,且輸入滿足條件2,則所有的中間值結(jié)果獨(dú)立于輸入x,y,…和輸出z。同時(shí),任一單個(gè)函數(shù)fi的功耗和其他特性獨(dú)立于x,y,…和z。

定理2表明,完全可以構(gòu)造出一組函數(shù),滿足任一單個(gè)函數(shù)fi的功耗與輸入x,y,…和輸出z無關(guān),此時(shí)功耗與數(shù)據(jù)之間不存在依賴性,DPA攻擊不再發(fā)揮作用[12]。

2 共享S盒實(shí)現(xiàn)

在秘密共享S盒中,需要將仿射變換的輸入輸出分成3組進(jìn)行運(yùn)算[13],由于SM4算法S盒2次仿射變換具有相同的循環(huán)矩陣和行向量,且仿射變換本身具有線性關(guān)系,因此用秘密共享函數(shù)代替2次仿射變換,完成對(duì)輸入輸出數(shù)據(jù)的分組[14]。

2.1 秘密共享函數(shù)

利用1.1節(jié)給出的循環(huán)矩陣和行向量數(shù)值,定義秘密共享函數(shù)u=L(v,s,r),v為輸入,u為輸出,u、v均為8 bit數(shù)據(jù),令u=(a,b,c,d,e,f,g,h),v=(j,k,l,m,n,o,p,q),則有以下公式成立:

a=j+k+m+p+q+1

(17)

b=j+k+l+n+q+1

(18)

c=j+k+l+m+o

(19)

d=k+l+m+n+p

(20)

e=l+m+n+o+q+1

(21)

f=j+m+n+o+p

(22)

g=k+n+o+p+q+1

(23)

h=j+l+o+p+q+1

(24)

將共享函數(shù)分為3組,有u1=L1(v2,s2,r)。

a1=j2+k2+m2+p2+q2+s2+r

(25)

b1=j2+k2+l2+n2+q2+s2+r

(26)

c1=j2+k2+l2+m2+o2+r

(27)

d1=k2+l2+m2+n2+p2+r

(28)

e1=l2+m2+n2+o2+q2+s2+r

(29)

f1=j2+m2+n2+o2+p2+r

(30)

g1=k2+n2+o2+p2+q2+s2+r

(31)

h1=j2+l2+o2+p2+q2+s2+r

(32)

同理,有u2=L2(v3,s3,r)。

a2=j3+k3+m3+p3+q3+s3+r

(33)

b2=j3+k3+l3+n3+q3+s3+r

(34)

c2=j3+k3+l3+m3+o3+r

(35)

d2=k3+l3+m3+n3+p3+r

(36)

e2=l3+m3+n3+o3+q3+s3+r

(37)

f2=j3+m3+n3+o3+p3+r

(38)

g2=k3+n3+o3+p3+q3+s3+r

(39)

h2=j3+l3+o3+p3+q3+s3+r

(40)

同理,有u3=L3(v1,s1,r)。

a3=j1+k1+m1+p1+q1+s1+r

(41)

b3=j1+k1+l1+n1+q1+s1+r

(42)

c3=j1+k1+l1+m1+o1+r

(43)

d3=k1+l1+m1+n1+p1+r

(44)

e3=l1+m1+n1+o1+q1+s1+r

(45)

f3=j1+m1+n1+o1+p1+r

(46)

g3=k1+n1+o1+p1+q1+s1+r

(47)

h3=j1+l1+o1+p1+q1+s1+r

(48)

其中,s是常量,滿足s=s1+s2+s3,共享函數(shù)實(shí)現(xiàn)流程如圖2所示。

圖2 共享函數(shù)實(shí)現(xiàn)流程

2.2 秘密共享S盒實(shí)現(xiàn)

由1.3節(jié)可知,滿足秘密共享S盒3個(gè)分組性質(zhì)的最小分組數(shù)為3,因此,選用3個(gè)分組來構(gòu)造SM4算法共享S盒時(shí)可以減少運(yùn)算量,降低功率消耗和面積,同時(shí)保證其抵抗高階DPA攻擊及glitch攻擊的能力。本文基于秘密共享的SM4算法S盒具體實(shí)現(xiàn)方案分為3個(gè)階段,如圖3所示。

圖3 秘密共享S盒具體實(shí)現(xiàn)

第1階段,通過秘密共享函數(shù)將進(jìn)入S盒的8 bit信息分成3組8 bit信息,進(jìn)入Map部分進(jìn)行第同構(gòu)映射變換,得到3組8 bit信息a1、a2、a3,再將每組8 bit信息分成2組4 bit信息,共得到6組4 bit信息b1、c1、b2、c2、b3、c3。將6組4 bit信息分成S1(b1,b2,b3)和S2(c1,c2,c3)2組,S1、S2進(jìn)行3次異或運(yùn)算后輸入平方計(jì)數(shù)器,得到3組4 bit信息d1、d2、d3,同時(shí)將S1、S2輸入GF(24)乘法器,得到3組4 bit信息e1、e2、e3。d1、d2、d3和e1、e2、e3進(jìn)行3次異或運(yùn)算后得到f1、f2、f3,將f1、f2、f3輸入寄存器進(jìn)行分組。

在乘法器中,由于2個(gè)輸入每個(gè)分成3組相乘時(shí),不滿足均勻性的性質(zhì)[12],因此,這里采用虛擬值的方法[15],在進(jìn)入乘法器時(shí)添加一個(gè)4 bit虛擬值z(mì),并將z分成3組4 bit信息z1、z2、z3,與b1、c1、b2、c2、b3、c3同時(shí)進(jìn)入GF(24)乘法器,得到e1、e2、e3,運(yùn)算公式如下:

e1=b2c2⊕b2c3⊕b3c2⊕b2z2⊕

b3z3⊕c2z2⊕c3z3

(49)

e2=b3c3⊕b1c3⊕b3c1⊕b3z3⊕

b1z1⊕c3z3⊕c1z1

(50)

e3=b1c1⊕b1c2⊕b2c1⊕b1z1⊕

b2z2⊕c1z1⊕c2z2

(51)

第2階段,把f1、f2、f3輸入寄存器重新分組,得到4組4 bit信息f1*、f2*、f3*、f4*,而后輸入反相器,采用分解法求逆[16],得到4組4 bit信息g1*、g2*、g3*、g4*。分解法可有效減少運(yùn)算次數(shù),降低功耗,具體方程式如下:

(g1*,g2*,g3*,g4*)=Inv(f1*,f2*,f3*,f4*)

(52)

g1*=f2*⊕f3*⊕f1*f3*⊕

f2*f3*⊕f2*f3*f4*

(53)

g2*=f4*⊕f1*f3*⊕f2*f3*⊕

f2*f4*⊕f1*f3*f4*

(54)

g3*=f1*⊕f2*⊕f1*f3*⊕

f1*f4*⊕f1*f2*f4*

(55)

g4*=f2*⊕f1*f3*⊕f1*f4*⊕

f2*f4*⊕f1*f2*f3*

(56)

將g1*、g2*、g3*、g4*輸入寄存器重新得到3組4 bit信息g1、g2、g3,輸出進(jìn)入第3階段。

第3階段,將b1、b2、b3和g1、g2、g3輸入GF(24)乘法器,采用虛擬值方法得到3組4 bit信息h1、h2、h3,同時(shí)將c1、c2、c3和g1、g2、g3輸入GF(24)乘法器得到3組4 bit信息k1、k2、k3。將得到的h1、h2、h3與g1、g2、g3輸入Inv.AT.lin.lmap部分,進(jìn)行第2次仿射變換及相應(yīng)的線性變換得到3組8 bit信息m1、m2、m3,將m1、m2、m3相加即得S盒最終輸出結(jié)果。

3 安全性分析及實(shí)驗(yàn)驗(yàn)證

3.1 安全性分析

3.1.1 抗高階功耗攻擊分析

高階DPA是利用密碼設(shè)備內(nèi)部的幾個(gè)中間值的聯(lián)合泄露信息進(jìn)行的攻擊[17]。本文采用基于秘密共享方法的設(shè)計(jì)實(shí)現(xiàn)了SM4的抗功耗攻擊S盒方案,整個(gè)實(shí)現(xiàn)過程滿足秘密共享對(duì)于分組的要求。在第一階段,輸入被分成了3組進(jìn)行運(yùn)算,其中間值a1、a2、a3與f1、f2、f3符合秘密共享分組要求,即滿足正確性、不完整性和均勻性。因此,有f1、f2、f3互相獨(dú)立且與a1、a2、a3線性無關(guān)。在第2階段,引入分解法,中間值f1、f2、f3求逆得到g1、g2、g3,因此有g(shù)1、g2、g3互相獨(dú)立且與f1、f2、f3線性無關(guān)。在第3階段,由g1、g2、g3得到m1、m2、m3,滿足m1、m2、m3均互相獨(dú)立且與g1、g2、g3線性無關(guān)。因此,當(dāng)攻擊者進(jìn)行HO-DPA攻擊時(shí),僅能得到3組獨(dú)立無關(guān)的中間值,無法通過對(duì)這3組中間值的統(tǒng)計(jì)分析來獲取關(guān)于密鑰的任何信息,從而達(dá)到抵御高階功耗攻擊的目的。因此,本文所設(shè)計(jì)的SM4加密方案能夠有效抵御HO-DPA攻擊。

3.1.2 抗glitch攻擊分析

glitch攻擊是利用電路輸入信號(hào)到達(dá)時(shí)間的不同,進(jìn)而引起輸出產(chǎn)生臨時(shí)狀態(tài)的特點(diǎn)來獲取信息[17]。本文采用基于秘密共享的SM4抗功耗攻擊S盒方案,由于S盒輸入數(shù)據(jù)被分成3個(gè)分組進(jìn)行計(jì)算,因此發(fā)生在一個(gè)分組上的glitch與發(fā)生在另一個(gè)分組上的glitch并不同步,對(duì)攻擊者而言,很難通過一組分組上的glitch攻擊來獲取整個(gè)電路的信息。因此,本文的秘密共享S盒方案能夠抵御glitch攻擊。

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

基于TSMC 60 nm工藝,在相同的條件下,仿真實(shí)現(xiàn)SM4算法的復(fù)合域掩碼方案,同時(shí)實(shí)現(xiàn)本文的秘密共享S盒方案。為了便于比較,復(fù)合域掩碼方案與本文掩碼方案均在TSMC 60 nm工藝下,約束頻率是50 MHz,性能指標(biāo)如表1所示。

表1 算法電路實(shí)現(xiàn)比較

本文S盒方案采用秘密共享方法實(shí)現(xiàn),將S盒輸入分成3組,并保證分組運(yùn)算后的中間值結(jié)果互相獨(dú)立,即分組運(yùn)算后的中間值功耗與分組前的中間值之間不相關(guān),保證了本文S盒具有抵御高階DPA攻擊及glitch攻擊的安全性?，F(xiàn)有方案的S盒比較如表2所示。

表2 現(xiàn)有方案的S盒比較

4 結(jié)束語

SM4作為我國自行設(shè)計(jì)的分組密碼標(biāo)準(zhǔn),采用32輪非線性迭代結(jié)構(gòu),具有很高的安全性,但仍然面臨DPA攻擊的巨大風(fēng)險(xiǎn)。現(xiàn)有的防護(hù)DPA攻擊的掩碼方案雖然很多,但多數(shù)局限性較強(qiáng),且防護(hù)能力較弱。本文通過對(duì)秘密共享抵抗DPA攻擊的原理分析及文獻(xiàn)[8]提出的AES算法S盒共享實(shí)現(xiàn)方案的研究,構(gòu)造了一個(gè)適用于SM4 算法實(shí)現(xiàn)的新型共享S盒,新的S盒通過利用秘密共享函數(shù)代替仿射變換,在乘法器分組中采用虛擬值法,并在反相器中引入分解法,使得本文實(shí)現(xiàn)方案具有較少的運(yùn)算次數(shù)和較低的空間占比。安全性分析和實(shí)驗(yàn)結(jié)果表明,該方案對(duì)高階DPA攻擊乃至glitch攻擊具有較強(qiáng)的抵抗能力。