TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.4, April 201 4, pp. 3200 ~ 3 2 0 7   DOI: http://dx.doi.org/10.11591/telkomni ka.v12i4.4931          3200     Re cei v ed Se ptem ber 21, 2013; Revi se d No vem ber  19, 2013; Accepted Decem ber 10, 20 13   Attack the Anycast Sig n ature Scheme      Jinbin Zhen g   Schoo l of Math ematics an d C o mput er Sci e n c e, Long ya n U n iversit y   No. 1, Dong  Xi ao North R o a d , Long ya n 3 6 4 0 12, Chi na. + 8 6 - 059 7-27 93 77 8   email: j b zhe n g 518 @16 3 .com       A b st r a ct  T oday, the i n te rnet is i n creas i ngly  bei ng c o n s ider ed  to  prov ide s e rvices, a nd n o t just i n   order t o   conn ect. As this vi ew  beca m e   more  un iv ersal, th i m p o rtant factors  of provi d i ng s u ch serv ices  a r e   relia bi lity an d avail a b ility of the serv ic es to  me et the ne e d s of a larg nu mb er of use r s. Anycast is a   communic a tio n  mo de  in w h ich  the sa me  ad dr ess is ass i gn e d  to a gr ou p of  servers a nd th e router w i l l  se nd   the requ est to the  b est  ser v er. Al-Ibrahi m and  Cer n y pr opos ed a n  aut hentic atio n sche m e of a n yc ast   communic a tio n .  T heir sche m e  is base d  o n  El -Gama l  ty pe si gnatur e sche m e. W e  prov e th at their pref err e d   sche m e, w h ich  does not re qui re interacti on a m o ng the var i o u s sign ers, is insecur e   Ke y w ords : dig i tal sig nature, a n ycast co mmu n ic ati on, de nia l  attack, forgery attack    Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion  Al-Ibrahi m an d Cerny describ e an auth enticatio n scheme for an ycast commu nicatio n   based  on El -Gamal type  d i gital si gnatu r e [1-[2],  [11].  They p r op osed a n  a u then tication  sol u tion  were  simila rly relat ed to  th e con c ept  of  proxy  signatu r es.  The  met hod  appli ed  a  strong  sch e m e   from [3, 4] and obtaine d by improving th e scheme fro m  [5, 15]. There a r e many  appro a che s  for  improving the scalability of  a serv ice, but the comm on one is to  repli c ate the  servers. Serv er  repli c ation i s  the key approa ch fo r maintainin g use r -perceive d  quality of  servi c e withi n  a   geog rap h icall y  wide-sp re ad network. This  is e m powered b y  the unde rlining n e twork  infrast r u c ture kno w n as anyca st  com m un ication.  Ea ch  use r  o w n s  a  private key a nd a p ublic  key,  and all  arith m etic i s  do n e  in a  co m m on g r ou p i n  whi c h  the  discrete  log a r ithm p r obl e m  is   intrac table. In this  sc heme,  the  autho r p r ese n ts vari eties d enial a ttac k s .  Thus , for this  sc heme  is   inse cu re.       2. Rev i e w  o f  An y cast Signatur e  Sche me  In anyca st co mmuni cation,  a commo n IP addre s s( a n yca s t add re ss) is u s e d  to define a   grou p of  serv ers  that provide  the  same  servi c e.  A  cli ent send er d e siri ng  to  co mmuni cate  with   only one of the serve r s sen d s data g ram s  with the IP  a n yca s t addre ss [1]. Al-Ibra h im et al. firstly  prop osed a  con c a s t sig n a ture in 20 0 2  [11], Stinson pointe d  o u t an attack for the con c a s scheme [1 2]; later, Liu ga ve an improvement  [13] u poun the  co n c a s t schem e. On the othe hand, Al-Ib r a h im an d Carny also  presented the   an ycast authent ication sig nat ure  i n   20 03. The   operation con c eptio n be de scribe d as foll ow:   a. Initializatio n. The com m unication o f  eac h serve r  with the g r oup  coo r di n a tor. A  sign ature  del egation  algo ri thm is  used i n  this  co mmu nicatio n . Each serve r  sta r t s  playin g the   role  of the coo r din a tor’s p r oxy.  b. The  actu al  se rving. T h e  anycast  se rver u s e s  th e d e legate d   sign ature, tog e th er  with  the proof of hi s dele gation.  The co ncept is de scribe d a s  follow [1].  Notation:   1)  q p , : two large p r i m es  su ch tha t   ) 1 ( | p q 2)  g : a generato r   with ord e * p Z q 3)  i U  and  V : are de note User’ s  ID.  4)  (.) H : denote a on e way ha sh functio n Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Attack the An ycast Signatu r e Sch e m e  (Jinbin Zhe n g )   3201 2.1. The Scheme of Co nc ept  Defini tion 1.   Di screte  log a rithm  proble m  is  ) , , ( y g p DLP  a p r o b lem that  on  i nput a   prime   p  and  int egers  g * p Z y , outputs   1 p Z y  satis f ying  ) (mod q y g x  if   su ch  an  x   exists. Othe rwise, it outputs  .   The above f unctio n , which outputs   if  there is no  solution to the query, shoul d be   expre s sed a s  DLP [16] an d the notatio n DLP  sh o u l d  be u s ed  on ly for a we aker fun c tion  such  that nothing i s  spe c ified fo r the be havio r of the fu n c ti on in the  ca se wh en the r e  is no  sol u tio n  to   the query [6].  G e n a ra l W o rk The Al-Ibrahi m et al.’s schem e consi s ts  of two  pha se s: Initializatio n pha se an Verific a tion phase.  Initialization Phase:  Us er  i U  signs a  messag M  in the followi ng  way.  Step 1.   i U  Computes      ). ( i i M H m                                                 (1)    Step 2.  i U  Selects a rando m integer i k , and compute s     ). (mod p g m r i k i i                                              (2)    Step 3.  i U  Computes    ). (mod q x r k s i i i                                              (3)    Step 4.  i U  Sends the  ) , , ( i i i r s M with mes s ages  to the verifier.  Verification Phase:  After rec e iv ing  ) , , ( i i i r s M  the signatu r e, Verifier  V  c an verifies  the following:  Step 1.   V  Computes      ). ( i i M H m                                                (4)    Step 2.   V  Computes      ). (mod p r y g l i r i s i i i                                            (5)    Step 3.  If it h o lds,  V  can b e   certai n that  ) , , ( i i i r s M  is ind eed the  sign ature  gen erate d   by  i U  when:     . i i l m                                                  (5)    2.2. The An y cast Sch e me   The anyca st operation will   play  the   role  of the  sig n e r  by  gro up  coordi nato r   G , whic deleg ates hi s signatu r e ri g h ts to all the membe r  of the anyca st gro up.    2.2.1. Initializatio n  Re ad y   Stage  Us er  i U  signs a  messag M  in the followi ng  way.  Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3200 – 3 207   3202 Step 1.  Coordinator  cho o ses the secret  key  p Z x  and com putes the p u b lic key     ). (mod p g y x                                              (7)    The key  y  is the identifier of the grou p.  Step 2.  Coordinator  ran d o m ly choo se s a value  p i Z z  and  comp utes    ). (mod p g U i z i                                              (8)    Whe r n i 1 , then it send i t  to  i th s e rver.  Step 3.  Server  i A  sele cts a ra ndomly value   p i Z  and comp utes    ). (mod p u g t i i i                                              (9)    belon g to  * p Z , th en it send i t  to the coo r din a tor.   Step 4.  Coordinator  com p utes    ). (mod p z x t v i i i                                            (10)    Step 5.  Server  i A  received  i v  from Coo r di nat or and  com p u t es    ). (mod p v x i i i                                              (11)    Then che c ks:     ). (mod p t y g i t x i i                                              (12)    if it is equality. If it is corre ct, then acce pts  i x  as secret key legal.    2.2.2. Actu al Serv ing Stage  Se v e i A  node:  Step 1.  Comp utes    ). ( i i M H m                                                (13)    Step 2.  Choo se s a ran dom  numbe i k  and  compute s     ). (mod p g m r i k i i                                              (14)    Step 3.  Comp utes    ). (mod q x r k s i i i i                                            (15)    Step 4.  Sends  ) , , , ( i i i i t r s M  to the c lient.       Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Attack the An ycast Signatu r e Sch e m e  (Jinbin Zhe n g )   3203 2.2.3. Client node:  Step 1.  Fetc hes  the key  i y  from the regi stry.   Step 2.  Comp utes    ). ( i M H h                                                (16)    Step 3.  Comp utes    ). (mod ) ( p r t y g l i r i t i s i i i i                                            (17)    Step 4.  Acce pts the sig nat ure if:    . l h                                                  (18)    With the rece nt intere st in  se curi ng g r o up an d broad ca st com m un ication  and m u ltica s comm uni cati on, there h a s  b een  a g r e a t dema nd f o r d e si gnin g   a ne cla s of fast  signat ure   scheme s  tha t  can handl e  a vast number of sig nat ure from b r o adcast com m unication a n d   multica s t co mmuni cation  or grou p-b a se d appli c a t ion efficientl y , rather than usi ng typical  sign ature  sch e mes. B a sed  on the th re sh old p r oxy  one -time  signatu r e sch e me, a  spe c ific ca se   is  whe n   1 t , which depi cts th e anyca st model. The  anyca st auth enticatio n problem was  discu s sed i n   [1] and  a  sol u tion was p r op ose d  b a sed  o n  a  co nventio nal di gital  sig nature.  Briefl y,  the  anycast model rep r e s ents  the situ ation  wher any of a gro up of n serv ers  (sign e rs)  ma provide the  same (e quival ent) se rv ice to a client (ve r ifier) [14].      3. Weak ness es of An y c a s t Scheme   Anycast i s  a netwo rk a d d r essing a nd routing sch e m e  whe r eby d a ta is ro uted  to the   ‘nearest’  or ‘ best’  de stinat ion a s  vie w e d  by th e routi ng top o logy [ 10]. For a n ycast  schem e, the  grou p co ordi nator will pl a y  the role of the sig ner, wh ich del egate s  his sig nature  rights to all th e   membe r s of the anyca st group. The term is in tended  to echo the term s unicast,  broad ca st a nd  multicast.  a)  In unicast, there i s  a on e-t o -on e  a s soci ation betwee n  network ad dre ss  and  net work  endp oint: ea ch d e stin atio n add re ss  un iquely identifi e s a  sin g le receive r  en dp oint Figu re 1.  In   comp uter net workin g, uni cast tran smission i s   the  se nding  of me ssage s to  a  singl e n e two r destin a tion id entified by a uniqu e add re ss [7].      Figure 1. Unic as t Servic es [7].       b)  In bro a d c a s t, there  is a  o ne-to -many  a s soci ation b e t ween  net work a ddresse and  netwo rk  end p o ints: ea ch d e stinatio n ad dre ss i dentif i e s a  set of re ceiver  end poi nts, to whi c all  informatio n is repli c ated  Fi gure  2. Bro a d c a s ting  can  b e  pe rform ed  as a  high  lev e l ope ration  i n  a   prog ram, fo r example b r oad ca sting  Messag e Pa ssi ng Inte rfa c e, o r  it ma y be a lo leve netwo rki ng o peratio n, for example b r oa dca s ting o n  Ethernet [8].  R R R R R Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3200 – 3 207   3204     Figure 2. Bro adcast Servi c es [8].      c)  In multicast, there is al so  a one-to -m a n y  asso ciation  betwee n  network ad dre sses  and network endp oints: ea ch de stinatio ad dre s i d e n tifies a  set o f  re ceiver en d points, to  whi c all informatio n is repli c ate d  Figure 3. Multica s t is most co mmo nly implemen ted in IP multica s t,  whi c h is ofte n employed i n  Internet Protocol (I P) a pplication s  of streami ng m edia and Inte rnet  televis i on [9].  d)  In anycast, t here  is al so  a on e-to -m an y asso ciation  between  net work  add re sses  and network endp oints: ea ch de stinatio ad dre s id e n tifies a  set o f  receiver end points,  but o n ly  one of th em i s  cho s en  at a n y given time  to re ce ive inf o rmatio n fro m  any given  sen der Figu re 4.  On the Internet, anyca st is usu a lly impleme n ted  by using  Borde r  Gate way Proto c ol  to   simultan eou sl y anno unce t he  same  de st ination IP a d d re ss range  from m any diff erent  pla c e s   on   the Internet [10].      Figure 3. Multic as t Servic es  [9]  Figure 4. Anyca s t Service s  [10]      As  k n own for a forgery a ttac k  in following [6].   Step 1.  Eve randomly cho o se s a num b e i s .   Step 2.  Eve calcul ates:     ). (mod ) 1 ( ) ( 2 q p g M H r i s i i                                          (19)    Step 3.  Eve forge d  sig natu r e on the me ssag i M  whe n  she use  A sig nature  forged  u s in g  upo n-de scri bed  metho d  is valid, b e c au se  the  followin g   equatio ns h o l d Proof.    ). (mod ) ( ) (mod ) ( 2 ) 1 ( ) ( p M H p M H y r y g i i p g M H i r s i s i i i                                      (20)    To actu al se rving of their schem e, even for:    ). (mod ) ( p r t y g l i r i t s i i i i                                          (21)  ) , , ( i i i r s M R R R R R R R R R R R R R Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Attack the An ycast Signatu r e Sch e m e  (Jinbin Zhe n g )   3205 Eve compute:     ). (mod ) ( ) (mod ) ( ) ( ) (mod ) ( 2 ) 1 ( ) ( p M H p M H t y p r t y g l i i p g M H i t i i r i t i s i i s i i i i i                                        (22)    3.1. Denial Atta ck I  E v e let s  se cr et  key   0 x  and  1 i k  in firs t.  Step 1.  Eve compute s   ). (mod 1 0 p g g y x i                                            (23)    Step 2.  Eve compute s   ). ( i i M H m                                                (24)    Step 3.  Eve compute s   ). (mod ) (mod 1 p g m p g m r i k i i i                                              (25)    Step 4.  Eve compute s   ). (mod 1 ) (mod 0 1 ) (mod q q q x r k s i i i                                              (26)    After Eve finishe d  the four steps , she h ad denie d  the  valid signatu r ) , , ( i i i r s M  of user  i U . Eve computes:     ). (mod ) (mod 1 ) (mod 1 1 1 p m p g m g p r y g m i i g m i r i s i i i i                                          (27)    3.2. Denial Atta ck II  Eve s e ts  secret k e 1 p x  and  . 2 p k i   Step 1.  Eve compute s   ). (mod 1 ) (mod ) (mod 1 p p g p g y p x i                                              (28)    Step 2.  Eve compute s   ). ( i i M H m                                                (29)    Step 3.  Eve compute s Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 4, April 2014:  3200 – 3 207   3206 ). (mod ) (mod ) (mod ) (mod 1 1 1 ) 2 ( p g m p g g m p g m p g m r i p i p i k i i i                                            (30)    Step 4.  Eve compute s   ). (mod 1 ) (mod 0 1 ) (mod q q q x r k s i i i                                              (31)    After Eve finishe d  the four steps , she h ad denie d  the  valid signatu r ) , , ( i i i r s M  of user  i U . Eve computes:     ). (mod ) (mod 1 ) (mod 1 1 ) 2 ( p m p g m g p r y g m i i g m i r i s i p i i i                                          (32)      4. Conclusio n   In the past, Al-Ibra h im et al. decribe d an  authenti c atio n schem e for  con c a s t and  anyca st  comm uni cati on ba sed  on  El-Gamal ty pe digital  sig nature. T hey prop osed a n  authenti c at ion   solutio n   were  simila rly rela ted to the  con c ept  of  proxy sign ature.  Fo r any ca st sch e me, the  gro up  coordinator  will pl ay the rol e  of the  signer,  whi c delegates  his signature rights  to all the  membe r of the  any ca st grou p.We   al ready kn o w  h o w to  de ny and fo rge  si gnature  so t hat  anyca st is  effected. Fo r fo rged  attack, we  can m a ke  a set of forg ery sig natu r e  whi c su cce e d   the anyca st communi catio n  of authenticati on. Thus, f o r this  schem e is insecure.       Ackn o w l e dg ements   The auth o rswoul d like to  thank  Che n g lian Li u fo his comme nts that help t o  improve  themanu scri p t. This p ape r pa rtially  su pporte d from  coll ege fu n d ing  unde r t he info rmatio n   se curity re se arch team project.       Referen ces   [1]  M Al-Ibrahim,  A Cerny .  Authentic ati on  of a n y c a st comm u n icati on.  MMM -ACNS 20 03; LNCS 27 76:   419- 423.   [2]  CP Schnorr. Efficient sig natur e gen erati on b y  smart cards.  Journ a l of Cryp tology . 19 91; 4 ( 3): 161-1 74.   [3]  K Z han g. T h resho l pro x sign ature  sche m es.  Infor m ati on s e curity,  L e cture  Notes  i n  C o mput er   Scienc e . 199 8; 1396: 2 82-2 9 0 .   [4]  H Gho dosi, J  Pie p rz y k Re pud iatio n   of c heati ng  an d n on-re pud iati on  of zh ang  pro x y s i gn atu r e   schemes.  Infor m ati on Sec u rit y  and Privacy,  Lecture Notes  in Co mp uter Scienc e . 199 9; 1587: 1 29- 134.   [5]  M Mamb o, K  Usud a, E Oka m oto. Pro x y s i gnatur e: d e le g a tion  of th e p o w e r  to  sig n  m e ssag e IEICE  T r ansactio n  on  F unda me ntals .  1996; E79-A:  133 8-13 54.   [6]  Che ngl ian  Liu,  Yongn in g Gou. Securit y   an al ys is of conc ast and a n y ca st digital si gn a t ure.   Applie d   Mechanics and  Materials.  20 1 2 ; 121(1 26): 11 77-1 182.   [7]  W i kiped ia. Un i c ast scheme.  Wikiped ia w e b s ite, http://en.wikipe d i a .org/w iki/Unicast.  2 012 [8]  W i kiped ia. Bro adcast schem e .   Wikipedia website, http://en.wi kipedia.org/ w iki/Broadcasting.  201 2.   [9]  W i kiped ia. Mult icast scheme.  Wikiped ia w e b s ite, http://en.wikipe d i a .org/w iki/Multicast.  20 12.   [10] W i kiped ia.   Anycast scheme.  Wikipedia website, http:// en.wikipe d i a .org/w iki/Anycas.  201 2.  [11]  M Al-Ibrah im, H Ghod osi,   J Pieprz y k. A u thentic atio of concast c o mmunicati on.    Progress in   Cryptology INDOCRYPT. Lecture  Notes i n  C o mputer Sci e n c e.  2002; 2 551 : 185-19 8.  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Attack the An ycast Signatu r e Sch e m e  (Jinbin Zhe n g )   3207 [12]  DR Stinso n. Attack on  a conc ast signatur e scheme.  Infor m ation Proc essi ng Letters.  20 0 4 ; 91(1): 39- 41.   [13]  C Liu. Improv e m ent  of authe n t ication of  a n y c a st communic a tion.  Internati o nal C onfer ence  for Internet  T e chno logy  an d Secure d T r ansactio n s (ICIT S T 0 9 ).  200 9; 1-3.  [14]  Moham ed Al- B rahim, Anton  Cern y .   Proxy  and thresh ol d one-ti me si gnatur e.  First International  Confer ence  o n  App lie d Cr ypt ogra p h y   an Net w ork  S e cur i t y , L e cture  N o tes i n  C o mp uter Sci ence 200 3; 284 6: 12 3-13 6.  [15]  Z  Yan, F  Z h a ng. Cr yptan a l ysis to a  Certificatel ess T h res hol d Sig natur e Scheme.  TE L K OM N I KA  Indon esi an Jou r nal of Electric al Eng i ne eri n g .  2012; 1 0 (6): 1 496- 150 2.   [16]  L Ma. More Efficient VLR Gro up Sig natur e Based o n  DT DH Assumption.  T E LKOMNIKA Indo nesi an  Journ a l of Elec trical Eng i ne eri n g . 201 2; 10(6) : 1470-1 4 7 6 .       Evaluation Warning : The document was created with Spire.PDF for Python.