王敏，吳震

（成都信息工程學院 網(wǎng)絡工程學院，四川 成都 610225）

1 引言

功耗分析攻擊是利用運算電路的功耗信息泄露，對密碼芯片加解密過程的功耗進行分析，猜測出密碼芯片加解密所使用密鑰的一種攻擊手段[1,2]。

在抵抗功耗分析攻擊的各種策略中，使用隨機動作來破壞功耗和密鑰間的相關(guān)性是一種重要的方法，正確的使用這種技術(shù)確實能很好地達到抗功耗分析攻擊目的。然而，錯誤的使用方式反而會使算法安全性大大下降。隨機偽操作橢圓曲線密碼標量乘算法就是這樣的一個實例。

橢圓曲線密碼（ECC, elliptic curve cryptography）是基于橢圓曲線數(shù)學的一種公鑰密碼。該算法與其他公鑰密碼算法相比具有比特強度高，計算速度快，存儲空間小等特點，在資源受限的嵌入式系統(tǒng)（如智能卡）等安全領(lǐng)域廣泛應用。

自從功耗分析攻擊提出以后，公鑰算法實現(xiàn)如何在兼顧效率的同時抵抗功耗分析攻擊，成為密碼學研究的一個重點。隨機偽操作橢圓曲線標量乘算法[3]是在固定添加偽點加法算法（又稱 double and add always算法）[4,5]基礎(chǔ)上引入隨機機制而形成的一種提高效率的改進型算法，該算法試圖用隨機性保持其抗簡單功耗分析（SPA, simple power analysis）攻擊能力的同時提高運算效率。但該類算法在設(shè)計實現(xiàn)中對隨機性的使用存在一定缺陷，為提高效率而引入的隨機偽操作反而可能成為 SPA攻擊成功的決定因素。

下面從添加偽點加法算法的抗 SPA攻擊原理入手，具體分析添加隨機偽操作的橢圓曲線標量乘算法的缺陷及其多樣本 SPA攻擊實現(xiàn)方法，并給出實測結(jié)果，最后給出抗多樣本SPA攻擊的改進建議。

2 橢圓曲線密碼算法的隨機偽操作標量乘法

2.1 橢圓曲線密碼算法的標量乘法

橢圓曲線密碼算法的核心運算為標量乘kP的計算，而標量乘法運算過程中包含有密鑰k的信息，因此對于標量乘法的功耗分析攻擊成為了橢圓曲線密碼算法重要的攻擊點。

在標量乘實現(xiàn)算法中主要使用點加(QQP= + )和倍點( 2PP= ) 2種定義在橢圓曲線上的運算[6,7]，SPA攻擊可利用這2種運算在功耗曲線上的不同形狀，直接恢復出K值[3]。

2.2 添加偽點加法

針對標量乘的添加偽點加法是根據(jù) SPA攻擊原理，為了掩蓋密鑰k與運算間的操作相關(guān)性，對標量乘實現(xiàn)算法進行修改，使得當密鑰k對應比特是“0”或“1”時，都進行點加和倍點2種運算，來達到掩蓋密鑰與運算間的操作相關(guān)性的目的，其具體實現(xiàn)算法、抗SPA攻擊能力和算法效率見文獻[3]。

2.3 隨機偽操作法實現(xiàn)原理

文獻[3]提出的隨機偽操作法是將上述添加偽點加實現(xiàn)算法進行的修改，當密鑰k對應比特為0時不再單純地添加一次偽點加操作，而是隨機添加一次偽操作，該偽操作為點加、倍點、無操作三者之一，并且為了既能提高抵抗SPA攻擊能力，又能盡可能地減少效率損失，對添加偽操作各類型概率進行控制，將添加無操作的概率控制在50%左右，添加點加和倍點的概率總和控制在50%左右，隨機偽操作法程序流程如圖1所示。

算法原意是想利用隨機偽操作來掩蓋功耗曲線與密鑰K之間的相關(guān)性，同時對固定添加偽點加的算法加以效率上的改進，詳見文獻[3]。然而，在下面的分析中可以看到，這種添加偽操作的方法如果沒有其他防護措施的配合，實際上破壞了原固定添加偽點法的安全性，僅使用 SPA攻擊便可獲取密鑰。

圖1 隨機偽操作法程序流程

3 針對隨機偽操作的SPA攻擊分析

