一种针对密钥的单比特电磁模板攻击方法

刘 飚 封化民 袁 征 高攸纲

(1.北京邮电大学电子工程学院，北京 100876；2.北京电子科技学院 信息安全重点实验室，北京 100070)

引 言

模板攻击根据泄漏信息的数据相关性和操作相关性进行攻击，首先为每一个可能的密钥构建一个对应的泄漏信息特征的模板，之后根据获取的一份或多份泄漏的信息寻找最匹配的模板，进而推断最可能的密钥。因为这种方法提取了每个样本信号携带的所有可能信息，从信息论的意义上来说，是迄今为止最强有力的攻击方式[1]。从2002年由 Rohatgi 等人提出以来，模板攻击一直是旁路攻击研究领域的热点。2005年，Agrawal 等人将模板分析和差分功耗分析(DPA)相结合，提出一种模板加强的DPA攻击[2]。2006年，Archambeau 等人提出从测量样本中选取有效点构成样本的主子空间以减小模板攻击运算量的方法[3]。同年，Gierlichs等人将模板攻击和随机方法进行比较，利用基于T检验的算法评价了模板攻击的效率[4]。2008年Standaert等人结合了功耗和电磁两种旁路信号，采用主成分分析(PCA)和Fisher判别进行模板分析[5]。

以上方法均将密钥经算法置换后生成的一个多比特中间变量作为攻击目标，以此建立模板来间接推导密钥。这样做的缺点是计算量巨大，需要建立的模板数量众多。在Agrawal 等人的工作中曾提出一种单比特模板攻击，该方法独辟蹊径为单比特建立“0”和“1”两个模板，大大减少了模板数量[2]。但该方法仍是以中间变量为攻击目标，需要已知明文或密文才能反推原始密钥。Lerman等人直接将密钥作为攻击目标，但攻击方法采用了机器学习[6]。

本文直接以密钥比特为攻击目标，通过改进传统的模板攻击方法来获取密钥。不同于以上文献[1-4，6]关注于密码设备的功耗泄漏特性，本文将电磁泄露作为分析对象。因为获取加密芯片运行时的电磁场信息并不需要采用入侵式的攻击方式也不用在电路中接入如电阻等器件，而是可以通过在芯片附近放置探头感应电磁场变化来获取电磁场数据，所以电磁攻击的隐蔽性更大，更加难以被察觉[7]。实验结果表明，该方法对破解数据加密标准(DES)密码芯片是快速有效的。

1 理论分析

1.1 密码芯片的电磁辐射

密码芯片的电磁辐射是旁路信号的一种，它和流过芯片的电流有关。在集成电路(IC)电磁兼容的标准IEC61967[8]中，传导电磁辐射和发射电磁辐射被认为是噪声并要求低于一定的阈值。IC的电磁辐射限制在一定的阈值以下，能防止与其他电子设备发生无意干扰。但是，对于执行密码算法设备而言，对电磁辐射还需要有额外的考虑。芯片辐射的电磁信号与芯片中处理的数据是相关的，因此，执行密码算法设备辐射的电磁信号中蕴含着和密钥信息相关的有用信息，电磁模板攻击正是利用这一特性进行密码分析的。

1.1.1 电磁辐射产生极其时域特性

图1给出的是互补金属氧化物半导体(CMOS)数字电路的基本组成单元—反相器。反相器可以看作是一个推拉开关：输入接地时切断下面的晶体管，产生高电平输出。高电平输入时刚好相反，将输出接地拉到低电平。当一个比特位从1翻转到0或者从0翻转到1时，反相器的P型金属氧化物半导体(PMOS)管或N型金属氧化物半导体(NMOS)管会导通一小段时间。这就导致一个从漏极(VDD)到源极(VSS)短暂的电流脉冲。而这个在CMOS门的输出变化时产生的电流会在芯片周围产生一个变化的电磁场，这个变化的电磁场可以用感应探头检测到。

