密码芯片基于聚类的模板攻击

吴震，杜之波，王敏，向春玲



密码芯片基于聚类的模板攻击

吴震，杜之波，王敏，向春玲

（成都信息工程大学网络空间安全学院，四川 成都 610225）

传统的模板攻击需要已知密钥建模等对实验设备完全控制的前置条件来实施攻击，该前置条件限制了模板攻击的应用场景，使模板攻击只能应用于可以控制密钥输入的设备。为了解决该问题，提出了基于聚类的模板攻击方法。该方法根据信息泄露模型的特征对聚类期望最大值（EM）算法进行改造，使改造后的聚类方法能够较为准确地拟合出泄露信息的概率模型，在未知密钥的情况下，即可确定信息泄露的位置。该方法通过建模进行模板匹配，消除了传统模板攻击对已知密钥建模等前置条件的依赖，从而扩大了模板攻击的应用范围。

侧信道攻击；模板攻击；聚类；EM算法

1 引言

侧信道攻击是一种利用加密设备的能量泄露来攻击设备密钥的方法。Kocher等最早提出SPA （simple power analysis）[1]和DPA（differential power analysis）[2]的能量攻击方法。这些攻击方法的原理是：假设加密的某个中间状态与泄露的能量具有相关关系，攻击者可以使用泄露的能量来检查、猜测密钥的正确性，从而达到攻击的目的。CPA（correlation power analysis）[3]是利用这种相关性进行攻击的最有效方法。SPA、DPA、CPA以及基于这些方法提出的其他方法都是直接对加密设备进行攻击的，并不需要一个训练阶段。

模板攻击[4]是侧信道攻击技术的另一个分支。模板攻击分为2个阶段：建模和攻击。在建模阶段，模板攻击利用与被攻击设备相同的、攻击者可完全控制的实验设备，通过设置密钥和明文实施多次加密操作，收集操作的大量能耗数据，并据此建立、刻画被泄露信息的能耗概率模型。精确的能耗概率模型可以使攻击者仅使用少量的攻击能迹就能够恢复设备的密钥。但相对于SAP、DPA和CPA，模板攻击需要攻击者具有对实验设备的完全控制能力，这限制了其应用范围。为了克服这一现状，文献[5]提出一种仅需3个密钥的半监督建模方法；文献[6-7]则更近一层地提出EIS（equal image under different sub-key）的概念，即不论使用固定密钥随机明文，还是使用固定明文随机密钥，加密中间值的分布都是相同的。这样，攻击者只需要知道实验设备的密钥，而不需要改变其密钥，采用固定密钥随机明文的方法收集能迹，同样可以建立泄露信息的模板，进而成功地获取被攻击设备的密钥。

本文对高斯混合分布的EM算法在模板攻击中的应用方法进行了详细的讨论。根据理论上和实际中的经验，提出了对EM算法的几种针对性的约束，以便真正提高聚类的质量。这些方法运用在9个簇的汉明重量模型的聚类中，可以相当准确地还原出真实成员分布。针对EM算法得到局部最优的问题，本文给出了切实可行的算法初始参数设置方法。此外，上述文献并未讨论如何在密钥或掩码未知的情况下，找到确切的泄露位置，针对泄露位置的问题，要么采用类似暴力攻击的方法，要么直接假设已知泄露位置。对此，本文提出了一种在未知密钥的情况下，准确找到信息泄露位置的方法。

2 基于聚类的模板攻击模型

2.1 基本攻击模型

假设攻击者没有标准模板攻击所需要的实验设备，即不能设置加密设备的密钥，只能设置任意随机明文使用加密设备进行加密操作，并收集设备能耗。在这种场景下，由于密钥未知，无法计算目标操作的中间值，不能使用有监督的学习方法获得模板。

在这种无法预知中间值、无法明确分类的情况下，则可以采用无监督的学习发现数据外在的划分或内在的模型。无监督的学习算法可以分为2个类别：簇合算法和基于潜变量模型的学习。簇合算法根据数据本身的特征（相似性、距离等），将特征相似或距离相近的数据聚集在一起形成簇。常见的簇合算法包括-means、DBSCAN、高斯混合模型等。簇合算法的质量取决于数据特征的显著程度。基于潜变量模型的学习算法认为数据中可观察的变量（显变量）是由内在的、不可观察的隐变量决定的。

