計時攻擊漏洞識別與防護能力量化評估技術＊

賀章擎，戴 葵，童元滿，鄒雪城

（1.湖北工業大學電氣與電子工程學院，湖北 武漢 430068；

2.華中科技大學光學與電子信息學院，湖北 武漢 430074；

3.國防科學技術大學計算機學院，湖南 長沙 410073)

計時攻擊漏洞識別與防護能力量化評估技術＊

賀章擎1，2，戴 葵2，童元滿3，鄒雪城2

（1.湖北工業大學電氣與電子工程學院，湖北 武漢 430068；

2.華中科技大學光學與電子信息學院，湖北 武漢 430074；

3.國防科學技術大學計算機學院，湖南 長沙 410073)

計時攻擊是最具威脅的旁路攻擊之一，為了設計安全高效的抗計時攻擊的密碼運算部件，需要在設計實現過程中及時發現密碼算法的安全漏洞，并量化分析密碼運算部件的抗計時攻擊防護能力。因此，提出了一種可發現在密碼算法具體實現中可能存在的計時攻擊漏洞的分析方法。將密碼算法采用增強數據相關圖表示，通過在數據相關圖中查找可被計時攻擊的過程變量來分析安全漏洞，給出了相應的識別算法。并以成功實施計時攻擊所需的樣本數來量化密碼運算部件抗計時攻擊能力，提出了一種估算所需樣本數的計算方法。

旁路攻擊；計時攻擊；增強數據相關圖；量化評估

1 引言

近年來，以獲取用戶密鑰為目的的旁路攻擊越來越成為各類密碼系統的嚴峻威脅［1］。計時攻擊是一種重要的旁路攻擊方式，通過獲取系統工作時的時間信息來分析密鑰，具有實施簡單、攻擊成功率高等特點，是目前最具威脅的攻擊方式之一。計時攻擊的概念由Kocher P C于1996年首次提出［2］。由于在密碼算法的實現過程中常常存在一些冗余操作、條件或分支語句、高速緩沖存儲器（Cache)命中狀態以及處理器指令等，在用不同的密鑰對不同的消息進行加密時，操作或指令等所消耗的時間會存在差異。密碼分析者通過儀器測量出時間上的細微差別，通過分析就很可能發現密碼機制中存在的弱點，進而破譯出明文或密鑰。

計時攻擊的一個最新研究進展，就是Cache計時攻擊［3］。現在軟件實現的分組密碼算法，例如高級加密標準AES（Advanced Encryption Standard)等，大都使用許多S盒查表法來提高效率，Cache計時攻擊主要利用從Cache中加載數據到中央處理器CPU（Central Processing Unit)要比從隨機存儲器RAM（Random Access Memory)中要快的特性進行密碼分析。通過測量密碼算法實現過程中由于Cache訪問帶來的時間差異信息，攻擊者可以推測密碼算法實現的內部狀態信息。同時，相比于其他旁路攻擊方式，例如功耗攻擊和電磁分析攻擊，計時攻擊還可以被應用到網絡環境［4］，攻擊范圍更大，影響更深遠。現在國內外針對計時攻擊的主要研究方向，一是針對不同密碼系統提出不同的攻擊方法，二是針對已提出的攻擊方法提出各種防護策略［5］。但是，在實際設計密碼系統的過程中，常常需要在設計過程中對該系統抵抗計時攻擊的能力進行評估，這樣不但可以確保系統的安全性是設計者可以預測和可控制的，同時還可以在系統設計過程中及時發現問題并解決，可以縮短設計周期，降低設計成本，防止密碼算法部件被過度防護，帶來不必要的成本及性能開銷。

在分析密碼算法部件抗旁路攻擊防護能力方面，國內外科研人員做了一定工作，不過大多數成果都是針對功耗攻擊。例如，文獻［6，7］提出了一種在設計的較早階段計算密碼運算部件抗功耗攻擊防護能力的技術。文獻［8］提出了一種密碼部件抗電磁輻射分析攻擊的防護能力量化分析技術。迄今還沒有一個公開發表的針對計時攻擊進行防護能力量化評估的成果。

