[2578] in cryptography@c2.net mail archive
Re: More on A5 strength
daemon@ATHENA.MIT.EDU (Ulf =?iso-8859-1?Q?M=F6ller?=)
Thu Apr 23 15:25:33 1998
Date: Thu, 23 Apr 98 15:47 +0200
From: ulf@fitug.de (Ulf =?iso-8859-1?Q?M=F6ller?=)
To: ukcrypto@maillist.ox.ac.uk
In-Reply-To: <wxyax54fno.fsf@polysynaptic.iq.org>
Cc: cryptography@c2.net
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
http://jya.com/gsm061088.htm 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 "On Fibonacci Keystream Generators", 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.
