一种适用于SM4的改进RSM掩码方案

一种适用于SM4的改进RSM掩码方案 An Improved RSM Mask Scheme for SM4 first-author 马双棚, 男, 硕士生, 现从事信息安全的研究. E-mail: mashuangpeng1108@163.com 马双棚, 男, 硕士生, 现从事信息安全的研究. E-mail: mashuangpeng1108@163.com mashuangpeng1108@163.com 武警工程大学 电子技术系, 陕西 西安 710086 武警工程大学 电子技术系, 陕西 西安 710086 Department of Electronic Technology, Engineering College of Chinese Armed Police Force, Xi'an 710086, Shaanxi, China Department of Electronic Technology, Engineering College of Chinese Armed Police Force, Xi'an 710086, Shaanxi, China 为了增强SM4算法抵御能量分析攻击, 提出了一种改进的循环移位 S 盒掩码(RSM, rotating S -box masking)算法.该算法采用RSM掩码与固定值掩码相结合的方法, 结合SM4算法本身的加密特性, 不需要设计者对掩码进行人工操作, 就可以起到循环移位 S 盒的目的, 从而有效降低了功率消耗与中间值的关联性.安全性分析表明, 本方案可以有效抵御高阶差分能量分析(DPA)攻击, 是一个非常匹配SM4算法的掩码方案. To resist power analysis attack, this paper presents an improved RSM(rotating S -box masking) algorithm for encryption mask. This method combines RSM algorithm with fixed value mask. With the characteristics of SM4 algorithm itself, the method can play the cyclic shift of S -box without requiring manual operation of designer for the mask, so it effectively reduces the power consumption and the relevance of the intermediate values. The security's analysis proved that the method can effectively resist the higher order DPA attack and match the SM4 algorithm perfectly. SM4算法 侧信道攻击 循环移位 S 盒掩码 差分能量分析 S 盒 SM4 algorithm power analysis attack RSM(rotating S -box masking) DPA(differential power analysis) S -box 引言 1 随着信息安全在社会生活中的影响越来越大, 人们对信息安全的需求非常强烈.密码学作为研究信息安全的核心科学, 其应用与研究也越来越广泛和重要.SM4密码算法是我国于2006年公开发布的第一个商用分组密码算法, 随着我国密码算法标准化工作的开展, SM4在2012年3月被作为国家密码行业标准(标准号GB/T 32907-2016), 得到了广泛的应用.然而近年来, 能量分析攻击的出现 [ 1 1 ] , 给该算法在智能卡等密码设备中的使用带来了严峻的挑战. 能量分析攻击即功耗攻击, 按照攻击者使用频率上可以分为:简单能量分析攻击(simple power analysis attack)、差分能量分析攻击(DPA，differential power analysis attack) [ 2 2 ] 和相关系数能量分析攻击(correlation power analysis attack) [ 3 3 ] .差分能量分析和相关系数能量分析需要的硬件资源非常小, 不需要对加密算法有具体的了解, 甚至只需要知道算法的名称即可, 非常有效.本质上, 这类攻击利用了两类能量消耗依赖性：数据依赖性和操作依赖性 [ 4 4 ] .2009年, Bai等 [ 5 5 ] 针对SM4算法的能量分析攻击结果表明DPA攻击对SM4算法的有效.掩码技术是抵抗DPA攻击有效方法.2013年Tan等 [ 6 6 ] 在Bai等的研究基础上, 提出了一种针对SM4的多路径乘法掩码的方法.该方法在保证密钥扩展运算过程中的数据被随机掩码的同时, 也保证了加密过程中的所有数据均被随机掩码, 达到了抵御DPA攻击的目的.但该方法在设计需要时增加了算法和电路设计的复杂度.本文提出了一种改进的循环移位 S 盒掩码(RSM, rotating S -box masking)算法, 结合SM4算法本身的加密特性, 不需要设计者对掩码进行人工操作, 就可以起到循环移位 S 盒的目的. SM4算法 1 SM4算法采用非平衡的Feistel结构, 分组长度和密钥长度均为128 bit, 加密算法与密钥拓展算法都采用了32轮非线性迭代结构, 加密过程中的轮函数主要是由异或运算, S 盒查表以及循环左移构成.解密算法和加密算法的结构相同.其具体加密流程如 图 1 图 1 所示. 加解密算法 2 设明文输入为( X 0 , X 1 , X 2 , X 3 )∈( Z 2 32 ) 4 , 密文输出为( Y 0 , Y 1 , Y 2 , Y 3 )∈( Z 2 32 ) 4 ，轮密钥为rk i ∈ Z 2 32 , i =0, 1, …, 31.具体运算过程如下: 1) 首先执行32次迭代运算 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258418&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258418&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258418&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258423&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258423&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258423&type=middle 其中, i =0, 1, …, 31, F 为轮函数, T 为合成变换, 由一个非线性变换 τ 和一个线性变换组成, 即 T (·)= L ( τ (·)).非线性变换 τ 由4个并行的8 bit输入输出的 S 盒组成, 用Sbox(·)表示.设输入 A =( a 0 , a 1 , a 2 , a 3 )∈( Z 2 8 ) 4 , 输出用 B 表示, 记为 B =( b 0 , b 1 , b 2 , b 3 )∈( Z 2 8 ) 4 , 则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258428&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258428&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258428&type=middle 非线性变换 τ 的输出是线性变换 L 的输入.设输入( Y 0 , Y 1 , Y 2 , Y 3 )= R ( X 32 , X 33 , X 34 , X 35 )=( X 35 , X 34 , X 33 , X 32 ), B ∈ Z 2 32 , 输出为 C ∈ Z 2 32 , 则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258436&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258436&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258436&type=middle 其中， B ＜＜＜ i 表示将 B 循环左移 i 位. 2) 对最后一轮进行反序变换得到密文输出: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258440&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258440&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258440&type=middle 密钥扩展算法 2 SM4算法加解密轮密钥由密钥扩展算法生成, 设密钥MK, 则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258441&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258441&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258441&type=middle 轮密钥生成算法为： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258451&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258451&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258451&type=middle 其中： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258462&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258462&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258462&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258469&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258469&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258469&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258475&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258475&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258475&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258484&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258484&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258484&type=middle T ′是将合成置换 T 的线性变换 L 替换为 L ′: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258492&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258492&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258492&type=middle FK i 为系统参数, CK i 为固定参数, 都是算法本身定义的常量.通过加密流程图结合能量分析攻击的本质可以得出在SM4加密算法过程中存在以下几个潜在攻击点, 分别是 S 盒输入, S 盒输出, 经过线性变换 L 后的输出. 掩码方法 1 本节首先对实测功耗和关键数据建立的重要模型和掩码技术进行介绍, 其次提出自己相关的掩码方案并对其可行性进行分析, 从而得出结论. 汉明模型 2 在能量分析攻击中, 通常必须要将操作数映射为能量消耗值, 而汉明模型就是在功耗分析中, 将实测功耗与关键数据建立一一映射的重要模型之一 [ 7 7 ] .具体又可以分为汉明距离模型和汉明重量模型. 汉明距离模型 3 在信息论中, 汉明距离定义为两个比特串对应比特间异或相加的结果. http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258498&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258498&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258498&type=middle 为了提高攻击效率我们假设从比特“1”到比特“0”跳变产生的功率和从比特“0”到比特“1”跳变产生的功率相同, 因此和数据相关比特串的汉明距离可以用一个线性模型表示： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258508&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258508&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258508&type=middle P 表示一个比特串在寄存器运算后产生的功耗, a 表示与寄存器本身相关的常数, b 表示与比特串无关的噪声和静态功耗的总和.通过该式可以将实测功耗与密钥对应起来. 汉明重量模型 3 汉明重量模型比汉明距离模型更简单.攻击者只需要考虑某一时刻寄存器中 S 1 比特串中“1”的个数.直观的认为功耗的大小与 S 1 的汉明重量有线性关系, 公式如下： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258516&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258516&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258516&type=middle 当 S 0 取值全为0时, 汉明距离模型就转化为汉明重量模型, 使问题简单化. 掩码技术 2 通过测量功耗, 并利用相应的模型可以很容易的将中间值测量出来, 这就对密码设备构成了严重的威胁.掩码技术是随之而产生的抵御能量攻击分析的一种方法. 掩码技术的核心思想就是随机化密码设备所处理的中间值 [ 8 8 ] , 这种方法的动机是处理被随机化后的中间值所需要的能量消耗与处理实际中间值所需要的能量消耗之间相互独立.需要注意的是, 掩码在算法开始前添加, 在算法结束时要通过相应的操作消除.整个掩码的过程是无法感知的, 由于添加了掩码, 使得算法在加密过程中泄露的功耗信息不再与密钥有很强的关联性, 因此能够抵御能量分析攻击. 改进RSM掩码算法 2 RSM方案全称为循环 S 盒掩码方案(rotating S -box masking) [ 9 9 ] , 是目前在智能卡等加密外设防护应用中讨论最多的掩码方案之一.改进的RSM方案结合了SM4算法本身特性, 具体步骤如下. 随机掩码的生成 3 以汉明重量为随机种子, 对每个32 bit的掩码值可能的汉明重量取值范围是[0, 32], 生成步骤如下. 步骤1   确定掩码的个数 n . 步骤2   以[0, 32]为种子, 随机生成 n 个不同汉明重量值HW i , HW i ∈[0, 8]. 步骤3   根据HW i 的取值以此来确定掩码中比特1的个数, 其位置随意放置, 生成具体的32 bit掩码值 m i . 步骤4   重复步骤3, 直至 n 个32 bit的掩码值全部生成. 图 2 图 2 展示了从开始到随机掩码生成的流程图, 从图中可以看出掩码的生成以汉明重量值为随机种子, 增大了掩码的随机性, 同时添加偏移量增加了初始掩码选取的随机性, 相较于其他掩码方案的选取更趋于均匀化, 这样就增加了掩码的复杂性, 从而起到很好的防护作用. 掩码过程 3 1) 从2.3.1中随机选取8个掩码常量, 记为 m 0 , …, m 7 , 对于算法的前4轮加密过程均使用这8个掩码变换得到. 2) 根据子密钥和掩码的取值重新计算8个新的 S 盒, 将他们记为 S 0-7 ′( x ′), 并使其满足 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258529&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258529&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258529&type=middle 其中 s i 表示掩码的偏移量, 共8个, 在算法行前随机产生, 且位置随机, 满足均匀分布, 分别记为 s 0 , s 1 , …， s 7 .根据随机选取的掩码值以及已知的信息, 可以事先将新的 S 盒 S 0 ′，…， S 7 ′计算出来, 并存储于ROM中, 这样可以增加算法运行的效率. S 盒的输出是线性运算 L 的输入, 为了使输出结果不变同时又不能暴露中间值, 此时运算 L 的输出进行掩码, 其掩码结果为： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258535&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258535&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258535&type=middle 最后线性运算的输出值 T 再与 X i 和 m i 进行异或, 不但还原出了真实值, 同时又对中间值进行了掩码, 改变了初始值, 起到了防护作用.而中间24轮则采用固定掩码值方案 [ 10 10 ] , 即从 n 个32 bit的掩码中随机选取24个, 结合明文及轮密钥相关信息, 求出相应的 S 4 ′，…， S 27 ′盒并存储于ROM中, 最后4轮加密与初始4轮加密方法相同.其具体流程图如 图 3 图 3 所示. 在软件密码系统, 所有的中间值都会存储在寄存器中, 如果对所有的中间值进行防护, 算法的运行效率必然下降.从DPA竞赛平台的众多实际攻击案例中可以看出, 能量分析攻击主要集中在第一轮和最后一轮上, 因为此时攻击者可以从明文输入或密文输出建立相应的功耗假设模型, 由于此时密钥与功耗之间的相关性是最强, 所以攻击成功率最高.因此, 从算法运行的效率角度考虑, 没有必要对所有中间值添加掩码, 这也是为什么本文只对SM4算法前4轮进行掩码的原因. 通过分析SM4算法也可以看出, 由于其算法固有的特点, 我们只需在第一轮随机选出8个32位的掩码对输入的明文进行异或, 就可以达到循环移位 S 盒的目的, 从而提高了算法的运行效率. 安全性分析 1 DPA攻击的实质就是利用中间结果与密钥之间的关联性进行攻击, 本文设计的方案对所有可能保存在寄存器中的中间值进行了掩码, 改变原有的中间结果.因此只要证明上述二者之间不存在关联, 即可有效抵御DPA攻击. 设 x 为随机变量, 中间值为 y , 对 y 进行掩码得到 y ′= y ⊕ x .根据文献[ 11 11 ]的引理1和引理2可知, y ′的概率分布与密钥无关, 因此本文掩码方案可抗一阶DPA攻击; 同理对于多个中间值结果, 根据文献[ 10 10 ]的引理3可知, 经过随机量掩码过后的中间值均服从均匀分布, 并且具有相互独立性.同时满足: http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258546&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258546&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4258546&type=middle 其中 α 1 ′, α 2 ′，…， α n ′是 y 1 ′, y 2 ′，…， y n ′的任意取值, N 是变量的最大值.从上式可以证明 n 个( n > 1)被掩码的中间值的联合概率分布与密钥无关.由以上分析可知, 若一个掩码方案的 n 个中间值 y 1 ′, y 2 ′，…， y n ′, 其中的一个概率分布与密钥无关, 则其联合概率分布也与密钥无关, 因此该方案可以抵御一阶DPA和高阶DPA攻击. 为进一步验证本方案的正确性, 使用差分功耗分析平台进行实验.得到如 图 4 图 4 和 图 5 图 5 所示的实验结果.通过差分功耗图对比可知, 加入本方案掩码的SM4算法差分功耗曲线, 在特定区域内没有出现明显峰值, 导致DPA攻击失效, 提高了密码实现的安全性. 结论 1 本文通过对国家标准SM4加密算法进行分析, 提出了一种抵抗能量分析攻击改进的RSM掩码方案.该方案结合SM4算法本身的特点, 同时以汉明重量为随机种子生成掩码, 并添加偏移量对密钥扩展和加解密过程中的所有中间值进行掩盖, 消除了数据与操作的相关性.从算法的运行效率角度考虑, 对SM4算法前4轮和后4轮采用循环掩码, 中间24轮采用固定掩码的方法, 不但达到抵御能量分析攻击的目的, 同时提高了效率.最后通过安全性分析得出该方案能够抵御一阶, 甚至高阶DPA攻击. 参考文献 KOCHER P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C]// Advances in Cryptology—CRYPTO '96. Berlin: Springer-Verlag, 1996: 104-113. KOCHER P, JAFFE J, JUN B. Differential power analysis[C]// Advances in Cryptology—CRYPTO '99. Berlin: Springer, 1999: 388-397. http://dx.doi.org /10.1007/3-540-48405-1_25 http://dx.doi.org/10.1007/3-540-48405-1_25 . BRIER E, CLAVIER C, OLIVIER F. Correlation power analysis with a leakage model[C]// Cryptographic Hardware and Embedded Systems-CHES 2004. Berlin: Springer, 2004: 16-29. http://dx.doi.org /10.1007/978-3-540-28632-5_2 http://dx.doi.org/10.1007/978-3-540-28632-5_2 . MANGARD S, OSWALD E, POPP T, et al . Power Analysis Attacks [M]. New York:Springer, 2008. BAI X F, GUO L, XU Y H, et al. Research on differential power analysis attack on SM4 algorithm[J]. Journal of Chinese Computer Systems , 2009, 30 (3): 541-544. TAN R N, LU YY, TIAN J L. SM4 muti-path multiplicative masking method against side-channel attack[J]. Computer Engineering , 2014, 40 (5): 130-108. 罗鹏, 冯登国, 周永彬.功耗分析攻击中的功耗与数据相关性模型[J].通信学报, 2012, 33 :276-281. LUO P, FENG D G, ZHOU Y B. Power model in power analysis attack[J]. Journal on Communications , 2012, 33 :276-281(Ch). CHEN Z, ZHOU Y. Dual-rail random switching logic: A Countermeasure to Reduce Side Channel Leakage[C]// Cryptographic Hardware and Embedded Systems-CHES 2006. Berlin : Springer, 2006: 242-254. WANG D H, WANG A, ZHENG X X. Fault-tolerant linear collision attack: A combination with correlation power analysis[C]// ISPEC 2014 Proceedings of the 10th International Conference on Information Security Practice and Experience . New York: Springer-Verlag, 2014: 232-246. DOI: 10.1007/978-3-319-06320-1_18 http://dx.doi.org/10.1007/978-3-319-06320-1_18 . GANDOLFI K, MOURTEL C, OLIVIER F. Electromagnetic analysis: Concrete results[C]// International Workshop on Cryptographic Hardware and Embedded Systems . Berlin : Springer, 2001: 251-261. 童元满, 王志英, 戴葵, 等.一种抗DPA及HO-DPA攻击的AES算法实现技术[J].计算机研究与发展, 2009, 46 (3):377-383. TONG Y M, WANG Z Y, DAI K, et al . A DPA and HO-DPA resistant implementation of AES[J]. Journal of Computer Research and Development , 2009, 46 (3):377-383(Ch). 10.14188/j.1671-8836.2018.02.012 TP309 whdxxblxb-64-2-183 国家自然科学基金资助项目(U1636114, 61572521);陕西省自然科学基础研究计划(2016JQ6037)资助项目 2017-08-07 2018-04-24 2020-11-30 版权所有© 2018 《武汉大学学报(理学版)》编辑部 Copyright © 2018 Journal of Wuhan University(Natural Science Edition). All rights reserved. 2018 武汉大学学报(理学版) 2 64