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

陳 力,葛萬成

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

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

陳 力,葛萬成

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

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

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

0 引 言

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

密碼是通信雙方按照事先約定的法則進行信息轉換的一種工具。依照密碼的機制,明文變為密文,此為加密變換;變密文為明文,稱為解密變換[1]。近代以前,密碼主要對文字或數字進行加密、解密變換。而伴隨著其他學科的發展,現在對于語音、圖像、數據等信息都可以實現加密、解密過程。

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

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

1 邊信道攻擊

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

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

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

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

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

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

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

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

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

2 邊信道攻擊實驗平臺

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

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

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

3 攻擊過程及數據分析

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

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

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

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

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

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

圖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 結 語

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

[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].通信技術,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