一种抗差分计算分析的白盒SM4方案_原梓清.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(2):386396密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]一种抗差分计算分析的白盒 SM4 方案*原梓清1,陈 杰1,21.西安电子科技大学 通信工程学院,西安 7100712.河南省网络密码技术重点实验室,郑州 450001通信作者:陈杰,E-mail:摘要:研究白盒密码的设计与分析对于保证密码算法在实际应用场景下的安全性具有重要意义.本文发现白鲲鹏等人提出的白盒 SM4 方案存在安全性漏洞,采用 Bos 等人的差分计算分析方法,可以在 8 分钟内恢复出整个初始密钥.基于非线性编码改进了该方案,可以抵抗差分计算分析.改进后方案需要的内存空间为 34.5 MB,各种查找表的白盒多样性的最小值为 2568.8,各种查找表的白盒含混度的最小值为2148.4,有效抵抗 Bos 等人的差分计算分析、潘文伦等人的攻击、BGE 攻击、林-来攻击、De Mulder 等人的攻击、MGH 攻击以及 Lepoint 等人的攻击.关键词:白盒密码;白盒实现;SM4 算法;旁信道分析;差分计算分析中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000601中文引用格式:原梓清,陈杰.一种抗差分计算分析的白盒 SM4 方案J.密码学报,2023,10(2):386396.DOI:10.13868/ki.jcr.000601英文引用格式:YUAN Z Q,CHEN J.A white-box SM4 scheme against differential computation analysisJ.Journal of Cryptologic Research,2023,10(2):386396.DOI:10.13868/ki.jcr.000601A White-box SM4 Scheme Against Differential Computation AnalysisYUAN Zi-Qing1,CHEN Jie1,21.School of Telecommunications Engineering,Xidian University,Xian 710071,China2.Henan Key Laboratory of Network Cryptography Technology,Zhengzhou 450001,ChinaCorresponding author:CHEN Jie,E-mail:Abstract:Design and analysis of white-box cryptography are of great significance for ensuring thesecurity of cryptographic algorithms in practical implementations.This paper reveals the securityvulnerability of the white-box SM4 scheme proposed by Bai Kunpeng et al.,the entire initial key canbe recovered within 8 minutes by the differential computation analysis(DCA)method of Bos et al.In order to resist differential computation analysis for the white-box SM4 scheme of Bai Kunpeng etal.,this paper proposes an improved scheme based on nonlinear coding.In the proposed scheme,thememory space requirement is 34.5 MB,the minimum value of white-box diversity of various look-uptables is 2568.8,and the minimum value of white-box ambiguity of various look-up tables is 2148.4.Theproposed scheme can effectively resist the differential computation analysis of Bos et al.,the attack*基金项目:陕西省自然科学基金基础研究计划(2021JM-126);河南省网络密码技术重点实验室研究课题(LNCT2022-A08)Foundation:Basic Research Program of Natural Science Foundation of Shaanxi Province(2021JM-126);OpenProject of Henan Key Laboratory of Network Cryptography Technology(LNCT2022-A08)收稿日期:2022-01-24定稿日期:2023-01-20原梓清 等:一种抗差分计算分析的白盒 SM4 方案387of Pan Wenlun et al.,the BGE attack,the Lin-Lai attack,the attack of De Mulder et al.,the MGHattack and the attack of Lepoint et al.Key words:white-box cryptography;white-box implementation;SM4 algorithm;side channelanalysis;differential computation analysis1引言传统密码算法假设运行环境是安全的,攻击者只能获取密码算法的输入输出,而无法得知密码算法的内部细节,此时的攻击模型为黑盒攻击模型.随着信息技术的快速发展,计算机、智能手机与互联网已被广泛应用于生产生活中,软件、视频、图像、音乐等数字产品被广泛传播.在这种情况下,数字产品的运行环境不再单纯可信,传统密码算法的安全性假设不再成立.因此,文献 1 中提出了白盒攻击模型的概念.在白盒攻击模型中,攻击者对运行密码算法的终端具有完全的控制力,可以直接观测或更改密码算法运行时的内部细节.为确保密码算法在白盒攻击模型中仍具有安全性,进而解决数字版权管理问题,文献 1 中提出了白盒密码的概念.白盒密码采取查找表等技术对密钥进行了混淆,即使攻击者对运行密码算法的终端具有完全的控制力,也不能提取密钥.在文献 1 中,Chow 等人还提出了一种将已有密码算法白盒化处理的方法,即将原密码算法修改为嵌入密钥的查找表网络,并对每个查找表的输入输出以及整个查找表网络的输入输出用混淆编码进行保护.基于此,Chow 等人设计了一个 AES 的白盒实现方案1以及一个 DES 的白盒实现方案2.此后的白盒实现方案大多沿用 Chow 等人的设计思路37.对白盒实现方案的安全性分析,目前主要有两种思路:一种是在纯白盒环境下,通过对算法内部细节的安全性分析找到漏洞,并采用查找表组合、仿射等价算法等手段消除混淆编码,对密钥相关的查找表进行分析并提取密钥.这类分析方法的典型代表有 Billet 等人提出的 BGE 攻击8、Michiels 等人提出的 MGH 攻击9、De Mulder 等人对肖-来白盒 SM4 方案的攻击10以及林婷婷等人对史扬白盒 SM4 方案的攻击11.另一种对白盒实现方案的分析思路,是在灰盒环境下,利用某些软件采集算法程序运行时泄露的信息,并采用相应的统计分析方法提取密钥.这类方法属于旁信道分析方法,分析时不需要洞悉密码算法的内部细节,对现有的白盒实现方案具有更高的实际威胁.近年来,针对白盒实现方案的旁信道分析方法不断得到完善1220,如今该类分析方法已成为检验白盒实现方案安全性的重要工具.本文利用差分计算分析13对白-武白盒 SM4 方案6进行安全性分析.分析表明,白-武白盒 SM4方案不能抵抗 Bos 等人的差分计算分析.为此,本文基于文献 14 的理论,采用非线性编码对白-武白盒SM4 方案进行了改进.改进后的白盒 SM4 方案能够抵抗 Bos 等人的差分计算分析、潘文伦等人的攻击、BGE 攻击、林-来攻击、De Mulder 等人的攻击、MGH 攻击以及 Lepoint 等人的攻击.2白-武白盒 SM4 方案白-武白盒 SM4 方案6针对标准 SM4 算法21采用随机的仿射变换进行编码,并应用查找表保护算法运行时的内部信息.该方案引入了较多的随机量,并且设计了更加复杂的内部编码和解码过程,这大大增加了该方案的分析难度.白-武白盒 SM4 方案的实现过程如下22:(1)根据密钥扩展算法,由 128 位的初始密钥生成 32 个 32 位的轮密钥 k1,k2,k32.(2)生成随机矩阵与随机向量:首先,生成 32 阶随机可逆矩阵 P0,P1,P35,E1,E2,E32,F1,F2,F32以及 32 位随机向量 pi,pi,j,pr+3,j,pr+3,j,er,0,er,1,er,5,fr,0,fr,1,fr,5.其中,i=0,1,35,i=0,1,34,j=0,1,2,3,r=1,2,32.3j=0pi,j=pi,3j=0pr+3,j=pr+3,3j=0pr+3,j=pr+3,pr+3 pr+3=pr+3,Er=diag(Er,0,Er,1,Er,2,Er,3),Fr=diag(Fr,0,Fr,1,Fr,2,Fr,3).然后按照以下步骤生成 16 位随机向量 ur,i:(a)计算 er=5i=0er,i,fr=5i=0fr,i.388Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023(b)记 er=er,0er,1er,2er,3,fr=fr,0fr,1fr,2fr,3.(c)将 er,i,fr,i重组为 16 位向量 ur,i=er,ifr,i,其中 i=0,1,2,3,r=1,2,32.(3)用轮密钥、随机矩阵与随机向量生成查找表:第 r 轮,存储以下 16 个查找表(遍历 8 位的输入值 x 存储 32 位的输出值 y),具体过程可由式(1)式(7)表示.TCr,j:y=Pr+3(P1r1,j x P1r1 pr1,j)pr+3,j,j=0,1,2,3,(1)TAr,j:y=Er(P1r,j x P1r pr,j)er,j,j=0,1,(2)TAr,j+2:y=Er(P1r+1,j x P1r+1 pr+1,j)er,j+2,j=0,1,(3)TAr,j+4:y=Er(P1r+2,j x P1r+2 pr+2,j)er,j+4,j=0,1,(4)TBr,j:y=Fr(P1r,j+2 x P1r pr,j+2)fr,j,j=0,1,(5)TBr,j+2:y=Fr(P1r+1,j+2 x P1r+1 pr+1,j+2)fr,j+2,j=0,1,(6)TBr,j+4:y=Fr(P1r+2,j+2 x P1r+2 pr+2,j+2)fr,j+4,j=0,1.(7)遍历 16 位的输入值 x 存储 32 位的输出值 y 的 4 个查找表,可由式(8)表示.TDr,j:y=Pr+3 Mj S(E1r,jF1r,j)(x ur,j)kr,j)pr+3,j,(8)其中,r=1,2,32,j=0,1,2,3,(E1r,jF1r,j)是 8 16 矩阵,(E1r,jF1r,j)(x ur,j)表示将 16 位向量(x ur,j)的两个 8 位分量分别经过 E1r,j与 F1r,j解码后再将两解码后的值异或,S 表示 SM4 的 S 盒查表运算,Mj表示标准 SM4 的扩散矩阵 M 的 4 个 32 8 分块.(4)输入编码如式(9)所示:Xi=Pi Xi pi,i=0,1,2,3.(9)(5)加密:若记 r 为加密循环轮次,则加密过程包括如下(a)(e)共 5 步.(a)查 TA 表、TB 表、TC 表,对输入进行解码与编码:由 Xr1的 4 个 8 位分量分别查询查找表 TCr,0,TCr,1,TCr,2,TCr,3,得 cr,0,cr,1,cr,2,cr,3;由 Xr的 4 个 8 位分量分别查询查找表 TAr,0,TAr,1,TBr,0,TBr,1,得 ar,0,ar,1,br,0,br,1;由 Xr+1的 4 个 8 位分量分别查询查找表 TAr,2,TAr,3,TBr,2,TBr,3,得 ar,2,ar,3,br,2,br,3;由 Xr+2的 4 个 8 位分量分别查询查找表 TAr,4,TAr,5,TBr,4,TBr,5,得 ar,4,ar,5,br,4,br,5.(b)重组:计算 ar=5i=0ar,i,br=5i=0br,i.记 ar=r,0r,1r,2r,3,br=r,0r,1r,2r,3,将 r,i,r,i重组为 4 个 16 位的向量 yr,0,yr,1,yr,2,yr,3,其中 yr,i=r,ir,i,i=0,1,2,3.(c)查 TD 表,完成主要加密操作:根据 yr,0,yr,1,yr,2,yr,3,分别查询查找表 TDr,0,TDr,1,TDr,2,TDr,3,得 dr,0,dr,1,dr,2,dr,3.(d)获取轮输出 Xr+3,如式(10)所示.Xr+3=3i=0(cr,i dr,i).(10)(e)循环执行步骤(a)到步骤(d)32 次,得到未解码的加密结果.原梓清 等:一种抗差分计算分析的白盒 SM4 方案389(6)输出解码如式(11)所示.Xi=Pi(Xi pi),i=32,33,34,35.(11)注:以上加密过程未考虑反序变换.3白-武白盒 SM4 方案的安全性分析本文利用差分计算分析方法对白-武白盒 SM4 方案进行安全性分析.3.1差分计算分析2016 年,Bos 等人首次提出差分计算分析(differential computational analysis,DCA)12.差分计算分析是基于差分功耗分析(differential power analysis,DPA)提出的分析方法,可借助特定的软件收集算法程序运行时泄露的信息,并对其进行分析从而提取密钥.标准差分计算分析的步骤如下:(1)获取软件迹.(2)选取算法计算过程中的某个密钥相关的中间状态字节,确定选择函数.选择函数的输出为中间状态字节的某一位,称为目标比特.对每种情况的目标比特,执行如下步骤(3)到(5):(3)根据目标比特是 0 还是 1,将软件迹分为两类.(4)分别求两类软件迹的均值迹.(5)求两条均值迹的差分迹.(6)比较各差分迹的峰值,其中最大者对应的目标比特为最佳目标比特.(7)对每种情况的密钥字节猜测,执行步骤(2)到(6),比较各种密钥字节猜测下的最佳目标比特对应的差分迹峰值,其中最大者对应的密钥字节猜测为最佳密钥字节猜测.差分计算分析本质上是统计分析方法,分析结果与分析程序的运行环境、密码算法的具体编码都有关系.当密码算法采用可逆矩阵或可逆仿射变换作为密钥相关查找表的输出编码,但是矩阵不含有汉明重量为 1 的行时,标准差分计算分析失效.此时采用变体差分计算分析,即将标准差分计算分析步骤(2)中选择函数的输出(即目标比特)改为中间状态字节各位的某种线性组合的结果,其他步骤不变,即可保证分析成功.3.2对白-武白盒 SM4 方案的差分计算分析本文用 Java 语言编程实现白-武白盒 SM4 方案作为分析对象.如何获取软件迹不属于本文讨论内容,本文用以下方式模拟分析所需软件迹:在白-武白盒 SM4 方案的程序中插入辅助代码,将第一轮加密时的所有查找表的输出存储在一个二进制文件中,将加密前的明文与加密后的密文存储在另一个二进制文件中.随机生成 200 组明文并加密,得到一个存储着 200 条查表记录的二进制文件以及一个存储着 200 组明密文对的二进制文件.在之后的分析中将查表记录对应的二进制文件的内容序列化即可模拟所需的软件迹.通过这种做法得到的模拟软件迹尺寸比实际通过 DBI 等工具捕获的软件迹尺寸小很多.因为实际通过 DBI 等工具捕获的软件迹中,除第一轮加密时的所有查找表的输出外,还有许多与问题无关的数据.那些多余的数据与第一轮子密钥不相关,因此不会影响分析正确率.但是模拟软件迹中没有那些多余的数据,这会导致对其进行分析的效率高于实际中的效率.本文用 C+程序语言编程实现差分计算分析算法,对前述二进制文件进行分析.分析程序的运行环境为:操作系统为 Windows 10 家庭中文版(64 位),开发平台为 Visual Studio 2015,处理器为 Intel(R)Core(TM)i5-8300H CPU 2.30 GHz,内存 8 GB.运用分析程序尝试恢复第一轮子密钥的最高字节,结果如下:(1)固定密码算法编码所用随机矩阵和随机向量,对 10 种不同初始密钥的方案采用数量不等的查表记录及其对应的随机明文进行变体差分计算分析,并统计采用各种数量的样本进行分析时的正确率,结果如表1所示.(2)固定密码算法的初始密钥,对 10 种不同编码的方案分别采用 200 条查表记录及其对应的 200 组随机明文进行变体差分计算分析,均能得出正确的结果.统计分析各种编码的方案所用的时间,结果如表2所示.390Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023表 1 变体差分计算分析的正确率Table 1Correct rate of variant differential computation analysis样本数目10202330100200分析正确率0%0%50%100%100%100%表 2 变体差分计算分析所需时间(毫秒)Table 2Time required for variant differential computation analysis(ms)所用编码编码 1编码 2编码 3编码 4编码 5编码 6编码 7编码 8编码 9编码 10所需时间30667306763082030676304353100230883305023056730930由表1可知,当分析所用软件迹足量时,分析正确率可达 100%,白-武白盒 SM4 方案不能抵抗变体差分计算分析.由表2可知,变体差分计算分析恢复第一轮子密钥最高字节所需时间在半分钟左右.可以用类似的方法恢复第一轮子密钥的全部四个字节.又因为恢复方案的整个初始密钥需要恢复连续四轮的轮密钥,故可以估计在当前实验条件下恢复整个初始密钥大约需要 8 分钟.图1与图2分别展示了密钥字节猜测正确和错误时最佳目标比特对应的差分迹图像,可以看到猜测正确时的图像出现了显著的尖峰,而猜测错误时的图像较为平缓,二者有显著差异.图 1 密钥字节猜测正确时最佳目标比特对应的差分迹图像Figure 1 Image of difference trace of best target bit when key byte was correctly guessed图 2 密钥字节猜测错误时最佳目标比特对应的差分迹图像Figure 2 Image of difference trace of best target bit when key byte was incorrectly guessed原梓清 等:一种抗差分计算分析的白盒 SM4 方案3914抗差分计算分析的改进方案根据文献 14 中所述理论,只采用线性或仿射变换进行内部编码的方案不能抵抗差分计算分析,在此基础上加入半字节非线性代换进行内部编码依旧不能抵抗差分计算分析,只有采用整字节非线性代换进行内部编码才能够抵抗差分计算分析.然而,对方案的所有查找表的输出编码都添加 8 比特的非线性代换会带来巨大的内存开销.由于差分计算分析只能从密码算法的第一轮或最后一轮的密钥相关查找表开始攻击,本文只对这些查找表的输出编码添加 8 比特的非线性代换,并由此出发讨论其他需要修改之处.4.1改进措施以白-武白盒 SM4 方案的第一轮加密为例,第一轮的密钥相关的查找表为式(12).TD1,j:y=P4 Mj S(E11,jF11,j)(x u1,j)k1,j)p4,j,j=0,1,2,3.(12)对其用非线性编码进行保护后变为式(13).TD1,j:y=I0,j(P4 Mj S(E11,jF11,j)(x u1,j)k1,j)p4,j),j=0,1,2,3.(13)其中,I0,j=I0,j,0I0,j,1I0,j,2I0,j,3,I0,j,0,I0,j,1,I0,j,2,I0,j,3都是 8 比特的非线性代换.对 TD 表添加非线性编码,TC 表的输出 c1,i与 TD 表的输出 d1,i不能直接相异或,需要额外的异或表.记 c1=3i=0c1,i,d1=3i=0d1,i.c1,i可以直接相互异或,c1可以直接求出.求 d1需要 12 个 16 比特输入 8 比特输出的异或表.记 16 比特输入 x=x0 x1,其中 x0,x1都是 8 比特的值,则求取 d1需要如下异或表:TE0,j:y=|J0,j(I10,0,j(x0)I10,1,j(x1),j=0,1,2,3J0,j(I10,2,j4(x0)I10,3,j4(x1),j=4,5,6,7J0,j(J10,j8(x0)J10,j4(x1),j=8,9,10,11,其中,J,I1,J1都是 8 比特的非线性代换.求取 X4=c1 d1需要如下异或表:TE0,j:y=H0,j12(x0J10,j4(x1),j=12,13,14,15,其中,H、J1都是 8 比特的非线性代换.由于 X4有非线性编码保护,在后续第 2、3、4、5 轮中涉及的查找表的输入解码都需要先消去非线性.具体地,修改了以下 16 个查找表,如式(14)(20)所示.TA2,j+4:y=E2(P14,j H10,j(x)P14 p4,j)e2,j+4,j=0,1,(14)TB2,j+4:y=F2(P14,j+2 H10,j+2(x)P14 p4,j+2)f2,j+4,j=0,1,(15)TA3,j+2:y=E3(P14,j H10,j(x)P14 p4,j)e3,j+2,j=0,1,(16)TB3,j+2:y=F3(P14,j+2 H10,j+2(x)P14 p4,j+2)f3,j+2,j=0,1,(17)TA4,j:y=E4(P14,j H10,j(x)P14 p4,j)e4,j,j=0,1,(18)TB4,j:y=F4(P14,j+2 H10,j+2(x)P14 p4,j+2)f4,j,j=0,1,(19)TC5,j:y=P8(P14,j H10,j(x)P14 p4,j)p8,j,j=0,1,2,3.(20)同理,对最后一轮的 TD 表的输出编码添加 8 比特的非线性代换,并添加相应的异或表.此外,输出解码环节中求取 X35需要先消去非线性.整个改进方案主要对原方案的第一轮与最后一轮进行了修改,对 TD 表的输出编码添加了 8 比特的非线性代换,添加了 32 个 TE 表用于实现异或操作,TA、TB、TC和 TD 表的尺寸与数量均没有变化.由于所有的非线性代换都被嵌入到查找表中,攻击者捕获的内存信息中既不可能包含单独的非线性代换也不可能包含单独的轮密钥,因此这种做法不会降低抵抗逆向分析的强392Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023度.4.2性能分析TA 表的尺寸为 1 KB,TB 表的尺寸为 1 KB,TC 表的尺寸为 1 KB,TD 表的尺寸为 256 KB,TE 表的尺寸为 64 KB.改进后的方案中有 632=192 个 TA 表、632=192 个 TB 表、432=128 个 TC表、432=128 个 TD 表、216=32 个 TE 表,内存占用 1921+1921+1281+128256+3264=35328 KB=34.5 MB.表3对比了改进后的方案与几个已有白盒实现方案的性能.表 3 性能对比Table 3Performance comparison方案查表次数查找表输入字节数异或表输出字节数异或次数矩阵乘法次数内存(MB)肖-来白盒 SM41281280192160约 0.15白-武白盒 SM46407680544032.5本文改进方案67283232536034.5由表3可知,改进后的方案与原方案相比内存占用增加了 2 M,这是为了提升安全性付出的代价.第5节中可以看到,改进后的方案可以抵抗多种已知的攻击,具有更高的安全性.5安全性分析5.1白盒多样性与白盒含混度白盒多样性与白盒含混度由 Chow 等人提出1,用于衡量方案抵抗暴力攻击的能力.白盒多样性指的是查找表所具有的不同构造方式的数量.白盒含混度指的是能够构造出同一个查找表的构造方式数量.以 TD 表为例,除第一轮与最后一轮外,其余各轮 TD 表的白盒多样性可根据本文第2节的式(8)计算.根据白盒多样性的定义,TD 表的白盒多样性只与 Pr+3、E1r,j、F1r,j、kr,j、ur,j和 pr+3,j有关.kr,j是 8 维随机向量,有 28种情况;ur,j是 16 维随机向量,有 216种情况;pr+3,j是 32 维随机向量,有 232种情况.Pr+3是 32 阶随机可逆矩阵,E1r,j和 F1r,j是 8 阶随机可逆矩阵,而 n 阶随机可逆矩阵的个数 N可根据式(21)计算.N=n1i=0(2n 2i).(21)根据该式计算,8 阶可逆矩阵的个数约为 262.2,32 阶可逆矩阵的数量约为 21022.2.故除第一轮与最后一轮外,TD 表的白盒多样性为 21022.2 262.2 262.2 28 216 232=21202.6.根据白盒含混度的定义,对于同一个查找表,一旦 E1r,j,F1r,j,kr,j和 ur,j确定,则 Pr+3和和 pr+3,j随之确定,故除第一轮与最后一轮外,TD 表的白盒含混度为 262.2 262.2 28 216=2148.4.而第一轮与最后一轮的 TD 表的输出编码中添加了非线性代换,查找表的构造方式更加复杂,故白盒多样性大于 21202.6,白盒含混度大于 2148.4.由此可以得出整个改进方案中 TD 表的白盒多样性的最小值为 21202.6,白盒含混度的最小值为2148.4.同理求得其他各种查找表的最小白盒多样性与最小白盒含混度,如表4所示.表 4 最小白盒多样性与最小白盒含混度Table 4Minimal white-box diversity and minimal white-box ambiguity评价指标TA 表TB 表TC 表TD 表TE 表白盒多样性2568.82568.821342.221202.623368.0白盒含混度2280.82280.82288.02148.421684.0由表4可以看出,改进后的方案中各种查找表的白盒多样性与白盒含混度的值都很高,足以抵抗暴力攻击.原梓清 等:一种抗差分计算分析的白盒 SM4 方案3935.2差分计算分析用3.2节所述方法对改进后的方案进行差分计算分析.在采用 200 个样本进行分析的情况下,无论改进方案采用的是3.2节中所述的哪一种初始密钥或编码,差分计算分析程序均未输出正确的结果.图3与图4分别展示了密钥字节猜测正确和错误时最佳目标比特对应的差分迹图像,可以看到无论猜测正确与否差分迹图像都是平缓的折线,并没有显著差异,无法进行甄别.故改进后的方案可以抵抗 Bos 等人的差分计算分析.图 3 密钥字节猜测正确时最佳目标比特对应的差分迹图像(改进后的方案)Figure 3 Image of difference trace of best target bit when key byte was correctly guessed(improved scheme)图 4 密钥字节猜测错误时最佳目标比特对应的差分迹图像(改进后的方案)Figure 4Image of difference trace of best target bit when key byte was incorrectly guessed(improved scheme)5.3潘文伦等人的攻击潘文伦等人在 2018 年对白-武白盒 SM4 方案进行分析22,将其安全性归结于仿射常数的安全性上,指出白-武白盒 SM4 方案的密钥和外部编码的取值空间大小为 612002128.本文沿文献 22 思路进行分析,依然可以确定 Er+1与 Fr+1.设 Xr+3=x0 x1x2x3,由 x0,x1,x2,x3分别经过查找表 TAr+1,4,TAr+1,5,TBr+1,4,TBr+1,5后的输出值分别为 y0,y1,y2,y3.当 r=1 时,通过式(22)(25)可得 y0,y1,y2和 y3的值.y0=E2(P14,0 H10,0(x0)P14 p4,0)e2,4,(22)y1=E2(P14,1 H10,1(x1)P14 p4,1)e2,5,(23)y2=F2(P14,2 H10,2(x2)P14 p4,2)f2,4,(24)394Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023y3=F2(P14,3 H10,3(x3)P14 p4,3)f2,5.(25)整理得 E12(y0y1)F12(y2y3)=P14,1H10(x)P14,1p4E12(e2,4e2,5)F12(f2,4f2,5),差分形式为 E12(y0 y1)F12(y2 y3)=P14,1(H10(x x)H10(x).由于非线性代换 H10未知,故无法根据该式求得 P14,1,也无法进行后续分析,故改进后的方案可以抵抗潘文伦等人的攻击.5.4基于查找表组合的攻击大部分白盒攻击手段都建立在查找表组合的基础上.对于改进后的方案,有两种查找表组合方式:(1)组合 TDr,j、TCr,j、TAr+1,5、TAr+1,6、TBr+1,5和 TBr+1,6.由于 TA 表和 TB 表的输出编码的线性矩阵部分不同,这些查找表的结果不能合并,这导致我们不能通过这种组合方式消去 TD 表和 TC表的输出编码,也无法建立起从 TDr,j和 TCr,j的输入到 TAr+1,5、TAr+1,6、TBr+1,5和 TBr+1,6的输出的关系,因此该种组合方式不成立.(2)组合 TAr,j、TBr,j、TCr,j和 TDr,j(可能还有 TEr,j).这种组合方式组合了一轮内的所有查找表,消去了所有级联的 8 比特仿射编码,需要解决的是 TC 表和 TD 表的输出编码.如果不从第一轮或最后一轮开始分析,则 BGE 攻击8和林-来攻击11的复杂度为 O(21054.2),De Mulder 等人的攻击10不适用于仿射等价问题,MGH 攻击9的复杂度为 O(281),Lepoint 等人的攻击23能够由输出间的碰撞找到输入间的一对一关系,之后仍然需要解决仿射等价问题,复杂度为 O(281)或 O(21054.2).如果攻击第一轮或最后一轮,则 TC 表和 TD 表的输出编码中有非线性代换,待解决的已不是一个仿射等价问题,复杂度会更高.表5对比了改进后的方案与几个已有 SM4 白盒实现方案的安全性.由表5可知,改进后的方案与原方案相比能够额外抵抗 Bos 等人的差分计算分析,具有更高的安全性.表 5 安全性对比Table 5Security comparison方案BGEMGHDe Mulder 的攻击Lepoint 的攻击林的攻击潘的攻击Bos 的 DCA肖-来白盒 SM4未知未知未知未知否否否白-武白盒 SM4是是是是是是否本文改进方案是是是是是是是6结束语提升白盒密码方案抗差分计算分析的能力对于保证密码算法在实际应用场景下的安全性具有重要意义.本文对白-武白盒 SM4 方案进行差分计算分析,可以在约 8 分钟内恢复初始密钥.基于 8 比特非线性编码,本文对白-武白盒 SM4 方案进行了改进.改进后的方案需要占用内存 34.5 MB,其白盒多样性的最小值为 2568.8,白盒含混度的最小值为 2148.4.改进方案能够抵抗 Bos 等人的差分计算分析、潘文伦等人的攻击以及 De Mulder 等人的攻击,对于 BGE 攻击和林-来攻击的复杂度至少为 O(21054.2),对于 MGH攻击的复杂度至少为 O(281),对于 Lepoint 等人的攻击的复杂度至少为 O(281).Bos 等人的差分计算分析属一阶差分计算分析,对于高阶差分计算分析改进方案是否有抵抗能力仍然是有待研究的课题.参考文献1 CHOW S,EISEN P A,JOHNSON H,et al.White-box cryptography and an AES implementationC.In:SelectedAreas in CryptographySAC 2002.Springer Berlin Heidelberg,2002:250270.DOI:10.1007/3-540-36492-7_172 CHOW S,EISEN P A,JOHNSON H,et al.A white-box DES implementation for DRM applicationsC.In:DigitalRights ManagementDRM 2002.Springer Berlin Heidelberg,2002:115.DOI:10.1007/978-3-540-44993-5_13 XIAO Y Y.White-box Cryptography and Implementations of AES and SMS4D.Shanghai:Shanghai Jiao TongUniversity,2010.肖雅莹.白盒密码及 AES 与 SMS4 算法的实现 D.上海:上海交通大学,2010.原梓清 等:一种抗差分计算分析的白盒 SM4 方案3954 LUO R,LAI X J,YOU R.A new attempt of white-box AES implementationC.In:Proceedings of Interna-tional Conference on Security,Pattern Analysis,and Cybernetics(SPAC 2014).IEEE,2014:423429.DOI:10.1109/SPAC.2014.69827275 SHI Y,WEI W J,HE Z J.A lightweight white-box symmetric encryption algorithm against node capture forWSNsJ.Sensors,2015,15(5):1192811952.DOI:10.3390/s1505119286 BAI K P,WU C K.A secure white-box SM4 implementationJ.Security and Communication Networks,2016,9(10):9961006.DOI:10.1002/sec.13947 BAI K P,WU C K,ZHANG Z F.Protect white-box AES to resist table composition attacksJ.IET InformationSecurity,2018,12(4):305313.DO