Arnold G. Reinhold wrote:
>
> Matthew,
>
> Your approach is interesting, but it claims a gain of about 100 in reduced
> cycle time, while giving up the ability to use the knowledge that ten key
> bits are zero, which is a factor of 1000. So it is not a win in that sense.
> However your analysis does suggest that going to a full 64 bit key would
> not yield a corresponding gain in strength for A5/1.
[...]
> Finally, it is not clear to me that you can run A5 backwards after the 100
> mixing steps because then the non-linear majority voting circuit is
> operating. I haven't thought that question through.
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.
Since the shift registers themselves are linear, it's trivial to run
them backwards a fixed number of clocks.
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.
Raph