2 識別密碼算法中計時攻擊漏洞的理論分析技術

為了對密碼運算部件抗計時攻擊的能力進行評估，首先需要分析其密碼算法中是否存在可被計時攻擊的可能。所以，本文的研究內容主要包括兩個部分：一是分析密碼算法具體實現中是否存在可被計時攻擊的漏洞；二是當密碼算法部件可能被實施計時攻擊時，評估其實施的難度。下面首先給出識別密碼算法中計時攻擊漏洞的理論分析技術，包括算法表示，相應的公設和算法等；然后給出密碼算法部件抗計時攻擊防護能力的量化評估方法。

2.1 算法表示

為識別密碼算法具體實現中可能存在的可被計時攻擊的漏洞，首先要將密碼算法采用一種合適的方式進行描述。文獻［9］在數據相關圖DDG（Data Dependence Graph)的基礎上，提出了一種增強數據相關圖EDDG（Enhanced DDG)。本文采用EDDG來對算法進行具體描述。關于EDDG的詳細描述請見文獻［9］，本文不再詳述。

2.2 計時攻擊漏洞的識別

將密碼算法采用EDDG表示之后，下一步的關鍵是如何識別密碼算法中是否存在計時攻擊的漏洞。密碼算法的執行時間存在差異主要是因為算法執行路徑不同，而執行路徑取決于條件轉移變量。計時攻擊的基本原理就是利用了一些條件轉移變量與密鑰相關，通過統計分析執行時間獲取條件轉移變量的信息從而推導密鑰。例如，如果某個密碼算法中存在以下分支：if（e＝＝1)then A；else B；在該例中e就是條件轉移變量。如果執行A和B的時間存在可觀測的差別，則攻擊者即可根據時間樣本的特性來確定e的值。假設e＝k1⊕p，如果p為攻擊者已知量，則攻擊者便可根據e和p的值推導出密鑰k1。

公設1如果密碼算法中存在滿足如下條件的條件轉移變量z，則攻擊者可對z實施計時攻擊以分析出密鑰：

（1)條件轉移變量z的表達式具有z＝f（k1，…，km，x1，…，xn)的形式，其中k1，…，km為可枚舉的部分子密鑰，x1，…，xn為攻擊者已知量；

（2)令ki（1≤i≤m)為破解目標，如果令除ki之外的其他項為固定值，當ki取不同值時z的值不同，且執行路徑的時間存在（可觀測的)差別。

如果存在滿足以上條件的條件轉移變量z，則該密碼算法中存在可被計時攻擊的漏洞，攻擊者可以針對z進行計時攻擊從而分析出密鑰ki。因此，分析密碼算法具體實現中是否存在可被計時攻擊的漏洞，就轉化為在EDDG中查找是否存在滿足公設1的條件轉移變量z。

2.3 實例分析

文獻［10］提出了一個基于隨機加減法鏈的橢圓曲線加密算法ECC（Elliptic Curve Cryptogra-phy)實現技術，將其實現算法的主體循環采用EDDG表示，如圖1所示，其中d為ECC算法的密鑰，sub（d，j，l)表示d的第j位，e 為引入的隨機數，state表示計算過程的狀態，R和T 為中間結果，j為系數d當前位的索引。在圖1中，v1為條件轉移節點，節點v1對應的過程變量（state，e，sub（d，j，l))與部分密鑰sub（d，j，l)存在數據相關且為可枚舉的。與該過程變量相關的兩條執行路徑branch（0，1，1)和branch（0，1，0)分別為：｛R＝R＋T〈0，tpadd〉，T ＝2T〈tpadd，tpadd＋ttpdbl〉｝和｛T＝2T〈0，ttpdbl〉｝，其中tpadd、ttpdbl分別為點的加法和倍加操作的延時，顯然這兩條執行路徑的運行時間存在明顯的可觀察的差別。

Figure 1 EDDG of ECC based on random addition subtraction chain圖1 基于隨機加減法鏈的ECC算法的增強數據相關圖

對該算法EDDG進行進一步分析，列出算法某輪循環的狀態表與執行時間如表1所示。

