On reduction of key space of the cipher A5/1 and on reversibility of the next-state function for a stream generator

We study stream ciphers based on feedback shift registers. For a stream generator (in general form) we prove that reversibility of its next-state function is closely connected to the recurrency of the shift control function. Then we study generator for the stream cipher А5/1 used in GSM cellular telephone standard. For this generator we count the number of states that can be obtained after $t$ cycles from an initial state without predecessors and cannot be obtained in this way after the smaller number of cycles. We show how to exponentially reduce the key space of A5/1 while clocking. The results can be directly used in cryptanalysis of A5/1. Ill. 5, tab. 1, bibliogr. 8.