Date | Revision |

3 May 1998 | Link to Cryptanalysis of Alleged
A5 Stream Cipher and On Random Mappings and Random Permutations |

30 April 1998 | Add Hanche-Olsen message |

28 April 1998 | Add Wagner/COMP128/Masson/ISN/Anon messages
Link to Chaos Computing Club GSM Hack |

25 April 1998 | Add Payne/Rose messages |

24 April 1998 | Add Anderson message |

23 April 1998 | Add Möller message |

22 April 1998 | Add A5 implementations and
Anderson/Leyland messages
Link to GSM paper: http://sky.fit.qut.edu.au/DataComms/Teach/units.972/itn530/ass/wkho/assign.htm |

20 April 1998 | Link to GSM consortium statement
Add Masson and Assange messages Link to 1988 GSM security study |

19 April 1998 | Add Briceno message |

18 April 1998

Date: Fri, 17 Apr 1998 16:28:05 +0200 From: Loos <david.loos@eudoramail.com> To: jya@pipeline.com Subject: CRACK A5 Yes, americanphreakers clone a SIM card GSM (A5/A8, IMSI,...) But, it's actually impossible to decrypt an air-interception conversation GSM. A5/A8 is not the full key crypting a consersation GSM. Illusion a sucessul of decyption is done:MOBILE EUROPE4.93: " Feedback from academic research by a leading university cryptographic research group (R. Anderson,..) in the UK is indicating that the much-vaunted GSM A5 cipher algorithm may not be a secure as first tought . The group has reported a 75% (!) success rate in recovery of the cipher bit stream and anticipate that it will not be long before a complete realtime off-air decryption is achieved (wrong!!). The A5 algorithm uses a three level, non-linear feedback shift register arrangement, designed to be sufficiently complex to resist attack. However, using new Russian techniques in sparse matrix inversion, the group have been able to determine accurately at least three quarters of the 114 bits used for encrypting and decrypting each message packet. The A5 cipher has been at the root of the controversy over the export of GSM to non-Cocom countries, and has been responsible for severely impeding the export potential of the system. A "watered down" version of the algorithm, codenamed "A5X ", has been proposed for equipment destined for controlled areas, while the original group CEPT countries responsible for the introduction of GSM will retain the A5 (A5-1) cipher system." interception@ii-mel.com Masson

Dear David Loos, Thanks for your note. Christian Masson has recently sent commentary on the impossibility of decrypting GSM air-interception to the mail list Cypherpunks <cypherpunks@cyberpass.net>. The three American "phreakers" subscribe to the Cypherpunks list. You might want to post your criticisms there for discussion. Also, on the mail list UK Crypto <ukcrypto@maillist.ox.ac.uk> there has also been discussion of GSM, A5 and R.J. Anderson's A5 paper. According to one writer the paper does not address all the aspects of the recent crack (see copy of message below). R.J. (Ross) Anderson <Ross.Anderson@cl.cam.ac.uk> subscribes to UK Crypto and surely would like to respond to your and Masson's critiques. Also, see Anderson's bountiful computer security Web site at: http://www.cl.cam.ac.uk/users/rja14/ Perhaps you'd like to discuss this more with the GSM crackers directly. I'd suggest David Wagner <daw@cs.berkeley.edu>. Please let me know what new information you learn from Dave or from any others who are probing A5 and GSM. BTW, have you seen the leaked Racal Research document listed at SDA site as the source of the A3A8 algorithm? http://www.scard.org/gsm/a3a8.txt This 1988 document was sent to us in early 1997. It includes not only the German COMP128 used by the crackers but also the French cipher proposed for GSM. Regards, John Young ---------- UK Crypto message: To: ukcrypto@maillist.ox.ac.uk Subject: Re: More on A5 strength From: Julian Assange <proff@iq.org> Date: 17 Apr 1998 07:31:39 +1000 David Hopwood <hopwood@zetnet.co.uk> writes: > According toApplied Cryptosection 16.5, > # There is a trivial attack requiring 2^40 encryptions: Guess the > # contents of the first two LFSRs, then try to determine the third > # LFSR from the keystream. (Whether this attack is actually > # feasible is under debate, but a hardware key search machine > # currently under design should resolve the matter soon [45].) > > [45] is: > # R.J.Anderson, "On Fibonacci Keystream Generators," K.U. Leuven > # Workshop on Cryptographic Algorithms, Springer-Verlag, 1995, > # to appear. > > Is that Ross Anderson - if so, how did this work out? Ross is into everything :) I haven't read Ross's [45] - I doubt it is about A5 per se, but rather about chaining of multiple LFSR's (A5 uses three), (Ross, please correct me) - and Bruce (or someone else) has seen that Ross's attack applies to A5. Note that there are several versions of A5, some telco's have phones which use A5/7 - these latter versions tend to be even weaker than A5/2! It's worth noting that AP 16.5, to my knowledge is talking about the proposed (untested) reconstruction of A5, and not a confirmed implementation. In Underground (http://www.underground-book.com/), (pub. June 1997), we presented transcripts from a Dete-Mobil (Deutche-Telekom) GSM monitoring port, which showed that at least the last 8 bits of key were all zero'd. Cheers, Julian.

Date: Thu, 16 Apr 1998 16:19:20 +0200 From: masson <interception@ii-mel.com> To: cypherpunks@cyberpass.net Subject: A5-1/A8 is not the definitive key GSM! Key A5-1/A8 GSM Dear Sir, The key encypts an air-consersation GSM is A5-1 or A5-2 + A8 + local hour (12:10:21) of the network where the GSM is. Except government, nobody could decode an air-interception of a conversation GSM. After, the BSC, the consersation GSM is clear. Foreigner air-interception GSM are made case by case. In Munchen , Rodhes & Schwarz sells a logger permits to catch IMSI, aso (no coded); See http://jya.com/gsm-cloned.htm http://www.ii-mel.com/interception/europegb.html http://www.ii-mel.com/interception/belgiquegb.html http://jya.com/snoop-gsm.htm MOBILE EUROPE magazine presents under subject "crack A5?" a pseudo-sucess. To prevent governmental leakage of private informations. The real scandal is the MOBILE TRACE (recognize by headquarters of GSM MoU of Dublin) tracing and storing the moving of each GSM in standbye (2X/H)! 80-100 millions MOBILE TRACE. Thks fr yr comments + regards, C. Masson