Table 1 State table and branching time in an ECC execution round表1 隨機加減法鏈ECC算法中某輪循環狀態表與分支執行時間

從表1可以發現，在某輪循環中，只有在state為11且sub（d，j，l)值為1時，執行時間被e隨機化，其他情況下執行時間只與攻擊者已知量state和密鑰sub（d，j，l)相關，密鑰sub（d，j，l)取值不同時執行路徑不同且存在明顯的時間差，所以該算法能被計時攻擊。

3 密碼算法部件抗計時攻擊防護能力評估

識別出密碼算法中計時攻擊的漏洞之后，就需要評估攻擊者成功實施攻擊的難度。為了有效指導設計抗計時攻擊的密碼算法部件，需要在密碼運算部件的設計實現階段量化評估其抗計時攻擊的防護能力。由于在實際的計時攻擊中，很難直接獲取某個分支或路徑的時間信息，一般要通過大量的時間樣本，采用合適的統計方法來進行分析。如果成功實施計時攻擊中所需要的樣本數越多，攻擊難度就越大。當所需樣本數超過一定數值時，攻擊就變得不可行，所以本文以成功實施計時攻擊所需的樣本數來量化密碼運算部件抗計時攻擊的能力。文獻［7］中提出了一種評估功耗攻擊抵抗能力的量化算法，本文在其基礎上進行了拓展，提出了根據計時攻擊的信噪比來估算成功實施計時攻擊所需樣本數的計算方法。

3.1 計時攻擊一般流程

根據前面的分析理論，如果發現密碼運算部件的實現算法中某個條件轉移變量z與可枚舉的部分子密鑰ki相關，且滿足計時攻擊的條件，則可對z實施計時攻擊以分析密鑰ki的值。攻擊時，攻擊者首先隨機選取n個明文，使用目標密鑰進行加密，獲得n個時間樣本。然后猜測密鑰ki的值（假設為K)，并設定一個區分函數，根據區分函數將時間樣本分為兩個子集，如果統計發現這兩個樣本子集的均值存在明顯的差值，則猜測正確，也就是目標的密鑰即為K。

例如，在上例分析的ECC算法中，如果sub（d，j，l)取值為0，若此時state的值為0或者1，則對應分支的執行時間t1＝ttpdbl，若state值為11，對應的分值執行時間為t2＝tpadd＋ttpdbl，顯然t1＞t2，時間差值是可區分的。如果sub（d，j，l)取值為1，則不存在這樣的規律。所以針對該算法，攻擊者可以首先猜測sub（d，j，l)的值為0，然后將state的值作為區分函數，將n個時間樣本分為兩個子集P1和P2，當state取0和1時對應的時間樣本屬于P1，否則屬于P2。由于state的值可根據對應的明文獲得，為攻擊者已知量，所以這樣的區分是可行的。然后攻擊者統計分析P1和P2的均值，如果樣本子集P1的均值小于樣本子集P2的均值，則猜測正確，對應的密鑰sub（d，j，l)的值為0。如果沒有明顯差值，則證明猜測是錯誤的，sub（d，j，l)的值就為1。這樣就可獲取sub（d，j，l)的值，采用同樣的方法可以獲得其他密鑰的值直至全部密鑰。

3.2 計時攻擊信噪比的定義

為了進行量化評估，首先定義計時攻擊的信噪比。對于執行時間未被隨機化的密碼部件來說，某次加密運算的時間是由明文p和密鑰k決定的一個函數，也就是t＝f（p，k)，考慮到密碼部件在執行和測量過程中會引入一些噪聲等因素，所以假定對于不同的定長明文p和給定密鑰k，執行加密運算的時間t為服從正態分布的隨機變量［10］。

從上式可知，當樣本數n增大時，計時攻擊的信噪比將逐漸增大，攻擊者實施計時攻擊的難度逐漸降低，攻擊成功的可能性將逐漸增大。

3.3 信噪比的計算

給出了計時攻擊信噪比的定義之后，本文按照如下方法估算總體X和Y的概率分布，從而求出計時攻擊的信噪比。

