Investigation of heuristic search functions for nonlinear substitutions for symmetric cryptography
DOI:
https://doi.org/10.30837/rt.2021.3.206.05Keywords:
heuristic techniques, informed search, nonlinear substitutions, symmetric cryptographyAbstract
Nonlinear substitutions (S-boxes) are used in most modern symmetric cryptoalgorithms. They are designed to mix input data and play a significant role in ensuring resistance against known cryptanalytic attacks (differential, linear, algebraic and other cryptanalysis methods). However, random generation of nonlinear substitutions with the desired indicators is an extremely difficult mathematical problem. This article explores the heuristic techniques for S-boxes informed search, in particular, discusses various cost functions used in most of the known algorithms (for example, local search, hill climbing, simulated annealing, genetic search, etc.). The aim of the study is to determine the specific parameters of heuristic functions, which, on the one hand, do not reduce the degree of awareness of the search nodes, and on the other hand, do not require significant computational costs. The article examines the influence of individual parameters on the value of the cost function and complexity of its calculation. It also provides specific recommendations for the formation of parameters for heuristic search for S-boxes, which significantly affect the efficiency of generating nonlinear substitutions for symmetric cryptography.
References
Menezes A.J., Oorscho, P.C., van Vanstone S.A., Oorschot P.C. van, Vanstone S.A. Handbook of Applied Cryptography. CRC Press (2018). https://doi.org/10.1201/9780429466335.
Schneier B. Applied cryptography : protocols, algorithms, and source code in C. New York : Wiley (1996).
Technology N.I. of S. and: Advanced Encryption Standard (AES). U.S. Department of Commerce (2001). https://doi.org/10.6028/NIST.FIPS.197.
Kuznetsov A., Gorbenko Y., Andrushkevych A., Belozersev I. Analysis of block symmetric algorithms from international standard of lightweight cryptography ISO/IEC 29192-2 // 2017 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PIC S T). pp. 203–206 (2017). https://doi.org/10.1109/INFOCOMMST.2017.8246380.
Kuznetsov O., Potii O., Perepelitsyn A., Ivanenko D., Poluyanenko N. Lightweight Stream Ciphers for Green IT Engineering // Kharchenko V., Kondratenko Y., and Kacprzyk J. (eds.) Green IT Engineering: Social, Business and Industrial Applications. pp. 113–137. Springer International Publishing, Cham (2019). https://doi.org/10.1007/978-3-030-00253-4_6.
Álvarez-Cubero J. Vector Boolean Functions: applications in symmetric cryptography (2015). https://doi.org/10.13140/RG.2.2.12540.23685.
AlSalami Y., Martin T., Yeun C. Linear and Differential Properties of Randomly Generated DES-Like Substitution Boxes // Park, J.J. (Jong H., Stojmenovic I., Jeong H.Y., and Yi G. (eds.) Computer Science and its Applications. pp. 517–524. Springer, Berlin, Heidelberg (2015). https://doi.org/10.1007/978-3-662-45402-2_77.
Eastlake 3rd D., Schiller J., Crocker S. Randomness Requirements for Security. (2005).
Daemen J., Rijmen V. Specification of Rijndael // Daemen, J. and Rijmen, V. (eds.). The Design of Rijndael: The Advanced Encryption Standard (AES). pp. 31–51. Springer, Berlin, Heidelberg (2020). https://doi.org/10.1007/978-3-662-60769-5_3.
Burnett L.D. Heuristic Optimization of Boolean Functions and Substitution Boxes for Cryptography, https://eprints.qut.edu.au/16023/ (2005).
Clark A.J. Optimisation heuristics for cryptology, https://eprints.qut.edu.au/15777/, (1998).
Clark J.A., Jacob J.L., Stepney S. The design of s-boxes by simulated annealing. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753). pp. 1533-1537 Vol. 2 (2004). https://doi.org/10.1109/CEC.2004.1331078.
Nyberg K. Linear Approximation of Block Ciphers. In: EUROCRYPT (1994). https://doi.org/10.1007/BFb0053460.
Millan W. How to improve the nonlinearity of bijective S-boxes. In: Boyd, C. and Dawson, E. (eds.). Information Security and Privacy. pp. 181–192. Springer, Berlin, Heidelberg (1998). https://doi.org/10.1007/BFb0053732.
Nover H. Algebraic Cryptanalysis of Aes: An Overview.
Bard G.V. Algebraic Cryptanalysis. Springer US, Boston, MA (2009). https://doi.org/10.1007/978-0-387-88757-9.
Ferguson N., Schroeppel R., Whiting D. A Simple Algebraic Representation of Rijndael // Vaudenay S. and Youssef A.M. (eds.). Selected Areas in Cryptography. pp. 103–111. Springer, Berlin, Heidelberg (2001). https://doi.org/10.1007/3-540-45537-X_8.
Courtois N.T., Pieprzyk J. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations // Zheng, Y. (ed.) Advances in Cryptology – ASIACRYPT 2002. pp. 267–287. Springer, Berlin, Heidelberg (2002). https://doi.org/10.1007/3-540-36178-2_17.
Courtois N.T., Bard G.V. Algebraic Cryptanalysis of the Data Encryption Standard // Galbraith, S.D. (ed.). Cryptography and Coding. pp. 152–169. Springer, Berlin, Heidelberg (2007). https://doi.org/10.1007/978-3-540-77272-9_10.
Кuznetsov О.О., Gorbenko Y.І., Bilozertsev І.М., Аndrushkevych А.V., Narizhnyi О.P.: ALGEBRAIC IMMUNITY OF NON-LINEAR BLOCKS OF SYMMETRIC CIPHERS. TRE. 77, (2018). https://doi.org/10.1615/TelecomRadEng.v77.i4.30.
Millan W., Burnett L., Carter G., Clark A., Dawson E. Evolutionary Heuristics for Finding Cryptographically Strong S-Boxes // Varadharajan V. and Mu Y. (eds.) Information and Communication Security. pp. 263–274. Springer, Berlin, Heidelberg (1999). https://doi.org/10.1007/978-3-540-47942-0_22.
Nedjah N., Mourelle L. de M., Mourelle L. de M. Multi-objective Evolutionary Design of Robust Substitution Boxes, https://www.taylorfrancis.com/, last accessed 2020/07/25. https://doi.org/10.1201/9781315366845-7.
Rodinko M., Oliynykov R., Gorbenko Y. Optimization of the High Nonlinear S-Boxes Generation Method. Tatra Mountains Mathematical Publications. 70, 93–105 (2017). https://doi.org/10.1515/tmmp-2017-0020.
Laskari E.C., Meletiou G.C., Vrahatis M.N. Utilizing Evolutionary Computation Methods for the Design of S-Boxes. In: 2006 International Conference on Computational Intelligence and Security. pp. 1299–1302 (2006). https://doi.org/10.1109/ICCIAS.2006.295267.
Edelkamp S., Schroedl S. Heuristic Search Theory and Applications. Morgan Kaufmann, Amsterdam ; Boston (2011).
Informed Search Algorithms in AI – Javatpoint, https://www.javatpoint.com/ai-informed-search-algorithms, last accessed 2021/05/19.
Katz M., Domshlak C. Optimal admissible composition of abstraction heuristics. Artificial Intelligence. 174, 767–798 (2010). https://doi.org/10.1016/j.artint.2010.04.021.
Kapuściński T., Nowicki R.K., Napoli C. Application of Genetic Algorithms in the Construction of Invertible Substitution Boxes // Rutkowski L., Korytkowski M., Scherer R., Tadeusiewicz R., Zadeh L.A., and Zurada J.M. (eds.) Artificial Intelligence and Soft Computing. pp. 380–391. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-39378-0_33.
Picek S., Cupic M., Rotim L. A New Cost Function for Evolution of S-Boxes. Evolutionary Computation. 24, 695–718 (2016). https://doi.org/10.1162/EVCO_a_00191.
Cusick T., Stănică P. Cryptographic Boolean Functions and Applications: Second edition. (2017).
Izbenko Y., Kovtun V., Kuznetsov A. The Design of Boolean Functions by Modified Hill Climbing Method // 2009 Sixth International Conference on Information Technology: New Generations. pp. 356–361. IEEE, Las Vegas, NV, USA (2009). https://doi.org/10.1109/ITNG.2009.102.
Freyre-Echevarría A., Martínez-Díaz I., Pérez C.M.L., Sosa-Gómez G., Rojas O. Evolving Nonlinear S-Boxes With Improved Theoretical Resilience to Power Attacks // IEEE Access. 8, 202728–202737 (2020). https://doi.org/10.1109/ACCESS.2020.3035163.
Freyre Echevarría A., Martínez Díaz I. A new cost function to improve nonlinearity of bijective S-boxes. (2020).
Ivanov G., Nikolov N., Nikova S. Reversed genetic algorithms for generation of bijective s-boxes with good cryptographic properties // Cryptogr. Commun. 8, 247–276 (2016). https://doi.org/10.1007/s12095-015-0170-5.
Freyre-Echevarría A., Alanezi A., Martínez-Díaz I., Ahmad M., Abd El-Latif A.A., Kolivand H., Razaq A. An External Parameter Independent Novel Cost Function for Evolving Bijective Substitution-Boxes // Symmetry. 12, 1896 (2020). https://doi.org/10.3390/sym12111896.
Tesar P. A New Method for Generating High Non-linearity S-Boxes (2010).
Kavut S., Yücel M.D. Improved Cost Function in the Design of Boolean Functions Satisfying Multiple Criteria // Johansson, T. and Maitra, S. (eds.) Progress in Cryptology – INDOCRYPT 2003. pp. 121–134. Springer, Berlin, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24582-7_9.
Carlet C. Vectorial Boolean functions for cryptography. Boolean Models and Methods in Mathematics, Computer Science, and Engineering (2006).
Clark J.A., Jacob J.L., Stepney S. The design of S-boxes by simulated annealing // New Gener Comput. 23, 219–231 (2005). https://doi.org/10.1007/BF03037656.
Nyberg K. Perfect nonlinear S-boxes // Davies, D.W. (ed.) Advances in Cryptology — EUROCRYPT ’91. pp. 378–386. Springer, Berlin, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_32.
Carlet C., Ding C. Nonlinearities of S-boxes. Finite Fields and Their Applications. 13, 121–135 (2007). https://doi.org/10.1016/j.ffa.2005.07.003.
Fuller J., Millan W. Linear Redundancy in S-Boxes // Johansson, T. (ed.) Fast Software Encryption. pp. 74–86. Springer Berlin Heidelberg, Berlin, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39887-5_7.
Clark J.A., Jacob J.L., Stepney S. Searching for cost functions // Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753). pp. 1517-1524 Vol.2 (2004). https://doi.org/10.1109/CEC.2004.1331076.
Ivanov G., Nikolov N., Nikova S. Cryptographically Strong S-Boxes Generated by Modified Immune Algorithm // Pasalic, E. and Knudsen, L.R. (eds.) Cryptography and Information Security in the Balkans. pp. 31–42. Springer International Publishing, Cham (2016). https://doi.org/10.1007/978-3-319-29172-7_3.
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).