Date: Sun, 19 Apr 1998 16:01:12 +1000 (EST) From: Marc Briceno <marc@scard.org> To: John Young <jya@pipeline.com> cc: interception@ii-mel.com Subject: Re: Masson This list apparently has seen some posts about A5 lately. I don't have the time to write a paper on this topic at the moment, so here is a list of facts known to be true. 1. I discovered COMP128. COMP128 is widely used as the GSM authentication algorithm (A3) and session key generating algorithm (A8). 2. The 64 bit output of A8 is used as the session key for A5 (including all A5 variants), a 64 bit cipher 3. A8 has been _deliberately_ weakened to provide only 54 bits of entropy. This is done by setting the last 10 bits of the A8 output to be always 0. 4. Assuming the cipher used is COMP128, the output of A3 and A8 is determined by exactly two factors: - The SIM's internal key Ki. - The random challenge sent by the base station. 5. We showed how to extract Ki from a SIM in our posession. A rogue base station could perform the same extraction of all the Ki's from all the GSM phones within the area covered by the rogue base station. 6. The challenge can be intercepted off the air. 7. From 2. and 4. follows that an attacker that knows the challenge (obtainable over the air) and the SIM's internal key Ki (obtainable over the) can determine the session key used by the on-the-air voice privacy algorithm A5. 8. Assuming the attacker knows A5, the attacker can therefore decrypt the voice privacy features. 9. Note that given the above facts, no cryptanalysis of A5 is required to compromise the voice privacy features of the GSM call of interest. -- Marc Briceno <marc@scard.org> Director, Smartcard Developer Association http://www.scard.org On Sat, 18 Apr 1998, John Young wrote: >Date: Sat, 18 April 1998 >To: interception@ii-mel.com >From: John Young <jya@pipeline.com> >Subject: Masson >cc: <marc@cryptsoft.org> > > Christian, > > We have put the "David Loos Crack A5" messages at: > > http://jya.com/crack-a5.htm > > There seems to be disagreement about the possibility of air-intercept. > See Marc Briceno's comments at <http://jya.com/gsm-cloned.htm> . > > Perhaps you should write Marc <marc@cryptsoft.com> to > reach agreement on the facts. > > Let me know what you hear from the Americans or British > about your comments on air-intercept of GSM. > > Regards, > > John Young

Date: Mon, 20 Apr 1998 14:40:29 +0200 From: masson <interception@ii-mel.com> To: jya@pipeline.com Subject: CRACK A5-1/A8 Dear John, ______________________________________________________________ Pls find and add if you wish the australian answer about A5. Add draw "canal radio" in www.ii-mel.com/interception/europegb.html Add draw humour draw for MOBILE TRACE GSM. ______________________________________________________________ SUBJECT: A5-1/A8 & air-interception GSM A5 use A8 but also a pseudo-aleatory number, the local hour of the GSM network. This apsect is not approached by Ross Anderson or Marc Briceno. A public success in cracking an air-interception GSM is a bluff! After you crack A5 (actually, only a government is able to crack A5 and rebuilt GSM voice): to understand the voice (8 X 26 bits per 4,6ms), you must rebuild and stick millions and millions of TELECOM bursts. Min. 4 days of work is required for 2mm of communication GSM (CRAY T3E,...) by an governmental interception. interception@ii-mel.com ---------- From - Mon Apr 20 13:54:38 1998 To: interception@ii-mel.com Subject: Re: CLONE SIM CARD GSM From: Julian Assange <proff@iq.org> Date: 19 Apr 1998 08:31:28 +1000 masson <interception@ii-mel.com> writes: 'alo masson. > Ross Anderson lies by omission. (he breaks at 75%: in clear 0%). Err, what do you mean exactly? > The clone of SIM CARD GSM is not a decryption of the encryption key of GSM > conversations (by air) and eachtime different and dont stay on SIM card. Yes. Although I'm not sure that you couldn't get the GSM to do 100k authentications by over-powering a MSC signal asking for authentication, and thus calculate Ki. Speaking of which, some investigative services are now using fake MSC's (i.e mim's) to monitor call traffic. Cheers, Julian.

Subject: RISKS DIGEST 14.60 REPLY-TO: risks@csl.sri.com RISKS-LIST: RISKS-FORUM Digest Wednesday 12 May 1993 Volume 14 : Issue 60 FORUM ON RISKS TO THE PUBLIC IN COMPUTERS AND RELATED SYSTEMS ACM Committee on Computers and Public Policy, Peter G. Neumann, moderator [Snip] ------------------------------ Date: Mon, 3 May 1993 19:27:33 +0200 From: brunnstein@rz.informatik.uni-hamburg.dbp.de Subject: Mobile ComSec in Europe (A5) Stimulated by the "Cripple Clipper" Chip discussions, I invested some time to investigate the European approach in this area. Mobile communication security is practically available, since some time, in Western Europe based on some technology which will now alsp be applied in Australia [see Roger Clarke: Risk Forum 14.56). In contacts with people from producers, carriers and Telecom research, I collected the following facts: - Dominated by Western European telecommunications enterprises, a CCITT subsidiary (CEPT=Conference Europeenne des Administrations des Postes et des Telecommunications; founded 1959, presently 26 European countries, mainly from Western/Northern Europe) formed a subgroup (ETSI=European Telecommunications Standards Institute) which specified, in a special Memorandum of Understanding (MoU) the GSM standard (=Groupe Special Mobile). Presently, ETSI (planned as EEC's Standardisation Institute in this area) has 250 members from industry (63%), carrier (14%), government (10%), appliers and research (together 10%). Research here means essentially Telecom and related "research" institutes. - GSM documents specify roughly the functional characteristics including secure encryption of transmitted digital messages (see "European digital cellular telecommunication system (phase 2): Security Related Network Functions"). Apart from protocols, details of algorithms are secret. - GSM contains 3 secret algorithms (only given to experts with established need-to-know, esp. carriers or manufacturers): Algorithm A3: Authentication algorithm, Algorithm A8: Cipher Key Generator (essentially a 1-way function), and Algorithm A5: Ciphering/Deciphering algorithm (presently A5/1,A5/2). Used in proper sequence, this set of algorithms shall guarantee that NOBODY can break the encrypted communication. - Mobile stations are equipped with a chipcard containing A3 and A8, plus an ASIC containing A5; the (non-mobile) base stations (from where the communication flows into the land-based lines) is equipped with an ASIC realising A5 encryption, and it is connected with an "authentication center" using (ASIC, potentially software based) A3 and A8 algorithms to authenticate the mobile participant and generate a session key. - When a secure communication is started (with the chipcard inserted in the mobile station), authentication of the mobile participant is performed by encrypting the individual subscriber key Ki (and some random seed exchanged between the mobile and base station) with A3 and sending this to the base station where it is checked against the stored identity. Length of Ki: 128 bit. - If authenticated, the individual subscriber key Ki (plus some random seed exchanged between mobile and basis station) is used to generate a session key Kc; length of Kc: 64 bit. Different from Clipper, a session key may be used for more than one session, dependent on the setting of a flag at generation time; evidently, this feature allows to minimize communication delays from the authentication process. - Using session key (Kc), the data stream (e.g. digitized voice) is en- crypted using the A5 algorithm and properly decrypted at base station. - A more complex authentication procedure including exchange of IMSI (International Mobile Subscriber Identity) may be used to authenticate the subscriber and at the same time to generate the session key (using a combined "A38" algorithm) and transmit it back to the mobile station. Comparing the European A5 approach with US' "Cripple Clipper Chip", I find some surprising basic similarities (apart from minor technical differences, such as key lengths and using ASICs only versus Chipcard in the mobile station): 1) Both approaches apply the "SbO Principle" (Security by Obscurity): "what outsiders don't know, is secure!" Or formulated differently: only insiders can know whether it contains built-in trapdoors or whether it is really secure! 2) Both approaches aim at protecting their hemisphere (in the European case, including some interest spheres such as "down-under", to serve the distinguished British taste:-) from other hemispheres' competition. The most significant differences are: A) that US government tries to masquerade the economic arguments with some legalistic phrases ("protect citizen's privacy AND protect them against criminal misuse") whereas Western Europeans must not argue as everybody knows the dominance of EEC's economic arguments (and the sad situation of privacy in most EEC countries :-) B) that US government must produce the rather complex "escrow agencies" where European law enforcers must only deal with ETSI (manufacturers and carriers!) about reduced safety in "A5/n" algorithms (n=1,2,...). Presently, different "A5/n" algorithms are discussed. Apart from the "secure" original algorithm A5 (now labeled A5/1), a "less secure, export oriented A5/2" has been specified (according to my source which may not be fully informed, this will go to "down-under" :-). One argument for such "A5/n" multiplicity is that availability of more A5/n algorithms may even allow to select, during authentication, one algorithm from the set thus improving security of communication; at the same time, as these algorithms are secret, the secret automatic selection (e.g. triggered by some obscure function similar to the random exchange in the authentication process) may allow to crack the encrypted message. My (contemporary) conclusion is that security of both A5 and CC is questionable as long as their security cannot be assessed by independent experts. In both cases, economic interests seem to play a dominant role; there are clear indications of forthcoming economic "competition", and I wonder which side Japan will take (maybe they decide to start their own crippled SecureCom standard?) Klaus Brunnstein (Univ Hamburg; May 3, 1993) ------------------------------

