Statistical attack on combination keystream generators with irregular clocking

Combination keystream generators with irregular clocking are the basis for constructing of stream ciphers, the most famous of which are A5 and Alpha1. Each such generator consists of several binary linear feedback shift registers, a Boolean combination function, and a register clocking control unit that defines the rules by which registers are shifted in the process of keystream generating. Despite certain weaknesses of known stream ciphers based on combination keystream generators with irregular clocking, such generators still arouse theoretical and applied interest due to the simplicity of their structure and the potential ability to provide security to a wide class of attacks, provided that their components are properly selected. Combination keystream generators, each register of which is either shifted by one step or is idle in each clock cycle, with one of the registers clocking regularly, are investigated in the article. Previously, the authors of the article showed that the mentioned generators have an inherent weakness, which consists in statistical dependence between each neighboring signs of their output sequences. The main result of this article is a statistical attack based on the mentioned weakness. The proposed attack is aimed at restoring the initial state of the register clocking uniformly by a known output sequence of the generator or several such sequences produced by the generator in the chosen IV mode. It is shown that in the latter case the complexity of the attack depends linearly on the length of the mentioned register. An analytical bound of the amount of keystream required to implement the proposed attack with the required success probability is obtained. In particular, it is shown that for Alpha1 the corresponding amount is approximately 300 keystream frames along with their corresponding initialization vectors. Conditions that weaken the security of generators with irregular clocking against the proposed attack are formulated. They consist in the fact that the Walsh-Hadamard coefficients of the combination function take zero values on all vectors of weight 0 or 1 and non-zero values on certain vectors of weight 2. It is shown that these conditions are fulfilled for the keystream generator of Alpha1. In this case, the average amount of keystream required to recover the initial state of an arbitrary keystream generator that satisfies the above conditions is of the same order as for Alpha1.