隨機產生多個定長明文輸入密碼運算部件并采用未知密鑰進行加密，獲取n個時間樣本。設加密的時間樣本T服從參數為εi的正態分布，記為T～N（εi)。根據數理統計理論，εi和的最優無偏估計量分別為：

其中，n為樣本容量，T1，T2，…，Tn為時間樣本的值。在不同的設計層次下，以上時間樣本可以通過時間分析模型、仿真軟件或者測試儀器獲取。

如果樣本容量n足夠大，則ˉT和S＊2收斂于εi和。計算εi和的估計值的算法如圖2所示。

Figure 2 Estimates the mean and variance of the time samples圖2 估算時間樣本信息的均值和方差的算法流程圖

該算法通過逐步求精進行計算，其中算法中的常數C為初始樣本數，為一經驗值，如2 000。根據上述算法可有效估計總體X和Y的均值和方差，從而求出時間偏差D的均值和方差ε和＋)/n。

3.4 成功實施計時攻擊所需樣本數的計算

得到總體X和Y的概率分布與無偏估計值后，便可求出時間偏差D的均值ε和方差＋)/n。由于D 服從參數為的正態分布，則D位于區間［ε－θε，ε＋θε］內的概率α為：

其中，Φ為正態分布函數。計時攻擊的可信度取決于θ和α這兩個參數的值，θ值越小，α的值越大，計時攻擊的可信度就越高。為有效實施計時攻擊，θ可取0.02，α取0.95，這樣時間偏差D以大概率接近于ε。此時計時攻擊所需的樣本數n為：

其中，u（1＋α)/2表示正態分布的 （1＋α)/2的分位數。

需要指出的是，以上求得的是獲取部分子密鑰ki時所需的樣本數。獲取全部密鑰所需的總的樣本量，可以用獲取所有密鑰時所需的總樣本數來表征。

4 結束語

本文給出了一種在密碼算法設計階段發現可能存在的可被計時攻擊漏洞的分析方法；同時，以成功實施計時攻擊所需的樣本數來量化密碼運算部件抗計時攻擊能力，并且提出了根據計時攻擊的信噪比來估算成功實施計時攻擊所需樣本數的計算方法。按照本文所述方法評估文獻［2］中RSA算法實現的抗計時攻擊防護能力，得到時間攻擊的信噪比為0.66，成功實施時間攻擊所需的樣本數（置信度α＝0.95，θ＝0.02)為22 000左右。而文獻［2］中實際攻擊結果需要20 000個樣本可恢復出密鑰，說明本文所述的量化評估方法具有較高的準確度。結合密碼算法部件防護能力的定性分析和定量分析技術，可以有效指導抗計時攻擊的密碼算法部件的設計與實現。

需要指出的是，本文提出的抗計時攻擊量化評估技術，適用于通過統計分析大量樣本的差分值來破解密鑰的計時攻擊方式。在進一步的研究工作中，將對本文提出的計時攻擊漏洞的識別算法和量化評估技術進行進一步完善，擴展到其他類型的攻擊方式上。另外，可以基于本文的研究成果建立密碼系統抗旁路攻擊的輔助設計EDA工具。

［1］ KULRD＆SCARD Consortium.Side channel attacks［EB/OL］.［2013-06-01］.http：//www.scard-project.org.

［2］ Kocher C.Timing attacks on implementations of diffie-Hellman，RSA，DSS，and other systems［C］∥Proc of the 16th Annual International Cryptology Conference on Advances in Cryptology，1996：104-113.

［3］ Bernstein D J.Cache timing attacks on AES［EB/OL］.［2013-06-01］.http：//cr.yp.to/papers.html〕cache timing.

［4］ Brumley B B，Tuveri N.Remote timing attacks are still practical［C］∥Proc of the 16th European Conference on Research in Computer Security，2011：355-371.

［5］ Oswald E.On side-channel attacks and the application of algorithmic countermeasures［D］.Graz：Graz University of Technology，2003.

［6］ Mangard S.Calculation and simulation of the susceptibility of cryptographic devices to power-analysis attacks［D］.Graz：Graz University of Technology，2003.

