RSA算法时序模板SDPA攻击研究

许 森, 陈 运, 陈 俊, 饶金涛, 孙敦灿

(成都信息工程学院信息安全研究所,四川成都610225)

1 引言

自从1996年Paul Kocher[1-2]首次公开发表功耗分析攻击理论开始,密码学界就对这种新型的攻击方法进行了广泛的研究。实施功耗分析攻击时,需要监测电子密码设备(如智能卡)一条或多条非常规信道,该信道会泄漏密码设备运行时功耗信息,并使用与密码设备连接的示波器中获取该功耗曲线,根据该功耗曲线恢复出加密时使用的密钥。

在功耗分析理论发展的过程中,先后出现了针对功耗曲线的时间攻击[1-2](TA)、简单功耗分析攻击[3](SPA)、差分功耗分析攻击[4](DPA)、模板攻击[5-7](Template Attack)、简单差分功耗分析攻击[8](SDPA)以及简单分支预测攻击[9-10](SBPA)等。其中模板攻击又被称为功耗分析攻击中最具威胁的攻击手段,它能在较少的样本曲线下,恢复出功耗曲线中的指数信息。

现以支持ISO7816协议的8位8051核心芯片和自主研发的攻击平台,分析功耗泄露原理,结合泄露功耗信息特征、模板攻击、SDPA攻击、分支预测攻击等思想,提出以时间序列模板的SDPA攻击方法,恢复芯片加密时的密钥信息。

2 相关理论

2.1 瞬时功耗

电子密码设备功耗泄漏原理,可参考文献[11-12],这里不再累述。监测芯片运算可以获取芯片加密时的瞬时功耗曲线,以P(t)表示在 t时刻的功耗情况,它包含了动态功耗和静态功耗的瞬时值,可用下面公式表示：

其中R是获取功耗信息时在芯片上外接的电阻,而 I(t)和U(t)表示当前t时刻经过R的电流值或电压值。加密时间段内得到的功耗曲线就可以用瞬时功耗序列表示：

所有泄漏信息都保存在功耗曲线序列中,通过对其分析进而实施攻击。

2.2 模板攻击

典型的模板攻击是在密码设备运行过程中获取其功耗曲线,利用该曲线中某种特征构建与指数相关的模板。然后利用同样的方法提取未知指数功耗曲线特征,并结合相应的配置算法攻击得到最终结果。

文献[5]最先提出一种高斯噪声模板,并利用概率统计方法进行匹配。该方法一个重要的缺点就是数量极其庞大,攻击周期较长。

2.3 分支预测攻击

文献[9-10]描述的分支预测攻击方法,是针对建立在多级流水线基础上超级CPU的攻击。超级CPU为了提高执行效率,在条件分支语句执行前会将可能的执行地址(自动预测)存入一个名为分支目标缓存中(Branch Target Buffer,BTB),执行分支时,如果CPU预测正确,将会直接跳转到缓存中地址,执行后续执行,其执行时间就会相对较短,否则分支执行时间将相对较长。

虽然8051芯片不是多级流水线的CPU,但利用分支语句与指数的相关性,有助于破解RSA密钥。

3 数据分析与模板建构

3.1 RSA幂剩余算法信息泄露分析

公钥密码算法中进行大数模乘的基本运算为幂剩余算法,其基本表达式为：

其中d为敏感信息,在RSA中可为私钥的一部分,泄露其值或相关内容的信息实质即为泄露密钥信息。基于幂剩余的RSA算法实现有很多种,其基本的快速算法有3种[13]：从左向右(LR)、从右向左(RL)和随机指数(randomized exponentiation)。这里只介绍从左向右二进制表示求幂剩余算法。

算法1 从左向右二进制表示求幂剩余算法

输入：明文 M,指数 ＜d=(didi-1…d1d0)＞

输出：C=MdmodN

经过对密码芯片功耗泄露的原理、RSA幂剩余算法以及示波器采集到波形的综合考察,可以得到以下结论：

(1)RSA幂剩余算法中进行模乘部分整体瞬时功耗大于执行循环语句和判断语句瞬时功耗。如图1所示。

可以看到图中存在高低瞬时功耗的差异,其中较高瞬时功耗为模乘运算,较低的瞬时功耗为判断和循环语句,这与前面分析一致。

(2)每次循环的内部,对应指数di不同的取值会执行不同的操作,模乘运算部分瞬时功耗,会被瞬时功耗较低的判断语句分割开,从而造成汉明重量信息泄露。图2显示了指数为A0时汉明重量泄漏情况。

