密碼芯片上高效的ECC抗功耗攻擊方案

湯 震

(黃淮學(xué)院，河南駐馬店 463000)

0 引 言

功耗攻擊技術(shù)給密碼芯片的安全帶來了極大的威脅，但由于密碼芯片自身資源限制，造成其了在采用防御功耗攻擊的方法后，將會降低密碼芯片運算效率，這就產(chǎn)生了效率與安全的矛盾，如何解決這一矛盾則成為密碼芯片研究的熱點問題。功耗攻擊是Paul Kocher在1998年首先提出的密碼分析方法，主要工作原理是密碼芯片運行時，不同操作產(chǎn)生的功耗不同，通過采集這些泄露的功耗信息，并分析功耗之間的差異即可獲取相關(guān)密鑰信息。而且功耗分析具有易于實現(xiàn)、成功率高等諸多良好攻擊特性，因而相較于傳統(tǒng)數(shù)學(xué)攻擊方法而言，功耗分析對密碼芯片所帶來的安全威脅更嚴(yán)重[1-2]。一般來說，功耗分析因攻擊手段不同主要分為兩類：簡單功耗攻擊技術(shù)(Simple Power Attack, SPA)和差分功耗攻擊技術(shù)(Differential Power Attack, DPA)。其中，密碼芯片中的主流算法大都是采用橢圓曲線密碼(Elliptic Curve Cryptogram, ECC)算法，這主要是因為ECC算法與傳統(tǒng)非對稱密碼算法相比而言，在安全性相同的情況下ECC算法有諸如密鑰長度更短，存儲空間更小等一系列優(yōu)勢，這使得ECC算法更能夠適合用在資源受限的系統(tǒng)[1]。然而，當(dāng)前出現(xiàn)了許多針對ECC的功耗攻擊，包括零值寄存器攻擊(Zero-value Power Attack, ZPA)與零值點攻擊(Refined Power Attack, RPA)[3-4]。國內(nèi)外學(xué)者關(guān)于密碼芯片的抗功耗攻擊方面做了大量研究工作。Mamiya H等人[5]給出了一種基于窗口隨機(jī)化初始點的ECC抗功耗攻擊方案(Window-Based Random Initial Point, WBRIP)，基本思想是通過將標(biāo)量的二進(jìn)制編碼進(jìn)行窗口化，在一個窗口內(nèi)實現(xiàn)掩蓋所執(zhí)行的點加運算與倍點運算次數(shù)的目的，致使攻擊者無法從中間值猜測運算過程中所執(zhí)行的具體操作及相關(guān)步驟，盡管WBRIP可以抵抗多種功耗攻擊，但是其運算效率需進(jìn)一步提高。張濤等人[6]給出了一種固定窗口寬度為w的非鄰接表示形式的ECC抗功耗攻擊算法(Fractional Width-w Non Adjacent From, FWNAF)，主要思想是利用二進(jìn)制的非鄰接表示形式來優(yōu)化編碼，減少在抵抗功耗攻擊過程中所需添加偽操作的次數(shù)，從而實現(xiàn)運算效率的提升。文獻(xiàn)[7]給出一種高效的窗口隨機(jī)化初始點ECC抗功耗攻擊算法(Efficient-Based Random Initial Point, EBRIP)，主要思想是將標(biāo)量的二進(jìn)制編碼表示成窗口寬度是w的非鄰接表示形式，并將其分成整數(shù)部分與分?jǐn)?shù)部分可實現(xiàn)抵抗SPA，接著再將基點分成固定部分與可變部分可實現(xiàn)抵抗DPA、ZPA與RPA，并且也可提升運算效率。奇系數(shù)Comb算法是ECC標(biāo)量乘法運算的一種快速計算方法，為保證算法能夠抵抗功耗攻擊并進(jìn)一步有效提升運算效率，文中通過在奇系數(shù)Comb標(biāo)量乘算法中結(jié)合添加偽操作與基點掩碼技術(shù)，給出了一種密碼芯片上基于奇系數(shù)Comb算法的ECC抗功耗攻擊算法(Resisting Power Attacks algorithm of ECC based on Odd-only Comb Method, RPAOCM )，同BR、WBRIP及FWNAF算法相比，所給抗功耗攻擊算法不僅有相同的抗功耗攻擊安全性，而且具有更高的運算效率[2-5]。

