計(jì)時(shí)攻擊研究與仿真

賈徽徽，王潮，顧健，宋好好，唐迪

（1. 公安部第三研究所，上海 200031；2. 上海大學(xué)特種光纖與光接入網(wǎng)省部共建重點(diǎn)實(shí)驗(yàn)室，上海 200072）

計(jì)時(shí)攻擊研究與仿真

賈徽徽1，王潮2，顧健1，宋好好1，唐迪1

（1. 公安部第三研究所，上海 200031；2. 上海大學(xué)特種光纖與光接入網(wǎng)省部共建重點(diǎn)實(shí)驗(yàn)室，上海 200072）

借助于隱馬爾可夫模型思想，提出了一種針對采用“倍點(diǎn)—點(diǎn)加”點(diǎn)乘算法的橢圓曲線數(shù)字簽名體系的一種計(jì)時(shí)攻擊方法，并對美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）公布的二進(jìn)制域上的5條Koblitz安全曲線進(jìn)行了攻擊仿真實(shí)驗(yàn)，成功地攻擊了除K-571以外的其他4條Koblitz安全曲線。對于每一條安全曲線僅采集一次時(shí)間數(shù)據(jù)、耗時(shí)幾十分鐘就能恢復(fù)出幾乎全部的密鑰比特，實(shí)驗(yàn)結(jié)果表明，該方法實(shí)施簡單、成功率高，是對當(dāng)前安全曲線有較大威脅的一種側(cè)信道攻擊手段。

側(cè)信道攻擊；計(jì)時(shí)攻擊；隱馬爾可夫模型；橢圓曲線密碼

1　引言

安全是計(jì)算機(jī)和通信系統(tǒng)長期以來一直關(guān)注的問題，大量的研究工作也一直致力于解決這個(gè)問題。密碼算法構(gòu)成了可以作為構(gòu)建模塊來構(gòu)造針對特定目標(biāo)的安全機(jī)制的原始材料，這些算法包括對稱密碼、公鑰密碼以及散列函數(shù)等。橢圓曲線密碼（ECC，elliptic curve cryptography）是1985年由Koblitz和Miller提出的一種公鑰密碼體制［1］，有安全性高、占用帶寬小、密鑰長度短、計(jì)算速度快等特點(diǎn)，已被廣泛應(yīng)用于無線通信、密碼芯片、電子商務(wù)等領(lǐng)域，也是衛(wèi)星網(wǎng)絡(luò)、物聯(lián)網(wǎng)等新型網(wǎng)絡(luò)的首選，因此，對其安全性的研究顯得尤為重要。ECC的安全性建立在橢圓曲線離散對數(shù)問題（ECDLP，elliptic curves discrete logarithm problem）的困難性之上，1999年9月28日，加拿大的Certicom公司宣布利用法國、澳大利亞、加拿大、美國、芬蘭、奧地利等國家的760臺計(jì)算機(jī)成功解決了97 bit的ECDLP問題。在解決問題過程中一共進(jìn)行了130 000億次橢圓曲線“點(diǎn)加”運(yùn)算。2002年11月6日，Chris Monico博士帶領(lǐng)NotreDame大學(xué)數(shù)學(xué)研究中心的數(shù)學(xué)家利用10 000臺計(jì)算機(jī)每天工作24 h，歷時(shí)549天才成功地完成了Certicom公司的109 bit P曲線的挑戰(zhàn)，109 bit也是目前傳統(tǒng)攻擊的最高挑戰(zhàn)比特?cái)?shù)。對于NIST公布的ECC安全曲線中最小的163 bit密鑰長度來說，以目前計(jì)算機(jī)的計(jì)算速度進(jìn)行窮舉攻擊大約需要1012年，這證明ECC算法確實(shí)具有極高的安全性。

但事實(shí)上，密碼算法不是決定整個(gè)密碼安全性的唯一因素，密碼算法的實(shí)現(xiàn)需要依附一個(gè)軟件或者硬件設(shè)備平臺，在這些設(shè)備運(yùn)行過程中會與周圍環(huán)境發(fā)生交互并受周圍環(huán)境的影響。攻擊者可以通過監(jiān)測這些物理交互作用找出可以用于密碼分析的有效信息，這種信息就被稱為側(cè)信道信息，而攻擊利用側(cè)信道信息進(jìn)行攻擊的方法就被稱為側(cè)信道攻擊（SCA，side channel attack）。所謂側(cè)信道攻擊是指攻擊者采集密碼設(shè)備實(shí)現(xiàn)過程中內(nèi)部狀態(tài)無意泄漏的物理效應(yīng)并進(jìn)行分析，典型的側(cè)信道攻擊包括計(jì)時(shí)攻擊［2］、功耗攻擊［3］、電磁分析攻擊［4］、Cache攻擊［5，6］、故障攻擊［7，8］、掃描式攻擊［9］等。

