Probabilistic properties of solutions to the equation system of keystream generators with irregular motion
Anton Alekseychuk, Ihor Samoylov · Radiotekhnika · 2024
The traditional basis for constructing modern stream ciphers is keystream generators, which are based on linear shift registers and nonlinear complexity elements. One of the well-known methods for increasing the resistance of such generators, in particular, against algebraic and correlation attacks, is using irregularity into register’s motion process. The most popular keystream generators with irregular motion, used in stream ciphers are A5/1, Alpha1, LILI-128 and others, were thoroughly studied in the 1990s and 2000s. However, specialists’ interest remains relevant, it’s evidenced by recent publications dedicated to new attacks on the A5/1 cipher and some other stream ciphers, constructed based on keystream generators with irregular motion. On the one hand, this known methods for covering wide range of different keystream generators, but on the other hand, it reduces the accuracy and adequacy of conclusions about the resistance of specific ones. The main result of the article is probabilistic properties of solutions to the system of keystream generation equitation of keystream generators with irregular motion. In particular, a matrix representation for the average number of solutions to these systems of equitation has been obtained and conditions have been established under which a combinational generator with external control is irreversible by Huffman. Additionally, sufficient conditions for the exponential growth of the average number of solutions to keystream generation of this generator, depending on the length of output sequence, have been obtained, along with analytical expressions and estimates of probability distributions for sums of random vectors produced by motion control blocks of a certain class of combinational keystream generators. The obtained results can be applied to solving the problems of evaluation the resistance of keystream generators with external controlled motion and justifying the requirements for the cryptographic parameters of complexity nodes in such generators in such generators, which determine their resistance to correlation attacks.