Is No, Much Gooc!

A cioser lock at the
A5 GSM Eneryption
Algorithm

(

>From sci.crypt Fri Jun l 7 17:11~49 1994
From: na14@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 effec-
tive 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 expor-
ted 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 saggests that we are
really seeing the results of the usual blundering, infighting and
incompetence of bloated government departments.

Indeed, rny spies inform me that there was a terrific row bet-
ween 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;

\

~ n1 \N
Kabelsalat ,~`
\ C~, ist gesund ÄrG\~O~/

W'~,.

but the other countries didn't feel this way, and the algoritEm 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 thresholrl 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 tbat there is a trivial 2A40 attack (guess the
contents of registers 1 and 2, work out register 3 from the key-
stream, and then step on to check whether the guess was right).
2A40 trial encryptions could take weeks on a workstation, but
the low gate count of the algorithm means that a Xiliox 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 micros-
econd 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 tbat A5 should be free of all export controls, just
like CDMF and the 40-bit versions of 1<C2 and RC4.

Indeed, there seems to be an even faster attack. As the clock con-
trol 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) tbat sparse matrix techniques are used to reconstruct the
initial state (this was published as a trniler' 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 1July 90] pp
285 - 288) and from the follow-up paper Divide and con-
quer attacks on certain classes of stream ciphers, by Ecl
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.

~=_

~ ,

Sir arheirc~ in, Inneq. und AuBcrdKn"
herLhulien blal ru lilH ern ~rtr~ di~;o aus
undnchmen Yerwuhung~i~ql~n wilhl

hrinlen~ Rtife p-us ab~rehlu~eer kauf
rnDil1niycl1er ll~'tl,ll. Min~c`Litiltr IŽ 31lht'.
d eu ts ehe StlLcls an~ehiri,~ keit, 7L`~rUL~Il -

úcit. kcinc V®,rslreicn uar krine .'iehuidt~.

~''
lo n~ch V~rbildimg-~isel~u I und 1 J.lh-
ren. `'iu;h dir Pn~bc~h lirocnn~l~g r.un, lic

;~ll`„ ;~Hr I C~lYldi! (~I8tL'iH(l~t).

I;l;~1'1Ll'l'llLi]'l;lL~dfllL„
Ie na,ch Aher ond Famil~n~amd zwisehe~
I Kiltl urd 21UO ~nrk
r~

14Dch ller~ccb vun lirlhildon'sikursen Aul-
sli~q inJcleich~hcxu3)ien~q m~li~h.

~3

/11111~1 ~ti vil'~ICiLLi úlilI.

~m

]c ruL'cl, 1~116~C~I. fill~t U'l~l ram~lLcmiart
7.wischen 3 SOI) urd li INhl ldialk l~>r.rb
hci' licomie hri~u~hrn k~ina S'lzial`'er~
~hera 1t. ~u z`Lhlell.

~ D! I ' 1

1~'l, I`li' Ah~L~h~lll'`f' urJ hl,~:l' |i
cuer. jc ~lach Eir=~' Ak P'c~mier
l;cinL Kbodigung. gutc Aller``ersorguag

Writ~re Ird~ b'l
,..."l..;.A~/.,,.~ ~pl, lFrir~n®~l~. ~a
~.~4 ~ '1~.n t ~ `~.lvI7v'~ I {.7 `'Ie~r bri ~L ~ .,rl(,

	.I~.~..IdA.	~L~ Hr~ed~ vwr~

	úunuuuunn-uu-uuu	~ie~Qten~c~leuber#~56	0ic~nten~c~leu~er#.~6	úuunu.----~--.