-

Nonlinear Properties of Rijndael S-boxes Represented by the Many-Valued Logic Functions

i V

i  VV

VV

ii VV

ii 

0 0 Odessa National Polytechnic University , Odessa , Ukraine

S-boxes of the Nyberg construction are one of the most important cryptographic primitives, which are used in the AES cryptographic algorithm and largely determines its effectiveness. Numerous researches have confirmed the high cryptographic quality of their component Boolean functions. Nevertheless, the cryptanalyst is not constrained in the methods used and can also use the mathematical apparatus of the functions of many-valued logic for cryptanalysis. This work is devoted to the research of the nonlinear properties of S-boxes of the Nyberg construction, presented in the form of component 4-functions and 16-functions. The paper proposes a method for calculating the nonlinearity value of 16-functions, for which the formula of the recursive construction of hexadecimal Vilenkin-Chrestenson matrices of arbitrary order is discovered. The performed researches made it possible to establish that the nonlinearity values of component 4-functions and 16-functions of S-boxes of the Nyberg construction is not stable and depends on the type of irreducible polynomial used to construct them. In the paper we present the irreducible polynomial for which the nonlinearity values of component 4-functions and 16-functions is evenly high. At the same time, it was established that the same polynomial also provides the uniform minimization of the correlation coefficients between output and input vectors of the S-box. The specified polynomial can be recommended for the practical use.

cryptography logic function Nyberg construction nonlinearity S-box

Introduction and problem statement Block symmetric cryptographic algorithms are a very important component of modern information security systems. The main component of block symmetric cryptographic algorithms, on which the overall quality of the cryptographic transform depends, is a cryptographic S-box. Today, there are many constructive methods for the synthesis of high-quality S-boxes. As one of the most effective methods for S-boxes design the Nyberg construction can be mentioned [1]. S-boxes of this construction are used in the Rijndael cryptographic algorithm, which is approved as the AES encryption standard [2].

S-boxes of the Nyberg construction are determined by using a mapping in the form of multiplicatively inverse elements of the Galois field GF(2k )

y  x1 modd[f (z), p], y, x GF(2k ) , which is in general combined with an affine transform b  A y  a, a,b GF(2k ) , ( 1 ) ( 2 ) ( 3 ) where as f (z) the standard AES irreducible over the field GF ( 2 ) polynomial is used f (z)  z8  z4  z3  z 1 ; A is the nonsingular affine transform matrix; a is the shift vector; p  2 is the characteristic of the extended Galois field, 01  0 is taken a-priory; a,b, x, y are the elements of the extended Galois field, that can be considered as decimal numbers, or binary vectors, or polynomials of degree k 1 .

A detailed research of the cryptographic properties of Nyberg construction S-boxes of length N  256 was performed in [3], where it was established that the cryptographic quality of the S-box depends on the type of irreducible polynomial used. The number of irreducible polynomials is defined as

Wk  1    d   p(k /d ) , k d

d k where d are the divisors of the k ,  (d ) is the Mobius function, the notation d k means that d divides k .

Moreover, to determine the cryptographic quality of S-boxes, the generally accepted approach is to represent the S-box using the mathematical apparatus of Boolean algebra: the original S-box is decomposed into component Boolean functions, to each of which a generally accepted set of criteria for cryptographic quality is used. In this set of criteria, the criterion of high nonlinearity is adopted as the most important criterion [4].

Nevertheless, when describing cryptographic algorithms, a cryptanalyst is not constrained in the facilities used, in particular, the mathematical apparatus of functions of many-valued logic can be used [5]. Today in the literature there are no researches of the nonlinear properties of S-boxes of the Nyberg construction, presented using the functions of many-valued logic.

The purpose of this work is to research the nonlinear properties of the component many-valued logic functions of Nyberg construction S-boxes of length N  256 based on the full set of irreducible polynomials.

Possible representations of AES S-boxes by functions of many-valued logic We introduce the definition of the S-box which is necessary for further research and consider the possible forms of its representation.

Definition 1. S-box is a substitution of the form ( 4 ) ( 5 )  0 y0

N 1 , yN 1 where the first row is a sequence of numbers from 0 to N 1, the second row is a sequence {yi} consisting of elements of the first row, rearranged according to the law specified by the designers of the S-box. The second row of the substitution ( 4 ) is called as the coding Q-sequence and denoted Q  {yi}, i  0,1,..., N 1.

