基于能耗旁路泄露的密码芯片模板攻击算法研究

张洪欣 李静 张帆 甘罕 贺鹏飞

(1.北京邮电大学 电子工程学院,北京 100876; 2.安全生产智能监控北京市重点实验室(北京邮电大学),北京 100876; 3.中国信息安全测评中心,北京 100085;4.浙江大学 信息与电子工程学院,杭州 310027; 5.山东省烟台大学光电信息技术学院,烟台 264005)



基于能耗旁路泄露的密码芯片模板攻击算法研究

张洪欣1,2李静1,3张帆4甘罕1贺鹏飞5

(1.北京邮电大学 电子工程学院,北京 100876; 2.安全生产智能监控北京市重点实验室(北京邮电大学),北京 100876; 3.中国信息安全测评中心,北京 100085;4.浙江大学 信息与电子工程学院,杭州 310027; 5.山东省烟台大学光电信息技术学院,烟台 264005)

为解决模板攻击对先验知识要求较为苛刻的问题,基于聚类的半监督式模板攻击方法,研究了能耗泄露曲线特征点的选择,提出了基于皮尔逊相关系数和主成分分析(Principal Component Analysis, PCA)方法对旁路泄露进行特征提取的方法．在聚类过程中,通过少量的有标号的信息来辅助并引导聚类过程对无标号数据的聚类处理,放宽了模板攻击的假设条件．以轻量级分组密码(Light Encryption Device, LED)算法旁路泄露为例,通过实验研究了特征选取等因素对密钥恢复的影响,并分析了能量迹中的数据依赖性．研究结果表明：与常规半监督式模板攻击方法相比,所采用的特征提取方法可以有效降低异常数据和噪声的干扰,提高先验信息的利用率及密钥恢复成功率．

密码芯片;旁路泄露;特征提取;系统安全

引 言

密码芯片的安全不能仅考虑数学上密码算法的安全性设计,还要考虑实际环境因素的影响．攻击者利用物理上旁路泄露的信息进行的攻击, 被称为旁路攻击(Side Channel Attacks, SCA),是目前系统信息安全研究的一个重点．旁路分析获取到的与密钥相关的信息主要包括: 处理时间[1], 能耗[2]和电磁辐射[3-6]．

2002年,Chari等[7]提出了模板攻击(Template Attack, TA)的旁路攻击方法．随之,Dakshi Agrawal等人提出了将模板攻击与差分能量分析DPA相结合的模板加强DPA攻击．TA与DPA、SPA等方法相比,可以利用较少的功耗曲线恢复密钥,但需获取与目标密码芯片相同的先验信息．突破模板设备的限制成为旁路分析方法发展的方向之一．

Lerman 等[8,14], Heuser 等[9], 和Hospodar等[10-11]讨论了机器学习方法在模板攻击中的作用．这种监督式机器学习方法显示出比传统模板攻击更高的效率．但其前提仍是假设攻击者在建模阶段可以完全控制或拥有一台与被攻击设备相同的设备,条件比较苛刻．在机器学习中,有两种主要的学习方法:有监督的学习和无监督的学习．有监督式学习依赖于一组带有类标号的样本观察数据的随机相关性,通过建立问题域的预测模型从一组被测量迹线中推测与密钥相关的信息．无监督的学习方法通过数据分析,发现迹线中难以发现的结构或模式,而不用知道其相应的密钥信息．本文结合有监督和无监督学习方法的优点,在聚类的基础上,引入半监督式模板攻击(Semi-Supervised Template Attack,SSTA),通过引入用户已知背景信息引导聚类过程,利用机器学习方法推测子密钥的汉明重量值,使得用户不必完全控制或拥有一台与被攻击设备相同的设备,只需通过少量的有标号的信息来辅助并引导聚类过程对无标号数据的聚类处理．本文基于SSTA研究了能耗泄露曲线特征点的选择,提出了皮尔逊相关系数和主成分分析(Principal Component Analysis, PCA)方法对旁路泄露进行特征提取的方法,提高了半监督式模板攻击的密钥恢复成功率．最后以LED密码为例进行了验证实验,评估了不同特征提取方法对SSTA密钥恢复成功率的影响．