在侧信道攻击中，广为接受的能耗模型是汉明重量或汉明距离模型。该模型认为，加密操作中间值的汉明重量或汉明距离与相应的能耗呈线性关系，且叠加高斯噪声。这样，各汉明重量或汉明距离的能耗是一个高斯分布，所有汉明重量或汉明距离的能耗则是一个混合高斯分布。这种成员分布就是模板攻击中所需要的模板。针对混合高斯分布的无监督学习算法是EM算法。如果攻击者可以使用EM算法还原出真实的内在分布，就可以以此为模板进行模板攻击。这里的关键问题是，对于高噪声、低信噪比的能耗数据，EM算法能够在多大程度上还原数据的真实分布。

2.2 混合高斯模型及其EM聚类算法

2.2.1 汉明重量能耗模型与混合高斯分布

以8位SBOX输出为例，其汉明重量为0~8。图1给出了实际能耗数据的混合一元高斯分布。

图1 实际能耗数据的混合一元高斯分布

从图1可以看出，实际分布与汉明能耗模型的预测是非常相符的。

2.2.2 使用EM算法估算能耗的混合高斯分布

若式(9)对各参数的偏导等于0，就可以得到EM算法迭代中参数的更新方法，为

EM算法通过反复迭代来优化对数似然率的数学期望，直到对数似然率的变化小于一个阈值为止。每次迭代分为E-Step和M-Step。

E-Step：根据当前的模型参数，使用式(9)计算成员率矩阵。

M-Step：根据当前的成员率，使用式(10)~式(12)更新模型参数。

然而，对于低信噪比的能耗数据，标准EM算法的聚类并不能恢复真实的成员分布。图2是在混合二元高斯模型下，EM算法得到的成员分布与真实成员分布的对比情况。其中，椭圆是各成员分布的95%最大概率密度的等高线。黑色为真实数据的成员分布，灰色是EM算法得到的混合高斯分布的聚类成员分布（下同）。可以看出，由于各汉明重量的能耗数据高度混淆在一起，标准EM算法并不能准确恢复真实成员分布的中心位置和方差。

图2 真实成员分布（黑色）与EM聚类成员分布（灰色）比较

2.3 汉明能耗模型及其EM聚类算法

汉明能耗模型是一种特殊的高斯混合分布模型，有以下特征。

1) 成员分布的先验概率固定

对于本文设定的攻击场景：密钥固定和采用随机明文，目标操作的中间值是均匀分布的。这样，中间值的汉明重量呈二项分布。假设中间值为位，汉明重量为时对应的成员分布的先验概率为

2) 相邻成员分布中心的距离相等

在汉明能耗模型中，由于均值能耗与汉明重量呈线性关系，即

则任意2个相邻的汉明重量的均值能耗之差为

其中，协方差矩阵的更新方式并未发生变化。

汉明能耗模型还有一个弱特征，即各成员分布的协方差矩阵相同或接近。这是因为，与同一个操作相关的噪声主要是由操作指令的硬件实现决定的，而与操作数的关系不大。假设该特征成立，则各成员的协方差矩阵应该是相同的。共享协方差矩阵的更新式为

图3和图4为采用上述特征改造EM算法后，数据的聚类成员分布与真实成员分布的对比情况。从图3可以看出，聚类得到的成员分布与真实成员分布仍然有一定差异。不仅是各成员分布中心与真实中心仍有较大的差异，成员分布的方差与真实方差相比也有较大差异。但总体来看，其比采用标准EM算法得到的结果要好得多。而图4是采用共享协方差矩阵得到的结果。其特点是：共享协方差矩阵的EM算法趋于将成员分布重叠在整体能耗均值中心，这一点可以从理论上得到证明（略）。因此，共享协方差矩阵在这里无法得到应用。

图4 共享协方差矩阵时，聚类成员分布与真实成员分布

3 EM算法改造

由于能耗数据的低信噪比的特点，标准的EM算法的聚类结果与真实数据分布相差巨大。而模板攻击所依赖的是对数据噪声的准确了解和表达。如果不对算法进行适应性改造，使用聚类算法进行模板攻击是不可行的。汉明重量模型提供了一些特征，可供对混合高斯模型以及相应的EM算法进行改造。

3.1 对聚类的优化

