From: rja14@cl.cam.ac.uk (Ross Anderson) 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:
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
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.
The actual source code has been moved here.
Kryptographie - Verschiedenes
Meine Homepage
UNIX-AG Homepage