抗簡單功耗攻擊的SM2原子算法

韓曉薇　烏力吉　王蓓蓓　王　安

(清華大學微電子學研究所　北京　100084)

?

抗簡單功耗攻擊的SM2原子算法

韓曉薇烏力吉王蓓蓓王安

(清華大學微電子學研究所北京100084)

(hanxiaoweihxw@gmail.com)

SM2算法是中國國家密碼管理局頒布的商用橢圓曲線公鑰密碼標準算法.傳統密碼算法通常存在安全漏洞，攻擊者往往針對算法中的安全薄弱環節展開攻擊，分析提取密鑰，對密碼系統和人們的財產安全構成很大威脅.功耗攻擊是最常見的攻擊方式，它具有較小密鑰搜索空間及較高分析效率等諸多優點.功耗攻擊利用密碼算法運行過程中的功耗泄漏，采集功耗曲線分析恢復得到密鑰.為有效抵抗功耗攻擊，提高SM2算法安全性，參考國際橢圓曲線密碼算法，將原子概念運用到SM2中，提出一種新型結構的原子算法.經理論分析，在運算量方面相比基本算法降低了27.4%，并且均低于已有的原子算法.經由SAKURA-GFPGA仿真驗證結果表明，能夠成功抵抗簡單功耗攻擊.

SM2算法；密碼系統；功耗攻擊；橢圓曲線密碼算法；原子算法

Fig. 1　Architecture of SM2 algorithms.圖1　SM2算法結構圖

橢圓曲線密碼體制[1-2]自1985年被提出以來在理論探究和實際應用方面均逐漸成為研究的重點.相比傳統公鑰加密算法RSA，橢圓曲線密碼體制安全性高、計算速度快、存儲空間小、帶寬要求低、計算參數少且簽名短小，更加適用于限制資源的系統.在商用密碼領域，中國不斷推出自主定義的密碼算法.2010年，國家密碼管理局公布了SM2橢圓曲線公鑰密碼標準算法[3].經各方不斷研究論證，SM2目前已應用于多種商用密碼通用產品中，并有望與其他國密算法一起登上國際密碼舞臺.

傳統密碼攻擊按攻擊主動性可分為側信道攻擊和故障攻擊兩大類[4-5].側信道攻擊通常被稱為被動攻擊，攻擊者通過采集密碼運算過程中泄露的側信道信息恢復密鑰.故障攻擊則通過人為注入故障(如時鐘毛刺、電壓毛刺等)，利用錯誤結果恢復密鑰.側信道攻擊包含功耗攻擊與電磁攻擊，其中功耗攻擊具有較小密鑰搜索空間和較高分析效率，是目前攻擊者們最常采用的攻擊方式，對商用智能卡芯片安全構成很大威脅.隨著國家由磁條卡向芯片卡計劃的不斷推進，研究SM2算法的抗功耗攻擊能力對于金融安全意義重大.

SM2包含加密、解密、簽名、驗簽和密鑰交換5部分，其中多次涉及標量乘操作.標量乘又稱點乘，即為給定橢圓曲線上的一點P與整數d，求取多倍點dP.標量乘的逆運算是已知P與dP，求取標量d，此即為求解橢圓曲線離散對數問題(ECDLP).該過程計算復雜度很高，從而保證了SM2算法的安全性.

現有攻擊方式大多針對標量乘，致力于不依靠求解ECDLP而恢復d.標量乘運算的中間過程涉及大量邏輯門的翻轉，不同的步驟會呈現不同的功耗.簡單功耗攻擊(simplepowerattack，SPA)[6]是最早提出的一種攻擊，它通過分析SM2運算過程中泄露的功耗信息得到點加(pointaddition)與倍點(pointdoubling)的執行規律，只需1條功耗曲線即可恢復密鑰.2004年，Chevallier-Mames等人[7]提出側信道原子算法的概念，其原理是將公鑰算法的中間過程分解為具有相同運算規律的原子塊，從而將功耗曲線平均化，能夠在不增加開銷的條件下成功抵抗SPA.

本文將原子算法的概念運用到SM2算法中，結合SM2的特殊性，在前人基礎上改進優化中間算法，旨在為抗SPA提供多種思路，最后與已有抗SPA的算法進行對比.

