分组密码的分区线性分析法

分组密码的分区线性法 分组密码的分区线性分析法 第18卷第3期 2007年9月 中国计量学院 JournalofChinaJiliangUniversity VoI.18NO.3 Sep.2007 【文章编号11004—1540(2007)03—0181—05 分组密码的分区线性分析法 侯宇,闫勇,苏开宇 (中国计量学院网络中心,浙江杭州310018) 【摘要】提出了用于分组密码分析的分区线性分析法.以SAFER++为例,通过基础模块的密码特性分 析,建立密码分析的线性逼近式.该逼近式的特点是把密钥的比特位分区出现在逼近式的任选项中,这样不仅 可以攻击密钥的所有比特位,而且大大降低了攻击的复杂度,并从理论上证明了逼近式的优势与任何子密钥 的最低有效位无关.迄今为止有关文献都认为相关子密钥最低有效位等于0是逼近优势非零的前提条件. 【关键词】密码分析;分区线性分析法;线性逼近;最低有效位;分组密码 【中图分类号1TP309.7【文献标识码】A Partitionlinearcryptanalysisforblockcipher HoUYu,YANYong,SUKai—yu (NewworkCenter.ChinaJiliangUniversity,Hangzhou310018,China) Abstract:Acryptanalysismethodcalledpartitionlinearcryptanalysisforblockciphersispres entedinthis paper.WiththecaseofSAFER++asanexample,thespeciallinearapproximationswereobtai nedbyanaly- zingthebasicmodules.Inthsesapproximations,thebitsofamasterkeyweredividedintoseveralpartsand couldbearbitrarilyselectedtOattackSAFER++.ItiSpossiblethatal1ofthekeybitscanbedeterminedand theattackcomplexityisgreatlyreducedatthesametime.Itisalsotheoreticallyprovedthatthebiasoflinear approximationshavenorelationwiththeleastsignificantbitofeverysubkey.Thisisanewconclusion.Many papersSOfarhavereportedthattheleastsignificantbitofcorrelativesubkeysshouldbe0forthebiasholding. Keywords:cryptanalysis;partitionlinearcryptanalysis;linearapproximation;theleastsignificantbit;block cipher 线性密码分析[1是一种常用的已知明文攻 击方法,由Matsui和Yamagishi发明,被广泛用 于分组密码系统的分析.这种方法可用2.个已知 明文破译8轮DES,可用2个已知明文破译16 轮DES.抗线性分析已成为分组密码的重要 指标之一. 线性密码分析的基本思想是寻找给定密码算 法的有效线性逼近来破译密码系统.线性逼近仅 涉及明文P,密文C和密钥K,且成立的概率p? 1/2,用lp一1/2l来刻画线性逼近的有效性,称之 为线性逼近的逼近优势.在实际中对,z轮迭代密 码进行线性密码分析时,常使用(,z一1)轮密码的 【收稿日期12007—06—08 【作者简介】侯宇(1958一),男,浙江温州人,教授,主要研究方向为信息安全理论与 技术研究 182中国计量学院第18卷 线性逼近;也就是说,假定已知最后一轮子密钥 K,构造如下线性逼近: Pri,…,i.]?c,…,五]?G(C,K)[P",ed] = KEk..'是](1) 式(1)中A[,J,…,是]一AEi]?A[]?…?A [是],AEi]是A的第i比特;"?"是异或运算符. 式(1)的有效性与G函数及K有关.如果在式 (1)中代入一个不正确的候选者K,那么这个等 式的有效性显然就降低了.因此,文献[2]给出如 下算法预测K和K[是,…,是] 第1步对K的每一个候选者K(i一1, 2,…),设是使得式(1)左边等于0的明文个数. 第2步一max{},一min{}. 如果ITm一N/2I>ITm一N/2I,那么将T…所 对应的密钥候选者作为K,并猜定KEk,…,是] 一0(当>1/2时)或KEk,…,是]一1(当<1/ 2时).如果ITm一N/2I<ITi一N/2I,那么将 Tmi所对应的密钥候选者作为K,并猜定K[是, … ,是]一1(当>1/2时)或KEk1,…,是]一0(当 <1/2时).其中N是给定的随机明文的个数. 逼近式(1)通常只能分析密钥的若干比特位, 而不能破译密钥的所有比特位;而且密码分析的 复杂度随子密钥K所取比特位数的增加而呈几 何增长.本文将以SAFER++为例寻找如下形式 的线性逼近式: CEj一,]?G(P,K[是…,是])[, … ,P]?(0,G(P,KEk,…,])[,…,], G(P,KEky1'…,是])[y1'…,P7],…>一0(2) 其中括号"(>"内是任选项;{是,…,是.,),{是,…, ),{是,…是),…是密钥比特位的子集,而它 们的并集等于密钥比特位的全集.利用上式我们 可以将密钥按比特位划分子集进行攻击,这样既 降低了攻击的复杂度,又能分析密钥的所有比特 位.由此,本文称之为分区线性分析法. 在线性密码分析中有一个非常有用的堆积引 理(piling—uplemma): 堆积引理:设X(1??)是独立的随机变 量,p(X一0)一P,p(X一1)一1一P,则 p(X?x.?…?x一o)一1/2+2一If[(一1/2) f一1 (3) 1SAFER++分组密码 SAFER++的整体结构是SP网络,分组 长度为128比特,密钥长度为128或256比特.本 文采用128比特的密钥. 令密文X和子密钥K为] X一(XX.X.XXXXX.X.X.X"X.X.X"XX) ?()" K一(K1n.2n.3n4n5n6n.7n.8n9n1.KK.K.KKK ?()" 子密钥"加" K:(F;)?一(F2)?X一K(X) 当i为奇数时,有 K(X)一(X?K,X+K,X.+K,K ?K,X?K,…,X"+K,X??K) 当为偶数时,有 K(X)一(X+K,X?K,X.?K,X +K,X+K,…,X?K,X?+K) 这里"?"是异或运算;"+"是模256加运算. 两个S盒: S1:F;一F;y—s1(y)一ymod257,约定S(128)一0 S2:F;一y—s2(y)一log5(y),约定S2(o)一128 混淆层: S:(F2)?一(F2)?X—S(X) S(X)一(S(X),S2(X),S2(X.),S1(X), S1(X),…,S2(X),S1(X)) 扩散层: P:(F2)?一(F;)?X--~-P(X)一PP1PP1(X) 其中 P:(F2)?一(F2)?X—P1(X)一(X.XX. XXXXX.XXXXX.X.XX) P:(F2)?一(F2)?X—P(X)一(PHT (XXX.X),PHT(XXXX.),PHT(X.X. X"X),PHT(X.XXX)) PHT:()一()XYZ一PHT(X 一 (2X+y+Z+V,X+2y+Z+V,X+y+2Z +V,X+y+Z+W) 子密钥的生成算法比较冗长,详见文献[3],此处 不赘述. ,2轮SAFER++加密算法为 E(X)一K. PKSK2一1…PK. SPaKPaKSat l4Jl (X) 第3期侯宇,等:分组密码的分区线性分析法183 2基础模块的密码特性 2.1模256加运算[ 设字节A的比特位为A一(n,…,a.,a.),对 于模256加运算Z—X+yrood256,有如下的线 性逼近及其优势: bias(Z[O]一x[0]oy[0]一2 bias(Z[1]一xD]?y[1]?<0,X[0],y[0], x[0]?y[0]>)一2(4) 这里用bias(L)示线性逼近式L的逼近优 势.为了书写简洁,在不引起歧义的前提下,将略 去逼近式中的异或运算符"?". 当模256加运算中的一个变量为常数时,比 如y等于常数K,则有 bias(z[0]一x[0])一2(5) bias(Z[1]一(x[0]?K[0])xD])一2(6) 2.2Sl和S:的密码特性_5] 对于y—s(X)和Z—s.(X),有如下的线性 逼近及其逼近优势: bias(Y[1]一x[0]一2一,bias(Y[1]一xD]一2 bias(Z[O]一xD]一2一,bias(Z[1]一x[1]一2一, bias(ZE0]Z[1]一xr1])一2(7) 2.3P变换的密码特性 根据模256加运算的密码特性以及字节移位变 换的特点,Z—P(y)有如下的线性逼近及其优势: bias(Z[0]z.[0]z?[0]z?[0]z?[0])一 Y.[0]y"[0]y?Eo])一2(8) bias(Z3[1]z?[1]z?[1]?Arb{0,Z.[0], z"[0],z?[0])_-y[0]y.[0]y[1]y[1]yEo] Y[1]y?[1]?Arb{0,Y[0],YEo],Y?[0])) 一 2(9) bias([1]Z3[1]zaEo]z~[1][1][1]z"Eo] ?Arb{0,Eo]z~Eo],[o]Z6Eo],[o]Eo])一 ys[1]y.[1]y?[1]?Arb(0,Y.[0]y.[0],Y.[0] Y?[0])?One{Y[0]y?[0]y?[0],Y[0]y?[0] Y[0]y?[0],Y[0]y?[0]y"[0]y[0]y?[0], Y[0]Y3[0]y8[0]y[0]y"[0],y2[0]y[0] Y[0]y?[0]y?[0]y?[0]))一2(10) bias(Z2[I]Z3[I]ZsE0]Z~[1][1][1]Z"Eo] ?Odd(Eo],z3Eo],Z6[o],Eo])=y3[1]y9[1] Y"E1-]?Odd{y3Eo],y9Eo],Y"Eo])?One{y2Eo] Y"[0]y?[0],Y[0]y?[0]y[0]y?[0],Y[0] Y?[0]yn[0]y[0]y?[0],Y[0]y.[0]y[0] Y[0]y[0],Y[0]y[0]y[0]y?[0]y?[0] Y?[0]))一2(11) bias(Z[1]z.[1]Z.[0]Z?[1]z?[1]z?[1] ?Arb{0,ZEo],z.[0],z"[0],z?[0],z?[0]) 一y2[1]Y3[1]y6[1]y8[1]0Arbf0,y2Eo],y3Eo], YEo],Y[0])0One}Y"[0]y?[0],Y4[0]y[0] Y?[0],Y[0]y[0]y?[0]y?[0],Y[0]y"[0] Y?[0]y?[0],Y[0]y[0]y?[0]y[0]y?[0])) 一 2(12) 以上诸式中集合{..)前的关键词称之为"异 或操作符",其中Arb{)表示对集合中的任意多个 元素做异或运算;Odd{)表示对集合中任意奇数 个元素做异或运算;One{)表示任选集合中的一 个元素进行异或运算.例如y.[1]y.[1]y?[1]o Arb{0,Y.[0]y.[0],Y.[0]y?[0])等价于以下任 一 式: y.[1]y.[1]y?[1] y.[1]y.[1]y?[1]y.[0]y.[0] y.[1]y.[1]y?[1]y.[0]y?[0] Y.[1]y.[1]y?[1]y.[0]y?[0](13) 而Y.[1]y.[1]y?[1]oOdd{Y.[0],Y.[0],Y? [0])等价于以下任一式: Y.[1]y.[1]y?[1]y.[0] y.[1]y.[1]y?[1]y.[0] Y.[1]y.[1]y?[1]y?[0] y.[1]y.[1]y?[1]y.[0]y.[0]y?[0](14) 2.4单轮加密特性 设C一…P‰S(W)为SAFER++的一轮 加密,而且C=aK…(Z),Z—P(y),y一(X), X—S(w),利用上述基础模块密码特性和堆积引 理,得到以下逼近式及其优势: bias(C2[0]C3[0]c?[0]c?[0]c?[0])一 W3[1]w?[1]w?[1])一2.(15) bias(C.[1]c?[1]c?[1]一W[1]w.[1] W[0]w[1]w[1]w[1]w?[0])一2(16) bias(C2Elic3[1]c[0]c[1]c[1]c[1] c?[0]一W[1]w.[1]w.[0]w"[1]w?[1] W?[1])一2(17) bias(C2[1][1]c5[0][1]C[I]C8[1]C"Eo] 一 X.[1IX.[1]X"[1]?One{X.Eo]X"Eo]XEo], X[0]x"[0]x[0]x?Eo],x[0]X[0]X"[0] 184中国计量学院第18卷 x地r-o~x?[0],xr-o~x.r-o~xr-o~x[0]X吨[0], x[0]x[0]x[0]xn[0]xn[0]x?[0]))一2 (18) bias(C[1]C.[1]C.[0]C?[1]CH[1]C?[1] 一X[1]X3[1]X[1]X.[1]0One{X"[0]X"[0], x[0]x[0]x[0],xr-o~x.[0]xH[0]X[0], x[0]x?[0]xn[0]x"[0],x[0]x[0]xn[0] X地[0]X?[0]))一2(19) 以上各个逼近式的优势与任何子密钥的最低 有效位K0]无关!这是本文研究的重要结论之 一 ,现证明如下. 由密码特性(5)(7)(8)三式及堆积引理可以 直接证明式(15)成立.对于式(16),由密码特性 (6),得到 bias(C.[1]C"[1]CH[1]一(Z.[0]?K酣3. [0])Z.[1](Z?[0]?K—ll+.[0])Z"[1](Zn[0]? K4+.[0])ZH[1])一2(20) 由P变换的密码特性(9)以及操作符Arb{) 的特性,不管K;[0],K—ll+.[0],K.[0]是何 值,均有 bias((Z.[0]?K;r+1[0])Z.[1](Z?[0]? K.[0])Z"[1](Z?[0]?K酣14.[0])ZH[1])一 Yr-o~Y.[0]Y[1]y[1]Y[0]Y[1]yn[1]? Arb{0,Y[0],Y[0],Yn[0]))一2(21) 同理,以下逼近式成立且优势为2,: Y.r-o~y3[0]y[1]yr-1]y[0]y[1]yn[1] ?Arb{0,Y[0],Y[0],Yn[0])一x[0]x.[0] (X[0]?Ki[0])x[1]x[1]x[0](x[0]? K2,[0])x[1](xn[0]?K1;[0])xn[1]?Arb {0,x[0],X[0],xn[0])一x[0]x.[0]x[1] x[1]xr-o~xr-l~xn[1](22) 利用S盒的密码特性(7),有 bias(X[0]x.[0]x[1]x[1]x[0]x[1] xn[1]一Wr-l~w.[1]w[0]wr-l~w[1]?[1] Wn[0]一2(23) 综合式(20)一(23)并由堆积引理,式(16)得证. 类似的,对于式(17),有 bias(C~[1]C3[1]C5[0]C6[1]C[1]c8[1]C"[0] 一 (Z[0]?K;[0])Z[1](Z.[0]?K;[0]) Z.[1]Z[0](Z[0]?K2[0])Z[1](Z[0]? K;r+1[0])Z7r-l~zr-l~zn[0]=2(24) 当K;[0]K;r+1[0]K2[0]K;r+1[0]一0时,由 P变换特性(10)得到 bias(Z[0]?K酣z.[0])Z[1](Z.[0]?K; [0])Z.[1]Z[0]](ZEo]?K2r+1[0])Z[1] (Z[0]?K计7.[0])Z[1]Z[1]Zn[0]一Y[0] Y.r-l~Y.[1]y"[0]yH[1]y?[0]?Arb{0,Y.[0] Y.[0],y9[0]y?[0]))一2(25) 当K;+.[0]K;+.[0]K2.[0]K;r+.[0]一1时,则 由P变换特性(11)得到 bias(Z[0]?K;[0])Z[1](Z.[0]?K; [0])Z.[1]Z[0](Z[0]?K2[0])Z[1] (Z[0]?K;[0])Z[1]Z[1]Zn[0]一Y[0] Y.[1]y.[1]y"[0]y"[1]y?[0]?Odd{y3[0]? Y.[0],YH[0]))一2(26) 利用密码特性(6)和操作符Arb{),Odd{)的 特性,以下逼近式的优势为2 Y[0]Y.[1]y.[1]Y?[0]Y?[1]Y[0]? Arb{0,Y.Eo]y.[0],y9[0]y"[0])一xr-o] x.[1](x.[0]?K2,[0])x.[1]x"[0]xH[1] Arb{0,x.[0]X.[0],x.[0]xH[0]) x?[0]? rx[0]x.[1]x.[1]x?[0]x?r-l~x?[0] - - IasK[.]一.l[0][1]r-l~xn[0]xHr-l~xEo~x3[0] lasK9[0]一1 (27) Y[0]y3[1]y.[1]Y"[0]Y?[1]Y?[0]? Odd{y.[0],y.[0],yH[0])一x[0]x.[1] (x.[0]?K2[0])x.[1]x?[0]xH[1]x?[0]? Odd{x.[0],x.[0],xH[0]) r[0]r-l~x.r-l~x"r-o~x"[1]x?[0][0] IaSK9,[0]一0 1x[0]x.[1]x.r-13X"[03XH[1]x[0] laSK9[0]一1 (28) 根据S盒的密码特性(7),我们有 bias(X[0]x[1]x.[1]x"[0]x"[1]x"[0]0 Arb(0,X3[0])=W[1]w.[1]W.[O]W"[1]W"[1] W[1])一2(29) 综合式(24)一(29)并由堆积引理,式(17)成立. 类似地,可证明式(18)(19)成立,并且与子密 钥最低有效位无关. 在[4][6]等文献中,由于未注意到类似于式 (9)一(12)的密码特性,构造线性逼近式及其优势 第3期侯宇,等:分组密码的分区线性分析法185 时附加了相关子密钥最低有效位必须等于0的要 求,实际上是不必要的. 3分区线性分析法 利用式(15)一(19),建立分区线性分析法攻击 完整的3轮和4轮SAFER4-4-.设P一(PP. … P)?()?和C一(C1C2…C")?() 是系统的明文和密文,分析3轮SAFER4-4-的线 性逼近式为: C.[0]C.[0]c?[0]c?[0]c?[0]一s.(P.4- Kj)[1]?S(P.?K{)[1]?S.(Pn4-Kl)[I] ?One{S.(P.4-K})[0]?s.(Pn4-K1)[0]o s.(P?+Kj)[0],s(P?K})[0]?S.(Pn4- Kl)[0]?S(PoKj.)[0]oS.(P?4-Kl) [0],S.(P4-K{)[0]?S.(P4-Kl.)[0]oS. (Pn+Kj)[0]?S(PoKl.)[0]?S(Po K1)[0],S(PoKj)[0]?S.(P.4-K{)[0]? S(P.?K{)[0]oS.(P4-K1.)[0]?S(P ?Kj.)[0],S.(P.+K})[0]?S(P?K)[0] ?s.(P+Kj)[0]?S.(Pn+Kj)[0]?S(P? oK1.)[0]?S.(P+Kj)[0]}(30) 其优势为2..为了使攻击有高成功率,根据文献 [2]需要N一8?(2.)—2.个已知明文.4轮 SAFER++的线性逼近式为: C.[0]C.[0]c?[0]c?[0]c?[0]一s.(P.4- K})[1]os.(P.4-K})[1]oS.(P4-K{)[1]+ s(P.?K})[1]oOne{S.(Pn4-Kl)[0]os. (P?+K;)[0],s(P?K;)[0]oS.(P+Ki) [0]oS.(P4-Kl.)[0],S(P?Ki)[O]oS (P.oK})[0]?S.(P?4-Kl)[0]oS(P?? K{)[0],S(PoK{)[0]?S.(P"+K{)[0]? S(P"?Kl.)Eo]os.(P"4-K;)[0],S(P? Kj)[0]oS(P?Ki)[0]oS.(P?4-Kl)[0] os(P?Ki.)[0]?S.(P+Ki)[0])(31) 其优势为2.,攻击需要N一8?(2.)—2. 个已知明文. 在以上两式的右边,16个字节的主密钥K{ 被分属于不同的选择项.利用One{}的特性,我们 依次选用集合中的一个选项作为逼近式,用前文 的方法进行攻击.这样,每次攻击所涉及的最多只 有6个字节的密钥,大大降低了攻击的复杂度.由 此,攻击3轮SAFER4-4-所有16字节密钥的复 杂度为(2"+2.?+2?.+2.+ 2.)?2.攻击4轮SAFER4-4-所有16字节 密钥的复杂度为(2+2.+2.+2.瑚 +2.")?2..复杂度都小于直接攻击7个字 节密钥的复杂度. 4结论 本文通过对SAFER4-4-的基础模块密码特 性的分析,建立了分区密码线性分析的逼近式.该 逼近式的特点是把密钥的比特位分区块出现在逼 近式的任选项中,然后进行分区攻击.这样不仅可 以分析密钥的所有比特位,而且大大降低了分析 的复杂度.文章从理论上证明了逼近式及其优势 与任何子密钥的最低有效位无关,纠正了有关文 献要求子密钥最低有效位等于0的错误结论,使 得密码分析不受密钥最低有效位的取值限制,更 具通用性.攻击带输出变换的3轮加密需要2.个 已知明文,复杂度小于(2+2.)?2.攻击带输 出变换的4轮加密需要2.个已知明文,复杂度 小于(2+2.)?2. 对于其它分组密码系统,只要其基础模块具 有本文所述的密钥分区任选特性,都可以利用本 文方法进行密码攻击. 【参考文献】 L1JMATSUIM,YAMAGISHIA.Anewmethodforknown plaintextattackonFEALcipher[A]//AdvancesinCryptol— ogy,PreceedingsEurocrypt'92[C].INCS658,RA Rueppel,Ed,Springer—Verlag,1993181-91. [2]MATSUIM.IinearcryptanalysismethodforDEScipher [A]//AdvancesinCryptology,PreceedingsEurocrypt'93 [c].LNCS658,RARueppel,Ed,Springer—Verlag, 1994:386—397. [3]MASSEYJL,KHACHATRIANGH,KUREGIANM. TheSAFER++BlockEncryptionAlgorithm[EB/OL]. (2000一ll—l3)[2007,05—30].CylinkCorporation,available onhttpt{{Www.cryptonessie.org. [4]吴文玲,马恒太,唐柳英,等.5轮SAFER++的非线性密 码分析[J].电子,2003,31(7):961—965. [5]侯宇.SAFER一64的弱密钥[J].中国计量学院, 2007,17(1):2007:54—58. [6]NAKAHARAJ,PRENEELB,VANDEwALLEJ.Linear CryptanalysisofReduced-RoundSAFER++[EB/OL]. (2001—08—31)[2007—06—01].. org.