上述根据汉明能耗模型特征对EM算法的改造仍然无法得到所需的聚类质量。本节根据其他一些隐藏的特征，为EM算法附加一些额外约束，以期提高聚类质量。

3.1.1 成员分布的相关系数约束（pdc）

成员分布的协方差矩阵的非对角元素为

相应地修改EM算法的M-Step：首先按对角协方差矩阵更新对角元素为

然后根据式(23)计算协方差矩阵的非对角元素。

图5显示了采用相同相关系数后，聚类得到的成员分布与真实成员分布的对比情况。与第2节的聚类结果相比，采用相同的相关系数后，成员分布的中心和方差与真实分布更加接近。

图5 pdc条件下聚类成员分布与真实成员分布对比

从图5可以看出，采用pdc相关系数约束后，成员分布中心和方差与真实分布较为接近。

3.1.2 成员分布的形状约束（pds）

根据真实分布的特点可以看出，所有成员分布等高线的“形状”大致相似。这并不是偶然的。“形状相似”实际上反映了不同汉明重量下，能耗的概率密度分布是相似的。不同的汉明重量可能影响方差的大小，但不会影响各维数据方差的比例关系和相关性。因此，成员分布形状相似的假设比共享协方差矩阵的假设稍弱。

从几何上看，等高线形状相似包括2个因素：等高线椭圆的方向一致，且椭圆的长短轴比例相等。首先推导二元高斯分布等高线的方向，然后扩展到多元高斯分布。

将式(28)代入式(27)，且设式(27)右端等于1，则有

式(30)旋转后得

(32)

比较式(30)和式(28)，有以下方程组成立。

解式(32)可得

对于多元高斯分布，对其中任意二维使用式(34)，可计算等高线在该二维子平面上的旋转角度。然后利用式(35)，根据成员分布在该二维上的方差，计算子平面上的协方差。

根据这种方法，聚类的结果如图6所示。除汉明重量为0和8的成员分布与真实分布有偏差外，其余成员分布的中心和方差几乎完全与真实分布相同，非常好地还原了真实成员分布。汉明重量为0和8的拟合成员分布与真实分布的偏差主要来源于真实分布自身的偏差：在固定密钥、随机明文的训练能迹中，汉明重量为0和8的能迹数与总训练能迹数的比例近似等于其理想先验概率，即0.39%。实验中使用8 000条能迹，而汉明重量为0和8的能迹数仅为31条左右。由于能迹不足，造成了其真实分布的统计偏差。

图6 psd条件下成员分布与真实成员分布对比

从图6可以看出，使用成员分布等高线形状相似约束后，EM算法可以很好地恢复真实分布。

3.2 聚类的初始参数设置

3.2.1 未知密钥时发现信息泄露的位置

由于能迹上的样本数非常多，大多数样本与目标操作的信息泄露无关。直接使用能迹的全部样本作为能迹向量的元素，在效率上不可行，聚类的结果也不可能作为有效的模板。在本文设置的攻击场景下，设备密钥位置，无法计算真实的目标中间值，因此无法使用这些方法得到POI。

3.2.2 根据设备信噪比设置聚类初始参数

由于EM算法得到的是局部最优解，算法初始参数的设置非常关键。根据混合分布的整体方差与成员方差的关系以及理想分布中关于成员分布中心均匀线性分布和方差相等的假设，可以根据POI上的信噪比估算初始参数。

混合分布与其成员分布的方差关系为

根据理想分布的假设，有

代入式(38)可得

根据能耗上信息泄露的特点，将信噪比定义为

代入式（40）后得到

4 实验分析

4.1 实验设置

针对某密码芯片的SM4算法软实现进行多种方式的攻击，共收集能迹10 000条，其中，8 000条用于训练，2 000条用于攻击测试。芯片主频为2.8 MHz，示波器采样频率为100 MHz。采样能迹进行了低通滤波和对齐处理。

4.2 确定信息泄露位置

根据上文所述方法，确定被攻击SM4芯片的POI，图7是根据SOST确定的第一个SBOX输入和输出的POI，图中2个高尖峰对应的位置即是SBOX输入和输出的POI，SBOX输入的位置为509，SBOX输出的位置为554，根据分组内SBOX输入和输出值以及输入和输出汉明重量确定的POI如表1所示。

图7 能耗迹的SOST峰值