1　背景介紹

1.1SM2算法及功耗攻擊

SM2公鑰密碼算法體系中簽名與解密因與私鑰有關而成為攻擊與防護的重點.5部分算法中都包含橢圓曲線標量乘，標量乘由大量橢圓曲線倍點與點加組成，其包含關系如圖1所示：

功耗攻擊利用密碼算法運算過程中的功耗泄漏恢復密鑰.密碼芯片屬于特殊的數字電路，數字電路由大量晶體管組成，晶體管的翻轉會影響功耗變化.總的來說，密碼芯片的功耗由4部分組成：與密碼運算相關的晶體管翻轉產生的功耗、與密碼運算無關的晶體管翻轉產生的功耗、漏電流產生的功耗和噪聲功耗.由此可見，密碼芯片的功耗與算法運算的指令和數據密切相關，這為功耗攻擊提供了可能.目前已有多種功耗攻擊方式：SPA、差分功耗攻擊(differentialpowerattack，DPA)[8]、相關功耗攻擊(correlationpowerattack，CPA)等.

標量乘決定著SM2算法的性能及安全性，多種快速算法及安全防護對策被相繼提出.但是，大多數安全對策均在不同程度上增加了運算量，研究不增加運算量的安全對策意義重大.最基本標量乘算法是二進制擴展法，將標量d用二進制表示，從左至右或從右至左依次判斷每一位，若為0則執行1次倍點，為1執行1次倍點與1次點加，如算法1所示.

算法1. 二進制擴展法.

輸入：d=(dn-1,dn-2,…,d1,d0)2，P∈E(Fq)；

輸出：Pd=dP.

① Q0←∞，Q1←P；

② 對于i從n-1到0重復執行

Q0←2Q0；

若di,=1,則Q0←Q0+Q1；

③ 返回Q0.

采用算法1，攻擊者利用點加與倍點功耗的不同，只需1條功耗曲線便可觀察出操作規律，進而得到密鑰，此即為SPA，如圖1所示.

之后，Coron提出總執行倍點與點加(double-and-addalways)算法[9]，該算法在di=0時添加冗余操作，保證無論di是0或1均執行1次倍點和1次點加，如算法2所示.如此可抵抗SPA，但同時增加了一倍的點加，大大增加了運算量.

算法2. 總執行點加與倍點法.

輸入：d=(dn-1,dn-2,…,d1,d0)2，P∈E(Fq)；

輸出：Pd=dP.

① Q0←∞，Q2←P；

② 對于i從n-1到0重復執行

Q0←2Q0；

Q1←Q0+Q2；

若di=1,則Q0←Q0；

否則Q0←Q1；

③ 返回Q0.

側信道原子算法[7,10-11]的概念將密碼算法表示為原子結構，使得算法執行過程中循環處理相同的指令原子塊，如此功耗曲線呈現相同規律變化，能夠成功抵抗SPA.

1.2SM2點加倍點介紹

設域K的特征為2或3，SM2使用定義在域K上的橢圓曲線y2= x3-3x+b.對這條曲線而言，倍點與點加(2個互不相同且互不為負的點相加)運算需要用到域上的求逆與乘法，而求逆操作比乘法耗費大量時間，因此將運算轉化到投影坐標系是常用的解決方法.其中，雅可比坐標下的倍點計算速度最快，雅可比與仿射混合坐標下的點加計算速度最快.

倍點：將橢圓曲線轉化到仿射坐標系下，然后利用仿射坐標形式的倍點公式計算2P，消去分母后得到雅可比坐標形式的計算公式：

(1)

由式(1)可知，通過4次域的平方和4次域的乘法能夠計算出X3，Y3，Z3.

C←B2，D←CX1，X3←A2-2D，

Y3←A(D-X3)-C22，Z3←BZ1.

點加：將橢圓曲線轉化到仿射坐標系下，令P=(X1:Y1:Z1)∈E，Z1≠0，Q=(X2:Y2:1)，假設P≠±Q.利用仿射坐標形式的點加公式計算P+Q，消去分母后得到雅可比坐標形式的計算公式：

(2)

由式(2)可知，通過3次域的平方和8次域的乘法能夠計算出X3，Y3，Z3.

