立方攻击成功率分析

宋海欣，范修斌，武传坤，冯登国

（1．中国科学院 软件研究所信息安全国家重点实验室，北京 100190；

2．中国科学院 研究生院，北京 100049）

1 引言

在 2009年欧洲密码年会上，Dinur和 Shamir提出了立方攻击（cube attack）[1]的密码分析方法并对流密码算法Trivium[2]进行了分析，立方攻击是一种新型的代数攻击方法，旨在寻找密码算法固有的低次方程以恢复密钥[3～7]或进行区分攻击[8～10]。

一般来讲，密码算法模型如图1所示。对分组密码来讲，密码算法可看作mbit明文与nbit密钥的函数，经过轮函数的迭代过程，产生密文。对流密码来讲，密码算法可看作mbit初始向量IV与nbit密钥的函数，流密码算法设计一般分为初始化过程和密钥流产生过程，很多流密码算法，如Trivium[2]、Grain v1[11]、Mickey[12]、F-FCSR-H[13]等，其初始化过程均采用低次函数迭代一定拍数，使密钥和初始向量达到一定程度的混乱与扩散。无论是流密码算法还是分组密码算法，一般开始随着迭代拍数的增加，密码算法的代数次数和代数标准型(ANF)项数会戏剧性地增加，迭代一定拍数后，密码算法的代数次数和代数标准型项数会达到一个相对稳定且不可预测的状态。

图1 密码算法模型

本文就一般随机布尔函数及布尔函数的代数次数或代数标准型项数受限情况下，从理论上分析了立方攻击的成功概率，设 f (v1,v2, … ,vm,k1, k2,… ,kn)为m个公开变量 ( v1,v2,… ,vm)及n个密钥变量(k1, k2,… ,kn)的布尔函数，证明了以下结论：1）针对一般随机布尔函数进行讨论，立方攻击的成功概论，设随机布尔函数的代数次数至多为s，若代数次数s与极大项(maxterm)[1]的代数次数l满足关系s - l = 1时，立方攻击的成功概率为1；当 s - l ＞ 1时，成功概率为3）针对布尔函数的代数标准型项数进行讨论，若随机布尔函数可被极大项整除的代数标准型中，代数次数大于等于(l +2)的代数标准型至多为N项，那么立方攻击的成功概率为2-N。

2 立方攻击简介

立方攻击是一种新型的代数攻击方法，在选择IV或选择明文条件下，寻找关于密钥的仿射函数以恢复密钥或进行区分攻击，它吸收了饱和攻击[14]及高阶差分分析[15]的思想，该攻击方法主要基于下述定理。

定理 1[1]设 f (x1, x2,… ,xn)为含有n个变量的布 尔 函 数 ， S = ｛ x1, x2, … , xn｝ , f(⋅)函 数 可 表 示 为其中，I为集合S的非空真子集，设， P (⋅)和 R (⋅)均为代数标准型表示的布尔函数， P (⋅)函数中的变量均取自集合I对S的余集 S I， R (⋅)函数代数标准型中的每一项均不含I中的全部变量，那么，当对集合I中的变量跑遍所有可能取值并对 f(⋅)函数求和，可得：

为了进一步说明该定理，举例如下：

其可以表示为

流密码算法中，在选择 IV攻击条件下，初始向量 IV为公开变量，密钥为未知变量。分组密码算法中，在选择明文攻击条件下，明文为公开变量，密钥为未知变量。

定义1[1]定理1中，若集合I中的变量均为公开变量，并且 P (⋅)的代数次数为 1，就得到了关于未知变量的一个仿射方程f(x1, x2,… ,xn)，并称T(I)为极大项(maxterm)，称P(⋅)为超级多项式(superpoly)。

立方攻击中，攻击者把密码算法看作一个黑盒子，它是关于公开变量和未知变量的未知多项式，只考虑输出的一个比特。对密码算法的立方攻击分为2个阶段：预处理阶段和密钥恢复阶段。在预处理阶段，攻击者可以改变公开变量及未知变量的值并可模拟算法的执行，目的是通过BLR线性测试的方法[16]找到尽量多的关于未知变量的超级多项式，预处理过程只进行一次。在密钥恢复阶段，攻击者只改变公开变量的值，通过在预处理阶段找到的超级多项式建立仿射方程组来恢复某些密钥比特或进行区分攻击。