From sci.crypt Fri Jun 17 17:11:49 1994From: rja14@cl.cam.ac.uk (Ross Anderson) Date: 17 Jun 1994 13:43:28 GMT Newsgroups: sci.crypt,alt.security,uk.telecom Subject: A5 (Was: HACKING DIGITAL PHONES) The GSM encryption algorithm, A5, is not much good. Its effective key length is at most five bytes; and anyone with the time and energy to look for faster attacks can find source code for it at the bottom of this post. The politics of all this is bizarre. Readers may recall that there was a fuss last year about whether GSM phones could be exported to the Middle East; the official line then was that A5 was too good for the likes of Saddam Hussein. However, a couple of weeks ago, they switched from saying that A5 was too strong to disclose, to saying that it was too weak to disclose! The government line now pleads that discussing it might harm export sales. Maybe all the fuss was just a ploy to get Saddam to buy A5 chips on the black market; but Occam's razor suggests that we are really seeing the results of the usual blundering, infighting and incompetence of bloated government departments. Indeed, my spies inform me that there was a terrific row between the NATO signals agencies in the mid 1980's over whether GSM encryption should be strong or not. The Germans said it should be, as they shared a long border with the Evil Empire; but the other countries didn't feel this way, and the algorithm as now fielded is a French design. A5 is a stream cipher, and the keystream is the xor of three clock controlled registers. The clock control of each register is that register's own middle bit, xor'ed with a threshold function of the middle bits of all three registers (ie if two or more of the middle bits are 1, then invert each of these bits; otherwise just use them as they are). The register lengths are 19, 22 and 23, and all the feedback polynomials are sparse. Readers will note that there is a trivial 2^40 attack (guess the contents of registers 1 and 2, work out register 3 from the keystream, and then step on to check whether the guess was right). 2^40 trial encryptions could take weeks on a workstation, but the low gate count of the algorithm means that a Xilinx chip can easily be programmed to do keysearch, and an A5 cracker might have a few dozen of these running at maybe 2 keys per microsecond each. Of course, if all you want to do is break the Royal Family's keys for sale to News International, then software would do fine. It is thus clear that A5 should be free of all export controls, just like CDMF and the 40-bit versions of RC2 and RC4. Indeed, there seems to be an even faster attack. As the clock control is stop-go rather than 1-2, one would expect some kind of correlation attack to be possible, and on June 3rd, Dr Simon Shepherd of Bradford University was due to present an attack on A5 to an IEE colloquium in London. However, his talk was spiked at the last minute by GCHQ, and all we know about his attack is: (a) that sparse matrix techniques are used to reconstruct the initial state (this was published as a `trailer' in the April 93 `Mobile Europe'); (b) that he used some of the tricks from my paper `Solving a class of stream ciphers' (Cryptologia XIV no 3 [July 90] pp 285 - 288) and from the follow-up paper `Divide and conquer attacks on certain classes of stream ciphers' by Ed Dawson and Andy Clark (Cryptologia XVIII no 1 [Jan 94] pp 25 - 40) (he mentioned this to me on the phone). I believe that we have to stand up for academic freedom, and I hope that placing A5 in the public domain will lead to the embargo on Simon's paper being lifted. Ross Anderson APPENDIX - AN IMPLEMENTATION OF A5 The documentation we have, which arrived anonymously in two brown envelopes, is incomplete; we do not know the feedback taps of registers 2 and 3, but we do know from the chip's gate count that they have at most 6 feedback taps between them. The following implementation of A5 is due to Mike Roe, and all comments and queries should be sent to him. /* * In writing this program, I've had to guess a few pices of information: * * 1. Which bits of the key are loaded into which bits of the shift register * 2. Which order the frame sequence number is shifted into the SR (MSB * first or LSB first) * 3. The position of the feedback taps on R2 and R3 (R1 is known). * 4. The position of the clock control taps. These are on the `middle' one, * I've assumed to be 9 on R1, 11 on R2, 11 on R3. */ /* * Look at the `middle' stage of each of the 3 shift registers. * Either 0, 1, 2 or 3 of these 3 taps will be set high. * If 0 or 1 or one of them are high, return true. This will cause each of * the middle taps to be inverted before being used as a clock control. In * all cases either 2 or 3 of the clock enable lines will be active. Thus, * at least two shift registers change on every clock-tick and the system * never becomes stuck. */ static int threshold(r1, r2, r3) unsigned int r1; unsigned int r2; unsigned int r3; { int total; total = (((r1 >> 9) & 0x1) == 1) + (((r2 >> 11) & 0x1) == 1) + (((r3 >> 11) & 0x1) == 1); if (total > 1) return (0); else return (1); } unsigned long clock_r1(ctl, r1) int ctl; unsigned long r1; { unsigned long feedback; /* * Primitive polynomial x**19 + x**5 + x**2 + x + 1 */ ctl ^= ((r1 >> 9) & 0x1); if (ctl) { feedback = (r1 >> 18) ^ (r1 >> 17) ^ (r1 >> 16) ^ (r1 >> 13); r1 = (r1 << 1) & 0x7ffff; if (feedback & 0x01) r1 ^= 0x01; } return (r1); } unsigned long clock_r2(ctl, r2) int ctl; unsigned long r2; { unsigned long feedback; /* * Primitive polynomial x**22 + x**9 + x**5 + x + 1 */ ctl ^= ((r2 >> 11) & 0x1); if (ctl) { feedback = (r2 >> 21) ^ (r2 >> 20) ^ (r2 >> 16) ^ (r2 >> 12); r2 = (r2 << 1) & 0x3fffff; if (feedback & 0x01) r2 ^= 0x01; } return (r2); } unsigned long clock_r3(ctl, r3) int ctl; unsigned long r3; { unsigned long feedback; /* * Primitive polynomial x**23 + x**5 + x**4 + x + 1 */ ctl ^= ((r3 >> 11) & 0x1); if (ctl) { feedback = (r3 >> 22) ^ (r3 >> 21) ^ (r3 >> 18) ^ (r3 >> 17); r3 = (r3 << 1) & 0x7fffff; if (feedback & 0x01) r3 ^= 0x01; } return (r3); } int keystream(key, frame, alice, bob) unsigned char *key; /* 64 bit session key */ unsigned long frame; /* 22 bit frame sequence number */ unsigned char *alice; /* 114 bit Alice to Bob key stream */ unsigned char *bob; /* 114 bit Bob to Alice key stream */ { unsigned long r1; /* 19 bit shift register */ unsigned long r2; /* 22 bit shift register */ unsigned long r3; /* 23 bit shift register */ int i; /* counter for loops */ int clock_ctl; /* xored with clock enable on each shift register */ unsigned char *ptr; /* current position in keystream */ unsigned char byte; /* byte of keystream being assembled */ unsigned int bits; /* number of bits of keystream in byte */ unsigned int bit; /* bit output from keystream generator */ /* Initialise shift registers from session key */ r1 = (key[0] | (key[1] << 8) | (key[2] << 16) ) & 0x7ffff; r2 = ((key[2] >> 3) | (key[3] << 5) | (key[4] << 13) | (key[5] << 21)) & 0x3fffff; r3 = ((key[5] >> 1) | (key[6] << 7) | (key[7] << 15) ) & 0x7fffff; /* Merge frame sequence number into shift register state, by xor'ing it * into the feedback path */ for (i=0;i<22;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock_r1(clock_ctl, r1); r2 = clock_r2(clock_ctl, r2); r3 = clock_r3(clock_ctl, r3); if (frame & 1) { r1 ^= 1; r2 ^= 1; r3 ^= 1; } frame = frame '>> 1; } /* Run shift registers for 100 clock ticks to allow frame number to * be diffused into all the bits of the shift registers */ for (i=0;i<100;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock_r1(clock_ctl, r1); r2 = clock_r2(clock_ctl, r2); r3 = clock_r3(clock_ctl, r3); } /* Produce 114 bits of Alice->Bob key stream */ ptr = alice; bits = 0; byte = 0; for (i=0;i<114;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock_r1(clock_ctl, r1); r2 = clock_r2(clock_ctl, r2); r3 = clock_r3(clock_ctl, r3); bit = ((r1 >> 18) ^ (r2 >> 21) ^ (r3 >> 22)) & 0x01; byte = (byte << 1) | bit; bits++; if (bits == 8) { *ptr = byte; ptr++; bits = 0; byte = 0; } } if (bits) *ptr = byte; /* Run shift registers for another 100 bits to hide relationship between * Alice->Bob key stream and Bob->Alice key stream. */ for (i=0;i<100;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock_r1(clock_ctl, r1); r2 = clock_r2(clock_ctl, r2); r3 = clock_r3(clock_ctl, r3); } /* Produce 114 bits of Bob->Alice key stream */ ptr = bob; bits = 0; byte = 0; for (i=0;i<114;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock_r1(clock_ctl, r1); r2 = clock_r2(clock_ctl, r2); r3 = clock_r3(clock_ctl, r3); bit = ((r1 >> 18) ^ (r2 >> 21) ^ (r3 >> 22)) & 0x01; byte = (byte << 1) | bit; bits++; if (bits == 8) { *ptr = byte; ptr++; bits = 0; byte = 0; } } if (bits) *ptr = byte; return (0); }

16.5 A5 A5 is the stream cipher used to encrypt GSM (Group Special Mobile). That's the non-American standard for digital cellular mobile telephones. It is used to encrypt the link from the telephone to the base station. The rest of the link is unencrypted; the telephone company can easily eavesdrop on your conversations. A lot of strange politics surrounds this one. Originally it was thought that GSM's cryptography would prohibit export of the phones to some countries. Now some officials are discussing whether A5 might harm export sales, implying that it is so weak as to be an embarrassment. Rumor has it that the various NATO intelligence agencies had a catfight in the mid-1980s over whether GSM encryp- tion should be strong or weak. The Germans wanted strong cryptography, as they were sitting near the Soviet Union. The other countries overruled them, and A5 is a French design. We know most of the details. A British telephone company gave all the docu- mentation to Bradford University without remembering to get them to sign a nondisclosure agreement. It leaked here and there, and was eventually posted to the Internet. A paper describing A5 is [1622]; there is also code at the back of this book. A5 consists of three LFSRs; the register lengths are 19, 22, and 23; all the feedback polynomials are sparse. The output is the XOR of the three LFSRs. A5 uses variable clock control. Each register is clocked based on its own middle bit, XORed with the invcrse threshold function of the middle bits of all three registers. Usually, two of the LFSRs clock in each round. There is a trivial attack requiring 2^{40}encryptions: Guess the contents of the first two LFSRs, then try to determine the third LFSR from the keystream. Whether this attack is actually feasible is under debate, but a hardware key search machine cur- rently under design should resolve the matter soon [45].) Nonetheless, it is becoming clear that the basic ideas behind A5 are good. It is very efficient. It passes all known statistical tests; its only known weakness is that its registers are short enough to make exhaustive search feasible. Variants of A5 with longer shift registers and denser feedback polynomials should be secure.[Add errata from: http://www.counterpane.com/ac2errv20.html]Page 389: Some more details on the GSM algorithms. A3 is the authentication algorithm in the smart card. A8 is just a bit shuffling process that takes part of the output of A3 and turns it into a session key for A5. A5 is the privacy algorithm. There are two algorithms used in GSM: A5/1 and A5/2. A5/1 can be used by only certain countries; A5/2 can be used by all countries. ---------- 45. R.J. Anderson, "On Fibonacci Keystream Generators,"K.U. Leuven Workshop onCryptographic Algorithms, Springer-Verlag, 1995, to appear. 1622. S.B. Xu, D.K. He, and X.M. Wang, "An Implementation of the GSM General Data Encryption Algorithm A5,"CHINACRYPT'94, Xidian, China, 11-15 Nov 1994, pp. 287-291. [In Chinese.] ----------[pp. 662-667]A5 typedef struct { unsigned long rl,r2,r3; } a5 ctx; static int threshold(rl, r2, r3) unsigned int rl; unsigned int r2. unsigned int r { int total; total = (((r1 >> 9) & 0x1) == 1) + (((r2 >> 11) & 0x1) == 1) + (((r3 >> 11) & 0x1) == 1); if (total > 1) return (0); else return (1): } unsigned long clock_r1(ctl, r1) int ctl unsigned lonq r1: { unsigned long feedback; ctl ^= ((rl >> 9) & Oxl); if (ctl) { feedback = (r1 >> 18) ^ (r1 >> 17) ^ (r1 >> 16) ^ (r1 >> 13); r1 = (r1 << 1) & Ox7ffff; if (feedback & 0x01) r1 ^= 0x01: } return (r1); } unsigned long clock_r2(ctl, r2) int ctl; unsigned long r2; { unsigned long feedback; ctl ^= ((r2 >> 11) & 0x1); if (ctl) { feedback = (r2 >> 21) ^ (r2 >> 20) ^ (r2 >> 16) ^ (r2 >> 12); r2 = (r2 << 1) & 0x3fffff; if (feedback & 0x01) r2 ^= 0x01; } return (r2): } unsigned long clock_r3(ctl, r3) int ctl unsigned long r3; { unsigned long feedback; ctl ^= ((r3 >> 11) & 0x1, if (ctl) { feedback = (r3 >> 22) ^ (r3 >> 21) ^ (r3 >> 18) ^ (r3 >> 17); r3 = (r3 << 1) & 0x7fffff; if (feedback & 0x01) r3 ^= 0x01: } return (r3); } int keystream(key, frame, alice, bob) unsigned char *key; /* 64 bit session key */ unsigned long frame; /* 22 bit frame sequence number */ unsigned char *alice; /* 114 bit Alice to Bob key stream */ unsigned char *bob; /* 114 bit Bob to Alice key stream */ { unsigned long rl; /* 19 bit shift register */ unsigned long r2; /* 22 bit shift register */ unsigned long r3; /* 23 bit shift register */ int i; /* counter for loops */ int clock_ctl; /* xored with clock enable on each shift register unsigned char *ptr; /* current position in keystream */ unsigned char byte; /* byte of keystream being assembled */ unsigned int bits; /* number of bits of keystream in byte */ unsigned int bit; /* bit output from keystream generator */ /* Initialise shift registers from session key */ r1 = (key[0] I (key[1] << 8) 1 (key[2] << 16) ) & 0x7ffff; r2 = ((key[2] >> 3) 1 (key[3] << 5) 1 (key[4] << 13) 1 (key[5] << 21)) & 0x3fffff; r3 = ((key[5] >> 1) 1 (key[6] << 7) 1 (key[7] << 15) ) & 0x7fffff; /* Merge frame sequence number into shift register state, by xor'ing it * into the feedback path */ for (i=0;i<22;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock r1(clock_ctl, r1); r2 = clock_r2(clock_ctl, r2); r3 = clock_r3(clock_ctl, r3); if (frame & 1) { r1 ^= 1; r2 ^= 1; r3 ^= 1; frame = frame >> 1; } /* Run shift registers for 100 clock ticks to allow frame number to * be diffused into all the bits of the shift registers */ for (i=0;i<100;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock r1(clock_ctl, r1); r2 = clock_r2(clock ctl, r2); r3 = clock r3(clock_ctl, r3); } /* Produce 114 bits of Alice->Bob key stream */ ptr = alice; bits = 0; byte = 0; for (i=0;i<114;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock rl(clock_ctl, r1); r2 = clock_r2(clock ctl, r2); r3 = clock_r3(clock_ctl, r3); bit = ((rl >> 18) ^ (r2 >> 21) ^ (r3 >> 22)) & 0x01; byte = (byte << 1) | bit; bits++; if (bits == 8) { *ptr = byte; ptr++; bits = 0; byte = 0; } } if (bits) *ptr = byte; /* Run shift registers for another 100 bits to hide relationship between * Alice->Bob key stream and Bob->Alice key stream. for (i=0;i<100;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock_r1(clock_ctl, r1); r2 = clock r2(clock_ctl, r2); r3 = clock r3(clock ctl, r3); } /* Produce 114 bits of Bob->Alice key stream ptr = bob; bits = 0: byte = 0; for (i=U;i<114;i++) { clock_ctl = threshold(r1, r2, r2); r1 = clock r1(clock_ctl, r1); r2 = clock_r2(clock ctl, r2); r3 = clock_r3(clock ctl, r3); bit = ((r1 >> 18) ^ (r2 >> 21) ^ (r3 >> 22)) & 0x01; byte = (byte << 1) | bit; bits++; if (bits == 8) { *ptr = byte; ptr++ bits = 0; byte = 0; } } if (bits) *ptr = byte; return (0); } void a5_key(a5_ctx *c, char *k)( c->rl = k[0]<<11|k[1]<<3 | k[2]>>5 ; /* 19 */ c->r2 = k[2]<<17|k[3]<<9 | k[4]<<1 I k[5]>>7; /* 22 */ c->r3 = k[5]<<15|k[6]<<8 | k[7] ; /* 23 */ } /* Step one bit in A5, return 0 or 1 as output bit. */ int a5_step(a5 ctx *c){ int control; control = threshold(c->r1,c->r2,c->r3); c->r1 = clock_r1(control,c->r1); c->r2 = clock_r2(control,c->r2); c->r3 = clock_r3(control,c->r3); return( (c->r1^c >r2^c->r3)&1); } /* Encrypts a buffer of len bytes. */ void a5_encrypt(a5_ctx *c, char *data, int len)l int i,j; char t; for(i=0:i<len i++) for(j=0;j<8;j++) t = t<<1 | a5_step(c) data[i]^=t; } } void a5_decrypt(a5_ctx *c, char *data, int len){ a5_encrypt(c,data,len); } void main(void){ a5_ctx c; char data[100]; char key[] = {1,2,3,4,5,6,7,8}; int i,flag; for(i=0;i<100;i++) data[i] = i; a5_key(&c,key); a5_encrypt(&c,data,100); a5_key(&c,key); a5_decrypt(&c,data,1); a5_decrypt(&c,data+1,99); flag = 0; for(i=0;i<100;i++) if(data[i]!=i)flag = 1; if(flag)printf("Decrypt failed\n"); else printf("Decrypt succeeded\n"); }

To: ukcrypto@maillist.ox.ac.uk Subject: Re: More on A5 strength Date: Wed, 22 Apr 1998 11:45:37 +0100 From: Ross Anderson <Ross.Anderson@cl.cam.ac.uk> > According to Applied Crypto section 16.5, > # There is a trivial attack requiring 2^40 encryptions... > > Is that Ross Anderson - if so, how did this work out? The trivial divide-and-conquer attack, of guessing two of the shift registers and then working out the third, actually takes 2^45 effort as you have to guess about half of the bits in the third register between the LSB and the clock bit. Golic showed how to reduce the effort to 2^40 by solving linear equations and stuff like that. If the ten lowest bits in one of the registers are set to zero then of course the trivial attack will work with effort 2^35: I haven't looked at the Golic attack again in detail but I wouldn't be surprised if the overall effort were now 2^30 Ross

From: Paul Leyland <pleyland@microsoft.com> To: "'ukcrypto@maillist.ox.ac.uk'" <ukcrypto@maillist.ox.ac.uk> Subject: RE: More on A5 strength Date: Wed, 22 Apr 1998 06:12:42 -0700 The "A5" implementation posted by Ross wasn't necessarily *the* A5 algorithm, if I remember correctly. Some assumptions had to be made as to where the LFSR taps were made and what the term "middle bit" means for the 22-bit shift register. Has anyone revealed the true A5 algorithm? Paul

Date: Thu, 23 Apr 98 15:47 +0200 From: ulf@fitug.de (Ulf Möller) To: ukcrypto@maillist.ox.ac.uk Subject: Re: More on A5 strength Julian Assange <proff@iq.org> wrote: >I haven't read Ross's [45] - I doubt it is about A5 per se, but rather >about chaining of multiple LFSR's (A5 uses three), (Ross, please >correct me) - and Bruce (or someone else) has seen that Ross's attack >applies to A5. Note that there are several versions of A5, some >telco's have phones which use A5/7 - these latter versions tend to be >even weaker than A5/2! It's worth noting that AP 16.5, to my knowledge >is talking about the proposed (untested) reconstruction of A5, and not >a confirmed implementation. The excerpt of the leaked GSM Security Study at http://jya.com/gsm061088.htm contains an incomplete description of "The French Proposal for the Cipher" A5. The cipher consists of three feedback shift registers; the output stream is the XOR of the MSB of all three registers. The 19 bit register R1 is given in figure 1 the LSB after the shift is the XOR of bits 19, 18, 17 and 14). The other registers are known to be 22 and 23 bits large, and their feedback functions to consist of only four XORs all together. Clock control is based on the registers' middle bits (they do not say exactly which bit in a 22 bit register is "middle"). Each register is clocked based on its middle bit, inverted if less than two bits are set. So at least two registers are clocked in each step. They mention how the keys are loaded, but the order of the bits is not given. So it seems to me that Ross used the same leaked document from which COMP128 has been reconstructed. In his paper "On Fibonacci Keystream Generators", Ross states that the best known attack on A5 consists of guessing the state of R1 and R2 and work out R3 from the keystream. He writes, "There has been controversy about the work factor involved in each trial, and at least one telecom engineer has argued that this is about 2^12 operations giving a real attack complexity on A5 of 2^52 rather than the 2^40 which one might naively expect." This known-plaintext attack does not depend on how the keys are loaded to the registers. To execute the attack, you need to know the feedback polynomials and the position of the "middle" bits, but the feasibility of the attack clearly does not depend on a particular choice of these (still unknown) parameters. So if the French A5 is in use, it can be broken in 2^52 decryptions. Assume we have guessed the 40 bits of R1 and R2, and want to find R3, given the output keystream (that is ciphertext XOR the known plaintext). We get the MSB of R3 from knowing the MSB of R1 and R2 and the output bit, because the output stream is the XOR of the three MSBs. So if we can cycle the registers through and get all the 23 bits of R3, we have determined the initial state of R3 and can do test decryptions to see if the guess of R1 and R2 was right in the first place. (Note that this works for any feedback polynomial.) However, not all registers are clocked in every step. Not knowing the middle bit of R3, in half the cases we don't know if R3 will be clocked, in the other half we don't know whether R1 or R2 will be clocked. But if we guess the middle bit correctly, we know which registers are clocked. Thus the MSBs of R1 and R2 in the next step are known and we can determine the content of the MSB of R3 from the output bit. Then, we guess the new middle bit, which determines the following step and again yields the MSB (bit 22 of the inital configuration). If we repeat this until we have the complete R3, guessing 11 bits gets us another 11 bits for free. (Does anyone see a shortcut there?) What this means for the security of GSM depends on the GSM protocol. How much known plaintext does it provide? Are the frame sequence numbers that are mixed into registers known to evesdroppers (otherwise they'd have to try ~2^52 decryptions on every frame)? If the frame sequence numbers are known, the reduced keyspace might also help to break the encryption. Assuming the 10 zero-bits end up in R1, you guess the remaining 9 bits and fast-forward the register according to the random distribution that is given by the position in the stream you are trying to break (in each step R1 is clocked with probability 3/4). Then guess R2 and half of R3 as above.

To: ukcrypto@maillist.ox.ac.uk Subject: Re: More on A5 strength Date: Fri, 24 Apr 1998 12:31:55 +0100 From: Ross Anderson <Ross.Anderson@cl.cam.ac.uk> > Does anyone see a shortcut there? Last time I looked at it carefully I concluded that you only need to guess the clock inout bit half the time, so you need about 5 bit guesses giving an overall complexity of 2^45. I could be wrong though - it's notorious that you only get the real complexity of an attack when you implement and test it. Jovan Golic showed that you can get a 2^40 attack with a little more work, and you can work back from a reconstructed state to get Kc. This paper is worth studying; it's in the proceedings of Eurocrypt 97 (LNCS v 1233) pp 239-255 and entitled `Cryptanalysis of Alleged A5 Stream Cipher' Ross

Date: Fri, 24 Apr 1998 08:00:52 -0600 From: bill payne <billp@nmol.com> To: jy@jya.com Subject: SHIFT REGISTER technology Friday 4/24/98 7:33 AM The stuff on linear and non-linear shift register sequences which is now appearing on jya.com is the ‘military-grade’ crypto technology. Semionoff and http://www.jya.com/crack-a5.htm contains material similar to what I saw Brian Snow present in schematics of NSA KG units. The statement by david.loos@eudoramail.com The A5 algorithm uses a three level, non-linear feedback shift register arrangement, designed to be sufficiently complex to resist attack. points to the technology used for military-grade crypto. The reason NSA regarded the R register, seen at http://jya.com/whpfiles.htm,[See: http://jya.com/da/whpda.htm]feedback function classified was that it contained a non-linear feedback function. I was ORDERED to build UNCLASSIFIED hardware. This is why I stuck the R register feedback function in a fast ram. This similarity between the structure of the nonlinear feedback function in the CAVE algorithm seen at http://www.semionoff.com/cellular/hacking/phreaking/ to the feedback function published in my SAND report : A11 A1 A5 AND A1 0= A9 0= AND XOR A6 A10 XOR XOR ; reveals “military-strength” technology. SHIFT REGISTERS. Words ‘shift registers’ also caused the Great American Spy Sting bust. http://caq.com/CAQ/caq63/caq63madsen.html The Cold War is over. And the crypto cat is now about fully out of the bag. Let’s hope for settlement so that we can all go on to more constructive tasks. Later bill

To: ukcrypto@maillist.ox.ac.uk Subject: Re: More on A5 strength Date: Sat, 25 Apr 1998 13:12:45 +1000 From: Greg Rose <ggr@qualcomm.com> Ross Anderson writes: >> Does anyone see a shortcut there? > >Last time I looked at it carefully I concluded that you only >need to guess the clock inout bit half the time, so you need >about 5 bit guesses giving an overall complexity of 2^45. I >could be wrong though - it's notorious that you only get the >real complexity of an attack when you implement and test it. I implemented this kind of attack about a year ago, and you're right, the complexity is about 2^44 (measured). Greg. Greg Rose INTERNET: ggr@qualcomm.com QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470 Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/ Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F

From: David Wagner <daw@cs.berkeley.edu> Subject: Algorithm ID on SIMs (fwd) To: jya@pipeline.com Date: Mon, 27 Apr 1998 08:29:04 -0700 (PDT) The following note appeared on a closed smartcard mailing list, where there's been some discussion of the GSM hacks. A translation to plain English: a GSM document suggests there are several other defined GSM authentication algorithms, in addition to the COMP128 one which we broke. (In our experience, most providers use COMP128, with some exceptions; but if there are other "standard" algorithms, one of them might become the future favorite after folks ditch COMP128.) Just thought you might be interested in posting this "teaser" about potential future targets on your site. Take care. -- Dave Forwarded message:[JYA note: ID removed at poster's request:Sure, put it on your homepage, but strip off all the headers andmy name, please. Just mention that it was posted on the scardmailing list.]Subject: Algorithm ID on SIMs To: scard@cryptsoft.com Date: Mon, 27 Apr 1998 16:31:16 +0200 (CEST) I was just browsing through en 726-3 when I saw "COMP 128" mentioned. This is in section 7.6.5 (Algorithm ID). The algorithm ID is stored in a keyfile. I don't know whether GSM has such a keyfile and if it is readable (the en 726-3 specs are not clear about this). Hmm... probably not readable, since the secret key is stored in the same file :-) The following values are defined: Algo ID AUTH PRO STAMPED KEY LOAD DSAA '1' x COMP NAT '2' x TESA-7 '4' x x x x COMP 128 '40' x Propr '7F' DSAA means DECT Standard Authentication Algorithm So perhaps the providers that do not use COMP 128 use one of the above? After all, they are off the shelf algorithms and it is very unlikely that a provider would spend a lot on its own proprietary algorithm.

Date: Tue, 28 Apr 1998 13:49:44 +0200 From: masson <interception@ii-mel.com> To: jya@pipeline.com Subject: Air-intercept IMSI to clone IMSI It's also possible to intercept IMSI when you turn on a GSM: in fact, at that moment the mobile phone transmits the identification number to the Base Station, and at this moment it's possible to numerically scan and to duplicate from a PC. Catching the IMSI isn't sufficient to be able to make calls. You also need to know the private key within the SIM. Of course, the owner of GSM knows when he has lost his SIM card, will notify the operator of the cellular phone (Bouygues...) and a phreaking will be prevented. The Bouygues Telecom operator, for example, has a counter-measure: - if the SIM card is used twice in the same time period; - last-next call incompatible with the distance The following events invoke a MSC or BSS trace: -Call set-up within MSC (OMC, MTC) -Location update (normal & periodic) -IMSI attach and detach MSCEventRecord invokingEvent servedIMSI served IMEI callingcalledNumber connectedNumber originalCallNumber Location RadioChannelTypes recordExtensions (Ericsson-F : mobile positionning center) TimedLocation LocationAreaAndCell changeTime MSCInvokingEvent moc mtc locationupdate sms-mo sms-mt imsiAttach imsiDetach DraftprETS 627 (GSM 12.08 version 4.5.0) september 1997

Date: Tue, 28 Apr 1998 05:03:35 -0400 (EDT) From: Gary Mounfield <mani@firehouse.net> To: jya@jya.com Subject: Re: [ISN] Hackers Copy Mannesmann Mobile Phone Sim Card (fwd) ---------- Forwarded message ---------- Date: Mon, 27 Apr 1998 19:00:22 -0600 (MDT) From: mea culpa <jericho@dimensional.com> To: InfoSec News <isn@sekurity.org> Subject: Re: [ISN] Hackers Copy Mannesmann Mobile Phone Sim Card From: Felix von Leitner <leitner@math.fu-berlin.de> Date: Tue, 28 Apr 1998 01:36:21 +0200 Subject: Re: [ISN] Hackers Copy Mannesmann Mobile Phone Sim Card > In order to clone a SIM card, the hackers had to have both a copy of the > original SIM card for at least 11 hours and know the PIN number. > Scientists at the University of California and the Smartcard Developers > Association in the USA already reported weaknesses in smaller mobile > telecoms networks at the beginning of April which work on the same GSM > standard as the German networks D1, D2 and E-Plus. This is of course bullshit. If they used the same standard, they would all be vulnerable. As a member of the CCC I can clarify a little here. D2 is the only German network using COMP128 right now, which is the GSM reference encryption algorithm. What we did is "simply" implement the attack outlined by Ian Goldberg et al from Berkeley. And we made the necessary software available on www.ccc.de, and there are blueprints for useful hardware. The PIN is not an issue because evil mobile dealers can sell cloned phones now. Our GSM guy says that there are only three networks that are known not to use COMP128 right now, and two of them are in Germany, obviously. For those who speak German, there is a nice round-up on http://www.ccc.de/D2Pirat/index.html and you can download the software there, too. There are pictures of the equipment there, too, that look quite cool ;) What we demonstrated was that you can get the pin from the "secure" envelope without traces and that you can use the attack from Goldberg to get the secret key from the card in about 11 hours without overclocking the card or tricks like that. The URL to Goldberg's method was already posted on ISN I believe. And we showed that the clone and the original can check into the D2 GSM network at the same time, they just can't place calls simultaneously without error messages. This all is of course still very useful to criminals who need anonymous phones. BTW: D2 put out some of the typical press blah like "no real damage", "only theoretical attack", "same problem as when you lose your card", stuff like that ;) What remains to be seen is whether the other German mobile carriers use better or just different algorithms. Felix -o- Subscribe: mail majordomo@sekurity.org with "subscribe isn". Today's ISN Sponsor: Dimensional Communications (www.dim.com)

Date: Tue, 28 Apr 1998 11:20:05 -0400 (EDT) From:[Deleted by request]To: John Young <jya@pipeline.com> Subject: Re: [ISN] Hackers Copy Mannesmann Mobile Phone Sim Card (fwd) The last post from Masson, re grabbing IMEI, raises some interesting thoughts. For several years now there have been devices available (not commonly, but available) which will effectively track a GSM cellfone. The units are about the size of a pack of cigarettes (occasionally concealed as such) and will "lock on" to a particular IMEI/IMSI. Tracking in the handheld models is much the same as other simple direction finding / tracking gear. However there are also items available which are closer to the old ETACS tracking sets, giving a map of the surrounding cellsites, and extremely accurate positioning. Very, very nice toys, and outstandingly useful. Makes this month's crypto@c2 discussions on position escrow seem a little redundant :)

Date: 26 April 1998 From: John Young <jya@pipeline.com> To: ukcrypto@maillist.ox.ac.uk,cypherpunks@toad.com Subject: GSM A5 Papers We would be grateful for assistance in obtaining copies of the following papers, particularly the first: S J Shepherd, "Cryptanalysis of the GSM A5 Cipher Algorithm", IEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141, Savoy Place, London, 3 June 1994, (COMMERCIAL-IN-CONFIDENCE). S J Shepherd, "An Approach to the Cryptanalysis of Mobile Stream Ciphers", IEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141, Savoy Place, London, 3 June 1994, (COMMERCIAL-IN-CONFIDENCE). S J Shepherd, "Public Key Stream Ciphers", IEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141, pp 10/1-10/7, Savoy Place, London, 3 June 1994. These are listed on Dr Shepherd's bio at: http://vader.brad.ac.uk/finance/SJShepherd.html ---------- Date: 26 April 1998 From: John Young <jya@pipeline.com> To: S.J.Shepherd@bradford.ac.uk Subject: Cryptanalysis Papers Dear Dr. Shepherd, May we ask your advice in obtaining copies of your papers, "Cryptanalysis of the GSM A5 Cipher Algorithm," and "An Approach to the Cryptanalysis of Mobile Stream Ciphers?" Thank you very much. Regards, John Young JYA/Urban Deadline 251 West 89th Street, Suite 6E New York, NY 10024 Tel: 212-873-8700 Fax: 212-799-4003 E-mail: jya@pipeline.com ---------- Date: 26 April 1998 From: John Young <jya@pipeline.com> To: sales@iee.org.uk Subject: Order for Publications The Institution of Electrical Engineers, PO Box 96, Michael Faraday House, Stevenage, Herts. SG1 2SD, UK Tel: +44 (0)1438 313311; Fax: +44 (0)1438 742792; E-mail: sales@iee.org.uk Please send me the following: Quantity: 1 of each S J SHEPHERD, "Cryptanalysis of the GSM A5 Cipher Algorithm", IEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141, Savoy Place, London, 3 June 1994. S J SHEPHERD, "An Approach to the Cryptanalysis of Mobile Stream Ciphers", IEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141, Savoy Place, London, 3 June 1994.[Snip balance]---------- Date: Mon, 27 Apr 1998 17:00:55 +0100 (BST) From: Simon Shepherd <sjshephe@vader.eeng.brad.ac.uk> To: jya@pipeline.com Subject: Re: Cryptanalysis Papers Dear John I regret that the two papers you mention have been classified by the spooks as UK EYES ONLY for "security reasons". They appeared only in the classified sections of the proceedings. Sorry. Simon S

To: cryptography@c2.net Subject: Re: TIME Magazine on GSM cell phone crack Date: Thu, 30 Apr 1998 11:17:09 +0200 From: Harald Hanche-Olsen <hanche@math.ntnu.no> - Phil Karn <karn@qualcomm.com>: | >> The SDA cautions that no practical over-the-air attack is known | >> yet but that one should not be ruled out. | | >Ok, so which is it? | | The latter. I am not intimately familiar with the details of GSM | over-the-air authentication, but I suspect it is indeed possible to | conduct this attack over the air. The bottleneck is apparently the | SIM card, so it wouldn't take much longer to do it over the air. But | I'll defer to the experts who actually worked on the problem. One problem with over-the-air attacks on a GSM phone suddenly occured to me: Remember that the output of COMP128 is 96 bits, 32 of which are called SRES (output of A3 algorithm) and 54 of which are called Kc (output of A8 algorithm, after 10 zero bits are appended) and 10 of which are thrown away (to make an attack on A5 easier?) Now, only SRES is transmitted over the air back to the base station. Kc, being the key used for A5 to encrypt the communication channel, is obviously not transmitted. Presumably, only getting 32 bits of the COMP128 output per round must increase the difficulty of the cracking attempt, thereby requiring more challenge-response pairs to make up for this. Does anybody in the know care to comment? - Harald

To: cryptography@c2.net From: iang@cs.berkeley.edu (Ian Goldberg) Subject: Re: TIME Magazine on GSM cell phone crack Date: 2 May 1998 20:48:25 GMT In article <19980430111709D.hanche@math.ntnu.no>, Harald Hanche-Olsen <hanche@math.ntnu.no> wrote:[Snip]>Presumably, only getting 32 bits of the COMP128 output per round must >increase the difficulty of the cracking attempt, thereby requiring >more challenge-response pairs to make up for this. Nope. In fact, we took this into account when designing the attack. It is extremely rare that the first 32 bits of the COMP128 output of two different inputs will match, but the whole output will not. - Ian