分组密码TWIS的三子集中间相遇攻击

?35??6? 2014?6?

? ? ? ?

Journal on Communications

Vol.35 No. 6 June 2014

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

????TWIS???▊Ё?????

???ē???

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

? ??????????TWIS??????????????▊Ё?????????Щ???????10?TWIS???TWIS?????ЩЁ????┻????┉??????62 bit???????????????10?TWIS??62 bit?????????245????????????????????????????TWIS???▊Ё???????????? ?????????TWIS?Ё?????????

Ё?????TP309 ??????A ?????1000-436X(2014)06-0180-05

3-subset meet-in-the-middle attack on block cipher TWIS

ZHENG Ya-fei,??WEI Hong-ru??

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

Abstract: To do further analysis of the security of lightweight block cipher TWIS, 3-subset meet-in-the-middle attack was applied to 10-round TWIS without the final whitening. Based on the weakness in the key schedule of TWIS?its ac-tual key size was only 62-bit and the confusion speed of the initial key was rather slow, the time complexity to recover the whole 62-bit key of 10-round TWIS was 245, and the data complexity was low enough with only one known plain-text-ciphertext pair. The result shows that block cipher TWIS is not secure under 3-subset meet-in-the-middle attack. Key words: block cipher; TWIS; meet-in-the-middle attack; complexity

1 ??

TWIS??Ojha???2009?????????????[1]???????CLEFIA[2]????НFeistel???????????????????128 bit??????10?????????????????????Su Bozhan???????????????????10??????????10?TWIS??????????[3]?╓??Onur Kocak ?Nese Oztop???TWIS???????????????10??TWIS???12 bit????????????221????9.5???????????????????TWIS??┉??????62 bit??????????

128 bit[4]?

Ё?????(meet-in-the-middle attack)?Diffie?Hellman?1977???DES??????[5]???????????????????????????????????????????Ё???????????????Ё????????????????Щ?????????????????????Ё???????????DES?AES?Keeloq?????????????Ё?????????????[6~10]?

?????Ё?????????????????????????▊Ё????????▊Ё??????Andrey Bogdanov????

?????2013-03-05??????2013-11-20

??-????????????-??61272476??????????????????????-??2012?

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

?6? ?▉???????TWIS???▊Ё????? g181g

??????KTANTAN[11]??????Ё????????????▊????????????????????Ё???????????????▊Ё??????????KTANTAN32?KTANTAN48????????????3/2??????????????275.044

/ 275.584[12]???▊Ё???????????Ё???????????????Ё???????????Gautham Sekar???XTEA????????[13]?

??????????TWIS???????┻???Щ????????10?TWIS????▊Ё?????????┉??62 bit???????????245?

??????????????????????TWIS???????▊Ё???????????????????????TWIS???????????

2 ????TWIS??

2.1 ????

A(l)?A????l bit?

<<<i??????i bit? >>>j??????j bit? A⊕B?A?B???????? A∧B?A?B?????? |A|?▊?AЁ??????

?i,j??i???j???????

2.2 ????TWIS

TWIS?????????????????????128 bit??????2-????НFeistel????????10??????????32 bit??P(128)=(P0,P1,P2,P3)??128 bit?????C(128)=(C0,C1,C2,C3)??128 bit?????RKi(i=0,1,??,10)???????TWIS????

???

(T0,T1,T2,T3)=(P0⊕RK0,P1,P2,P3⊕RK1)

fori=1to10do

(X0,X1)=G(RKi?1,T0,T1)

T2=X0⊕T2T3=X1⊕T3

T1=T1<<<8

T3=T3>>>1

(T0,T1,T2,T3)=(T2,T3,T0,T1)(X0,X1)=G(RKi,T0,T3)

T1=X0⊕T1T2=X1⊕T2

T2=T2>>>1T3=T3<<<8endfor

(C0,C1,C2,C3)=(T0⊕RK2,T1,T2,T3⊕RK3)

?Ё????G????3?32 bit??????2?32 bit?????32 bit???????2?32 bit????

G(RK,X0,X1)=(Y0,Y1)

Y1=X1⊕F(RK,X0)

Y0=X1

F???????????????????

????????????????????[1]?

TWIS?????????Щ?128 bit?????K??11?32 bit????RKi(i=0,1,??,10)??ЁRK0?RK1????????RK2?RK3?????????

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

K=(k1,k2,??,k16)fori=1to11doK=K<<<3 k1=S(k1∧0x3f)k

15=S(k15∧0x3f)k16=k16⊕i

RKti?1=M(k13k14k15k16)tend

?Ё?S?F??Ё???S????M??????

3 ??▊Ё???????

??▊Ё??????Ё????????

??????????????▊??????????????????????Ё?????????????2?????????▊??????▊Ё?????????????3????▊??