1 奇系數(shù)Comb標(biāo)量乘算法

ECC標(biāo)量乘快速算法主要有兩類，一類是通過提高底層域運算來實現(xiàn)，另一類是對標(biāo)量進(jìn)行重新編碼來實現(xiàn)。其中，奇系數(shù)Comb標(biāo)量乘算法屬于第二類快速算法，同時也是常用的ECC標(biāo)量乘快速算法，與其它同類快速算法(諸如雙基數(shù)系統(tǒng)快速算法[8]、階乘展開式快速算法[9]和整數(shù)拆分表示形式快速算法[10]等)相比，具有所需存儲空間較小、運算效率更高等優(yōu)點。

下面給出ECC的奇系數(shù)Comb標(biāo)量乘快速算法實施過程：

(1)

通過利用奇系數(shù)Comb算法對ECC的正奇數(shù)標(biāo)量進(jìn)行重新編碼，則標(biāo)量k的奇系數(shù)Comb形式編碼如式(2)所示：

(2)

其中，li表示標(biāo)量k的奇系數(shù)Comb算法編碼系數(shù)，且有l(wèi)i≠0。t表示li的編碼長度，且有t=「n/s?，s表示li的二進(jìn)制編碼長度，n表示k的二進(jìn)制編碼長度。下面對li進(jìn)行二進(jìn)制編碼可得如下式(3)：

(3)

(4)

則ECC標(biāo)量乘法的運算形式可轉(zhuǎn)換為如下形式，如式(5)所示：

Q=k·P

(5)

其中，Pi為預(yù)計算點，且有各預(yù)計算點Pi=(u(s-1)2(s-1)t+…+ui2it+…+u12t+1)·P，ui∈{0,1}。然后根據(jù)已預(yù)計算出的各預(yù)計算點生成預(yù)計算表[6-8]。

需要把已知標(biāo)量k奇數(shù)化，且令奇數(shù)化后的標(biāo)量為l。即如果k為正奇數(shù)，則l=k+1；但如果k是正偶數(shù)，則l=k+2。由于對k進(jìn)行了奇數(shù)化，所以需在返回Q值時增加后處理操作：若k為奇數(shù)，則要增加一次Q=Q-2P操作；若k為偶數(shù)，則要增加一次Q=Q-P操作。所以ECC標(biāo)量重新編碼之后，則奇系數(shù)Comb標(biāo)量乘運算的具體過程如下面算法1所示[11]：

算法1 ECC的奇系數(shù)Comb標(biāo)量乘快速算法

輸入：k,s,P；

輸出：Q=kP。

步驟1 對標(biāo)量k進(jìn)行奇數(shù)化變換成l；

步驟2 令m表示l的二進(jìn)制長度；

步驟3 生成預(yù)計算表Pi；

步驟4 計算奇系數(shù)Comb編碼長度t=「m/s?；

步驟5 計算奇系數(shù)Comb編碼系數(shù)li；

步驟6 令Q=O；

步驟7 對于i從t-1到0，重復(fù)執(zhí)行：

步驟7.1Q=2Q；

步驟7.2Q=Q+liP；

步驟8 返回輸出值Q：

步驟8.1 若k為偶數(shù)，則返回Q=Q-P;

步驟8.2 若k為奇數(shù)，則返回Q=Q-2P。

2 新算法設(shè)計

