Probabilistic properties of solutions to the equation system of keystream generators with irregular motion
DOI:
https://doi.org/10.30837/rt.2024.3.218.07Keywords:
cryptographic information protection, stream cipher, keystream generator with irregular motion, finite automaton, Huffman irreversibility, keystream generation equation system, resistance justificationAbstract
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.
References
Katz J., Lindell Y. Introduction to Modern Cryptography. Taylor & Francis Group, 2021. 628 p.
Олексійчук А. М., Курінний О. В. Методи криптоаналізу потокових шифрів : навч. посіб. Київ : КПІ ім. Ігоря Сікорського, 2023. 172 с.
Anderson R., Roe M. A5. [Електронний ресурс] : http://jya.com/crack-a5.htm.
Komninos N., Honary B., Darnell M. An efficient stream cipher Alpha1 for mobile and wireless devices // Proceedings of the 8-th IMA International Conference on Cryptography and Coding. 2001. P. 294–300.
Simpson L.R. LILI Keystream Generator / L.R. Simpson, E. Dawson, J.D. Golić, W.L. Millan // Selected Are-as in Cryptography. SAC 2000. Lecture Notes in Computer Science, vol. 2012. Springer, Berlin, Heidelberg. P. 248–261.
Sadkhan S.B. A proposed Development of Clock Control Stream Cipher based on Suitable Attack // 2020 1st. Information Technology To Enhance e-learning and Other Application. IT-ELA, 2020, P. 165–170. doi: 10.1109/IT-ELA50150.2020.9253074.
Xu Y., Hao Y., Wang M. Revisit two memoryless state-recovery cryptanalysis methods on A5/1 // http://eprint.iacr.org /2023/1557.
Meneses A., van Oorschot P., Vanderstone S. Handbook of applied cryptography. CRC Press, 1997.
Kholosha A.A. Clock-controlled shift registers for key-stream generation // http://eprint.iacr.org /2001/061.
Gollman D., Chambers W.G. Clock-controlled shift registers: a review // IEEE J. on Selected Areas in Com-munication. 1989. V. 7. № 4. P. 525–533.
Golić J., O’Connor L. Embedding and probabilistic correlation attacks on clock-controlled shift registers // Advances in Cryptology – EUROCRYPT’94, Proceedings. Springer Verlag. 1995. P. 230 243.
Golić J., Petrovic M.V. A generalized correlation attacks with a probabilistic constrained edit distance // Ad-vances in Cryptology – EUROCRYPT’92, Proceedings. Springer Verlag. 1992. P. 472–476.
Johansson T. Redused complexity correlation attacks on two clock-controlled generators // ASIACRYPT’98, Proceedings. Springer Verlag. 1998. P. 342–356.
Mikhailov G.V., Chistyakov V.P. On the problems of finite automatons theory related to the number of pre-images of the output sequences // Review of Applied and Industrial Mathematics. 1994. Vol. 1, Iss. 1. P. 108–117.
Ekdahl P., Johansson T. Another attack on A5/1 // IEEE Trans. on Inform. Theory. 2003. Vol. 49. P. 1–7.
Ekdahl P. On LFSR-based stream cipher: analysis and design. Ph. D. Th., 2003.
Коваленко І.М., Гнеденко Б.В. Теорія ймовірностей. Київ : Вища шк., 1990. 328 с.
Feller W. An introduction to probability theory and its application. Willey. N.-Y., 1950. 420 p.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
