Int ern at i onal  Journ al of Ele ctrical  an d  Co mput er  En gin eeri ng   (IJ E C E)   Vo l.   9 , No .   5 ,  Octo ber   201 9 , pp.  4287 ~42 95   IS S N: 20 88 - 8708 ,  DOI: 10 .11 591/ ijece . v9 i 5 . pp 4287 - 42 95          4287       Journ al h om e page :  http: // ia es core .c om/ journa ls /i ndex. ph p/IJECE   A crypta nalyti c atta ck of  simp lified - AES   usin g  a nt   colon y o ptim iza tion       Hicham  Gr ari, Ahmed  Az ouaoui , Khali d  Z ine - Dine   LAROS ERI  La b . ,   Facult y   of   Science s,  Chou ai b   Doukkali Unive rsi t y ,   Moroc co       Art ic le  In f o     ABSTR A CT    Art ic le  history:   Re cei ved   Feb  23 , 20 1 9   Re vised  A pr   2 2 , 2 01 9   Accepte d  Apr   30 , 201 9       Ant  col on y   Opt imiza ti on  is  a  nat ure - inspire d  m et a - heur ist ic   o pti m iz ation   al gorit hm   th at  gai ned   a  gr eat  int er est  in   resol uti on  of  combi nat ori al   and  num eri ca l  opt imization  proble m s  in  m an y   scie n c e  and  engi n ee ri n g  dom ai ns.   The   ai m   of  thi s  work  was  to  inv esti gate  the   use  of  Ant  Colon y   Optimiza ti o n   in  cr y pt anal y s is  of  Sim pli fie d  Ad vanc ed   Enc r y p tion  Standa rd  (S - AES),  using   a  known  pla int e xt  at tack.   W e  ha ve  def ine d  the   e ss ent ia l  components  of  our  al gorit hm   such  a s  he uristi c  va lue,  fit ness  func t ion   and  the   strateg y  to  updat e   pher om one  tra il s .   It  is  show n  fro m   the   expe rimenta l  resul ts  tha t  o ur  proposed  al gorit hm   a ll ow  us  to  bre ak   S - AES  cr y ptos y s te m   aft e r  exp lori ng  a  m ini m um   sea rch   spa ce   wh en  compare d  wi th  othe rs  t ec hn i q ues  and  req u iring  onl y   two   pla intext - ci pher t ext   p ai rs.   Ke yw or d s :   ACO   Crypta naly sis   Me ta - heurist ic   Ph e ro m on e   S - A ES     Copyright   ©   201 9   Instit ut e  o f Ad vanc ed   Engi n ee r ing  and  S cienc e .    Al l   rights re serv ed .   Corres pond in g  Aut h or :   Kh al id  Zine - Di ne,     LARO SER I  L ab. ,  Fac ulty  o f   Scie nces,     Chouaib  Do ukkali U niv e rsity ,   Rou te  Be n  Ma achou,  24 0 00, E l Jadida , M orocco .   Em a il :  zi ned ine@u c d. ac .m a       1.   INTROD U CTION   Cryptolo gy  is  on e   of  th e  m os t  sign i ficant  t echn i qu e s  f or  achievin g  i nfo rm ation   sec ur i ty   wh ic h  is  beco m e  a  vi ta l  need   i n  c ommun ic at io n  netw orks  a nd   c om pu te r  syst em s.  Cryptolo gy  is  the  sci ence of  buil di ng   and  analy sin g  diff e re nt  enc ry ption  an d  dec r ypti on   syst e m s.  It  c onsist s  of   two  s ubfiel ds ;   Crypto grap hy   an d   Crypta naly sis.  Crypto gr a phy  is  the  stud y  of  bu il di ng   ne w  powe rful  an d  eff ic ie nt  e ncr y ption   a nd  de cr ypti on  al gorithm s.  Crypta naly sis  is  the  art  of   deciph e rin g  com m un ic at io ns   that   are  secur e d  by   cryptogra phy,  it   is   us e d  to  f in d we akn e ss a nd f la ws of ci phers .   Actuall y,  re se arch  in  t he  cryptol og y  fie ld  are   inc rea s ing ly   us in g  evo l ution a ry  t echn i qu e s ,  encou rag e d  by   the  prom isi n g  obta ine d  re su lt s.  Sp e ci al ly ,  An t  Colo ny   Op ti m iz at io n  ( ACO )  w hich  is  a     well - kn own  m et a - heu risti c   that  was  suc cessf ully   us ed  f or   s olv in g  a  var io us   re al - w or ld  op ti m iz at ion   pro blem s.  Re c ently   ,  A nt  C olony  O ptim izati on   was  us e d  to   at ta ck  D ES  ( Data  E nc ryptio n  Sta nd a rd)  by  Sala bat  K ha n  e t  al .  in  [ 1 ] .  Als o,   Gr a ri  et   al .  [ 2 ]   pro posed  a  novel  at ta ck  of  Sim ple  Su bs ti tuti on   Ci phe rs  base d  on Ant C olony O pti m iz at ion .   In  t his  pa per , we intr oduce a   novel cry ptana ly ti c at ta ck  of   Si m plifie d  A dvance d  E nc ryp ti on  Sta nd a rd  (S - AES)  us in g  A nt  Col onny  Op ti m iz ation   .   we  hav e   m od el le d  the  c rypta na ly sis’s  pro ble m   to  a  com bina torial  pro blem   in  ord er  to  ap ply  AC O  m et aheu risti c  to  br ea k  the  Si m plifie d - A E S  crypto syst em .  W e  w il l  show  t hat   our  a ppr oach  is  sign ific a ntly   faster  a nd  r equ i res  a  sm al le r  nu m ber   of  plainte xt - ci pherte xt  pair s,  wh e n  com par ed  t o other s  att acks.   The  c ryptanaly sis  of   S - AES   ha s  bee n  the  s ubj ect   of   seve ra l  pr e vious  wor ks .  Ma inly ,  M us a  et   al .  [ 3 ]  at ta cked   S - A E S  for  the  fi rst  tim e   us ing   li near   a nd   dif fe ren ti al   cryptan al ysi s,  con cl ud ing   that  their  li nea r   cryptanaly ti c  at ta ck  seem s  ve ry  at tract ive  co m par ed  to  a  pu re  brute  f orce  at ta ck,   re qu iri ng  10 9  plainte xt  and  the  corres pond ing   ci pherte xt  pairs  to  at ta ck   on ly   the  first   round  in  S - A ES.  Ma nso or i  et   al .  [ 4 ,   5]  a pp li ed     Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  9 , N o.   5 ,  Oct ober  20 19  :   4287   -   4 2 9 5   4288   a  li near   c rypta naly sis   to   S - A ES  .  It  has  bee n  s how n  that  a t  le ast   116  plainte xt  a nd  co rr e sp on ding  ci ph e r  te xt   pairs  are  requi red   to  br ea k  t he  first  r ound  and   548  to  break  the  sec ond  r ound,  co ncl ud i n g  t hat  S - AES   is  vu l ner a ble  aga inst  li near   at ta ck.   Wh il e,  Si m m on s  [ 6 ]   pe rfor m ed  an  al gebraic  crypta naly sis  to  S - A ES,  by   reso l ving  a  sy stem   of   po ly nom ial  equ at io n.   H ow e ver,  s om e  oth ers  at t acks  base d  on  m e ta heu risti c s  we re   carried   out  s uc h  as  Valarm ath i  an d  V im al a t hithan  [ 7 ,   8]  w hich  at ta cke d  S - A ES  us in g  Gen et ic   Algori thm   [ 7 ]  and  Pa rtic le   Sw arm   Op ti m izati on   [ 8 ] ,  t he y  br ea k  t he  ke y  us e d  in   S - AES   i n  a   m i nim u m   search  sp ace   com par ed  to  brute  f or ce  at ta ck.   Ra nia  Saee d  an d  As hr a f  Bhery  [ 9 ]  pro po s ed  cry ptana ly sis  of   S - AE S  us i ng   In te ll igent  A ge nt n ee ding  onl y on e  p la inte xt .   The  r em ai nd er  of   t his  pa pe r  is  organ iz e d  a s  fo ll ows .  I n  t he  ne xt  sect io n,   we  intr oduc e  Si m plifie d  Adva nced  Enc ryptio n  Stan da rd.  I n  sect io n  3 ,  we  descr i be  the  A nt  colo ny  opti m izati on   m et a - heu risti c .   The  f ully   auto m at ed  at ta ck  is   giv en  i n  sect ion   7 ,  wit h  ex pe rim ental  resu lt s  in  sect ion   5 .   Finall y,  con cl us io ns  are  giv e n  in  se ct ion   6 .       2.   SIM PLI FIED  ADVA NC E D  ENCR YPTI ON STA NDA RD (S - AES)   Si m plifie d  A dvance d  E ncr y pt ion   Stan da rd   ( S - A ES)  is  a  bl ock   Ci ph e r  al gor it hm   that  ta kes  a  16 - bit   plainte xt a nd  16 - bit   key as  in pu t t o gen e rate s  16 - bit   ci phert ext as  ou t pu t.   The  16 - bit   input plai nte xt ar e  treat ed   as  4x 4   m at rix  of  n ib bles ( a  ni bb le   is  a  4 - bits   blo c k),  cal le d  s ta te .  Each r ou nd  ta kes   a  sta te   and  ge ner at es  a  ne w   on e   t o  be  us e d  in   the  ne xt  round.   Four   tra nsfo rm at ion s  are  us ed  i n  S - A ES:  Substi tuti on  (Su bN i bb le s ),   s hift   row,   m ix  colu m ns   and   ad d  r ound  key.  Fig ur e   1  s hows  e ncr y ption   al gorithm ,  key  generati on   a nd  de crypti on   al gorithm  f or   S - AE S.           Figure  1. S - AE S E ncr yp ti on a nd d ec ryptio n       Sub Nibbles   (S - bo x) :  is  t he   only   nonlinea r  com pone nt  in  the   al gorith m   that  prov i de s  co nfusion   eff ect ,  the  s ubsti tuti on   ta ble  us e d  for  this  pur pose  is  desc ribe d  in  (1) .  It   ta kes  a  4 - bit   input  and   produces     a  4 - bit   ou t pu t .  In   the  i nput   n ibb le ,  the  le ft  2  bits  det erm ine  the  ro w  an d  the  ri ght  2  bits  dete rm ine     the  c olu m n  of  the  s ub sti tuti on  ta ble.  T he  he xad eci m al   valu e  at   the   ju nctio n  of  the   r ow  a nd  the   col um n  is  the     ou t pu t  nibble.     = [ 9 4 1 8 5 6 2 0 3 7 ]       (1)     ShiftR ows :  I n  this  ste p  the ,  t he  first  row  of   the  sta te   m at rix  rem ai ns   unc hange d.  Wh il e  the  sec ond  row,   a  on e - ni bble  circ ular  s hi ft is p e rfo rm ed.   Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A crypt analyt ic  a tt ack  of si mp l if ie d - AES  usi ng  an t c olony  opti miza ti on   ( Hi cham Gr ar i )   4289   Mix Co lu mns :  As  a  third   ste p,   the  Mi xCo lum ns   trans f or m at i on   op e rates  at   t he  colum n  of   the  m a trix;  each  col um n  of   the  sta te   is  transfor m ed  into  a  ne w  col um n.   The  tran sform at ion   is  act ually   the  m at ri x  m ul ti plica ti on   of   a  sta te   colu m n  by  a  con sta nt  square  m atr ix.  T he  ni bb le s  in  the  sta te   colum n  and   c onsta nts  m at rix  a re  interp reted  as p oly no m ia ls  with  coeffic ie nts  in G al ois  Fiel d  G F  (2).   Mult ipli cat ion   of  byte s   is  done   in  GF   ( 2 4 )  wit h  m od ulu s  the  irreducible  pol ynom ia l   (x 4 +x +1)   to  en sure  that  the  resu lt   is  sti ll  within  the  file d  GF   (2 4 ).   Let   (a 0 ,a 1 ,a 2 ,a 3 )   the  input  nib bl es  of   the  Mi xC olu m ns   op e r at ion ,  the  blo c k  at   the  ou t put  (b 0 ,b 1 ,b 2 ,b 3 )  is def i ned as  fol lows :     [ 0 2 1 3 ] = [ 3 2 2 3 ] [ 0 2 1 3 ]       Ad d R ou n dKe y :  T he  la st  sta ge   of  eac h  rou nd  is  t o  a dd  the   rou nd  key.   It  c on sist s   of  t he  bi twise   X OR  of the  16 - bit sta te   m at rix  an d t he  16 - bit  Key  rou nd.   S - AE S  Ke y  E xpansio n:   In   t his  proce ss,  th ree  r ound  key s  a re   ge ne rated  f ro m   the  or i gin at ed  key ,   each  key  is  use d  in  dif fer e nt   sp eci fic  r ou nd,  al lo wing  in creasin g  the  se cur it y  of  S - AE S.  T he  k ey s  use d  f or  encr y ption al gorithm  are  al so use d for  decr y ption.   The  key  e xp a ns io n  al gorith m   create s  ro und  keys  w ord   by  word,  where  a  wor d  is  an  a rr ay   of  2  nibbles, t he  al gorithm  p r oduce s 6   w ords, w hi ch  a re call ed      W 0 , W 1 … W 5 .      Wh e re:   K 0 =W 0 W 1   , K 1 =  W 2 W 3  a nd K 2 = W 4 W 5 .   Fr om   the  or i gin al   key  we   ge ner at e  t he  t wo  byte   W 0   an d  W 1 .   Ne xt  ,w e   ca n  pro du ce   the   oth e rs  w ords  us in g  al gorith m  d escribed  a s  foll ow :      S - AE S Key E xpansi on   For  2 ≤ i  ≤ 5  do       If  i ≡  0(m od  2)   then      W i   = W i - 2 ⊕   R CON( i/ 2 )   ⊕ SubNib(RotN ib( W i - 1 ))      Else      W i   = W i - 1 ⊕   W i - 2      E nd if   En d  f or     In  t his  al gorithm ,  RCON [i]   =  RC [i] 0000,   wh e re  RC [i]   is  def ine d  as   RC [i]   =x i+2   ∈   GF(2 4 )  so    RC [1 ]   =  x 3   =  1000  an d  RC [ 2]  =  x 4   =  x  + 1  =  0011.  If   N 0   and   N 1   a re   two  nibbles  a nd   t heir  c onca te nation  denoted  as  N 0 N 1 .  The  RotNi b   an  SubN i b  f un ct io n s   are  def i ned  to  be:  Rot Ni b ( N 0 N 1 )= N 1 N 0   an d  SubNib ( N 0 N 1 )= Sbox ( N 0 ) Sb ox ( N 1 ) wh ic h  m e ans  res pecti vely   ro ta te   nibble  and  s ub sti tute  nibble.   Decry pt i on :  D ecrypti on  is  th e  rev e rse  proc ess  of   e ncr y ption.  It  ta kes  a  16 - bit   ci ph e rtex t,  the  1 6 - bit   key,  an d  ge nerat es  the  or igi na l  16 - bit   Plai ntext.  Sim il arly   t o  enc ryptio n,   decr y ption   us e s  on e  pr e - r ound  an d  two  rou nd   tra nsfo rm at ion s,  as   sh ow n  in  Fig ure   1.  The  proc esses  pe rfor m ed  du rin g  dec ryption   a re  the  i nverse   of th os e em plo ye d  in e nc ryption.       3.   AN T  COL ONY O PTIMIZ A TION  (ACO )   Op ti m iz ation   m et aheu risti cs  ha ve  a  sig nif ic ant  i m po rta nc e  in  dete rm i ning  ef fici ent  so luti ons  of  diff e re nt  com plex  an d  hard  pro blem s.  Especial ly ,  An t  Colo ny  O ptim izati on ,  w hich  r epr ese nts  a  cl ass  of   natu re - in sp ire d  m e ta - heuris ti cs,  based  on   th e  be hav i or  of  real  ant  wi thi n  their  c olonies .  D ori go  et   al .   [1 0 ]  pro po ses   the  f irst  ACO  al go rithm s  in  the  early   1990s.  T he  stu dy  of   t he   be hav i or   of  ants  withi n  c ol on ie s   insp ire s  the   de velo pm ent  of  these  al gorithm s.  Howe ver,  ants   are   a  s oci al   insect s  a nd  their   be ha vior  i s   gove rn e d  by  the  go al   of  col on y  s urvi val  be ing   focuse d  on  the  s urvi va l  of   i nd i vidual s.  First,   ants  e xp l ore   rand om l y  the  area  arou nd i ng   their  nest  to  search  the  foo d.   Wh e n  an  a nt  fin ds   f ood,   it   walks  back   to  the  colo ny leavin g beh in d  a p he r om on e trai l on  the g r ound that  m ay  dep en d  on the q ua ntit y  and  the  qu al it y of  th e   foo d.   T his  phe ro m on es  trai l  will   gu i de  ot he r  ants  t o  the  foo d  sou rce.  Old  paths  a re  le ss  li kely   to  be  use d  because   of  the p he r om on e  ev aporati on  m ec han ism .  This  f ood  s upplies  be hav i or  h as  ins pire d  the  de vel op m ent   of   AC O,   in  pa rtic ular,   this  abili ty   to  exp l or e  pat hs   bet ween   f ood  s ources  a nd   thei r  nest  and   fi ndin g  the  sh ort est   on e .   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  9 , N o.   5 ,  Oct ober  20 19  :   4287   -   4 2 9 5   4290   The  first  AC O  al gorithm ,  cal le d   An t  Syst e m   (A S)   introd uced   by  D or i go   [1 0 ]   was  app li ed   t o  Trav el li ng  Sal esm en  Pr ob le m .  Other   ACO   var ia nts  m os tly  diff e r  in  the   r ule  us e d  for  th e  so luti on  c ons tructi on   and   the  ph e r om on e  up date,  i nclu ding  A nt  Colo ny  Syst em   (A CS)  prese nted  by  D ori go   and   Gam bard el la   [1 1 ] ,   and Mi n  Ma x An t  Syst em  ( MM AS ) give n by St utzle  a nd  Hoos [ 1 2 ].       4.   THE  PROPO SED  APP ROAC H   Assum ing   that  we  know   a  par t  of  plain  te xt  P   and   his   cor res pondin g  ci ph e rtext  C   du ri ng   th e   op ti m iz ation   proces s .  Let   z  t he   num ber   of  kn own  plainte xt - ci ph e rtext p ai r s  P i  / C i .  The  m ai n  goal   is  to f i nd  the  key  that   al lows  to  perf or m ing   this  encr y ption.  Using o ur  pr opose d  al gorith m ,  we  gen erate   a  cand i date  ke y  K c ,  wh ic h  is  us ed   to  dec rypt  the   cy ph e r  te xt  C i .   The n,   a  can di date  plainte xt  PG i   is  gen e rat ed .  Furthe rm or e,  this   cand i date  Plai ntext  is   us e d  in   the  fitness   f un ct ion   def i ne d  i n  (3)  t o  e valua te   K c .  T he  Fu ll   Lay out  of  our   at ta ck   al gorithm  is d escribe d  in  F ig ure  2.           Figure  2 .   Lay out o f  our   at ta c k  al gorithm       In   order   t o  ap pl y  the  ACO  m et aheurist ic ,  w e  hav e  m od el le d  the  searc h  s pace  to  a  n+1 - nodes   gr a ph    (  n   re pr ese nt  the  key  le ngth  us e d  by  S - AE S) .  E ver y  no de   in  the  gr a ph   i s  connecte d  to   the  nex t  no de   by  two  diff e re nt  ed ges , th e  uppe r  e dg e   is eq ual to  0  and the l ow e r  e dg e   is e qu al  t o 1 as   sho wn   i n Fi gure   3.           Figure  3. Searc h  s pace  for  c ryptanaly sis  of  S AES       E ach   ant  sta rts   it   tou r  f r om   the  sta rt  no de  N 0   m ov ing   from   l eft  to  righ t;   it s  tour  is  finish e d  at   the  la s t   node  N n .   At  e ach  Node ,  a n  ant  can   only   sel ect   a  sing l e  ed ge   du rin g  a  pa rtic ular  t our.   The refor e ,   each   com plete   path   from   the  node   N 0  to  N n+1   that  com p ly   w it h  the  pr ece de nce  c onstrai nt s   is  co ns ide r ed  as    a  f easi ble  s ol ution   ,   i t  will   co ns ist   of   n - bit   bi nar y  strin g  w hich  is  co ns i de red   as  a  ca nd i da te   key.  Af te r  al l  the  ants  hav e   co m ple te d  their   tours,  al l  t he  so luti ons  ge ne rated  duri ng  the  c urre nt  Cy cl e   ar e  e valua te d  a nd   com par ed  by  the  ob j ect ive  functi on,  the  ca ndidate   key  with  the  best  fit ne ss  val ue  in  ea ch  Cy cl e  is  saved   a s     a g lo bal  best a nt  K Best .     4.1.    So luti on co nstr uctio n   Each  a nt  co nst ru ct s  a  key  us in g  the  functi on   Pro babi li sti c  Stepwise  Con st ru ct io n  bas ed  on     a  pr ob a bili sti c  m ov e  of  a nts   acro s s  t he  node s.  For   an   a nt   k  ,   the   pr ob a bi li ty      to  m ov es   from   a  no de  i   to  node  i +1   f ollo wing the  p at h j   is de fine d by  (2 ).   Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A crypt analyt ic  a tt ack  of si mp l if ie d - AES  usi ng  an t c olony  opti miza ti on   ( Hi cham Gr ar i )   4291     P  ( k ) = { 0                               if   no t   a ll owed   τ  ( k ) α   ρ  ( k ) β ∑ τ  ( k ) α l ϵ ρ  ( k ) β         Oth er wi se                       (2)     Wh e re  S is the   set  o f   the   possi ble p at h ( 0  an d   1 ) .   This p r obabili ty  o f  m ov in g  from  a  n od e to nod e  dep e nd on two  p a ram et ers.  Th e first,  the  ph e r om on e   trai l  τ(i,j)  on  the  e dg e   bet we en  the   tw o  node s.  A nd  sec on d  the   he uri sti c  value  ρ (i,j)  re presenti ng  t he  a   pri or i   knowle dge  of  desi ra bili ty   of   the  ch oice.  Th e  par am et ers  α  and   β  a re  pa ra m et ers  wh ic h  determ ine  the  relat ive   influ e nce  of ph ero m on e trai l  ve rsu s  heu risti c v al ue.       4.2.    Heuristic   va lu e   Heurist ic   valu e   is  essenti al   fo r  the  gen e rati on   of   high - qu al it y  so luti on s   in  the  early   s ta ges  of  the  search  process .   Especial ly ,  wh en  us in g  he uri sti c  value  cal c ulati on   m et ho d  fr om   the  pr ob lem   do m ai n.   In   ou r   appr oach,  we h ave  us e d  a  dynam ic  h eur ist ic   that has  to be c om pu te d  at  eac h  ste p of  a n  a nt ’s walk.   First,  as  e xpla ined   previ ously ,  the  ca n did at e  key  with   the  be st  fitness  valu e  in  eac h  Cy cl e  is  save d  a s   a g lo bal  best a nt ( K Best ). T hen, at eve ry  node, ants  us es  h e ur i sti c v al ue  cal c ulate d  as   sho w n  in  Fig ure  4.             Figure  4.   He ur i sti c v al ue  cal c ulati on       Let   N i   the  cur r ent  node   as  show n  in  Fi gure   4,   an  ant  has  t o  decide  w hic h  path   to  f ollo w  to  m ov e  to  the  ne xt   node   N i+1 .  The  j   i s  the  e dg e   to   be  c hoos e   ,  on ly   tw o  valu es  are  possibl e  i.e.  ei the r  0  or  1 .     we  def i ne  H j  as  a  c on cat e na ti on   of  the  c ur ren t  key  (th e   par ti al   s olu ti on   )  f r om   0  to  i  and  t he   j  val ue  a nd    K Best  from   i+2   to  n - 1 .   \     H j = { Cu rrentK ey   ( f r om   0   to  i - 1 )  |  j   |  K Best   (i+ 1   to  n - 1 )}     So ,  t he  c on cat enated  bin a ry  string  H j   repre sente  a  gu es se d  key  w hich  is   evaluate d  us in g  the  fitness   functi on, t he o btained  v al ue  i s u se d  as  a  he uri sti c v al ue  in ( 2 ) .      4.3.    Fitness  fu n cti on   The  qual it y  of   a  gen erated  ke y  is  assessed  by  it s  fitness  fu nctio n  val ue.   The  m ai n  go al   of   a  fitness  functi on  is  to  pro vid e  a  m easur a ble  value  f or   a  gi ven   key   that  ind ic at e  i ts  proxom it y  t o  the  real  key.   It  is    a  pr im or d ia l  com po ne nt  gu i ding  the  searc h  al gorithm   to   the  best  so lu ti on s  withi n  a  la rg e  searc h  sp ac e .   Allowi ng s o  th at  to  ex plore t he  searc h  s pace  m or e eff ic ie ntly .   Let   z  the  nu m ber   of   know n  plainte xt - ci pherte xt  pairs  P i  /  C i .  To  ev al uate  a  can did at e  Key  K c ,    a ca ndidate   pla intext  G P i   is  produce d base d on   K c . T he fit ne ss funct ion  F   of the  key  K c   is   de fine d  in  3 :     ( ) =   ∑ # ( GP i   ⊕   i = 1 ) ∗ 16       ( 3 )     ⊕   re pr ese nts the   Xor ope rati on, a nd # de note s t he nu m ber   of z ero s  in ( G P i   ⊕ P i ).   The  r an ge  of   F   is  [ 0, 1 ] .   Parti cularly ,  F   is  e qual   to  1,   if  al l  bits  in  G P i   are  identic al   to  P i   for  any  i   in  [1 - z] . In  t his ca se ,   t he   ge ner at ed   key is  the  r e al  o ne , so  our g oal is to  m axi m iz e the f it nes s fun ct io n.     4.4.    Pherom on e   u pdate   In it ia ll y,  the   quantit y  of  phe r om on e  i n  ea c h  ed ge   is   eq ual   to  0   (initi al   pher om on e  value ) .  On ly   t he   best  so l utio n  ( K best ) in  a  part ic ular  Cy cl e  (C)  is  al lo we d  to  update  t he  phe ro m on e   values  on  th e  edges  const it uting   th e  tou r.   T he  be st  ant  info rm at ion   is  al so   updated  after  eac h  Cy cl e.  The  ph e r om on es  over  the   Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  9 , N o.   5 ,  Oct ober  20 19  :   4287   -   4 2 9 5   4292   edg e s  co ns ti tut ing   t he  to ur  of   the  best  ant  is   update d  us in g  ( 4 ),   so  la rg e r  the  fitnes s  val ue,   t he  gr eat er   is  the   a m ou nt  pher om on e con ce ntr at ed.     τ , = ∗ ,     + ∗ ( K )           ( 4 )     Wh e re   Q   is  som e  const ant  a nd    re pr e sent   a  phe ro m on e   evapo rati on  ( will   be   bet wee n  0  an d  1 ),   it   con sist   to  de creases  th e  phe ro m on e  trai l  unif or m ly   in  al l  edg e s.  T his  operati on  al lows  avo i ding  a  pr e m at ur e   conve rg e nce  of the alg ori thm  i nto  a  local  opti m al  so luti on.     Out li ne  of AC O A l go ri th m :   St ep 1 : Pe rform   init ia li za ti on  of  ph e r om on e    St ep 2 : R epeat  the foll owin gs   ste ps     1.  C om plete  the tours o f  ( N )  a nts  by m aking   the d eci si on s  usi ng proba bili ty   ( 2 )   2.  Cal c ulate  f it ness value  for t he  to urs  of (N)  an ts acc ordin g t o  ( 3 )   3.   U pd at e  best  ant in form at io n  a nd phe ro m on e  values  on e dg e s c o ns ti tuti ng the t ours usi ng  ( 4 )   St ep 3 :  If   a  m a xim u m   nu m ber   of   Cy cl e  (C)   hav e  been   at ta ined  or   th res ho l d  of  fitness   functi on   i s   reache d  t hen st op   St ep 4 : El se  go  to  Step  2       5.   E X PERI MEN TAL RES UL TS A ND DIS CUSSIO NS   Gen e rall y,  the  per f or m ances   of   any  ev olu t ion a ry  com pu ta ti on   al gorith m   are  cl os el y  relat ed  to  the  par am et ers  val ues.  Th ere fore,   one  of  the   m ain   c halle nge  is  t o  fin d  the   op t i m al   par am et er s  set ti ng  al lowi ng  to   i m pr ove  ef fici ency  of  our  al gorithm .  The  va lues  of   pa ram et ers  ass um ed  in  this  pa per  s uch  as  α ,   β  (wei gh t  of   ph e r om on e  a nd  he ur ist ic   val ue),  N   ( Nu m ber   of  An ts ),  C   ( N um ber   of   Cy cl e),  ‘ Q’  a nd   σ   wer e   fine - tu ne d  by    a  com bin a ti on  of   seve ral  e xp e rim ents  in  orde r  to  opti m iz e  t he  c ryptanaly si s  proces s.  T he  def a ult  val ue  of  the   par am et ers  wa s α=1,  β=1,  Q= 2 ,  =0.9 7   a nd   0 = 5 . We  hav e  im ple m ented  ou r  al gorithm  w it h  C ++ l angua ge.       5.1.    Key sp ace  ana lysis   The  fi rst  pa rt  of   t he  e xpe rim ents  is  to  de te rm ine  the  op tim a l  nu m ber   of   a nts  to  us e   that  al lows   fin ding  the  ke y  in  a  m ini m a l  search  sp ace .   The  e xperim e ntal  res ults  obta ined  i n  this  pa rt  are  il lustrat ed  i n  Table  1.  I n  T hi s  ta ble,  we  ca n  see  the  nu m ber   of   keys  sea rch e d  befor e  l oca ti ng   t he  ree l  key  and   t he  a ver a ge  nu m ber   of Cy cl e C (T he  a verage is cal c ulate d on 10 00 lau nc h) n ee de d  f or  each  value  of  N.       Table  1.  E xper i m ental  r esults  for diffe re nt v a lues  of   N   Used  Key   Nu m b e r  o f  cycles  (C)  n eeded   Nu m b e r  o f  Ants   (N)  us ed   Nu m b e r  o f  Ke y s   b rows ed   Key  f o u n d   C3 F0   -   10   -   BE5 6   C3 F0   -   20   -   C5 F0   C3 F0   -   30   -   C1 2 A   C3 F0   163   40   6520   C3 F0   C3 F0   122   50   6100   C3 F0   C3 F0   106   60   6360   C3 F0   C3 F0   92   70   6440   C3 F0   C3 F0   77   80   6160   C3 F0   C3 F0   66   90   5940   C3 F0   C3 F0   59   100   5900   C3 F0   C3 F0   50   110   5500   C3 F0   C 3 F0   43   120   5160   C3 F0   C3 F0   42   130   5460   C3 F0   C3 F0   42   140   5880   C3 F0   C3 F0   41   150   6150   C3 F0       As  s how n  i n  T able   1,  with  a   sm a ll   nu m ber   of  ants  ( N<40),  ou r  al gorit hm  can no t   locat e  the  real  key,   the  nu m ber   of   ants  is  no t  enou gh   la r ge,   t hu s  t he  best  s olu ti on  f ound  on   eac h  Cy cl e  (which  is   use d  in   ph e r om on e  update)  is  no t  en ough  good,  w hi ch  pen al iz es  the  co nv e rg e nc e  of   the  optim i sat ion   proces s   to  the   rig ht so l ution.    As  note d  i n  th e  Table   1,  wit h  the  values  N =120  we  nee d  43   Cy cl es   to  l ocate  the  real  key  (C=4 3),   t he  real  key  is  fou nd  in  a   m in i m u m   search  s pace.  The   m axi m u m   fitness  va lue  is  r eache d  after  c hec king   51 60   keys,  th us   bei ng  co ns ide ra bly  lower   (b y  a  fa ct or   of  12 )  tha n  the  br ute - f or ce  search  s pac e  siz e  (w hic h  is  equ al   Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A crypt analyt ic  a tt ack  of si mp l if ie d - AES  usi ng  an t c olony  opti miza ti on   ( Hi cham Gr ar i )   4293   to  2 16   possibl e  keys),   a nd   l ow e r  tha n  G A [ 7 ]   an d  PS O[8]  wh ic h  nee d  to  exp l or e  6000  an d  6905   keys,   resp ect ively   , t o  locat e t he rea l on e .   Figure   5  s how s  the  evo l ution  of   the  num ber  of   keys  brow s ed  be fore  locat ing   the  real  ke y  un de r  the   nu m ber   of  ants   us ed  ( N),  It  is  cl ear  from   Fig ur e   that  w he n  the   num ber   of   An ts  is  gr eat e r   than  128,  the  search   sp ace i ncr eases  r a pid ly  w it h n o  im pr ovem ent  of the  num ber   of Cy cl e (C).         Figure  5. N umber  of  key sear ched ev olu ti on       5 . 2.     Relev an ce  of the  fit ness  fu nc tion    The  desig n  of   fitness  f unct ion   is  a  c ru ci a l  st ep  in  ev ol ution   al gorith m s.  In   order   t o  assess  t he   releva nce  of   our  fitness   f un c ti on ,  t he  c orre la ti on   coe ff ic i ent  ‘C orr’   bet ween  the  c os t   functi on  ( 3 )  and  the   nu m ber   of  co r rected  key  el e m ents  (Num ber   of   c orrect  bits  in  t he  key)  i s  cal culat ed  usi ng   ( 5 ) ,   f or   di f fer e nt  values  of z  ( num ber  o f k now n plai ntext - ci ph ertext  pairs use d).   This  coe ff ic ie nt   is  us ed  to  eva luate   the  relat ion s hi p  betwee n  the  co st  func ti on   an d  the  num ber   of   ke y   el e m ents   corre ct ly   reco ve red.   In  the  ca se  of  a  perfect   direct   (inc reasin g)  li nea r  relat ionsh ip  we   ha ve  C orr  =   1,  it s  m eans  that  we  ha ve  a  good  m echan ism   f or   e valuati on  of  ge ner at e d  ke y,  therefo re  th e  conve rg e nce  of   our   al gorithm   to  the  best  key  is  m os t  gu ara nteed.   Inve rsely ,  in  a  perfect   dec reasin g  li nea r  relat ion s hip   w e  ha ve   Corr  =  - 1.  Fi gure   6   s hows  the  val ue  of   t he  c orrelat ion  coeffic ie nt  be tween  our  fitn ess  f un ct io n  a nd  the   nu m ber   of  corr ect ed  key  el e m ents,  f or   dif fe r ent  nu m ber   of  known  plainte xt - ci pherte xt  pa irs.  To  cal cul at e  this   coeffic ie nt,  w e   hav e  us e d  10 00   keys  as  sa m ple,  by  cal culat ing   the  fitne ss  an d  the  c orr ect   nu m ber   of  bits  for  each  on e .      ( , ) = ∑   − ∑   ∑   √ ∑ 2 − ( ∑ ) 2   √ ∑ 2 − ( ∑ ) 2          ( 5 )     Wh e re  x  a nd y  are tw o  a rr ay s  of n el em ents.   As  s how n   in  F igure   6 ,  t he  correla ti on   c oe ff ic ie nt  inc re ases  with  t he  nu m ber   of   pai r  use d,  but     from   3  pairs  re qu i red,  we  note   a  sta gn at i on   of   t his  coe ff ic i ent.  T he  us e  of   3  pairs  in  t he  fitness  f unct io n  gi ves   alm os t  the  sam e  resu lt s  as  z=2,  wh il e  the   us e  of  a  sin gle  pair  can  dr i ve   the  al gorith m   to  a  so luti on  with  a  m axi m u m  f it ness  f un ct i on v al ue wit hout  bei ng the  rig ht  ke y.           Figure  6. Co rr e la ti on  coe f fici ent evoluti on  th rou gh num ber   of kn own plai nt ext - ci pherte xt     0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 7 0 0 0 10 20 30 40 50 60 70 80 90 1 0 0 1 1 0 1 2 0 1 3 0 1 4 0 1 5 0 Nbr  o f  K ey   sea rched Num ber  o f  Ants  (N) Evaluation Warning : The document was created with Spire.PDF for Python.
                          IS S N :   2088 - 8708   In t J  Elec  &  C om p  En g,   V ol.  9 , N o.   5 ,  Oct ober  20 19  :   4287   -   4 2 9 5   4294   5 . 3.     Nu mber  of  plainte xt - ci pher te xt p airs  anal ys is   Our  pr opos e d  appr oach   al lo ws  us  to  fi nd   t he  key  us in g  only   two  know n  plainte xt - ci pherte xt  pairs ,   wh e reas i n oth er att acks t he n um ber  of  plain te xt - ci pherte xt  pairs re qu ire d  is   re ported  in  T able 2.       Table  2.   N um ber   of   plainte xt - ci ph e rtext  requ ired fo r  at ta cki ng   Metho d o lo g y   Ro u n d s attack ed   Nu m b e r  o f  Plainte x t - Cip h ertext  p air  requ ired   Linear c ry p tan al y s is   Mus a [ 3 ]   Ro u n d  1   109   Linear c ry p tan al y s is   Dav o o d  [ 5 ]   Ro u n d  1   116   Ro u n d  1 &  Ro u n d   2   548   Linear c ry p tan al y s is   Bizak i [ 4 ]   Ro u n d  1 &  Ro u n d   2   96   Usin g  GA   Vi m alath ith an  [ 7 ]   Ro u n d  1 &  Ro u n d   2   3   Ou r  Ap p roch  us in g  ACO   Ro u n d  1 &  Ro u n d   2   2       A  fitnes s  f unct ion   base d  on  only   on e   pair  of   known  plainte xt - ci pherte xt  ( z=1  in  t he  ( 3 ) ),  we  ca n  fin d  a  so luti on  t hat m axi m iz es  the  fitness f unct io n  bu t wit hout bei ng   t he  reel k ey .  The refor e ,   the  nee d  for  a s econd  pair pr oves  nec essary t o co nf i rm  that is t he  ri gh t  key.     5 . 4.     Pherom on e   se nsitivit y an alysi s   In   orde r  to   analy se  the  pher om on e  trai ls  eff ect   with in  the  s ol utio ns   c onstruc ti on  process.   The  nu m ber   of   ants  ( N)  is  fix ed  at   12 0  a nd   β  at   1.   First,  w e  us e d  a  rather  stron g  phe rom on e  con ce ntr at io n,   il lustrate d  by  t he  value  α   =  2.   As  s how n  i n  Fi gure  7 ,  w e  can  obser ve   as  an  ea rly   sta gn at io n  of  re search   because   of   t he   al gorithm   has  cease d  e xplo ring  ne w  possibi l it ie s.  In ve rsel y,  with  a  t oo  weak  guida nce   of  the   search ,  we   not ic ed  an  e xcess ive  ex plorat ion  of   t he  sea rch   sp ace,  t his  un de sirable  b eha vi our  is  il lustrat ed  in   the  F igure 8   with   α   is   equ al   to  0. 5.  As  a   resu lt ,  the  search  al gorith m   is   no t  able  to  converge  to   an   op ti m al  so luti on .   The  best  res ults  are  ob ta ine d  with  α   =  1.2 .  T hu s ,  a  qu ic k  c onve r gen ce  of  the  al gorithm   to  the  c orrect   key  is  obser ve d  in  this  case .  Con cl ud i ng   t ha t  the  rig ht  pa ram et ers  are  tho s e  al lowi ng   a  reasona ble  ba la nce  betwee n  a t oo  narrow  f ocu s  of the  searc h process a nd a t oo w ea k gu i dan c e.           Figure  7 .  Fitne ss F un ct io n  e voluti on  for diff eren t  values  of  α       6.   CONCL US I O N   In  this  pap e r  the  ne w  a ppr oach  to  break ing   Sim plifie d - AE S  was  presented   us i ng  ant  c olon y   op ti m iz ation .  This  m e tho d  oc curred  to   be  qu it e  eff e ct ive  and   prom isi ng .  The  ex per im e ntal  resu lt s  sho w  that   our  ap proac h  i s  sign ific a ntly   faster  a nd   requ ires  a  sm aller  nu m ber   of   known  plainte xt - ci ph e rtext  pairs,   wh e n  com par ed  t o other s  att acks.   ACO  pro vid es   a  ver y  powerf ul  too l  for  the  cryptan al ysi s  of  Sim plifie d - A ES,  it   is  intere sti ng   to  be   app li ed   to  c ryp ta naly sis  of   som e  oth ers   str ong  enc ryptio n  al gorithm s  li ke   DES  ( Data  en crypti on  Al gor it h m )   or A E S (A dva nced E ncr ypti on Sta nd a r d) .   Evaluation Warning : The document was created with Spire.PDF for Python.
