一种新的s盒设计准则

一种新的s盒设计准则

2000年10月，由美国国家基准研究所（nist）确定的rijnam算法被美国国家基准研究所（nist）确定为美国高质量加密标准。自那以后，密码分析专家们对该算法的研究越来越感兴趣。aes密码分析已成为当前国际密码学术界的研究重点。在传统的分组密码分析中，aes算法的两种主要攻击方法是微分分析和线性分析，而aes算法的主要设计指标是抗差分和线性分析能力。因此，一些基于差分和线性分析的攻击很难在aes算法的基础上取得实质性进展。最近,代数攻击已经成为对AES最有希望的分析方法,很多人将希望寄托于代数攻击,因此代数攻击深受当前密码学界的广泛关注.最简洁的代数攻击由两步组成:第一步是建立一个简单的代数方程组,该方程组描述密码系统的明文、密文和密钥是怎样关联的;第二步通过一些已知的明密文来求解方程组以获取密钥.第一步已经得到研究者的一些关注,他们以不同的方式描述AES算法:Ferguson等把AES算法描述为有限域GF(28)上一个简单的,非常结构化的非线性方程,该方程对10轮的AES算法共有250项;Courtois等通过建立GF(2)上含有8000个二次方程和1600个变量的方程组来描述AES;Murphy等得出一个GF(28)上非常稀疏的超定多变量二次方程组,且有充分的理由认为该方程组比GF(2)上相应的方程组更容易求解;文献给出了一个GF(28)上描述AES更简单的方程组,求解该方程组比求解Murphy-Robshaw的方程组复杂度更低.第二步中的求解多变量二次方程组仍然是一个研究中的问题,且被认为是NP难问题.但如果方程组是超定的(方程个数多于未知变元数),求解方程组的复杂性可被降低;而且,如果方程是稀疏的且有规则的代数结构,通过应用XSL(eXtendedSparseLinearization)技术,复杂性还可被进一步降低.S盒作为分组密码中最重要的非线性部件,怎样利用二次方程来描述S盒是一个值得研究的问题.本研究在文献的基础上,分析了n×n的S盒在域GF(2n)上的二次方程存在条件,接着给出描述AES的S盒二次方程组,这个方程组是稀疏且超定的.最后,根据S盒的二次方程存在条件,给出了一个新的S盒设计准则.1预测的能力模型t-12n设GF(2)n→GF(2)n是一个n×n的S盒F:x=(x0,x1,…,xn-1)→y=(y0,y1,…,yn-1),记GF(2)上的一个多变量二次方程为P(x0,x1,…,xn-1,y0,y1,…,yn-1),r为所有形如P(x0,x1,…,xn-1,y0,y1,…,yn-1)的线性无关二次方程的个数,由这些方程组成的方程组中,t为出现在方程组中的项的个数,包括常数项1.一般情况下,有t≈n2n2.根据文献,有定义1和定义2如下.定义1对于一个二次方程,如果有t≪n2n2,则这个方程是稀疏的.当r≈n时,这些方程给出关于S盒的足够信息,即对于给定的y=F(x),给一个x,使方程组被足够定义以产生一个解.定义2在一个方程组中,如果r≫n,则这个方程组是超定的.对于给定的一个n×n的S盒,本研究的目标是得到一个超定的多变量二次方程组.在文献中,在GF(2)上的每个二次方程中,所有可能出现的二次项是{1,x0,x1,…,xn-1,y0,y1,…,yn-1,…,xn-1yn-1,…,xn-2xn-1,…,yn-2yn-1},总数为t=2n2+n+1.对每个可能的二次方程,记{c0,c1,…,ct-1}为一组含t个项的二进制系数,对每个可能的输入x(0≤x≤2n-1),计算这t项的值记为{ax,0,ax,1,…,ax,t-1}.把{c0,c1,…,ct-1}作为未知元,可以写出一个具有2n个方程的方程组:⎛⎝⎜⎜⎜⎜⎜a0,0a1,0⋮a2n−1,0a0,1a1,1⋮a2n−1,1⋯⋯⋯a0,t−1a1,t−1⋮a2n−1,t−1⎞⎠⎟⎟⎟⎟⎟⎛⎝⎜⎜⎜⎜c0c1⋮ct−1⎞⎠⎟⎟⎟⎟=⎛⎝⎜⎜⎜⎜00⋮0⎞⎠⎟⎟⎟⎟(1)(a0,0a0,1⋯a0,t-1a1,0a1,1⋯a1,t-1⋮⋮⋮a2n-1,0a2n-1,1⋯a2n-1,t-1)(c0c1⋮ct-1)=(00⋮0)(1){c0,c1,…,ct-1}的每个可能的非零解构成S盒的一个二次表达,记A为式(1)中ai,j构成的矩阵(0≤i≤2n-1,0≤j≤2n-1),其秩为R(A).有R(A)≤min(2n,t)≤min(2n,2n2+n+1).当n≤6时,有R(A)≤2n<t.假设一个S盒使得R(A)=2n,那么对式(1)进行高斯消元,可以得到2n项系数ci(0≤i<t)的表达式,不失一般性,假设为前2n项c0,c1,…,c2n-1,则⎛⎝⎜⎜⎜⎜⎜b0,0b1,0⋮b2n−1,0b0,1b1,1⋮b2n−1,1⋯⋯⋯b0,t−2n−1b1,t−2n−1⋮b2n−1,t−2n−1⎞⎠⎟⎟⎟⎟⎟⎛⎝⎜⎜⎜⎜c2nc2n+1⋮ct−1⎞⎠⎟⎟⎟⎟=⎛⎝⎜⎜⎜⎜c0c1⋮c2n−1⎞⎠⎟⎟⎟⎟(2)(b0,0b0,1⋯b0,t-2n-1b1,0b1,1⋯b1,t-2n-1⋮⋮⋮b2n-1,0b2n-1,1⋯b2n-1,t-2n-1)(c2nc2n+1⋮ct-1)=(c0c1⋮c2n-1)(2)式中:b0,0,b0,1,…,b0,t-2n-1,…,b2n-1,t-2n-1是二进制常数,可通过消元法得到.因此方程组的自由未知元个数是t-2n,其基础解系中有t-2n个线性无关的向量来表达所有的解:⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜c0c1⋮c2n−1c2nc2n+1⋮ct−1⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟=c2n⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜b0,0b1,0⋮b2n−1,010⋮0⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟+c2n+1⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜b0,1b1,1⋮b2n−1,101⋮0⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟+⋯+ct−1⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜b0,t−2n−1b1,t−2n−1⋮b2n−1,t−2n−100⋮1⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟(3)(c0c1⋮c2n-1c2nc2n+1⋮ct-1)=c2n(b0,0b1,0⋮b2n-1,010⋮0)+c2n+1(b0,1b1,1⋮b2n-1,101⋮0)+⋯+ct-1(b0,t-2n-1b1,t-2n-1⋮b2n-1,t-2n-100⋮1)(3)根据文献中的分析,当R(A)=2n时,S盒有r=t-2n个线性无关的二次方程,通过上述方法可求出r个线性无关的解{c0,c1,…,ct-1},从而求出r个相对应的二次方程.总结文献有如下结论.结论1对于上述的n×n的S盒,GF(2)上无关的二次方程个数是r:1)如果R(A)<t,有r=t-R(A),否则r=0;2)如果(t-R(A))≫n,存在GF(2)上的一个超定方程组.2exmam、ymos,xys,xys一般情况下,在GF(28)上描述AES的二次方程组比GF(2)上的更简单,用XSL技术更容易求解.因此,对于一个n×n的S盒,GF(2n)上的二次方程组更应该被考虑.对于一个n×n的S盒,假设S盒的输入和输出分别为x和y,其中x,yue84aSymbolNCpGF(2n).假设xm+1=x2mm2,ym+1=y2mm2,其中:0≤m<n,m+1为模n运算.那么可以把上述S盒看成GF(2n)上一个n×n的S盒:其输入为x0,x1,…,xn-1,输出为y0,y1,…,yn-1.于是,关于S盒的所有变量xm和ym,总共可能出现的二次项是{1,xm,ym,xmys,xpxq,ypyq},其中,0≤m<n,0≤s<n,0≤p≤q<n,其总数为t=2n2+3n+1.S盒的所有可能输入数为2n,因此通过假设变量,用上一节的方法,可以得到一个2n×t的矩阵,记这个GF(2n)上的矩阵为B,通过计算可获取矩阵B的秩R(B),当(t-R(B))≫n时,存在GF(2n)上的超定方程组,相似于结论1,有结论2.结论2对于上述的n×n的S盒,GF(2n)上无关的二次方程个数是r:1)如果R(B)<t,有r=t-R(B),否则r=0;2)如果(t-R(B))≫n,存在GF(2n)上的一个超定方程组.对于一个4×4的S盒,在GF(2)上所有可能的输入为x=(x0,x1,x2,x3),共有2n=16个,所有GF(2)上的二次单项式个数为t=2n2+n+1=37:{1,x0,x1,x2,x3,y0,y1,y2,y3,x0y0,x0y1,x0y2,x0y3,x1y0,x1y1,x1y2,x1y3,x2y0,x2y1,x2y2,x2y3,x3y0,x3y1,x3y2,x3y3,x0x1,x0x2,x0x3,x1x2,x1x3,x2x3,y0y1,y0y2,y0y3,y1y2,y1y3,y2y3}.于是得到一个16×37的矩阵A,其秩至多为16.根据结论1,无论S盒怎么定义,将至少有r≥t-2n=21个二次方程存在.从而得到一个GF(2)上非常超定的二次方程组.在GF(24)上,有t=2n2+3n+1=45,且R(B)≤16,由结论2,也可得到一个含有29个二次方程的超定方程组.对于一个8×8的随机S盒,有2n=256,可计算出所有二次项的总数为t=137,有2n≫t,所以不期待碰巧有任何可用的性质存在,如文献中给出的10个随机产生的8×8S盒不存在任何二次方程.然而,由于AES的S盒具有丰富的代数机构,因此可能产生非常特别的有用性质,关于AES的二次方程将在下面介绍.3aes的第二个平方本节将分别在GF(2)和GF(28)上讨论关于AES密码S盒的二次方程.3.1++4.5+5+5+1+5+1+5+1+2+5+1+2+2+5+5+1+2+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+1+5+5+5+1+5+5+1+5+5+1+5+5+1+5+5+1+5+5+5+1+5+1+5+5+1+5+1+5+1+5+5+1+5+5+5+5+1+5+5+5+5+5+5+5+5+5+5+5+5+5+5+1+2+5+2+5+1+5+1+5+1+5+2+5+5+1+5+5+1+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+5+2+5+2+5+1+5+2+5+1+5+2+5+5+1+5+1+5+2+5+5+5+5+5+1+5+2+5+5+5+5+1+5+5对于AES的S盒,通过计算关于S盒的t,A及R(A),再根据结论1,有结论3.结论3对于AES的S盒,通过计算,有R(A)=98,t=137.因此存在一个GF(2)上的超定方程组,这个方程组由39个GF(2)上线性无关的二次方程构成.这39个二次方程可由第2节中求取线性方程组基础解系的方法计算出,也可通过S盒的定义求出.AES的S盒可定义为两个变换的合成S=fg,其中:f为一个GF(2)上的可逆仿射变换,g为GF(28)上的乘法逆变换,其中0元素映射到自身.对于一个S盒的输入x=(x0,x1,…,x7),有输出z=f(g(x))=f(y),其中y=(y0,y1,…,y7),z=(z0,z1,…,z7).当x≠0时,有GF(28)上的方程xy=1,再通过GF(2)上的仿射变换f对方程中y元素的作用,可得出GF(2)上相应的8个分位的二次方程:x0z2+x0z5+x0z7+x1z1+x1z4+x1z6+x2z0+x2z3+x2z5+x3z2+x3z4+x3z7+x4z1+x4z3+x4z6+x5z0+x5z1+x5z2+x5z4+x5z5+x5z6+x6z0+x6z3+x6z5+x6z6+x6z7+x7z2+x7z4+x7z5+x7z6+x7z7+x0+x6=1,x0z0+x0z3+x0z6+x1z1+x1z2+x1z4+x1z5+x1z6+x1z7+x2z0+x2z1+x2z3+x2z4+x2z5+x2z6+x3z0+x3z2+x3z3+x3z4+x3z5+x3z7+x4z1+x4z2+x4z3+x4z4+x4z6+x4z7+x5z0+x5z2+x5z3+x5z4+x5z5+x6z1+x6z2+x6z3+x6z4+x6z7+x7z0+x7z2+x7z3+x7z4+x1+x6+x7=0,x0z1+x0z4+x0z7+x1z0+x1z3+x1z6+x2z1+x2z2+x2z4+x2z5+x2z6+x2z7+x3z0+x3z1+x3z3+x3z4+x3z5+x3z6+x4z0+x4z2+x4z3+x4z4+x4z5+x4z7+x5z1+x5z2+x5z3+x5z4+x5z6+x5z7+x6z0+x6z2+x6z3+x6z4+x6z5+x7z1+x7x2+x7z3+x7z4+x7z7+x0+x2+x7=0,x0z0+x0z2+x0z5+x1z6+x1z7+x2z5+x2z6+x3z1+x3z5+x3z6+x4z0+x4z4+x4z5+x5z1+x5z3+x5z6+x5z7+x6z0+x6z1+x6z2+x6z4+x6z5+x7z0+x7z3+x7z6+x7z7+x1+x3+x6=0,x0z1+x0z3+x0z6+x1z0+x1z1+x1z2+x1z4+x1z5+x1z6+x2z0+x2z3+x2z5+x2z6+x2z7+x3z2+x3z4+x3z5+x3z6+x3z7+x4z3+x4z5+x5z1+x5z2+x5z6+x6z0+x6z1+x6z5+x7z0+x7z1+x7z6+x7z7+x2+x4+x6+x7=0,x0z2+x0z4+x0z7+x1z1+x1z3+x1z6+x2z0+x2z1+x2z2+x2z4+x2z5+x2z6+x3z0+x3z3+x3z5+x3z6+x3z7+x4z2+x4z4+x4z5+x4z6+x4z7+x5z3+x5z5+x6z1+x6z2+x6z6+x7z0+x7z1+x7z5+x3+x5+x7=0,x0z0+x0z3+x0z5+x1z2+x1z4+x1z7+x2z1+x2z3+x2z6+x3z0+x3z1+x3z2+x3z4+x3z5+x3z6+x4z0+x4z3+x4z5+x4z6+x4z7+x5z2+x5z4+x5z5+x5z6+x5z7+x6z3+x6z5+x7z1+x7z2+x7z6+x4+x6=0,x0z1+x0z4+x0z6+x1z0+x1z3+x1z5+x2z2+x2z4+x2z7+x3z1+x3z3+x3z6+x4z0+x4z1+x4z2+x4z4+x4z5+x4z6+x5z0+x5z3+x5z5+x5z6+x5z7+x6z2+x6z4+x6z5+x6z6+x6z7+x7z3+x7z5+x5+x7=0.上述8个方程中,第一个方程当且仅当x≠0时正确,正确的概率为255/256,其它7个正确的概率均为1.其余的32个概率为1的方程可分别由xy128=x128,yx128=y128,x4y=x3,y4x=y3通过相同方法求出,详细方程组及利用该方程组进行的攻击可参考文献.3.2u3000x-1+0x-1+3+8x-1+33用第3节的方法假设S盒在GF(28)上的变量,通过计算关于S盒的t,B及R(B),再根据结论2,有结论4.结论4对于AES的S盒,通过计算,有R(B)=98,t=153,因此存在一个GF(28)上的超定方程组,这个方程组由55个GF(28)上线性无关的二次方程构成.经过计算,发现这个方程组较为复杂,因为有的方程中含有太多的项(有的方程含有项数达79).下面将通过S盒的代数表达式,给出一个较为简单的二次方程组,该方程组中的每个二次方程最多含有二项,因此是极端稀疏的.根据有限域GF(28)上的性质x255=1及拉格朗日插值公式,S盒的代数表达式可写为S(x)=05x254+09x253+…+8Fx127+63=05x-1+09(x-1)2+…+8F(x-1)27+63=05y0+09y1+…+8Fy7+63.其中:y0=x-1,y1=(x-1)2,y2=(x-1)22,…,y7=(x-1)27,式中系数为16进制;可以简记为S(x)=g(y0,y1,…,y7),它是一个关于变量(y0,y1,…,y7)的线性方程.再次假设xm+1=x2mm2(0≤m≤7),因此可得一个GF(28)上的S盒,这个S盒的输入为xm,输出为ym,对这个S盒的输出ym实施线性变换z=g(y0,y1,…,y7),可得到原始AES的S盒的输出,线性方程z=g(y0,y1,…,y7)可看作是所假设的S盒之后的又一个线性变换.根据结论2,计算出相应的t,B及R(B),同样有结论5.结论5对于具有上述输入和输出的S盒,通过计算,有R(B)=98,t=153,因此存在一个GF(28)上的超定方程组,这个方程组由55个GF(28)上线性无关的二次方程构成.通过计算,可以得到上述55个二次方程.加上一个线性方程,可得到一个方程组来描述AES的S盒,这个方程组是极端稀疏的,且是超定的.这个方程组由下面的56个方程构成如下(m+1为模8加运算):⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪xmym+x0y0=0,1≤m≤7x2m+xm+1=0,0≤m≤7y2m+ym+1=0,0≤m≤7xmym+1+ym=0,0≤m≤7ymxm+1+xm=0,0≤m≤7xmym+2+ymym+1=0,0≤m≤7ymxm+2+xmxm+1=0,0≤m≤7z+g(y0,y1‚⋯,y7)=0(4){xmym+x0y0=0,1≤m≤7xm2+xm+1=0,0≤m≤7ym2+ym+1=0,0≤m≤7xmym+1+ym=0,0≤m≤7ymxm+1+xm=0,0≤m≤7xmym+2+ymym+1=0,0≤m≤7ymxm+2+xmxm+1=0,0≤m≤7z+g(y0,y1‚⋯,y7)=0(4)利用GF(28)上的二次方程组进行的代数攻击及有关攻击的复杂性可参考文献.4随机88的s盒要开始对一个密码实施代数攻击,如XSL攻击,一个必要的条件是S盒必须可以描述成一个具有r个二次方程、t个项(包括一个常数项)的超定二次方程组.因此,如果一个S盒不能用超定的二次方程组来描述,这样的S盒就可以抵抗XSL攻击.这个方法可以被密码设计者利用以确保:即使XSL技术变成一种可实践的方法,拥有如此设计S盒的密码仍然对这种攻击是免疫的.这个思想暗示了一种新的S盒设计准则.对于一个4×4的S盒,注意到在GF(2)上当n=4时,有R(A)≤2n<t,且t-R(A)≫n.因此存在超定的二次方程组,这样的S盒对于XSL攻击不是免疫的.而对于随机8×8的S盒,这是完全可能的.一般情况下,当n=8时有R(A)≥t.因此对于随机产生的8×8的S盒,不存在有效的二次关系,结果XSL攻击完全无效,故分组密码中的S盒不应该设计得太小.第3节式(4)中,AES的S盒可被一个GF(28)上的超定方程组描述.一般情况下,