29 December 2009. GSM A5 Files Published on Cryptome

Date | Revision
16 December 1999 | Link to Biryukov/Shamir A5/1 Cryptanalysis Paper Link to Smartcard Org GSM Analysis: http://www.scard.org/gsm/
3 May 1998 | Link to Cryptanalysis of Alleged A5 Stream Cipher and On Random Mappings and Random Permutations Add Ian Goldberg message
30 April 1998 | Add Hanche-Olsen message
28 April 1998 | Add Wagner/COMP128/Masson/ISN/Anon messages Link to Chaos Computing Club GSM Hack Add messages on A5 cryptanalysis
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 EUROPE 4.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 to Applied Crypto section 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 1994
    From: 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); }

Applied Cryptography, Bruce Schneier, John Wiley, 2nd. Edition, 1996, p. 389.

    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 240 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 on
    Cryptographic 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 and
       my name, please. Just mention that it was posted on the scard
       mailing 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