Re: Idle question...

From: Ian Farquhar <ifarqhar@laurel.ocs.mq.edu.au>

	I was compiling a list of crypto algorithms the other night, trying to
	produce a library of description documents for the algorithms, and an
	interesting but idle question hit me: what ever happened to RC1, RC3,
	MD1, MD3, A1, A2, A4, A6, and A7?

	Just wondering if anyone knows...

								Ian.

Any reason why you left out A5 above? :-) ...

>From gtoal Mon Jun 20 14:35:50 1994
To: cypherpunks@toad.com
Subject: Didn't anyone note the A5 posting?
X-Phone: +44 31 662 0366
X-Fax: +44 31 662 4678
X-Organisation: An Teallach Limited
Status: RO

Didn't anyone notice that someone posted a putative source code for
the secret A5 algorithm as used in GSM phones?  (It was on sci.crypt
xposted to uk.telecom, on Friday).  Seems someone was going to give
a talk on ways of hacking the algorithm, at some university, and he
got stomped on by CGHQ.  So another guy has come out in sympathy and
posted his reconstruction of the algorithm in C as reverse engineered
from a hardware description he received in a plain brown envelope!

This is *significantly* more of a coup on the net that the NSA handbook.

Now, all I need is for you guys to explain coherently *why* it's a
good coup and what the political implications are, and I'll feed the
story to the UK press.  (I don't think anyone here has it yet...)

G

| Now, all I need is for you guys to explain coherently *why* it's a
| good coup and what the political implications are, and I'll feed the
| story to the UK press.  (I don't think anyone here has it yet...)

	It is a coup because it means that codes released to the
public do get reverse engineered.  The release of A5 bodes poorly for
Skipjack.  If the NSA wants Skipjack to remain secret, they can not
release it, in hardware or software.

	Cyphers to be used by the public will be studied and
understood.  The public no longer trusts governments to be honest.  In
the USA, this is a result of our free press printing things like the
Pentagon papers, where the government documented the fact that it lied
to us, systematically, for years.

	We do not trust the NSA, the ATF, or the DEA with our privacy.
They have repeatedly shown they will try to push the boundaries of
what is acceptable to get at people they don't like.  Just ask CISPES,
the Branch Dividians, or Rev. Aceyne (sp?) Williams widow.

Adam


(CISPES is the Committee in Solidarity with the People of El Salvador,
a left wing group working in support of the revolutionaries of El
salvador.  The FBI monitored, infiltrated, and harrassed them for 5
years with no evidence that they were breaking any law.  The Davidians
everyone knows.  Rev. Williams (age 77) was killed by Boston drug
police who burst into the wrong apartment, threw him to the floor, and
gave him a heart attack.  (In the newspapers Thanksgiving Day, 1993))

-- 
Adam Shostack 				       adam@bwh.harvard.edu

Politics.  From the greek "poly," meaning many, and ticks, a small,
annoying bloodsucker.

On Tue, 12 Jul 1994, Graham Toal wrote:
> Subject: Didn't anyone note the A5 posting?
Does anyone have a copy of this posting?

>	interesting but idle question hit me: what ever happened to RC1, RC3,
>	MD1, MD3, A1, A2, A4, A6, and A7?

>Any reason why you left out A5 above? :-) ...

I left it out simple because it is a known cipher.  All of the ciphers mentioned
above are parts of series, but I have never seen published mention of them
(eg. we know MD2, MD4 and MD5, but those very numbers imply the existance of
MD1 and MD3, which I have never seen any reference to.)  I left A3 and A8
out as well.

>This is *significantly* more of a coup on the net that the NSA handbook.

Definitely, although the algorithm description posted was not complete.
What is clear, though, is that the French-designed A5 cipher is hideously
insecure (unless there is some amazing subtlty to it's design, and I
very much doubt it).

Some implications:

1. The French - with their well-known and legislated hatred of civilian
   crypto - won the battle of the GSM crypto algorithm, and managed to
   corrupt any chance of the incorporation of decent security in this
   mobile protocol.  The French position has had wide reaching implications
   globally, which I suspect that a lot of people would not be too happy
   about.

2. That our governments lied to us about the security of the algorithm.
   I note with some disgust that Australian organisations like ASIO and the
   AFP pushed HARD for A5X over A5 on the grounds that A5 was too hard
   to break.  This position was a fabrication, that much is clear.

3. That GSM phones are NOT in any way secure.  Sure, it's better than AMPS,
   but that is not saying much.  I also wonder if the embargo on the
   release of the A5 algorithm was simply to enforce the monopoly of
   the government SIGINT operations.

Anyway, let's throw this discussion open.  Here is the algorithm description,
and don't forget that A3 and A8 probably came from the same guys, and they're
part of GSM's key exchange protocol.  If they're as good as A5, GSM is in deep,
deep trouble security-wise.

BTW, the algorithm leaked, it was not reverse engineered.  I do not expect
SKIPJACK to leak, as it's distribution would be VERY limited, even within
the NSA and chip houses.  Even A5 was reputed to be known to only 2 or 3
people within Motorola.

I do not have a description of A5X, but I have heard rumors that A5 generates
a single 114 bit key, and then continues to use it over and over again.
As all of you would realise, this would be utterly trivial to break.

						Ian.

>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
>Message-ID: <2ts9a0$95r@lyra.csx.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);

}

End of post...