E←C-X1，F←D-Y1，G←E2，H←GE，

I←X1G，X3←F2-(H+2I)，

Y3←F(I-X3)-Y1H，Z3←Z1E.

上述點加公式中，Q為固定點，若Q為非固定點(X1:Y1:Z1)，則需要4次域的平方和12次域的乘法.

2　改進的原子算法

實際實現中模平方通常用模乘代替.Chevallier-Mames等人[7]的方案中，原子塊為MUL-ADD-REV-ADD結構，即模乘-加法-求反-加法.本文將原子概念與SM2結合，調整寄存器運算順序，把點加倍點均表示為模乘-加法-減法(MUL-ADD-SUB)結構的指令原子塊.

如圖2所示，傳統算法根據di不同執行不同指令，令Π0代表倍點，Π1代表點加.改進算法將Π0與Π1用統一的原子塊Г表示，Г包含1次模乘、1次加法和1次減法，適用于雅可比坐標系下的標量乘.

Fig. 2　Atomic structure of scalar multiplication.圖2　標量乘原子結構示意圖

算法3. 原子標量乘算法.

輸出：Pd=dP.

R0←X1，R1←Y1，R2←Z1，R6←X1，R7←Y1；

i←m-2，s←1.

① 對于i≥0重復執行：

k←(s)(k+1)；

s←di(kdiv18)+(di)(kdiv7)；

i←i-s；

② 返回(R1,R2,R3).

P為非固定點時，點加需16次模乘，算法3中的s替換為di(kdiv23)+(di)(kdiv7)，寄存器下標矩陣取)0≤k≤230≤l≤8.考慮到此時倍點需8次循環，點加需16次循環，二者均為8的倍數，變換算法如算法4所示.在循環內部嵌套1個周期為8的for循環，設for循環為原子塊Γ ′，通過k與s控制i的變化，di=0時執行1次Γ ′，di=1時執行3次Γ ′，即倍點執行1次Γ ′，點加執行2次Γ ′.如此，可在具有相同安全性的基礎上節省多次計算k，s和i的操作，進一步降低計算量.

算法4. 改進原子標量乘算法.

輸出：Pd=dP.

R0←X1，R1←Y1，R2←Z1，R6←X1，R7←Y1；

i←m-2，s←1.

① 對于i≥0重復執行：

s←di(kdiv16)+(di)；

對于j從0至7重復執行：

j=j+1；

i←i-s；

② 返回(R1,R2,R3).

3　性能評估

3.1安全性分析

傳統SM2算法中，攻擊者很容易通過觀察功耗波形得到點加與倍點的運算規律，進而推算密鑰.本文將原子概念運用到SM2算法中，把SM2中的點加與倍點用相同的原子塊表示，執行點加和倍點時功耗波形將不再存在差別，攻擊者無法得到運算規律，能夠成功抵抗SPA.

為了驗證該方案的安全性，本文基于傳統算法與所提方案分別進行電路設計實現，并在如圖3所示的SAKURA-G開發板上成功驗證.開發工具為ISEDesignSuite14.4，FPGA型號為XilinxSpartan-6 (XC6SLX75-2CSG484C)，時鐘頻率為48MHz.

Fig. 3　SAKURA-G FPGA development board.圖3　SAKURA-G FPGA開發板

功耗采集平臺如圖4所示.硬件電路通過Modelsim功能驗證后，PC機將SM2運算電路下載至主FPGA，將控制電路下載至控制FPGA，外部向開發板提供3.3V電源.觸發控制電路工作，控制電路傳送地址、數據和控制等信號給主FPGA中的SM2IP核，示波器通過功耗采集接口采集SM2運行過程的功耗波形，如圖5所示.

Fig. 4　Architecture of power acquisition platform.圖4　功耗采集平臺結構示意圖

Fig. 5　Power wave of SM2 intermediate operation process.圖5　SM2中間運行過程功耗波形

分別采集傳統算法和本文算法對應的功耗曲線，進行攻擊.對比結果如圖6所示，采用傳統算法的功耗波形中點加與倍點呈現明顯不同的尖峰，可以準確區分點加與倍點，無法抵抗SPA，而采用本文方案的波形中點加與倍點具有相同運算規律，3個尖峰1組，與理論中MUL-ADD-SUB原子結構相符，成功驗證本文方案能夠抵抗SPA，達到預期目標.

