More on A5 strength

[Ross Anderson]

> 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. Golic showed 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