橢圓曲線加密算法的邊信道攻擊*

陳 力,葛萬(wàn)成

(同濟(jì)大學(xué)中德學(xué)院,上海200092)

橢圓曲線加密算法的邊信道攻擊*

陳 力,葛萬(wàn)成

(同濟(jì)大學(xué)中德學(xué)院,上海200092)

橢圓曲線加密算法是目前已知的公共密鑰體系中加密強(qiáng)度最高的一種算法,為了將其破解,采用邊信道攻擊,即通過(guò)對(duì)密碼機(jī)在加密過(guò)程中的功率變化的分析來(lái)嘗試獲取密鑰信息,從而繞過(guò)了從數(shù)學(xué)上破譯橢圓曲線密鑰極其困難的問(wèn)題。所搭建的實(shí)驗(yàn)平臺(tái),利用示波器探測(cè)正在運(yùn)行加密程序的設(shè)備,對(duì)其中進(jìn)行差分功率分析,從而找到加密規(guī)則。實(shí)驗(yàn)結(jié)果驗(yàn)證了所采用方法的有效性。

橢圓曲線加密 密鑰 破解 邊信道攻擊

0 引 言

密碼學(xué)是以研究秘密通信為目的的一門(mén)學(xué)科,對(duì)所要傳送的信息采取一定的保護(hù)措施,以防止未經(jīng)授權(quán)的第三方竊取信息。密碼學(xué)發(fā)展至今,已經(jīng)成為一門(mén)綜合性的尖端技術(shù)科學(xué)。它與數(shù)學(xué)、語(yǔ)言學(xué)、電子學(xué)、計(jì)算機(jī)科學(xué)、信息論等學(xué)科有著日益密切的聯(lián)系。與此同時(shí),密碼破譯技術(shù)也隨著科技的不斷進(jìn)步發(fā)生著日新月異的變化,借助的設(shè)備越來(lái)越先進(jìn),破譯手段越來(lái)越高明。密碼學(xué)與密碼破譯技術(shù)相互鉗制,相互促進(jìn),共同向前發(fā)展。

密碼是通信雙方按照事先約定的法則進(jìn)行信息轉(zhuǎn)換的一種工具。依照密碼的機(jī)制,明文變?yōu)槊芪?此為加密變換;變密文為明文,稱為解密變換[1]。近代以前,密碼主要對(duì)文字或數(shù)字進(jìn)行加密、解密變換。而伴隨著其他學(xué)科的發(fā)展,現(xiàn)在對(duì)于語(yǔ)音、圖像、數(shù)據(jù)等信息都可以實(shí)現(xiàn)加密、解密過(guò)程。

20世紀(jì)70年代以來(lái),美國(guó)學(xué)者提出了公共密鑰體系,有別于傳統(tǒng)密鑰體系,即運(yùn)用單向函數(shù)的數(shù)學(xué)原理,以實(shí)現(xiàn)加密密鑰、解密密鑰的分離。加密密鑰是公開(kāi)的,解密密鑰是保密的[2]。這種新的密碼體制,引起了密碼學(xué)界的廣泛注意和探討,公共密鑰體系近幾十年來(lái)從理論到實(shí)踐都發(fā)展迅速,已經(jīng)成為當(dāng)今密碼學(xué)的主要研究方向和應(yīng)用領(lǐng)域。

本課題研究基于橢圓曲線密碼學(xué),如何通過(guò)邊道(Side-Channel)信息獲取密鑰信息。由于橢圓曲線加密算法的安全性非常高,通過(guò)數(shù)學(xué)算法破解的難度非常大[3],同時(shí)需要花費(fèi)很長(zhǎng)的時(shí)間。因此邊信道攻擊是一種比較有效的破解方式。本文通過(guò)設(shè)計(jì)實(shí)驗(yàn),實(shí)現(xiàn)了一個(gè)通過(guò)尋找密碼機(jī)加密過(guò)程中的功率變化與密文之間的關(guān)系,成功獲取明文的例子。