Each coding Q-sequence can be unambiguously represented in the form of k  logq N its component q-functions, where q belongs to the set of such values that the length N of the S-box can be represented in the form N  qk .

Obviously, the Nyberg S-boxes used in the AES cryptoalgorithm can be uniquely represented using component Boolean functions (2-functions), using component 4functions, and also using component 16-functions. Moreover, each of these functions completely determines the structure and cryptographic quality of the S-box in the sense of the corresponding logic.

For example, consider the S-box of the Nyberg construction ( 1 ) based on a polynomial f (z)  28310  z8  z4  z3  z 1 used in the AES cipher in the form of its coding Q-sequence the first of which is given as an example Ffouri , i  1, 2,..., 4 , the first of which has the form

Fhex1  {01D6B2B18F90015744AB9B0F8FDCF0E2AEA15D891A85 0422C52C3962250F7B99DE77D15974B34599DC5AC47F8E201C17 6EF39663471F331B977505AC60061A123EF063E6BE597294EA2D8 A42A4F89C9ABCE3F858682AE722C0FF15815E6DDC67B8F3A44F 9734BCC6A7E35B2A4B45D80B1D6B6EFD8E73D0E3B384863CDC

D0DA1C}. 3

Method for determining the nonlinearity value of manyvalued logic functions The most important characteristic of the cryptographic quality of S-boxes is its nonlinearity distance. The binary case is classical, in which the nonlinearity distance is defined as the minimum Hamming distance between Boolean function f and all codewords of an affine code [6]

2N f  min(dist( f , A j )), j  0,1,..., 2k1 1 .

Definition 2. For an arbitrary positive integer k , an affine code A(N, k) of length N  2k is defined as the set of all rows of those Boolean functions whose algebraic degree of nonlinearity does not exceed 1, that is A(N, k)  A f | f  Fk , deg f  1 [7].

In turn, the nonlinearity distance of the entire S-box is determined by the worst from its component Boolean functions, i.e. as 2NS  min{2NF }, i  1, 2,..., k2 .

i ( 10 )

Moreover, since the set of codewords of the non-inverse part of the affine code coincides with the rows of the Walsh-Hadamard matrix, the nonlinearity distance of the component Boolean functions can also be found in the domain of the WalshHadamard transform coefficients in accordance with the following formula ( 6 ) ( 7 ) ( 8 ) ( 9 )

max W f (v) , 2 vZ2k

A2k 

 ,  A2k  where Wf (v)  f  AN is the vector of coefficients of the Walsh-Hadamard transform of the component Boolean function f , AN is the Walsh-Hadamard matrix, which is constructed in accordance with the following recurrence rule V4k  V4k1  V4k V k  4 V4k

V4k V4k V4k  V4k 1 V4k  2 V4k  3

 , V4k  2 V4k V4k  3 V4k  2

V4k  2

 V4k 1 where the summation is performed modulo 4, and ( 12 ) ( 13 ) ( 14 ) where A1  1 .

Applying formulas ( 9 ) or ( 11 ) to the first component Boolean function ( 6 ) of the Sbox ( 5 ), it is easy to verify that its nonlinearity distance is equal to NFbin1  112 , while the nonlinearity distances of all component Boolean functions of the S-box ( 5 ) are equal to NFbini  {112,112,112,112,112,112,112,112}, i  1, 2,...,8 .

Nevertheless, formulas ( 9 ) and ( 11 ) are not applicable for the estimation of the nonlinearity value of functions of many-valued logic, in particular, for the 4-functions and 16-functions that we are researching.

Estimation of the nonlinearity value of 4-functions is an important problem, which was solved in [8, 11]. The proposed method for estimating the nonlinearity value of 4functions is based on finding the coefficients of the Vilenkin-Chrestenson transform  f  f V of the investigated 4-function f , where the investigated 4-function f and the Vilenkin-Chrestenson matrix V are presented in exponential form using the unique transformation

 j 2 0 {0,1, 2, 3}  e 4  

j 2 1 e 4

j 2 2 j 2 3  e 4 e 4  .   The Vilenkin-Chrestenson matrix is constructed according to the following recurrence rule (15) (16)