計(jì)時(shí)攻擊是利用密碼算法在執(zhí)行過程中泄漏出來的時(shí)間信息來進(jìn)行攻擊的，由于要考慮性能優(yōu)化問題，密碼算法往往會使用一些分支語句、條件語句等來加快執(zhí)行速度，但也同時(shí)給加解密時(shí)間帶來了差異，這些差異可能會泄漏一些重要信息，計(jì)時(shí)攻擊就是利用這種差異來推測密鑰信息的。計(jì)時(shí)攻擊不需要額外的硬件設(shè)備，既可在本地實(shí)現(xiàn)，也可以在遠(yuǎn)程網(wǎng)絡(luò)中實(shí)現(xiàn)，并且由于計(jì)時(shí)攻擊所需要的時(shí)間差異信息來源于密碼算法本身，因此，攻擊威脅力比較大，是目前側(cè)信道研究的熱點(diǎn)之一。需要強(qiáng)調(diào)的是這種攻擊方法主要適用于RSA、ECC等公鑰密碼。

1996年，Kocher首次提出了計(jì)時(shí)攻擊的概念［2］，并成功地對 RSA模指數(shù)運(yùn)算實(shí)施了攻擊；之后Schindler對基于CRT算法的RSA進(jìn)行了攻擊［10］，其主要思想是利用 Montgomery算法運(yùn)算時(shí)發(fā)生的額外約減所泄漏出來的時(shí)間差異來推測密鑰。

OpenSSL是一個(gè)開放源代碼的SSL實(shí)現(xiàn)，主要用來實(shí)現(xiàn)通信的高強(qiáng)度網(wǎng)絡(luò)加密，現(xiàn)在被廣泛應(yīng)用于各種網(wǎng)絡(luò)應(yīng)用程序中。斯坦福大學(xué)的Brumley等展示了怎樣用計(jì)時(shí)攻擊恢復(fù)出OpenSSL 中RSA密碼算法的私鑰信息［11］，對Kocher提出的計(jì)時(shí)攻擊方法進(jìn)行了改進(jìn)并對運(yùn)行 OpenSSL的服務(wù)器實(shí)施了遠(yuǎn)程攻擊，通過 30多萬次的訪問，2 h左右恢復(fù)出了1 024 bit的RSA密鑰。Canvel設(shè)計(jì)出了一種針對SSL和TLS中的CBC加密體系的計(jì)時(shí)攻擊方案［12］，可以解密一些簡單的密文。

Cachalo等提出了針對歐洲 NESSIE項(xiàng)目中GPS識別體系的計(jì)時(shí)攻擊［13］，僅用800次測量數(shù)據(jù)，耗時(shí)幾秒鐘就恢復(fù)出了其中的密鑰，成功率高達(dá)80%。Sakruai通過觀測解密諭言時(shí)丟棄信號的時(shí)間，提出了針對EROC-2公鑰密碼體制的一種計(jì)時(shí)攻擊［14］，這種公鑰密碼體制被證明是非常安全的，并被寫入了IEEE P1363標(biāo)準(zhǔn)中，目前很多國際密碼標(biāo)準(zhǔn)組織將EPOC作為公鑰密碼的候選算法。Levine等提出了針對低延時(shí)混合基系統(tǒng)的計(jì)時(shí)攻擊［15］，這些系統(tǒng)是一些企圖掩蓋輸入和輸出信息之間對應(yīng)關(guān)系的通信代理服務(wù)器，他們還提出了一種新的技術(shù)來抵御這種計(jì)時(shí)攻擊。匈牙利人Rudolf等提出了一種重建密鑰方法高級計(jì)時(shí)攻擊［16］，利用統(tǒng)計(jì)學(xué)上方差分析和t檢驗(yàn)方法對采集到的時(shí)間數(shù)據(jù)進(jìn)行分析，成功地恢復(fù)出了128 bit的RSA密鑰。