1 邊信道攻擊

傳統(tǒng)的密碼分析假定對(duì)手只能訪問(wèn)密碼設(shè)備的輸入和輸出對(duì),但沒(méi)有關(guān)于該設(shè)備的內(nèi)部狀態(tài)的知識(shí)。然而,隨著邊信道分析的提出,帶來(lái)了一個(gè)全新的密碼學(xué)分析的視角。邊信道分析顯示了一個(gè)密碼設(shè)備,在加密過(guò)程中可以泄露其內(nèi)部狀態(tài)的重要信息。通過(guò)監(jiān)測(cè)的密碼設(shè)備加密的時(shí)間信息,溫度功耗,電磁輻射或其他信息,攻擊者可以獲取內(nèi)部數(shù)據(jù)或操作的信息,并通過(guò)分析這些信息獲取加密算法的密鑰,以避開(kāi)數(shù)學(xué)算法破解的難題[4]。

邊信道密碼分析主要通過(guò)觀察芯片運(yùn)行過(guò)程中的功耗軌跡來(lái)獲取一些與密鑰相關(guān)的有用信息,特別適合于攻擊具有分支結(jié)構(gòu)的加密算法[5]。該方法似乎沒(méi)有傳統(tǒng)密碼分析學(xué)的更加一般化,但是如今在實(shí)際破譯中邊信道密碼分析更為強(qiáng)大和有效。

數(shù)學(xué)方法是分析密碼學(xué)設(shè)備的有效工具,通過(guò)數(shù)學(xué)方法可以評(píng)估密碼的加密強(qiáng)度。實(shí)際實(shí)現(xiàn)各種加密算法必定是通過(guò)某種硬件設(shè)備。這些硬件設(shè)備在進(jìn)行加密或解密的過(guò)程中,必定有功耗或是其周?chē)碾姶艌?chǎng)發(fā)生變化。這些變化會(huì)涉及到密鑰信息。

文中使用差分功耗分析(DPA,Differential Power Analysis)?；贒PA[6]的攻擊需要大量的功率波形。DPA使用數(shù)學(xué)統(tǒng)計(jì)方法去分析該密碼設(shè)備的密鑰信息。通常一個(gè)基于橢圓曲線的DPA攻擊執(zhí)行如下:

第1步:選擇一個(gè)橢圓曲線算法,計(jì)算該算法的中間值。這中間值是一個(gè)函數(shù)f(d,k),其中d是一個(gè)已知的非恒定的數(shù)值,k是密鑰的一部分。

第2步:讓對(duì)N塊不同的數(shù)據(jù)進(jìn)行加密或解密,并測(cè)量加密設(shè)備的功率損耗。攻擊者應(yīng)該知道相應(yīng)的數(shù)據(jù)值d,可以表示為一個(gè)向量d=(d1,d2,…,dN),di表示第i個(gè)加密或解密的數(shù)據(jù)值。和其對(duì)應(yīng)的功率曲線可以表示為p′i=(pi,1,pi,2,…,pi,T),其中T為功率曲線的長(zhǎng)度。而對(duì)于所有的N個(gè)不同的數(shù)據(jù)塊的功率曲線可以寫(xiě)成一個(gè)矩陣P,其尺寸為N×T[7]。

第3步:對(duì)每一個(gè)可能的密鑰k計(jì)算出一個(gè)假設(shè)中間值,假設(shè)一共有K個(gè)可能的選擇,可作表示為一個(gè)向量k=(k1,k2,…,kK)。對(duì)于所有的N個(gè)數(shù)據(jù)塊和所有可能的密鑰k,可以計(jì)算出一個(gè)大小為T(mén) ×K的假設(shè)中間值f(d,k)的矩陣V,其中的任意一個(gè)元素可以表示為

第4步:將矩陣V映射到一個(gè)假設(shè)的功率損耗值矩陣H。通過(guò)仿真,利用如漢明距離模型將每個(gè)假設(shè)中間值vi,j是映射到一個(gè)假設(shè)的功耗值hi,j。

