Study of a new cost function for generating random substitutions of symmetric ciphers
DOI:
https://doi.org/10.30837/rt.2022.2.209.07Keywords:
symmetric cryptography, cost function, generation methods, nonlinearity, Walsh – Hadamard transform, S-boxAbstract
Cryptographic transformations with a secret key play an essential role in providing information and cyber security. Block and stream symmetric ciphers are used in various applications both as a separate cryptographic protection mechanism and as part of other applications (pseudo-random sequence generators, hashing algorithms, electronic signature protocols, etc.). Therefore, the design and study of individual components of symmetric ciphers is a relevant and important scientific task. In this paper we consider and investigates iterative algorithms for generating non-linear substitutions (substitutions, S-boxes), which are used in modern block and stream encryption algorithms with a symmetric key. Cryptographic resistance of symmetric ciphers to statistical, differential, linear and other methods of cryptanalysis is provided by the properties of substitutions. In addition, S-boxes must be random from the point of view of the possibility to use algebraic cryptanalysis. Therefore, the task of quickly generating random S-boxes with the desired cryptographic properties is an urgent, but extremely difficult task. For example, the best known generation algorithm requires more than 65 thousand iterations to find a random bijective 8-bit substitution with a non-linearity of 104. In this paper, we study an iterative algorithm for generating substitutions for hill climbing with different cost functions and propose a new cost function, the use of which can significantly reduce the number of search iterations. In particular, the search for a bijective S-box with nonlinearity 104 requires less than 50 thousand iterations.
References
Menezes A.J. et al. Handbook of Applied Cryptography. CRC Press, 2018.
Delfs H., Knebl H. Introduction to Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015.
Kuznetsov A.A. et al. Stream Ciphers in Modern Real-time IT Systems: Analysis, Design and Comparative Studies. Springer International Publishing, 2022. XVI. 611 p.
Daemen J., Rijmen V. Specification of Rijndael // The Design of Rijndael: The Advanced Encryption Standard (AES) / ed. Daemen J., Rijmen V. Berlin, Heidelberg: Springer, 2020. P. 31–51.
Daemen J., Rijmen V. AES proposal: rijndael. 1999.
Shannon C.E. Communication theory of secrecy systems // The Bell System Technical Journal. 1949. Vol. 28, № 4. P. 656–715.
Freyre Echevarría A. Evolución híbrida de s-cajas no lineales resistentes a ataques de potencia. 2020.
Gorbenko I. et al. Random S-Boxes Generation Methods for Symmetric Cryptography // 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON). 2019. P. 947–950.
Moskovchenko I. et al. HEURISTIC METHODS FOR THE DESIGN OF CRYPTOGRAPHIC BOOLEAN FUNCTIONS: 3 // International Journal of Computing. 2019. Vol. 18, № 3. P. 265–277.
Cusick T., Stănică P. Cryptographic Boolean Functions and Applications: Second edition // Cryptographic Boolean Functions and Applications: Second Edition. 2017. P. 2751 p.
Bard G.V. Algebraic Cryptanalysis. Boston, MA: Springer US, 2009.
Courtois N.T., Bard G.V. Algebraic Cryptanalysis of the Data Encryption Standard // Cryptography and Coding / ed. Galbraith S.D. Berlin, Heidelberg: Springer, 2007. P. 152–169.
Courtois N.T., Pieprzyk J. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations // Advances in Cryptology — ASIACRYPT 2002 / ed. Zheng Y. Berlin, Heidelberg: Springer, 2002. P. 267–287.
Technology N.I. of S. and. Advanced Encryption Standard (AES): Federal Information Processing Standard (FIPS) 197. U.S. Department of Commerce, 2001.
Daemen J., Rijmen V. Rijndael/AES // Encyclopedia of Cryptography and Security / ed. van Tilborg H.C.A. Boston, MA: Springer US, 2005. P. 520–524.
Burnett L.D. Heuristic Optimization of Boolean Functions and Substitution Boxes for Cryptography: phd. Queensland University of Technology, 2005.
Ivanov G., Nikolov N., Nikova S. Cryptographically Strong S-Boxes Generated by Modified Immune Algorithm // Cryptography and Information Security in the Balkans / ed. Pasalic E., Knudsen L.R. Cham: Springer International Publishing, 2016. P. 31–42.
Freyre-Echevarría A. et al. An External Parameter Independent Novel Cost Function for Evolving Bijective Substitution-Boxes: 11 // Symmetry. Multidisciplinary Digital Publishing Institute. 2020. Vol. 12, № 11. P. 1896.
Freyre-Echevarría A. et al. Evolving Nonlinear S-Boxes With Improved Theoretical Resilience to Power Attacks // IEEE Access. 2020. Vol. 8. P. 202728–202737.
Kuznetsov A. et al. Optimizing the Local Search Algorithm for Generating S-Boxes // 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology (PIC S T). 2021. P. 458–464.
Kuznetsov A. et al. WHS Cost Function for Generating S-boxes // 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology (PIC S T). 2021. P. 434–438.
Ivanov G., Nikolov N., Nikova S. Reversed genetic algorithms for generation of bijective s-boxes with good cryptographic properties // Cryptogr. Commun. 2016. Vol. 8, № 2. P. 247–276.
Kapuściński T., Nowicki R.K., Napoli C. Application of Genetic Algorithms in the Construction of Invertible Substitution Boxes // Artificial Intelligence and Soft Computing / ed. Rutkowski L. et al. Cham: Springer International Publishing, 2016. P. 380–391.
Mariot L., Leporati A. Heuristic Search by Particle Swarm Optimization of Boolean Functions for Cryptographic Applications // Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery. 2015. P. 1425–1426.
Freyre Echevarría A., Martínez Díaz I. A new cost function to improve nonlinearity of bijective S-boxes. 2020.
Clark J.A., Jacob J.L., Stepney S. The design of S-boxes by simulated annealing // New Gener Comput. 2005. Vol. 23, № 3. P. 219–231.
McLaughlin J. Applications of search techniques to cryptanalysis and the construction of cipher components: phd. University of York, 2012.
Wang J. et al. Construction Method and Performance Analysis of Chaotic S-Box Based on a Memorable Simulated Annealing Algorithm: 12 // Symmetry. Multidisciplinary Digital Publishing Institute, 2020. Vol. 12, № 12. P. 2115.
Picek S., Cupic M., Rotim L. A New Cost Function for Evolution of S-Boxes // Evolutionary Computation. 2016. Vol. 24, № 4. P. 695–718.
Carlet C. Vectorial Boolean functions for cryptography // Boolean Models and Methods in Mathematics, Computer Science, and Engineering. 2006.
Tesar P. A New Method for Generating High Non-linearity S-Boxes. Společnost pro radioelektronické inženýrství, 2010.
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).