在所給的算法1中，由于標(biāo)量的奇系數(shù)編碼系數(shù)li都不為0，因而在步驟6中總是執(zhí)行同樣的操作步驟和順序。也即是，每當(dāng)執(zhí)行一次倍點運算后就接著也執(zhí)行一次點加運算，所獲得的能耗圖譜基本沒有出現(xiàn)顯著的功耗曲線差異，這樣也就使攻擊者不能根據(jù)功耗的差異來猜測相關(guān)的密鑰信息。并且無論所給標(biāo)量是奇數(shù)還是偶數(shù)，在步驟8中都會執(zhí)行一次點加運算，因此所給標(biāo)量的奇偶性也不會被泄露。因而所給算法1能夠防御SPA。然而，因為已知的基點P致使運算中間值和輸入之間具有一定的相關(guān)性，這就使得攻擊者能夠利用運算過程的中間值來推測出相關(guān)的密鑰信息，因而算法1不能防御DPA。與此同時，所給的基點中可能存在有可以被攻擊者利用的特殊點，從而使得算法1不能抵抗ZPA與RPA[9-10]。

文中采用了基點掩碼技術(shù)，即通過在標(biāo)量乘運算中引入隨機(jī)點將基點隨機(jī)化，同時再結(jié)合預(yù)計算的方法可實現(xiàn)多標(biāo)量乘法運算中各分基點的隨機(jī)化，以此即可掩蓋每個小標(biāo)量乘法運算同功耗之間的相關(guān)性，這樣就致使攻擊者無法利用統(tǒng)計分析的方法，通過多次猜測來獲取有效的密鑰信息。所以，基于奇系數(shù)Comb編碼標(biāo)量乘運算Q=kP在引入隨機(jī)點R之后可轉(zhuǎn)化成如下形式，如式(6)所示：

Q=k·P+R

(6)

其中，因為引入了隨機(jī)點R，使得在返回Q時，需增加后處理操作來進(jìn)行恢復(fù)：若k為奇數(shù)，則增加操作Q=Q-2P-R；若k為偶數(shù)，則增加操作Q=Q-P-R。所給基于奇系數(shù)Comb的標(biāo)量乘抗功耗攻擊算法具體過程如下面算法2所示：

算法2 基于奇系數(shù)Comb的標(biāo)量乘抗功耗攻擊算法

輸入：k,P；

輸出：Q=kP。

步驟1 對標(biāo)量k進(jìn)行奇數(shù)化變換成l；

步驟2 令m為奇數(shù)化標(biāo)量l的二進(jìn)制長度；

步驟3R=random()；

步驟5 計算奇系數(shù)Comb編碼長度t=「m/s?；

步驟6 計算奇系數(shù)Comb編碼系數(shù)li；

步驟7 令Q=R；

步驟8 對于i從t-1到0，重復(fù)執(zhí)行：

步驟8.1Q=2Q；

步驟8.2Q=Q+liP；

步驟9 返回輸出值Q：

步驟9.1 若k為偶數(shù)，則返回Q=Q-P-R;

步驟9.2 若k為奇數(shù)，則返回Q=Q-2P-R。

3 仿真及性能分析

3.1 安全性分析

在算法2中，因為不存在系數(shù)為0的系數(shù)，使得其沒有功耗差異的操作，所以其能耗圖譜是相同的，這也說明其本身具備抵抗SPA的能力。同時，由于引入了隨機(jī)點R，使得預(yù)計算表中分基點Pi和功耗之間的相關(guān)性被掩藏，進(jìn)而也可隱藏可被利用的某些特殊點，因而所給算法2能防御DPA、ZPA與RPA。最后，所給算法2執(zhí)行了兩次后處理操作，這主要是實現(xiàn)兩個方面的目的：一方面是用于掩蓋原標(biāo)量自身的奇偶性，有效提升了算法的安全性；另一方面是可減去引入的隨機(jī)點，從而恢復(fù)真實的返回值。其中，文中采用了文獻(xiàn)[12]所給的功耗仿真平臺對算法1和算法2進(jìn)行功耗仿真分析，如圖1和圖2所示(以實施DPA攻擊為例)[11]。

下面圖1中給出了對算法1實施DPA攻擊所獲得的功耗曲線圖。由圖1可以看出，對算法1實施DPA攻擊后，其功耗軌跡曲線出現(xiàn)明顯的起伏，這就使得攻擊者有可能推測出相關(guān)的密鑰信息。雖然算法1具有相同的能力圖譜可以抵抗SPA，但如果攻擊者對算法1實施DPA攻擊，然后對已獲得的大量功耗軌跡曲線進(jìn)行統(tǒng)計分析，攻擊者將能夠推測出相關(guān)的密鑰信息。所以，仿真結(jié)果表明算法1是無法抵抗DPA攻擊的，因而需要對其進(jìn)行改進(jìn)。

