More on A5 strength

[Julian Assange]

David Hopwood <hopwood@zetnet.co.uk> writes:

> According to Applied Crypto 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 (http://www.underground-book.com/), (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.