??1????l??????K=k0k1??kl?1????????НK1={ki|????1,α?????▊?}?K2= {ki:????R?β+1,R?????▊

?}?A0=K1∩K2???????1?α??R?β+1,R?????▊???A1=K1\K1∩K2?A2=K2\K1∩K2?????1,α??R?β+1,RЁ???

??▊????K=K1∪K2?

g182g ? ? ? ? ?35?

?В???????????????????(P,C)??Ё??????v’?u’????????b?????????b????????????????????????┨2b??????????2l?m?b??????????????????????????

?????????

2l?m+2l?m?b+2l?m?2b+??

?1 ??▊Ё?????

?R?β+1=α????▊Ё????????Ё??????

??▊Ё??????????2??????????▊Ё???????????????????????????????????????????????

??????▊Ё??????

?(P,C)?????????A0???????

1) ??A1Ё???????????v=?1?α(P)?

?????????▊Ё???????????????

2|A0|(2|A1|+2|A2|)+(2l?m+2l?m?b+2l?m?2b+??) ?????▊????Ё???|A1|+|A2|>2?

???????В????????? ???????????????l/b????????????????????????????????????????????l?????b??DC=??l/b???

2) ??A2Ё???????????

?1

u=?R?β+1?R(C)?

3) ????Ё????????v?u??????????????????????????v’?????u’?m(1?m?b)??????m??????????m??????????????????????????????2?m???????????????2l?m?

?????????

4 TWIS???▊Ё?????

TWIS?????????????128 bit???????????Щ??????????????3 bit????????24 bit??????????????????????????┉??????62 bit???Щ?????????????????????????

???????????????????????Щ????????10?TWIS???

2|A0|(2|A1|+2|A2|)

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

?1

?? ???? i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 i=9 i=10 ????

TWIS?????

RKi?1

{k0,k1,k2,k99,k100,??,k127} {k0,k1,k2,k99,k100,??,k127} {k0,k1,??,k5,k102,k103,??,k127} {k0,k1,??,k8,k105,k106,??,k127} {k0,k1,??,k11,k108,k109,??,k127} {k0,k1,??,k14,k111,k112,??,k127} {k0,k1,??,k17,k114,k115,??,k127} {k0,k1,??,k20,k117,k118,??,k127} {k0,k1,??,k23,k120,k121,??,k127} {k0,k1,??,k26,k123,k124,??,k127}

{k0,k1,??,k29,k126,k127} {k0,k1,??,k8,k105,k106,??,k127}

RKi

{k0,k1,??,k5,k102,k103,??,k127} {k0,k1,??,k5,k102,k103,??,k127} {k0,k1,??,k8,k105,k106,??,k127} {k0,k1,??,k11,k108,k109,??,k127} {k0,k1,??,k14,k111,k112,??,k127} {k0,k1,??,k17,k114,k115,??,k127} {k0,k1,??,k20,k117,k118,??,k127} {k0,k1,??,k23,k120,k121,??,k127} {k0,k1,??,k26,k123,k124,??,k127}

{k0,k1,??,k29,k126,k127}

{k1,k2,??,k32}

{k0,k1,??,k11,k108,k109,??,k127}

?6? ?▉???????TWIS???▊Ё????? g183g

?▊Ё?????? 4.1 ?????

??▊Ё???????TWIS????????????????Ё??????????????TWIS???▊Ё???????????????????????TWIS?????Щ???????????????1???

???????????????????TWIS???????????128 bit???┉?????????62 bit??????????Ё??????????{k0,k1,??,k32,k99,k100,??,k127}?62 bit????66 bit???????TWIS??В??????2128┑?262???┉?????K′={k0,k1,??,k32,k99,k100,??,k127}? 4.2 10?TWIS???▊Ё?????

?TWIS?┉????l=62????????▊Ё??????????????┑??

??????????Щ?????????????????????

??0???4????????????▊??{k0,k1,??,k14,k99,k100,??,k127}?????┉???18???▊??{k15,k16,??,k31,k32}?

??7???10????????????

▊??{k0,k1,??,k32,k117,k118,??,k127}?????┉???18??▊??{k99,k100,??,k115,k116}? ??TWIS??????2????????

?3?Ё???▊Ё????????????????α=4?β=7?????┉???????3??▊?A0?A1?A2???????

Kÿ={k0,k1,??,k32,k99,k100,??,k127} Kÿ

1=K\{k15,k16,??,k31,k32}

={k 0,k1,??,k14,k99,k100,??,k127}Kÿ

2=K\{k99,k100,??,k115,k116}

={k

0,k1,??,k32,k117,k118,??,k127}A0=K1∩K2={k0,k1,??,k14,k117,k118,??,k127}