圖1 對算法1實施DPA攻擊的功耗曲線

下面圖2中給出了對所給算法2實施DPA攻擊所獲得的功耗曲線圖。由圖2可以看出，算法2的功耗軌跡曲線總體來說比較平滑，并無明顯的波形起伏，因而攻擊者無法根據(jù)所獲得的大量功耗軌跡曲線進(jìn)行統(tǒng)計分析，來得到與之相關(guān)的密鑰信息。因此，仿真結(jié)果表明所給算法2能夠有效地抵抗DPA攻擊。

圖2 對所給算法2實施DPA攻擊的功耗曲線

3.2 效率分析

在所給算法2中，步驟1、2和3所需運算量與其它步驟的運算量相比可忽略不計。步驟4的預(yù)計算需要計算2(s-1)tP,…,2tP和Pi-R，其中前者所需運算量是(s-1)tD，后者所需運算量是(2s-1)A，因此生成預(yù)計算表Pi′需要的運算量是(2s-1)A+(s-1)tD。步驟5和6所需運算量與其它步驟的運算量也可忽略不計。步驟8中主循環(huán)運算的運算量是tA+tD。步驟9中后處理運算的運算量是2A或2A+D。所以，算法2需要的總運算量是(2s+t+1)A+(st+1)D。其中，A為點加運算，D為倍點運算，t為奇系數(shù)編碼長度，s為奇系數(shù)Comb算法編碼系數(shù)的二進(jìn)制長度，而且t=「n/s?，n為奇數(shù)化標(biāo)量的二進(jìn)制長度。下表1給出了所給算法2和BR算法(二進(jìn)制)、WBRIP算法以及FWNAF算法的運算效率比較[12]。其中，w表示窗口寬度，且有w=4。此外，w0和w1分別為FWNAF抗功耗攻擊算法中窗口w的整數(shù)部分和碎片部分，且有w0=「w?，w1=w-(w0-1)[13]。

表1 所給算法2和BR、WBRIP以及FWNAF抗功耗攻擊算法的運算效率比較

由表1可知，所給算法2需要的存儲空間要比WBRIP和FWNAF的小。但是，WBRIP比所給算法2要多執(zhí)行了(2s-1-2)次點加操作和(2s-1+s-2)次倍點操作，而FWNAF算法比所給算法2多執(zhí)行了(w0-1)次倍點操作，執(zhí)行的點加操作次數(shù)基本相似。由此可以看出，所給算法2不僅能夠保持同樣抗功耗攻擊能力，同時還能夠在降低存儲空間的情況下提升運算效率。當(dāng)前ECC中512bit的密鑰一般被認(rèn)為是安全的，即n=512。令s=4，w=4，則t=128，w0=4，w1=1。

此外，在文獻(xiàn)[14]給出的仿射坐標(biāo)系下，A=23M，D=24M，M表示模乘運算。則BR抗功耗攻擊算法的總運算量為24064M，WBRIP抗功耗攻擊算法的總運算量為16025M，F(xiàn)WNAF抗功耗攻擊算法的總運算量為15766M，而算法2的總運算量為15671M。因此，所給算法2比BR算法的運算效率提升了34.88%，比WBRIP算法提升了2.21%，而與FWNAF算法的總運算量基本相似。盡管所給算法2所需的預(yù)計算量要比WBRIP算法和FWNAF算法大的多，但是預(yù)計算表能夠預(yù)先存儲到密碼芯片中。然而，僅僅對于主循環(huán)運算來說，所給算法2比WBRIP算法與FWNAF算法的運算效率均提升了60.04%左右。由此可知，所給算法2可以同時兼顧到安全和效率兩個方面，可以較好地用于各種資源受限的應(yīng)用環(huán)境中[13-14]。

