針對(duì)隨機(jī)偽操作的簡(jiǎn)單功耗分析攻擊

王敏，吳震

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

1 引言

功耗分析攻擊是利用運(yùn)算電路的功耗信息泄露，對(duì)密碼芯片加解密過(guò)程的功耗進(jìn)行分析，猜測(cè)出密碼芯片加解密所使用密鑰的一種攻擊手段[1,2]。

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

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

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

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

2 橢圓曲線密碼算法的隨機(jī)偽操作標(biāo)量乘法

2.1 橢圓曲線密碼算法的標(biāo)量乘法

橢圓曲線密碼算法的核心運(yùn)算為標(biāo)量乘kP的計(jì)算，而標(biāo)量乘法運(yùn)算過(guò)程中包含有密鑰k的信息，因此對(duì)于標(biāo)量乘法的功耗分析攻擊成為了橢圓曲線密碼算法重要的攻擊點(diǎn)。

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

2.2 添加偽點(diǎn)加法

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

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

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

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

圖1 隨機(jī)偽操作法程序流程

3 針對(duì)隨機(jī)偽操作的SPA攻擊分析

3.1 單樣本SPA攻擊分析

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

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

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

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

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

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

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

3.2.1 隨機(jī)偽操作的分析模型

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

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

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

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

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

其中， 當(dāng)i≠j時(shí) ,Ri≠Rj。

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

其中，運(yùn)算符“·”為按比特做邏輯“與”運(yùn)算。

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

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

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

則當(dāng)L充分大時(shí)：

另外，當(dāng)在原樣本集合中再增加一條新樣本時(shí)，有

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

3.2.3 多樣本遞推逼近SPA攻擊的實(shí)現(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攻擊出猜測(cè)值Kei

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

6)返 回Ki'

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

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

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

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

3.2.4 多樣本遞推逼近攻擊實(shí)測(cè)實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

4 隨機(jī)偽操作算法抗 SPA攻擊可能的改進(jìn)措施

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

[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] 朱冰, 陳運(yùn), 吳震等. 一種抗簡(jiǎn)單功耗分析攻擊的橢圓曲線標(biāo)量乘快速實(shí)現(xiàn)算法[J]. 成都信息工程學(xué)院學(xué)報(bào). 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] 廖嘉, 夏國(guó)坤, 王立鵬等. 抵抗SPA和 DPA的橢圓曲線上點(diǎn)的標(biāo)量乘法[J]. 天津科技大學(xué)學(xué)報(bào), 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.