3.1 單樣本SPA攻擊分析

根據(jù)隨機偽操作算法可知，當密鑰比特為0時，隨機添加偽點加、偽倍點運算或無操作。當添加偽點加運算時，則該比特使真“0”變?yōu)榧佟?”，從波形上看無法區(qū)分；當添加偽倍點時，該比特會使單比特的“0”變?yōu)殡p比特的“00”；但當無操作時，真“0”將真實地表現(xiàn)出來。

首先，根據(jù)文獻[2,8,9]以及實測數(shù)據(jù)發(fā)現(xiàn)，如圖1所示的算法中，每個循環(huán)內(nèi)部2個運算之間的時間間隔較小，而循環(huán)之間的時間間隔比較大。用時間間隔的差別，可以在單樣本中定位各個不同循環(huán)輪數(shù)，這就是利用計時攻擊（TA, timing attack）在單樣本中獲取定位信息。由于每輪循環(huán)均可被定位，而每輪循環(huán)只會對應單比特二進制數(shù)“0”或“1”。則填加的偽倍點運算會被識別出來，這是因為該運算對應的雙比特“00”不可能存在于同一個輪循環(huán)中。由此可知，單樣本下，每輪中觀測到的“00”波形均可被還原為真實值“0”。與之相對應，固定添加偽操作算法每輪邊界被區(qū)分出來也得不到對K有用的SPA攻擊信息。

其次，在單樣本中，還可提取密鑰K漢明重量的上限。令HW（C）為二進制序列C的漢明重量（即二進制序列C中“1”的個數(shù)），K為nbit的真實密鑰值，其漢明重量HW（K）為nk，Ke為單樣本SPA攻擊下獲取K的估計值，其漢明重量HW（Ke）為ne，則有

通過計算Ke的漢明重量，可獲得K的漢明重量上限。即可確定在K中最多有nk個“1”，至少存在n-ne個“0”。從暴力破解的難度上看，只需對nkbit的“1”進行真假猜測，最壞情況計算復雜度從原來的2n降到 2ne。若K為真隨機數(shù)，在大數(shù)情況下，nk= [ 0.5n]的概率趨近 1，這意味著在ne中猜測有[0.5n]個“1”的猜中幾率最大，即進行次猜中的幾率最大。根據(jù)式（1），有

可知單樣本 SPA攻擊可使基于概率最大化暴力破解法的復雜度也大幅減小。由于“0”的個數(shù)下限及其位置信息的暴露，還可綜合使用其他方法進行更有力、快速的密鑰破解。而固定添加偽操作算法也不存在這樣的缺陷。

3.2 基于SPA的多樣本遞推逼近攻擊

由上述分析可知，想讓破解復雜度降低，在n不變的情況下，應盡量使ne的值接近nk。進行SPA攻擊時，可先進行L個樣本獲取，然后對每個樣本進行SPA攻擊，獲取不同Kei(1≤i≤L)，選取其中漢明重量最小的猜測值Kej(1≤j≤L)，再進行其他類型攻擊。事實上，在多樣本條件下，還存在更有效的分析攻擊方法。

3.2.1 隨機偽操作的分析模型

從密碼分析和波形分析的角度看，隨機偽操作法可看作將K中的“0”進行掩碼保護，隨機編碼成“0”、 “00”或“1”，而對K中的“1”并未進行掩碼，僅編碼成“1”。由于單樣本 TA攻擊在可直接將“00”反推成“0”，故“00”這種情況在下面的分析中將歸結(jié)于“0”中而不單獨討論。

根據(jù)這種規(guī)則，可得如下密碼分析模型：

其中，K為nbit的真實密鑰，R為nbit的真隨機數(shù)，Ke為單樣本SPA攻擊后猜測值，運算符“+”為按比特做邏輯“或”運算。易驗證該模型完全符合以上編碼規(guī)則。

3.2.2 多樣本遞推逼近SPA攻擊的原理

在多樣本條件下，令L為采集的樣本次數(shù)，則第i個樣本利用真隨機數(shù)Ri形成的猜測值Kei為

其中， 當i≠j時 ,Ri≠Rj。

令KL'為多樣本綜合猜測值，構(gòu)造以下運算：

其中，運算符“·”為按比特做邏輯“與”運算。

將式（4）代入式（5），根據(jù)邏輯運算規(guī)則，有：

