home *** CD-ROM | disk | FTP | other *** search
/ Chaos Computer Club 1997 February / cccd_beta_feb_97.iso / chaos / ds56 / ds56_13.txt < prev    next >
Text File  |  1997-02-28  |  5KB  |  149 lines
  1. Is No, Much Gooc!
  2.  
  3. A cioser lock at the
  4. A5 GSM Eneryption
  5. Algorithm
  6.  
  7. (
  8.  
  9. >From sci.crypt Fri Jun l 7 17:11~49 1994
  10. From: na14@cl.cam.ac.uk (Ross Anderson)
  11. Date: 17 Jun 1994 13:43:28 GMT
  12. Newsgroups sci. crypt,alt.security,uk.telecom
  13. Subject: A5 (Was: HACKING DIGITAL PHONES)
  14.  
  15. The GSM encryption algorithm, A5, is not much good. Its effec-
  16. tive key length is at most five bytes; and anyone with the time
  17. and energy to look for faster attacks can find source code for it
  18. at the bottom of this post.
  19.  
  20. The politics of all this is bizarre. Readers may recall that there
  21. was a fuss last year about whether GSM phones could be expor-
  22. ted to the Middle East; the official line then was that A5 was too
  23. good for the likes of Saddam Hussein.
  24.  
  25. However, a couple of weeks ago, they switched from saying that
  26. A5 was too strong to disclose, to saying that it was too weak to
  27. disclose! The government line now pleads that discussing it
  28. might harm export sales.
  29.  
  30. Maybe all the fuss was just a ploy to get Saddam to buy A5 chips
  31. on the black market; but Occam's razor saggests that we are
  32. really seeing the results of the usual blundering, infighting and
  33. incompetence of bloated government departments.
  34.  
  35. Indeed, rny spies inform me that there was a terrific row bet-
  36. ween the NATO signals agencies in the mid 1980's over whether
  37. GSM encryption should be strong or not. The Germans said it
  38. should be, as they shared a long border with the Evil Empire;
  39.  
  40. \
  41.  
  42. ~ n1 \N
  43. Kabelsalat ,~`
  44. \ C~, ist gesund ─rG\~O~/
  45.  
  46. W'~,.
  47.  
  48. but the other countries didn't feel this way, and the algoritEm as
  49. now fielded is a French design.
  50.  
  51. A5 is a stream cipher, and the keystream is the xor of three clock
  52. controlled registers. The clock control of each register is that
  53. register's own middle bit, xor'ed with a thresholrl function of
  54. the middle bits of all three registers (ie if two or more of the
  55. middle bits are 1, then invert each of these bits; otherwise just
  56. use them as they are). The register lengths are 19, 22 and 23, and
  57. all the feedback polynomials are sparse.
  58.  
  59. Readers will note tbat there is a trivial 2A40 attack (guess the
  60. contents of registers 1 and 2, work out register 3 from the key-
  61. stream, and then step on to check whether the guess was right).
  62. 2A40 trial encryptions could take weeks on a workstation, but
  63. the low gate count of the algorithm means that a Xiliox chip can
  64. easily be programmed to do keysearch, and an A5 cracker might
  65. have a few dozen of these running at maybe 2 keys per micros-
  66. econd each. Of course, if all you want to do is break the Royal
  67. Family's keys for sale to News International, then software
  68. would do fine.
  69.  
  70. It is thus clear tbat A5 should be free of all export controls, just
  71. like CDMF and the 40-bit versions of 1<C2 and RC4.
  72.  
  73. Indeed, there seems to be an even faster attack. As the clock con-
  74. trol is stop-go rather than 1-2, one would expect some kind of
  75. correlation attack to be possible, and on June 3rd, Dr Simon
  76. Shepherd of Bradford University was due to present an attack
  77. on A5 to an IEE colloquium in London. However, his talk was
  78. spiked at the last minute by GCHQ and all we know about his
  79. attack is:
  80.  
  81. (a) tbat sparse matrix techniques are used to reconstruct the
  82. initial state (this was published as a trniler' in the April 93
  83. Mobile Europe');
  84.  
  85. (b) that he used some of the tricks from my paper 'Solving a
  86. class of stream ciphers' (Cryptologia XIV no 3 1July 90] pp
  87. 285 - 288) and from the follow-up paper Divide and con-
  88. quer attacks on certain classes of stream ciphers, by Ecl
  89. Dawson and Andy Clark (Cryptologia XVIII no 1 [Jan 94]
  90. pp 25 - 40) (he mentioned this to me on the phone).
  91.  
  92. I believe that we have to stand up for academic freedom, and I
  93. hope that placing A5 in the public domain will lead to the
  94. embargo on Simon's paper being lifted.
  95.  
  96. ~=_
  97.  
  98. ~ ,
  99.  
  100. Sir arheirc~ in, Inneq. und AuBcrdKn"
  101. herLhulien blal ru lilH ern ~rtr~ di~;o aus
  102. undnchmen Yerwuhung~i~ql~n wilhl
  103.  
  104. hrinlen~ Rtife p-us ab~rehlu~eer kauf
  105. rnDil1niycl1er ll~'tl,ll. Min~c`Litiltr IÄ 31lht'.
  106. d eu ts ehe StlLcls an~ehiri,~ keit, 7L`~rUL~Il -
  107.  
  108. ·cit. kcinc V«,rslreicn uar krine .'iehuidt~.
  109.  
  110. ~''
  111. lo n~ch V~rbildimg-~isel~u I und 1 J.lh-
  112. ren. `'iu;h dir Pn~bc~h lirocnn~l~g r.un, lic
  113.  
  114. ;~ll`ä ;~Hr I C~lYldi! (~I8tL'iH(l~t).
  115.  
  116. I;l;~1'1Ll'l'llLi]'l;lL~dfllLä
  117. Ie na,ch Aher ond Famil~n~amd zwisehe~
  118. I Kiltl urd 21UO ~nrk
  119. r~
  120.  
  121. 14Dch ller~ccb vun lirlhildon'sikursen Aul-
  122. sli~q inJcleich~hcxu3)ien~q m~li~h.
  123.  
  124. ~3
  125.  
  126. /11111~1 ~ti vil'~ICiLLi ·lilI.
  127.  
  128. ~m
  129.  
  130. ]c ruL'cl, 1~116~C~I. fill~t U'l~l ram~lLcmiart
  131. 7.wischen 3 SOI) urd li INhl ldialk l~>r.rb
  132. hci' licomie hri~u~hrn k~ina S'lzial`'er~
  133. ~hera 1t. ~u z`Lhlell.
  134.  
  135. ~ D! I ' 1
  136.  
  137. 1~'l, I`li' Ah~L~h~lll'`f' urJ hl,~:l' |i
  138. cuer. jc ~lach Eir=~' Ak P'c~mier
  139. l;cinL Kbodigung. gutc Aller``ersorguag
  140.  
  141. Writ~re Ird~ b'l
  142. ,..."l..;.A~/.,,.~ ~pl, lFrir~n«~l~. ~a
  143. ~.~4 ~ '1~.n t ~ `~.lvI7v'~ I {.7 `'Ie~r bri ~L ~ .,rl(,
  144.  
  145.     .I~.~..IdA.    ~L~ Hr~ed~ vwr~
  146.  
  147.     ·unuuuunn-uu-uuu    ~ie~Qten~c~leuber#~56    0ic~nten~c~leu~er#.~6    ·uunu.----~--.
  148.  
  149.