Fig. 6　Comparison of attacks results.圖6　攻擊結果對比圖

3.2運算量分析

傳統抗SPA的方法為總執行點加倍點算法，取該算法和前人原子算法與本文方案進行對比，結果如表1所示，其中文獻[7，10]與本文均取原型為二進制展開法的改進算法參與對比，點加取固定點加.D，A代表基本點加倍點，D1，A1代表文獻[7]中的點加倍點，D2，A2代表文獻[10]中的點加倍點，D3，A3代表本文中的點加倍點，M代表模乘，S代表模平方，a代表加減法，R代表求反.D=4M+6S+7a，A=8M+3S+9a.表2為多種原子結構對比，經統計知，D1=4M+6S+20a+10R，A1=8M+3S+22a+11R，D2=4M+4S+24a+16R，A2=8M+3S+33a+22R，D3=4M+4S+16a，A3=8M+3S+22a.令S≈0.8M，a≈0.1M，R≈0.1M.

Table 1　Comparison of Cost and Applicable Scope表1　 運算量及適用范圍對比

Table 2　Comparison of Different Atomic Structures表2　不同原子結構對比

總執行點加倍點的算法添加了一倍點加操作，計算效率較低，文獻[7，10]中方案因原子結構較長，為了構成原子塊添加的冗余操作也遠大于本文方案.由于文中優化基于SM2標準參數曲線，本文方案僅適用于SM2算法.由表2容易看出，本文算法運算量得到顯著降低，比傳統算法節約了27.4%，比文獻[7]中算法多節約了17.1%，比文獻[10]則多節約了19.5%.

4　結束語

本文將原子概念與SM2算法相結合，提出一種新型MUL-ADD-SUB結構的改進原子算法，對其安全性和性能進行了理論評估.經FPGA實際驗證，證明所提方案能夠有效抵抗SPA.

[1]Koblitz,N.Ellipticcurvecryptosystems[J].MathematicsofComputation, 1987, 48(177): 203-209

[2]MillerVS.Useofellipticcurvesincryptography[C] //ProcofAdvancesinCryptology-CRYPTO’85.Berlin:Springer, 1986: 417-426

[3]ChineseCryptographyAdministration.GM//T0003—2012.SM2ellipticcurvepublickeycryptographicalgorithms[S].Beijing:NationalCommercialCryptographyManagementOffice, 2010 (inChinese)

