ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.202-206



LOKI97
ᡡǹ˹
ժҪLOKI97˹,ʾ,LOKI97İȫԲûдﵽ߼ܱ׼Ҫ;е㷨1250Ķ,0.977ĳɹԤ92Կ;е㷨2245Ķ,0.967ĳɹԤLOKI97Կ.
ؼʣ,Աƽ,Զ.
ţTP309
Linear Cryptanalysis of LOKI97
WU Wen-lingLI BaoFENG Deng-guoQING Si-han
(Engineering Research Center for Information Security Technology The Chinese Academy of Sciences,Beijing,100080)
WU Wen-lingLI BaoFENG Deng-guoQING Si-han
(State Key Laboratory of Information Security Institute of Software The Chinese Academy of Sciences,Beijing,100080)
AbstractIn this paper,LOKI97 is analyzed using linear cryptanalysis.The results show that LOKI97 does not meet the needs of AES (advanced encryption standard).Using algorithm 1 of linear cryptanalysis,the authors can get the 92bit subkey with 250 known-plaintexts and the success rate is 0.977; using algorithm 2 of linear cryptanalysis,it is possible to break LOKI97 with 245 known-plaintexts and the success rate is 0.967.
Key wordsLinear cryptanalysis,linear approximation,nonlinearity.
LOKI97ұ׼о(NIST)1521͸߼ܱ׼(advanced encryption standard,AES)ĺѡ㷨֮һ,LOKIϵ²Ʒ.BihamShamirף1жLOKI89˷,ʾ,ȻLOKI89ټֱܲĹ,ȫ16ֵLOKI89ȴĹ.Tokita SorimachiMatsuiף2жLOKI91Խ,12ϵLOKI91ǰȫ.LOKI97ѡȡS-еķܷǳ,S1Աƽĸp:,S2Աƽĸp:.ɴ,ף3ݸн:
.ֵԱƽpbest:;
.14LOKI97Աƽpbest:;
.16LOKI97Աƽpbest:.
ף4ݺĽ,ԹƳLOKI97ĶԴԼΪ2282.ƺӳLOKI97ߵ,ȻʵȴȻ,ڱ,LOKI97ֺص,ĳЩԿֵԱƽ,ǽ漰Կ,Ȼá+ͱλ,ѵֵԱƽ,14ֺ16LOKI97Աƽ,ǵĸpֱ:

ЩԱƽ,ǶLOKI97.
1 LOKI97㷨
LOKI97ķ鳤Ϊ128,ԿΪ128,192,256.õ16ֵFesitelṹ.
1.1 ܹ
1.1.1 㷨ṹ
P=L0|R0Ϊ128ص,зʽ,j=1,...,16,
Ri=Li-1F(Ri-1+K3i-2,K3i-1),
Li=Ri-1+K3i-2+K3i
C=R16|L16Ϊ.
1.1.2 ֺF
ֺF:F642F642F642,
F(A,B)=Sb(P(Sa(E(KP(A,B))),B).
KP(A,B)һ򵥵Կû,64Aֳ32,BĽϵ(ұ)32ȷǽЩбصӦλ(Կ1),ǲ(ԿΪ0).
Eһչ,E64вһ96ֵ.
4-0,63-56|58-48|52-40|42-32|34-24|28-16|18-8|12-0.
SaɺS1ͺS2ù,Sa=S1,S2,S1,S2,S2,S1,S2,S1,SaE.
Pأ63-0ӳ䵽:
56,48,40,32,24,16,08,00,57,49,41,33,25,17,09,01,
58,50,42,34,26,18,10,02,59,51,43,35,27,19,11,03,
60,52,44,36,28,20,12,04,61,53,45,37,29,21,13,05,
62,54,46,38,30,22,14,06,63,55,47,39,31,23,15,07,
63ת56,62ת48.
SbɺS1ͺS2ù,Sb=S2,S2,S1,S1,S2,S2,S1,S1,Sb
B63-61|P63-56,B60-58|P55-48,B57-53|P47-40,
B52-48|P39-32,B47-45|P31-24,B44-42|P23-16,
B41-37|P15-8,B36-32|P7-0,
B63-61ݱʾBĵ6361ɵıش.Sbĵ1SS2ΪB63-61|P63-56.
1.2ܹ
C=R16|L16,Ȼֽв.i=1,...,16,
Li-1=RiF(Li-K3I,K3i-1),
Ri-1=Li-K3i-K3i-2,
P=L0|R0,Ϊ.
1.3 Կ
16LOKI97Ҫ4864صԿ,ԿKչΪԿ.,Կĳ,Ԥ464֣K40|K30|K20|K10.
K=Ka|Kb|Kc|KdΪ256,K40|K30|K20|K10=Ka|Kb|Kc|Kd;
K=Ka|Kb|KcΪ192,K40|K30|K20|K10=Ka|Kb|Kc|f(Ka,Kb);
K=Ka|KbΪ128,K40|K30|K20|K10=Ka|Kb|f(Kb,Ka)|f(Ka,Kb),
Ȼi=1,...,48¼:
Ki=K1i=K4i-1gi(K1i-1,K3i-1,K2i-1),
K4i=K3i-1,
K3i=K2i-1,
K2i=K1i-1,
gi(K1,K3,K2)=F(K1+K3+(Delta*i),K2),
Delta=(sqrt(5)-1)*263=9E3779B97F4A7C1516.
2 LOKI97Աƽ
S1(x12,...,x2,x1,x0)=(f7,f6,f5,f4,f3,f2,f1,f0):F132F82,ͨ,ǸS1ķ֧f0ĴʽΪ:

(x12,x11,x10,x9,x8)=i,0i31,ɵ32gi(x7,x6,x5,x4,x3,x2,x1,x0),ǵĺ:
WH(g0)=144,WH(g1)=128,WH(g2)=128,WH(g3)=128,WH(g4)=144,WH(g5)=128,
WH(g6)=128,WH(g7)=128,WH(g8)=128,WH(g9)=144,WH(g10)=128,WH(g11)=128,
WH(g12)=128,WH(g13)=112,WH(g14)=128,WH(g15)=128,WH(g16)=128,WH(g17)=112,
WH(g18)=128,WH(g19)=128,WH(g20)=128,WH(g21)=144,WH(g22)=128,WH(g23)=128,
WH(g24)=112,WH(g25)=128,WH(g26)=128,WH(g27)=128,WH(g28)=112,WH(g29)=128,
WH(g30)=128,WH(g31)=128.
Ȼ,g0,g4,g9,g13,g17,g21,g24,g28ǷƽĲ,,ǵķԶС16.ΪֺFSbÿһSе߼Կ,ԶĳЩԿ,ԸֺF(X,K)=YһΪҽ漰ԿԱƽ:
Y0=Kh(36-32),(1)
Kh(36-32)=h(k36,k35,k34,k33,k32),hԲ.
(Li-1,Ri-1)(Li,Ri)ֱǵiֵ,
Li=Ri-1+K1i+K3i,(2)
Ri=Li-1F(Ri-1,K2i).(3)
ʽ(2),иΪ1Աƽ:
Ei:Li0=Ri-10K1i0K3i0.
ʽ(3),ʽ(1),иΪԱƽ:
Di:Ri0=Li-10K2ih(36-32).
16ֵLOKI97,(L0,R0)(R16,L16)ֱ,ǹ켣ΪE1,D2,E3,D4,E5,D6,E7,D8,E9,D10,E11,D12,E13,D14,E15,D16Աƽ:
(4)
켣ΪD1,E2,D3,E4,D5,E6,D7,E8,D9,E10,D11,E12,D13,E14,D15,E16Աƽ:
(5)
ʽ(4)ʽ(5)ĸʶ:.
ӵ2ֿʼ,Թ켣E2,D3,E4,D5,E6,D7,E8,D9,E10,D11,E12,D13,E14,D15,E16Աƽ:
L00F(R0+K11,K21)0k=L160,(6)
,ʽ(6)ĸ:

3 LOKI97
ʽ(4),0.977ĳɹԤK2iĵ3632,iż,1i16;ʽ(5),0.977ĳɹԤK2iĵ3632,i,1i16.
ĶN=250.ʽ(4)Ϊ,취.
1.żj(1j16),̶ʽ(4)K2ih(36-32)(ij)h.
2.K2jh(36-32)=K2j32,ʽ(4)Ԥk0=kK2j32..
3.K2jh(36-32)=K2j33,ʽ(4)Ԥk1=kK2j33.
4.K2jh(36-32)=K2j32,33,ʽ(4)Ԥk2=kK2j32,33.
5.K2jh(36-32)=K2j32,33,34,ʽ(4)Ԥk3=kK2j32,33,34.
6.K2jh(36-32)=K2j32,33,34,35,ʽ(4)Ԥk4=kK2j32,33,34,35.
7.K2jh(36-32)=K2j32,33,34,35,36,ʽ(4)Ԥk5=kK2j32,33,34,35,36.
8.K2j32=k0k2,K2j33=k1k2,K2j34=k3k2.K2j35=k3k4,K2j35=k5k4.
㷨1,0.977ĳɹԤԿ92,ĶΪ250.棬ǶԿΪ128صLOKI97㷨2з.K=(K1,K2),Կɵķ:
(7)
Ǽٶ֪K11K21,Ӵ˷K1K2Ƚ.
ΪF(R0+K11,K21)0K213763޹,ΪK213236֪,,K11,K21Ŀֵ296.,ʽ(6)ף4е㷨2,ԤK11K21ĵ32,ĶΪ245,ɹ0.967;Ȼ,K21ֵ227,ⷽʽ(7);,ĶԼõĽǷΪԿ.
4 
ĶLOKI97,ʾLOKI97İȫԲûϣôǿֺĽ漰ԿԱƽ,FeistelĽṹ,ĳЩԿ14ֺ16LOKI97Աƽ,Դ˶LOKI97з.ɴ,ָ:ʱ,ֺӦ֤Կĳֻ,ʹù߹첻漰ԿЧԱƽ.
ĿоõȻѧ(No.69673016)͹Ҳʿ.
߼飺,Ů,1966,ʿ,ҪоΪ.
,1962,ʿ,ҪоΪԲ߹ԿƵķʵ.
ǹ,1965,оԱ,ҪоΪϢȫ.
˹,1939,оԱ,ʿʦ,ҪоΪϢȫ.
ߵλ(йѧԺϢȫоġ100080)
(йѧԺϢȫоġ100080)
ǹ(йѧԺϢȫоġ100080)
˹(йѧԺϢȫоġ100080)
(йѧԺоϢȫصʵҡ100080)
(йѧԺоϢȫصʵҡ100080)
ǹ(йѧԺоϢȫصʵҡ100080)
˹(йѧԺоϢȫصʵҡ100080)
οף
1Biham E,Shamir A.Differential cryptanalysis Snefru,Kharfe,REDOC-II,LOKI and Lucifer,Vol.576.Lecture Notes in Computer Science,Berlin:Springer-Verlag,1991.156171
2Toshio Tokita,Tohru Sorimachi,Mitsuru Matsui.Linear cryptanalysis of LOKI and S2DES,Vol.917.Lecture Notes in Computer Science,Berlin:Springer-Verlag,1994.363366
3Lawrie Brown.LOKI97,http://csrc.ncsl.nist.gov/encryption/aes/aes-home.htm
4Mitsuru Matsui.Linear cryptanalysis method for DES cipher,Vol.765.Lecture Notes in Computer Science,Berlin:Springer-Verlag,1993.368397
ոڣ1998-12-15
޸ڣ1999-03-17