max W f , q  2.

Based on the Vilenkin-Chrestenson transform coefficients, a generalized formula for estimation of the nonlinearity value of q-valued logic functions is introduced in [8]

Same to the binary case, the nonlinearity value of the S-box is determined by its worst component q-function, respectively, qNS  min{qNF }, i  1, 2,..., kq . i

Using expression ( 14 ), it is easy to construct the Vilenkin-Chrestenson matrix over the alphabet {0,1, 2, 3} of order N  256 , with help of which we can find the coefficients of the Vilenkin-Chrestenson transform of sequence ( 7 ). Further, using expression (16), it is not difficult to determine that the nonlinearity value of the 4-function ( 7 ) is equal to 4NF  219.5034 . The nonlinearity value of the remaining component 1 4-functions are equal to

4NFfouri  {219.5034 221.9412 216.5538 219.2849} , i  1, 2, 3, 4 . Accordingly, the nonlinearity value of the entire S-box ( 5 ) is equal to 4NS  216.5538 . Note that, in contrast to the binary case, the nonlinearity values of the component 4-functions of S-boxes of the Nyberg construction are different for different component 4-functions [12-13].

Although the general formula for the nonlinearity value for an arbitrary q was introduced in [8], however, a specific mechanism for finding the nonlinearity value of 16-functions was not shown, and in order to evaluate the nonlinearity values of the component 16-functions of the Nyberg construction S-boxes, it is necessary to develop recurrence algorithm for constructing Vilenkin-Chrestenson matrices over the alphabet  0 e 216 0  j

8 e j 216 8

1 e j 216 1

9 e j 216 9

2 e j 216 2

A e j 216 10

3 e j 216 3

4 e j 216 4

5 e j 216 5

6 e j 216 6

7 e j 216 7

B e j 216 11

C e j 216 12

D e j 216 13

E e j 216 14

F  j 2 15 . e 16  (17)

Obviously, the affine functions of a k  1 variable over the alphabet (17) have a general form i (x1)  a1x1  a0 . Taking a0  0 , we construct 16 affine 16-functions 1  0 0000000000000000 2  x1 0123456789ABCDEF 3  2x1 02468ACE02468ACE 4  3x1 0369CF258BE147AD 5  4x1 048C048C048C048C 6  5x1 05AF49E38D27C16B 7  6x1 06C28E4A06C28E4A 8  7x1 0078E058C038A081088F068D048B0289 . 9  8x1 10  9x1 092B4D6F81A3C5E7 11  Ax1 0A4E82C60A4E82C6 12  Bx1 0B61C72D83E94FA5 13  Cx1 0C840C840C840C84 14  Dx1 0DA741EB852FC963 15  Ex1 0ECA86420ECA8642 16  Dx1 0FEDCBA987654321 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 1 2 3 4 5 6 7 8 9 A B C D E F 0 2 4 6 8 A C E 0 2 4 6 8 A C E 0 3 6 9 C F 2 5 8 B E 1 4 7 A D 0 4 8 C 0 4 8 C 0 4 8 C 0 4 8 C 0 5 A F 4 9 E 3 8 D 2 7 C 1 6 B 0 6 C 2 8 E 4 A 0 6 C 2 8 E 4 A V16  00 78 E0 85 C0 83 A0 81 80 F8 06 D8 04 B8 02 98 .

00 A9 24 BE 84 D2 C6 F6 80 A1 A4 E3 C8 52 CE 76 0 B 6 1 C 7 2 D 8 3 E 9 4 F A 5 0 C 8 4 0 C 8 4 0 C 8 4 0 C 8 4 0 D A 7 4 1 E B 8 5 2 F C 9 6 3 0 E C A 8 6 4 2 0 E C A 8 6 4 2 0 F E D C B A 9 8 7 6 5 4 3 2 1 

The resulting set of the first 16 affine 16-functions (18) determines the VilenkinChrestenson matrix of order N 16

In view of the fact that for our purposes of researching the nonlinearity values of component 16-functions of S-boxes of the Nyberg construction of length N  256 , we need a Vilenkin-Chrestenson matrix of order N  256 . Note that the previously used method [9] for constructing Vilenkin-Chrestenson matrices for arbitrary q is complex. It makes the task of developing of simple method for the synthesis of Vilenkin-Chrestenson matrices over the alphabet (17) actual. Researches allowed us to derive a formula for the recurrence construction of Vilenkin-Chrestenson matrices of any given order N 16k (19)

