代数攻击教学提纲.ppt

代数攻击代数攻击内容简介代数攻击的起源非线性方程组求解算法简介基于LFSR的序列密码算法的代数攻击标准代数攻击快速代数攻击布尔函数的代数免疫性简介基于NFSR的序列密码算法的代数攻击线性前馈模型的代数攻击Cube攻击结束语2什么是代数攻击通过求解一组代数方程来实现对密码算法的攻击。如何构造方程如何求解方程3代数攻击的起源1949,Shannon,Communication Theory of Secret Systems“.the cryptanalyst can set up equations for the different key elements k1,k2,kr(namely the enciphering equations).Each of these equations should therefore be complex in the ki,and involve many of them.Otherwise the enemy can solve the simple ones and then the more complex ones by substitution.”4代数攻击的起源多变元公钥密码算法基于的困难问题：求解有限域上一组随机二次多变元多项式方程组是NP-hard问题.公钥：一组二次多变元多项式f1(x1,xn),f2(x1,xn),fn(x1,xn)kx1,xn加密：设明文(p1,p2,pn)kn,则密文(c1,c2,cn)满足 c1 f1(p1,p2,pn)c2 f2(p1,p2,pn)cn fn(p1,p2,pn)5代数攻击的起源k=Fq,K=FqnknknKKknknL1L2F(X)=X1+q knkn(f1(x1,xn),f2(x1,xn),fn(x1,xn)1idid6代数攻击的起源2003年前后，Nicolas T.Courtois等人将代数攻击思想用于分组密码和序列密码。代数攻击对基于LFSR的序列密码算法构成严重威胁。7非线性方程组求解算法简介非线性方程组求解算法简介8非线性方程组求解算法简介计算复杂度理论求解有限域上一组随机二次多变元多项式方程组是NP-hard问题.实际情形从具体的密码算法中得到的非线性方程组往往不符合随机的要求,这为代数攻击中解方程组提供了可能.9非线性方程组求解算法简介线性化方法Grbner基方法SAT方法10线性化方法用新变元代替高次(2)单项式,使得原始的非线性方程组转化为线性方程组.再利用Gauss消元法求解关于新变元的线性方程组根据新变元的取值求解原始变元11线性化方法x1x2x4x1x3x5x0 x2x6x2x3x7x0 x3x8x0 x1x9x4+x5+x0+x2=0 x6+x4+x7+x1+x3+1=0 x8+x7+x0+x1+x2=0 x9+x8+x5+x2+x3+1=0 x9+x6+x0+x3+1=0 x4+x5+x0=0 x6+x4+x7+x1=0 x8+x7+x2=0 x9+x8+x5+x1+x3+1=0 x9+x6+x0+x2=0 x1x2+x1x3+x0+x2=0 x0 x2+x1x2+x2x3+x1+x3+1=0 x0 x3+x2x3+x0+x1+x2=0 x0 x1+x0 x3+x1x3+x2+x3+1=0 x0 x1+x0 x2+x0+x3+1=0 x1x2+x1x3+x0=0 x0 x2+x1x2+x2x3+x1=0 x0 x3+x2x3+x2=0 x0 x1+x0 x3+x1x3+x1+x3+1=0 x0 x1+x0 x2+x0+x2=0 x0=0,x1=0,x2=0,x3=1,x4=0,x5=0,x6=0,x7=0,x8=0,x9=012线性化方法13线性化方法Relinearization方法A.Kipnis,A.Shamir.Cryptanalysis of the HFE Public Key Cryptosystem,Crypto99.基本思想第一次线性化：xaxb=yab,xcxd=ycd,因为 (xaxb)(xcxd)(xaxc)(xbxd)(xaxd)(xbxc)所以 yabycd=yacybd=yadybcyab=lab(z1,z2,),ycd=lcd(z1,z2,),第二次线性化：zizj=vij,方程数量的增加大于变方程数量的增加大于变元数量的增加。元数量的增加。线性相关的方程。线性相关的方程。需要的方程个数大约为线性化方需要的方程个数大约为线性化方法所需方程个数的五分之一法所需方程个数的五分之一(xaxb)(xcxd)(xexf)(xaxd)(xbxc)(xexf)14线性化方法eXtended Linearizations方法N.Courtois,A.Klimov,J.Patarin,and A.Shamir.Efficient algorithms for solving overdefined systems of multivariate polynomial equations,EUROCRYPT 200015线性化方法eXtended Linearizations方法设 fi(x1,x2,xn)0,i1,2,m 是二元域F2上的非线性方程组.16线性化方法17线性化方法eXtended Linearizations方法Free=minT,R or minT,R 1 or minT,R 2n10101020202020m10161820406065Free11017417542084012601350Free/R1.0000.98860.88381.00001.00001.00000.9890Free/T0.62500.98860.99430.31090.62180.93620.9993D=318线性化方法eXtended Linearizations方法D345Free420401021699Free/R1.00000.95020.7301Free/T0.31090.64721.000n=20,m=2019线性化方法Relinearization方法和eXtended Linearizations方法线性化方法的改进，减少了线性化方法所需方程数量方程数量与线性化的规模相当时，计算复杂度是多项式时间方程数量与方程规模相当的情形计算复杂度无法估计20Grbner基方法Grbner基Grbner Bases were introduced by Bruno Buchberger in 1965.The terminology acknowledge the influence of Wolfgang Grbner on Buchbergers work.给定零维理想I,找Kx1,xn/I在K上的一组基 Grbner Bases,A Computational Approach to Commutative Algebra.GTM 141.(Chapter 5 Grbner Bases)21Grbner基方法多变元多项式环F2x1,xn 项集：TT(x1,xn),T(f)x1,x1x2,x12x2x3 f=x1+x1x2+x2x3x4,T(f)=x1,x1x2,x2x3x4项序:定义在项集T上的大小关系字典序:x2x3 x1次数字典序:x1 x2x3 首项HT(f)线性序线性序对对任意的任意的X T(x1,xn),有有1 X;对对Y,X1,X2 T(x1,xn),有有X1 X2YX1 YX2.22Grbner基方法多项式约化（除法）P F2x1,xn,f,gF2x1,xnf 模P约化到g:f g f g mod Id(P)若g模P不能再约化了，则g称为f 模P的一个正规型f 0 f Id(P)Pf g1 p1 g2 p2 gk=g pkP23Grbner基方法什么是Grbner基F2x1,x2,.,xn中理想的一组特殊的生成元I=Id(G),对任意的fI,存在gG满足HT(g)整除HT(f)给定项序，既约Grbner Bases唯一f 模G的正规型唯一f 0 f Id(G)G24Grbner基方法Grbner基算法Buchberger 算法(Buchberger,1965)F4 算法(Jean-Charles Faugre,1999)F5算法(Jean-Charles Faugre,2002)GVW(S.H.Gao,F.Volny,and M.S.Wang.,2010)25Grbner基方法Grbner基与解方程设 fi(x1,x2,xn)0,i1,2,m是二元域F2上非线性方程组.在字典序下,计算由 f1,fm,x12x1,xn2xn生成的理想I的既约Grbner基G*=g1,g2,gk.解方程组gi=0,i=1,k,即得原方程组的解.General MethodGeneral Method26Grbner基方法Grbner基与解方程设 fi(x1,xn)0,i1,2,m是二元域F2上非线性方程组.在次数字典序下,计算由 f1,fm,x12x1,xn2xn生成的理想I的既约Grbner基G.利用Grbner基的换序算法，计算在字典序下理想I的既约Grbner基G*=g1,g2,gk.解方程组gi=0,i=1,k,即得原方程组的解.General MethodGeneral Method27Grbner基方法Grbner基与解方程令Gi=G*F2xi,xn,i=1,2,n,则依次解方程组Gn=0,Gn1=0,G1=0可得方程组的全体解.General MethodGeneral Method28Grbner基方法Grbner基与解方程定理 设 fi(x1,xn)0,i1,2,m是二元域F2上非线性方程组,若该方程组在F2中有唯一一组解(x1,x2,xn)(a1,a2,an),则由 f1,fm,x12x1,xn2xn生成的理想的既约Grbner基为x1a1,x2a2,xnan.29Grbner基方法优点方程数量要求低局限性存储复杂度大计算复杂度无法估计30SAT方法Boolean Satisfiability Problem(SAT)布尔变量(Boolean variable):取两个值True或False的变量布尔运算(Boolean operations):and,or,not 布尔公式(Boolean formula)：由,变量,括号构成的公式可满足(satisfiable)不可满足(unsatisfiable)Satisfiability Problem判断一个布尔公式是否可满足第一个NP-完全问题x1(x2x3)可满足的：可满足的：x1=T,x2=T,x3=T.31SAT方法Boolean Satisfiability Problem(SAT)字(literal)：一个布尔变量或者一个布尔变量的取“非”子句(clause)：一些字的“或”合取范式(CNF):一些子句的“与”构成的布尔公式任何布尔公式都可以转化成CNF一个CNF是“可满足”的该CNF中的每一个子句是“可满足”的.Eg:x1(x2 x3)(x3 x4)x532SAT方法Boolean Satisfiability Problem(SAT)国际上对SAT实例的描述统一采用CNF,并用DIMACS格式写成以.cnf为后缀名的文件,所有的SAT求解器都只能识别DIMACS格式的CNF文件.SAT Competition:20022005,20072013Rsat,minisat,cryptominisat33SAT方法SAT与解方程将非线性方程组转化为DIMACS格式的SAT实例34SAT方法SAT与解方程将非线性方程组转化为DIMACS格式的SAT实例ANF转化为CNFf1(x1,xn)0f2(x1,xn)0fm(x1,xn)0(f1(x1,xn)+1)(f2(x1,xn)+1)(fm(x1,xn)+1)35SAT方法SAT与解方程将非线性方程组转化为DIMACS格式的SAT实例ANF转化为CNFl个变元的异或加表示成CNF需要2l1个子句(a b c)(ab c)(a bc)(abc)a b c=036SAT方法SAT与解方程将非线性方程组转化为DIMACS格式的SAT实例ANF转化为CNFl个变元的异或加表示成CNF需要2l1个子句Mate Soos开发的求解器cryptominisat输入格式支持异或运算37SAT方法SAT与解方程将非线性方程组转化为DIMACS格式的SAT实例ANF转化为CNFcryptominisat输入格式支持异或运算用SAT求解器判断SAT实例是否可满足若SAT实例可满足，则方程组有解。此时，SAT求解器会返回一组使SAT实例取值为“真”的一组布尔变量的取值，从而获得方程组的一组解.若SAT实例不满足，则方程组没有解。38SAT方法优点算法过程中存储复杂度不会变大，基本由方程组转化后的SAT实例的规模决定。计算复杂度主要由方程的稀疏度决定。G.V.Bard,N.T.Courtois,and C.Jefferson.Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2)via SAT-Solvers.http:/eprint.iacr.org/2007/024/局限性返回一组解计算复杂度无法估计39SAT方法SAT在序列密码分析中的应用N.T.Courtois,G.V.Bard,and D.Wagner.Algebraic and Slide Attacks on KeeLoq,FSE 2008.对于64轮Keeloq算法，已知两对明密文，用MiniSat 2.0.解方程，约0.3秒可求得密钥.C.McDonald,C.Chernes,J.Pieprzyk.Attacking Bivium with MiniSat.http:/eprint.iacr.org/2007/129,2007.猜测34比特，用minisat解一个方程的时间约440秒Tobias Eibach,Enrico Pilz,and Sebastian Steck.Comparing and optimising two generic attacks on Bivium.猜测48比特，用Rsat解一个方程的时间约0.116秒40基于基于LFSR的序列密码算法的代数攻击的序列密码算法的代数攻击41基于LFSR的前馈模型n级LFSRm(x)=c0+c1x+cn 1xn 1+xnsst+n=st+c1st+1+cn 1sn 1+t+cnsn+t,t 0.42基于LFSR的前馈模型n级LFSRf(x0,x1,xn 1)m(x)=c0+c1x+cn 1xn 1+xnz=(z0,z1,zl 1,)43Toyocrypt63,64,125的一的一个置换个置换17次单项式次单项式44基于LFSR的序列密码算法的代数攻击第一步：获得关于密钥比特和输出密钥流比特的代数关系。fi(k0,k1,kn,zt1,zt2,ztm)=0,i=1,2,l.第二步：将已知的密钥流比特带入方程，从而获得关于密钥变量的代数方程组。gi(k0,k1,kn)=0,i=1,2,l.第三步：解代数方程组，验证解，从而获得密钥。预计算预计算45标准标准代数攻击代数攻击46基于LFSR的序列密码算法的代数攻击标准代数攻击N.Courtois,and W.Meier.Algebraic attacks on stream ciphers with linear feedback.EUROCRYPT 200347基于LFSR的前馈模型的标准代数攻击寄存器的第t时刻状态St=(s0t,s1t,sn1t)寄存器初始状态S0=(s0,s1,sn1)=(k0,k1,kn1)第t时刻密钥流比特zt和第t时刻状态St的代数关系：zt=f(St)=f(s0t,s1t,sn1t)n级LFSRf(x0,x1,xn 1)m(x)=c0+c1x+cn 1xn 1+xnz=(z0,z1,zl 1,)48基于LFSR的前馈模型的标准代数攻击St+1=St M状状态转移矩移矩阵n级LFSRf(x0,x1,xn 1)m(x)=c0+c1x+cn 1xn 1+xnz=(z0,z1,zl 1,)49基于LFSR的前馈模型的标准代数攻击寄寄存存器器的的第第t时刻刻状状态和和初始状初始状态的代数关系：的代数关系：St=S0 Mt可可以以建建立立第第t时刻刻密密钥流流比比特特zt和和初初始始状状态比比特特的的代数关系：代数关系：zt=f(St)=f(S0 Mt)=f(Lt(k0,k1,kn 1)n级LFSRf(x0,x1,xn 1)m(x)=c0+c1x+cn 1xn 1+xnz=(z0,z1,zl 1,)50基于LFSR的前馈模型的标准代数攻击若若已已知知密密钥流流比比特特为zt1,zt2,ztl，则zt1=f(Lt1(k0,k1,kn 1)zt2=f(Lt2(k0,k1,kn 1)ztl=f(Ltl(k0,k1,kn 1)前前馈函函数数的的次次数数决决定定了了方方程程组的次数的次数n级LFSRf(x0,x1,xn 1)m(x)=c0+c1x+cn 1xn 1+xnz=(z0,z1,zl 1,)51基于LFSR的前馈模型的标准代数攻击若若已已知知密密钥流流比比特特为zt1,zt2,ztl，则zt1=f(Lt1(k0,k1,kn 1)zt2=f(Lt2(k0,k1,kn 1)ztl=f(Ltl(k0,k1,kn 1)前前馈函函数数的的次次数数决决定定了了方方程程组的次数的次数例如例如Toyocrypt128级LFSR前前馈函函数数f(x0,x1,x127)是是一个一个63次的布次的布尔函数函数 52基于LFSR的前馈模型的标准代数攻击降低方程次数f(x0,x1,xn 1)g(x0,x1,xn 1)zti=f(Lti(k0,k1,kn 1)zti g(Lti(k0,kn 1)=f(Lti(k0,kn 1)g(Lti(k0,kn 1)=h(Lti(k0,kn 1)=h(x0,x1,xn 1)低次低次53基于LFSR的前馈模型的标准代数攻击降低方程次数zti g(Lti(k0,kn 1)=h(Lti(k0,kn 1)注：若注：若h=0,则仅取则仅取zti=1的位置。的位置。注：若注：若g是高次函数或是高次函数或deg(g)deg(h)，则可以仅，则可以仅取取zti=0的位置。的位置。f(x0,x1,xn 1)g(x0,x1,xn 1)zti=f(Lti(k0,k1,kn 1)=h(x0,x1,xn 1)低次低次54基于LFSR的前馈模型的标准代数攻击定理(Courtois,Meier,Eurocrypt 2003)设f 是一个m元布尔函数,则存在次数小于等于m/2的布尔函数g满足gf 的次数小于等于m/2.注：前馈函数的输入变元个数可能小于LFSR的级数。N.Courtois,and W.Meier.Algebraic attacks on stream ciphers with linearfeedback.EUROCRYPT200355基于LFSR的前馈模型的标准代数攻击预计算找低次代数关系gf=h,获得关于初态比特的方程组在线攻击代入已知密钥流比特解方程组（超定、线性化）zt g(Lt(k0,kn 1)=h(Lt(k0,kn 1)注注：低低次次代代数数关关系系不不止止一一个个，找尽可能多的低次代数关系。找尽可能多的低次代数关系。56Toyocrypt三次方程组！三次方程组！gf=hdeg(g)=1,deg(h)=357Toyocrypt58LILI-128LILI-128 was submitted as a synchronous stream cipher candidate to the NESSIE project.It uses a 128-bit key and an internal memory of 128 bits.39级LFSRcfc89级LFSRdfdzclockcontrol10元元6次布尔次布尔函数函数59LILI-128fd=x3x5x6x7x8x9 x4x5x6x7x8x9 x2x6x7x8x9 x3x5x6x7x8 x3x5x6x8x9 x3x6x7x8x9 x4x5x6x7x8 x4x5x6x8x9 x0 x7x8x9 x1x6x7x8 x1x6 x8x9 x2x6x7x9 x2x7x8x9 x3x5x6x8 x3x6x7x8 x3x6x8x9 x3x7x8x9 x4x5x6x8 x4x6x7x9 x5x6x8x9 x5x7x8x9 x1x8x9 x2x6x8 x2x7x8 x2x7x9 x2x8x9 x3x6x8 x3x6x9 x3x7x9 x3x8x9 x4x6x9 x4x8x9 x5x6x8 x5x6x9 x5x7x8 x0 x7 x0 x8 x1x7 x2x8 x3x9 x5x6 x5x9 x1 x2 x3 x460LILI-128fd(x9+1)(x10+1)=h 是4次函数fd x8x10=h 是4次函数fd x8x10(x2x9+x3x7+x4x7+x5x9+x1+x4+x5+x6+1)=014个四次关系四次方程组！四次方程组！61LILI-12862快速快速代数攻击代数攻击63LFSR非线性前馈的快速代数攻击快速代数攻击N.Courtois.Fast algebraic attacks on stream ciphers with linear feedback.CRYPTO 2003f(x0,x1,xn 1)g(x0,x1,xn 1)=h(x0,x1,xn 1)gh密钥流比特密钥流比特低次低次0-标准代数攻击标准代数攻击低次低次低次低次-高次高次低次低次zt=0低次低次高次高次连续连续快速代数攻击快速代数攻击64基于LFSR的前馈模型的快速代数攻击已知zt=f(Lt(k0,k1,kn1)gf=h,deg(g)=e l,已知连续r比特密钥流zt,zt+1,zt+r1,可以获得一个关于寄存器初始状态比特的次数小于等于k(l+1)/2的多项式方程.注：F(Xt,Xt+r1,zt,zt+1,zt+r1)=0.例如：E0是(4,4)-combiner,存在关于连续4个时刻的4次代数关系。80布尔函数的代数免疫性布尔函数的代数免疫性81代数免疫度定义(Meier,Pasalic,Carlet,EUROCRYPT 2004)设 f 是一个 n 元布尔函数,称 f 或 f+1 的非零零化子的最低次数为 f 的代数免疫度(algebraic immunity),记为AI(f).注：要抵抗标准代数攻击,布尔函数必须具有高的代数免疫度.W.Meier,E.Pasalic,andC.Carlet,AlgebraicattacksanddecompositionofBooleanfunctions,Eurocrypt200482代数免疫度gf=h,h是低次函数gh低次低次0gf=0f有一个低次零化子有一个低次零化子低次低次低次低次gf=hgf=hf h=hfh(f+1)=0f+1有一个低次零化子有一个低次零化子高次高次低次低次gf=hh(f+1)=0f+1有一个低次零化子有一个低次零化子83代数免疫度定理(Courtois,Meier,Eurocrypt 2003)对任意 n 元布尔函数 f,有AI(f)n/2.定义(Meier,Pasalic,Carlet,EUROCRYPT 2004)称 AI(f)达到n/2的布尔函数f 为具有最优代数免疫的布尔函数.N.Courtois,and W.Meier.Algebraic attacks on stream ciphers withlinearfeedback.EUROCRYPT2003W.Meier,E.Pasalic,andC.Carlet.AlgebraicattacksanddecompositionofBooleanfunctions.EUROCRYPT200484代数免疫度最优代数免疫布尔函数的构造择多函数(A.Braeken,B.Preneel,INDOCRYPT 2005)迭代构造法(D.K.Dalai,K.C.Gupta,and S.Maitra,FSE 2005)矩阵构造法(N.Li,W.F.Qi,ASIACRYPT 2006)仿射平面构造法(C.Carlet,Coding and Cryptography,2007)基于有限域的构造一元多项式(C.Carlet,and K.Q.Feng,ASIACRYPT 2008)二元多项式(Z.R.Tu,and Y.P.Deng,DCC 2011)85代数免疫度86代数免疫度87快速代数免疫度高代数免疫度不足以抵抗快速代数攻击eSTREAM候选算法SFINKS(N.Courtois,ICISC 2006)256比特LFSR、前馈函数17个变元、次数15degreeeofgdegreedofh=fgDataPre-computationSubstitutionSolvingSystem标准代标准代数攻击数攻击6236.52108快速代快速代数攻击数攻击28248.6259.8269.7242.137243.6254.5271260.146238.5249271.6276.988快速代数免疫度定理(Courtois,Crypto 2003)设f 是一个n元布尔函数。若整数对(e,d)满足e+d n,则存在次数小于等于e的布尔函数g满足h=gf 的次数小于等于d.mindeg(g)+deg(gf)n定义(Liu,Zhang,and Lin.,ASIACRYPT 2012)若对所有次数小于n/2的正整数e和所有满足deg(g)e的函数g 0有deg(gf)ne,则称f 为完全代数免疫函数(PAI函数)。注：完全代数免疫函数一定是最优代数免疫函数。M.C.Liu,Y.Zhang,andD.D.Lin.Perfectalgebraicimmunefunctions.ASIACRYPT2012.89完全代数免疫函数定理 n元完全代数免疫布尔函数存在当且仅当n=2k或2k+1.平衡完全代数免疫布尔函数的变元个数一定是2k1.非平衡完全代数免疫布尔函数的变元个数一定是2k.M.C.Liu,Y.Zhang,andD.D.Lin.Perfectalgebraicimmunefunctions.ASIACRYPT2012.90完全代数免疫函数定理 设n=2k+1,是F2n的本原元.若布尔函数f 的支撑集为supp(f)=l,l+1,l+2n1 1,0 l 2n2,则f是完全代数免疫布尔函数。定理 设n=2k,是F2n的本原元.若布尔函数f 的支撑集为supp(f)=0,l,l+1,l+2n1 1,0 l 2n2,则f是完全代数免疫布尔函数。M.C.Liu,Y.Zhang,andD.D.Lin.Perfectalgebraicimmunefunctions.ASIACRYPT2012.91基于基于NFSR的序列密码算法的代数攻击的序列密码算法的代数攻击92序列密码设计思想的发展传统的序列密码算法设计思想LFSRLFSR非线性运算层非线性运算层密钥流密钥流非线性前馈非线性前馈钟控钟控进位加运算进位加运算存储记忆存储记忆难以抵抗代难以抵抗代数攻击！数攻击！93序列密码设计思想的发展新的序列密码设计思想LFSRLFSR非线性运算层非线性运算层密钥流密钥流NFSRNFSR线性或简单的线性或简单的非线性过滤非线性过滤94NFSR线性前馈的代数攻击线性前馈的代数攻击95NFSR线性前馈的代数攻击n级NFSR g(x0,x1,xn 1)z=(z0,z1,)寄存器序列寄存器序列s满足足递归关系：关系：st+n=g(st,st+1,st+n 1),t 0输出密出密钥流序列流序列z满足：足：zt=0st 1st+1 n 1st+n 1,t 096NFSR线性前馈的代数攻击对任意的时刻t,寄存器比特st可以表示成初始状态和密钥流比特的线性关系。st=Lt(s0,sn1,z0,zt)寄存器序列寄存器序列s满足足递归关系：关系：st+n=g(st,st+1,st+n 1),t 0输出密出密钥流序列流序列z满足：足：zt=0st 1st+1 n 1st+n 1,t 0 k=1,k+1=n 1=0zn k=0sn k 1sn k+1 k 1sn 1 sn,sn=zn k 0sn k 1sn k+1 k 1sn 1,zn k+1=0sn k+1 1sn k+2 k 1sn sn+1,sn+1=zn k+1 0sn k+1 1sn k+2 k 1sn,97NFSR线性前馈的代数攻击第一步：对任意的时刻t,寄存器比特st可以表示成初始状态和密钥流比特的线性关系：st=Lt(s0,sn1,z0,zt)，t 0第二步：将线性关系代入NFSR的反馈函数得到方程组Lt+n=g(Lt,Lt+1,Lt+n1),t 0第三步：考察是否存在函数h满足deg(h)和deg(gh)的次数小于d。若存在，则得到新的方程组：Lt+nh=gh,t 098注：次数等于反馈注：次数等于反馈函数次数函数次数deg(g)=d.98Modified Grain8080级NFSR80级LFSRhkeystream1 14 47 76次函数次函数g(x0,x1,x79)5元元3次函数次函数99Modified Grain8080级NFSRkeystream1 17 76次函数次函数g(x0,x1,x79)zt=st+1 st+2 st+4 st+10 st+31 st+43 st+56 st+63,t 0100Modified Grain80线性关系s80=z17 s18 s19 s21 s27 s48 s60 s76,s81=z18 s19 s20 s22 s28 s49 s61 s77,s82=z19 s20 s21 s23 s29 s50 s62 s78,s83=z20 s21 s22 s24 s30 s51 s63 s79,s84=z21 s22 s23 s25 s31 s52 s64 s80,s84=z21 z17 s22 s23 s25 s31 s52 s64 s18 s19 s21 s27 s48 s60 s76,st=Lt(s0,sn 1,z0,zt)，t 0101Modified Grain80由反馈函数得80元6次方程组Lt+80=g(Lt,Lt+1,Lt+79),t 0代数关系：(x281)(x601)g(x0,x1,x79)为4次函数 80元4次方程组Lt+80(Lt+281)(Lt+601)=(Lt+281)(Lt+601)g(Lt,Lt+1,Lt+79)线性化方法解方程组：221密钥流比特，249计算复杂度。102NFSR线性前馈+LFSR非线性前馈n级NFSRm级LFSRhkeystream103NFSR线性前馈+LFSR非线性前馈第一步：对任意的时刻t,NFSR寄存器比特xt可以表示成初始状态和密钥流比特的代数关系：xt=Lt(x0,xn1,z0,zt)Ht(y0,ym1),t 0第二步：将代数关系代入NFSR的反馈函数得到方程组Lt+n Ht+n=g(Lt Ht,Lt+n1 Ht+n1),t 0第三步：考察是否存在函数f 满足deg(f)和deg(fg)的次数小于dg。若存在，则得到新的方程组：(Lt+n Ht+n)f=gf,t 0104注：次数等于注：次数等于dgdh.注：次数注：次数dg dh104Modified Grain-128128级NFSR128级LFSRhkeystream2 27 77 72次函数次函数g(x0,x1,x127)3次函数次函数105Modified Grain-128128级NFSR128级LFSRhkeystream7+27+27 72次函数次函数g(x0,x1,x127)3次函数次函数解解256元元6次方程组次方程组线性化方法：线性化方法：239密钥流比特，密钥流比特，2105计算复杂度计算复杂度106Cube攻击攻击选择选择IV代数攻击代数攻击107Cube攻击108Cube攻击109Cube攻击密码算法密码算法私有私有Key公开公开IV初始化算法初始化算法密钥流生成算法密钥流生成算法密钥流密钥流zt=Ft(Key,IV)=Ft(k1,kn,v1,vm)=tI pI(Key,IVI)+q(),从从IV中中选选择择cube变变量量I=vi1,vi2,vid.如何选择如何选择cube变量变量i？如何计算超多项式？如何计算超多项式pI？110Cube攻击如何检测函数的次数和还原函数的代数正规型？faf(a)111Cube攻击n元布尔函数f(x1,xn)的线性检测随机取两组输入X1和X2,查询函数值f(0),f(X1),f(X2),f(X1+X2),判断 f(X1)+f(X2)+f(0)=f(X1+X2)?若不成立，则f是非线性函数。112Cube攻击确定线性函数f(x1,xn)的代数正规型设Ei=(0,0,1,0,0)是n维向量且仅第i分量等于1,i=1,2,n.查询函数值：f(0)=c0,f(E1)=c1,f(E2)=c2,f(En)=cn,那么，函数线性函数f(x1,xn)的代数正规型为f=(cn+c0)xn+(cn1+c0)xn1+(c1+c0)x1+c0 f(x1,x2,x3,x4)=1+x1+x2+x4x3的系数：的系数：f(0,0,1,0)+f(0,0,0,0)=1+1=0113Cube攻击n元布尔函数f(x1,xn)的二次检测随机取三组输入X1,X2,X3,查询函数值f(0),f(X1),f(X2),f(X3),f(X1+X2),f(X1+X3),f(X2+X3),f(X1+X2+X3),判断 f(X1+X2+X3)=f(0)+f(X1)+f(X2)+f(X3)+f(X1+X2)+f(X1+X3)+f(X2+X3)?若不成立，则f是大于二次的函数。114Cube攻击离线阶段离线阶段115Cube攻击离线阶段：寻找足够多cube变量I和低次超多项式pI(Key)在线阶段：通过选择IV，确定超多项式在当前密钥下的函数值，从而获得关于密钥比特的代数方程。计算复杂度主要由cube变量的维数决定。116Cube攻击Trivium密钥：密钥：80比特比特IV:80比特比特初始化轮数：初始化轮数：1152KeyKeyIVIV1 1，1 1，1 1117Cube攻击I.Dinur and A.Shamir,Cube attacks on tweakable black box polynomials,EUROCRYPT 2009672,735,767线性方程P.Mroczkowski and J.Szmidt,The cube attack on stream cipher Trivium and Quadraticity Test.Fundam.Inform.,2012709线性、二次方程P.Fouque and T.Vannet,Improving key recorvery to 784 and 799 rounds of Trivium using optimized cube attacks,FSE 2013784-线性方程799-线性、二次方程118Cube攻击Trivium-672(Dinur,Shamir,EUROCRYPT 2009)12维cube,63个线性方程SuperpolyCubeindexesOutputbitindex1+x0+x9+x502,13,20,24,37,42,43,46,53,55,57,676751+x0+x242,12,17,25,37,39,46,48,54,56,65,786731+x1+x10+x513,14,21,25,38,43,44,47,54,56,58,686741+x1