图1 瞬时功耗说明图

图2 汉明重量信息泄漏

(3)算法1中循环语句和循环体内部判断语句具有相同水平的瞬时功耗,但其执行时间会有略微差异,是模板建立的基础,图3统计了指数为0xA0的时间序列。

3.2 时间序列与指数对应关系

for、if等条件分支语句在芯片中执行首先转化成汇编语言的形式,图4是汇编语言中典型的for、if分支语句形式：

图3 指数A0时间序列

图4 汇编代码比较

通过对两种语句汇编语言代码比较,可以得到for语句和if语句在执行时间上有差异,在某种条件下可以量化该时间。表1显示了不同语句可能相关的指数信息及其执行时间。

表1 不同数据执行时间差异

图5 分支语句与数据之间关系

for、if等条件分支语句的瞬时功耗在同一水平,其执行的顺序与指数密切相关,图5显示了分支语句与指数之间的关系,其中C2对应RSA算法中平方模乘,MC为乘积模乘。

针对图5指数1001,则其时序即为：

就一般情况而言,一个字节内汉明重量取值为0到8,不同汉明重量在功耗曲线上对于不同的模乘个数,设一个字节内汉明重量为HW,模乘个数为N,该字节可能的取值为NofBytes,则3者之间有如下关系：

某个字节内功耗曲线,可以表达成一个时间序列：

3.3 时序深入分析

由于芯片自身、采集设置及其他原因,每次采集的功耗曲线会存在一定差异,进而统计出来时间序列不尽相同,下面介绍一些主要的影响因素及对策。

3.3.1 条件分支语句时耗统计特性

由于密码设备本身可能存在抖动等问题,如图6～图9分别显示了 T0、T1、T2和 T3在1000条样本下的统计情况。

图6 T0时间差异

图7 T1时间差异

图8 T2时间差异

图9 T3时间差异

由前面统计信息可以看到,单样本不能完全体现时序特性,鉴于功耗曲线之间差异,利用时序的均值向量组成模板元素

3.3.2 采样率对时间序列的影响

采样率的不同可能会对时间序列产生一定的影响,而时间序列内各元素之间关系表达其代表的指数信息,如果采样率较低则可能无法表达出指数信息,进而造成无法正确匹配。如图10显示了相同数据的3种采样率下的时间序列。

在相同的采样点数下,采样率的不同造成了时序模板之间的差异。图中曲线A为基础采样率,曲线B为2倍基础采样率,曲线C为3倍基础采样率。可以得出这样的结论：采样率较低时可能会将淹没一些重要信息。图10中4、5、6基础采样率下持平,而在较高采样率下其特征明显不同。

3.4 模板构建

根据前面分析,在特定采样率下获得的功耗曲线可对其构建模板,则模板定义了一个二元组：

模板中N是模乘个数,¯t是分支语句执行序列的时间特征,通过大量功耗曲线样本,统计得出。

3.5 模板匹配

文献[5]中描述模板匹配原则为缩减,即利用模板将可能的指数取值集合缩减到尽可能小,最终利用匹配方式确定指数。文中攻击方法进行两次,首先利用模板中 N值进行缩减密钥取值空间(最多只有70个值,最少只有一个值)得到结果集合,然后利用集合中元素进行匹配得到最终结果。

匹配时利用了欧式距离,公式为[14]：

图10 不同采样率时序对比

利用上式计算攻击模板与猜测模板之间的距离,得到一个集合：

集合中存在一个最小值Dmin,因此其对应的就是最可能的正确密钥。

4 实测结果

测试平台的搭建可参考文献[15],其中使用到的关键技术及实现见文献[16]。按照之前论述的攻击思想对某1024位指数实施攻击,图11给出了某一字节A0各猜测值的匹配结果,由于A0汉明重量为2,则该字节内模乘个数为10,时序长度为10。猜测密钥时,可能取值集合个数为28。

通过实验可以看到,利用前面构建的模板和匹配算法,密钥为A0的数据具有最小的匹配值,从而可以确定它就是被攻击字节的数据。

实验表明,依据传统方法首先对所有可能的密钥取值构建模板,然后对指数进行攻击得到平均正确率为85%,由此可知传统的模板匹配方法仍然有提高的空间。图12给出了传统方法中模板匹配错误的数据。