通過對計(jì)時(shí)攻擊的研究發(fā)現(xiàn)，計(jì)時(shí)攻擊主要應(yīng)用在RSA公鑰密碼上，針對ECC的計(jì)時(shí)攻擊目前還沒有相關(guān)文獻(xiàn)，本文基于隱馬爾可夫模型（HMM，hidden Markov model）思想，以HMM為框架，提出了一種針對橢圓曲線數(shù)字簽名算法（ECDSA，elliptic curve digital signature algo-rithm）的計(jì)時(shí)攻擊方案，對NIST公布的5條二進(jìn)制域上的 Koblitz安全曲線實(shí)施了攻擊仿真實(shí)驗(yàn)，解決了在實(shí)驗(yàn)過程中遇到的3個(gè)關(guān)鍵性技術(shù)問題，成功地攻擊了5條安全曲線中除K-571以外的其他4條曲線。針對這種攻擊，本文還提出了相應(yīng)的防御措施，并展望了針對ECC的計(jì)時(shí)攻擊在今后的發(fā)展，為以后實(shí)施物理攻擊做好鋪墊。

2　ECC基本知識

ECC的核心運(yùn)算是橢圓曲線上的點(diǎn)乘運(yùn)算Q=kP，這種令橢圓曲線上的一個(gè)非零點(diǎn)P重復(fù)相加k次的操作稱為標(biāo)量乘法，它決定著橢圓曲線密碼體制的運(yùn)算速度。為了提高ECC的加解密速度，密碼學(xué)家們提出了許多計(jì)算點(diǎn)乘運(yùn)算的算法，基于二進(jìn)制的“倍點(diǎn)—點(diǎn)加”（double-and-add）算法就是被廣泛應(yīng)用的一種點(diǎn)乘算法，算法描述如下。

從算法1中可以看出，當(dāng)ik為0或1時(shí)，執(zhí)行的運(yùn)算量不同，泄漏出來的信息就是運(yùn)算的時(shí)間不同，本文正是利用這個(gè)時(shí)間信息來進(jìn)行計(jì)時(shí)攻擊的。

由于 ECC私鑰的使用只發(fā)生在解密和數(shù)字簽名過程中，因此，計(jì)時(shí)攻擊也只能在這2個(gè)過程中使用，本文選取在橢圓曲線數(shù)字簽名（ECDSA）過程中使用計(jì)時(shí)攻擊來獲取私鑰。數(shù)字簽名的算法描述如下。

其中，P為基點(diǎn)，m為要簽名的消息，H表示一個(gè)密碼雜湊函數(shù)，k為產(chǎn)生的隨機(jī)數(shù)，稱之為臨時(shí)密鑰，d為私鑰，（r，s）表示簽名。

3　隱馬爾可夫模型

隱馬爾可夫模型（HMM）是馬爾可夫鏈的一種，它的狀態(tài)不能直接觀察到，但能通過觀測向量序列觀察到，每個(gè)觀測向量都是通過某些概率密度分布表現(xiàn)為各種狀態(tài)，每一個(gè)觀測向量是由一個(gè)具有響應(yīng)概率密度分布的狀態(tài)序列產(chǎn)生。自20世紀(jì)80年代以來，HMM被應(yīng)用于語音識別，取得了重大成功。到了20世紀(jì)90年代，HMM還被引入計(jì)算機(jī)文字識別和移動(dòng)通信核心技術(shù)“多用戶的檢測”。近年來，HMM在生物信息科學(xué)、故障診斷、密碼分析等領(lǐng)域也開始得到應(yīng)用。HMM和側(cè)信道攻擊的結(jié)合早有應(yīng)用，2003年，Chris Karkof等第一次將HMM用于密碼分析上［17］，并提出了一個(gè)用于恢復(fù)密鑰的有效算法；2005年，Green等［18］對HMM在密碼分析上的應(yīng)用做了進(jìn)一步研究，提出了將HMM和啟發(fā)式搜索相結(jié)合來進(jìn)行密碼分析的思想；2009年，在亞密會上，Brumley等［19］提出了一種Cache計(jì)時(shí)模板攻擊架構(gòu)，將HMM和向量量化理論運(yùn)用到了Cache攻擊中，實(shí)現(xiàn)了針對ECC的攻擊，對于160 bit的密鑰，使其平均復(fù)雜度由2160降低到248。本文提出的HMM與計(jì)時(shí)攻擊的結(jié)合還是首次。HMM涉及到的一些參數(shù)描述［20］如表1所示。

表1　HMM的參數(shù)描述