V16i V16i V16i V16i V16i V16i V16i V16i  V16i  8 V16i  9 V16i 10 V16i 11 V16i 12 V16i 13 V16i 14 V16i 15

V16i V16i  2 V16i  4 V16i  6 V16i  8 V16i 10 V16i 12 V16i 14 V16i  8 V16i 11 V16i 14 V16i 1 V16i  4 V16i  7 V16i 10 V16i 13

V16i V16i  4 V16i  8 V16i 12 V16i V16i  4 V16i  8 V16i 12 V16i  8 V16i 13 V16i  2 V16i  7 V16i 12 V16i 1 V16i  6 V16i 11

V16i V16i  6 V16i 12 V16i  2 V16i  8 V16i 14 V16i  4 V16i 10 V16i  8 V16i 15 V16i  6 V16i 13 V16i  4 V16i 11 V16i  2 VV1166ii  98 .

V16i V16i  8 V16i V16i  8 V16i V16i  8 V16i  V16i  8 V16i 1 V16i 10 V16i  3 V16i 12 V16i  5 V16i 14 V16i  7 

V16i V16i 10 V16i  4 V16i 14 V16i  8 V16i  2 V16i 12 V16i  6  V16i  8 V16i  3 V16i 14 V16i  9 V16i  4 V16i 15 V16i 10 V16i  5 

V16i V16i 12 V16i  8 V16i  4 V16i V16i 12 V16i  8 V16i  4  V16i  8 V16i  5 V16i  2 V16i 15 V16i 12 V16i  9 V16i  6 V16i  3 

V16i V16i 14 V16i 12 V16i 10 V16i  8 V16i  6 V16i  4 V16i  2  V16i  8 V16i  7 V16i  6 V16i  5 V16i  4 V16i  3 V16i  2 V16i 1  (20)

By constructing the Vilenkin-Chrestenson matrix with the help of (20), and also multiplying it by the component 16-function ( 8 ) of the S-box ( 5 ), it is easy to obtain the Vilenkin-Chrestenson transform coefficients of the 16-function ( 8 ). Further, applying formula (16), we find that the nonlinearity value of the 16-function ( 8 ) is equal to 16NFhex1  213.8184 . Moreover, the nonlinearity value of the second component 16-function is equal to 16NFhex2  212.4385 , and, accordingly, the nonlinearity value of the entire S-box is equal to 16NS  212.4385 .

Research of the Nyberg construction S-boxes of length N=256 based on the full class of irreducible polynomials To compare nonlinearity values, it is convenient to use such perfect algebraic constructions as bent-functions [10], which have the minimum possible value of the maxk imal Vilenkin-Chrestenson transform coefficient equal to q 2 , and, accordingly, the maximum nonlinearity value equal to k qN f  qk  q 2 . (21)

Thus, in our case for q  4 and k  4 the maximum value of nonlinearity is equal to 4N f  240 , while for q  16 and k  2 the maximum value of nonlinearity will also reach the value 16N f  240 .

Using the proposed method for estimating 2-nonlinearity, 4-nonlinearity and 16nonlinearity values of S-boxes of Nyberg construction of length N  256 , it is not difficult to estimate the nonlinearity values for all S-boxes that can be built over a field GF(256) . These values are summarized in Table 1. different values of nonlinearity in the sense of 4-functions and 16-functions. So, an Sbox based on a polynomial f19  41910 has the highest nonlinearity values of component 4-functions, while the S-box based on a polynomial f16  39510 has the highest nonlinearity values of component 16-functions. Moreover, both nonlinearity values of the component 4-functions and the nonlinearity values of the component 16-functions of S-box based on the polynomial f28  49910 are optimal. Earlier in [3], it was found that the polynomial f28  49910 (however, like polynomial f9  35510 ) also provides the most uniform minimization of the matrix of correlation coefficients. From our perspective, this S-box can be recommended for practical use in the AES cryptographic algorithm from the point of view of nonlinearity criteria for component functions of many-valued logic [14]. 5

