陳 曼,羅 順

(1.保密通信重點(diǎn)實(shí)驗室,四川成都610041;2.上海通用識別技術(shù)研究所,上海201112)

掩碼方案中的最優(yōu)預(yù)處理技術(shù)*

陳 曼1,羅 順2

(1.保密通信重點(diǎn)實(shí)驗室,四川成都610041;2.上海通用識別技術(shù)研究所,上海201112)

本文旨在說明優(yōu)化處理技術(shù)攻擊帶掩碼實(shí)現(xiàn)的密碼算法的有效性。在攻擊者擁有一塊可自由操控的、與待攻擊密碼設(shè)備硬件實(shí)現(xiàn)完全相同而密鑰不同的設(shè)備的條件下,本文給出了利用高階相關(guān)能量分析攻擊和碰撞攻擊破解密碼算法掩碼實(shí)現(xiàn)方案時的最優(yōu)化處理技術(shù)。本文在接觸式智能卡芯片上實(shí)現(xiàn)了Herbst等人提出的掩碼AES算法,對于待攻擊的硬件采集了5000條能耗波形,證實(shí)了兩種預(yù)處理技術(shù)的有效性。

預(yù)處理技術(shù) 高階相關(guān)能量分析攻擊 碰撞攻擊 掩碼

0 引 言

自1999年Kocher等人提出能量分析攻擊技術(shù)以來[1],其對實(shí)際密碼產(chǎn)品具有較高的安全威脅[2-3],從而引起了人們的極大關(guān)注。Kocher等人開辟了密碼攻防的新方向。

從攻擊者的角度,為提高能量分析攻擊的有效性,人們對Kocher的方法進(jìn)行了改進(jìn),提出了高階相關(guān)能量分析攻擊、碰撞攻擊以及多種優(yōu)化方法[4-5]。2012年,Oswald等人對能量分析技術(shù)進(jìn)行分析,考慮最常用的相關(guān)系數(shù)方法的運(yùn)算規(guī)則,提出了一種最優(yōu)的線性變換預(yù)處理技術(shù)[6]。實(shí)驗證明,他們的預(yù)處理技術(shù)能有效提高能量分析攻擊的有效性。

從防御者的角度,為了防止能量分析攻擊,業(yè)界提出了很多防御措施。最常用的一種防御措施是使用掩碼。掩碼技術(shù)旨在消除產(chǎn)品運(yùn)行時產(chǎn)生的能量泄露與密碼運(yùn)算中間值之間的相關(guān)性,從而保護(hù)密碼產(chǎn)品安全。而實(shí)際中,由于掩碼使用的不合理,如掩碼重用,即使使用掩碼技術(shù)的密碼產(chǎn)品仍然存在被攻擊的風(fēng)險。

本文將Oswald等人提出的最優(yōu)化預(yù)處理技術(shù)應(yīng)用到掩碼重用的密碼實(shí)現(xiàn)方案中,研究最優(yōu)化預(yù)

處理技術(shù)攻擊掩碼方案的有效性。本文實(shí)現(xiàn)了Herbst等人提出的AES掩碼方案,利用其能耗波形,在使用最優(yōu)化預(yù)處理方案后僅使用5000條波形即可對掩碼方案實(shí)施成功攻擊。

本文主要結(jié)構(gòu)如下:第一節(jié)描述了能量分析攻擊及防御技術(shù)及本文的貢獻(xiàn);第二節(jié)介紹了掩碼AES實(shí)現(xiàn)方案和最優(yōu)預(yù)處理技術(shù);第三節(jié)研究高階相關(guān)能量分析攻擊和碰撞攻擊的最優(yōu)預(yù)處理技術(shù);第四節(jié)利用智能卡運(yùn)行AES算法時產(chǎn)生的能耗波形驗證最優(yōu)預(yù)處理技術(shù)的有效性。

1 背景知識

1.1 AES掩碼實(shí)現(xiàn)方案

AES算法中,非線性S盒是掩碼實(shí)現(xiàn)的重點(diǎn)和難點(diǎn)?？偨Y(jié)已有的參考文獻(xiàn),S盒的掩碼實(shí)現(xiàn)分為帶掩碼的查表運(yùn)算[7]和掩碼S盒計算[8]兩種方式。查表運(yùn)算通常占用較多的存儲單元,而掩碼S盒計算則需要更多的運(yùn)算周期。出于實(shí)際產(chǎn)品面積、成本、速率要求方面的考慮,一般的掩碼方案使用同一個掩碼保護(hù)多個中間值,為高階相關(guān)能量分析攻擊[9]和碰撞攻擊[10]提供了可能性。