在HMM的實(shí)際應(yīng)用中有3個(gè)中心問題需要解決，具體如下。

2）解碼問題：對于給定模型和觀察值序列，求可能性最大的隱含狀態(tài)序列。

3）學(xué)習(xí)問題：對于給定的一個(gè)觀察值序列，調(diào)整參數(shù)λ，使觀察值的輸出概率P（O|λ）最大，也就是用給定的觀察值去訓(xùn)練HMM模型，優(yōu)化模型參數(shù)。

本文要解決的是HMM的3個(gè)中心問題中的解碼問題。利用HMM進(jìn)行側(cè)信道攻擊的基本思想是通過密碼算法泄漏出來的側(cè)信道信息對未知密鑰比特序列進(jìn)行猜測，而HMM的解碼問題是指通過對觀察到的序列分析猜測未知狀態(tài)序列，兩者有相似的地方，可以建立這樣一個(gè)HMM模型，其中，未知狀態(tài)序列就是密鑰bit序列，而觀測序列就是指通過側(cè)信道獲取的觀測信息，在本文中是指通過側(cè)信道獲取的計(jì)時(shí)信息。

4　基于HMM的計(jì)時(shí)攻擊方案

計(jì)時(shí)攻擊首先由Kocher于1996年提出，并成功對RSA模指數(shù)運(yùn)算進(jìn)行了攻擊，其基本原理是利用密碼算法在加解密過程中泄漏出來的時(shí)間信息來進(jìn)行攻擊的。密碼系統(tǒng)加解密時(shí)間差異信息產(chǎn)生的來源為性能優(yōu)化、分支運(yùn)算、條件語句、RAM Cache命中、運(yùn)行時(shí)間不固定的處理器指令以及其他多變的原因。

在double-and-add算法中，由于if語句的存在使密鑰比特為0或1時(shí)執(zhí)行的操作步驟不同，比特為1時(shí)比比特為0時(shí)要多一步“點(diǎn)加”運(yùn)算，最終表現(xiàn)出來的是比特為0或1時(shí)的執(zhí)行運(yùn)算時(shí)間不同，這就為實(shí)施計(jì)時(shí)攻擊提供了可能性。

由算法2可知，在步驟2）中有點(diǎn)乘運(yùn)算，所以可以利用計(jì)時(shí)攻擊在計(jì)算 kP點(diǎn)乘運(yùn)算時(shí)求出臨時(shí)密鑰k，臨時(shí)密鑰在每次簽名都不同，因此，一次簽名只能采集一次計(jì)時(shí)數(shù)據(jù)，這也是計(jì)時(shí)攻擊難點(diǎn)所在。由于H（m）、簽名s已知，就可以利用式（1）求出私鑰d。

所以，針對ECDSA攻擊的關(guān)鍵就是利用獲取的計(jì)時(shí)數(shù)據(jù)求解臨時(shí)密鑰k。基于HMM思想，本文首先建立double-and-add標(biāo)量乘法的HMM，如圖1所示。

圖1　double-and-add標(biāo)量乘法的HMM

假設(shè)臨時(shí)密鑰k=26，通過編寫程序采集到的時(shí)間數(shù)據(jù)從最高位到最低位依次是t1=0.000 189 668 s，t2=0.156 695 s，t3=0.070 859 s，t4=0.147 188 s，t5=0.056 313 2 s，因?yàn)橛^察到5組數(shù)據(jù)，那么可以推測密鑰的長度l=5，分別對應(yīng)k4到k0，最高位k4=1是已知的，那么第一個(gè)數(shù)據(jù)就舍棄不用，通過余下的4個(gè)數(shù)據(jù)來推測剩余的密鑰比特。比較數(shù)據(jù)發(fā)現(xiàn)：第一個(gè)數(shù)據(jù)t1明顯比其他幾個(gè)要小好幾個(gè)數(shù)量級，這是必然的，因?yàn)閳?zhí)行第一次循環(huán)，Q的初始值為0，它其實(shí)是執(zhí)行的0+P的運(yùn)算，沒有用到大數(shù)運(yùn)算中的“點(diǎn)加”運(yùn)算，所需時(shí)間較少。在后面4個(gè)數(shù)據(jù)中，t2和t4大小相近并遠(yuǎn)大于t3和t5，結(jié)合算法分析，時(shí)要比時(shí)多執(zhí)行一次“點(diǎn)加”運(yùn)算，不難推測出t2和t4是ki=1時(shí)算法的執(zhí)行時(shí)間和是時(shí)算法的執(zhí)行時(shí)間，也就是，推測結(jié)果與原始密鑰一致，說明破解成功。

