掩码方案中的最优预处理技术*

陈 曼,罗 顺

(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)