陳 力,葛萬成

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

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

陳 力,葛萬成

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

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

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

0 引 言

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

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

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

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

1 邊信道攻擊

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

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

數(shù)學(xué)方法是分析密碼學(xué)設(shè)備的有效工具,通過數(shù)學(xué)方法可以評估密碼的加密強度。實際實現(xiàn)各種加密算法必定是通過某種硬件設(shè)備。這些硬件設(shè)備在進行加密或解密的過程中,必定有功耗或是其周圍的電磁場發(fā)生變化。這些變化會涉及到密鑰信息。

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

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

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

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

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

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

2 邊信道攻擊實驗平臺

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

圖1 實驗平臺示意Fig.1 Experimental platform

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

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

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

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

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

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

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

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

圖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īng)對復(fù)雜的橢圓曲線編碼時可以得到令人滿意的結(jié)果。因此邊信道攻擊仍是一種有效的密碼破解技術(shù)。更重要的是,通過對邊信道攻擊的模擬,我們對其攻擊手段和特點進行研究,使現(xiàn)有的加密算法能夠得到針對性優(yōu)化,從而能夠防范此類攻擊,提高加密的安全性。所謂知己知彼百戰(zhàn)不殆,邊信道攻擊的分析研究對于密碼學(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.

葛萬成(1964—),男,博士,教授,主要研究方向為信號與信息處理。

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—),男,碩士研究生,主要研究方向為信號與信息處理;

2014-06-23;

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