第5步:對(duì)比假設(shè)的功率損耗值和實(shí)際測(cè)量的功率損耗值,將矩陣H的每列hi和矩陣P每列的pj相比,這種比較的結(jié)果是一個(gè)矩陣R,大小為K×T。

2 邊信道攻擊實(shí)驗(yàn)平臺(tái)

圖1為實(shí)驗(yàn)平臺(tái)的示意圖。實(shí)驗(yàn)平臺(tái)包括一個(gè)安捷倫DSO9254A示波器,一個(gè)SmartFusion的測(cè)試板和基于Linux系統(tǒng)的計(jì)算機(jī)。而除了這些硬件組件,數(shù)據(jù)收集和處理是借助MATLAB Control Toolbox,VXI-11協(xié)議,串行通信協(xié)議。

圖1 實(shí)驗(yàn)平臺(tái)示意Fig.1 Experimental platform

從圖1可以看出,計(jì)算機(jī)與安捷倫示波器之間的通信是基于VXI-11協(xié)議,計(jì)算機(jī)和SmartFusion測(cè)試板通過(guò)USB連接,并且計(jì)算機(jī)通過(guò)USB連接為SmartFusion測(cè)試板提供電能。測(cè)試板通過(guò)一個(gè)用戶I/O口提供外部時(shí)鐘信號(hào)給示波器,同時(shí)它也提供了示波器進(jìn)行測(cè)量的觸發(fā)信號(hào),使我們可以同步測(cè)量SmartFusion測(cè)試板上的加密設(shè)備的功耗。

3 攻擊過(guò)程及數(shù)據(jù)分析

按照預(yù)測(cè)中間值(0或1),我們將功率損耗曲線分成對(duì)應(yīng)的兩部分。將預(yù)測(cè)中間值是0的功率損耗曲線相加并求平均值,得到預(yù)測(cè)值為0的平均功率損耗曲線;將預(yù)測(cè)中間值是1的功率損耗曲線相加并求平均值,得到預(yù)測(cè)值為1的平均功率損耗曲線。我們計(jì)算出兩條功率損耗曲線的差別。如果有明顯差異曲線的峰值,則假設(shè)是正確的。否則,假設(shè)是錯(cuò)誤的。

圖2 基于比特模式的DPA攻擊原理示例Fig.2 Principle of DPA attacks based on bits

圖2顯示了基于比特模式的DPA攻擊。標(biāo)量r的第一位是已知的,其值是1。攻擊的目的是試圖找出其余位的值。根據(jù)蒙哥馬利階梯算法,1號(hào)位的值可由確2號(hào)位和3號(hào)位的值決定。具體攻擊過(guò)程可以表示如圖3所示。

圖3 基于比特模式的DPA攻擊過(guò)程示意Fig.3 Process of DPA attacks based on bits

實(shí)驗(yàn)結(jié)果顯示,4P、5P和8P假設(shè)的差異曲線有明顯的峰值出現(xiàn),而6P和7P假設(shè)的差異曲線沒(méi)有明顯的峰值出現(xiàn)(見(jiàn)圖4～圖8)。在加密過(guò)程中,如果預(yù)測(cè)的中間值被使用了,如圖4顯示,那么在差異曲線中將會(huì)出現(xiàn)峰值。這意味著,7P假設(shè)沒(méi)有在加密過(guò)程中出現(xiàn)。根據(jù)圖3可以斷定,在標(biāo)量r的第1位是0。由于4P假設(shè)的峰值高于基于6P假設(shè)的峰值,那么它可以猜測(cè)標(biāo)量r的第二位為0的概率更大。

4P和5P的差異曲線有兩個(gè)峰(見(jiàn)圖4和圖5),它們代表從寄存器到寄存器的一個(gè)讀操作和一個(gè)寫(xiě)操作。但在圖8中只有一個(gè)峰值,這是因?yàn)?我們只觀察兩個(gè)位,與8P假設(shè)的差異曲線峰值已經(jīng)超出示波器的觀測(cè)范圍。

