A faster cryptanalysis of the self-shrinking generator

Abstract

A novel algorithm for cryptanalysis of the self-shrinking generator is presented and discussed, assuming that number of the shift register feedback taps is large and that length of the available generator output sequence is under a certain limit. It is baseo on a probabilistic approach and employes the generator output sequence not only for the hypothesis testing, but also for reducing the set of hypothesis which have to be tested. When the shift register length is L and the characteristic polynomial is known, the novel algorithm ensures the cryptanalysis with overall compexity 2L-l, l ≤ L/2, assuming that required length of the generator output sequence is not greater than l2L/2 (L/2/l)-1 . The proposed algorithm yields significant average gain of 2l-0.25L in comparison with the best one pubhshed so far, which can work under the assumed conditions.