在预处理阶段，若找到的多项式P为常量，为方便起见，下面讨论中仍视其为攻击成功。

下面就一般布尔函数及布尔函数的代数次数或代数标准型项数受限情况下对立方攻击的成功概率进行分析。

3 一般布尔函数立方攻击成功概率分析

在一般情况下，分析对随机布尔函数立方攻击的成功概率。

设 V = ｛ v1, v2,… ,vm｝ 为m个公开变量， K ={k1,k2,… ,kn}为n个密钥变量，f(v1,v2,… ,vm,k1,k2,… ,kn)为含(m+n)个变量的布尔函数，立方攻击在寻找超级多项式时，先选定集合V的一个非空子集I，不妨设 I = ｛v1, v2,… ,vl｝, 1≤l≤m，并将其他公开变量设置为常数 0或 1 ，此时，f（v1, v2, … ,vm,k1, k2,… ,kn） 函数就退化为含(l + n)个 变 量 的 布 尔 函 数 g（v1, … ,vl,k1, … ,kn）=f（v1, … ,vl,c1, … ,cm-l, k1, … ,kn） ，其中，ci∈ ｛ 0,1｝,1≤i≤ m - l 。

证明 根据以代数标准型表示的 g (⋅)函数中各项所含集合I中变量的个数，可将 g (⋅)函数表示如下

若将 g (⋅)函数表示如下

若使 P(⋅)为仿射函数或常量，参数ai（0≤ i≤n） 可 任 意 取 值 为0或1， 参 数值为0，因此所有参数的可能取值共有 S1= 2n+1。

从定理2可以推出如下结论。

推论1 立方攻击中，针对随机布尔函数，P （⋅）为仿射函数或常量的概率与选择的公开变量的子集I的大小l无关，只与密钥长度n有关。

密码算法设计的目的是使密钥和初始向量（或明文）达到充分的混乱与扩散，在密码算法接近于随机的情况下，又一般密钥长度 n ≥ 8 0，则由定理

4 布尔函数的代数次数受限情况下立方攻击成功概率分析

本节针对布尔函数的代数次数对立方攻击的成功概率进行分析。

定 理 3 设 g(v1,v2, … ,vl,k1,k2,… ,kn)为 含(l + n )个变量的随机布尔函数，该布尔函数的代数次数不大于 s( 2 ≤ s ≤ l + n)，设 I ={v1,v2,… ,vl},1 ≤ l≤ s -1， K = { k1,k2,… , kn}，将 g (⋅)函数表示如下：其中，P (⋅)和 R (⋅)均为代数标准型表示的布尔函数， T (I)/| R (⋅)代数标准型中的任意一项，那么， P (⋅)为仿射函数或常量的概率为

证明 根据以代数标准型表示的 g (⋅)函数中各项所含集合I中变量的个数，可将 g (⋅)函数表示如下

其中， f0为关于变量 （k1, k2,… ,kn） 的以代数标准型i2＜ … ＜it≤ l, 1 ≤ t≤ l )均为关于变量 （k1, k2,… ,kn）的以代数标准型表示的代数次数小于等于（s - t ）的布尔函数， fi1i2…it可表示如下

若将 g (⋅)函数表示如下

下面分2种情况进行讨论。

若使 P (⋅)为仿射函数或常量，参数 ai(0 ≤ i≤n)iq≤ n , 2 ≤ q ≤ s - l)必须全部取值为0，因此所有参数的可能取值共有

从定理3可以看出，设随机布尔函数的代数次数至多为s，若代数次数s与极大项的代数次数l满足关系 s -l=1，立方攻击的成功概率为1。然而，若选择的公开变量的个数l过小，或算法的代数次数 s ＞(m +1)，则有s-l＞1，又一般情况下，密钥长度 n ≥ 8 0，由定理3可知， P (⋅)为仿射函数或常量的概率即 P r几乎为0。这

