对两个SM4白盒方案的分析

Cryptanalysis of Two White-box SM4 Implementations

传统密码算法在设计时并未考虑算法运行平台的安全风险. Chow等在2002年提出了白盒攻击模型,假定攻击者具有完全控制算法运行过程的能力,可以获取算法的运行状态、更改算法运行的中间值等.此模型更符合密码设备在失控环境下的应用情况,因为一个合法的用户也可能变为一个潜在的攻击者.在这种环境下,传统攻击模型中设计的密码算法将不再安全.如何保护密码算法在白盒环境下的安全性,在数字版权保护、移动终端安全等领域具有强烈的现实需求. Chow等使用混淆与查找表等方式设计了AES、DES白盒方案,肖雅莹等在2009年使用类似方法设计了SM4算法的白盒方案(肖-来方案),白鲲鹏等进一步通过复杂化内部解码编码过程以及引入更多随机数的方式设计了一个新的SM4白盒方案(白-武方案).本文分析了这两个SM4白盒方案.首先指出林婷婷等对肖-来方案分析的复杂度计算存在偏差(林-来分析).具体来讲,该分析中唯一确定了编码矩阵及仿射常数,而实质上根据该分析方法,编码矩阵与仿射常数存在61200·2^(32)种可能取值.进一步地,我们改进了林-来的分析方法,通过调整仿射常数的恢复顺序,大幅降低了计算复杂度.如恢复查找表外部编码的仿射常数时,我们通过搜索等价密钥再确定仿射常数的方式只需不超过210次查表运算就可确定该仿射常数,而林-来分析中获取该仿射常数的计算复杂度为2^(46).同时,我们提出了首个针对白-武方案的第三方分析,指出其密钥和外部编码的取值空间大小为61200·2^(128).我们的分析表明,肖-来、白-武方案的安全性主要依赖外部编码中仿射常数的安全性.两个方案的线性变换部分对安全性的影响有限,且复杂化内部编码解码过程并不能有效提高线性变换的安全性.另外,通过对仿射矩阵或仿射常数进行拆分来增大白盒多样性的策略只会增大白盒方案的实现难度,而对方案的安全性并无明显加强.这一系列发现将对白盒密码的分析与设计提供借鉴作用.

Traditional cryptographic algorithms are designed to be secure without considering their platform risks.In 2002,Chow et al.introduced the white-box context,assuming attackers have full control over the execution of a cryptographic algorithm.Attackers can thus observe the algorithm internal states and even modify these values.This white-box model is very practical when evaluating cryptographic devices which are used in untrusted environments,where a legitimate user may be a potential attacker.Then,traditional cryptographic algorithms become no longer secure in such a context,and how to protect their security is strongly required in practice,e.g.digital rights protection and mobile device security.Taking advantage of obfuscation operations and lookup-tables,Chow et al.constructed a white-box implementation of AES and DES.Similarly,Xiao et al.constructed a whitebox implementation of SM4 and Bai et al.proposed another white-box SM4 by more complex inner encodings/decodings and random numbers.This paper analyzes these two white-box implementations of SM4.It first points out a flaw in Lin’s analysis on Xiao’s white-box SM4.In counting encoding matrixes and affine constants,the real value should be 61 200·232 instead of only one in their analysis.Then an improvement of Lin’s method is given.By adjusting the order of recovering affine constants,the improved method greatly reduces the attacking complexity.For example,in recovering the affine constants of external encoding of look-up tables,the new method needs no more than 210 look-ups by first searching equivalent keys and then determining affine constants.This is far less than 246 in Lin’s analysis.This study also proposes a third-party analysis on Bai’s white-box SM4,and points out that the size of keys and external encodings is 61 200·2128.Analysis shows that,both of the two white-box SM4 rely on the security of their affine constants in external encodings,the linear transformation parts contribute very little to security,and simply complicating internal encodings/decodings.Furthermore,at the expense of implementation hardness to increase diversity,the method of splitting affine matrixes or constants cannot efficiently improve security.All these findings will be useful to analyze and design white-box ciphers.