IMPROVEMENT OF THE CONSTRUCTION TECHNIQUE OF SUBSTITUTION BLOCKS FOR SYMMETRIC ENCRYPTION ALGORITHMS

Full Text

Introduction. As it is known, block symmetric transformation matrix; a - shift vector; p = 2 - encryption algorithms are widely used to ensure confidentiality. The growth of computer processing power and the development of cryptanalysis methods require increasing the cryptographic stability of existing algorithms and the development of new ones. Researchers and practitioners are conducting work in this direction. The stability of the encryption algorithm to the most common types of cryptanalysis is determined by the quality of the replacement block, the substitution block. At present, it is already generally accepted that the quality of replacement units is characterized by the values of nonlinearity and avalanche effect [1; 2]. There are two main approaches to the construction of replacement tables. Thus, in [3], a reasonable method was proposed for the step-by-step selection of Boolean functions that are components of the replacement block, which takes into account not only the nonlinearity of each of the functions making up the block, but also the nonlinearity of all possible nontrivial linear combinations. It is also noted that it is possible to simultaneously solve the problem of increasing stability, both to linear and differential cryptanalysis methods, if both nonlinearity and dynamic distance are used as selection criteria [4-6]. The methodology of step-by-step selection was programmatically implemented in relation to the algorithm of GOST 28147-89, currently considered to be very stable, in [1]. The most typical example of the second approach is also the Rijndael algorithm [7], which is considered to be stable, in which the replacement block is completely determined by an irreducible polynomial over the Galois field. In Rijndael the construction of Nyberg is used [8], characteristic of the extended Galois field, 0-1 º 0 - by definition; a, b, x, y - elements of the extended Galois field GF (2k ) , which are considered as decimal numbers, or binary vectors, or polynomials of degree k -1 . Among the quality indicators of S-units, the following are most often distinguished [2]: - maximum of the modules of the matrix elements of the correlation coefficients of the input and output bits; - the number of zeros in the matrix of correlation coefficients; - non-linearity, understood as the distance to the set of affine functions; - algebraic degree of nonlinearity. It is noted that the S-blocks of the Nyberg construction have many practically valuable cryptographic properties, such as high nonlinearity distance, homogeneous minimization of correlation coefficients, and relative simplicity of technical implementation both using the tabular method and using Galois field operations. In the present work, research is continued in these two directions. The study of the set of Boolean functions of four variables. The study of the full set of Boolean functions of four variables was carried out. In addition to cryptographic properties of Boolean functions, such as: balance, possessing a strict avalanche effect, possessing correlation immunity, for the first time the nonlinearity distances of the first and second orders of Boolean functions are simultaneously considered. F which is a reflection in the form of multiplicatively Nonlinearity of r- order nlr ( f ) of Boolean function inverse elements of the Galois field GF (2k ) : f over n is called min d ( f , l) . Nonlinearity deg(l )£r nl1 ( f ) 2 y = x-1 modd[f (z), p], y, x Î GF (2k ) , (1) of Boolean function f is called the distance between f in combination with affine transformation: and a set of affine functions. Nonlinearity nl2 ( f ) of b = A × y + a, a, b Î GF (2k ) , (2) Boolean function f is called the distance between f where f (z) = z8 + z4 + z2 + z +1 - irreducible over the and a set of quadratic functions. For example, a Boolean function of four variables field GF (28 ) polynomial; A - non-degenerate affine with the following truth table: f = {000101001001101} , its nonlinearity of the first order is 3 and the nonlinearity of the second order is 1. The result of the study of the nonlinearity of the first and second orders Boolean functions of four variables is presented in tab. 1. Table 1 Nonlinearity of the first and second orders of Boolean functions Bijective replacement blocks with a maximum correlation coefficient of 0.25 were constructed, using Boolean functions with the following properties: - the first-order nonlinearity distance is 2; - the second-order nonlinearity distance is 2; - balance. Table 2 Nonlinearity distance The maximum modulus of the correlation coefficient of a bijective replacement block Class volume s 1 order 2 order 0 0 0 22 1 1 Doesn’t exist 0 2 2 0.25 1408 3 1 Doesn’t exist 0 4 0 0 304 4 2 0.25 5280 5 1 Doesn’t exist 0 6 0 Doesn’t exist 0 Class volumes Nonlinearity distance Class scopes 1 order 2 order 0 0 22 1 1 0 2 2 0 3 1 0 4 0 200 4 2 0 5 1 0 6 0 0 So, there are a total of 22 linear first-order Boolean functions and 200 second-order linear Boolean functions with these characteristics. Boolean functions with a first order nonlinearity distance equal to 0 will not be considered further, since the replacement blocks obtained from them are unstable to linear cryptanalysis [9]. The remaining 200 Boolean functions are linear functions of the second order, they are not enough to study the nonlinearity of higher orders. Therefore, Boolean functions not linear of the first and second orders were found, and the maximum value of the correlation coefficient of the replacement block when using these functions at absolute value was minimal. The correlation properties of the substitution units were analyzed; Boolean functions with the same nonlinearity properties of the first and second orders were used as component functions. The results of the study are shown in tab. 2, which reflects the maximum correlation coefficient of the replacement unit in absolute value when using certain Boolean functions and the number of such functions. Boolean functions with a first order nonlinearity distance equal to 1, 3, 5, and 6 are not balanced Boolean functions because they cannot be used as component functions of the replacement blocks of the encryption algorithm. Bijective replacement units with a maximum correlation coefficient of 0.25 were worked out, using Boolean functions with the following properties: - the first order nonlinearity distance is 4; - the second order nonlinearity distance is 2; - balance; - have a strict avalanche effect. These Boolean functions do not satisfy the strict avalanche criterion; therefore, replacement blocks obtained from such Boolean functions are less resistant to the differential cryptanalysis method. We distinguish two sets of Boolean functions that are most suitable to construct blocks of replacement. For testing, the AES encryption algorithm was chosen and the following tests were used: series distribution, autocorrelation function, D. Knuth's correlation test: - the first order nonlinearity distance is 4; - the second-order nonlinearity distance is 2; - balance; - have a strict avalanche effect. The power of the recieved set is 5280. The functions of this set can be recommended for use as a component of replacement blocks for the algorithms of GOST 28147- 89, AES and (with minor and obvious changes) of similar algorithms. The set of boolean functions used to build the replacement block is shown below. The test results presented in fig. 1-3, indicate the quality of the constructed replacement unit. F = [0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0] ; F = [0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1] ; F = [0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0] ; F = [1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0] . Fig. 1. Autocorrelation function Рис. 1. Автокорреляционная функция Fig. 2. Schedule distribution of series-triples Рис. 2. График распределения серий троек Fig. 3. The result of D. Knut's correlation test Рис. 3. Результат проверки корреляции Д. Кнута Selection of optimal irreducible polynomials for the implementation of the AES algorithm. One of the techniques for enhancing the durability of the AES algorithm is the construction of replacement blocks based not on one selected irreducible polynomial for all rounds, but on various irreducible polynomials chosen for each round. However, due to unacceptable computational complexity (1010 combinations), first it was decided to conduct a study of compositions, which are a different combination of five specially selected irreducible polynomials in ten rounds. In works [10; 11], nonlinear transformations of the Nyberg construction were studied in detail on the basis of all isomorphic and automorphic representations of the fields. All irreducible polynomials over the fields are presented, and the values of the quality indicators determined by these S-blocks polynomials are calculated. The possibility of choosing one of the many irreducible polynomials is of practical importance. After the publication of papers [5; 6; 10], it became possible to combine the advantages of the GOST and Rijndael approaches. In article [11] the use of irreducible polynomial compositions is analyzed. The composition in this case is the alternation of two irreducible polynomials. Irreducible polynomials, with the most remarkable cryptographic characteristics, were taken from this article. Encryption was carried out using each of the polynomials on 20 texts (the same polynomial was used in each round). As a result, cryptographic characteristics were obtained and a comparative analysis of indicators for each irreducible polynomial was carried out (tab. 3, 4). Polynomials are represented by their decimal equivalents, and filled cells show the most remarkable indicators for each irreducible polynomial. As a result, irreducible polynomials were selected - 283, 319, 333, 355, 357, since they have minimum values of the maximum modulus of the correlation coefficients and the largest number of zero elements of the correlation matrix. Then an encryption procedure was carried out with all possible combinations of selected irreducible polynomials and five open texts. Using the same encryption quality criteria, the maximum of the modules of the matrix coefficients correlation elements and the number of zeros of the elements of the correlation matrix, correlation matrices were constructed and a comparative analysis of indicators for each composition was performed. The selection of the best compositions of irreducible polynomials, surpassing the rest of the compositions in cryptographic characteristics, was done. Table 3 The maximum modulus of the correlation coefficients № text Maximum of the modules of the correlation matrix elements Irreducible polynomials 283 285 299 301 313 319 333 351 355 357 1 0.75 0.75 0.625 0.625 0.625 0.5 0.5 0.625 0.5 0.5 2 0.5 0.5 0.625 0.75 0.625 0.5 0.5 0.5 0.5 0.625 3 0.5 0.875 0.625 0.5 0.625 0.5 0.5 0.5 0.75 0.625 4 0.5 0.5 0.5 0.5 0.625 0.5 0.625 0.625 0.75 0.5 5 0.625 0.625 0.625 0.75 0.5 0.75 0.625 0.625 0.625 0.5 6 0.75 0.75 0.625 0.625 0.5 0.5 0.5 0.5 0.625 0.5 7 0.5 0.625 0.75 0.625 0.625 0.75 0.625 0.625 0.5 0.625 8 0.625 0.625 0.5 0.5 0.5 0.625 0.625 0.75 0.625 0.5 9 0.5 0.625 0.625 0.5 0.625 0.625 0.5 0.625 0.5 0.5 10 0.5 0.625 0.625 0.625 0.625 0.625 0.625 0.75 0.75 0.75 11 0.5 0.625 0.625 0.75 0.375 0.5 0.625 0.625 0.5 0.5 12 0.75 0.5 0.625 0.625 0.625 0.5 0.5 0.5 0.625 0.625 13 0.5 0.5 0.75 0.625 0.75 0.5 0.625 0.625 0.5 0.5 14 0.625 0.75 0.625 0.625 0.5 0.625 0.625 0.625 0.625 0.5 15 0.625 0.5 0.625 0.625 0.625 0.875 0.75 0.625 0.625 0.5 16 0.625 0.5 0.75 0.625 0.5 0.5 0.625 0.625 0.625 0.625 17 0.5 0.625 0.75 0.625 0.75 0.625 0.625 0.5 0.625 0.625 18 0.625 0.75 0.625 0.625 0.625 0.5 0.75 0.5 0.5 0.75 19 0.625 0.625 0.625 0.5 0.5 0.5 0.5 0.625 0.375 0.5 20 0.625 0.625 0.625 0.625 0.5 0.75 0.5 0.5 0.5 0.5 Table 4 The number of zeroes of the correlation matrix elements № text The number of zeros of the correlation matrix Irreducible polynomials 283 285 299 301 313 319 333 351 355 357 1 9 13 10 15 9 15 10 9 9 14 2 16 11 9 12 16 19 18 18 15 11 3 10 9 12 10 13 15 14 15 13 13 4 13 11 12 7 12 16 7 16 18 14 5 19 19 11 11 7 19 8 8 3 21 6 8 14 11 11 16 15 9 15 11 11 7 10 20 16 12 7 11 23 4 14 12 8 12 15 19 13 11 9 9 13 16 7 9 9 15 8 9 13 14 15 14 12 14 10 12 13 14 14 17 12 19 17 13 11 11 21 11 12 10 12 12 15 13 11 14 12 20 13 13 21 10 9 6 18 11 6 13 10 9 11 13 19 18 9 17 14 12 14 7 9 10 21 19 17 10 13 13 7 15 8 10 9 17 8 19 10 7 9 4 16 16 14 11 15 13 15 9 13 13 16 17 14 12 6 13 10 13 13 13 10 12 18 16 11 14 18 9 9 13 12 11 10 19 16 13 7 10 17 10 14 13 13 17 20 10 17 10 16 12 9 9 13 15 13 The composition here is a combination of five polynomials in ten rounds. For example, compositions 333, 283, 283, 319, 357, 283, 333, 355, 283, 333 (or 2001402302). Experiments have shown that the use of the listed irreducible polynomials in Rijndael encryption provides the best cryptographic strength indicators in comparison with others. Examples of the best and the worst compositions on two criteria are presented respectively in tab. 5, 6. Table 6 Maximum correlation coefficient Number of ze- roes Composition 0.625 7 32000000003 0.75 9 32000000004 0.625 16 32000000140 0.875 11 32112010432 0.625 11 32112010433 0.75 12 32000000143 0.875 16 32000000222 0.625 13 32201110444 0.75 11 32201111000 0.875 14 32000001120 Examples of the worst compositions on the basis of two criteria Examples of the best compositions on the basis of two criteria Table 5 Maximum correlation coefficient Number of ze- roes Composition 0.375 36 3104034331 0.375 34 3313210233 0.375 34 4142344410 0.375 34 4303234230 0.375 33 4202203343 0.375 33 4324342340 0.375 32 333434303 0.375 32 2422044342 0.375 32 4443342101 0.25 30 3241333141 The data in the tab. 5 are not fully presented, since the output of all data would take several hundred pages, and their information content would tend to zero. The program, which is engaged in the calculation of the above data, can be found by clicking the following link [12]. The compositions presented in tab. 5, have high rates of cryptographic characteristics. The results of the study allow choosing the optimal set of polynomials with the best cryptographic properties, the combination of which gives a high rating of the quality of encryption according to the AES scheme, which increases the cryptographic strength of the AES algorithm. The developed method allows selecting encryption op- tions in such a way that it can compete not only with the standard AES encryption algorithm, but also with other modern block encryption algorithms. Conclusion. The results of the study of two approaches showed a good quality of substitution units construction, which ensures the best cryptographic performance indicators, both for the Rijndael algorithm and for GOST. On the basis of the obtained results, it is necessary to further explore possible options of increasing the strength of block encryption algorithms. It is interesting to compare the obtained results with their ternary counterparts, see [13].

About the authors

A. S. Merinov

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

K. A. Nesterov

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

O. N. Zhdanov

Reshetnev Siberian State University of Science and Technology

Email: onzhdanov@mail.ru
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

References

Supplementary files