5　ECDSA計(jì)時(shí)攻擊的仿真實(shí)現(xiàn)

5.1仿真實(shí)驗(yàn)過程中的關(guān)鍵技術(shù)

1）精度問題

計(jì)時(shí)攻擊主要通過對執(zhí)行時(shí)間的監(jiān)測來推算密鑰，由于差異值一般都很小，因此需要高精度精確計(jì)時(shí)技術(shù)。本文采用的是windows.h庫中獲取機(jī)器內(nèi)部時(shí)鐘頻率的QueryPerformanceFrequency（）函數(shù)和 QueryPerformanceCounter（）函數(shù)。在定時(shí)前應(yīng)該先調(diào)用 QueryPerformanceFrequency（）函數(shù)獲得機(jī)器內(nèi)部計(jì)時(shí)器的時(shí)鐘頻率，接著在需要嚴(yán)格計(jì)時(shí)的事件發(fā)生前后分別調(diào)用QueryPerformanceCounter（）函數(shù)，利用2次獲得的計(jì)數(shù)之差和時(shí)鐘頻率就可以計(jì)算出事件經(jīng)歷的精確時(shí)間，利用這2個(gè)函數(shù)可以將計(jì)時(shí)時(shí)間精確到微秒級，滿足實(shí)驗(yàn)所需要的精度要求。

2）閾值問題

由于受到噪聲、Cache命中失效、CPU資源利用率等因素的影響，每次執(zhí)行得到的計(jì)時(shí)數(shù)據(jù)都不盡相同，都有一個(gè)小范圍的波動(dòng)，因此，這里有一個(gè)閾值選擇的問題，閾值過大或過小都影響實(shí)驗(yàn)結(jié)果，閾值一旦確定不準(zhǔn)確就會對后面比特信息的判斷產(chǎn)生直接影響。對于不同安全級別的曲線，對應(yīng)閾值就有很大的差異，本文采用的是統(tǒng)計(jì)學(xué)方法，通過上百次的計(jì)算得出K-283安全曲線，“倍點(diǎn)—點(diǎn)加”運(yùn)算平均耗時(shí)為0.205 537 s，“倍點(diǎn)”運(yùn)算平均耗時(shí)為0.101 148 s，取閾值r=然后從次高位開始逐一判斷（最高位為1無需判斷），如果比特對應(yīng)的計(jì)時(shí)時(shí)間大于r=0.153 323 s，此比特就確定為1；反之，如果比特對應(yīng)的計(jì)時(shí)時(shí)間小于r=0.153 323 s，就確定為0。

3）錯(cuò)誤比特值確定

由于外界環(huán)境以及CPU本身的影響，在判斷密鑰比特信息時(shí)會存在一定的誤差，并不能保證每次都能恢復(fù)出全部的密鑰比特?cái)?shù)，而且對于ECDSA簽名，臨時(shí)密鑰都是隨機(jī)選取，也就是說每次的臨時(shí)密鑰都不相同，因此，只有一次采集時(shí)間數(shù)據(jù)的機(jī)會，如果攻擊失敗，怎樣從已獲取的臨時(shí)密鑰中快速找出錯(cuò)誤的比特從而破解密碼系統(tǒng)是一個(gè)非常關(guān)鍵的技術(shù)問題。

在實(shí)驗(yàn)過程中發(fā)現(xiàn)，猜測出的臨時(shí)密鑰偶爾會出現(xiàn)1個(gè)或2個(gè)錯(cuò)誤比特的情況。雖然錯(cuò)誤比特?cái)?shù)較少，但是對于傳統(tǒng)的方法，如果有1個(gè)錯(cuò)誤比特，最多需要進(jìn)行N（臨時(shí)密鑰長度）次搜索，復(fù)雜度為O（ N），如果有2個(gè)錯(cuò)誤比特，需要進(jìn)行N（N-1）次搜索，復(fù)雜度為為了降低其搜索的復(fù)雜度，本文提出使用Grover算法進(jìn)行搜索以降低復(fù)雜度。Grover算法是在第28屆美國計(jì)算機(jī)學(xué)會舉辦的計(jì)算理論國際會議上提出的一種量子搜索算法［21］，它將問題的搜索步數(shù)從經(jīng)典算法的N縮小到起到了對經(jīng)典算法的二次加速作用，從而顯著地提高了搜索的效率。在猜測的臨時(shí)密鑰中，如果只有一個(gè)錯(cuò)誤比特，那么只需要次搜索就可以找出來，如果有M個(gè)錯(cuò)誤比特，也僅需要搜索即可，