1 特征提取

在解决分类问题以前,机器学习方法需要对数据进行预处理和特征提取[13]．功耗曲线的特征提取,就是找到一些能够描述这段功耗曲线的特征量,并以此作为分类标准．

密码设备运行一次过程中采集到的时域功耗信号为一条样本曲线,每一采样成分都与时间t相关．这些特征中很多都不携带与目标子钥相关的信息,更多地表示的是噪音,理论上不能用于分类．本文针对功耗曲线特征选择采用两种方法: 皮尔逊相关系数和PCA．

1.1 皮尔逊相关系数的方法

选择能耗迹线的N个特征点最直接的方法是找到与目标子钥具有最大相关性的N个位置．

皮尔逊相关系数由以下公式给出

(1)

式中: cov(·,·)表示两变量的协方差; var(·)代表方差;x(t)表示实际密钥对应的能耗的集合;y表示猜测密钥对应的假设能耗的集合．如果ρ(t)=0,则x(t)和y不相关,否则,x(t)和y相关．

1.2 PCA

PCA在统计学中可以将数据从高维数据空间变换到低维特征空间,因而可以用于数据的特征提取及数据压缩．PCA 特征提取方法需要计算输入数据的协方差矩阵, 并运用一个对角化步骤来提取特征值及对应的特征向量,减小特征向量之间的相关性,使冗余信息最小化．

假设有k个可能的子密钥,用所有可能的子密钥对同一个明文p加密n/k次,获取得到n条能耗迹线．这n条能耗迹线组成的训练集X可表示为[x1,x2,…，xn],每条迹线有m个点,即xi1,xi2,…，xim(1≤i≤n)．设X经线性变换P得到Y,即Y=PX,P的行向量{P1,P2,…，Pm}就是X的主成分,提取训练集X的部分特征需要建立特征向量的协方差矩阵．令训练集X的均值为

(2)

X的协方差矩阵为

(3)