2可以解释为什么密码算法的代数次数较低时立方攻击的成功概率较高。

由定理3易得，在立方攻击中，若布尔函数的代数次数s固定，随着选择的公开变量的子集I的大小l的逐渐增加， P (⋅)为仿射函数或常量的概率也逐渐增加。因此，在对密码算法进行立方攻击时，若长时间找不到超级多项式，应适当增加选取的公开变量的个数l，这也正是文献[1]中立方攻击所采用的手段。然而，立方攻击至少需要2l次密码算法运算，因此随着l的增加，寻找超级多项式也变得越来越困难。

5 布尔函数的代数标准型项数受限情况下立方攻击成功概率分析

本节针对布尔函数的代数标准型项数对立方攻击的成功概率进行分析。

定理4 设 I = {v1,v2,…,vl}，K ={k1,k2,… ,kn}，g（v1, v2,… ,vl,k1, k2,… , kn） 为含(l + n )个变量的随机布尔函数，，其中，P(⋅)和 R (⋅)均为代数标准型(A NF ) 表示的布尔函数，T(I)/| R (⋅)代数标准型中的任意一项。若 g (⋅)函数可被 T (I)整除的代数标准型中，代数次数大于等于(l + 2 )的代数标准型至多为N项且均匀出现，那么P(⋅)为仿射函数或常量的概率为2-N。

证明 根据以代数标准型表示的 g (⋅)函数中各项所含集合I中变量的个数，可将 g (⋅)函数表示如下：为关于变量（k1, k2,… ,kn）的以代数标准型表示的布尔函数。不妨以 f1,2,…,l为例，其可表示如下：∈ { 0,1}，且各参数取值0或1的概率均为12。

若将 g (⋅)函数表示如下

因 g (⋅)函数可被 T (I)整除的代数标准型中，代数次数不小于(l + 2 )的代数标准型至多为N项，因1≤t≤n)的可能取值共有

若使式(9)中 P (⋅)为仿射函数或常量，参数ai(0 ≤ i≤n)可任意取值为0或1，参数值为0，因此所有参数的可能取值共有

式(7)中，设函数 f0及it≤l,1≤t≤ l-1)中各参数的可能取值共有Δ3，那么 P (⋅)为仿射函数或常量的概率为

由定理4可以看出，若布尔函数可被极大项整除的代数标准型中，代数次数不小于(l + 2 )的项数至多为N项，那么随着N的逐渐减小，立方攻击的成功概率逐渐增大。

6 实验结果

上述理论分析结果与文献[1]中对Trivium算法的实验分析结果是相吻合的，如表1所示。为了节省硬件资源，Trivium算法初始化过程采用二次函数迭代1 152拍，迭代672拍时，找到63个超级多项式，选取的公开变量的个数l=12；迭代735拍时，找到52个超级多项式，l =23；迭代770拍时，找到4个超级多项式，l =29，30。再随着迭代拍数的增加，密码函数的代数次数增高，代数标准型项数增多，需要选择的公开变量的个数l也随之增加，理论上立方攻击的成功概率越来越低，实际上也超出了计算机的运算能力，因此并没有找到更多的超级多项式。

表1 对Trivium算法的立方攻击结果

应用立方攻击方法，编程对Grain v1算法进行了分析[17]，如表2所示，实验结果与上述命题及结论也是吻合的。Grain v1算法与Trivium算法相比，非线性次数较高，密钥扩散速度快，Grain v1算法非线性反馈移存器的反馈多项式的非线性次数为6，过滤函数的非线性次数为3，而Trivium算法非线性反馈移存器的反馈多项式的非线性次数为2，过滤函数是线性的。Grain v1算法初始化过程共迭代160拍，迭代70拍时，找到19个超级多项式，迭代75拍时，找到1个超级多项式，再随着迭代拍数的增加，程序运行了数月仍未找到超级多项式。

表2 对Grain v1算法的立方攻击结果

7 结束语