從密碼破譯的角度看，KL'和真實值K兩者的差值正是隨機數(shù)RL'，該隨機數(shù)中“1”的個數(shù)越少，則猜測值越接近于真實值。

根據(jù)隨機數(shù)性質(zhì)，當L充分大的時候，有

則當L充分大時：

另外，當在原樣本集合中再增加一條新樣本時，有

這說明每增加一條新樣本，KL+1'將越接近于真實值K。

3.2.3 多樣本遞推逼近SPA攻擊的實現(xiàn)算法

根據(jù)以上性質(zhì)，構(gòu)造新型多樣本攻擊算法如下。

算法1多樣本遞推逼近S PA攻擊算法

輸入：C=[K]P

輸出：Ki' =K

1) 初 始化：K0'為全1的比特序列，i=0

2)i=i+ 1， 單樣本S PA攻擊出猜測值Kei

5)若Ci≠C，則轉(zhuǎn)至2）繼續(xù)

6)返 回Ki'

在真隨機數(shù)條件下，根據(jù)其均勻性有

根據(jù)上面的討論可知，L個樣本猜測后得到的猜測值K'正確猜出密鑰的概率最高，當L= l bn-1時，有

由信息熵理論也可得到類似的結(jié)果。

如此可見，攻擊樣本數(shù)L與受攻擊K的比特數(shù)n之間呈對數(shù)關(guān)系，計算復雜度極小，攻擊效率比一般的多樣本攻擊高得多。例如一個n=256的K在7個樣本下就有極高的幾率被完全攻破。

3.2.4 多樣本遞推逼近攻擊實測實驗結(jié)果分析

實驗1 在n=256bit時，對一個漢明重量為130的密鑰K，實施多樣本遞推逼近攻擊，共獨立測試10 000組，每組均用不同的隨機數(shù)進行偽隨機操作。測試結(jié)果頻數(shù)直方圖如圖2所示，7個樣本攻擊成功的頻數(shù)最高，為2 401次，占總次數(shù)的24.01%。其次是6個樣本攻擊成功，頻數(shù)為2 336次，占總次數(shù)23.36%。攻擊成功所花樣本數(shù) 11L≤ 的百分比為97.03%， 13L≤ 的百分比是99.25%

圖2n=256bit密鑰K的10 000組攻擊成功樣本數(shù)頻數(shù)直方圖

實驗2 對n=1 024bit，漢明重量為541的密鑰K，對其實施多樣本遞推逼近攻擊。10 000組測試后，測試結(jié)果頻數(shù)直方圖如圖3所示。

圖3n=1 024bit密鑰K的10 000組攻擊成功樣本數(shù)頻數(shù)直方圖

由圖3可知，當成功攻擊樣本L=9時的頻數(shù)最高，為2362次，占23.62%；其次為L=8，為2 313次，占 23.13%，攻擊成功所花樣本數(shù)L≤ 1 3的百分比為97.09%,L≤ 1 5的百分比是99.28%。

經(jīng)過大量實驗統(tǒng)計分析得到，對于nbit的密鑰K，成功攻擊所花樣本數(shù)L≤lbn+3的概率大于97%，L≤lbn+5的概率大于99%。這說明只需小于等于lbn+3個樣本，就有97%的概率破解出完整的nbit密鑰，在此基礎(chǔ)上再增加2個樣本則有大于99%的概率成功破解。

4 隨機偽操作算法抗 SPA攻擊可能的改進措施

隨機偽操作算法中存在的多樣本遞推逼近攻擊缺陷主要由以下原因造成。

1) 由于輪與輪之間的時間間隔與循環(huán)體內(nèi)的時間間隔不同，可獲得定位信息。

2) 由于運算的不同，倍點和點加運算在功耗曲線上很容易被辨識出來。結(jié)合隨機偽操作算法，可獲得每輪K的信息。

3) 掩碼采用真隨機數(shù)，對于相同的K每次都用不同的隨機數(shù)進行掩碼，而多樣本遞推逼近攻擊正是針對這種隨機機制實施的攻擊。

針對第1個缺陷，需在精確測量的基礎(chǔ)上，加入適當?shù)难訒r機制，使得各運算之間的時間間隔相等，消除TA攻擊的隱患。

針對第2種缺陷，需要在倍點和點加運算算法中加以改進，使得2種運算的操作相等，這樣在功耗曲線上無法區(qū)分2種不同運算，給SPA攻擊識別“0”、“1”增加難度。

