对轻量级密码算法MIBS的相关密钥不可能差分攻击

?35??2? 2014?2?

? ? ? ?

Journal on Communications

Vol.35 No. 2 February 2014

doi:10.3969/j.issn.1000-436x.2014.02.023

????????MIBS????????????

ч?ē??юē???

(?????? ?ˊ?┦??? 100083)

? ??????????????MIBS?????????????????MIBS-80????????????????????????????????????????10???????????????????????14??MIBS-80???????????????????????????????254???????256?

????????????MIBS???????????????

Ё?????TP309 ??????A ?????1000-436X(2014)02-0190-04

Related-key impossible differential attack

on a lightweight block cipher MIBS

CHEN Ping, LIAO Fu-cheng, WEI Hong-ru

(School of Mathematics and Physics, University of Science and Technology Beijing, Beijing 100083, China)

Abstract: The strength of MIBS algorithm against the related-key impossible differential attack was examined. MIBS is a lightweight block cipher algorithm. By using the key-expanding properties of MIBS-80 algorithm, a related-key differ-ential feature was presented and a 10-round impossible differential method was constructed by combining special ci-pher-plaintexts. Based on the impossible differential method, an attack to 14-round MIBS-80 algorithm was given, and the attack complexity both on data and on time were gained. Analysis results indicate the attack to MIBS of 14 rounds MIBS-80 algorithm needs 254 chosen plaintext operations and 256 encrypting computations. Key words: lightweight block cipher; MIBS algorithm; related-key; impossible differential attack

1 ??

???????RFID (radio frequency identi-fication)???????????⑤??????└???Ё???????????????????????????MIBS[1]??2009???????????????????⑤???????????????⑤?└??????????????????????????[2]????MIBS-64?13?????????[3]?MIBS???18???????14?????????????12????????????[4]????

?[3]Ё?MIBS?????????????????????????????[5]????MIBS?4?5?????????????????????8??9??Integral????????[6]??????????MIBS???8~11??Ё??????

???????????????????[7,8]????????[9]???????????????????????????????????????????????????????????????????????????????????????????AES[10,11]?LBLOCK[12]

?????2013-05-19??????2013-12-06

??-????????????-?(61174209, 61272476)???????????????????-?(2012)

Foundation Items: The National Natural Science Foundation of China(61174209, 61272476); The Oriented Award Foundation for Science and Technological Innovation, Inner Mongolia Autonomous Region(2012)

?2? ┌???????????MIBS???????????? g191g

???????Ё??????????????????????????MIBS-80??????????????

2 MIBS????????

MIBS???Feistel???????????

?????64 bit?

?????64 bit?80 bit?????????32?????????64 bit?80 bit?????????????????????????????MIBS-80?????????????MIBS-80???????? 2.1 ????

?64 bit?????P0=L0R0?L0,R320∈Z2

?

k32

i∈Z2

(1?i?32)??i??????MIBS??????????

1) ????(L0,R0)???4 bit???????????(nibble)??Ё??L0=(X0,8,X0,7,

X4

0,6,X0,5,X0,4,X0,3,X0,2,X0,1),X0,j∈Z2(1?j?8)???

2) ?i=1:32?Li=F(Li?1,Ki)⊕Ri?1?Ri=Li?1????F(Li?1,Ki)???????S????????P????Ё?S?4×4????S?????

??????P???.?????????P???????????L[5]

?(Yi,8,Yi,7,??,Yi,1)=

L(Xi,8,Xi,7,??,Xi,1)??Ё?

Yi,1=Xi,1⊕Xi,2⊕Xi,4⊕Xi,5⊕Xi,7⊕Xi,8? Yi,2=Xi,2⊕Xi,3⊕Xi,4⊕Xi,5⊕Xi,6⊕Xi,7? Yi,3=Xi,1⊕Xi,2⊕Xi,3⊕Xi,5⊕Xi,6⊕Xi,8? Yi,4=Xi,2⊕Xi,3⊕Xi,4⊕Xi,7⊕Xi,8? Yi,5=Xi,1⊕Xi,3⊕Xi,4⊕Xi,5⊕Xi,8? Yi,6=Xi,1⊕Xi,2⊕Xi,4⊕Xi,5⊕Xi,6? Yi,7=Xi,1⊕Xi,2⊕Xi,3⊕Xi,6⊕Xi,7? Yi,8=Xi,1⊕Xi,3⊕Xi,4⊕Xi,6⊕Xi,7⊕Xi,8 ?????L???????L?1???(Xi,8,Xi,7, ??,X?1i,1)=L(Yi,8,Yi,7,??,Yi,1)??Ё?