本文就一般布尔函数及布尔函数的代数次数或代数标准型项数受限情况下，从理论上分析了立方攻击的成功概率，为立方攻击密码分析方法提供了理论支持，理论结果与对流密码算法Trivium及Grain v1的实验结果是相吻合的。

在实际密码算法运行过程中，算法的迭代过程也是密钥的扩散过程，若算法迭代一定拍数后，代数次数已经比较高，且代数标准型项数也比较多，按照上述理论分析结果，这时找到超级多项式的概率几乎为 0，若在实际立方攻击过程中仍能找到超级多项式，则说明密码算法设计中密钥的扩散能力较差，因此立方攻击可作为密码算法设计中检验密钥扩散能力的一种手段。

致谢 在此，我们向对本文的工作给予支持和建议的同行，尤其是冯登国教授领导的讨论班上的同学和老师表示衷心的感谢。

[1] DINUR I, SHAMIR A. Cube attacks on tweakable black box Polynomials[A]. EUROCRYPT 2009[C]. Cologne, Germany, 2009. 278-299.

[2] CANNIÈRE C, PRENEEL B. TRIVIUM - a stream cipher construction inspired by block cipher design principles[EB/OL]. eStream-ECRYPT Stream Cipher Project, Report 2005/030, http:// www.ecrypt.eu. org/stream/trivium.html, 2005.

[3] AUMASSON J, DINUR I, MEIER W, et al. Cube testers and key recovery attacks on reduced-round MD6 and trivium[A]. FSE 2009[C].Leuven, Belgium, 2009. 1-22.

[4] YANG L, WANG M, QIAO S. Side Channel Cube Attack on PRESENT[A]. CANS 2009[C]. Beijing, China, 2009. 379-391.

[5] FISCHER S, KHAZAEI S, MEIER W. Chosen IV statistical analysis for key recovery attacks on stream ciphers[A]. AFRICACRYPT 2008[C]. Casablanca, Morocco, 2008. 236-245.

[6] KHAZAEI S, MEIER W. New directions in cryptanalysis of self-synchronizing stream ciphers[A]. INDOCRYPT 2008[C]. Kharagpur, India, 2008. 15-26.

[7] VIELHABER M. Breaking ONE FIVIUM by AIDA an algebraic IV differential attack[EB/OL]. http://eprint.iacr.org/2007/413, 2007.

[8] ENGLUND H, JOHANSSON T, TURAN M S. A framework for chosen IV statistical analysis of stream ciphers[A]. INDOCRYPT 2007[C]. Chennai, India, 2007. 268-281.

[9] FILIOL E. A new statistical testing for symmetric ciphers and hash functions[A]. ICICS 2002[C]. Singapore, 2002. 342-353.

[10] SAARINEN M. Chosen-IV statistical attacks on eStream ciphers[A].SECRYPT[C]. Setubal Portugal, 2006. 260-266.

[11] HELL M, JOHANSSON T, MAXIMOV A, et al. The Grain family of stream ciphers[A]. LNCS 4986[C]. Setubal, Portugal, 2008. 179-190.

[12] BABBAGE S, DODD M. The stream cipher MICKEY[EB/OL].http://www.ecrypt.eu.org/stream, 2005.

[13] ARNAULT F, BERGER T, LAURADOUX C. Update on F-FCSR stream cipher[EB/OL]. http://www.ecrypt.eu.org/stream, 2006.

[14] LUCKS S. The saturation attack - a bait for Twofish[A]. FSE 2001[C].Yokohama, 2001. 1-15.

[15] KNUDSEN L. Truncated and higher order differentials[A]. FSE 1994[C].Leuven, Belgium, 1995. 196-211.

[16] BLUM M, LUBY M, RUBINFELD R. Self-testing/correcting with applications to numerical problems[A]. Proc 22nd Annual ACM Symp on Theory of Computing[C]. New York, USA, 1990. 73-83.

[17] 宋海欣, 范修斌, 武传坤等. 流密码算法 Grain的立方攻击[J]. 软件学报, 2012, 23(1): 171-176.SONG H X, FAN X B, WU C K, et al. Cube a ttack on Grain[J].Journal of Software, 2012, 23(1): 171-176.