表1 POI点

4.3 与标准模板攻击的对比实验

实验中分别采用以下方法获得模板，以便进行对比。

1) 标准的模板攻击。即使用已知的固定密钥对训练能迹集进行分组，从而得到模板，该方法用STD表示。

2) 采用EM算法对训练能迹进行聚类得到的模板，该方法用EM表示。

3)采用根据汉明能耗模型改造的EM算法聚类得到的模板，该方法用EMPD表示。

4) 在汉明能耗模型的基础上，采用增加相关性约束改造EM算法后聚类得到的模板，该方法用EMPDC表示。

5) 在汉明能耗模型基础上，采用增加“形状相似”约束改造EM算法后聚类得到的模板，该方法用EMPDS表示。

攻击方法2)~5)选择POI的方法见3.2节。实验中统一选择2个兴趣点。攻击质量的指标用1阶成功率到4阶成功率表示。阶成功率表示正确密钥在攻击后得到的、按概率降序排序的候选密钥集的前个的比例。猜测熵[16]表示在多次实验攻击中，正确密钥的平均位置。根据文献[16]给出的猜测熵计算方法，计算每个攻击方法的猜测熵。

从图8可以更明确地观察5种模板生成方法之间的比较关系。从表2可以看出，EMPDS方法的攻击成功率基本与模板攻击相当，而EM方法最差，EMPD与EMPDC没有本质的区别。

图8 5种模板生成方法的1阶成功率比较

4.4 对一个能迹集的攻击实验

在本文设定的攻击场景下，由于训练时密钥未知，因此在实际攻击时，不存在训练能迹集与攻击能迹集的区别。本节实验采用一个能迹集，同时用于训练和攻击。本实验的目的是，测试能迹集的大小与攻击成功率的关系。

攻击时并不采用全部能迹，而仅选择在能耗均值向量附近的30条能迹作为攻击能迹。由于计算成功率需要多次实验，且每次实验需要采用不同的能迹进行攻击，因此首先选择与能耗均值向量最接近的600条能迹作为攻击能迹集，每次实验随机从其中选择30条进行攻击，共进行20次攻击。此外，根据4.2节实验的结果，这里仅对标准模板攻击和采用EMPDS的攻击进行比较，如表3所示。

从表3可以看出，训练能迹集达到3 000条后，4阶成功率可达到100%；训练能迹集达到5 000条后，1阶成功率可达到100%，该成功率已优于标准模板攻击。当能迹数在4 000条以下时，由于数据稀缺问题，聚类质量出现下降，该问题在标准模板攻击中同样存在。从猜测熵的对比来看，EMPDS在所有训练能迹数下均小于标准模板攻击。

5 结束语

从实验结果可以看出，改造后的EM算法可以相当好地还原出不同汉明重量能耗的成员分布，从而成功实现模板攻击。这种攻击方式并不需要攻击者掌握对被攻击设备的控制权，甚至也不需要了解任何密钥信息，就能以相当高的成功率攻击出密钥。从效率来看，由于本文方法可以准确地找到POI，同时合理地设置了EM算法的初始参数，聚类效率也比较高（一般10次迭代就可以达到阈值）。实验中为了证明本文方法的有效性，与标准模板攻击进行对比，验证了两者的应用场景不同。标准模板攻击通过实验设备得到模板后，只需要少量能迹即可实施攻击。而本文方法虽然不需要实验设备，但事实上需要更多的能迹来以聚类方式建模和实施攻击。本文的主要贡献在于：突破了已有对实验设备完全可控的局限性，详细讨论了EM聚类算法在能耗混合高斯分布中的适应性改造，并在实践中证明了这种改造的有效性。

表2 5种模板训练方法的攻击成功率和猜测熵对比

表3 STD与EMPDS训练能迹数与攻击成功率的关系

[1] KOCHER P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C]//Annual International Cryptology Conference. 1996: 104-113.

[2] KOCHER P, JAFFE J, JUN B. Differential power analysis[C]//Annual International Cryptology Conference. 1999: 388-397.