Conclusions Let us to summarize the main results of the research: 1. The nonlinearity values of component 4-functions and 16-functions of S-boxes of Nyberg construction of length N  256 based on the full set of irreducible polynomials has been researched. It has been determined that the S-boxes of the Nyberg construction, which have the same nonlinearity distance of component Boolean functions, are at the same time characterized by different nonlinearity values of 4-functions and 16-functions for various irreducible polynomials. It was found that the nonlinearity values of the component 4-fucntions and component 16-functions of the S-box based on the polynomial f28  49910 are optimal, therefore this polynomial can be recommended for practical use. 2. The method for researching the nonlinearity value of 4-functions was adapted to the case of 16-functions. This technique can be applied to S-boxes of other practically valuable constructions. 3. A recursive rule is proposed for constructing hexadecimal Vilenkin-Chrestenson matrices of an arbitrary order.

1. Nyberg

: Differentially uniform mappings for cryptography. I Advances in cryptology . Proc. of EUROCRYPT'93 . Berlin, Heidelberg, Lecture Notes in Compuer SpringerVerlag, New York,. Vol. 765 , pp. 55 - 65 ( 1994 ).

2. Schneier

: Applied Cryptography. 2 -nd edition . John Wiley & Sons, New York, p. 784 ( 1996 ).

3. Mazurkov

M.I.

, Sokolov

A.V.

: Cryptographic properties of nonlinear transform of Rijndael cipher based on complete classes of irreducible polynomials . Odes' kyi Politechnichnyi Universytet. Pratsi , No. 2 ( 39 ), pp. 183 - 189 ( 2012 ).

4. Zhdanov

O.N.

: Key Information Selection Technique for Block Encryption Algorithm . INFRA-M, Moscow, p. 90 ( 2013 ).

5. Sokolov

, Zhdanov

: Prospects for the Application of Many-Valued Logic Functions in Cryptography . International Conference on Theory and Applications of Fuzzy Systems and Soft Computing , pp. 331 - 339 ( 2018 ).

6. Maier

, O. Staffelbach: Nonlinearity criteria for cryptographic functions . In Advances in Cryptology. EUROCRYPT'89, Lecture Notes in Computer Science , Springer-Verlag, vol. 434 , pp. 549 - 562 ( 1990 ).

7. Logachev

O.A.

, Salnikov

A.A.

, Yashchenko

V.V.

: Boolean functions in coding theory and cryptology , Publishing house MTsNMO , Moscow, p. 472 ( 2004 ).

8. Sokolov

A.V.

, Krasota

N.I.

: Very nonlinear permutations: synthesis methods for S-boxes with maximal 4-nonlinearity. Proceeding of ONAT named after A.S. Popov , Odessa, No. 1 , pp. 145 - 154 ( 2017 ).

9. Trachtman

A.M.

, Trachtman

V.A.

: Fundamentals of the theory of discrete signals on finite intervals . Soviet radio , Moscow, p. 208 ( 1975 ).

10. Tokareva , N.N. : Bent-functions: results and applications . Review of works. PDM , No. 1 ( 3 ), pp. 15 - 37 ( 2009 ).

11. Gnatyuk

, Akhmetov

, Kozlovskyi

, Kinzeryavyy

, Aleksander

, Prysiazhnyi

. New Secure Block Cipher for Critical Applications: Design, Implementation, Speed and

Security

Analysis , Advances in Intelligent Systems and Computing , vol. 1126 , pp. 93 - 104 , 2020 .

12. I. Gorbenko , O.

Kuznetsov , Y.

Gorbenko , A.

Alekseychuk and V.

Tymchenko , Strumok key stream generator , IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT) , Kyiv, Ukraine, 2018 , pp. 294 - 299 .

13. Yeoh , W. -., Teh, J. S. , & Sazali , M. I. “ µ2: A lightweight block cipher” , Lecture Notes in Electrical Engineering , vol. 603 , pp. 281 - 290 , 2020 , doi:10.1007/ 978 -981-15-0058-9_ 27 .

14. Zodpe

, Sapkal

“ FPGA-Based High-Performance Computing Platform for Cryptanalysis of AES Algorithm” , Advances in Intelligent Systems and Computing , Springer, vol. 1025 , pp. 637 - 646 , 2020 .