掩碼方案中的最優預處理技術*

陳 曼,羅 順

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

掩碼方案中的最優預處理技術*

陳 曼1,羅 順2

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

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

預處理技術 高階相關能量分析攻擊 碰撞攻擊 掩碼

0 引 言

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

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

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

本文將Oswald等人提出的最優化預處理技術應用到掩碼重用的密碼實現方案中,研究最優化預

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

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

1 背景知識

1.1 AES掩碼實現方案

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

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

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

圖1 AES掩碼實現方案Fig.1 Masked AES implementation

1.2 最優預處理技術

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

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

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

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

2 掩碼實現的最優預處理技術

對于Oswald的掩碼實現方案,多個密碼運算中間值使用相同的掩碼進行保護。采用高階相關能量分析攻擊或碰撞攻擊的方法,可能對重用型掩碼實現方案進行攻擊。

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

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

2.1 基于高階相關能量分析攻擊的最優預處理

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

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

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

實際進行攻擊時,通常選取中間值為某個數值而非多維向量,此時,變換系數變為數值β,相應的變換系數可轉化為(),也就是說,變換系數β可省略。式(6)可進一步減化為式(7)。

2.2 基于碰撞攻擊的最優預處理

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

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

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

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

3 實驗結果

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

使用力科示波器WAVE RUNNER 610Zi,設置采樣率為250MSa/s,在字節1和字節5進行S盒操作采集其能耗波形。總共對5000個隨機選取的明文進行

了加密操作,采集得到5000條能耗波形。字節1對應的密鑰字節為0X00,字節5對應的密鑰波形為0XC7。本文使用這些能耗波形,分別在使用/不使用最優化預處理技術時,對AES實現進行了攻擊。

3.1 高階相關能量分析攻擊

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

圖2 隨機選取樣本點的高階相關能量分析攻擊Fig.2 High-order correlation attack related to a random sample point

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

圖3 最優預處理后的高階相關能量分析攻擊Fig.3 High-order correlation attack after optimal pre-processing

3.2 碰撞攻擊

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

圖4 隨機選取樣本點的碰撞攻擊Fig.4 Collision attack related to a random sample point

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

圖5 最優預處理后的碰撞攻擊Fig.5 Collision attack after optimal pre-processing

4 結 語

本文實驗結果表明,最優預處理技術可有效提升對加入了掩碼對策的密碼實現攻擊效率。因此,

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

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

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

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

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

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

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—),男,碩士,主要研究方向為計算機與通信工程。

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)