圖4 4P的差異曲線Fig.4 Cross-correlation function for 4P

圖5 5P的差異曲線Fig.5 Cross-correlation function for 5P

圖6 6P的差異曲線Fig.6 Cross-correlation function for 6P

圖7 7P的差異曲線Fig.7 Cross-correlation function for 7P

圖8 8P的差異曲線Fig.8 Cross-correlation function for 8P

4 結(jié) 語(yǔ)

雖然進(jìn)行邊信道攻擊的前提條件(即獲得密碼機(jī))比較苛刻,但它在應(yīng)對(duì)復(fù)雜的橢圓曲線編碼時(shí)可以得到令人滿意的結(jié)果。因此邊信道攻擊仍是一種有效的密碼破解技術(shù)。更重要的是,通過(guò)對(duì)邊信道攻擊的模擬,我們對(duì)其攻擊手段和特點(diǎn)進(jìn)行研究,使現(xiàn)有的加密算法能夠得到針對(duì)性優(yōu)化,從而能夠防范此類攻擊,提高加密的安全性。所謂知己知彼百戰(zhàn)不殆,邊信道攻擊的分析研究對(duì)于密碼學(xué)的發(fā)展具有重大意義。

[1] JOACHIMS Woboda,SPITZS Tephanand,PRAMATERFTAKIS Michael.Kryptographie und IT-Sicherheit: Grundlagen und Anwendungen[J].ViewegTeubner, 2008,21(04):199-202.

[2] KOBLITZ Neal.Elliptic Curve Cryptosystems[J].Mathematics of Computation,1987,48(02):203-209.

[3] MILLER V.Use of Elliptic Curves in Cryptography[C]// Proc 4th IEEE Conf Evolutionary Computation.Berlin: Springer-Verlag,1996:417-428.

[4] STALLINGS William.Cryptography and Network Security Principles and Practices[M].New York:House of Electronics Industry,2006:210-224.

[5] 葉賓.安全芯片之安全性分析[J].通信技術(shù),2013, 46(08):91-92.

YE Bin.Security Analysis of Security Chip[J].Communications Technology,2013,46(08):91-92.

[6] KOBLITZ Neal.The State of Elliptic Curve Encryption Algorithm[J].Designs Codes and Cryptography,2000, 19(01):173-193.

[7] KOCHER P.Timing Attacks on Implementations of Diffie -Hellman,RSA,DSS,and Other Systems[C]//PACIIA1996.USA:Springer-Verlag,1996:109-113.

CHENLi(1990-),male,graduate student,mainly engaged in the research of signal and information processing.

葛萬(wàn)成(1964—),男,博士,教授,主要研究方向?yàn)樾盘?hào)與信息處理。

GE Wan-cheng(1964-),male,Ph.D.,professor,principally working at signal and information processing.

Side-Channel Attack on Elliptic Curve Encryption Algorithm

CHEN Li,GE Wang-cheng
(Chinese-German School for Postgraduate Studies,Tongji University,Shanghai 200092,China)

Elliptic-curve encryption algorithm is currently known as the best algorithm in the public-key cryptosystem.In order to break it,a side-channel information attack is designed and used.With near-field probe to measure the power traces generated by the chip,the relation between the power traces and secret key is tried to find out.In this way,the mathematical problems can be avoided.In the experiment,oscilloscope is used to acquire the data from the crypto device and then to analyze them.From the differential power analysis,the secret key may be found.The experiment shows that the side-channel attack could work effectively.

elliptic curve encryption;secret key;decipher;side-channel attack

TN918

A

1002-0802(2014)09-1062-04

10.3969/j.issn.1002-0802.2014.09.017

陳 力(1990—),男,碩士研究生,主要研究方向?yàn)樾盘?hào)與信息處理;

2014-06-23;

2014-07-24 Received date：2014-06-23;Revised date：2014-07-24