In t J  Elec  &  C om p  En g     IS S N: 20 88 - 8708       A crypt analyt ic  a tt ack  of si mp l if ie d - AES  usi ng  an t c olony  opti miza ti on   ( Hi cham Gr ar i )   4295   REFERE NCE S     [1]   Sala ba t  Khan,   Arm ughan  Ali  and  Mehr  Yah y a   Durrani ,   "A nt - Cr y p to,   a  Cr y ptogr aphe r  for   Data   Enc r y pt i on  Standa rd, "   IJCSI ,   vol .   10 ,   no   1,   Jan  2013.   [2]   Hicha m   Grari ,   Ahm ed  Azoua oui  Khali d  Z ine - Dine,   "A   Novel   Ant  Colon y   Op ti m iz ation  Base d  Cr y pt ana l y sis  of  Subs ti tut ion  C ip her , "  In te rnation al  A fro - Europea n  Confe ren c e   for   Industrial Adv a nce ment   A ECIA ,   2016.   [3]   M.  A.  Mus a,   E . F.  Schae f er,   S.   W edi g,   "A   Sim pli fie d   AES  al gor it hm   and  it s  li ne ar  and  Diff ere n tial  Cr y pt ana l y sis ",  Cryptol ogia ,   pp . 148 - 177,   Apr 20 03.   [4]   H.  K.  Bi za ki ,   S.   David  Mansoor ,   A.  Fa la ha ti,  "L ine ar  C r y pta n alys is   on  Second  R ound  Mini - AES" ,   Inte rnat ional  Confe renc e  on   I nformation  and  Comm unic ati on  Techmologi es ,   2 006,   pp .   1958 - 1 962.   [5]   S.  D.  Mansoori ,   H.  Khal eghei   Biz ak i,   "O n  t he  Vulner abi l ity  of  Sim pli fie d  AES  Algorit hm   Against  Li n ea r   Cr y pt anal y sis , "  I nte rnational   Jou rnal  of  Comput e r Sc ie n ce and  N e twork  Se curit y , v ol.   7 ,   n o.   7 ,   pp .   2 57 -   263 ,   2007 .   [6]   Sim m on s   S. ,   " Al gebr aic cr y pta n a l y sis of   sim pli fi e d  AES ,"   Crypto l ogia ,   vo l.  33 ,   no.   4,   pp.   305 – 314 ,  2009 .   [7]   Vim al at hit h an  M.  Om ana ,   C.   Metra ,   " Cr y pta n aly s is  of  Sim pli f ie d - AES  En cr y p te d  Com m unic at ion ,"   Inte rnation a l   Journal  of   Computer  Sc ie nc e  and   Information  S ecur it y  ( IJCSI S) ,  v ol.   13 ,   n o .   10 ,   O ct   2015 .   [8]   Vala rm at hi   M.   L . ,   Vim alathithan ,   R. ,   " Cr y pt anal ysis  of  sim pli fie d - ae s  us ing  par ti c le   sw arm  opti m i za t ion, "   Def ence  Sci .   J . ,   vol .   62 ,   n o.   2 ,   117 – 121 ,   2 012 .   [9]   Rani a  Sa ee d   (B)   and  As hra f  Bh e r y ,  " Cr y pta n aly s is  of  Sim pli fie d - AES  Us ing  Inte l li gent  Agent ,"   1 0th  Inte rnat iona l   Confe renc e, HA I S  2015 ,   Bil b ao,  Spain,   June   22 - 2 4,   2015 .   [10]   M.  Dorig o,   V.  Manie z zo,   A.   Colorni ,   " Th e  an t   s y stem:  Optimi za t ion  b y   a  col o n y   of  coope r at i ng  age nts,"   I EEE   Tr ansacti ons on Systems,  Man ,   a nd  Cybe rne ti cs - Part  B ,  vo l.  26 ,   no.   1 ,   pp .   29 - 41 ,   1996 .   [11]   M.  Dorigo,   L.   Gam bar del la,   " Ant  col on y   s y st em:  A  coope rative   learni ng  ap proa ch  to  th e  tr ave l ing  sale sm a n  proble m , "   IE EE  Tr an sacti ons on Evol ut ionary  Co mputati on ,   vol .   1,   pp . 1,   pp.   53  - 66 ,   1997 .   [12]   T.   Stu tz l e  and  H.  Hoos ,   " Im prove m ent s  on  th e  an t  s y s te m ,   i ntroduc ing   the  MA X - MI N  ant   s y stem, "   in   Pro c.  ICANNGA97 — Thir d  Int.   Con f.A rtif icial  N eural  Net works  and  Gene tic  A lgorit hms ,   W ie n,   Ger m an y :  Spring er - Verl ag, 1997.       BIOGR AP H I ES   OF  A UTH ORS       Hi cham  Gr a ri   is  a  PhD   student   withi n  the   LAROS ERI  La b.   a t  Facul t y   of  Sci enc es  –   Chouaib  Doukkal i  Univ e rsit y ,   El   Jad ida/ Morocc o.   H e  h olds  an  E nginee r  Degre e   in   Co m pute r  S ci en ce   i n  2005.   His do ct or a l  r ese ar ch inve s ti gates t h e  use   of   m et ahe ur isti cs  i n  cr y pto log y   f ie l d.           Ah me d  A z ouo ui   rec ei v ed  his   li ce nse  in  Co m pute r  Scie nc e   and  Engi ne eri n g  in  June - 2001  and   Master   in  Com p ute r  Sci ence   an d  Te l ec om m unic ation  from   Uni ver sit y   of  Moh a m m ed  V  -   Agd al ,   Ra bat,  Morocc o   in  2003.   H e  re ce iv ed  his  PH D  in  Com pute r   S ci en ce   in  2014  and  Engi n ee r ing   at   Depa rtment  of  Com pute r  Scie n ce ,   ENSIA S  (N at ion al   School  of  Com pute r  Scie nc e  and  S y st em s   Anal y sis) ,   Rabat,   Morocc o .   Cur ren tly ,   he  is  an   As socia te   P rof essor  at   Depa rt m en t  of  Com pute r  Scie nc e,   Fa cult y   of   sci enc es ,   Univer sit y   Cho uai b  Do u kka l y ,   El   Jad ida,  Mo roc co.  His  ar eas   of   int er est  ar e  In for m at ion   s y s te m s ,   Coding  Th eor y   a nd  Artificial  In telli gen ce.         Khali d  Z ine - Di ne   recei v ed  his  PhD   degr ee   from   the   Moham me d  V  Univer sit y  of  Raba t,   Moro cc o,   in  2000.   He  spe nt  four  y ears   in  bank  Inform at io n  S y stem  as  a  n et work  &  s y s tem   sec urity   proj e ct   m ana ger .   Curr e ntly ,   h e  is  an  As socia te   Profe ss or   and  le ad   o f  LAROS ERI  La b.   at   Fa cult y  of     Scie nc es  –   Chou ai b  Doukka li   Un ive rsit y ,   E l  Jadi d a/ Morocc o .   His  r ese arc h   intere sts   are  in  the   area  o f  wire le ss   ad  ho c  and  sensor  net w orks,  Mobili t y ,   c loud  computing ,   m ic rogrid   and  s y stem  &  n et wor k   arc hi te c ture s  an d  protoc ols.  Dr.   Zi ne -   Dine  was   a  co - orga n iz er  and  co - ch ai r   of  conf ere n ce s  and   is  invol ved   in  m or e  th an  06   PhD   T hesis  and  fu nded   rese a rch   pro ject s.     Evaluation Warning : The document was created with Spire.PDF for Python.