计算主成分的贡献率(数值上等于特征值的贡献率),选择前面D(D

2 半监督式模板攻击

一般模板攻击主要分为两步:建模过程和攻击过程．在建模过程中假设攻击者可以获取攻击对象的先验信息．通过改变密钥(或者密钥的一部分),攻击者可以为每一个(子)密钥构建一个模板．基于SSTA的方法, 可以放宽这种限制,攻击者仅需要获取部分先验信息[14],并能收集未知密钥的曲线,即可重构密钥．当然,半监督式模板攻击与有监督学习的攻击方法相比,恢复密钥的正确率要下降．本文通过引入特征提取的方法提高半监督式模板攻击的正确率．

当密码设备执行密码操作时,假设每一个用户和一个特定的密钥相连,则攻击者就可以在不同用户使用不同密钥进行操作时采集迹线．换句话说,攻击者控制设备时虽不能改变密钥,但他可以知道哪些相同的密钥正在被使用．

设攻击者采集到能耗迹线为T={(x1,y1),…,(xl,yl),xl+1,…,xn},其中,xi∈Rd,i=1,…,n,yi∈Y,k=1,…,l,l为有标记样本个数,u=n-l为未标记样本个数．据此寻找与xl+1,…,xn对应的在Y中取值的输出yl+1,…,yn的值,这里yi∈Y={1,2,…,c}．有标记的是第一组迹线Tk∈T,是一些已知密钥的迹线, 攻击者可利用已标记的迹线分类的准确度．无标记的第二组迹线Tu∈T,是获得的未知密钥所对应的迹线．

在第二阶段,攻击者确定每一类所对应的汉明重量的值,主要考虑单个字节中汉明重量的密度分布．攻击者可以通过观察迹线的相对数量和每个类的能量消耗确定其汉明重量．

在攻击阶段,攻击者测量被攻击设备上的一条迹线T．然后,模型返回所测量到的字节kb的汉明重量h,保证其满足以式(4)子最小.

(4)

式中,dt是两条迹线在时刻t(操作kb的时间)的距离度量．采用Euclidean距离来进行距离度量．一旦确定了汉明重量,攻击者可以通过暴力攻击找到被攻击字节的值．在汉明重量已知的情况下进行暴力枚举,所尝试的次数比未知情况下,对所有可能的值进行枚举要少得多．

从攻击设备中采集到一条迹线后,对它进行分类．这条迹线可以加入到模型中,以进一步提高执行的准确性．模型通过在建模阶段不断插入新的迹线,不断提高攻击设备密钥恢复的成功率．

3 试验与分析

本节针对64-bit长度密钥的LED密码算法进行模板攻击实验．LED算法使用64比特密钥加密64比特的明文分组．数据和密钥均用一个4×4的矩阵表示,每个元素4比特．如图1所示,该矩阵也称为状态．LED是一个密钥迭代型密码算法,轮变换将会反复应用于状态．LED计算采用了32轮迭代,每一轮迭代使用一个轮密钥．解密过程的工作原理与加密过程的工作原理类似,但是,解密过程必须以与加密过程相反的顺序应用各类密钥,并且使用轮变换的逆变换．

图1 LED 状态和密钥设计

在8位AVR微控制器ATMEGA324P上运行加密算法,功耗分析时在电源或者地线上嵌入取样电阻,采用电流探头(P6139A等)取样, 其信息采集硬件平台如图2所示．计算机中安装旁路攻击分析软件,计算机通过交换机与示波器的LAN口相连,旁路攻击分析软件可以控制示波器自动进行连续的数据采集并以一定格式存储．泰克示波器DPO7254的CH2通道作为触发信号使用．通过微控制器执行LED算法进行实际攻击测试,由RS232接口接收计算机输出的测试明文,并返回密文和解密得到的明文．测试明文输入后,由触发代码来控制示波器在LED代码相应位置进行采集．

图2 信息采集硬件平台示意图

其中,电压设置为5V,微控制器工作频率为8MHz,示波器采样频率为100MS/s．

采集到的数据集包含4 096条功耗曲线,每条迹线含有2 000个成分．当m⨁k取不同值时(其中m为明文,k为密钥),功耗曲线具有差异性,而这种差异性是分类的前提．以第一组第二段功耗曲线为例,用皮尔逊相关系数法选择一部分特征明显的功耗点即有效点来进行特征提取, 特征维数为32．

本实验选取了5类(覆盖汉明重量0到4)标记样本,从每类4条功耗曲线到每类36条功耗曲线作为标记样本,每次增长4条,验证其分类的准确度．从图3可以看出基于PAM的半监督聚类算法在标记样本规模为每类标记曲线为24条左右时,标记样本成功概率趋于稳定,也就是说每类样本曲线达到24条以上时,对聚类的影响趋于稳定．因此,对于PAM算法来说,较小的样本数目就足够可以确定中心曲线．

图3 不同标记曲线下的成功率

将480×32的样本数据矩阵进行PAM算法聚类．样本数据被分成5类,选取欧氏距离作为样本间距离计算方法,初始聚类中心采用随机生成中心点,为了使结果尽可能收敛,但也不耗费过长时间,本文设定迭代次数为100次．分类效果如图4所示．

图4 基于聚类的分类

如表1所示, 由于半监督式攻击算法利用了部分先验信息,故与有监督学习的TA方法相比其密钥恢复成功率要低．而聚类算法对噪音数据敏感,故直接用PAM算法聚类,准确率不高．特征点的选择会影响分类的精度和密钥恢复成功率．基于皮尔逊相关系数和PCA方法对旁路泄露进行特征提取的方法对聚类结果有明显改进．特征点的选取需要充分反映不同模板之间的差异性,否则将会削弱功耗曲线的统计特征,降低匹配的精度．使用PCA提取迹线特征,分类精度及密钥恢复成功率最高,基于皮尔逊相关系数效率稍差,但与没有采用特征提取的半监督式攻击算法相比攻击成功率都有明显提高．所以,研究搜寻更适合的特征参数有利于提高密钥恢复成功率．

表1 不同方法下的成功率

在利用PCA提取特征曲线时,本文注意到特征点的数目并不是越多越好．如图5所示,成功率随着特征数目的增加而下降．也就是说,当特征数目增加到一定数量后,由于协方差矩阵缺陷的问题,增加特征点的数量不能为分类器提供更多的额外信息．如表2所示,当变量为35时,PAM:PCA模型预测的精准率下降了．

图5 特征选择的影响

本文研究了能量迹中的数据依赖性,确定密码设备处理不同数据时能量消耗的概率分布．考虑当对具有同样汉明重量的数据进行操作时,微控制器能量消耗的分布基本相同．对于不同的汉明重量,各个分布具有不同的均值,但是标准差基本相同．对于LED算法而言,4比特数有5个不同的汉明重量:0,1,2,3,4．表2给出了本实验均匀分布的4比特数据的汉明重量的概率分布．可以看出,汉明重量2出现的概率最高,而汉明重量为3和4出现的概率最小．

表2 汉明重量概率分布

4 结 论

旁路分析是一种强大而行之有效地攻击安全系统的方式．能耗迹线常常泄露大量的、有意义的关于处理密钥方面的信息．本文利用聚类和半监督学习的方法对模板攻击的普适性作了进一步探索,研究了特征提取算法对半监督式模板攻击算法的改进．并以LED密码为例进行了验证实验,结果表明,有效的特征提取算法可以提高SSTA算法的密钥恢复成功率,并验证了算法的有效性．

[1] KOCHER P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems [C]//CRYPTO 1996, LNCS 1109. Berlin: Springer, 1996: 104-113.

[2] KOCHER P C, JAFFE J, JUN B. Differential power analysis [C]//CRYPTO 1999, LNCS 1666. Berlin: Springer, 1999: 388-397.

[3] QUISQUATER J, SAMYDE D. Electromagnetic analysis (EMA): measures and countermeasures for smart cards [C]//E-Smart 2001, LNCS 2140. Berlin: Springer, 2001: 200-210.

[4] GANDOLFI K, MOURTEL C, OLIVIER F. Electromagnetic analysis: Concrete results[C]//Workshop of Cryptographic Hardware and Embedded Systems (CHES'01), 2001: 251-261.

[5] 潘晓东, 魏光辉, 卢新福,等.注入法等效替代电磁辐照法试验技术研究[J].电波科学学报,2013,28(1):97-104.

PAN Xiaodong, WEI Guanghui, LU Xinfu et al. Testing technology of using injection as a substitute for electromagnetic radiation [J]. Chinese Journal of Radio Science,2013,28(1):97-104.(in Chinese)

[6] 刘飚, 封化民, 袁征, 等. 一种针对密钥的单比特电磁模板攻击方法[J]. 电波科学学报, 2012, 27(6): 1213-1218.

LIU Biao, FENG Huamin, YUAN Zheng, et al. Single bit electromagnetic template attack aiming at key[J]. Chinese Journal of Radio Science, 2012, 27(6): 1213-1218.(in Chinese)

[7] CHARI S, RAO J R, ROHATGI P. Template attacks[C]//Workshop of Cryptographic Hardware and Embedded Systems, 2002:13-28.

[8] LERMAN L, BONTEMPI G, MARKOWITCH O. Side channel attack: an approach based on machine learning[J]. Center for Advanced Security Research Darmstadt, 2011, 29-41.

[9] HEUSER A, ZOHNER M. Intelligent machine homicide[C]//Proceedings of COSADE 2012. Berlin: Springer, 2012, 249-264.

[10]HOSPODAR G, GIERLICHS B, DE MULDER E, et al. Machine learning in side-channel analysis: a first study[J]. Journal of Cryptographic Engineering, 2011, 1(4): 293-302.

[11]HOSPODAR G, DE MULDER E, GIERLICHS B, et al. Least squares support vector machines for side-channel analysis[C]//COSADE 2011, 2011: 99-104.

[12]GUO J, PEYRIN T, POSCHMANN A, et al. The LED block cipher[C]//CHES 2011. Berlin: Springer, 2011: 326-341.

[13] 李静, 张洪欣, 甘罕. 基于回声状态网络的功耗曲线特征提取[J].电波科学学报,2014,29(4):1127-1132.

LI Jing,ZHANG Hongxin, GAN Han. A study on ESN-based power trace feature extraction[J]. Chinese Journal of Radio Science,2014,29(4):1127-1132. (in Chinese)

[14]LERMAN L, MEDEIROS S F, VESHCHIKOV N, et al. Semi-supervised template attack[C]//COSADE 2013, 2013:184-199.

A study on template attack of chip base on side channel power leakage

ZHANG Hongxin1,2LI Jing1,3ZHANG Fan4GAN Han1HE Pengfei5

(1.SchoolofElectronicEngineering,BeijingUniversityofPostsandTelecommunications,Beijing100876,China；2.BeijingKeyLaboratoryofWorkSafetyIntelligentMonitoringBeijingUniversityofPostsandTelecommunications,Beijing100876,China; 3.ChinaInformationTechnologySecurityEvaluationCenter,Beijing100085,China；4.ZhejiangUniversity,CollegeofInformationScienceandElectricalEngineering,Hangzhou310027,China;5.SchoolofOpto-electronicInformationScienceandTechnology,YanTaiUniversity,Yantai264005,China)

To meet the rigid requirements of prior knowledge in template attack, a semi-supervised template attack method based on clustering is investigated, where the selection of power trace feature points is studied, and a feature selection method based on Pearson correlation coefficient and principal component analysis is put forword. In the process of clustering, the assumption of template attack is relaxed through clustering for unmarked data under the guidance of a certain marked information. The effect of factors such as feature selection is studied in a test based on LED encryption, and at the same time, the data dependence on power traces is analyzed. Compared to the traditional semi-supervised template attack method, the result shows that this feature selection method can effectively reduce the effect of the abnormal data and noise, and improve the utilization of the prior information and success rate of key recovery.

cryptographic modules; side channel leakage; feature selection; system security

10.13443/j.cjors. 2014102105

2014-10-21

国家自然科学基金(No.61571063,61472357,61202399); 北京市自然基金(No.4112039)

TN918

A

1005-0388(2015)05-0987-06

张洪欣 (1969-),男,山东人,北京邮电大学电子工程学院教授,博士生导师．宽带通信与微波技术实验室主任,国家自然科学基金项目同行评议专家,教育部学位与研究生教育发展中心评议专家,中国电子学会DSP应用专家委员会委员,中国工业和信息化部科技人才库专家,北京市科学技术奖励评审专家,北京电子电器协会电磁兼容分会委员,北京邮电大学育人标兵．

李静 (1981-),女,湖北人,博士研究生北京邮电大学电子工程学院微波、天线与电磁环境专业博士研究生．

张帆 (1978-),男，浙江人,美国康涅狄格大学计算机科学与工程系博士,现就职于浙江大学信息与电子工程学院．主要的研究方向包括信息安全,计算机体系结构,人机交互以及传感器网络．

甘罕 (1986-),女,河北人,北京邮电大学电子工程学院微波、天线与电磁环境专业博士研究生．

张洪欣, 李静, 张帆,等. 基于能耗旁路泄露的密码芯片模板攻击算法研究[J]. 电波科学学报,2015,30(5):987-992.

ZHANG Hongxin, LI Jing, ZHANG Fan, et al. A study on template attack of chip base on side channel power leakage [J]. Chinese Journal of Radio Science,2015,30(5):987-992. (in Chinese). doi: 10.13443/j.cjors. 2014102105

联系人： 张帆 E-mail：fanzhang@zju.edu.cn