The development of modern cryptanalysis methods, in particular, with the use of many-valued logic functions, leads to the need for a more detailed research of the correlation properties of Sboxes of modern cryptographic algorithms. In this paper, we introduce indicators for the maximum and integral deviation of a many-valued logic functions on the basis of criterion for the independence of its output from the input variables. These indicators are a convenient tool for comparative analysis of the correlation properties of S-boxes of various lengths when they are represented using the many-valued logic functions with different bases q. The research and comparative analysis of the S-boxes of the AES and Kalyna cryptographic algorithms was performed, which showed a general tendency of a decreasing of their correlation properties with an increase in the value of representation base q, and also made it possible to establish that for all values of the representation base q, the correlation properties of the Kalyna cryptographic algorithm S-box are weaker than the correlation properties of the AES cryptographic algorithm S-box.
and problem
Block symmetric ciphers are one of the most important components of modern cybersecurity systems, the task of which is to make it impossible to access transmitted or stored information without knowing the key. Nevertheless, the rapid increase in the computing power of modern information systems, development of the mathematical methods of cryptanalysis, as well as the prospects for the creation of quantum computers lead to the need for continuous improvement of the structure and components of modern block symmetric ciphers.
The issues of improving modern cryptographic algorithms are inextricably linked with the theory of estimation of their cryptographic quality. The modern theory of estimation of the cryptographic quality of block symmetric ciphers involves the representation of their constituent parts (first of all, S-boxes) using component Boolean functions [1, 2]. Further, cryptographic quality criteria are applied to the obtained Boolean functions, each of which reflects the ability of the Boolean function to resist one or another cryptanalysis attack, as well as to provide a sufficient level of diffusion and confusion [3].
However, publications in the field of cryptography [4] show an increasing need to research all possible representations of S-boxes, in particular, using functions of many-valued logic. Research [5] is devoted to the method of estimation of the nonlinearity, as well as avalanche characteristics of S-boxes of modern cryptographic algorithms, represented by functions of many-valued logic.
Nevertheless, the results of the analysis of the correspondence of the constructions of modern cryptographic algorithms to the criterion of correlation immunity of functions of many-valued logic are not presented in the open sources.
The purpose of this paper is to perform a comparative analysis of the correlation immunity of the cryptographic algorithms AES (USA) and Kalyna (Ukraine) when they are represented by the many-valued logic functions. 2. Correlation immunity of manyvalued logic functions
The definition of the correlation immunity of Boolean functions is widely known [6], which can be specified through the definition of a subfunction of a Boolean function.
Definition 1 [6]. A Boolean function f (x) , x Vk , is called as correlation-immune of order m , 1 m k if its output y f (x1k ) and any set of m its input variables are statistically independent.
Definition 2 [6]. A subfunction of a Boolean function f (x) , x Vk , is a function f obtained by substitution in f constants "0" or "1" instead of a part of variables. If we substitute constants i 1 , , i s in the function f instead of variables xi , , xi , respectively, then the resulting 1 s subfunction is denoted f i1 ,,i s . If a constant is xi1 ,,xis not substituted for a variable xi , then xi is called as a free variable.
For example, let a Boolean function f (x1, x2 , x3) be given, then its subfunctions will be f (x1, x2 ,0) , f (x1, x2 ,1) , f (x1,0,0) , f (x1,0,1) , etc.
Definition 3 [6]. Boolean function f (x) , x Vk , is called correlation-immune of order m , 1 m k if weight is equal to wt( f ) wt( f ) / 2m , for any of its subfunctions f of k m variables.
In [7], the theoretical foundations for estimating the correlation immunity of functions of many-valued logic were developed, while in [8], definitions of the independence of the output of a 3-function from its input variables, as well as the definition of the correlation immunity of a 3function were introduced. The basis of these definitions is the definition of the imbalance of functions of many-valued logic.
Consider an arbitrary sequence over the alphabet {0,1,..., q 1}
fi {0,1,..., q 1}, i 0,1,..., N 1. (
(
For a given sequence (
Definition 4. An imbalance of a sequence f
is the absolute value of the sum of element-wise
products of vector K elements by the
corresponding elements of the exponential
alphabet {z0 , z1,..., zq1}
( f ) K0 z0 K1z1 ... Kq1zq1 .
(
The definitions of the independence of the output of a 3-function from its input variables, as well as the definition of the correlation immunity of a 3-function, introduced in [8] using Definition 4 of the imbalance of a many-valued logic function can be generalized to the case of qfunctions for an arbitrary value of q.
Definition 5 [8]. It is said that the output of a q-function f (x) does not depend on the group of its input variables {xi} , i 1,..., m if, when any constants of these substituting i 1 , , i s {0,1,...q 1} instead variables, the imbalance of the subfunctions obtained in this way is ( f ) qmf .
Note, however, that the correlation immunity of component Boolean functions, as well as component many-valued logic functions, is a rather stringent requirement that is not met for most S-boxes used in practice. This circumstance poses the task of developing a mathematical apparatus for performing a comparative analysis of the degree of correspondence of S-boxes to the correlation immunity criterion of component qfunctions.
The Definition 5 gives us the possibility to estimate the degree of deviation of the manyvalued logic functions and S-boxes from the criterion of correlation immunity by introducing two basic indicators of cryptographic quality: the maximum and integral deviation from the criterion of independence of the output of manyvalued logic functions from their input.
Let's consider these indicators on a specific example, and then apply them to specific cryptographic algorithms.
Let an S-box of length N 16 be given, which can be represented in the form of four component Boolean functions, as well as in the form of two component 4-functions.
S 12 0 2141311 3 5 1 7 15 9 10 6 4 8 f20 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 f21 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 f22 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 f23 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 f40 0 0 2 2 1 3 3 1 1 3 3 1 2 2 0 0 f41 3 0 0 3 3 2 0 1 0 1 3 2 2 1 1 2
We begin our research with the first
component Boolean function f20 , for which, in
accordance with Definition 3, we find all its
subfunctions of three variables
wt( f20 (x1, x2 , x3 , 0) [00111100]) 4;
(
In a similar way, we can find subfunctions for
the component function f41 of the S-box (
Since the weight of each of the subfunctions
(
Consider the S-box (
( f41(3, x2 ) [2112]) 8.
Analysis of expressions (
To solve the problem of quantitative estimating of the compliance of the S-box with the criterion of correlation immunity, we introduce the indicators of the maximum and integral deviation from the compliance with the criterion of the independence of the S-box output from its input variables.
Definition 6. The maximum deviation of an Sbox from the criterion of independence of the output from the input variables when it is represented by component q-functions is the maximum among all deviations from the criterion of independence of the output from the input variables of its component q-functions.
In our case, the S-box (
In the case of representation by component 4functions, the maximum deviation from the criterion for the independence of the output from the input variables is max f4i 8 2.8284 .
It is obvious that the maximum possible value
of the maximum deviation of the q-function from
the criterion of the independence of the output
from the input variables is the maximum value of
the imbalance of the q-function of k 1 variables,
that is max{max fqi} N q . In the case of
representing an S-box of length N 16 using
component 4-functions the maximum value of the
maximum deviation from the criterion of
independence of the output from the input
variables would reach max{max f4i} 16 4 4 .
I.e. the maximum deviation from the criterion of
independence of the output from the input
variables among the component functions for our
S-box (
Definition 7. The integral deviation of the Sbox from the criterion of independence of the output from the input variables when it is represented by component q-functions is the total value of all deviations from the criterion of independence of the output from the input variables of its component q-functions
k
fqi fqi . (
i0
In our example, in view of the compliance of
the S-box (
In the case of representation using component
4-functions, and using (
It is obvious that the maximum value of the
integral deviation of the q-function from the
criterion for the independence of the output from
the input variables is
max{fqi} qk1z ,
(
In our case, the maximum value of the integral deviation of the q-function from the criterion of the independence of the output from the input variables is max{f4i} 4 8 32 , i.e. the 4function f40 is characterized by the integral deviation from the criterion of the independence of the output from the input variables equal to 25% of the maximum value, while for the component function f41 this indicator is 42.68%.
Note also that since the S-box (
Note also that for the cryptographic algorithms AES and Kalyna which are researched in this paper, the length of the S-boxes used is N 256 , respectively, the maximum value of the maximum deviation of the Boolean function from the criterion for the independence of the output from the input variables is max{max f2i} 256 2 128, while the maximum value of the maximum deviation of the 4functions from the criterion for the independence of the output from the input variables is max{max f4i} 256 4 64 .
In this case, the maximum value of the maximum deviation of the 16-function from the criterion for the independence of the output from the input variables is max{max f16i} 256 16 16.
The maximum value of the integral deviation of the Boolean function from the criterion for the independence of the output from the input variables is max{f2i} 128 16 2048 , while this indicator for the entire S-box will be max{S2} 8 2048=16384 .
The maximum value of the integral deviation of the 4-function from the criterion for the independence of the output from the input variables is max{f4i} 64 16 1024 , while this indicator for the entire S-box will be max{S4} 4 1024=4096 .
The maximum value of the integral deviation of the 16-function from the criterion for the independence of the output from the input variables is max{f16i} 16 32 512 , while this indicator for the entire S-box will be max{S16} 2 512=1024 . 3. Indicators of deviation from the criterion of correlation immunity of S-boxes of modern ciphers
In this paper, we research the deviation from the criterion of correlation immunity of S-boxes of cryptographic algorithms AES (USA) [9], as well as Kalyna (Ukraine) [10].
The cryptographic algorithm AES is based on
a Nyberg construction S-box [11], which is
defined using a mapping in the form of
multiplicatively inverse elements of the Galois
field GF (2k )
y x1 modd[f (z), p],
y, x GF (2k ) ,
(
b A y a, a,b GF (2k ) , (
A is a non-singular affine transformation matrix, a is a the shift vector, p 2 is the characteristic of the extended Galois field, k 8 , and 01 0 ,
a,b, x, y are the elements of the extended Galois field GF (2k ) , which are considered as decimal numbers, or binary vectors, or polynomials of degree k 1.
In this paper, we consider the AES S-box of
the Nyberg construction without using the affine
transformation (
The indicators of the maximum and integral deviation from the criterion of independence of the output vectors from the input variables for the AES cryptographic algorithm are presented in Table 1.
Analysis of the data presented in Table 1 shows a tendency towards an increase in both the maximum and integral deviation from the criterion of independence of the output vectors from the input variables of the AES cipher with an increase in the representation base q. At the same time, the use of an affine transformation insignificantly reduces the growth of this value (except for the maximum deviation from the criterion of independence of the output vectors from the input variables of 4-functions), but the deviation even in this case is quite strong.
Ukraine has developed its own block symmetric cryptographic algorithm Kalyna, which was adopted as the standard DSTU 7624: 2014 “Information technologies. Cryptographic data security. Symmetric block transformation algorithm” [12].
Today, there are several options for the implementation of the Kalyna cryptographic algorithm, which differ in the key length: Kalyna128, Kalyna-256 and Kalyna-512. However, they all use the same cryptographic primitives on which the cryptographic quality of the cryptographic algorithm relies.
The Kalyna block symmetric cipher is characterized by the use of an SP-network and thus has an AES-like structure. The basis of the Kalyna cryptographic transformation is its nonlinear elements, which are four permutations specified in [12].
The indicators of the maximum and integral deviations from the criterion for the independence of the output vectors from the input variables for the permutations 0 , 1, 2 , 3 are presented in Table 2.
Note at the same time that in view of the fact that the overall quality of the cipher is determined by the weakest of its constituent elements [1], in order to demonstrate the overall quality of the Kalyna cryptographic algorithm, the smallest values of the maximum and integral deviations from the criterion for independence of the output from the input vectors are selected in the last row of Table 2.
Analysis of the data presented in Table 2 shows a steady increase in both the maximum and integral deviation from the criterion for independence of the output vectors from the input variables of the S-boxes of the Kalyna cipher with an increase in the representation base q. For the convenience of comparing the correlation properties of the AES cipher S-box (with affine transformation) and the Kalyna cipher S-box the Fig. 1 shows the graphs of changes in the maximum (a) and integral (b) deviation from the criterion of independence of the output vectors from the input variables for these cryptographic algorithms.
Analysis of the data presented in Fig. 1 shows that both the maximum and integral deviation of the S-boxes of the AES and Kalyna cryptographic algorithms from the criterion for the independence of the output vectors from the input variables show an increase with an increase in the representation base q. At the same time, the Kalyna cryptographic algorithm has a significantly higher level of the maximum and integral deviation from the criterion for the independence of the output vectors from the input variables. 4. Conclusions
1. The development of cryptanalysis methods necessitates a more detailed research of the structure of modern cryptographic algorithms, not only when they are represented by Boolean functions, but also when they are represented by functions of many-valued logic. In this paper, on the basis of the criterion for the independence of the output of many-valued logic functions from their input variables, the indicators of the maximum and integral deviation from the criterion for the independence of the output of many-valued logic functions from their input variables are introduced. For these indicators, the maximum possible values for the given N and q are obtained. These indicators are applicable to individual functions of many-valued logic, as well as to S-boxes of various lengths with all their possible representations, and allow a comparative analysis of the correlation properties of S-boxes of modern cryptographic algorithms when they are represented by functions of many-valued logic.
2. The analysis of S-boxes of modern cryptographic algorithms AES and Kalyna was performed, which showed that S-boxes of both ciphers demonstrate a decrease in correlation properties with an increase in the representation base q. At the same time, for all values of the representation base q, the correlation properties of the Kalyna cryptographic algorithm are weaker than the correlation properties of the S-box of the AES cryptographic algorithm.
3. Research shows the possibilities for further improvement of the nonlinear transformation of the Ukrainian cryptographic algorithm Kalyna due to its representation by functions of many-valued logic, in conjunction with the fact that the DSTU 7624: 2014 standard allows the use of other, more advanced nonlinear elements, increases the relevance of the development of new cryptographic constructions, which are optimal from the point of view of criteria for the cryptographic quality of functions of many-valued logic.