對于長度為256 bit的臨時(shí)密鑰，如果只有一個(gè)錯(cuò)誤比特，根據(jù)量子Grover搜索理論最多進(jìn)行 16次搜索就能找出，而利用窮舉搜索，最多需要進(jìn)行256次搜索，搜索效率明顯得到提高。

5.2仿真實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)環(huán)境為Intel Core2 Duo CPU T6570 2.10 GHz，內(nèi)存2 GB，編程環(huán)境為Microsoft Visual Studio C++ 2005。實(shí)驗(yàn)對象為 NIST推薦的二進(jìn)制域上的 5 條Koblitz安全曲線，以K-283為例，其安全曲線參數(shù)如表2所示。

3）對輸出進(jìn)行測量，觀察結(jié)果為Sv，若

表2　NIST推薦的K-283安全曲線參數(shù)

其中，Gx、Gy為基點(diǎn)的橫縱坐標(biāo)，臨時(shí)密鑰k隨機(jī)選取并取值為

針對ECDSA的計(jì)時(shí)攻擊流程如圖2所示。

圖2　計(jì)時(shí)攻擊流程

根據(jù)流程圖編寫C++程序，當(dāng)對消息m簽名時(shí)，在源程序中植入QueryPerformanceFrequency（）和QueryPerformanceCounter（）2個(gè)函數(shù)，在定時(shí)前應(yīng)該先調(diào)用QueryPerformanceFrequency（）函數(shù)獲得機(jī)器內(nèi)部計(jì)時(shí)器的時(shí)鐘頻率，接著在密鑰比特執(zhí)行循環(huán)運(yùn)算前后分別調(diào)用QueryPerformanceCounter（）函數(shù)，利用2次獲得的計(jì)數(shù)之差和時(shí)鐘頻率就可以計(jì)算出事件經(jīng)歷的精確時(shí)間，也就是執(zhí)行一次密鑰比特運(yùn)算所消耗的時(shí)間。采集有關(guān)計(jì)時(shí)數(shù)據(jù)，得到一組時(shí)間數(shù)據(jù)序列，然后將得到的時(shí)間數(shù)據(jù)序列與先前確定出的閾值進(jìn)行比較，得到一個(gè)二進(jìn)制比特序列，也就是猜測出的臨時(shí)密鑰，實(shí)驗(yàn)仿真如圖3所示。

圖3　double-and-add算法計(jì)時(shí)攻擊仿真（256 bit密鑰）

通過對仿真圖分析后得到的猜測密鑰為

經(jīng)比對，猜測密鑰k'與原始臨時(shí)密鑰k完全一致，說明本次實(shí)驗(yàn)攻擊成功。

本文提出的計(jì)時(shí)攻擊是根據(jù)點(diǎn)乘算法中算法不同帶來的時(shí)間差異信息進(jìn)行的攻擊，并結(jié)合HMM 模型進(jìn)行了側(cè)信道攻擊的仿真，對使用double-and-add算法的加密算法僅耗時(shí)幾十分鐘就可以恢復(fù)出全部的密鑰，可以看出計(jì)時(shí)攻擊對密碼安全性的強(qiáng)大威脅。預(yù)防此類攻擊的方法就是消除點(diǎn)乘算法中表現(xiàn)出來的時(shí)間差異，稱之為“盲化技術(shù)”，其中較流行的是Montgomery點(diǎn)乘算法，具體如下。

Montgomery算法最大的特點(diǎn)就是密鑰的比特?zé)o論是0還是1都執(zhí)行相同的運(yùn)算，也就是說ki為0或1時(shí)的加密時(shí)間幾乎是相同的，因此，可以有效地防御計(jì)時(shí)攻擊。通過本文提出的計(jì)時(shí)攻擊方法對采用Montgomery點(diǎn)乘算法的密碼系統(tǒng)進(jìn)行攻擊得到的結(jié)果如圖4所示。

圖4　Montgomery算法計(jì)時(shí)攻擊仿真（256 bit密鑰）

通過圖4可以看出，計(jì)時(shí)攻擊所得到的時(shí)間信息相差無幾，很難通過時(shí)間差異來推測密鑰，所以，Montgomery點(diǎn)乘算法能夠很好地防御本文提出的時(shí)間攻擊。

