基于秘密共享的SM4算法S盒實現方案

李新超,鐘衛東,劉明明,李 棟

(武警工程大學 a.網絡與信息安全武警部隊重點實驗室; b.密碼工程學院,西安 710086)

0 概述

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

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

針對SM4算法如何有效防御DPA攻擊問題,本文根據SM4算法S盒的特點,在對Bilgin的共享S盒分組實現方案進行分析研究的基礎上,結合文獻[5]的工作,構造了一個適用于SM4算法的低功耗共享S盒。

1 相關知識

1.1 S盒

S盒作為SM4算法唯一的非線性部分,是評估SM4算法安全性的關鍵。2007年,文獻[2]通過對SM4算法S盒的研究,成功獲得了S盒的代數表達式,并給出了相關參數的具體值。通過實驗驗證發現,該表達式及相關參數值能夠滿足所有的S盒取值。

代數表達式為:

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

(1)

不可約多項式為:

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

(2)

循環矩陣為:

(3)

行向量為:

(4)

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

1.2 差分功耗分析

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

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

步驟2對密碼設備輸入大量不同數據,測量能量消耗軌跡mi及ti。

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

(5)

分析差分結果,若出現明顯尖峰則猜測正確,否則重復步驟3。

步驟4通過上述步驟猜測得到全部子密鑰,計算恢復密碼設備的密鑰。

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

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

(6)

(7)

(8)

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

(9)

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

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

性質1(不完整性) 每個函數至少獨立于輸入變量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)

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

(13)

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

(14)

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

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

定理1滿足性質1和性質2的非線性變換,若有s個變量,其最小分組數n滿足:

n≥1+s

(15)

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

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

n=1+2mu

(16)

定理2在一個電路實現中,若一組函數滿足性質1和性質2,且輸入滿足條件2,則所有的中間值結果獨立于輸入x,y,…和輸出z。同時,任一單個函數fi的功耗和其他特性獨立于x,y,…和z。

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

2 共享S盒實現

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

2.1 秘密共享函數

利用1.1節給出的循環矩陣和行向量數值,定義秘密共享函數u=L(v,s,r),v為輸入,u為輸出,u、v均為8 bit數據,令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)

將共享函數分為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,共享函數實現流程如圖2所示。

圖2 共享函數實現流程

2.2 秘密共享S盒實現

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

圖3 秘密共享S盒具體實現

第1階段,通過秘密共享函數將進入S盒的8 bit信息分成3組8 bit信息,進入Map部分進行第同構映射變換,得到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進行3次異或運算后輸入平方計數器,得到3組4 bit信息d1、d2、d3,同時將S1、S2輸入GF(24)乘法器,得到3組4 bit信息e1、e2、e3。d1、d2、d3和e1、e2、e3進行3次異或運算后得到f1、f2、f3,將f1、f2、f3輸入寄存器進行分組。

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

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*。分解法可有效減少運算次數,降低功耗,具體方程式如下:

(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,輸出進入第3階段。

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

3 安全性分析及實驗驗證

3.1 安全性分析

3.1.1 抗高階功耗攻擊分析

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

3.1.2 抗glitch攻擊分析

glitch攻擊是利用電路輸入信號到達時間的不同,進而引起輸出產生臨時狀態的特點來獲取信息[17]。本文采用基于秘密共享的SM4抗功耗攻擊S盒方案,由于S盒輸入數據被分成3個分組進行計算,因此發生在一個分組上的glitch與發生在另一個分組上的glitch并不同步,對攻擊者而言,很難通過一組分組上的glitch攻擊來獲取整個電路的信息。因此,本文的秘密共享S盒方案能夠抵御glitch攻擊。

3.2 實驗結果

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

表1 算法電路實現比較

本文S盒方案采用秘密共享方法實現,將S盒輸入分成3組,并保證分組運算后的中間值結果互相獨立,即分組運算后的中間值功耗與分組前的中間值之間不相關,保證了本文S盒具有抵御高階DPA攻擊及glitch攻擊的安全性。現有方案的S盒比較如表2所示。

表2 現有方案的S盒比較

4 結束語

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