24 September 2021 in Radiotekhnika
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.
24 September 2021 in Radiotekhnika
Nonlinear substitutions (S-boxes) are an important component of modern symmetric cryptography algorithms. They complicate symmetric transformations and introduce nonlinearity into the input-output relationship, which ensures the stability of the algorithms against some cryptanalysis methods. Generation of S-boxes can be done in different ways. However, heuristic techniques are the most promising ones. On the one hand, the generated S-boxes are in the form of random substitutions, which complicates algebraic cryptanalysis. On the other hand, heuristic search allows one to achieve high rates of nonlinearity and δ-uniformity, which complicates linear and differential cryptanalysis. This article studies the simplest local search algorithm for generating S-boxes. To assess the efficiency of the algorithm, the concept of a track of a cost function is introduced in the article. Numerous experiments are carried out, in particular, the influence of the number of internal and external loops of local search on the complexity of generating the target S-box is investigated. The optimal (from the point of view of minimum time consumption) parameters of the local search algorithm for generating S-blocks with a target nonlinearity of 104 and the number of parallel computing threads 30 are substantiated. It is shown that with the selected (optimal) parameters it is possible to reliably form S-blocks with a nonlinearity of 104.