針對第3種缺陷，則需規(guī)定隨機數(shù)生成算法的規(guī)則，對相同的K生成相同的隨機數(shù)R，不同的K生成不同的隨機數(shù)R。固定添加偽點加算法是該改進的一個特例，其添加的隨機數(shù)R為K的反碼，這樣可使得任意K對應的Ke均為固定值：全“1”。值得指出的是，該隨機數(shù)產(chǎn)生算法最好能保證其單向性，即使在獲得隨機數(shù)R信息的條件下，仍無法逆推出K的值。其實現(xiàn)方案可使用散列技術(shù)或?qū)作為隨機數(shù)發(fā)生器的種子，其破解的復雜度就等價于破解散列算法或隨機數(shù)發(fā)生器。

特別要指出的是，修正以后的算法，其安全性仍然低于固定添加偽點加算法。首先，攻擊者仍可獲得K序列漢明重量的上限，其次，雖然不能確定“0”的絕對位置，但可確定“0”和“1”的相對前后位置，最后，還可通過觀察“0”和“1”的行程來確定子序列中“0”的最少個數(shù)和“1”的最多個數(shù)，這些信息均可使攻擊難度大大下降，由此可見，消除倍點和點加運算之間的差別也非常重要，具體攻擊過程另文撰述。

5 結(jié)束語

隨機偽操作橢圓曲線標量乘算法雖然將運算效率提高，但本文證明，其抗 SPA攻擊能力大大降低。本文提出的多樣本遞推逼近攻擊，利用在多樣本中消除隨機數(shù)的方法，實測結(jié)果表明只需小于等于lbn+3個樣本，就有97%的概率破解出完整密鑰。該類攻擊的存在證明，不恰當?shù)膽秒S機性，不但不能增加安全性，反而會產(chǎn)生極大的安全缺陷。

在改進措施中，將隨機數(shù)生成算法進行改進，有效抵抗了多樣本遞推逼近攻擊；同時平衡了運算之間的時間間隔。但必須認識到，由于隨機添加偽操作算法本身的缺陷，其安全性仍弱于固定添加偽點加算法，建議不使用該類算法。

[1] KOCHER P, JAFFE J, JUN B. Differential power analysis[A]. Lecture Notes in Computer Science; Proceedings of the 19th Annual International Cryptology. Conference on Advances in Cryptology[C]. 1999.388- 397.

[2] KOCHER P C. Timing attacks on implementations of Diffie-Hellman,RSA, DSS, and other systems[A]. Advances in Cryptology-CRYPTO'96, of Lecture Notes in Computer Science[C]. 1996.104-113.

[3] 朱冰, 陳運, 吳震等. 一種抗簡單功耗分析攻擊的橢圓曲線標量乘快速實現(xiàn)算法[J]. 成都信息工程學院學報. 2011, 28(1):5-10.ZHU B, CHEN Y, WU Z,et al. A fast algorithm of scalar multiplication on ECC resistant against SPA[J]. Journal of Chengdu University of Information Technology, 2011, 28(1):5-10.

[4] 廖嘉, 夏國坤, 王立鵬等. 抵抗SPA和 DPA的橢圓曲線上點的標量乘法[J]. 天津科技大學學報, 2009, 24(2):67-70.LIAO J, XIA G K, WANG L P,et al. Scalar multiplication on ECC resistant against SPA and DPA[J]. Journal of Tianjin University of Science and Technology,2009,24(2): 67-70

[5] TETSUYA I, BODO M, TSUYOSH T. Improved elliptic curve multiplication methods resistant against side channel attacks[A].Progress in Cryptology, LNCS 2551[C]. Springer-Verlag, 2002.295-313.

[6] MILLER V S. Use of elliptic curves in cryptography[A]. Proceedings of Crypto 85 LNCS 218[C]. Springer, 1986. 417-426.

[7] KOBLITZ N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987,(48):203- 209.

[8] ACICMEZ O, SEIFERT J P, KOC C K. Predicting secret keys via branch prediction[A]. Topics in Cryptology-CT-RSA 2007, Leture Notes in Computer Science[C]. 2006.225-242.

[9] ACIICMEZ O, KOC C K, SEIFERT J P. On the Power of Simple Branch Prediction Analysis[R]. Cryptology ePrint Archive, 2006.312-320.