A1=K1\A0={k99,k100,??,k116} A2=K2\A0={k15,k16,??,k32} |A1|=|A2|=18,|A0|=26

??????????10?TWIS???▊Ё????????????????????????

????????(P,C)??A260?2????? 1) ??A181Ё?????2???????

v=?1,4(P)?

2) ??A2Ё?????218???????

u=??1

7,10(C)?

3) ???5??Ё??????

???5???v’?u’?????????2????Ё???????????A1?A2???????????????v’?u’??????????32??????????32????????????????????????2?32?

??????????226(218+218)=245?

?2 Ё?????

?????В????2l?m=230?????????????(P,C)????v’?u’??????128 bit???????128 bit????????????????????????2?128?????????????v’=u’????????

?????????

2l?m+2l?m?b+2l?m?2b+??

=230+2?98+??

≈230

?????????TWIS????????

g184g ? ? ? ? ?35?

?????????????????????? 4.3 ?????

???3?Ё???▊Ё????????????????10?TWIS?┉??62 bit???????????

2|A0|(2|A1|+2|A2|)+2l?m+2l?m?b+??

=226(218+218)+230+2?98

+??

≈245

??????DC=??l??62?

?b??=??128??

=1?

5 ???

??2?????TWIS???????ЩЁ????┻???????Щ??????10?TWIS?????▊Ё?????????┉?????62 bit?????????????????????????245

????????Щ??????10?TWIS???????▊Ё??????????????[4]ЁOnur Kocak??????10?TWIS??????

?2

TWIS???????

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

?? ???? ?? 10 62 245 1

??▊MITM

??[4]

10

12

2

21

2

21

????

?????

[1] OJHA S K, KUMAR N, JAIN K. TWIS–a lightweight block cipher[A].

Information Systems Security[C]. Berlin: Springer Heidelberg, 2009.280-291.

[2] SHIRAI T, SHIBUTANI K, AKISHITA T, et al. The 128 bit block

cipher CLEFIA[A]. Fast Software Encryption[C]. Berlin: Springer Heidelberg, 2007.181-195.

[3] SU B Z, WU W L, ZHANG L, et al. Full-round differential attack on

TWIS block cipher[A]. Information Security Applications[C]. Berlin: Springer Heidelberg, 2011.234-242.

[4] KOCAK O, OZTOP N. Cryptanalysis of TWIS block cipher[A]. Re-search in Cryptology[C]. Berlin: Springer Heidelberg, 2012.109-121.

[5] DIFFIE W, HELLMAN M E. Special feature exhaustive cryptanalysis

of the NBS data encryption standard[J]. Computer, 1977, 10(6): 74-84. [6] CHAUM D, EVERTSE J H. Cryptanalysis of DES with a reduced

number of rounds[A]. Cryptology-CRYPTO’85 Proceedings[C]. Ber-lin: Springer Heidelberg, 1986.192-211.

[7] DEMIRCI H, SELCUK A A. A meet-in-the-middle attack on 8-round

AES[A]. Fast Software Encryption[C]. Berlin: Springer Heidelberg, 2008.116-126.

[8] DEMIRCI H, TASKM ?, COBAN M, et al. Improved meet-in-the-

middle attacks on AES[A]. Progress in Cryptology- INDOCRYPT 2009[C]. Berlin: Springer Heidelberg, 2009.144-156.

[9] DUNKELMAN O, SEKAR G, PRENEEL B. Improved meet-in-the-

middle attacks on reduced-round DES[A]. Progress in Cryptology– INDOCRYPT 2007[C]. Berlin: Springer Heidelberg, 2007.86-100. [10] INDESTEEGE S, KELLER N, DUNKELMAN O, et al. A practical

attack on keeloq[A]. Cryptology-EUROCRYPT 2008[C]. Berlin: Springer Heidelberg, 2008.1-18.

[11] DE C C, DUNKELMAN O, KNEZEVIC M. KATAN and KTAN-TAN—a family of small and efficient hardware-oriented block ci-phers[A]. Cryptographic Hardware and Embedded Systems-CHES 2009[C]. Berlin: Springer Heidelberg, 2009.272-288.

[12] BOGDANOV A, RECHBERGER C. A 3-subset meet-in-the-middle

attack: cryptanalysis of the lightweight block cipher KTANTAN[A]. Selected Areas in Cryptography[C]. Berlin: Springer Heidelberg, 2011.229-240.

[13] SEKAR G, MOUHA N, VELICHKOV V, et al. Meet-in-the-middle

attacks on reduced-round XTEA[A]. Topics in Cryptology–CT-RSA 2011[C]. Berlin: Springer Heidelberg, 2011.250-267.

?????

?▉??1988-???????????????????????????????

????1963-????┙???????????????????????????????????????????