(國家密碼管理局.GM//T0003—2012.SM2橢圓曲線公鑰密碼算法[S]. 北京: 國家商用密碼管理辦公室, 2010)

[4]JoyeM.Ellipticcurvesandside-channelanalysis[J].STJournalofSystemResearch, 2003, 4(1): 17-21

[5]FanJ,GuoX,DeMulderE,etal.State-of-the-artofsecureECCimplementations:Asurveyonknownside-channelattacksandcountermeasures[C] //Procofthe2010IEEEIntSymponHardware-OrientedSecurityandTrust(HOST).Piscataway,NJ:IEEE, 2010: 76-87

[6]WalterCD.SimplepoweranalysisofunifiedcodeforECCdoubleandadd[G] //LNCS3156:CryptographicHardwareandEmbeddedSystems-CHES2004.Berlin:Springer, 2004: 191-204

[7]Chevallier-MamesB,CietM,JoyeM.Low-costsolutionsforpreventingsimpleside-channelanalysis:Side-channelatomicity[J].IEEETransonComputers, 2004, 53(6): 760-768

[8]KocherP,JaffeJ,JunB.Differentialpoweranalysis[C] //ProcofAdvancesinCryptology-CRYPTO’99.Berlin:Springer, 1999: 388-397

[9]MamiyaH,MiyajiA,MorimotoH.EfficientCounter-measuresAgainstRPA,DPA,andSPA[M].Berlin:Springer, 2004

[10]WangHong,ZhuFeng.Ellipticcurvescalarmultiplicationalgorithmsbasedonside-channelatomicconcept[J].JournalofElectronicsTechnology, 2012, 25(4): 16-20 (inChinese)

(王宏, 朱峰. 基于邊信道原子的橢圓曲線標量乘算法[J]. 電子科技, 2012, 25(4): 16-20)

[11]QinBaodong,KongFanyu.Secureandfastellipticcurvescalarmultiplicationalgorithmsbasedonside-channelatomicconcept[J].JournalofComputerApplications, 2009, 29(11): 2983-2986 (inChinese)

(秦寶東, 孔凡玉. 基于邊帶信道原子的安全快速橢圓曲線密碼點乘算法[J]. 計算機應用, 2009, 29(11): 2983-2986)

HanXiaowei,bornin1991.MasteroftheInstituteofMicroelectronicsofTsinghuaUniversity.HermainresearchinterestiscoutermeasuresagainstsidechannelanalysisofSM2algorithms.

WuLiji,bornin1965.PhD,associateprofessorandPhDsupervisoroftheInstituteofMicroelectronicsofTsinghuaUniversity.Hismainresearchinterestsincludeintegratedcircuitsystemandcommercialinformationsecurity.

WangBeibei,bornin1983.MasterandengineeroftheInstituteofMicroelectronicsofTsinghuaUniversity.Hermainresearchinterestischipinformationsecurity.

WangAn,bornin1983.AssociateresearcherandpostdoctoralresearcheroftheInstituteofMicroelectronicsofTsinghuaUniversity.Hismainresearchinterestsincludecrypto-graphicengineeringandsidechannelattackanddefensetechnology.

AtomicAlgorithmAgainstSimplePowerAttackofSM2

HanXiaowei,WuLiji,WangBeibei,andWangAn

(Institute of Microelectronics, Tsinghua University, Beijing 100084)

SM2algorithmsarecommercialellipticcurvepublic-keyalgorithms,whicharereleasedbyChineseCryptographyAdministrationandsimilartoECC.Traditionalcryptographicalgorithmsalwayshavesecurityflaws.Attackersoftenattackonsecurityweaknessesofalgorithmsandanalyzethesecret-key,whichposesgreatthreattocryptographicsystemsandpeoples’property.Therearevariouskindsofattacks,suchaspowerattack,faultattackandelectromagneticattack.Amongtheseattacks,powerattackisthemosttraditionalone,whichhasmanyadvantagessuchassmallsecret-keysearchingspaceandhighanalysisefficiency.Usually,powerattackutilizesthepowerleakageduringoperationprocessesofcryptographicalgorithms,acquirespowerwavesandretrievesthesecretkey.InordertoresistpowerattackandenhancethesecurityofSM2algorithms,thisarticlelearnsfromellipticcurvecryptographyalgorithms,appliestheatomicconceptintoSM2andproposesanovelatomicalgorithm.Accordingtotheoreticalcomparisonbetweentheproposedalgorithmandotherformeralgorithms,itshowsthattheproposedalgorithmsaves27.4%ofcomputationincomparisontodouble-and-addalwaysalgorithm.Besides,ithaslesscomputationamountthanotheratomicalgorithms.Furthermore,implementationhasbeenfulfilledonSAKURA-GFPGAboard.Simulationresultsdemonstratethattheproposedalgorithmcanresistsimplepowerattacksuccessfully.

SM2;cryptographicsystem;powerattack;ellipticcurvecryptographicalgorithm;atomicalgorithm

2015-01-19；

2015-12-29

“核高基”國家科技重大專項基金項目(2014ZX01032205，2014ZX01032401-001-Z05)；國家自然科學基金項目(61402252，61402536)；信息保障技術重點實驗室開放基金項目(KJ-14-006)；北京理工大學青年教師學術啟動計劃項目

烏力吉 (lijiwu@mail.tsinghua.edu.cn)

TP309

ThisworkwassupportedbythetheNationalScienceandTechnologyMajorProjectsofHegaoji(2014ZX01032205, 2014ZX01032401-001-Z05),theNationalNaturalScienceFoundationofChina(61402252, 61402536),theFoundationofScienceandTechnologyonInformationAssuranceLaboratory(KJ-14-006),andtheBeijingInstituteofTechnologyResearchFundProgramforYoungScholars.