6　結(jié)束語

計(jì)時(shí)攻擊是最早被提出來的側(cè)信道攻擊方法，也是在側(cè)信道攻擊中少有的不用通過其他的輔助硬件就能實(shí)現(xiàn)的攻擊方法，攻擊成本較低，易于實(shí)現(xiàn)。但是國內(nèi)對計(jì)時(shí)攻擊的研究還處于初級階段，而且大部分都是針對RSA公鑰密碼的攻擊，針對ECC方面的研究分析幾乎還沒有涉及。本文基于HMM思想提出來了一種針對ECDSA的計(jì)時(shí)攻擊方法，并編程對NIST公布的安全曲線進(jìn)行了仿真實(shí)驗(yàn)，解決了實(shí)驗(yàn)過程中存在的 3個(gè)關(guān)鍵技術(shù)問題，僅耗時(shí)幾分鐘就能恢復(fù)出幾乎全部的臨時(shí)密鑰比特值，對當(dāng)前密碼的安全性具有極大的威脅。消除點(diǎn)乘算法中的時(shí)間差異是抵御時(shí)間攻擊最有效的方法，因此，研究構(gòu)造能夠抵御時(shí)間攻擊并且加密速度又快的點(diǎn)乘算法具有重要現(xiàn)實(shí)意義。本文提供的仿真實(shí)驗(yàn)方法可以為以后研究有關(guān)計(jì)時(shí)物理實(shí)驗(yàn)攻擊提供一些借鑒，實(shí)施計(jì)時(shí)物理實(shí)驗(yàn)攻擊也是下一步要研究的內(nèi)容。側(cè)信道攻擊的提出為密碼設(shè)計(jì)者提供了更高的要求，要求設(shè)計(jì)出來的密碼系統(tǒng)除了能夠抵御傳統(tǒng)的數(shù)學(xué)攻擊外還要抵御來自各個(gè)側(cè)信道方向的攻擊，只有這樣的密碼系統(tǒng)才稱得上是一個(gè)安全的密碼體統(tǒng)。

［1］KOBLIZ N. Elliptic curve cryptosystems［J］. Mathematics of Computing American Mathematical Society，1987，48（48）： 203-309.

［2］KOCHER P C. Timing attacks on implementations of diffie-hellman，RSA，DSS and other systems［C］//International Cryptology Conference on Advances in Cryptology. c1996：104-113.

［3］KOCHER P，JAFFE J，JUN B. Differential power analysis［C］//The 19th Annual International Cryptology Conference on Advances in Cryptology.c1999：388-397.

［4］QUISQUATER J J，SAMYDE D. Electromagnetic analysis（EMA）：measuresand counter measures for smart cards［C］//The International Conference on Research in Smart Cards： Smart Card Programming and Security. c2001：200-210.

［5］PADE D. Theoretical use of cache memory as a cryptanalytic side-channel［R］. Department of Computer Science，University of Bristol，2002.

［6］趙新杰，郭世澤，王韜. 針對AES和CLEFIA的改進(jìn)Cache蹤跡驅(qū)動(dòng)攻擊［J］. 通信學(xué)報(bào)，2011，32（8）： 101-110. ZHAO X J，GUO S Z，WANG T，et al. Improved cache trace driven attack on AES and CLEFIA［J］. Journal on Communications，2011，32（8）：101-110.

［7］BONEH D，DEMILLO R A，LIPON R J. On the importance of checking cryptographic protocols for faults［J］. Journal of Cryptology，2001，14（2）： 101-119.

［8］張金中，寇應(yīng)展，王韜. 針對滑動(dòng)窗口算法的橢圓曲線密碼故障分析［J］. 通信學(xué)報(bào)，2012，33（1）： 71-78. ZHANG J Z，KOU Y Z，WANG T. Elliptic curve cryptosystem fault analysis on the sliding window algorithm［J］. Journal on Communications，2012，33（1）：71-78.

［9］YANF B，WU K J，KARRI R. Scan-based side-channel attack on dedicated hardware implementations of data encryption standard［C］//IEEE International Test Conference（ITC）. c2004： 339-344.

［10］SCHINDLER W. A timing attack RSA with the Chinese remainder theorem［C］//Lecture Notes in Computer Science（LNCS）. c2000：109-124.

