I worked on cryptanalyzing A5-1 several years ago. I built a
tree-based search routine that could retire many keys in each test
cycle. The exact number per cycle varied enormously depending on how
far into the tree I was when I found a conflict with the keystream
that would let me prune the branch. In the early phases of the search
this could be as much as 1/8 of the entire 64-bit shift register
space, but most of the time it was "only" a few million keys.
My approach assumed an arbitrary 64 bits of initial shift register
state, and I couldn't readily see how to exploit the fact that the
initial key had less entropy because of the way the crank is turned
100 times before generating a keystream.
I haven't worked on this problem in a while, but it did seem to me
that this problem is even more amenable to custom hardware than DES.
I suppose I could dust off my code...
Phil
