Filter generators with variable transition functions over finite fields of characteristic 2
DOI:
https://doi.org/10.20535/2411-1031.2024.12.1.306256Keywords:
cryptographic protection of information, stream cipher, filter generator, transition function, algebraic attack, statistical attack, security proofAbstract
Filter generators are a traditional basis for creating synchronous stream ciphers. They are built with the help of linear shift registers (usually over a field of two elements) and nonlinear complexity functions, which are subject to a number of requirements in terms of the generators security against known attacks. Intensive researches of filter generators during the last decades show that meeting these requirements without degrading the performance of the generators is a very difficult task. Despite a large number of publications devoted to the construction of complexity functions with known “good cryptographic properties”, the usage of such functions in practice often becomes unacceptable due to the bulkiness of their constructions, which slows down the functioning of the corresponding generators, especially during software implementation. The way to overcome the noted difficulties by using an additional secret parameter that determines the appearance of the generator transitions’ function is proposed. Such a modification makes it possible to increase the security of generator (compared to traditional filter generators) against known attacks without increasing the length of its initial state. In particular, a specific version of a generator construction with a complexity function, which is determined with the help of substitutions used in the “Kalyna” encryption scheme, is considered. A lower estimate of the output sequences periods of the proposed generators was obtained. A research of their security to known attacks, in particular, Babbage-Golic balancing attack; an attack associated with a small number of terms in the polynomial representation of the complexity function (which negatively affects the value of the equivalent linear complexity of the output sequences of the generator); a natural correlation attack associated with the specifics of the proposed generator construction scheme; algebraic attacks of the Courtois-Mayer type were also conducted. At the end of the article, it is indicated how to choose the components of the proposed generators to ensure their security at a predetermined level.
References
A.N. Alekseychuk, and О.V. Kurinnyi, Methods of cryptanalysis of stream ciphers. Educational edition. Kyiv, Ukraine: Igor Sikorsky Kyiv Polytechnic Institute, 2023. [Online]. Available: https://ela.kpi.ua/server/api/core/bitstreams/a16bc1db-07a3-4d38-b9e7-a331ef2cc 111/content. Accessed on: Feb. 20, 2024.
T.W. Cusick, and P. Stanica, Cryptographic Boolean Functions and Applications. San Diego, California, USA: Academic Press is an imprint of Elsevier, 2009.
C. Carlet, Boolean Functions for Cryptography and Error Correcting Codes, LAGA, University of Paris 8, France, 2007.
A. Canteaut, and Y. Rotella, “Attacks against Filter Generators Exploiting Monomial Mappings”, Cryptology ePrint Archive, Paper 2016/389. [Online]. Available: https://ia.cr/2016/384. Accessed on: Feb. 23, 2024.
A.N. Alekseychuk, and K.І. Vorobei, “Filter generators with increased resistance against algebraic attacks”, Information Technology and Security, vol. 11, iss. 2 (21), pp. 149-155, July–December 2023, doi: https://doi.org/10.20535/2411-1031.2023.11.2.293748.
S. Babbage, “A space/time tradeoff in exhaustive search attacks on stream ciphers in IEE Conf. Pub. European Convention on Security and Detection, Brighton, 1995, no. 408.
J.Dj. Golić, “Cryptanalysis of alleged A5 stream cipher”, in Proc. Advances in Cryptology – EUROCRYPT’97, Lecture Notes in Computer Science, vol 1233. Springer, Berlin, Heidelberg, 1997, pp. 239-255, doi: https://doi.org/10.1007/3-540-69053-0_17.
C. Carlet, Vectorial Boolean Functions for Cryptography, LAGA, University of Paris 8, France, 2006.
A.N. Alekseychuk, and M.V. Poremskyi, “Lover bounds for the data complexity of correlation attacks on stream ciphers over fields of order ”, Ukrainian Information Security Research Journal, vol. 19, № 2, с. 126-131, 2017, doi: https://doi.org/10.18372/2410-7840.19.11435.
R. Oliynykov et al., “A New Encryption Standard of Ukraine: The Kalyna Block Cipher”, Cryptology ePrint Archive, Paper 2015/650. [Online]. Available: https://ia.cr/2015/650. Accessed on: Mar. 4, 2024.
A.N. Alekseychuk, L.V. Kovalchuk, A.S. Shevtsov, and S.V. Yakovliev, “Cryptographic properties of the new national encryption standard of Ukraine”, Cybernetics and systems analysis, vol. 52, № 3, с. 16-32, 2016. [Online]. Available: http://www.kibernetika.org/volumes/2016/numbers/03/articles/02/2.pdf. Accessed on: Mar. 12, 2024.
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, doi: https://doi.org/10.1007/3-540-39200-9_21.
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, 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, doi: https://doi.org/10.1007/978-3-540-45146-4_11.
L. Bettale, J.-C. Faugere, and L. Perret “Hybrid approach for solving multivariate systems over finite fields”, Journal of Mathematical Cryptology, vol. 3, pp. 177-196, 2009, doi: https://doi.org/10.1515/JMC.2009.009.
Р.V. Oliynykov, I.D. Gorbenko, О.V. Kazymyrov, V.І. Ruzhentsev та I.І. Gorbenko, “Design principles and main properties of the new Ukrainian national standard of block encryption”, Ukrainian Information Security Research Journal, vol. 17, № 2, с. 142-157, 2015, doi: https://doi.org/10.18372/2410-7840.17.8789.
R. Crandall, and C.Pomerance, Prime numbers. A computational perspective, USA: Springer, 2005.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Collection "Information Technology and Security"
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:
- 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.
- 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.
- 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).