Xi,1=Yi,2⊕Yi,4⊕Yi,6⊕Yi,7⊕Yi,8? Xi,2=Yi,1⊕Yi,4⊕Yi,5⊕Yi,7⊕Yi,8? Xi,3=Yi,1⊕Yi,3⊕Yi,4⊕Yi,5⊕Yi,6? Xi,4=Yi,2⊕Yi,3⊕Yi,5⊕Yi,6⊕Yi,7? Xi,5=Yi,1⊕Yi,3⊕Yi,4⊕Yi,5⊕Yi,7⊕Yi,8? Xi,6=Yi,1⊕Yi,2⊕Yi,4⊕Yi,5⊕Yi,6⊕Yi,8?

Xi,7=Yi,1⊕Yi,3⊕Yi,5⊕Yi,6⊕Yi,7⊕Yi,8? Xi,8=Yi,1⊕Yi,2⊕Yi,3⊕Yi,4⊕Yi,6⊕Yi,7 3) ????Ci=(Li,Ri),1?i?32? 2.2 MIBS-80??????

????80 bit?????K??=(K??79,K??78

,??,K??0)???????32?32 bit????ki(1?i?32)??????

statei←K

????i=1,2,??,32? 1) statei=statei>>>19?

2) statei=S(stateii)statei

[79:76])S(state[75:72][71:0]

? 3) statei=(stateii[79:19])(state[18:14])⊕Round_counter statei

[13:0]?

4) ki

i=state[79:48]?

2.3 ????????

????[4]?????MIBS-80?????????????????

??1 ???????k1?????K??[18:0]?K??[79:67]???K??[18:0]K??[79:67]?k1????????K??[25:0]K??[79:74]?k14?K??[58:55]?k13,4?K??[21:18]?k2,4?

?Ё????Ё????????Ё????

3 ?14??MIBS????????????

????MIBS?10??????????????????????2?????2??????MIBS?14???? 3.1 ???????????

?MIBS-80???????????MIBS????????????????S?????????????????????????????S??????2??????????S?????????????????????2???S?????╘???????S????????????????????????????????

?????????K

??=(00000000000000080000)??ki(1?i?10)??????

(00000000)?(00002000)?(00000000)?(00000000)?(00000000)?(00020000)?

(00000000)?(00000000)?(00000000)?(00200000)?

???????????(00000000,00002000)??????????6????????1???

g192g ? ? ? ? ?35?

?1

????????????

??(i)

?Li?1 ?Ri?1 ?ki 1 00000000 00002000 00000000 2 00002000 00000000 00002000 3 00000000 00002000 00000000 4 00002000

00000000 00000000 5 t0ttt0tt 00002000 00000000 6

(c8c7c6c5c4c3c2c1)⊕

t0ttt0tt

0002000

(00002000)

??10????????????(00000000, 0020000)????5???????????2???

?2

????????????

??/i ?Li ?Ri ?ki 10 00000000 00200000 00200000 9 00200000 00000000 00000000 8 00000000 00200000

00000000 7 00200000

www00ww0

00000000 6

www00ww0

?R6

00020000

?Ё?ci(1?i?8), t, w??4 bit??????

??1??2??????????R6=?L5= (c8c7c6c5c4c3c2c1)⊕(00002000)?????????

?R6⊕?L7=(c8c7c6c5c4c3c2c1)⊕(02002000)?

??L?1

(?R6⊕?L7)=(t80t6t5t40t2t1)⊕(02022020)= (t82t6??0?t1)?????7????L6?????

??S???(w8w7w600w3w20)??(ti(i=1,2,4,5, 6,8),wi(i=2,3,6,7,8)??4 bit?????)???????????

3.2 ?14??MIBS???????????? ???10??????????2?????2?????MIBS?14?????????

?????????K

????2??????K??= (00000200000000000000)??????????2???????3.1?Ё?10???????????????????????????????(?L0,?R0)=((g0gg,g0gg),L(y80y6y5,y40y2y1)⊕(0000,2000))???2?????????????10??????????????????

MIBS?14????????1????Ё????4 bit????????

?1 MIBS?14??????

??????????14?MIBS????

????????

1) ??228????????????Ё?

g,y4

i(i=1,2,4,5,6,8)∈Z2

?????????????????255????????????

(?L0,?R0)=((g0gg,g0gg),L(y80y6y5,y40y2y1)⊕(0000,2000))

??2m????????????2m+55??

????

2) ??????????(?L14,?R14)= ((????,????),(sss0,0ss0)⊕(0020,0000))??Ё??L14?????L14⊕(0020,0000)=(sss0,0ss0)????s???????

???????????????????2?28?????????Н????2m+27??

3) ??32 bit?14???k14????Н?????????14???????????????????k14?????????????

S(R'?1

14,i⊕k14,i)⊕S(R14,i⊕k14,i)=L(L14⊕L14′)[i]

,

1?i?8?????????2?32????2m?5???Ё????Ё????????????

4) ??k13,4???13??????????

??????????????k13,4=4??Н??

