Filter generators with increased resistance against algebraic attacks

Authors

  • Kateryna Vorobei Institute of Special Communication and Information Protection of the National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine https://orcid.org/0009-0007-4523-0626
  • Anton Alekseychuk Institute of Special Communication and Information Protection of the National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv, Ukraine https://orcid.org/0000-0003-4385-4631

DOI:

https://doi.org/10.20535/2411-1031.2023.11.2.293748

Keywords:

cybersecurity, cryptographic protection of information, stream cipher, filter generator, algebraic attack, security justification

Abstract

Filter generators form one of the best known and most studied classes of key stream generators used in synchronous stream ciphers. Each such generator consists of a binary linear shift register with a primitive feedback polynomial and a nonlinear Boolean function, which has a number of requirements related to the condition of generator security against known attacks. One such requirement is the high algebraic immunity of the generator's filter function; this parameter characterises security filter generator against modern algebraic attacks. In certain cases, this requirement is too restrictive in sense of practicality, as it increases the computational or circuit complexity of the key stream generation algorithm. This makes the actuality of increasing the resistance of filter generators with fixed filter functions, that have limited (low) algebraic immunity. The paper proposes to solve this problem by modifying the feedback function of the linear shift register. the security of the proposed generators against algebraic attacks is investigated and is shown that (under certain natural conditions) such generators are more secure at the same initial state length as compared to traditional filter generators. The proposed solution seems to be useful for practical application in advanced hardware-oriented stream ciphers design.

Author Biographies

Kateryna Vorobei, Institute of Special Communication and Information Protection of the National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

postgraduate student at the state information resources academic department

Anton Alekseychuk, Institute of Special Communication and Information Protection of the National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

doctor of technicai science, professor, professor at the state information resources academic department

References

T. W. Cusick, and P. Stanica, Cryptographic Boolean Functions and Applications. San Diego, California, USA: Academic Press is an imprint of Elsevier, 2009.

N. Courtois, and W. Meier, “Algebraic attacks on stream ciphers with linear feedback”, in Proc. Advanced in Cryptology – EUROCRYPT 2003, Springer Verlag, pp. 345-359, 2003. [Online]. Available: https://www.researchgate.net/publication/221348082_Algebraic_Attacks_on_Stream_Ciphers_with_Linear_Feedback. Accessed on: Sep. 12, 2023.

N. Courtois, A. Klimov, J. Patarin, and A. Shamir, “Efficient algorithms for solving overdefined systems of multivariate polinomial equations”, in Proc. Advanced in Cryptology – EUROCRYPT 2000, Springer Verlag, pp. 392-407, 2000. [Online]. Available: https://www.researchgate.net/publication/221347926_Efficient_Algorithms_for_Solving_Overdefined_Systems_of_Multivariate_Polynomial_Equations. Accessed on: Sep. 12, 2023. doi: https://doi.org/10.1007/3-540-45539-6_27.

N. Courtois, “Fast algebraic attacks on stream ciphers with linear feedback”, in Proc. Advanced in Cryptology – EUROCRYPT 2003, Springer Verlag, pp. 177-194, 2003. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-540-45146-4_11. Accessed on: Sep. 04, 2023.

L. Bettale, J.-C. Faugere, and L. Perret, “Hybrid approach for solving multivariate systems over finite fields”, J. Math. Crypt., vol. 3, pp. 177-197, 2009. doi: https://doi.org/10.1515/JMC.2009.009.

A. S. Meluzov, “On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a part of variables”, Diskretnaya Matematika, vol. 23, pp. 66-79, 2011. doi: https://doi.org/10.4213/dm1162.

F. Armknecht, “Improving fast algebraic attacks” in Proc. Fast Software Encryption – FSE’04, Proceedings, Springer-Verlag, pp. 65-82, 2004. [Online]. Available: https://www.researchgate.net/publication/220942492_Improving_Fast_Algebraic_Attacks. Accessed on: Sep. 04, 2023. doi: https://doi.org/10.1007/978-3-540-25937-4_5.

C. Carlet, Boolean Functions for Cryptography and Error Correcting Codes, LAGA, University of Paris 8, France, 2007.

F. Armknecht, “On the existence of low-degree equatios for algebraic attacks”, Theoretische Informatik. [Online]. Available: https://eprint.iacr.org/2004/185.pdf. Accessed on: Sep. 16, 2023.

J.-C. Faugere, “A new efficient algorithm for computing Groebner bases (F4)”, Journal of Pure and Applied Algebra, vol. 139, pp. 61-88, 1999.

J.-C. Faugere, “A new efficient algorithm for computing Groebner bases without reduction to zero (F5)”, ISSAC 2002, ACM Press, pp. 75-83, 2002. [Online]. Available: https://dl.acm.org/doi/10.1145/780506.780516. Accessed on: Sep. 14, 2023. doi: https://doi.org/10.1145/780506.780516.

D. K. Dalai, K. C. Gupta, and S. Maitra, “Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity”, in Proc. Fast Software Encryption – FSE’05, Proceedings, Springer-Verlag, pp. 98-111, 2005. [Online]. Available: https://dl.acm.org/doi/10.1007/11502760_7. Accessed on: Sep. 16, 2023. doi: https://doi.org/10.1007/11502760_7.

D. K. Dalai, S. Maitra, and S. Sarkar, “Basic theory in construction of Boolean functions with maximum possible algebraic immunity”, Designs, Codes and Cryptography, vol. 40, pp. 41-58, 2006. [Online]. Available: https://eprint.iacr.org/2005/449.pdf. Accessed on: Jul. 17, 2023.

I. Gorbenko, A. Kuznetsov, Yu. Gorbenko, A. Alekseychuk, and V. Timchenko, “Strumok Keystream Generator”, in Proc. 20018 IEEE 9th International Conference on De-pendable Systems, Services and Technologies (DESSERT), Kyiv, 2018, pp. 292-299. [Online]. Available: https://ieeexplore.ieee.org/document/8409147. Accessed on: Sep. 19, 2023. doi: https://doi.org/10.1109/DESSERT.2018.8409147.

E. Berlekamp, Algebraic Coding Theory. London, UK: World Scientific Publishing Company, 2015.

Downloads

Published

2023-12-28

How to Cite

Vorobei, K., & Alekseychuk, A. (2023). Filter generators with increased resistance against algebraic attacks. Collection "Information Technology and Security", 11(2), 149–155. https://doi.org/10.20535/2411-1031.2023.11.2.293748

Issue

Vol. 11 No. 2 (2023)

Section

INFORMATION SECURITY

License

Copyright (c) 2023 Collection "Information Technology and Security"

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The authors that are published in this collection, agree to the following terms:

  1. The authors reserve the right to authorship of their work and pass the collection right of first publication this work is licensed under the Creative Commons Attribution License, which allows others to freely distribute the published work with the obligatory reference to the authors of the original work and the first publication of the work in this collection.
     
  2. The authors have the right to conclude an agreement on exclusive distribution of the work in the form in which it was published this anthology (for example, to place the work in a digital repository institution or to publish in the structure of the monograph), provided that references to the first publication of the work in this collection.
     
  3. Policy of the journal allows and encourages the placement of authors on the Internet (for example, in storage facilities or on personal web sites) the manuscript of the work, prior to the submission of the manuscript to the editor, and during its editorial processing, as it contributes to productive scientific discussion and positive effect on the efficiency and dynamics of citations of published work (see The Effect of Open Access).