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.

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

Section

INFORMATION SECURITY