［11］BRUMLEY D，BONEH D. Remote timing attacks are practical［J］. Computer Networks，2005，48（5）： 701-716.

［12］CANVEL B，HILTGEN A，VAUDENAY S. Password interception in a SSL/TLS channel［J］. Information Technology Journal，2003，2729（3）：583-599.

［13］CATHALO J，KOEUNE F，QUISQUATER J J. A new type oftiming attack： application to GPS［M］//Berlin Heidelberg： Springer，2003：291-303.

［14］SAKURAI K，TAKAGI T. A reject timing attack on an IND-CCA2 public-key cryptosystem［C］//The 5th International Conference on Information Security and Cryptology. c2002：359-373.

［15］LEVINE B N，REITER M K，WANG C，et al. Timing attacks in low-latency mix systems［M］//Berlin Heidelberg： Springer，2004：251-265.

［16］TOTH R，F(xiàn)AIGL Z，SZALAY M. An advanced timing attack scheme on RSA［C］//The 13th International IEEE Telecommunications Network Strategy and Planning Symposium. c2008：1-24.

［17］KARLOF C，WAGNER D. Hidden Markov model cryptanalysis［C］//Lecture Notes in Computer Science（LNCS）.c2004：17-34.

［18］GREEN P J，NOAD R，SMART N P. Further hidden Markov model crytannalysis［M］//Berlin Heidelberg： Springer，2005：61-74.

［19］BRUMLEY B B，HAKALA R M. Cache-timing template attacks［C］//Lecture Notes in Computer Science（LNCS）. c2009：667-684.

［20］RABINER L R. A tutorial on hidden Markov models and selected applications in speech recognition［J］. Proceedings of the IEEE，1989，77（2）： 257-289.

［21］GROVER L. A fast quantum mechanical algorithm for database search［C］//ACM Symposium on Theory of Computing. c1996：212-219.

Research and simulation of timing attacks on ECC

JIA Hui-hui1，WANG Chao2，GU Jian1，SONG Hao-hao1，TANG Di1

（1.The Third Research Institute of Ministry of Public Security，Shanghai 200031，China；2. Shanghai University Key Lab of Specialty Fiber Optics and Optical Access Network，Shanghai 200072，China）

Based on the hidden Markov model（HMM）idea，a timing attack on the elliptic curve digital signature system，which adopted the “double-and-add” scalar multiplication，was proposed. Simulation experiments on the secure Koblitz curve which released by the National Institute of Standards Technology（NIST）were implemented and four secure Koblitz curves except the K-571 were attacked successfully. The experiment results show that the attack can recover almost all the key bits in a few minutes by collecting only once time data，and is easy to implement at a high success rate.

side channel attack，timing attack，hidden Markov model，elliptic curve cryptography

TP309.7

A

10.11959/j.issn.2909-109x.2016.00025

2016-01-25；

2016-02-07。通信作者：賈徽徽，jiahh@mctc.org.cn

國家自然科學(xué)基金資助重點(diǎn)項(xiàng)目（No.61332019）；國家自然科學(xué)基金資助項(xiàng)目（No.61572304，No.61272056）；上?？莆萍紕?chuàng)新行動(dòng)計(jì)劃技術(shù)標(biāo)準(zhǔn)基金資助項(xiàng)目（No.13DZ0500501）

Foundation Items： Key Program of National Natural Science Foundation of China（No.61332019），The National Natural Science Foundation of China（No.61572304，No.61272056），The Technical Standard of Shanghai Science and Technology Innovation Action Plan（No.13DZ0500501）

賈徽徽（1986-），男，山東臨沂人，碩士，公安部第三研究所工程師，主要研究方向?yàn)樾畔踩?、智能卡安全、云安全?/p>

王潮（1971-），男，江蘇鎮(zhèn)江人，博士，上海大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)信息安全與橢圓曲線密碼學(xué)、量子計(jì)算密碼、社會網(wǎng)絡(luò)。

顧?。?963-），男，江蘇鎮(zhèn)江人，博士，公安部第三研究所研究員、博士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)信息安全、智能卡安全、軟件測試。

宋好好（1979-），女，山東淄博人，博士，公安部第三研究所副研究員，主要研究方向?yàn)榫W(wǎng)絡(luò)信息安全、云安全。

唐迪（1983-），男，陜西西安人，博士，公安部第三研究所助理研究員，主要研究方向?yàn)殡[私信息保護(hù)、車聯(lián)網(wǎng)網(wǎng)絡(luò)安全協(xié)議。