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