本文以ACNS 2006上Herbst等人提出的帶掩碼的查表運(yùn)算[7]為例,以對它的攻擊效率來說明掩碼方案最優(yōu)預(yù)處理技術(shù)的有效性。使用相同的方法,可對一般的帶掩碼實(shí)現(xiàn)進(jìn)行攻擊。

Herbst等人的方法如圖1所示。給定輸入掩碼和輸出掩碼,帶掩碼的查表運(yùn)算使用S′(a⊕M)=S(a)⊕M′。使用掩碼M1′,M2′,M3′,M4′來隨機(jī)化明文。使用掩碼M1⊕M′,M2⊕M′,M3⊕M′,M4⊕M′對查表得到的值進(jìn)行隨機(jī)化。其中Mic(M1,M2,M3,M4)=(M1′,M2′,M3′,M4′),Mic表示列混合運(yùn)算。

圖1 AES掩碼實(shí)現(xiàn)方案Fig.1 Masked AES implementation

1.2 最優(yōu)預(yù)處理技術(shù)

CARDIS2012上,Oswald等人對能量分析攻擊進(jìn)行分析,提出了一種最優(yōu)的線性變換預(yù)處理技術(shù)[6]。該預(yù)處理技術(shù)考慮能耗波形上多個樣本點(diǎn)的能耗值,使用線性變換,將多維能耗泄露轉(zhuǎn)化為一維泄露。在變換過程中,引入權(quán)重的概念,最大化有效樣本點(diǎn)(即泄露點(diǎn))的能耗值,去除無關(guān)樣本點(diǎn)的能耗值。

Oswald等人的方法要求攻擊者擁有兩塊硬件實(shí)現(xiàn)完全相同而密鑰不一定相同的密碼設(shè)備,一塊是攻

擊者已知密鑰、可自由操控的設(shè)備,另一塊則是未知密鑰、待攻擊的設(shè)備。攻擊者利用可自由操控設(shè)備獲取攻擊位置、優(yōu)化參數(shù)等信息。在破解待攻擊設(shè)備時使用這些信息可提高密鑰破解效率。根據(jù)能量分析攻擊的一般方法,在采集到密碼產(chǎn)品的能量消耗波形后,利用相關(guān)系數(shù)的方法進(jìn)行密鑰恢復(fù)。用表示能量消耗波形各個樣本點(diǎn)的值,表示密碼算法中間值hi(key,P)組成的向量,即=(h1(key,P),…,hn(key,P))。對于固定的密鑰key,為找到最優(yōu)的線性變換系數(shù)攻擊者計算相關(guān)系數(shù)公式:

這里key表示正確密鑰,Koptim表示錯誤密鑰的集合,表示集合Koptim中元素的個數(shù)。

2 掩碼實(shí)現(xiàn)的最優(yōu)預(yù)處理技術(shù)

對于Oswald的掩碼實(shí)現(xiàn)方案,多個密碼運(yùn)算中間值使用相同的掩碼進(jìn)行保護(hù)。采用高階相關(guān)能量分析攻擊或碰撞攻擊的方法,可能對重用型掩碼實(shí)現(xiàn)方案進(jìn)行攻擊。

使用預(yù)處理技術(shù),同時使用能量消耗波形上多個不同點(diǎn)的泄露信息,攻擊的有效性將會大幅提高。分析密碼算法的實(shí)現(xiàn),通常為了設(shè)計的簡便性及實(shí)現(xiàn)的快捷性,相同的密碼操作使用相同的電路結(jié)構(gòu),因此,它們產(chǎn)生能量泄露的時間是一致的。這種一致性為尋找最優(yōu)預(yù)處理技術(shù)提供了途徑。

用Y1,Y2表示密碼算法中間值,即Y1=h(key1,P)⊕m,Y2=h(key2,P)⊕m。X1,X2表示與Y1,Y2對應(yīng)的能量消耗波形上某泄露點(diǎn)處的能耗值。用表示密碼算法中間值與掩碼運(yùn)算后構(gòu)成的向量,=(h1(key1,P)⊕m1,…,hn(key1,P)⊕mn),=(h1(key2,P)⊕m1,…,hn(key2,P)⊕mn)。,表示與對應(yīng)的能量消耗波形各個樣本點(diǎn)值構(gòu)成的向量。假設(shè)對于已知密鑰的密碼產(chǎn)品,加密N個不同的明文,得到N條不同的能量消耗波形,每條能量消耗波形上有MT個樣本點(diǎn),對應(yīng)L個不同的密碼運(yùn)算中間值。

