基于聚类分析的轻量化掩码分析方法

基于聚类分析的轻量化掩码分析方法 Clustering-Based Power Analysis against Lightweight Mask Scheme 1 2 first-author 唐明，女，副教授，主要从事密码学和密码芯片的研究. E-mail:m.tang@126.com 唐明，女，副教授，主要从事密码学和密码芯片的研究. E-mail: m.tang@126.com m.tang@126.com 1 2 3 1 2 武汉大学 计算机学院，湖北 武汉，430072 武汉大学 计算机学院，湖北 武汉，430072 School of Computer , Wuhan University, Wuhan 430072, Hubei, China School of Computer , Wuhan University, Wuhan 430072, Hubei, China 空天信息安全与可信计算教育部重点实验室，湖北 武汉，430072 空天信息安全与可信计算教育部重点实验室，湖北 武汉，430072 Key Laboratory of Aerospace Information Security and Trusted Computing Ministry of Education, Wuhan 430072, Hubei, China Key Laboratory of Aerospace Information Security and Trusted Computing Ministry of Education, Wuhan 430072, Hubei, China 北京南瑞智芯微电子科技有限公司，北京， 100192 北京南瑞智芯微电子科技有限公司，北京， 100192 Beijing Nari Smartchip Microelectronics Technology Company Limited, Beijing 100192, China Beijing Nari Smartchip Microelectronics Technology Company Limited, Beijing 100192, China 轻量化掩码是资源受限的密码芯片的主要防护方法，而现阶段针对掩码的分析方法都不适用于轻量化掩码.本文提出了基于聚类分析的non-profiled 侧信道分析方法,对通用轻量化掩码方案进行安全性分析：分别利用PCA(principal component analysis)和FFT(fast Fourier transform)对功耗曲线进行特征提取以准确地选择掩码对应的特征点，然后将每条功耗曲线的特征点作为其特征按掩码单字节取值进行聚类.通过对DPA Contest V4.1竞赛提供的实测数据的分析表明本文提出的non-profiled 侧信道分析方法适用于通用轻量化掩码方案，同时本文所采用的特征提取方法也适用于侧信道分析预处理阶段的特征点选择. Lightweight mask scheme has been the majority protection method for cipher chips which are resource limited. At the present stage, those analysis methods which aimed at mask are not appropriate for lightweight mask. In the paper, we propose clustering-based non-profiled side channel analysis method aiming at the general lightweight mask scheme and conduct security analysis on the lightweight mask scheme. First of all, we select the feature points of mask by PCA(principal component analysis) and FFT(fast Fourier transform), then cluster the power traces by masks’ single byte value. According to the analysis of power traces provided by the DPA Contest V4.1, it manifests that the non-profiled side channel analysis method proposed by us can be utilized to the general lightweight mask scheme, also the feature points selection of pretreatment. 掩码方案 轻量化防护 non-profiled分析 侧信道分析 聚类分析 mask scheme lightweight countermeasure non-profiled analysis side channel analysis cluster analysis 引言 1 掩码是分组密码防护侧信道分析时最广泛使用的对抗方法.1999年至今，掩码从最初的一阶掩码发展为高阶掩码并进一步扩展为通用高阶掩码及轻量化掩码. 高阶掩码方案虽然具有很高的安全性，但其资源消耗高往往不能在资源受限的密码设备(如智能卡)中被实现，于是出现了轻量化掩码方案的发展趋势，这也是RSM(Rotating S-box Masking) 方案 [ 1 1 ] 设计的目的和优势.轻量化掩码方案通过掩码复用等手段减少方案中掩码的数量，能实现安全性与资源开销的折衷. 侧信道分析可以分为profiled分析和non-profiled分析 [ 2 2 ] .profiled分析适用于已知密钥从而可以建立精确泄露模型的评价场景，而non-profiled方法旨在对不具有先验信息的目标设备进行实际的分析 [ 3 3 , 4 4 ] .针对掩码的高阶non-profiled分析和profiled分析由于较高的分析复杂度和严格的分析条件对于轻量化掩码都不适用.聚类分析是一种无监督学习，它不需要先验信息，因而也是一种non-profiled分析方法.聚类可作为侧信道分析的预处理方法，与传统的non-profiled分析方法结合可以形成新的效果更好的non-profiled分析方法.因此，本文提出基于聚类分析的轻量化掩码分析方法. 轻量化掩码方案 1 轻量化掩码方案能实现安全性与资源开销的折衷，适用于资源受限的密码设备.RSM方案是一种轻量化掩码方案，它是DPA Contest V4.1 ( http://www.dpacontest.org/v4/index.php http://www.dpacontest.org/v4/index.php )所采用的防护方法.RSM方案随机生成一个偏移量，再对基础掩码按偏移量循环左移生成新的掩码序列.RSM掩码方案中所用的基本掩码对应汉明重为{0,4,4,4,4,4,4,4,4,4,4,4,4,4,4,8}.经过分析我们发现，可以从时间上将功耗曲线按每个字节对应的操作进行划分.以汉明重量为泄露模型，可以在明文异或掩码的时间点附近获得对应掩码的汉明重量，从而取得掩码的对应信息. 由上述介绍可知，原始RSM方案中存在缺陷：其所用的掩码字节存在三种不同的汉明重.文献 [ 5 5 ] 主要利用汉明重的差异来选点和聚类. 本文的分析对象是通用的轻量化掩码方案，所以并未利用RSM方案的汉明重缺陷.当掩码字节的汉明重量相同且掩码字节未知时，只有对每字节掩码按掩码取值选点并聚类才能对通用的轻量化掩码方案进行有效地分析.本文仍以8bit处理器为芯片载体，从non-profiled角度对轻量化掩码方案进行有效性研究. 针对掩码的攻击方法 1 针对掩码方案的攻击可分为非通用性攻击和通用性攻击.非通用性攻击针只对特定的掩码方案，利用该掩码方案存在的某些缺陷作为突破口进行分析.例如，文献 [ 6 6 ] 利用掩码方案中的零值缺陷(即在乘法掩码方案中，中间状态可能始终存在零值)进行分析，文献 [ 7 7 ] 利用AES(advanced encryption standard)的掩码方案的硬件实现中出现的毛刺缺陷进行分析. 通用性攻击主要包括高阶non-profiled分析和profiled分析. d 阶non-profiled分析同时利用功耗曲线上对应加密算法中 d 个不同中间值的 d 个功耗点进行攻击.由于高阶non-profiled分析的区分器(差分、相关性等)为单变量运算符，攻击者必须利用联合函数(combining function)C将于目标变量相关的d+1个联合泄露值( L 0 ,…, L d )转化为1个泄露值 C ( L 0 ,…, L d ).其中 L 0 = Leakage ( Z 0 ), L 1 = Leakage ( Z 1 ),…, L d = Leakage ( Z d )， L i 表示中间变量 z i 的泄露值.常用的联合函数主要有：内积联合函数 C prod ( L 0 ,…, L d )= L 0 ×…×L d 和差分联合函数 C diff ( L 0 ,…, L d )=||| L 0 - L 1 |- L 2 |… L d |.高阶non-profiled分析利用多个泄露点进行联合分析 [ 8 8 ] ，虽然具备通用性，但随着掩码方案阶数 d 的增加其复杂度呈指数式增长.profiled分析包括一个预先的profiling阶段，先利用先验信息恢复出掩码再恢复密钥.profiled分析对功耗曲线的信息利用率高，因而分析成功率高，但它需要攻击者能克隆实际的加密设备.因此，高阶non-profiled分析和profiled分析都不适用于实测曲线的分析场景，这也是本文提出基于聚类的non-profiled分析方法的原因. 掩码的特征提取 1 侧信道曲线上有许多与密钥有关的位置，但也有大量与密钥无关的样本点，这增加了计算复杂度并浪费了计算资源 [ 9 9 ] ，所以特征选择或特征提取，也即特征点选择的好坏决定了侧信道分析的成功与否. 衡量聚类技术优劣的核心指标是聚类准确率，而提高聚类准确率有两种方法，一是改进聚类算法，二是采用特征选择或特征提取技术.经过几十年的发展聚类算法已趋于稳定，虽然不断涌现出新的聚类算法但并未出现对所有应用场景都适用的方法 [ 10 10 ] .因此，相比于对聚类算法进行改进，选择一个合适的聚类算法意义更大. 特征提取方法的基本思想是利用原始特征构造新特征，新特征是原始特征的函数或变换，它们更具代表性且更能反映本质；同时新特征的维数小于原始特征维数，实现了特征空间的降维却能保留原始特征的主要信息 [ 9 9 ] .RSM掩码方案中的掩码是在16字节原始掩码上按offset移位得到的，原始掩码每一字节的值都是不一样的.在之前的研究中 [ 5 5 ] ，我们选取了16字节掩码对应的特征点进行聚类，由于不同掩码相同字节对应的值是不同的，所以只需要选择一字节掩码对应的特征点即可进行聚类.本文在之前研究的基础上利用更精准的选点方法以实现按值聚类而不是按汉明重聚类. 基于线性变换的特征提取 2 PCA(principal component analysis)是经典的基于线性变换的特征提取方法，它通过某种线性变换将高维数据映射到低维空间中表示，并期望在所投影的维度上数据的方差最大以使用较少的数据维度同时保留较多的原始数据特征. 在原始的高维空间中，包含有大量冗余信息以及噪声，在实际应用例如聚类分析中造成了误差，降低了准确率；而通过降维,我们希望减少冗余信息所造成的误差,提高识别(或其他应用)的精度.通过降维算法可找数据内部的本质结构特征并加速后续计算的速度. 由于PCA依赖于协方差矩阵的二阶相关性，PCA适用于高斯分布的数据 [ 11 11 ] .侧信道信号服从高斯分布，PCA在侧信道分析领域有广泛的应用但PCA的潜能并未完全被挖掘 [ 12 12 ] . 对于 n 条曲线每条曲线 m 个点的功耗曲线可以表示为一个 n × m 的矩阵 X n×m ，通过 PCA 计算出每一个成分的贡献率可以得到贡献率矩阵 A m×n ，选择前 k (一般 k 远小于 m )个贡献率最大的特征值使得这 k 个主成分的累积贡献率达到一定值(一般大于85%),这时对应的 k 个向量仍然保留原始信号足够多的信息.因此，可以利用这 k 个特征值对应的主成分来将原高维特征矩阵映射成一个低维特征矩阵，根据公式 Y n×k = X n×m × A m×k 可以计算出新的低维特征矩阵Y. 基于时频变换的特征提取 2 时频变换将信号从时域转换到频域，常见的方法包括傅里叶变换和余弦变换. 长度为N的时域序列 x(n) (0≤ n ≤ N －1)的离散傅里叶变换(DFT,discrete Fourier transform) X(k) 仍然是一个长度为 N (0≤ k ≤ N －1)的频域序列，变换关系式为： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458205&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458205&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458205&type=middle 若 y(n) = x ( n - m )，则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458209&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458209&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458209&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458213&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458213&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4458213&type=middle 由上式可知，信号x(n)在时域中的移位等效于在频域中相位移动，即信号时移后期振幅谱不变只是相位谱产生附加变化.FFT(transform Fourier fast)是DFT的一种快速计算方法，它大大减少了计算过程中所需要的乘法数量.因此，本文在特征提取时用FFT来实现DFT. 由于功耗采集触发机制不固定、设备时钟频率不稳定、加入了防护(插入随机时间片等)和噪声等因素的影响，导致功耗曲线上相同操作对应的时间点不对齐，从而导致基于时域的诸多侧信道分析方法准确率下降甚至失效.示波器采集的信号可以看成能量有限信号，由能量守恒定律可知时域信号的能量等于频域信号的能量，也即信号经傅里叶变换其总能量保持不变. 对于侧信道分析，频域已被证明比时域有更大的优势 [ 13 13 ] ：在时域进行分析时攻击者通常认为每个时间样本点都是独立的从而没能充分利用泄露信息；在频域分析时具有更健壮的抗噪性，因为频域分析同时处理多个样本点从而能容忍一些异常值. 实验与结果分析 1 特征点选择 2 对DPA Contest V4.1 官网上的参照曲线分别利用PCA和FFT进行选点. 利用PCA对2 000条参照曲线(第4 000至第5 023点)进行选点，将2 000×1 024的原始矩阵降维至2 000×29的特征矩阵.在 图1 图1 中曲线为累积贡献率，柱体为每一维的贡献率.由 图1 图1 可知，10个维度即可表示70%的原始特征，而表示95%的原始特征只需要29个维度.因此，通过PCA降维大大降低了聚类分析和侧信道分析的时间复杂度并能提高聚类分析和侧信道分析的成功率. 对DPA Contest V4.1 官网上的1条原始曲线(第4 000至第5 023点)如 图2 图2 ，对其进行傅里叶变换后如 图3 图3 .在 图3 图3 和 图4 图4 中横坐标为时间，纵坐标为振幅.FFT处理之后的数据与频率不对应，如 图4 图4 所示，fftshift将FFT的直流分量(零频)移动到中心使数据与频率对应.在 图4 图4 中取高振幅部分(400至600)作为聚类的特征点. 聚类分析 2 利用PCA和FFT对DPA Contest V4.1上公布的reference traces中的100条曲线进行选点再K-means进行聚类，K-means聚类的参数设置：距离模型采用默认的欧氏距离模型；重复次数为500次.由于每字节掩码共16类，故聚类后分成16类，每一类正确率不同，当在实际攻击时，需要对聚类后的任选一类进行PA攻击，所以聚类时要考虑最差情况即把16类中的最低正确率作为评价标准.本实验侧重对曲线数量不同情形下及选点方法不同情形下聚类正确率的影响，聚类正确率见 图5 图5 ，其中横坐标为聚类所用的曲线数量，纵坐标为聚类成功率.由 图5 图5 可知，基于FFT的聚类仅需约200条曲线能恢复掩码，而基于PCA的聚类需要约1 000条能恢复掩码.PCA和FFT不需要掩码的信息就能有效地选择掩码对应的特征点，因而都是non-profiled特征点选择方法. 基于聚类的non-profiled分析不要掩码的信息就能正确地按字节恢复掩码，而profiled分析需要已知掩码取值的训练曲线集，这个条件在实际的攻击场景是不满足的.基于聚类的non-profiled分析在恢复掩码后再进行一阶non-profiled分析就能恢复密钥，而一阶non-profiled分析复杂度远低于高阶non-profiled，基于聚类的non-profiled分析时间复杂度优于高阶non-profiled分析.综上所述，基于聚类的non-profiled分析是一种有效的轻量化掩码分析方法. 结果分析 2 在原始功耗曲线矩阵中夹杂的噪声维度和明文维度对掩码，协方差矩阵的特征值对应贡献率，特征值越大则该维度对方差影响越大.对于掩码对应的曲线段，掩码的特征点对方差的影响大于噪声和明文对应的特征点.PCA将样本协方差矩阵进行特征值分解，选取最大的若干个特征值对应的特征向量组成投影矩阵，再利用投影矩阵将数据集从高维空间投影到低维空间，保留了特征值较大且不相关的主成分，使得投影后每一个维度内部方差最大而维度之间的协方差为0(两两正交)，从而起到降维、去噪和去冗余的作用.利用PCA进行特征提取时，每一个特征点的权重是该点的贡献率，而在掩码对应的曲线段掩码的贡献率大于明文并远大于噪声，选择贡献率最大的若干维度进行降维可以去掉大部分明文和噪声的干扰并保持绝大部分掩码的特征，这也是聚类的成功率低于95%的原因. 若功耗曲线在时域上没对齐，通过FFT转换到频域后其振幅谱保持不变，因此FFT可将功耗曲线对齐.在功耗曲线上一个中间值产生的泄露对应于时域上的多个时间点，但在时域进行分析时将各个时间点独立处理，因此未能充分利用泄露信息.FFT将功耗曲线从时域转换到频域后能更精确的刻画时域多个时间点对应的泄露，所以频域的泄露信息利用率比时域高.频域的抗噪性高于时域，噪声、明文和掩码在频域上有不同的分布特征：噪声和明文主要分布在低振幅区域，而掩码主要分布在高振幅区域.利用FFT进行特征提取时，经傅里叶变换后掩码的振幅谱保持不变.进行fftshift之后掩码对应的高振幅汇聚到中心，取中心范围的高振幅就完全去除了明文和噪声的干扰. 结论 1 掩码防护是侧信道分析中被广泛采用且已被普遍认为可证明安全的防护方法之一，对于掩码的分析方法主要为高阶non-profiled分析和profiled分析，但它们都有诸如较高的复杂度或严格的分析条件以至于对于轻量化掩码的适用性都较弱. 本文针通用的轻量化掩码方案进行了non-profiled 侧信道安全性分析，首先分析了RSM掩码方案中的缺陷，再利用两种不同的特征提取方法高效地选择一字节掩码对应的特征点，然后对功耗曲线按掩码字节取值进行聚类，使得同一类的曲线具有相同的掩码序列，这样也就成功消除了掩码的作用，从而可以有效地进行密钥恢复.由于本文提出的分析方法是按值选点和按值聚类，对于其他轻量化掩码方案同样是适用的，因而是一种通用的轻量化掩码分析方法，这可为轻量化掩码方案的设计提供参考与借鉴.此外，由于本文提出的non-profiled特征提取方法能成功选择掩码在功耗曲线上对应的特征点，在预处理阶段将选择区间切换到明文或密钥对应的区域即可选出侧信道分析需要的特征点.因此，本文提出的non-profiled特征提取方法也适用于侧信道分析预处理阶段的特征点选择，这可以大大提高侧信道分析的成功率，还能减小分析的复杂度. 参考文献 NASSAR M, SOUISSI Y, GUILLEY S, et al. RSM: A small and fast countermeasure for AES, secure against 1st and 2nd-order zero-offset SCAs[C]// Design, Automation & Test in Europe Conference & Exhibition (DATE’ 2012). Washington D C: IEEE, 2012: 1173-1178. VEYRAT-CHARVILLON N, STANDAERT F X. Generic side-channel distinguishers: Improvements and limitations[C]// Advances in Cryptology-CRYPTO 2011. Berlin Heidelberg: Springer-Verlag, 2011: 354-372. 张焕国, 李春雷, 唐明. 演化密码对抗多重线性密码分析能力的研究[J]. 中国科学: 信息科学, 2012, 42(5): 603-616. ZHANG H G, LI C L, TANG M. Research on evolutionary cryptography against multidimensional linear cryptanalysis[J]. Scientia Sinica(Informationis), 2012, 42(5): 603-616(Ch). 张焕国, 李春雷, 唐明. 演化密码对抗差分密码分析能力的研究[J]. 中国科学: 信息科学, 2013, 43(4): 545-554. ZHAGN H G, LI C L, TANG M. Capability of evolutionary cryptosystems against differential cryptanalysis[J]. Scientia Sinica(Informationis), 2013, 43(4): 545-554(Ch). 唐明, 王欣, 李延斌, 等. 针对轻量化掩码方案的功耗分析方法[J]. 密码学报, 2014, 1(1): 51-63. TANG M, WANG X, LI Y B,et al. The power analysis on the lightweight mask scheme[J]. Journal of Cryptologic Research, 2014, 1(1): 51-63(Ch). GOLIĆ J D, TYMEN C. Multiplicative masking and power analysis of AES[C]// Cryptographic Hardware and Embedded Systems(LNCS 2523). Berlin Heidelberg: Springer , 2002: 198-212. CORON J S, PROUFF E, RIVAIN M. Side Channel Cryptanalysis of a Higher Order Masking Scheme[C]// Cryptographic Hardware and Embedded Systems(LNCS 4727). Berlin Heidelberg: Springer , 2007: 28-44. KOCHER P, JAFFE F, JUN B. Differential Power Analysis[C]// Advances in Cryptology-CRYPTO’99. Berlin Heidelberg: Springer, 1999: 388-397. 郭世泽, 王韬, 赵新杰. 密码旁路分析原理与方法 [M]. 北京:科学出版社,2014: 89-90. GUO S Z, WANG T, ZHAO X J. Principles and Methodologies of Side-Channel Analysis in Cryptography [M]. Beijing: Science Press,2014: 89-90(Ch). JAIN A K. Data clustering: 50 years beyond k-means[J]. ECML/PKDD (1), 2008, 5211: 3-4. JAIN A, DUBES R. Algorithms for Clustering Data[M]. Englewood Cliffs: Prentice-Hall, 1988. BATINA L, HOGENBOON J, van WOUDENBERG J G J. Getting more from PCA: Firstresults of using principal component analysis for extensive power analysis[C]//Topics in Cryptology-CT-RSA 2012. Berlin Heidelberg: Springer, 2012: 383-397. MAURINE P, TIRAN S. SCA with Magnitude Squared Coherence[C]//CARDIS’12: Eleventh Smart Card Research and Advanced Application Conference. Berlin Heidelberg: Springer, 2012: 001-010. 10.14188/j.1671-8836.2016.03.004 TP 309.7 whdxxblxb-62-03-230 国家重点基础研究发展计划（973）项目(2014ZX01032401-001)；国家自然科学基金(61472292，61202386)资助项目 2014-12-10 2016-06-24 2020-12-09 版权所有 © 《武汉大学学报(理学版)》编辑部 Copyright © 2016 Journal of Wuhan University (Natural Science Edition). All rights reserved. 2016 武汉大学学报(理学版) 3 62