>Golic's paper shows how to run the state backwards 100 cycles in 10^4
>expected, 10^6 worst case work factor. Briefly, you exhaustively search
>the space of how many clocks each of the shift register goes through.
>This value is about 75 +/- 4 for each of the three shift registers.
At least 2 of the 3 registers must shift per clock, and the probability
of any one shifting is 0.75, so 75+- makes sense.
Is there a reference for this paper?
>Since the shift registers themselves are linear, it's trivial to run
>them backwards a fixed number of clocks.
Yep.
>I think it's also possible to run the state backwards more directly, by
>considering each of the four possible "pre-states" and rejecting those
>for which the clock bits don't match up. Thus, you get a state tree with
>a variable (0..4) branching factor. David Wagner has suggested that
>traversing this tree is a good way to get a handle on how many key bits
>are lost, and maybe giving insight into the relatively short cycles of
>A5/1. This is a great project for someone who has hacking ability and
>wants to contribute to the cryptanalysis knowledge for A5/1.
I started a little exploration in this yesterday, wondering if the
"map" I suggested is actually feasible.