［7］ Tong Yuan-man，Wang Zhi-ying，Dai Kui，et al.Quantitative evaluation of the cryptographic blocks resistibility to power analysis at tack at different design level［J］.Journal of Computer Research and Development，2009，46（6)：940-947.（in Chinese)

［8］ Li Hui-yun，Markettos A T，Moore S.Security evaluation against electromagnetic analysis at design time［C］∥Proc of the 10th IEEE International on High-Level Design Validation and Test Workshop，2005：280-292.

［9］ Tong Yuan-man，Wang Zhi-ying，Dai Kui，et al.A unified method for identifying the feasible power analysis attacks in various implementations of cryptographic algorithms［J］.Journal of Computer-aided Design＆Computer Graphics，2008，20（3)：395-402.（in Chinese)

［10］ Oswald E，Aigner M.Randomized addition-subtraction chains as a countermeasure against power attacks［C］∥Proc of CHES’01，2001：39-50.

附中文參考文獻：

［7］ 童元滿，王志英，戴葵，等.不同設計層次下密碼運算部件抗功耗攻擊能力量化評估技術［J］.計算機研究與發展，2009，46（6)：940-947.

［9］ 童元滿，王志英，戴葵，等.識別密碼算法具體實現中潛在功耗攻擊的理論分析方法［J］.計算機輔助設計與圖形學學報，2008，20（3)：395-402.

Quantitative security evaluation against timing attacks in cryptographic algorithm

HE Zhang－qing1，2，DAI Kui2，TONG Yuan-man3，ZOU Xue-cheng2
（1.Department of Electrical ＆ Electronic Engineering，Hubei University of Technology，Wuhan 430068；2.School of Optical and Electronic Information，Huazhong University of Science ＆ Technology，Wuhan 430074；3.College of Computer，National University of Defense Technology，Changsha 410073，China)

Timing attack is one of the most threatening side-channel attacks.In order to design efficient cryptosystems against timing attack，it is necessary to find the vulnerability at design time and quantitative analyze the resistibility to timing attack of the cryptographic algorithms.The paper proposes a unified method for identifying the feasible timing attack in various implementations of cryptographic algorithms，which are described by the Enhanced Data Dependence Graph（EDDG)，and analyzes the timing attack vulnerabilities by finding some intermediary variable in the EDDG.The number of time samples required for a successful timing attack is used to characterize the resistibility，which is computed based on the signal-to-noise ratio of the corresponding timing attack.

side-channel attack；timing attack；enhanced data dependence graph；quantitative evaluation

TP309

A

10.3969/j.issn.1007-130X.2014.04.012

2013-06-05；

2013-10-28

國家自然科學基金資助項目（60973035，61202481)

通訊地址：430068湖北省武漢市湖北工業大學電氣與電子工程學院

Address：Department of Electrical ＆ Electronic Engineering，Hubei University of Technology，Wuhan 430068，Hubei，P.R.China

1007-130X（2014)04-0639-05

賀章擎（1980-)，男，湖北天門人，博士生，講師，研究方向為信息安全與數字集成電路設計。E-mail：ivan＿hee＠126.com

HE Zhang－qing，born in 1980，PhD candidate，lecturer，his research interests include information security，and digital integrated circuit design.

戴葵（1968-)，男，湖北恩施人，博士，教授，研究方向為高性能處理器系統設計與信息安全。E-mail：daikui＠mail.hust.edu.cn

DAI Kui，born in 1968，PhD，professor，his research interests include high performance processor system design，and information security.

童元滿（1982-)，男，安徽太湖人，博士，講師，研究方向為高性能處理器系統設計與信息安全。E-mail：yuanmantong＠yahoo.com.cn

TONG Yuan-man，born in 1982，PhD，lecturer，his research interests include high performance processor system design，and information security.

鄒雪城（1964-)，男，湖北京山人，博士，教授，研究方向為超大規模集成電路設計。E-mail：estxczou＠gmail.com

ZOU Xue-cheng，born in 1964，PhD，professor，his research interest includes VLSI design.