图1 CMOS倒相器在输入信号E出现上升沿 和下降沿时的动态电流

根据楞次定律，穿过探头的电感力取决于磁通量的变化率，其表示为

(1)

式中：v表示探头的输出电压；φ表示探头感应的磁通量；t表示时间；B表示磁场；S表示磁力线穿透的区域。

基于安培定理的麦克斯韦方程将磁场的产生表示为

(2)

式中：J表示电流密度；E表示电场；ε表示电导率；μ表示磁导率。式(1)和式(2)说明探头的输出电压v和电流密度J以及电场E成正比，也就是和芯片内部翻转的晶体管数量成正比。

1.1.2 电磁辐射的数据相关性

IR=λ·H(D⊕R)+μ

(3)

式中：λ是一个和系统相关的常数；μ是随机噪声。

从式(3)可以看出，微控制器内部电流大小是和操作数的汉明重量(汉明距离)相关的，结合式(1)和式(2)，微控制器工作时辐射的电磁信号也与其内部处理的数据是相关的。

1.2 传统的电磁模板攻击方法

总体来说，电磁模板攻击方法把密码设备运行时的电磁泄漏作为随机变量，利用多维随机变量均值向量和协方差矩阵来构建模板，再用Bayes判别来匹配模板。

电磁模板分析攻击由两个步骤组成：

1) 模板构建阶段。

为了将电磁曲线按不同的密钥值分类，需要预先为每个可能的密钥都构建一个模板。该模板反映了与密钥对应的电磁样本曲线的统计特性，模板反映了电磁样本曲线上所有点的概率分布特性。模板的数量与算法的密钥空间中所有可能的密钥总数一致，即如果算法有K个可能的二进制密钥Ok，k=1，2，…，K，其中K=2B，B表示Ok的位数(不包括奇偶校验位)，需要建立的模板总数即为K个。具体的构建方法如下：

P(T(k)|OK；μk，∑k)

(4)

式中，μk∈Rn和∑k，k=1，…，K，分别表示用第k个密钥进行加密的N条电磁样本曲线的期望及协方差。

(5)

(6)

2) 模板匹配阶段

使用采集电磁样本曲线同样的方式，可以采集一条密钥未知的电磁曲线。将该曲线与先前构建好的模板进行比较。根据极大似然法则，匹配概率最大的模板就是匹配得最好的模板。而该模板对应的密钥就是最可能的正确密钥，如公式(7)为

(7)

传统的模板攻击方法主要有三大问题：一是计算量巨大，上述高斯分布中未知参数的数量为抽样点数n的函数，为(n2+3n)/2[6]，而曲线上的抽样点往往很多( >103)，直接用于模板攻击将导致巨大的计算量。二是需要建立的模板数量众多，以DES为例，DES加密算法的密钥空间为256，即需要建立256个模板。三是因为通常选择中间变量为攻击目标，要想反推密钥必须已知明文或者密文。

在实际应用中，对于第一个问题，可以利用PCA技术[3]和有效点提取技术[9]来减少样本点。

而对于第二个问题通常采用分段处理的方式。例如若密钥长度为X，所需要建立的模板数量就是2X个。但是如果进行分段处理，将总长为X的密钥分为长为Y的小段，对每一段密钥需要建立的模板总数就是2Y个，对整个密钥，需要建立的模板总数即为2Y*(X/Y)个。明显的，前一个模板数量2X大于2Y*(X/Y).

第三个问题是目前研究的热点，如Hanley等人就提出了一种未知明文的模板攻击方法[10].

1.3 单比特密钥电磁模板攻击

对于传统模板攻击存在的问题，提出了一种针对密钥的单比特模板攻击方法。该方法根据标注好的电磁样本曲线集合来估计条件概率P(Ok|T)，其中Ok∈{0，1}B.为了从样本数据中学习这种依赖关系，攻击过程分为以下三步：首先将猜测整个密钥的任务分解为B个不同的猜测子任务，然后，选择抽样点，建立模板和匹配。