S(R'

13,4⊕k13,4)⊕S(R13,4⊕k13,4⊕4)=L?1(?R14⊕

(00200000))?9[4]????????2m?????

?2? ┌???????????MIBS???????????? g193g

5) ???1??32 bit?????2.3?Ё???????????????k1,2[3]?k1,3?k1,4?k1,5?

k1,6?k1,7?k1,8?????k1,1,k1,2[2,1,0]?7 bit???

???L?1(?R0⊕?L1)=L?1(?R0)⊕L?1(0000,2000)=

L?1(?R?1

0)⊕L(0222,2220)??М8????????L?1

(?R0)????М??????????k1,1????Н??S(L'?1

0,1⊕k1,1)⊕S(L0,1

⊕k1,1)=L(?R0)[1]??????k1,2[2,1,0]??Н??S(L0,2⊕k1,2)⊕

S(L0,2

′⊕k1,2)=L?1(?R0)[2]⊕2?????????2m?17??

6) ???2??k2,4????????????

????????????????S(L1,4⊕k2,4)⊕

S(L1,4

′⊕2⊕k2,4)??????????L?1(?L0)[4]???????????????????????????????????????????

???2m?17????????????????????n=232

×24

×27

×(1?2?4)

2m?17

??n<1?

?????????????m=26? 3.3 ?????

???????????14??????????????????????

?????S???? ?/??????Ё???S????×1

??×

???????????????????7

???3)???2×18×1

14×∑(2m+27?4i×24+4i)≈

i=0

2m+25.2???4)???2×11

8×14

×232×2m?5×24=

2m+25.2???5)???2×11

8×14

×232×24×

(2m?9×24+2m?13×27)=2m+26.8???6) ???2×1×1

×232×24×27×2m?17814

≈2m+20.2??m=26????????????256?14??????

???????????256?????254?

4 ???

????MIBS-80????????????????????????10???????????????????????????14??MIBS????????????????3???????????????????????

??????[3]???[4]???????????

????72 bit????????43 bit??????????????254???????256?

?3

MIBS-80???????

???? ?? ??????8????

??

??? ?? Integral 9 239.6 268.4 ü

[5] Ё??? 11 224.9 266.25 251.03 [6] ?? 13 262 225 ü [2] ????? 12 262 246.42 ü [3] ????? 12 259 263 ü [4] ???????????

14

254

256

ü

??

?????

[1] IZADI M, SADEGHIYAN B, SADEGHIAN S S. MIBS: a new light-weight block cipher[A]. CANS 2009[C]. Berlin: Springer, 2009. 334-348. [2] ??, ???. ????MIBS???????[J]. ??????

(ˊ??), 2010, 45(4):12-15.

YANG L, WANG M Q. Differential cryptanalysis of reduced-round MIBS[J]. Journal of Shandong University(Natural Science), 2010, 45(4):12-15.

[3] BAY A, NAKAHARA J J, VAUDENAY S. Cryptanalysis of re-duced-round MIBS block cipher[A]. CANS 2010[C]. Berlin: Springer, 2010. 1-19.

[4] ???, ┌??. ?????????MIBS???????[J].

??????(ˊ??), 2012, 47(7):55-58.

DU C H, CHEN J Z. Impossible differential cryptanalysis of re-duced-round MIBS[J]. Journal of Shandong University(Natural Sci-ence), 2012, 47(7):55-58.

[5] ??Б, ???. ?MIBS???Integral??[J]. ???????

??, 2012, 33(4):773-777.

WANG G L, WANG S H. Integral cryptanalysis of reduced-round MIBS block ciphe[J]. Journal of Chinese Computer Systems, 2012, 33(4):773-777.

[6] ??, ???, ???. ?MIBS???Ё?????[J]. ???

????(?????), 2013, 44(3):308-315.

LIU C, LIAO F C, WEI H R. Meet-in-the-middle attacks on MIBS[J]. Journal of Inner Mongolia University(Natural Science Edition), 2013, 44(3):308-315.

[7] KNUDSEN L R. Cryptanalysis of LOKI91[A]. Advances in Cryptol-ogy-Auscrypt 1992[C]. Gold Coast, Australia, 1992.196-208. [8] BIHAM E. New types of cryptanalytic attacks using related keys[J].

Journal of Cryptology, 1994, 7(4):229-246.

[9] BIHAM E, BIRYUKOV A, SHAMIR A. Cryptanalysis of skipjack

reduced to 31 rounds using impossible differentials[A]. Advances in Cryptology-Eurocrypt 1999[C]. Berlin: Springer-Verlag, 1999. 12-23. [10] BIHAM E, DUNKELMAN O, KELLER N. Related-key impossible

differential attacks on 8-round AES-192[A]. CT-RSA 2006[C]. Berlin: Springer-Verlag, 2006.21-33.

[11] ZHANG W T, WU W L, ZHANG L. Related-key impossible differential

????201??