2.1 基于高階相關(guān)能量分析攻擊的最優(yōu)預(yù)處理

在中間值對應(yīng)的能量泄露波形中選取一個泄露點(diǎn),使用式(3)所示的相關(guān)系數(shù)計算公式進(jìn)行高階相關(guān)能量分析攻擊。根據(jù)能耗值的特性,X1-X2與Y1⊕Y2之間存在相關(guān)性。攻擊者猜測的密鑰字節(jié)key1,key2正確時,式(3)計算得到最大相關(guān)系數(shù),這里需要遍歷拆分后的密鑰段的整個密鑰空間。

為了同時使用能量消耗波形上多個泄露點(diǎn)的信息,使用Oswald等人最優(yōu)預(yù)處理的思想,尋找最優(yōu)的線性變換系數(shù)。假設(shè)有線性系數(shù)高階相關(guān)能量分析攻擊相關(guān)系數(shù)的計算公式如式(4)所示。

式(5)中,Koptim是所有可能字節(jié)組成的密鑰空間除去正確密鑰形成的集合。對于任意的,式 (5)中存在相同的因子,略去該因子不影響最大值對應(yīng)的變換系數(shù),因此,式(5)可進(jìn)一步轉(zhuǎn)換成式(6)。

實(shí)際進(jìn)行攻擊時,通常選取中間值為某個數(shù)值而非多維向量,此時,變換系數(shù)變?yōu)閿?shù)值β,相應(yīng)的變換系數(shù)可轉(zhuǎn)化為(),也就是說,變換系數(shù)β可省略。式(6)可進(jìn)一步減化為式(7)。

2.2 基于碰撞攻擊的最優(yōu)預(yù)處理

使用碰撞攻擊的思想,猜測key1,key2的關(guān)系并選取合適的明文值,若猜測的密鑰關(guān)系正確,則總有Y1=Y2,此時X1=X2有較大相關(guān)性,式(8)得出的相關(guān)系數(shù)值較大;而若猜測的密鑰關(guān)系錯誤,式(8)相當(dāng)于是計算隨機(jī)值產(chǎn)生的能耗值之間的相關(guān)性,相關(guān)系數(shù)較小。

為了拓展式(8)的碰撞模型,選取合適的濾波參數(shù)綜合使用能量消耗波形上多個泄露點(diǎn)的信息,本文采用Oswald等人最優(yōu)預(yù)處理的思想。式(8)的計算僅與X相關(guān)而不涉及中間值Y。此僅需計算變換系數(shù)。碰撞攻擊相關(guān)系數(shù)的計算公式如(9)式所示

為了最優(yōu)化使用各樣本點(diǎn)的能耗值,減小成功攻擊所需的波形數(shù)量,需要使用最優(yōu)化的。根據(jù)Oswald的思想,為避免過度匹配的影響,使用式(10)計算正確密鑰的區(qū)分度,區(qū)分度最大的即是最優(yōu)的預(yù)處理變換系數(shù)。

式(10)中,Koptim是所有可能密鑰組成的空間除去正確密鑰關(guān)系形成的集合。對于任意的,式(10)中存在相同的因子,略去該因子不影響最大值對應(yīng)的變換系數(shù),因此,式(10)可進(jìn)一步轉(zhuǎn)換成式(11)。

3 實(shí)驗結(jié)果

我們在通用的智能卡芯片上實(shí)現(xiàn)了Herbst等人提出的AES掩碼實(shí)現(xiàn)方案,并對其進(jìn)行了攻擊。我們將AES的128位運(yùn)算值分成4*4字節(jié)組成的矩陣,字節(jié)的處理順序為1,5,9,13,2,6,10,14,3, 7,11,15,4,8,12,16。

使用力科示波器WAVE RUNNER 610Zi,設(shè)置采樣率為250MSa/s,在字節(jié)1和字節(jié)5進(jìn)行S盒操作采集其能耗波形?？偣矊?000個隨機(jī)選取的明文進(jìn)行