1) 分解任务

如图2所示，可以将一个DES密钥字节的猜测任务分解为7个不同的猜测子任务，每个密钥比特只有{0，1}两种取值可能，即只需要为每个密钥比特建立1对模板。

图2 一个DES密钥字节的分解过程

因为整个DES密钥有56个有效位，要建立56对模板。

2) 选取抽样点

选取抽样点的好处主要有两点：一是大大降低计算难度和存储空间；二是防止无关的抽样值扰乱甚至降低判断准确度。

不同于文献[3]和[9]，本文采用的方式是选取电磁样本曲线上M个与密钥比特有最大相关性的抽样点。计算相关性的方法采用的是皮尔逊相关系数，如公式(8)所示

(8)

式中： cov(·，·)表示协方差；var(·，·)表示方差；T(t)表示在所有已标注电磁曲线上，由t抽样时间对应电磁辐射值组成的向量，yB表示每条电磁曲线对应密钥的第B比特组成的向量。ρ(t)越大，代表T(t)与yB越相关，即表示当前时刻第B密钥比特正在被存取。图3显示了DES密码芯片的电磁曲线辐射值与某密钥比特向量之间的相关系数计算结果，从图中可以看到高尖峰值不止一个，这是因为同一密钥比特在加密过程中数次被存取。对于每一个密钥比特，记下所有高尖峰值对应的时刻，在后期对该密钥比特建立模板和匹配时，只处理这些时刻对应的抽样点，其余抽样点可以全部忽略。因有分析表明，56比特原始密钥的每比特的使用次数在12～15次之间[11]。所以在实验中，对于每个密钥比特，抽样点数限制在12～15个之间。

图3 DES电磁曲线与密钥比特之间的相关系数

3) 模板构建和匹配。

这与1.2节方法相同，此处不再赘述。

2 实验结果及分析

2.1 DES

DES的原始密钥长度为64位，其中有8位用作奇偶校验位。原始密钥并不直接用于加密明文，而是用于生成轮密钥。通过对原始密钥一系列的置换和移位运算生成16个轮密钥，每个轮密钥长48位。DES的轮密钥产生与使用很有特色，它确保了原始密钥中各位的使用次数基本上相同。16个轮密钥分别顺序应用于密码函数的16次完全相同的迭代运算中。

传统的模板攻击通常选择第一轮或最后一轮的S盒的输入作为攻击点。由于一个S盒的输入是6位的，就需要构建26个模板。每轮中这样的S盒有8个，可建立8*26个模板来猜测48位轮密钥，根据DES密钥扩展算法可以反推到原始密钥的48位，对剩余未知的8位密钥可以进行穷举搜索，也可以对当前轮的上一轮或者下一轮再做一次模板攻击，当前轮未知的8位密钥在上一轮或者下一轮是可以猜测的，以上两种方法都可以恢复出56位原始密钥。

2.2 实验方案

实验中在AT89C52单片机中实现DES密码程序，用一个在单片机表面上的手制的20匝线圈将单片机运行时泄漏的电磁信号感应成电压信号，用数字存储示波器(Tektronix DPO4104)进行采集并通过USB传输到PC机存储，采样频率设置为500 MSa/sec.示波器的采集过程由PC机上用LabView编写的虚拟仪器控制平台实现自动控制，并且该虚拟仪器还通过RS232将明文发往单片机。实验方案如图4所示。

图4 实验方案

实验时，首先用随机产生的密钥加密随机明文20 000次，基于采集到的20 000条电磁曲线按照第1.3节描述的方法构建56对模板，然后再用随机密钥加密随机明文100次，以同样的实验设置采集并记录其电磁曲线作为测试集，最后按式(7)计算每一条电磁曲线与56对密钥比特模板的匹配概率，根据最大概率值可以推断每个密钥比特是0还是1.

2.3 实验结果及分析