4 結(jié) 語

ECC是密碼安全芯片中主流的密碼算法，廣泛應(yīng)用于各類安全環(huán)境中，而其中基于奇系數(shù)Comb的標(biāo)量乘算法則是ECC中的一種快速標(biāo)量乘算法，但是因為近年來出現(xiàn)的功耗分析技術(shù)致使密碼安全芯片遭遇了非常大的安全風(fēng)險和挑戰(zhàn)。因而文中結(jié)合奇系數(shù)Comb快速標(biāo)量乘算法與基點掩碼技術(shù)，從而給出了一種改進(jìn)的ECC抗功耗攻擊算法。該算法與BR、WBRIP以及FWNAF抗功耗攻擊算法相比，不僅同樣能夠有效抵抗多種功耗攻擊，同時具有更高的運算效率。由此可知，所給RPAOCM算法能較好地解決密碼芯片等類似系統(tǒng)因資源受限而存在效率和安全兩方面矛盾的問題，能夠較好地用于各類自身資源受限的應(yīng)用系統(tǒng)中。

[1] Pang S C, Tong S Y, Cong F Z, et al. A efficient elliptic curve scalar multiplication algorithm against side channel attacks [C]//Proceedings of the 2010 International Conference on Computer, Mechatronics, Control and Electronic Engineering (CMCE2010), Springer-Verlag, Berlin, 2010: 361-364.

[2] 王正義，趙俊閣.ECC抗功率分析攻擊的等功耗編碼算法[J].計算機(jī)工程，2012，38(10)：111-113．

[3] Akishita T, Takagi T. Zero-value point attacks on elliptic curve cryptosystems [EB/OL]. http://www.Informatik. tudarmstadt.de/ftp/pub/TI/TR/TI-03-01.zvp.ps.

[4] Gobin L. A refined power analysis attack on elliptic curve cryptosystems [C]//Public Key Cryptography 2003, LNCS 2567, Springer-Verlag, 2003.

[5] Mamiya H, Miyaji A, Morimoto H. Efficient countermeasures against RPA, DPA, and SPA [C]//Cryptographic Hardware and Embedded Systems(CHES’04), LNCS 3156, Springer-Verlag, 2004: 343-356.

[6] 張濤. Smartcard上橢圓曲線密碼算法的能量攻擊和防御[J]．計算機(jī)工程，2007，33(14)：125-127．

[7] Zhang Tao, Fan Mingyu, Zheng Xiaoyu. Secure and efficient elliptic curve cryptography resists side-channel attacks [J]. Journal of Systems Engineering and Electronics, 2009, 20(3): 660-665.

[8] Dimitrov V S, Jullien G A, Miller W C. Theory and applications for a double-base number system [J]. IEEE Transactions on Computers, 1999, 48(10): 1098-1106.

[9] 賴忠喜，張占軍，陶東婭．橢圓曲線中直接計算7P的方法及其應(yīng)用[J]．計算機(jī)應(yīng)用，2013，33(7)：1870-1874.

[10] 石潤華，葛麗娜，鐘誠．橢圓曲線密碼體制上一種快速kP算法[J]．計算機(jī)工程與科學(xué)，2004，26(4)：55-58．

[11] Feng M, Zhu B B. Efficient comb elliptic curve multiplication methods resistant to power analysis [EB/OL]. http://eprint.iacr. org/2005/222.ps.gz.

[12] 王晨旭，趙占峰，喻明艷，等．Picclol相關(guān)性功耗分析攻擊技術(shù)研究[J]．哈爾濱工業(yè)大學(xué)學(xué)報，2013，45(9)：17-22．

[13] 姚劍波，張濤．基于素數(shù)域上復(fù)合運算的快速標(biāo)量乘算法[J]．計算機(jī)應(yīng)用研究，2012，29(12)：4639-4643．

[14] 王玉璽，張串絨，張柄虹，等．基于素數(shù)域上復(fù)合運算的快速標(biāo)量乘算法[J]．計算機(jī)應(yīng)用研究，2013，30(11)：3365-3387.