了加密操作,采集得到5000條能耗波形。字節(jié)1對應(yīng)的密鑰字節(jié)為0X00,字節(jié)5對應(yīng)的密鑰波形為0XC7。本文使用這些能耗波形,分別在使用/不使用最優(yōu)化預(yù)處理技術(shù)時,對AES實(shí)現(xiàn)進(jìn)行了攻擊。

3.1 高階相關(guān)能量分析攻擊

在采集得到的能耗波形上,隨機(jī)選取一個樣本點(diǎn),在MATLAB中編程實(shí)現(xiàn)高階相關(guān)能量分析攻擊,攻擊結(jié)果如圖2所示(這里只列出了密鑰字節(jié)1為0X00時,密鑰字節(jié)5遍歷0-255時,相關(guān)系數(shù)的大小)。由圖可知,在相關(guān)系數(shù)值為0.035附近出現(xiàn)多個尖峰,尖峰幅值區(qū)別不明顯,正確密鑰字節(jié)0XC7=199不能被有效區(qū)分出來。

圖2 隨機(jī)選取樣本點(diǎn)的高階相關(guān)能量分析攻擊Fig.2 High-order correlation attack related to a random sample point

使用2.1節(jié)基于高階相關(guān)能量分析攻擊的最優(yōu)預(yù)處理方法計算得到的最優(yōu)預(yù)處理參數(shù),本文對波形進(jìn)行了預(yù)處理,并對預(yù)處理后的波形進(jìn)行了高階相關(guān)能量分析攻擊,攻擊結(jié)果如圖3所示(這里只列出了密鑰字節(jié)1為0X00時,密鑰字節(jié)5遍歷0-255時,相關(guān)系數(shù)的大小)。由圖(3)可知,密鑰字節(jié)0XC7對應(yīng)的相關(guān)系數(shù)為0.072,而其它密鑰字節(jié)候選值對應(yīng)的相關(guān)系數(shù)均小于0.04,正確密鑰字節(jié)0XC7=199被有效識別。

圖3 最優(yōu)預(yù)處理后的高階相關(guān)能量分析攻擊Fig.3 High-order correlation attack after optimal pre-processing

3.2 碰撞攻擊

在采集得到的能耗波形上,隨機(jī)選取一個樣本點(diǎn),使用MATLAB編程進(jìn)行碰撞攻擊,攻擊結(jié)果如圖4所示。由圖可知,多個密鑰關(guān)系導(dǎo)出尖峰,這些尖峰幅值差別不明顯,正確的密鑰關(guān)系0X00⊕0XC7=0XC7=0XC7=199不能被有效區(qū)分出來。

圖4 隨機(jī)選取樣本點(diǎn)的碰撞攻擊Fig.4 Collision attack related to a random sample point

使用3.2節(jié)基于碰撞攻擊的最優(yōu)預(yù)處理方法計算得到的最優(yōu)預(yù)處理參數(shù),本文對波形進(jìn)行了預(yù)處理,并對預(yù)處理后的波形進(jìn)行了碰撞攻擊,攻擊結(jié)果如圖5所示。由圖可知,密鑰關(guān)系0XC7=199對應(yīng)相關(guān)系數(shù)值為0.042,而其它密鑰關(guān)系對應(yīng)的相關(guān)系數(shù)值均小于0.03,正確密鑰關(guān)系0XC7=199被有效識別。

圖5 最優(yōu)預(yù)處理后的碰撞攻擊Fig.5 Collision attack after optimal pre-processing

4 結(jié) 語

本文實(shí)驗結(jié)果表明,最優(yōu)預(yù)處理技術(shù)可有效提升對加入了掩碼對策的密碼實(shí)現(xiàn)攻擊效率。因此,

本文建議,在使用掩碼方案時盡可能使用不同的掩碼來保護(hù)中間值,同時結(jié)合其它的防御措施,如隨機(jī)化時鐘,隨機(jī)操作序列等來增強(qiáng)防護(hù)能力。

本文提出的最優(yōu)預(yù)處理技術(shù)要求攻擊者擁有兩塊硬件實(shí)現(xiàn)完全相同而密鑰不一定相同的密碼設(shè)備,一塊是攻擊者已知密鑰、可自由操控的設(shè)備,另一塊則是未知密鑰、待攻擊的設(shè)備。在某些情況下,這樣的條件并不能實(shí)現(xiàn),因此,如何在僅有待攻擊設(shè)備情況下使用最優(yōu)預(yù)處理技術(shù),并將其應(yīng)用到密碼算法的掩碼實(shí)現(xiàn)中,是一個值得深入研究的課題。

