計時攻擊研究與仿真

2016-10-09 08:59:20賈徽徽王潮顧健宋好好唐迪

網絡與信息安全學報 2016年4期

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

（1. 公安部第三研究所，上海 200031；2. 上海大學特種光纖與光接入網省部共建重點實驗室，上海 200072）

計時攻擊研究與仿真

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

（1. 公安部第三研究所，上海 200031；2. 上海大學特種光纖與光接入網省部共建重點實驗室，上海 200072）

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

側信道攻擊；計時攻擊；隱馬爾可夫模型；橢圓曲線密碼

1　引言

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

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

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

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

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

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

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

2　ECC基本知識

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

從算法1中可以看出，當ik為0或1時，執行的運算量不同，泄漏出來的信息就是運算的時間不同，本文正是利用這個時間信息來進行計時攻擊的。

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

其中，P為基點，m為要簽名的消息，H表示一個密碼雜湊函數，k為產生的隨機數，稱之為臨時密鑰，d為私鑰，（r，s）表示簽名。

3　隱馬爾可夫模型

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

表1　HMM的參數描述

在HMM的實際應用中有3個中心問題需要解決，具體如下。

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

3）學習問題：對于給定的一個觀察值序列，調整參數λ，使觀察值的輸出概率P（O|λ）最大，也就是用給定的觀察值去訓練HMM模型，優化模型參數。

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

4　基于HMM的計時攻擊方案

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

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

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

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

圖1　double-and-add標量乘法的HMM

假設臨時密鑰k=26，通過編寫程序采集到的時間數據從最高位到最低位依次是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，因為觀察到5組數據，那么可以推測密鑰的長度l=5，分別對應k4到k0，最高位k4=1是已知的，那么第一個數據就舍棄不用，通過余下的4個數據來推測剩余的密鑰比特。比較數據發現：第一個數據t1明顯比其他幾個要小好幾個數量級，這是必然的，因為執行第一次循環，Q的初始值為0，它其實是執行的0+P的運算，沒有用到大數運算中的“點加”運算，所需時間較少。在后面4個數據中，t2和t4大小相近并遠大于t3和t5，結合算法分析，時要比時多執行一次“點加”運算，不難推測出t2和t4是ki=1時算法的執行時間和是時算法的執行時間，也就是，推測結果與原始密鑰一致，說明破解成功。

5　ECDSA計時攻擊的仿真實現

5.1仿真實驗過程中的關鍵技術

1）精度問題

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

2）閾值問題

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

3）錯誤比特值確定

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

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

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

5.2仿真實驗及結果分析

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

3）對輸出進行測量，觀察結果為Sv，若

表2　NIST推薦的K-283安全曲線參數

其中，Gx、Gy為基點的橫縱坐標，臨時密鑰k隨機選取并取值為

針對ECDSA的計時攻擊流程如圖2所示。

圖2　計時攻擊流程

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

圖3　double-and-add算法計時攻擊仿真（256 bit密鑰）

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

經比對，猜測密鑰k'與原始臨時密鑰k完全一致，說明本次實驗攻擊成功。

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

Montgomery算法最大的特點就是密鑰的比特無論是0還是1都執行相同的運算，也就是說ki為0或1時的加密時間幾乎是相同的，因此，可以有效地防御計時攻擊。通過本文提出的計時攻擊方法對采用Montgomery點乘算法的密碼系統進行攻擊得到的結果如圖4所示。

圖4　Montgomery算法計時攻擊仿真（256 bit密鑰）

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

6　結束語

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

［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的改進Cache蹤跡驅動攻擊［J］. 通信學報，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］張金中，寇應展，王韜. 針對滑動窗口算法的橢圓曲線密碼故障分析［J］. 通信學報，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，FAIGL 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

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

2016-01-25；

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

國家自然科學基金資助重點項目（No.61332019）；國家自然科學基金資助項目（No.61572304，No.61272056）；上海科委科技創新行動計劃技術標準基金資助項目（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）