Xref: comlab.ox.ac.uk sci.crypt:22777 alt.security:14519 uk.telecom:11563
Path: comlab.ox.ac.uk!uknet!lyra.csx.cam.ac.uk!rja14
From: rja14@cl.cam.ac.uk (Ross Anderson)
Newsgroups: sci.crypt,alt.security,uk.telecom
Subject: A5 (Was: HACKING DIGITAL PHONES)
Date: 17 Jun 1994 13:43:28 GMT
Organization: U of Cambridge Computer Lab, UK
Lines: 299
Message-ID: <2ts9a0$95r@lyra.csx.cam.ac.uk>
NNTP-Posting-Host: nene.cl.cam.ac.uk


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 <mrr@cl.cam.ac.uk>, 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);

}

Xref: comlab.ox.ac.uk sci.crypt:24092 alt.security.pgp:14803
Path: comlab.ox.ac.uk!uknet!EU.net!howland.reston.ans.net!usc!nic-nac.CSU.net!charnel.ecst.csuchico.edu!yeshua.marcam.com!zip.eecs.umich.edu!newsxfer.itd.umich.edu!isclient.merit.edu!msuinfo!harbinger.cc.monash.edu.au!yarrina.connect.com.au!warrane.connect.com.au!spectrum.apana.org.au!triode.apana.org.au!not-for-mail
From: cskinner@triode.apana.org.au (Christopher T Skinner)
Newsgroups: sci.crypt,alt.security.pgp
Subject: Re: mobil phone in europe <gms-standard>, a precedence?
Date: 13 Aug 1994 01:57:50 +1000
Organization: Paul Black's Linux Node
Lines: 109
Message-ID: <32g65u$mpt@triode.apana.org.au>
References: <32eot5$jvt@charm.magnus.acs.ohio-state.edu> <32fmjs$ri4@stud.uni-sb.de>
NNTP-Posting-Host: localhost.apana.org.au
X-Newsreader: TIN [version 1.2 PL2]

Mobile Phones:
Walker, M. Security in mobile and cordless telecommunications
CompEuro 1992 Proceedings. Computer Systems and Software
Engineering  p.493-6 ed Dewilde, P.; Vandewalle, J.IEEE
Comput. Soc. Press  Los Alamitos, CA, USA    1992  xviii+717 pp.  USA
4-8 May 1992 The Hague
"DECT uses Standard cipher DCS ..synchronised to the MAC layer frame
numbering. For each standard slot the input to the
PSC is the cipher key and the frame number and the output from the
algorithm is two consecutive key stream sequences
each 360 bits long...GSM is essentially the same...cipher is
re-synchronised on every frame..to enable handover "
- this looks like XOR keys are generated often enough to make the
system strong
- of course it is an algorithmic generation, not a true one-time-pad,
the algorithm must have some sort of regularity  and cycle...
Cooke, J. C.; Brewster, R. L.Cryptographic security techniques for
digital mobile telephones.
Cooke, J.C.; Brewster, R.L. Cryptographic security techniques for
digital mobile telephonesUK
1992 IEEE International Conference on Selected Topics in Wireless
Communications. Conference Proceedings
(Cat.No.92TH0462-2)p. 425-8  Eds: Bhargava, V.K.; Callendar, M.; Toms,
N.  Publisher:    IEEE New York, NY, USA : 1992  xiv+468 pp. 25-26
June 1992: Vancouver, BC, Canada :Aston Univ., Birmingham,
I assume these 2 are the same paper
  "...two types  cellular or cordless
   cellular is E.T.S.I G.S.M900
has a personal commn network variant (PCN-DCS1800) for populated,
small cell areas
cordless (Europe) are CEPT CT2 & ETSI DECT
3 modes domestic cordless, public telepoint, corl\dless PABX
Third generation under specification: merge high rate broadband (ISDN)
& PSTN
with ETSI UMTS (Universal Mobile Telecomns System) for Europe &
GSM:
AUC Authentication Centre
has subscrbers IMSI (International Mobile Subscriber Identity) and Ki
(Subscribers secret key)
Encrypted communication with ADC (Admin Centre)
algorithms depend on particular telecoms operator.....
HLR Home Location Register
secure database, current subscribar location (?)
VLR Visitor Location Register
Authentication:
  TMSI (Temporary Mobile Subscriber Identity) sent to current VLR
fromlast VLR
  new TMSI calculated & encrypted & sent to mobile
  AUC uses A3(IMSI-Ki,Rand) to give signed response SRES
      and  A8(Ki,Rand) to give traffic encryption key Kc
      so (Rand,SRES,Kc) is unique authentication set for each call
  AUC sends set to VLR
  VLR sends Rand to mobile
  mobile does same A3 & A8 calculations, sends SRES back to VLR (must
match)    message is encrypted via A5 using Kc
C ooke & Brewster point out that GSM digital cell phone security rests
on confidential algorithms (A3,A5,A8).
It is a principle of cryptography that security should rest on secrecy
of the keys, "and not of the algorithms used".
GSM does not currently use Public Key Cryptography (PKC).
They suggest that PKC should be considered. PKC could "allow the
secure exchange of cryptographic keys without there being any prior
knowledge of a commonly held key"
Currently the subscriber's secret key is held at the authentication
centre as well as in the subscribers chip.
GSM is secure against casual scanners (the Squidgy factor) but not
against insiders at the base station. Legal Authorities can presumably
access the base stations and the secret keys. Any eavesdropping
revealed to the public would publicly compromise the entire GSM
system. The current encryption algorithm (A5) is frame based, so
although it uses a simple XOR method, new keys are produced by
algorithm A8 so frequently that the system is probably secure, if A8
is a good one-way algorithm.
C & Brewster sugggest possible optional "extra features" including
PKC, complete end-to-end security, and the additional requirement of a
password during subscriber authentication.
A GSM call placed in a foreign country currently refers back to the
home country. This may be to preserve secrecy of authentication
algorithms. If two nearby GSM phones wish to connect in a foreign
country, there are two overseas charges involved, no matter how close
the phones are. New end-to-end encryption may be needed to avoid this
situation.
........
Privacy and authentication on a portable communications system.
  Author: Beller, Michael J.; Chang, Li-Fung; Yacobi, Yacov
  Conference Title: IEEE Global Telecommunications Conference -
GLOBECOM '91.Part 3 (of 3)
  Conference Location: Phoenix, AZ, USA  Conference Date: 1991 Dec 2-5
   IEEE Service Center, Piscataway, NJ, USA (IEEE cat n 91CH2980-1). p
1922-1927
  CODEN: CRIEET  ISBN: 0-87942-697-7
  They consider possible PKC for smart card- mobile use
    MSR Modular Square Root (Rabin '79,Williams '80)
    DH  Diffie Hellman 76,85,88
    IMSR Improved MSR

method   Port Authenticated  Secret given to Base    Mod Multiplies
 MSR          no                yes                  1
IMSR          yes               yes                  2
MSR+DH        yes               no                   212
Rates  8-bit microcontroller (75-150mw, 6MHz) one 512 bit modmul =
180ms
       DSP 1 ms
       (386sx < 3ms??)
       the portable may have a DSP for speech transcoding
       (cf RSA 630 modmuls, LUC = 1280 modmuls, before CRT-halfLUC)
 IF a general DSP is available in the handset, MSR+DH is OK
 (as is LUC = ca 0.5 second??)