[1] KOCHER,P.C.,JAFFE,J.,Jun,B.Differential Power Analysis[C]//CRYPTO 1999.Heidelberg:Springer, 1999:388-397.

[2] EISENBARTH,T.,KASPER,T.,Moradi,A.,Paar, C.,Salmasizadeh,M.,Shalmani,M.T.M.On the Power of Power Analysis in the RealWorld:A Complete Break of the KeeLoq Code Hopping Scheme[C]// CRYPTO 2008.Heidelberg:Springer,2008:203-220.

[3] MORADI,A.,BARENGHI,A.,KASPER,T.,Paar, C.On the Vulnerability of FPGA Bitstream Encryption against Power Analysis Attacks Extracting Keys from Xilinx Virtex-II FPGAs.[C]//Proceedings of ACM CCS 2011.ACMPress:111-124.

[4] CLAVIER,C.,CORON,J.-S.,DABBOUS,N.Differential Power Analysis in the Presence of Hardware Countermeasures.[C]//CHES 2000.Heidelberg: Springer,2000:252-263.

[5] CHARVET,X.,PELLETIER,H.Improving the DPA Attack Using Wavelet Transform.[C]//NIST Physical Security Testing Workshop(2005):USA:Honolulu, 2005:121-125.

[6] OSWALD,D.and C.PAAR.Improving Side-Channel Analysiswith Optimal Linear Transforms[C]//CARDIS. Heidelberg:Springer,2012:219-233.

[7] HERBST,P.,OSWALD,E.,MANGARD,S.An AES Smart Card Implementation Resistant to Power Analysis Attacks[C]//ACNS 2006.Heidelberg:Springer,2006: 239-252.

[8] PROUFF,E.and ROCHE,T.Higher-Order Glitches Free Implementation of the AESUsing Secure Multi-party Computation Protocols[C]//CHES 2011.Heidelberg:Springer,2011:63-78.

[9] PEETERS,E.,STANDAERT,F.-X.,Donckers,N. and Quisquater,J.-J..Improved Higher Order Side-Channel Attacks with FPGA experiments[C]//CHES 2005.Heidelberg:Springer,2006:157-171.

[10] BOGDANOV,A.Multiple-differential side-channel collision attacks on AES[C]//CHES 2008.Heidelberg:Springer,2008:30-44.

陳 曼(1988—),女,助理工程師,主要研究方向為密碼算法側(cè)信道攻擊與防御; CHEN Man(1988-),female,assistantengineer,mainly engaged in side-channel attack and defence of crypto algorithm.

羅 順(1985—),男,工程師,主要研究方向為通信技術(shù)。

LUO Shun(1985-),male,engineer,mainly engaged in communication technology.

夏愛民(1977—),男,博士,高級工程師,主要研究方向為計算機(jī)網(wǎng)絡(luò)工程、信息安全;

XIA Ai-min(1977-),male,Ph.D.,senior engineer,mainly engaged in computer networking engineering and information security.

程 芳(1975—),女,博士,主要研究方向為信息工程;

CHENG Fang(1975-),female,Ph.D.,maily engaged in information engineering.

張宏志(1983—),男,碩士,主要研究方向為計算機(jī)與通信工程。

ZHANGHong-zhi(1983-),male,M.Sci.,maily engaged in computer and communication engineering.

Optimal Pre-Processing Techniques in M asked Im plementations

CHEN Man1,LUO Shun2
(1.Science and Technology on Communication Security Laboratory,ChengduSichuan 610041,China;
(2.ShanghaiGeneral Recognition Technology Institute,Shanghai201112,China)

This paper expounds the validity of pre-processing techniques in masked implementations of crypto algorithm.Under the condition that the attacker can manipulate an identical device as the device under attack,the optimal pre-processing techniques are adopted to realize high-order correlation power analysis and collision attack.Masked AESproposed by Herbstetal.and implemented on a universal smart card verifies the efficiency of these techniques.Experiment results indicate that the attack can be successfully launched on 5000 traces after the application of optimal pre-processing techniques.

pre-processing technique;high-order correlation power analysis;collision attack;mask

TN919.72

A

1002-0802(2014)12-1439-06

10.3969/j.issn.1002-0802.2014.12.019

2014-09-15;

2014-11-20 Received date：2014-09-15;Revised date：2014-11-20

國家科技部項目(No.2011BAK13B05)

Foundation Item:Project supported by Ministry of Science and Technology of China(No.2011BAK13B05)