[3] BRIER E, CLAVIER C, OLIVIER F. Correlation power analysis with a leakage model[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2004: 16-29.

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

[5] LERMAN L, MEDEIROS S F, VESHCHIKOV N, et al. Semi- supervised template attack[C]//International Workshop on Constructive Side-Channel Analysis and Secure Design. 2013: 184-199.

[6] SCHINDLER W, LEMKE K, PAAR C. A stochastic model for differential side channel cryptanalysis[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2005: 30-46.

[7] GIERLICHS B, LEMKE-RUST K, PAAR C. Templates vs. stochastic methods[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2006: 15-29.

[8] KARSMAKERS P, GIERLICHS B, PELCKMANS K, et al. Side channel attacks on cryptographic devices as a classification problem[J]. Esat Kuleuven Be, 2009, 7: 36.

[9] LERMAN L, POUSSIER R, BONTEMPI G, et al. Template attacks vs. machine learning revisited (and the curse of dimensionality in side-channel analysis)[C]//International Workshop on Constructive Side-Channel Analysis and Secure Design. 2015: 20-33.

[10] 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.

[11] BATINA L, GIERLICHS B, LEMKE-RUST K. Differential cluster analysis[M]//Cryptographic Hardware and Embedded Systems-CHES. 2009: 112-127.

[12] CHOU J W, CHU M H, TSAI Y L, et al. An unsupervised learning model to perform side channel attack[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. 2013: 414-425.

[13] HEYSZL J, IBING A, MANGARD S, et al. Clustering algorithms for non-profiled single-Execution attacks on exponentiations[C]// International Conference on Smart Card Research and Advanced Applications. 2013: 79-93.

[14] LEMKE-RUST K, PAAR C. Gaussian mixture models for higher-order side channel analysis[C]//International Workshop on Cryptographic Hardware and Embedded Systems. 2007: 14-27.

[15] MANGARD S, OSWALD E, POPP T. Power analysis attacks: revealing the secrets of smart card[M]. New York: Springer. 2007.

[16] STANDAERT F X, MALKIN T G, YUNG M. A unified framework for the analysis of side-channel key recovery attacks[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2009: 443-461.

Template attack of Crypto chip based on clustering

WU Zhen, DU Zhibo, WANG Min, XIANG Chunling

College of Information Security Engineering, Chengdu University of Information Technology, Chengdu 610225, China

The known-key establishment template and others full control of experimental equipment preconditions are required to implement the traditional template attack. The preconditions restrict the application scenario of template attack. The template attack is only applied to the device that the key input can be controlled. In order to resolve the restrictive preconditions, a novel method of template attack based on clustering was proposed. The clustering EM algorithm was modified according to the characteristics of information leakage model in the method. The modified clustering methods accurately fitted the leaked information probability model in the case of unknown key, the location of information leakage could be determined. Then the attack established the templates in the location, and implemented template matching. The proposed method eliminates the dependence of traditional template attacks on per-conditions and expand the application scenario of template attack.

side channel attack, template attack, clustering, EM algorithm

TP309.1

A

10.11959/j.issn.1000−436x.2018130

吴震（1975−），男，江苏苏州人，成都信息工程大学副教授，主要研究方向为信息安全、密码学、侧信道攻击与防御、信息安全设备设计与检测。

杜之波（1982−），男，山东冠县人，成都信息工程大学副教授，主要研究方向为信息安全、侧信道攻击与防御、天线应用和物联网安全。

王敏（1977−），女，四川资阳人，成都信息工程大学副教授，主要研究方向为网络攻防、侧信道攻击与防御。

向春玲（1990−），女，湖北宜昌人，成都信息工程大学助教，主要研究方向为信息安全、嵌入式系统安全、侧信道攻击与防御。

2018−04−02；

2018−07−16

杜之波，du139123456789@163.com

国家科技重大专项基金资助项目（No.2014ZX01032401）；国家高技术研究发展计划（“863”计划）基金资助项目（No.2012AA01A403）；“十三五”国家密码发展基金资助项目（No.MMJJ20180244）；四川省科技支撑计划项目基金资助（No.2017GZ0313）；四川省教育厅重点科研基金资助项目（No.17ZB0082）

The National Science and Technology Major Project of China (No.2014ZX01032401), The National High Technology Research and Development Program of China (863 Program) (No.2012AA01A403), The “13th Five-Years” National Cryptogram Development Fund (No.MMJJ20180244), Sichuan Science and Technology Support Programmer (No. 2017GZ0313), Sichuan Provincial Education Department Key Scientific Research Projects (No.17ZB0082)