利用表1的判断结果，可以实施增强型的暴力攻击策略来快速获得密钥：用模板攻击猜测密钥，如果密钥猜测错误，就把判断成功率最低比特取反。如果此时密钥猜测正确则攻击成功，否则，继续将判断成功率次低的比特取反，并以此类推。因为攻击时考虑了各个密钥比特的成功率，这种暴力破解密钥的效果会大大增强。

表1 判断成功率ηBibj

例如猜测一个8比特的密钥，模板攻击的结果是10111101.各个比特的判断成功率如表2所示。

表2 假设判断成功率

如果结果不正确，可将b1取反，依次尝试以下密钥：10111100、10111111、10111110、10111001等，直到结果正确为止。

结合增强型的暴力攻击策略，单比特密钥模板攻击可以大大缩小DES算法的密钥空间，原因是同一个密钥比特会使用在同一轮运算的不同位置以及不同轮运算中，DES的这种高扰乱特性非常适合直接将密钥比特作为攻击目标。但单比特模板攻击方法也有其局限性，从图3中，可发现相关系数的最大值也才0.3左右，相关性小导致判断精度并不高，造成这种现象的原因是单比特密钥在电磁曲线中影响很小，而且被多种噪声叠加，包括其他的相邻密钥比特。下一步研究的重点是如何消除干扰，提高相关性。

3 结 论

本文提出了一种直接以密钥为目标的单比特模板攻击方法，该方法的优点在于：根据相关系数大小选择抽样点，大大降低了计算复杂度；根据比特建立模板，模板数量大大减少；直接以密钥为攻击目标，无须知道明文或者密文。

通过对单片机上实现的DES密码系统的电磁模板分析攻击，验证了该方法的可行性和有效性。

[1] CHARI S, RAO J R, ROHATGI P. Template attacks[C]//Proceedings of CHES 2002. Berlin: Springe: 13-28.

[2] AGRAWAL D, RAO J R, ROHATGI P, et al. Templates as master keys[C]// Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems (CHES'05). Edinburgh, 2005: 15-29.

[3] ARCHAMBEAU C, PEETERS E, STANDAERT F X, et al. Template attacks in principal subspaces[C]// Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems (CHES'06). Yokohama, 2006: 1-14.

[4] GIERLICHS B, LEMKE-RUST K, PAAR C. Templates vs. Stochastic methods[C]// Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems (CHES'06). Yokohama, 2006: 15-29.

[5] STANDAERT F X, ARCHAMBEAU C. Using subspace-based template attacks to compare and combine power and electromagnetic information leakages[C]// Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems (CHES'08). Washington, 2008: 411-425.

[6] LERMAN L, BONTEMPI G, MARKOWITCH O. Side channel attack: an approach based on machine learning[C]// Proceedings of 2nd International Workshop on Constructive Side-Channel Analysis and Security Design, 2011: 29-41.

[7] 邓高明, 赵 强, 张 鹏, 等. 针对密码芯片的电磁频域模板分析攻击[J]. 计算机学报, 2009, 32(4): 602-610.

DENG Gaomin, ZHAO Qiang, ZHANG Peng, et al. EM frequency domain template analysis on cipher chips[J]. Chinese Journal of Computers, 2009, 32(4): 602-610.(in Chinese)

[8]International Electro Technical Commission. IEC 61967: Integrated Circuits-Measurement of Electromagnetic Emanations, 150 kHz to 1 GHz[S/OL] 2002. http://www.iec.ch/

[9] RECHBERGER C, OSWALD E. Practical template attacks[C]// WISA, Springer, 2004, 3325: 440-456.

[10] HANLEY N, TUNSTALL M, MARNANE W P. Unknown plain-text template attacks[C]// Workshop on Information Security Applications, December 2009:148-162.

[11] 周建钦, 何凌云. DES加密算法的密钥扩展[J]. 科技通报, 2011, 27(2): 263-267.

ZHOU Jianqin, HE Lingyun. Key expansion of DES encryption algorithm[J]. Bulletin of Science and Technology, 2011, 27(2): 263-267.(in Chinese)