crack-a5.htm
d8acc9cb709f5c4749cfbff0e5a3662f4d442daf949446bd9012d804beb3460f<HTML>
<HEAD>
<!-- Created with AOLpress/2.0 -->
<TITLE>CRACK A5</TITLE>
</HEAD>
<BODY>
<CENTER>
<TABLE BORDER CELLPADDING="6" ALIGN="Center">
<TR>
<TD>Date</TD>
<TD>Revision</TD>
</TR>
<TR VALIGN="Top">
<TD>3 May 1998</TD>
<TD>Link to <A HREF="http://jya.com/a5-hack.htm">Cryptanalysis of Alleged
A5 Stream Cipher</A> and<A HREF="http://jya.com/a5-hack.htm"><BR>
On Random Mappings and Random Permutations</A>
<P>
Add <A HREF="#ian">Ian Goldberg message</A></TD>
</TR>
<TR VALIGN="Top">
<TD>30 April 1998</TD>
<TD>Add <A HREF="#hanche">Hanche-Olsen message</A></TD>
</TR>
<TR VALIGN="Top">
<TD>28 April 1998</TD>
<TD>Add <A HREF="#daw">Wagner/COMP128/Masson/ISN/Anon messages</A>
<P>
Link to <A HREF="http://jya.com/gsm-chaos.htm">Chaos Computing Club GSM
Hack</A>
<P>
Add <A HREF="#a5c">messages on A5 cryptanalysis</A></TD>
</TR>
<TR VALIGN="Top">
<TD>25 April 1998</TD>
<TD>Add <A HREF="#whp">Payne/Rose messages</A></TD>
</TR>
<TR VALIGN="Top">
<TD>24 April 1998</TD>
<TD>Add <A HREF="#rja2">Anderson message</A></TD>
</TR>
<TR VALIGN="Top">
<TD>23 April 1998</TD>
<TD>Add <A HREF="#moller">Möller message</A></TD>
</TR>
<TR VALIGN="Top">
<TD>22 April 1998</TD>
<TD>Add <A HREF="#a5-algo">A5 implementations</A> and
<A HREF="#Anderson">Anderson/Leyland messages</A>
<P>
Link to GSM paper:
<A HREF="http://sky.fit.qut.edu.au/DataComms/Teach/units.972/itn530/ass/wkho/assign.htm">http://sky.fit.qut.edu.au/DataComms/Teach/units.972/itn530/ass/wkho/assign.htm</A></TD>
</TR>
<TR VALIGN="Top">
<TD>20 April 1998</TD>
<TD>Link to <A HREF="http://jya.com/gsm042098.txt">GSM consortium statement</A>
<P>
Add <A HREF="#masson2">Masson and Assange messages</A>
<P>
Link to <A HREF="http://jya.com/gsm061088.htm">1988 GSM security study</A></TD>
</TR>
<TR VALIGN="Top">
<TD>19 April 1998</TD>
<TD>Add <A HREF="#mb">Briceno message</A></TD>
</TR>
</TABLE>
</CENTER>
<P ALIGN=Center>
<P ALIGN=Center>
18 April 1998
<P>
<HR>
<PRE>Date: Fri, 17 Apr 1998 16:28:05 +0200
From: Loos <david.loos@eudoramail.com>
To: jya@pipeline.com
Subject: CRACK A5
Yes, americanphreakers <A HREF="http://jya.com/gsm-cloned.htm">clone a SIM card GSM</A> (A5/A8, IMSI,...)
But, it's actually impossible to decrypt an air-interception
conversation GSM. A5/A8 is not the full key crypting a consersation GSM.
Illusion a sucessul of decyption is done:
<I>MOBILE EUROPE</I> 4.93: " Feedback from academic research by a leading
university cryptographic research group (R. Anderson,..)
in the UK is indicating that the much-vaunted GSM A5 cipher algorithm
may not be a secure as first tought .
The group has reported a 75% (!) success rate in recovery of the cipher
bit stream and anticipate that it will not be long before
a complete realtime off-air decryption is achieved (wrong!!).
The A5 algorithm uses a three level, non-linear feedback shift
register arrangement, designed to be sufficiently complex to resist
attack. However, using new Russian techniques in sparse matrix inversion,
the group have been able to determine accurately
at least three quarters of the 114 bits used for encrypting and
decrypting each message packet.
The A5 cipher has been at the root of the controversy over the export of
GSM to non-Cocom countries, and has been responsible
for severely impeding the export potential of the system.
A "watered down" version of the algorithm, codenamed "A5X ",
has been proposed for equipment destined for controlled areas,
while the original group CEPT countries responsible for the introduction
of GSM will retain the A5 (A5-1) cipher system."
interception@ii-mel.com
Masson
<HR>
Dear David Loos,
Thanks for your note.
Christian Masson has <A HREF="#cm">recently sent commentary</A> on
the impossibility of decrypting GSM air-interception to the
mail list Cypherpunks <cypherpunks@cyberpass.net>.
The three American "phreakers" subscribe to the Cypherpunks
list. You might want to post your criticisms there for discussion.
Also, on the mail list UK Crypto <ukcrypto@maillist.ox.ac.uk>
there has also been discussion of GSM, A5 and R.J. Anderson's
A5 paper. According to one writer the paper does not address
all the aspects of the recent crack (see copy of message below).
R.J. (Ross) Anderson <Ross.Anderson@cl.cam.ac.uk> subscribes
to UK Crypto and surely would like to respond to your and Masson's
critiques. Also, see Anderson's bountiful computer security Web
site at:
<A HREF="http://www.cl.cam.ac.uk/users/rja14/">http://www.cl.cam.ac.uk/users/rja14/</A>
Perhaps you'd like to discuss this more with the GSM crackers directly.
I'd suggest David Wagner <daw@cs.berkeley.edu>.
Please let me know what new information you learn from Dave or from
any others who are probing A5 and GSM.
BTW, have you seen the leaked <A HREF="http://jya.com/gsm061088.htm">Racal Research document</A> listed
at SDA site as the source of the A3A8 algorithm?
<A HREF="http://www.scard.org/gsm/a3a8.txt">http://www.scard.org/gsm/a3a8.txt</A>
This 1988 document was sent to us in early 1997. It includes not
only the German COMP128 used by the crackers but also the French
cipher proposed for GSM.
Regards,
John Young
----------
UK Crypto message:
To: ukcrypto@maillist.ox.ac.uk
Subject: Re: More on A5 strength
From: Julian Assange <proff@iq.org>
Date: 17 Apr 1998 07:31:39 +1000
David Hopwood <hopwood@zetnet.co.uk> writes:
> According to <I>Applied Crypto</I> section 16.5,
> # There is a trivial attack requiring 2^40 encryptions: Guess the
> # contents of the first two LFSRs, then try to determine the third
> # LFSR from the keystream. (Whether this attack is actually
> # feasible is under debate, but a hardware key search machine
> # currently under design should resolve the matter soon [45].)
>
> [45] is:
> # R.J.Anderson, "On Fibonacci Keystream Generators," K.U. Leuven
> # Workshop on Cryptographic Algorithms, Springer-Verlag, 1995,
> # to appear.
>
> Is that Ross Anderson - if so, how did this work out?
Ross is into everything :)
I haven't read Ross's [45] - I doubt it is about A5 per se, but rather
about chaining of multiple LFSR's (A5 uses three), (Ross, please
correct me) - and Bruce (or someone else) has seen that Ross's attack
applies to A5. Note that there are several versions of A5, some
telco's have phones which use A5/7 - these latter versions tend to be
even weaker than A5/2! It's worth noting that AP 16.5, to my knowledge
is talking about the proposed (untested) reconstruction of A5, and not
a confirmed implementation.
In Underground (<A HREF="http://www.underground-book.com/">http://www.underground-book.com/</A>), (pub. June 1997),
we presented transcripts from a Dete-Mobil (Deutche-Telekom) GSM
monitoring port, which showed that at least the last 8 bits of key were
all zero'd.
Cheers,
Julian.
<HR>
<A NAME="cm">Date: Thu, 16 Apr 1998 16:19:20 +0200</A>
From: masson <interception@ii-mel.com>
To: cypherpunks@cyberpass.net
Subject: A5-1/A8 is not the definitive key GSM!
Key A5-1/A8 GSM
Dear Sir,
The key encypts an air-consersation GSM is A5-1 or A5-2 + A8 + local hour (12:10:21)
of the network where the GSM is.
Except government, nobody could decode an air-interception of a conversation GSM.
After, the BSC, the consersation GSM is clear. Foreigner air-interception GSM are made case
by case. In Munchen , Rodhes & Schwarz sells a logger permits to catch IMSI, aso (no coded);
See http://jya.com/gsm-cloned.htm
http://www.ii-mel.com/interception/europegb.html
http://www.ii-mel.com/interception/belgiquegb.html
http://jya.com/snoop-gsm.htm
MOBILE EUROPE magazine presents under subject "crack A5?" a pseudo-sucess. To prevent
governmental leakage of private informations.
The real scandal is the MOBILE TRACE (recognize by headquarters of GSM MoU of Dublin)
tracing and storing the moving of each GSM in standbye (2X/H)! 80-100 millions MOBILE TRACE.
Thks fr yr comments + regards,
C. Masson
<HR>
<A NAME="mb">Date: Sun, 19 Apr 1998 16:01:12 +1000 (EST)</A>
From: Marc Briceno <marc@scard.org>
To: John Young <jya@pipeline.com>
cc: interception@ii-mel.com
Subject: Re: Masson
This list apparently has seen some posts about A5 lately. I don't have the
time to write a paper on this topic at the moment, so here is a list of
facts known to be true.
1. I discovered COMP128. COMP128 is widely used as the GSM authentication
algorithm (A3) and session key generating algorithm (A8).
2. The 64 bit output of A8 is used as the session key for A5 (including
all A5 variants), a 64 bit cipher
3. A8 has been _deliberately_ weakened to provide only 54 bits of entropy.
This is done by setting the last 10 bits of the A8 output to be always 0.
4. Assuming the cipher used is COMP128, the output of A3 and A8 is
determined by exactly two factors:
- The SIM's internal key Ki.
- The random challenge sent by the base station.
5. We showed how to extract Ki from a SIM in our posession. A rogue base
station could perform the same extraction of all the Ki's from all the GSM
phones within the area covered by the rogue base station.
6. The challenge can be intercepted off the air.
7. From 2. and 4. follows that an attacker that knows the challenge
(obtainable over the air) and the SIM's internal key Ki (obtainable over
the) can determine the session key used by the on-the-air voice privacy
algorithm A5.
8. Assuming the attacker knows A5, the attacker can therefore decrypt the
voice privacy features.
9. Note that given the above facts, no cryptanalysis of A5 is required to
compromise the voice privacy features of the GSM call of interest.
-- Marc Briceno <marc@scard.org>
Director, Smartcard Developer Association
<A HREF="http://www.scard.org">http://www.scard.org</A>
On Sat, 18 Apr 1998, John Young wrote:
>Date: Sat, 18 April 1998
>To: interception@ii-mel.com
>From: John Young <jya@pipeline.com>
>Subject: Masson
>cc: <marc@cryptsoft.org>
>
> Christian,
>
> We have put the "David Loos Crack A5" messages at:
>
> <A HREF="http://jya.com/crack-a5.htm">http://jya.com/crack-a5.htm</A>
>
> There seems to be disagreement about the possibility of air-intercept.
> See Marc Briceno's comments at <<A HREF="http://jya.com/gsm-cloned.htm">http://jya.com/gsm-cloned.htm</A>> .
>
> Perhaps you should write Marc <<A HREF="mailto:marc@cryptosoft.com">marc@cryptsoft.com</A>> to
> reach agreement on the facts.
>
> Let me know what you hear from the Americans or British
> about your comments on air-intercept of GSM.
>
> Regards,
>
> John Young
<HR>
<A NAME="masson2">Date: Mon, 20 Apr 1998 14:40:29 +0200</A>
From: masson <interception@ii-mel.com>
To: jya@pipeline.com
Subject: CRACK A5-1/A8
Dear John,
______________________________________________________________
Pls find and add if you wish the australian answer about A5.
Add draw "canal radio" in <A HREF="http://www.ii-mel.com/interception/europegb.html">www.ii-mel.com/interception/europegb.html</A>
Add draw humour draw for MOBILE TRACE GSM.
______________________________________________________________
SUBJECT: A5-1/A8 & air-interception GSM
A5 use A8 but also a pseudo-aleatory number, the local hour of the GSM
network.
This apsect is not approached by Ross Anderson or Marc Briceno. A public
success in cracking an air-interception GSM is a bluff!
After you crack A5 (actually, only a government is able to crack A5
and rebuilt GSM voice): to understand the voice (8 X 26 bits per
4,6ms), you must rebuild and stick millions and millions of TELECOM bursts.
Min. 4 days of work is required for 2mm of communication GSM (CRAY
T3E,...) by an governmental interception.
interception@ii-mel.com
----------
From - Mon Apr 20 13:54:38 1998
To: interception@ii-mel.com
Subject: Re: CLONE SIM CARD GSM
From: Julian Assange <proff@iq.org>
Date: 19 Apr 1998 08:31:28 +1000
masson <interception@ii-mel.com> writes:
'alo masson.
> Ross Anderson lies by omission. (he breaks at 75%: in clear 0%).
Err, what do you mean exactly?
> The clone of SIM CARD GSM is not a decryption of the encryption key of GSM
> conversations (by air) and eachtime different and dont stay on SIM card.
Yes. Although I'm not sure that you couldn't get the GSM to do 100k
authentications by over-powering a MSC signal asking for authentication, and
thus calculate Ki.
Speaking of which, some investigative services are now using fake
MSC's (i.e mim's) to monitor call traffic.
Cheers,
Julian.
<HR>
<A NAME="a5-algo">Subject: RISKS DIGEST 14.60</A>
REPLY-TO: risks@csl.sri.com
RISKS-LIST: RISKS-FORUM Digest Wednesday 12 May 1993 Volume 14 : Issue 60
FORUM ON RISKS TO THE PUBLIC IN COMPUTERS AND RELATED SYSTEMS
ACM Committee on Computers and Public Policy, Peter G. Neumann, moderator
[Snip]
------------------------------
Date: Mon, 3 May 1993 19:27:33 +0200
From: brunnstein@rz.informatik.uni-hamburg.dbp.de
Subject: Mobile ComSec in Europe (A5)
Stimulated by the "Cripple Clipper" Chip discussions, I invested some time to
investigate the European approach in this area. Mobile communication security
is practically available, since some time, in Western Europe based on some
technology which will now alsp be applied in Australia [see Roger Clarke: Risk
Forum 14.56). In contacts with people from producers, carriers and Telecom
research, I collected the following facts:
- Dominated by Western European telecommunications enterprises, a
CCITT subsidiary (CEPT=Conference Europeenne des Administrations des
Postes et des Telecommunications; founded 1959, presently 26 European
countries, mainly from Western/Northern Europe) formed a subgroup
(ETSI=European Telecommunications Standards Institute) which specified,
in a special Memorandum of Understanding (MoU) the GSM standard (=Groupe
Special Mobile). Presently, ETSI (planned as EEC's Standardisation
Institute in this area) has 250 members from industry (63%), carrier
(14%), government (10%), appliers and research (together 10%). Research
here means essentially Telecom and related "research" institutes.
- GSM documents specify roughly the functional characteristics including
secure encryption of transmitted digital messages (see "European digital
cellular telecommunication system (phase 2): Security Related Network
Functions"). Apart from protocols, details of algorithms are secret.
- GSM contains 3 secret algorithms (only given to experts with established
need-to-know, esp. carriers or manufacturers):
Algorithm A3: Authentication algorithm,
Algorithm A8: Cipher Key Generator (essentially a 1-way function),
and
Algorithm A5: Ciphering/Deciphering algorithm (presently A5/1,A5/2).
Used in proper sequence, this set of algorithms shall guarantee that
NOBODY can break the encrypted communication.
- Mobile stations are equipped with a chipcard containing A3 and A8, plus
an ASIC containing A5; the (non-mobile) base stations (from where the
communication flows into the land-based lines) is equipped with an ASIC
realising A5 encryption, and it is connected with an "authentication
center" using (ASIC, potentially software based) A3 and A8 algorithms to
authenticate the mobile participant and generate a session key.
- When a secure communication is started (with the chipcard inserted in
the mobile station), authentication of the mobile participant is
performed by encrypting the individual subscriber key Ki (and some
random seed exchanged between the mobile and base station) with A3 and
sending this to the base station where it is checked against the stored
identity. Length of Ki: 128 bit.
- If authenticated, the individual subscriber key Ki (plus some random
seed exchanged between mobile and basis station) is used to generate a
session key Kc; length of Kc: 64 bit. Different from Clipper, a session
key may be used for more than one session, dependent on the setting of
a flag at generation time; evidently, this feature allows to minimize
communication delays from the authentication process.
- Using session key (Kc), the data stream (e.g. digitized voice) is en-
crypted using the A5 algorithm and properly decrypted at base station.
- A more complex authentication procedure including exchange of IMSI
(International Mobile Subscriber Identity) may be used to authenticate
the subscriber and at the same time to generate the session key (using
a combined "A38" algorithm) and transmit it back to the mobile station.
Comparing the European A5 approach with US' "Cripple Clipper Chip", I find
some surprising basic similarities (apart from minor technical differences,
such as key lengths and using ASICs only versus Chipcard in the mobile
station):
1) Both approaches apply the "SbO Principle" (Security by Obscurity): "what
outsiders don't know, is secure!" Or formulated differently: only
insiders can know whether it contains built-in trapdoors or whether it
is really secure!
2) Both approaches aim at protecting their hemisphere (in the European
case, including some interest spheres such as "down-under", to serve
the distinguished British taste:-) from other hemispheres' competition.
The most significant differences are:
A) that US government tries to masquerade the economic arguments with some
legalistic phrases ("protect citizen's privacy AND protect them against
criminal misuse") whereas Western Europeans must not argue as everybody
knows the dominance of EEC's economic arguments (and the sad situation
of privacy in most EEC countries :-)
B) that US government must produce the rather complex "escrow agencies"
where European law enforcers must only deal with ETSI (manufacturers and
carriers!) about reduced safety in "A5/n" algorithms (n=1,2,...).
Presently, different "A5/n" algorithms are discussed. Apart from the "secure"
original algorithm A5 (now labeled A5/1), a "less secure, export oriented
A5/2" has been specified (according to my source which may not be fully
informed, this will go to "down-under" :-). One argument for such "A5/n"
multiplicity is that availability of more A5/n algorithms may even allow to
select, during authentication, one algorithm from the set thus improving
security of communication; at the same time, as these algorithms are secret,
the secret automatic selection (e.g. triggered by some obscure function
similar to the random exchange in the authentication process) may allow to
crack the encrypted message.
My (contemporary) conclusion is that security of both A5 and CC is
questionable as long as their security cannot be assessed by independent
experts. In both cases, economic interests seem to play a dominant role; there
are clear indications of forthcoming economic "competition", and I wonder
which side Japan will take (maybe they decide to start their own crippled
SecureCom standard?)
Klaus Brunnstein (Univ Hamburg; May 3, 1993)
------------------------------
<HR>
<A NAME="rja">From sci.crypt Fri Jun 17 17:11:49 1994</A>
<PRE>From: rja14@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 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 <A HREF="mailto:mrr@cl.cam.ac.uk">Mike Roe</A>, 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); } </PRE>
</PRE><HR>
<I><A HREF="http://www.counterpane.com">Applied Cryptography</A></I>, Bruce Schneier, John Wiley, 2nd. Edition, 1996, p. 389.
<PRE>16.5 A5
A5 is the stream cipher used to encrypt GSM (Group Special Mobile). That's the
non-American standard for digital cellular mobile telephones. It is used to encrypt
the link from the telephone to the base station. The rest of the link is unencrypted;
the telephone company can easily eavesdrop on your conversations.
A lot of strange politics surrounds this one. Originally it was thought that
GSM's cryptography would prohibit export of the phones to some countries. Now
some officials are discussing whether A5 might harm export sales, implying that
it is so weak as to be an embarrassment. Rumor has it that the various NATO
intelligence agencies had a catfight in the mid-1980s over whether GSM encryp-
tion should be strong or weak. The Germans wanted strong cryptography, as they
were sitting near the Soviet Union. The other countries overruled them, and A5 is
a French design.
We know most of the details. A British telephone company gave all the docu-
mentation to Bradford University without remembering to get them to sign a
nondisclosure agreement. It leaked here and there, and was eventually posted to the
Internet. A paper describing A5 is [<A HREF="#1622">1622</A>]; there is also <A HREF="#code">code</A> at the back of this book.
A5 consists of three LFSRs; the register lengths are 19, 22, and 23; all the feedback
polynomials are sparse. The output is the XOR of the three LFSRs. A5 uses variable
clock control. Each register is clocked based on its own middle bit, XORed with the
invcrse threshold function of the middle bits of all three registers. Usually, two of
the LFSRs clock in each round.
There is a trivial attack requiring 2<SUP>40</SUP> encryptions: Guess the contents of the first
two LFSRs, then try to determine the third LFSR from the keystream. Whether this
attack is actually feasible is under debate, but a hardware key search machine cur-
rently under design should resolve the matter soon [<A HREF="#45">45</A>].)
Nonetheless, it is becoming clear that the basic ideas behind A5 are good. It is
very efficient. It passes all known statistical tests; its only known weakness is that
its registers are short enough to make exhaustive search feasible. Variants of A5
with longer shift registers and denser feedback polynomials should be secure.
<I>[Add errata from: <A HREF="http://www.counterpane.com/ac2errv20.html">http://www.counterpane.com/ac2errv20.html</A>]</I>
Page 389: Some more details on the GSM algorithms. A3 is the authentication algorithm
in the smart card. A8 is just a bit shuffling process that takes part of the output of
A3 and turns it into a session key for A5. A5 is the privacy algorithm. There are two
algorithms used in GSM: A5/1 and A5/2. A5/1 can be used by only certain countries;
A5/2 can be used by all countries.
----------
<A NAME="45">45</A>. R.J. Anderson, "<A HREF="http://www.cl.cam.ac.uk/ftp/users/rja14/fibonacci.ps.Z">On Fibonacci Keystream Generators</A>," <I>K.U. Leuven Workshop on</I>
<I>Cryptographic Algorithms</I>, Springer-Verlag, 1995, to appear.
<A NAME="1622">1622</A>. S.B. Xu, D.K. He, and X.M. Wang, "An Implementation of the GSM General Data
Encryption Algorithm A5," <I>CHINACRYPT'94</I>, Xidian, China, 11-15 Nov 1994, pp. 287-291.
[In Chinese.]
----------
<I>[pp. 662-667]</I>
<A NAME="code">A5</A>
typedef struct {
unsigned long rl,r2,r3;
} a5 ctx;
static int threshold(rl, r2, r3)
unsigned int rl;
unsigned int r2.
unsigned int r
{
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 lonq r1:
{
unsigned long feedback;
ctl ^= ((rl >> 9) & Oxl);
if (ctl)
{
feedback = (r1 >> 18) ^ (r1 >> 17) ^ (r1 >> 16) ^ (r1 >> 13);
r1 = (r1 << 1) & Ox7ffff;
if (feedback & 0x01)
r1 ^= 0x01:
}
return (r1);
}
unsigned long clock_r2(ctl, r2)
int ctl;
unsigned long r2;
{
unsigned long feedback;
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;
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 rl; /* 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] I (key[1] << 8) 1 (key[2] << 16) ) & 0x7ffff;
r2 = ((key[2] >> 3) 1 (key[3] << 5) 1 (key[4] << 13) 1 (key[5] << 21)) &
0x3fffff;
r3 = ((key[5] >> 1) 1 (key[6] << 7) 1 (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 rl(clock_ctl, r1);
r2 = clock_r2(clock ctl, r2);
r3 = clock_r3(clock_ctl, r3);
bit = ((rl >> 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=U;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);
}
void a5_key(a5_ctx *c, char *k)(
c->rl = k[0]<<11|k[1]<<3 | k[2]>>5 ; /* 19 */
c->r2 = k[2]<<17|k[3]<<9 | k[4]<<1 I k[5]>>7; /* 22 */
c->r3 = k[5]<<15|k[6]<<8 | k[7] ; /* 23 */
}
/* Step one bit in A5, return 0 or 1 as output bit. */
int a5_step(a5 ctx *c){
int control;
control = threshold(c->r1,c->r2,c->r3);
c->r1 = clock_r1(control,c->r1);
c->r2 = clock_r2(control,c->r2);
c->r3 = clock_r3(control,c->r3);
return( (c->r1^c >r2^c->r3)&1);
}
/* Encrypts a buffer of len bytes. */
void a5_encrypt(a5_ctx *c, char *data, int len)l
int i,j;
char t;
for(i=0:i<len i++)
for(j=0;j<8;j++) t = t<<1 | a5_step(c)
data[i]^=t;
}
}
void a5_decrypt(a5_ctx *c, char *data, int len){
a5_encrypt(c,data,len);
}
void main(void){
a5_ctx c;
char data[100];
char key[] = {1,2,3,4,5,6,7,8};
int i,flag;
for(i=0;i<100;i++) data[i] = i;
a5_key(&c,key);
a5_encrypt(&c,data,100);
a5_key(&c,key);
a5_decrypt(&c,data,1);
a5_decrypt(&c,data+1,99);
flag = 0;
for(i=0;i<100;i++) if(data[i]!=i)flag = 1;
if(flag)printf("Decrypt failed\n"); else printf("Decrypt succeeded\n");
}
<HR>
<A NAME="Anderson">To: ukcrypto@maillist.ox.ac.uk</A>
Subject: Re: More on A5 strength
Date: Wed, 22 Apr 1998 11:45:37 +0100
From: Ross Anderson <Ross.Anderson@cl.cam.ac.uk>
> According to Applied Crypto section 16.5,
> # There is a trivial attack requiring 2^40 encryptions...
>
> Is that Ross Anderson - if so, how did this work out?
The trivial divide-and-conquer attack, of guessing two of the shift
registers and then working out the third, actually takes 2^45 effort
as you have to guess about half of the bits in the third register
between the LSB and the clock bit. <A HREF="http://jya.com/a5-hack.htm">Golic showed</A> how to reduce the
effort to 2^40 by solving linear equations and stuff like that.
If the ten lowest bits in one of the registers are set to zero
then of course the trivial attack will work with effort 2^35: I
haven't looked at the Golic attack again in detail but I wouldn't be
surprised if the overall effort were now 2^30
Ross
<HR>
From: Paul Leyland <pleyland@microsoft.com>
To: "'ukcrypto@maillist.ox.ac.uk'" <ukcrypto@maillist.ox.ac.uk>
Subject: RE: More on A5 strength
Date: Wed, 22 Apr 1998 06:12:42 -0700
The "A5" implementation posted by Ross wasn't necessarily *the* A5
algorithm, if I remember correctly. Some assumptions had to be made as to
where the LFSR taps were made and what the term "middle bit" means for the
22-bit shift register.
Has anyone revealed the true A5 algorithm?
Paul
<HR>
<A NAME="moller">Date: Thu, 23 Apr 98 15:47 +0200</A>
From: ulf@fitug.de (Ulf Möller)
To: ukcrypto@maillist.ox.ac.uk
Subject: Re: More on A5 strength
Julian Assange <proff@iq.org> wrote:
>I haven't read Ross's [45] - I doubt it is about A5 per se, but rather
>about chaining of multiple LFSR's (A5 uses three), (Ross, please
>correct me) - and Bruce (or someone else) has seen that Ross's attack
>applies to A5. Note that there are several versions of A5, some
>telco's have phones which use A5/7 - these latter versions tend to be
>even weaker than A5/2! It's worth noting that AP 16.5, to my knowledge
>is talking about the proposed (untested) reconstruction of A5, and not
>a confirmed implementation.
The excerpt of the leaked GSM Security Study at
<A HREF="http://jya.com/gsm061088.htm">http://jya.com/gsm061088.htm</A> contains an incomplete description of
"The French Proposal for the Cipher" A5. The cipher consists of three
feedback shift registers; the output stream is the XOR of the MSB of
all three registers. The 19 bit register R1 is given in figure 1 the
LSB after the shift is the XOR of bits 19, 18, 17 and 14). The other
registers are known to be 22 and 23 bits large, and their feedback
functions to consist of only four XORs all together.
Clock control is based on the registers' middle bits (they do not say
exactly which bit in a 22 bit register is "middle"). Each register is
clocked based on its middle bit, inverted if less than two bits are
set. So at least two registers are clocked in each step.
They mention how the keys are loaded, but the order of the bits is not
given. So it seems to me that Ross used the same leaked document from
which COMP128 has been reconstructed.
In his paper "<A HREF="http://www.cl.cam.ac.uk/ftp/users/rja14/fibonacci.ps.Z">On Fibonacci Keystream Generators</A>", Ross states that the
best known attack on A5 consists of guessing the state of R1 and R2
and work out R3 from the keystream. He writes, "There has been
controversy about the work factor involved in each trial, and at least
one telecom engineer has argued that this is about 2^12 operations
giving a real attack complexity on A5 of 2^52 rather than the 2^40
which one might naively expect."
This known-plaintext attack does not depend on how the keys are loaded
to the registers. To execute the attack, you need to know the
feedback polynomials and the position of the "middle" bits, but the
feasibility of the attack clearly does not depend on a particular
choice of these (still unknown) parameters. So if the French A5 is in
use, it can be broken in 2^52 decryptions.
Assume we have guessed the 40 bits of R1 and R2, and want to find R3,
given the output keystream (that is ciphertext XOR the known
plaintext). We get the MSB of R3 from knowing the MSB of R1 and R2
and the output bit, because the output stream is the XOR of the three
MSBs. So if we can cycle the registers through and get all the 23
bits of R3, we have determined the initial state of R3 and can do test
decryptions to see if the guess of R1 and R2 was right in the first
place. (Note that this works for any feedback polynomial.)
However, not all registers are clocked in every step. Not knowing the
middle bit of R3, in half the cases we don't know if R3 will be
clocked, in the other half we don't know whether R1 or R2 will be
clocked. But if we guess the middle bit correctly, we know which
registers are clocked. Thus the MSBs of R1 and R2 in the next step are
known and we can determine the content of the MSB of R3 from the
output bit. Then, we guess the new middle bit, which determines the
following step and again yields the MSB (bit 22 of the inital
configuration). If we repeat this until we have the complete R3,
guessing 11 bits gets us another 11 bits for free. (Does anyone see a
shortcut there?)
What this means for the security of GSM depends on the GSM protocol.
How much known plaintext does it provide? Are the frame sequence
numbers that are mixed into registers known to evesdroppers (otherwise
they'd have to try ~2^52 decryptions on every frame)?
If the frame sequence numbers are known, the reduced keyspace might
also help to break the encryption. Assuming the 10 zero-bits end up
in R1, you guess the remaining 9 bits and fast-forward the register
according to the random distribution that is given by the position in
the stream you are trying to break (in each step R1 is clocked with
probability 3/4). Then guess R2 and half of R3 as above.
<HR>
<A NAME="rja2">To: ukcrypto@maillist.ox.ac.uk</A>
Subject: Re: More on A5 strength
Date: Fri, 24 Apr 1998 12:31:55 +0100
From: Ross Anderson <Ross.Anderson@cl.cam.ac.uk>
> Does anyone see a shortcut there?
Last time I looked at it carefully I concluded that you only
need to guess the clock inout bit half the time, so you need
about 5 bit guesses giving an overall complexity of 2^45. I
could be wrong though - it's notorious that you only get the
real complexity of an attack when you implement and test it.
Jovan Golic showed that you can get a 2^40 attack with a
little more work, and you can work back from a reconstructed
state to get Kc. This paper is worth studying; it's in the
proceedings of Eurocrypt 97 (LNCS v 1233) pp 239-255 and
entitled `<A HREF="http://jya.com/a5-hack.htm">Cryptanalysis of Alleged A5 Stream Cipher</A>'
Ross
<HR>
<A NAME="whp">Date: Fri, 24 Apr 1998 08:00:52 -0600</A>
From: bill payne <billp@nmol.com>
To: jy@jya.com
Subject: SHIFT REGISTER technology
Friday 4/24/98 7:33 AM
The stuff on linear and non-linear shift register sequences which is now
appearing on jya.com is the ‘military-grade’ crypto technology.
Semionoff and <A HREF="http://www.jya.com/crack-a5.htm">http://www.jya.com/crack-a5.htm</A> contains material similar
to what I saw Brian Snow present in schematics of NSA KG units.
The statement by david.loos@eudoramail.com
The A5 algorithm uses a three level, non-linear feedback shift
register arrangement, designed to be sufficiently complex to resist
attack.
points to the technology used for military-grade crypto.
The reason NSA regarded the R register, seen at
<A HREF="http://jya.com/whpfiles.htm">http://jya.com/whpfiles.htm</A>, <I>[See: <A HREF="http://jya.com/da/whpda.htm">http://jya.com/da/whpda.htm</A>]</I>
feedback function classified was that it contained a non-linear feedback
function.
I was ORDERED to build UNCLASSIFIED hardware. This is why I stuck the R
register feedback function in a fast ram.
This similarity between the structure of the nonlinear feedback function
in the CAVE algorithm seen at
<A HREF="http://www.semionoff.com/cellular/hacking/phreaking/">http://www.semionoff.com/cellular/hacking/phreaking/</A>
to the feedback function published in my SAND report
: A11 A1 A5 AND
A1 0= A9 0= AND XOR
A6 A10 XOR XOR ;
reveals “military-strength” technology.
SHIFT REGISTERS.
Words ‘shift registers’ also caused the Great American Spy Sting bust.
<A HREF="http://caq.com/CAQ/caq63/caq63madsen.html">http://caq.com/CAQ/caq63/caq63madsen.html</A>
The Cold War is over. And the crypto cat is now about fully out of the
bag. Let’s hope for settlement so that we can all go on to more constructive
tasks.
Later
bill
<HR>
To: ukcrypto@maillist.ox.ac.uk
Subject: Re: More on A5 strength
Date: Sat, 25 Apr 1998 13:12:45 +1000
From: Greg Rose <ggr@qualcomm.com>
Ross Anderson writes:
>> Does anyone see a shortcut there?
>
>Last time I looked at it carefully I concluded that you only
>need to guess the clock inout bit half the time, so you need
>about 5 bit guesses giving an overall complexity of 2^45. I
>could be wrong though - it's notorious that you only get the
>real complexity of an attack when you implement and test it.
I implemented this kind of attack about a year
ago, and you're right, the complexity is about
2^44 (measured).
Greg.
Greg Rose INTERNET: ggr@qualcomm.com
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
<HR>
<A NAME="daw">From: David Wagner <daw@cs.berkeley.edu></A>
Subject: Algorithm ID on SIMs (fwd)
To: jya@pipeline.com
Date: Mon, 27 Apr 1998 08:29:04 -0700 (PDT)
The following note appeared on a closed smartcard mailing list,
where there's been some discussion of the GSM hacks.
A translation to plain English: a GSM document suggests there
are several other defined GSM authentication algorithms, in
addition to the COMP128 one which we broke.
(In our experience, most providers use COMP128, with some exceptions;
but if there are other "standard" algorithms, one of them might
become the future favorite after folks ditch COMP128.)
Just thought you might be interested in posting this "teaser"
about potential future targets on your site.
Take care.
-- Dave
Forwarded message:
<I>[JYA note: ID removed at poster's request:</I>
<I></I>
<I>Sure, put it on your homepage, but strip off all the headers and </I>
<I> my name, please. Just mention that it was posted on the scard </I>
<I> mailing list.]</I>
Subject: Algorithm ID on SIMs
To: scard@cryptsoft.com
Date: Mon, 27 Apr 1998 16:31:16 +0200 (CEST)
I was just browsing through en 726-3 when I saw "COMP 128" mentioned.
This is in section 7.6.5 (Algorithm ID).
The algorithm ID is stored in a keyfile. I don't know whether GSM has such a
keyfile and if it is readable (the en 726-3 specs are not clear about this).
Hmm... probably not readable, since the secret key is stored in the same
file :-)
The following values are defined:
Algo ID AUTH PRO STAMPED KEY LOAD
DSAA '1' x
COMP NAT '2' x
TESA-7 '4' x x x x
COMP 128 '40' x
Propr '7F'
DSAA means DECT Standard Authentication Algorithm
So perhaps the providers that do not use COMP 128 use one of the above? After
all, they are off the shelf algorithms and it is very unlikely that a provider
would spend a lot on its own proprietary algorithm.
<HR>
Date: Tue, 28 Apr 1998 13:49:44 +0200
From: masson <interception@ii-mel.com>
To: jya@pipeline.com
Subject: Air-intercept IMSI to clone IMSI
It's also possible to intercept IMSI when you turn on a GSM:
in fact, at that moment the mobile phone transmits the identification
number to the Base Station, and at this moment it's possible to
numerically scan and to duplicate from a PC.
Catching the IMSI isn't sufficient to be able to make calls. You also
need to know the private key within the SIM.
Of course, the owner of GSM knows when he has lost his SIM card, will
notify the operator of the cellular phone (Bouygues...) and a
phreaking will be prevented.
The Bouygues Telecom operator, for example, has a counter-measure:
- if the SIM card is used twice in the same time period;
- last-next call incompatible with the distance
The following events invoke a MSC or BSS trace:
-Call set-up within MSC (OMC, MTC)
-Location update (normal & periodic)
-IMSI attach and detach
MSCEventRecord
invokingEvent
servedIMSI
served IMEI
callingcalledNumber
connectedNumber
originalCallNumber
Location
RadioChannelTypes
recordExtensions (Ericsson-F : mobile positionning center)
TimedLocation
LocationAreaAndCell
changeTime
MSCInvokingEvent
moc
mtc
locationupdate
sms-mo
sms-mt
imsiAttach
imsiDetach
DraftprETS 627 (GSM 12.08 version 4.5.0) september 1997
<HR>
Date: Tue, 28 Apr 1998 05:03:35 -0400 (EDT)
From: Gary Mounfield <mani@firehouse.net>
To: jya@jya.com
Subject: Re: [ISN] Hackers Copy Mannesmann Mobile Phone Sim Card (fwd)
---------- Forwarded message ----------
Date: Mon, 27 Apr 1998 19:00:22 -0600 (MDT)
From: mea culpa <jericho@dimensional.com>
To: InfoSec News <isn@sekurity.org>
Subject: Re: [ISN] Hackers Copy Mannesmann Mobile Phone Sim Card
From: Felix von Leitner <leitner@math.fu-berlin.de>
Date: Tue, 28 Apr 1998 01:36:21 +0200
Subject: Re: [ISN] Hackers Copy Mannesmann Mobile Phone Sim Card
> In order to clone a SIM card, the hackers had to have both a copy of the
> original SIM card for at least 11 hours and know the PIN number.
> Scientists at the University of California and the Smartcard Developers
> Association in the USA already reported weaknesses in smaller mobile
> telecoms networks at the beginning of April which work on the same GSM
> standard as the German networks D1, D2 and E-Plus.
This is of course bullshit. If they used the same standard, they would
all be vulnerable. As a member of the CCC I can clarify a little here.
D2 is the only German network using COMP128 right now, which is the GSM
reference encryption algorithm. What we did is "simply" implement the
attack outlined by Ian Goldberg et al from Berkeley. And we made the
necessary software available on www.ccc.de, and there are blueprints for
useful hardware. The PIN is not an issue because evil mobile dealers
can sell cloned phones now.
Our GSM guy says that there are only three networks that are known not
to use COMP128 right now, and two of them are in Germany, obviously.
For those who speak German, there is a nice round-up on
<A HREF="http://www.ccc.de/D2Pirat/index.html">http://www.ccc.de/D2Pirat/index.html</A>
and you can download the software there, too. There are pictures of the
equipment there, too, that look quite cool ;)
What we demonstrated was that you can get the pin from the "secure"
envelope without traces and that you can use the attack from Goldberg to
get the secret key from the card in about 11 hours without overclocking
the card or tricks like that. The URL to Goldberg's method was already
posted on ISN I believe. And we showed that the clone and the original
can check into the D2 GSM network at the same time, they just can't
place calls simultaneously without error messages. This all is of
course still very useful to criminals who need anonymous phones.
BTW: D2 put out some of the typical press blah like "no real damage",
"only theoretical attack", "same problem as when you lose your card",
stuff like that ;)
What remains to be seen is whether the other German mobile carriers use
better or just different algorithms.
Felix
-o-
Subscribe: mail majordomo@sekurity.org with "subscribe isn".
Today's ISN Sponsor: Dimensional Communications (www.dim.com)
<HR>
Date: Tue, 28 Apr 1998 11:20:05 -0400 (EDT)
From: <I>[Deleted by request]</I>
To: John Young <jya@pipeline.com>
Subject: Re: [ISN] Hackers Copy Mannesmann Mobile Phone Sim Card (fwd)
The last post from Masson, re grabbing IMEI, raises some interesting
thoughts. For several years now there have been devices available (not
commonly, but available) which will effectively track a GSM cellfone.
The units are about the size of a pack of cigarettes (occasionally
concealed as such) and will "lock on" to a particular IMEI/IMSI.
Tracking in the handheld models is much the same as other simple direction
finding / tracking gear. However there are also items available which are
closer to the old ETACS tracking sets, giving a map of the surrounding
cellsites, and extremely accurate positioning. Very, very nice toys, and
outstandingly useful. Makes this month's crypto@c2 discussions on
position escrow seem a little redundant :)
<HR>
<A NAME="a5c">Date: 26 April 1998</A>
From: John Young <jya@pipeline.com>
To: ukcrypto@maillist.ox.ac.uk,cypherpunks@toad.com
Subject: GSM A5 Papers
We would be grateful for assistance in obtaining copies of the
following papers, particularly the first:
S J Shepherd, "Cryptanalysis of the GSM A5 Cipher Algorithm",
IEE Colloquium on Security and Cryptography Applications to
Radio Systems, Digest No. 1994/141, Savoy Place, London, 3
June 1994, (COMMERCIAL-IN-CONFIDENCE).
S J Shepherd, "An Approach to the Cryptanalysis of Mobile
Stream Ciphers", IEE Colloquium on Security and Cryptography
Applications to Radio Systems, Digest No. 1994/141, Savoy
Place, London, 3 June 1994, (COMMERCIAL-IN-CONFIDENCE).
S J Shepherd, "Public Key Stream Ciphers", IEE Colloquium on
Security and Cryptography Applications to Radio Systems,
Digest No. 1994/141, pp 10/1-10/7, Savoy Place, London, 3 June
1994.
These are listed on Dr Shepherd's bio at:
<A HREF="http://vader.brad.ac.uk/finance/SJShepherd.html">http://vader.brad.ac.uk/finance/SJShepherd.html</A>
----------
Date: 26 April 1998
From: John Young <jya@pipeline.com>
To: S.J.Shepherd@bradford.ac.uk
Subject: Cryptanalysis Papers
Dear Dr. Shepherd,
May we ask your advice in obtaining copies of your papers,
"Cryptanalysis of the GSM A5 Cipher Algorithm," and "An
Approach to the Cryptanalysis of Mobile Stream Ciphers?"
Thank you very much.
Regards,
John Young
JYA/Urban Deadline
251 West 89th Street, Suite 6E
New York, NY 10024
Tel: 212-873-8700
Fax: 212-799-4003
E-mail: jya@pipeline.com
----------
Date: 26 April 1998
From: John Young <jya@pipeline.com>
To: sales@iee.org.uk
Subject: Order for Publications
The Institution of Electrical Engineers, PO Box 96, Michael
Faraday House, Stevenage, Herts. SG1 2SD, UK
Tel: +44 (0)1438 313311; Fax: +44 (0)1438 742792;
E-mail: sales@iee.org.uk
Please send me the following:
Quantity: 1 of each
S J SHEPHERD, "Cryptanalysis of the GSM A5 Cipher Algorithm",
IEE Colloquium on Security and Cryptography Applications to Radio
Systems, Digest No. 1994/141, Savoy Place, London, 3 June 1994.
S J SHEPHERD, "An Approach to the Cryptanalysis of Mobile
Stream Ciphers", IEE Colloquium on Security and Cryptography
Applications to Radio Systems, Digest No. 1994/141, Savoy Place,
London, 3 June 1994.
<I>[Snip balance]</I>
----------
Date: Mon, 27 Apr 1998 17:00:55 +0100 (BST)
From: Simon Shepherd <sjshephe@vader.eeng.brad.ac.uk>
To: jya@pipeline.com
Subject: Re: Cryptanalysis Papers
Dear John
I regret that the two papers you mention have been classified
by the spooks as UK EYES ONLY for "security reasons". They
appeared only in the classified sections of the proceedings.
Sorry.
Simon S
<HR>
<A NAME="hanche">To: cryptography@c2.net</A>
Subject: Re: TIME Magazine on GSM cell phone crack
Date: Thu, 30 Apr 1998 11:17:09 +0200
From: Harald Hanche-Olsen <hanche@math.ntnu.no>
- Phil Karn <karn@qualcomm.com>:
| >> The SDA cautions that no practical over-the-air attack is known
| >> yet but that one should not be ruled out.
|
| >Ok, so which is it?
|
| The latter. I am not intimately familiar with the details of GSM
| over-the-air authentication, but I suspect it is indeed possible to
| conduct this attack over the air. The bottleneck is apparently the
| SIM card, so it wouldn't take much longer to do it over the air. But
| I'll defer to the experts who actually worked on the problem.
One problem with over-the-air attacks on a GSM phone suddenly occured
to me: Remember that the output of COMP128 is 96 bits, 32 of which
are called SRES (output of A3 algorithm) and 54 of which are called Kc
(output of A8 algorithm, after 10 zero bits are appended) and 10 of
which are thrown away (to make an attack on A5 easier?)
Now, only SRES is transmitted over the air back to the base station.
Kc, being the key used for A5 to encrypt the communication channel, is
obviously not transmitted.
Presumably, only getting 32 bits of the COMP128 output per round must
increase the difficulty of the cracking attempt, thereby requiring
more challenge-response pairs to make up for this.
Does anybody in the know care to comment?
- Harald
<HR>
<A NAME="ian">To: cryptography@c2.net</A>
From: iang@cs.berkeley.edu (Ian Goldberg)
Subject: Re: TIME Magazine on GSM cell phone crack
Date: 2 May 1998 20:48:25 GMT
In article <19980430111709D.hanche@math.ntnu.no>,
Harald Hanche-Olsen <hanche@math.ntnu.no> wrote:
<I>[Snip]</I>
>Presumably, only getting 32 bits of the COMP128 output per round must
>increase the difficulty of the cracking attempt, thereby requiring
>more challenge-response pairs to make up for this.
Nope. In fact, we took this into account when designing the attack.
It is extremely rare that the first 32 bits of the COMP128 output
of two different inputs will match, but the whole output will not.
- Ian
<HR>
</PRE></PRE>
</BODY></HTML>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed