1、技术应用DOl:10.12379/j.issn.2096-1057.2023.10.12TechnicalApplications针对带DFA防护SM4的SIFA攻击谭子欣胡永波龚彦昊胡春雅张琪朱文锋(深圳市汇顶科技股份有限公司上海分公司脆弱性分析实验室上海2 0 12 10)()SIFA Attack Against SM4 with DFA Protection龚子超Tan Zixin,Hu Yongbo,Gong Yanhao,Hu Chunya,Zhang Qi,Zhu Wenfeng,and Gong Zichao(Laboratory of Vulnerability Analys
2、is,Shenzhen Huiding Technology Co.,Ltd.Formula Shanghai Branch,Shanghai201210)Abstractt As a national standard block cipher algorithm issued by State CryptographyAdministration(SCA),SM4 is widely used in domestic security products,such as financial ICcard,blockchain,encryption card,router,electronic
3、 wallet,electronic ID card and otherapplications.Its security has always been concerned by various industries,with the continuousinnovation of attack methods,carious SM4 implementation schemes with countermeasure have alsobeen proposed.We proposed a statistical ineffectual fault analysis(SIFA)attack
4、 on SM4 withdifferential fault analysis(DFA)countermeasure firstly inspired by the idea of SIFA proposed byChristoph et al.in 2018,and this attack can recover the key of SM4 with the computationalcomplexity of 234.Then,we had successfully recovered the key on the STM32F103C8T6 micro-controller with
5、voltage glitch fault injection.Finally,we further improved this attack by chosenplaintext,and reduced the computational complexity to 212.Key words SM4;SIFA;DFA protection;voltage glitch fault injection;chosen plaintext摘要SM4算法作为中国密码管理局(SCA)发布的一项国家标准分组密码算法,当前被广泛应用到国内市场的安全产品中,如金融IC卡、区块链、加密卡、路由器、电子钱包以及
6、电子身份证等.其安全性一直受各业界所关注,随着攻击方法不断的革新,各类带有防护的SM4实现方案也被提出。基于2 0 18 年Christoph等人提出的统计无效错误分析(SIFA)的思想,首次针对带差分错误分析(DFA)防护的SM4算法,提出了一套统计无效错误分析攻击方案,该攻击方案能以2 34的计算复杂度破解出SM4的密钥.然后,在单片机STM32F103C8T6上利用电压毛刺故障注入成功还原密钥,最后在该攻击的基础上进一步改进,利用选择明文的策略能将计算复杂度降低至2 12.关键词SM4;统计无效错误分析;差分错误分析防护;电压毛刺故障注入;选择明文中图法分类号TP309收稿日期:2 0
7、2 2-0 9-2 0通信作者:胡永波()引用格式:谭子欣,胡永波,龚彦昊,等.针对带DFA防护SM4的SIFA攻击J.信息安全研究,2 0 2 3,9(10):10 15-10 2 2网址http:/11015信息安全研究第9 卷第10 期2 0 2 3年10 月Journalotimformation Securty BesearchVol.9No.10Oct.2023自1997 年Boneh等人1在RSA算法上成功实现了故障注人攻击并破解密钥之后,故障注入攻击在密码学领域以势如破竹之势迅猛发展.故障注入后的输出分为2 种类型:一种是有效错误,攻击者可利用这种错误计算结果进行差分故障分析2
8、 、碰撞故障分析(collision fault analysis,CFA)3、统计故障攻击(statistical fault attack,SFA)4、故障敏感性分析(fault sensitivity analysis,FSA)5以及差分错误强度分析(differential fault intensityanalysis,D FIA)6 1等一系列分析手段.另一种是故障未能影响输出结果,攻击者无法直接利用,通常称之为无效错误.针对有效错误的故障注入防护方案通常有余防护7 以及传染防护8 .九余防护主要用于对称算法和非对称算法,传染防护主要用于对称算法。穴余防护即重复进行1次或多次密码计
9、算,再将每次计算结果进行比对,仅当比对正确才将运算结果输出.传染防护即利用伪计算和亢余计算混淆至真实的轮运算中,当有故障注人到密码算法的计算中时,产生的错误将会逐轮次地传递下去,以保证密码算法无法输出对攻击者有效的错误输出,即有效错误.虽然传染防护可以避开单次输出检查防护所遇到的跳过检查的问题,但也需要通过检查输出保证密码算法正常的功能,以供用户使用.在以硬件实现密码算法的实际安全产品中,由于传染防护方案相对于输出检查防护方案增加了更多的逻辑布线,出于对算法实现开销的权衡,多采用穴余防护方案。目前对于余防护方案的有效攻击方式有IFA和SIFA.IFA在2 0 0 7 年由ClavierL9首次
10、提出,该方案的创造性主要在于可以无需有效错误即可还原DES的密钥,同时还可以避开输出检查防护,但IFA需要故障注入精准到指令级别,使最后轮次的中间值产生固定错误,此类攻击方案对于故障注入的技术要求较高,依赖于特定的故障模型(如置0 模型等),不易于实现.2 0 18 年,Dobraunig等人10 提出了比IFA方案更加便于实现的SIFA方案,其不需要指定的故障模型,只要求输出结果与注人故障的中间值之间存在依赖关系,该方案分别对带穴余防护方案的AES算法和带传染防护的AES算法成功实现了SIFA攻击.SIFA方案除了无效错误相关的密文或明文,无需攻击者更10161多信息,因此在现实攻击中具有较
11、强的实用性。对于SM4算法11,由于其本身是抗差分分析和线性分析的,所以目前比较有效的攻击手段主要是差分故障分析.如2 0 0 6 年Zhang等人12 首次提出的对SM4的差分故障分析,仅通过约47 条错误密文就能恢复12 8 b种子密钥;2 0 11年Li等人13 提出了一种基于单字节错误模型的DFA方案,其恢复出12 8 b种子密钥的平均计算复杂度只需要2 2.11;2 0 19年,朱仁杰14针对SM4算法提出了一种扩大故障注人范围DFA方案,其破解出128b种子密钥的计算复杂度甚至可以降低至2 1;2020年金雨旋等人15】提出了一种基于单比特故障模型的DFA方案,其恢复12 8 b种
12、子密钥的平均计算复杂度为2 15.352 6.以上攻击方案都是针对没有防护的SM4算法,一旦带有穴余防护等DFA防护(即有效错误防护)之后,DFA分析便难以开展,所以为了对抗DFA防护,本文基于文献10 的SIFA思想,对带DFA防护方案的SM4算法展开研究.本文的主要贡献为:首次针对SM4提出了一套抵抗DFA防护的随机明文SIFA方案,并以234的计算复杂度完成了对12 8 b种子密钥的破解,同时给出了另外一套选择明文SIFA方案,该方案能够将攻破种子密钥的计算复杂度降低至2 1,从计算效率上优于大部分针对无防护SM4的DFA方案.1预备知识1.1带带余防护的SM4方案SM4是一种分组为12
13、 8 b长度、密钥为12 8 b长度的分组密码,由于SM4是对称结构,其加密过程和解密流程共用一个结构.在安全产品的实际应用中,为了有效防止SM4遭受DFA攻击,最常见的做法是通过穴余保护阻止有效错误结果的输出,本文所使用的带穴余防护的SM4算法如下所示:算法1.带穴余防护的SM4算法.输人:P,K;输出:C=SM4ENc(P,K).计算 C-SM4ENc(P,K);计算 P-SM4DEc(C,K);如果P=P,则输出C,否则生成随机数r并输出r.技术应用.TechnicalApplications1.2带统计无效错误分析SIFA的主要思想是通过故障注入,使得原本分布均匀的中间值变得不均匀,然
14、后利用分布不均匀的中间值变量对真实轮密钥的偏向性,即受影响的中间值状态位对轮密钥位具有非线性依赖关系,同时其他错误密钥推导出的错误中间值会呈现出均匀的分布,再利用SEI或者CHI计算出非均匀分布与均匀分布之间的距离,从而区分出真实的密钥.本文采用SEI来区分非均匀分布与均匀分布的偏差,当X=(;ieo n-1,X 的SEI计算公式如下所示:255(#(i|;=,i E 0,n-1)8-0其中#(il;=,iEo,n 一1)表示集合X中;=的个数.2针对带穴余防护SM4算法的SIFAXoYSEI(X)=21n256XX2YYS变换L变换XS变换L变换Yrskorski激光注入位置本节将详细介绍对
15、带余防护SM4算法的SIFA实现,首先介绍基于随机明文的SIFA方案,然后再介绍为了降低攻击复杂度而设计的选择明文SIFA方案.2.1基于随机明文的SIFA2.1.1算法原理在本文的攻击方案设计中,选择带穴余防护SM4算法(算法1)的步骤(详见1.1节)作为攻击目标,对其第2 轮中S非线性变换注人故障,图1展示了本文进行故障注人的具体位置.本文提出的统计无效错误注入攻击的原理是在第2 轮非线性S变换时注入错误,从而导致第2轮非线性S变换的输出结果souti存在偏差,即souti呈现出非均匀分布.因此,整个SM4的计算可以用C=SM4ENc(P,K,f a u l t)模型表示,在没有故障fau
16、lt引人的情况下,非线性S变换的输出souti符合均匀分布.假设故障fault导致sout1呈现出一个非均匀的分布,在这种错误模型假设下,若一共进行n次固定密钥K的加密,这n次加密的随机明文集合记为Psum=(p;l i EO,n),密文集合记为Csum=(c;l i EO,n).由于带穴余防护的SM4算法包含了对差分错误注入的防护,图1SM4前2 轮算法框图因此 SM4 在故障注人的过程中将会筛查掉所有错误的密文,同时仅会输出正确的密文.当SM4成功输出m条密文,令输出的密文集合为Cgot=(cgot;liEo,m),其对应的明文集合为Pgot=(pgot;liEo,m),对应的第2 轮S变
17、换的输出集合为Sout=(souti,1liEo,m),其中souti.i表示第i条明文对应的第2 轮中非线性S变换的输出.假如Sout呈现出非均匀分布,由于S是非线性转换,那么第2 轮S变换的输人Sin也会呈现出非均匀分布,其中Sin=(s i n i,1|s i n i,1=S-1(s o u t i,1),iEO,m】,s i n i.1为第i条明文对应的第2 轮非线性S变换的输人,S-1表示S变换的逆变换,又由于rski是固定值,故而中间值temp=Sinrski=YiY2Y:也会呈现出非均匀分布.当使用错误的候选轮密钥rsk,对Pgot计算temp=YiY2Ys,其中 Y=L(S(X
18、iX 2 X:r s k),由于X1,X2,X3,Yi,Y,r s k。都服从均匀分布,故而temp也会呈现出均匀分布.当使用正确的候选轮密钥rsk。计算 temp=YiYz L(S(X i X,网址http:/ 1 1017信息安全研究第9 卷第10 期2 0 2 3 年10 月Journalot lmformation Security BesearchVol.9No.10Oct.2023X:?r s k。),就可以得到非均匀的分布.所有只要50对3 2 b的rsk。进行2 3 2 遍历猜测,再通过计算SEI区分出偏离均匀分布最大的非均匀分布,即可得到正确的轮密钥rsk。.为了计算出最大的
19、SEI值,需要计算出候选temp中每个字节所对应的SEI值,得到4组m(2 3 2 一1)的矩阵,再找出其中最大SEI值所对应的候选轮密钥,即找到真实轮密钥rsko,为此本文设计攻击算法如下:算法2.攻击算法A.输人:明文集合Pgot=(P.)(i E0.3),其中P;表示Pgot中的第i字节组成的数据集;输出:seimax,r s k.初始化seimax=0,rsk=0,kguss=0;计算 temp=P2P:L(S(PiP2 Pk guess);计算 sei;=SEI(t e m p j),其中jEo,3,t e m p Li 表示temp中的第i字节组成的数据集;若(sei;hieo.3
20、中存在seiseimax,则seimax=seik,rsk=kguess;?计算kguess=kguess+1;当kguessE0,232-1,返回步骤,否则进入步骤;输出seimax和rsk.在获得rsk。之后,采用同样的方式分别对第35轮的S变换进行故障注入,然后相继将rsk1,r s k 2,r s k 3 解析出来,最后根据密钥扩展算法的流程,逆向推导出种子密钥K,故基于随机明文的SIFA方案的计算复杂度为2 3 4.2.1.2仿真实验本文设计仿真实验如下:先设置密钥K=0 x676F6F6469787661747261696E696E67,其首轮轮密钥为0 x8A443F8C,然后随
21、机生成1万条仿真明文数据M,再计算这些明文对应的中间值temp.为了构造出非均匀分布的temp集合,选择所有temp0,:JE(50,2 0 0)(即temp的第0 字节的数值在50 2 0 0 之间)对应的明文组成新的明文集M,M所对应的中间值为temp,经过筛选后M剩余550 0 条明文.图2 展示了temp第0 字节分布与temp第0 字节分布的对比图,其中图2(a)对应temp的第0 字节分布,图2(b)对应temp的第0 字节分布.1018140F30上20F10F00504030/鲁2010F00图2 第0 字节分布对比图然后将M输人到算法2 中,计算出所有候选密钥所对应的SEI值
22、,由于候选密钥的范围较大,不宜在图中完整展示,故而本文选择了候选密钥范围为0 x8A4300000 x 8 A 46 FFFF,横坐标共计196603个候选值,具体如图3 所示,发现轮密钥0 x8A443F8C所对应的SEI值高于其他错误轮0.081 50.08100.08050.08000.07950.079 00.078 50图3 部分SEI-候选密钥对应图50(a)temp的第0 字节的分布50100temp的第0 字节(b)temp的第0 字节的分布50000100000候选密钥100temp的第0 字节150150000150200200250250200000技术应用Technic
23、alApplications密钥对应的SEI值,因此得出真实的轮密钥为0 x8A443F8C.2.1.3基于STM32F103CT6的实际攻击为了检验实际攻击的有效性,本文首先按照触发信号0VCC1al2a23STM32F103CT6a34a4正常工作电压为3.3 V毛刺电压配置为0 V,随机毛刺脉宽配置为50 0 550 ns,电压毛刺的触发信号设在SM4第2 轮轮计算开始位置.为了能让故障发生在S变换时间区域,配置毛刺延迟约为6 3 0 ns,通过电压毛刺造成的瞬时掉电使得S变换功能紊乱,从而引人故障.首先将SM4的密钥配置成固定形式,如K=0 x676F6F646978766174726
24、1696E696E67,然后传入2 0 0 0 条随机明文数据,在电压毛刺的故障注人下,有17 99条数据由于触发余防护而输出随机数,剩余2 0 1条由于未触发余防护或者故障注入未成功而返回正常密文.将这2 0 1条明文输入到算法2,可以计算出所有候选密钥对应的SEI值,图5展示了候选密钥范围在0 x8A4300000 x 8 A 46 FFFF的SEI值.其中0 x8A443F8C所对应的SEI值最大,故而得到候选轮密钥0 x8A443F8C为真实轮密钥.0.080.070.060.050.041.1节中的设计,将带穴余防护的SM4在keil软件通过C语言实现后,将其下载至单片机STM32F
25、103CT6中,然后基于电压毛刺故障注人平台搭建环境,平台连接示意如图4所示:5b16b2b38GNDb40州VCCGND10图4电压毛刺故障注入平台连接示意图间值temp,发现temp呈现出单字节分布不均匀的特征,其中图6(a)中展示的第0 字节分布表现出的不均匀特性尤为明显.17.515.012.510.07.55.02.500(a))实际攻击中temp的第0 字节的分布54321指令下发与数据回发故障注入设备随后用真实轮密钥和这2 0 1条明文计算出中50100temp的第O字节计算机1502002500.030图5在实际攻击中部分SEI-候选密钥对应图050000100000候选密钥1
26、50000200.0000(b)实际攻击中temp的第1字节的分布网址http:/1 101950100temp的第1字节150200250信息安全研究第9 卷第10 期2 0 2 3 年10 月Journalot lmformation Security BesearchVol.9No.10Oct.2023然后可以得到4.03.53.02.52.01.51.00.500(c)实际攻击中temp的第2 字节的分布4.03.53.02.52.01.51.00.500(d)实际攻击中temp的第3 字节的分布图6 实际攻击后temp的字节分布图2.2基于选择明文的SIFA2.1节所介绍的攻击需要对
27、rsk。猜测2 3 2 次,因此实现攻击的计算量非常大,本节提出一种选择明文攻击方式能够降低攻击的运算量,由于K。是一个固定值,而且X1X 2 X:r s k。是一个32b的中间值,因此要计算出L(S(Xi?X2?X:?rsk。)),需要猜测3 2 b的密钥,当把XiX 2?X 3?rsk。表示为4个独立的字节(to,t i,t 2,t 3),有L(S(XiX 2 X:rsk o)=L(S(to,t1,t2,t3)=L(Sto24)L(St16)L(St2 8)L(St:).假设能使t1t 3 固定成任意常数,即固定明文XiX 2 X:的第13 字节为常数,则L(St i16)L(St2 8)
28、L(St3)=,为常数,故而L(S(XiX,X r s k。)=L(S(to)O,10201YiOY,OL(S(X,OXOX:rsk。)=YiY2 L(S(to)2 4).此时要得到中间值temp=Yi?Y2L(S(t o)24),只需计算L(S(t。)2 4),而计算 to只需要遍历rsk。的高8 b即可,即遍历rsk。o.当SM4算法输人选择明文集合后,SM4算法的第2 轮非线性S变换经过故障注人返回的一系列正常密文,对应的明文集合为Pgot。50100temp的第2 字节50100temp的第3 字节150150200200250250算法3.攻击算法B.输人:明文Pgot=(P,lie
29、0.3,bytenum,其中P,表示Pgot中第i字节组成的数据集;输出:seimax,r s k _ b y t e n u m.初始化seimax=0,rsk_bytenum=0,t=0;若bytenum=0,令e=S(t)24;若bytenum=1,令e=S(t)16;若bytenum=2,令e=S(t)seimax,则seimax=sei;,rsk_bytenum=t;计算t=t+1;若tE0,28一1,返回步骤,否则进人下一步;输出seimax和rsk_bytenum.令rsk。=(r s k。o,r s k。1,r s k。2,r s k o3),选择明文M。=(=(o,p 1,p
30、 2,p s ),pip 2 p 的第1,2,3 字节固定成任意常数,经过故障注人后获取到明文集合M。,满足M。二M。,然后将(M。,0)输人至算法3,通过遍历8 b的候选值,找出中间值temp的最大SEI值,便可得出真实的rsk。o,接着继续获取到rsk。1,r s k。2,rsk。3.同理,用同样的方法分别攻击第3 5轮的S变换,直到破解出rsk1,r s k 2,r s k 3,最后再通过密钥扩展的逆运算获取种子私钥K.因此,本节方法可以将计算复杂度降低至2 12.本文提出的SIFA攻击方案不仅可以抵御DFA防护,选择明文SIFA方案在效率上甚至优技术应用.TechnicalApplic
31、ations于现有大部分针对无防护SM4的攻击方案,具体如表1所示:表1本文方案与现有方案对比情况方案攻击类型计算复杂度SM4防护情况文献13 DFA文献14DFA文献15DFA随机明文SIFA(本文)SIFA选择明文SIFA(本文)SIFA3 结 语本文首次提出了一套针对带DFA防护SM4的SIFA方案,并通过仿真进行了实验验证.同时,本文针对带余防护的SM4算法,在单片机STM32F103CT6上成功破解了密钥,计算复杂度为2 3 4.实验证明,只需要少量的带有无效错误的密文所对应的明文,便可实施攻击.另外还提出了一套基于选择明文的 SIFA方案,能够将计算复杂度降低至2 1,从计算效率上
32、优于目前大多数针对无防护SM4的DFA方案.本文提出的针对SM4的SIFA攻击方案同样可以应用于带掩码防护的SM4方案以及带传染防护的SM4方案.对于带掩码防护的方案,攻击者需要对第2 轮S变换进行注错,导致sout1的2 条掩码数据发生无效错误,使得正确密文所对应的真实sout1依旧呈现出不均匀分布,攻击者通过重复加密过滤出正确的密文,再将正确密文带入本文提出的随机明文SIFA方案,破解出首轮的轮密钥,直至破解出SM4的完整密钥.而对于带传染防护的SM4方案,只需要通过重复加密过滤出带有无效错误的正确密文即可.通过验证,也更加证实了SIFA策略对于带DFA防护的对称算法方案存在较大威胁,但从
33、文献10 的结果与本文的实践不难看出,SIFA策略对于攻击的时间位置依旧存在较大的依赖性,因为随着无效错误在正常密文中的比重减少,目标中间值的分布也将趋近于均匀分布,故给密码算法增加随机延迟防护或添加伪计算防护可以很好地提高SIFA攻击难度,从攻击复杂度上削弱SIFA的效率.参考文献1 Boneh D,DeMillo,R A,Lipton R J.On the importance ofchecking cryptographic protocols for faults C/Proc of22.11无210无215.35无234DFA防护212DFA防护Int Conf on the The
34、ory and Applications of CryptographicTechniques.Berlin:Springer,1997:37-512 Biham E,Shamir A.Differential fault analysis of secret keycryptosystems C/Proc of Annual Int Cryptology Conf.Berlin:Springer,1997:513-5253 Hemme L.A differential fault attack against early roundsof(T r ip le-)D ES C /Pr o c
35、o f I n t W o r k s h o p o nCryptographic Hardware and Embedded Systems.Berlin:Springer,2004:254-2674 Fuhr T,Jaulmes E,Lomne V,et al.Fault attacks on AESwith faulty ciphertexts only CJ/Proc of 2013 Workshopon Fault Diagnosis and Tolerance in Cryptography.Piscataway,NJ:IEEE,2013:108-1185 Li Y,Sakiya
36、ma K,Gomisawa S,et al.Fault sensitivityanalysis C/Proc of Int Workshop on CryptographicHardware and Embedded Systems.Berlin:Springer,2010:320-3346 Ghalaty N F,Yuce B,Taha M,et al.Differential faultintensity analysis C/Proc of 2014 Workshop on FaultDiagnosis and Tolerance in Cryptography.Piscataway,N
37、J:IEEE,2014:49-587 Bar-EI H,Choukri H,Naccache D,et al.The sorcerersapprentice guide to fault attacks JJ.Proceedings of theIEEE,2006,94(3):370-3828 G i e r l i c h s B,Sc h m i d t J M,T u n s t a l l M.I n f e c t i v ecomputation and dummy rounds:Fault protection for blockciphers without check-bef
38、ore-output CJ/Proc of Int confon cryptology and information security in Latin America.Berlin:Springer,2012:305-3219 Clavier C.Secret external encodings do not preventtransient fault analysis C /Pr o c o f C r y p t o g r a p h i cHardware and Embedded Systems.Berlin:Springer,2007:181-1941o Dobraunig
39、 C,Eichlseder M,Korak T,et al.SIFA:Exploiting ineffective fault inductions on symmetriccryptography JJ.IACR Trans on Cryptographic HardwareEmbedded System,2018,2018(3):547-57211吕述望,苏波展,王鹏,等.SM4分组密码算法综述J.信息安全研究,2 0 16,2(11):995-10 0 712 Zhang L,Wu W L.Dfferential fault analysis on SMS4 J.Chinese Jour
40、nal of Computers,2006,29(9):159613 Li R,Sun B,Li C,et al.Differential fault analysis onSMS4 using a single fault JJ.Information ProcessingLetters,2011,111(4):156-163网址http:/11021信息安全研究第9 卷第10 期2 0 2 3 年10 月Journalotimformation Security BesearchVol.9No.10Oct.202314朱仁杰.扩大故障注入范围的SM4差分故障攻击研究J.计算机科学,2 0
41、19,46(S2):493-50 615金雨璇,杨宏志,王相宾,等对SM4算法的改进差分故障攻击.密码学报,2 0 2 0,7(4):453-46 4谭子欣硕士,工程师.主要研究方向为理论密码学、零知识证明、侧信道攻击及故障注入分析。胡永波硕士,工程师.主要研究方向为侧信道分析与故障注入分析、逻辑分析、物理安全实现以及安全认证。龚彦昊硕士,工程师.主要研究方向为侧信道分析与故障注入分析胡春雅硕士,工程师.主要研究方向为理论密码学、零知识证明、侧信道分析以及故障注入分析。张琪硕士,工程师.主要研究方向为密码学、侧信道分析和故障注入分析。朱文锋硕士,工程师.主要研究方向为分组密码分析。龚子超硕士,工程师.主要研究方向为侧信道攻击与故障注入分析10221