Correlation Analysis On Several Stop-and-Go Clocked Keystream Generators

Irregularly clocking is the general technique for destroying the linearity inherent in LFSRs, as well as producing sequence with long periods and high linear complexity. The stop-and-go clocking is interesting particularly for high speed applications. Correlation analysis and correlation attack, as the most important approaches to attack irregularly clocked keystream generators, are widely studied. In this paper, using the idea of probability, measure theory and stochastic process, we consider correlation analysis on three typical keystream generators incorporating stop-and-go clocked LFSRs, i.e., the alternating step generator, the stop-and-go clocked combiner and the bilateral stop-and-go generator.Firstly, we demonstrate a fast correlation on the alternating step generator, based on a probabilistic analysis which reconstructs a sequence associated with the regularly clocked LFSR sequence from the output sequence. Comparisons with other attacks show that our attack offers good trade-off between the required keystream length, complexity and the success probability.Secondly, the properties of output sequences of stop-and-go clocked combiners are discussed. It is proved that the output sequences are stationary and obey strong law of large numbers and central limit theorem. Using the probabilistic model properly built, we analyze the rate of coincidence between the output sequences of two kinds of generators with basic operations and corresponding LFSRs' sequences. All the computational formulae are derived. A recursive algorithm for efficiently computing the poster probability of partial input strings and corresponding joint probability is introduced. Moreover, divide-and-conquer attacks on this kind of generators which reconstruct the initial states of the input stop-and-go generators individually are proposed.Thirdly, proper probabilistic model is built for the bilateral stop-and-go generator and the probability properties of its output sequence are studied. It is proved that the output sequence obey strong law of large numbers and central limit theorem and that, however, the distributions of 0 and 1 in the output sequence are imbalanced, which implies that this generator cannot be used as keystream generator directly. The rate of coincidence between the output sequence and corresponding LFSR sequences, together with their first derivatives are obtained, which reveal the existence of correlation between these sequences.