图12中时序曲线A代表数据为0x42,时序曲线B代表的数据为0x44,而被攻数据时序曲线代表真实数据为0x42,但它体现出的特征与0x44非常相近,可见先建模板的不足,其中原因将另撰文详述。

鉴于图12表现出的模板特性,抛弃了传统的先验模板构建方法,引入了SDPA思想实时构建模板。即在攻击时首先获取被攻击指数的模板信息,依据模乘个数获取所有可能的取值,并获取这些可能取值的模板,最后进行匹配。引入SDPA思想就是为了消除数据带来的先验模板差异,实验表明该方法提高了攻击的正确性,正确率可达100%。图13显示了传统模板构建方法与SDPA构建方式之间正确率的对比。

图11 匹配结果

图12 传统方法模板与真实数据之间差异

图13 两种模板构建方法攻击结果对比

实验室已经对类似使用分支泄漏信息进行攻击的方法,提出了防御策略具体参考文献[17]。

5 结束语

文中结合模板攻击原理和SDPA思想,利用密码芯片加密时循环语和判断语句功耗泄漏时间特征和单字节内模乘个数特征构成模板,利用欧式距离匹配实施攻击。通过在真实智能卡RSA二进制模幂算法环境下进行实验分析,证实了该攻击方法的正确性和有效性。同时,该方法也具有缺点,就时攻击时的指数越长,需要的功耗曲线越多。

致谢：感谢成都市“十一五”重点科技专项(09GGZD988GX-033);成都市科技攻关项目(10GGYB368GX-023)对本文的资助。

[1]KOCHER P.Timing attacks On implementations of diffe-hellman,RSA,DES,and other system[A].Proceedings of Advances in Cryptology-CRYPTO'96[C],1996：104-113.

[2]DHEM J F.KOEUME F,LEROUX P A,et al.A practical implementation of the timing attack[A].Proceedings of CARDIS 1998[C].1998：14-16.

[3]MESSERGES T S,DABBISH E A,SLOAN R H.Investigations of power analysis attacks on smarteards[A].Proc USENIX Workshop Smarteard Technology[C].Chicago,Illinois,USA,1999：151-161.

[4]KOCHER P,JAFFE J,JUN B.Differential power analysis[A].Proceedings of Advances in Cryptology-CRYPTO'99[C].1999：388-397.

[5]Suresh Chari,Josyula R.Rao,and Pankaj Rohatgi.Template Attacks[A].CHES 2002,LNCS 2523,2003：13-28.

[6]C.Archambeau,E.Peters et al.Template Attacks in Principal Subspaces[A].CHES 2006,LNCS 4249,2006：1-14.

[7]Francois-Xavier Standaert et al.and Cedric Archambeau.Using Subspace-Based Template Attacks to Compare and Combine Power and Electromagnetic Information Leakages[A].CHES 2008,LNCS 5154,2008：411-425.

[8]周俐莎,陈运.真实环境下对幂剩余指数的SDPA攻击[J].计算机工程,2010,36(7)：156-158.

[9]O Acicmez,J P Seifert,C K Koc.Predicting secret keys via branch prediction[J].Topics in Cryptology-CTRSA 2007.

[10]O Aclicmez,C K Koc,J P Seifert.On the power of simple branch prediction analysis[J].Cryptology ePrint Archive,2006：351.

[11]邓高明,吴恒旭,张鹏.旁路模板在密码芯片指令分析中的应用[J].微电子学与计算机,2011,28(2)：1837-1839.

[12]Stefan.Mangard,Elisabeth Oswald,Thomas Popp.Power Analysis Attacks-Revealing the Secrets of Smart Cards[M].Springer Science Business Media,LLC,2007：30-32.

[13]陈运,吴震,陈俊,等.防范边信道攻击的等功耗编码实现算法[J].电子科技大学学报,2008,37(2)：168-171.

[14]孙即祥.现代模式识别[M].北京：高等教育出版社,2088：19-20.

[15]吴震,陈运,陈俊,等.真实硬件环境下幂剩余功耗轨迹指数信息提取[J].通信学报,2010,(2).

[16]孙敦灿,陈运,万武南,等.功耗分析平台中混合编程的应用研究[J].成都信息工程学院学报,2011,126(2)：127-131.

[17]饶金涛,陈运,吴震,等.一种抗简单功耗分析攻击的模幂算法[J].成都信息工程学院学报,2011,126(2)：123-126.