Construction of Cryptographically Secure AES S-Box using Second-order Reversible Cellular Automata

Abstract

In cryptography the block ciphers are the mostly used symmetric algorithms. In the existing system the standard S-Box of Advanced Encryption Standard(AES) is performed using the irreducible polynomial equation in table form known as look-up tables(LUTs). For more security purposes, second-order reversible cellular automata based S-box is created. The security aspects of the S-Box used in the AES algorithm are evaluated using cryptographic properties like Strict Avalanche Criteria, Non-Linearity, Entropy, and Common Immunity Bias. The design of S-Box using second-order reversible Cellular Automata is better concerning security and dynamic aspect as compared to the classical S-boxes used Advanced Encryption Standard.

Keywords

Look-up tables cellular automata classical S-Box

1 Introduction

A cellular automaton (CA) is a parallel computational model that has been used to simulate and analyze a wide variety of discrete complex systems in different application domains. The Cellular Automata is a group of cells on a grid that changes its state through each discrete time steps according to a set of rules based on the states of neighboring cells. The state of the current cell and its neighboring cells combined called neighborhood states. The neighborhood radius is defined as the number of neighbor cells to either side of the central cell. Neighborhood state l is defined as l = 2r+1. For one-dimensional (1-D) CA, when the radius r = 1, then the neighborhood state l = 3. The number of neighborhood states K = 2l and the number of rules is R = 2k (when k = 8,r = 256). During a single time step, each cell in the lattice synchronously updates its state according to a local rule, which is applied to the neighborhood of the cell.

2 Method

The Advanced Encryption standard algorithm is the symmetric block cipher algorithm which consists of secret keys.The AES algorithm consists of four transformations which are repetedly specified in each rounds for encryption algorithm and inverse steps are involved for decryption process.The four transformations are substitute box,shift rows,mix column and add round key [1].

The 128 bits inputs are arranged in a block of bytes using the 4×4 square matrix. The bytes processing is defined in the Galois Field GF(2⁸) [2].

$[\begin{matrix} byte 0 & byte 4 & byte 8 & byte 12 \\ byte 1 & byte 5 & byte 9 & byte 13 \\ byte 2 & byte 6 & byte 10 & byte 14 \\ byte 3 & byte 7 & byte 11 & byte 15 \end{matrix}]$

The following steps involved in the encryption process, which is shown in Fig. 2.1.

Initial Round: AddRoundKey

Rounds: SubBytes, ShiftRows, MixColumns, and AddRoundKey

Last Round: SubBytes, ShiftRows, and AddRoundKey

Fig. 2.1

The overall structure of AES Algorithm.

3 S-Box design

S-Box is the basic component of a cipher system. It Substitutes a given value of the input into another value as output [3]. It can have the different number of inputs and outputs (m-bit input word and n-bit output word)

There are two different types of design approaches:

3.1 Look Up Table (LUT) based

In the LUT based design, fixed table are normally used in which for each value of “m’’ bit word an alternate value of “n’’ bit word is pre-defined. (Ex: S-Boxes in AES, DES) [4].

3.2 Function-based

In the function-based design, the functions are defined such that $F : {0, 1}^{m}_{0, 1}^{n}$

4 Second order reversible cellular automata

At each time step, by applying local rule to every cells of a CA, one obtains a new configuration C^t+1 from the CA’s old configuration C^t called C^t+1’s predecessor. Thus, the local rule defines a mapping from C to C^t+1, called the global map F (·), i.e. C^t+1 = F (C^t). And such CA is called one-order CA because its “next” configuration is only derived from its “current”configuration [5]. Figure 4.1 shows the rule 75 definition.

Fig. 4.1

Rule 75 definition.

A CA is called second-order CA (CA²) if its “next” configuration is a function of both the “current” and the “previous” one. For instance, a one-order CA could be characterized by $C^{t + 1} = F (C^{t}),$ (1)

Where C^t denotes CA’s configuration at time step t, and F (·) is a global map determined by local rule [6, 7]. Then a second order CA could be characterized as $C^{t + 1} = G (C^{t}, C^{t - 1})$ (2) where G (·) is a global map defined by some time and space relations between the cells [8].

If given C^t+1 and C^t, there is only one configuration C^t-1 that satisfies Equation (2), then such CA is called reversible CA² (RCA²) [9, 10]. Figure 4.2 shows the structure of second order cellular automata

Fig. 4.2

Second order reversible cellular automata.

4.1 Steps for the proposed algorithm

The proposed AES implementation constructed by the following steps. Also it is shown in Fig. 4.3.

The Standard AES algorithm is to be constructed.

Check for the reversible rules using cryptographic properties.

The rules which follows the cryptographic properties are taken for the construction of RCA² based S-Box.

The rules are inserted into the AES algorithm instead of standard S-Box for both encryption and decryption process.

Second order reversible CA based S-Box is constructed.

Fig. 4.3

Steps of the proposed algorithm.

4.2 Finding ca rules with cryptographic properties

4.2.1 Strict avalanche criteria (SAC)

If one bit input is changed in a Boolean function, then half of the output bit should be changed. For a Boolean function, if f is to satisfy SAC the following condition should be satisfied, f (x) ⊕ f (x ⊕ α) should be balanced, where the hamming weight of is 1.

$\begin{matrix} {dSAC}_{f} = max_{1 ⩽ i ⩽ n} \\ | 2^{n - 1} \sum_x \in B^{n} f (x) \oplus f (x \oplus c_i^{n}) | \end{matrix}$ (3)

4.2.2 Non linearity

The non-linearity of a Boolean function can be defined as a minimum hamming distance between the function and the set of all the affine function. $N_{f} = min [d (f, g)]$ (4) (where g ∈ A_n) Where A_n is the set of all the affine function $d (f, g) = 2^{n - 1} - (1 / 2) * [< η, β >]$ (5) where η,β are the binary sequence of f,g respectively and < η,β>define the scalar product of sequence,so far a function f : B^n→B^m $N_{f} = 2^{n - 1} - (1 / 2) * [max (< η, β >)]$ (6)

4.2.3 Correlation immunity bias

If Boolean function f is statistically independent of combination of any m input bits, then it satisfies CIB of order m.If m inputs bits are fixed then we can get ⁿ C_m2 ^m g function. so far f : Bⁿ → B^m ${CIB}_{f} (m) = max | 2^{m *} w (g_{j}) - w (f) |$ (7) where W(g_j) belongs to the hamming weight of all the possible function while keeping m bits in f fixed. W(f) corresponds to the hamming weight of function f.

In a S-Box with μ : Bⁿ ⟶ B^m so, there would be m no.of function μ = μ₁, μ_2,μ₃ … . . μ_m [where i ∈ (1, m)]

4.2.4 Entropy

This property provides us the amount of information in the input bits, when output bit are already known. There exists 2ⁿ possible inputs and 2 ^m outputs for a Boolean function of n input and m output. The (i, j)th input/output bit to bit entropy of S-Box is computed with H(xi/fj(x)) and represented by HS $H (P_{i}) = P_{i} {log}_{2} \frac{1}{P_{i}} + (1 - P_{i}) {log}_{2} \frac{1}{1 - P_{i}}$ (8)

5 Experimental analysis

Analysis is based upon the values of the cryptographic properties such as non linearity, entropy,correlation immunity bias, strict avalanche criteria.

The values for non linearity for CA based AES S-Box is calculated using rule number and number of time step, which is shown in Fig. 5.1.

Fig. 5.1

Values for Non Linearity for CA based AES S-Box.

The values of entropy for CA based AES S-Box is calculated using rule number and number of time step, which is shown in Fig. 5.2.

Fig. 5.2

Values for Entropy for CA based AES S-Box.

The values of correlation immunity bias for CA based AES S-Box is calculated using rule number and number of time step, which is shown in Fig. 5.3.

Fig. 5.3

Values for CIB of CA Based AES S-Box.

The values of strict avalanche criteria for CA based AES S-Box is calculated using rule number and number of time step, which is shown in Fig. 5.4.

Fig. 5.4

values for SAC of CA Based AES S-Box.

6 Conclusion

A second order reversible cellular automata based S-Box for AES algorithm is proposed to overcome the limitations of standard classical LUT based S-Box.The proposed RCA² based S-Box eliminates inefficient memory tables and possibility to create an S-Box, which are dynamic in nature and also cryptographically secure than the conventional S-Box used in AES algorithm. The comparative analysis with respect to level of security for LUT based conventional S-Box and RCA² based S-Box was evaluated using cryptographic properties. Therefore, it has been observed that the values corresponding to RCA² based S-Box outperform that of LUT based S-Box realisations.

References

Rao

S.K.

, Mahto

and Ali Khan

, A survey on advanced encryption standard, In proceedings of the International Journal of Science and Research (IJSR) 6(1), 2017.

Mariot

and Leporati

, Cellular automata based S-boxes, In the proceedings of, springer, May 2018.

Szaban

and Seredynski

, Dynamic Cellular Automata-Based S-Boxes, in the proceedings of Springer-Verlag Part I (2012), 184–191.

Picek

and Mentens

, Design of S-boxes Defined with Cellular Automata Rules, In Proceedings of CF’17, Siena, Italy, May 15-17, (2017), pp. 6.

Szaban

and Seredynski

, Application of Cellular Automata to Create S-Box Functions, In the proceedings of IEEE symposium on parallel and distributed processing, May 2008.

Szaban

and Seredynski

, CA-based Generator of S-boxes for Cryptography Use, In the proceedings of IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW), May 2010.

Jegadish Kumar

K.J.

and Karthick

, AES S-Box Construction using One Dimensional Cellular Automata Rules, In, the proceedings of International Journal of Computer Applications 110(12), 2015.

Seredynski

and Bouvry

, Block cipher based on reversible cellular automata, In the Proceedings of the Congress on Evolutionary Computation (IEEE Cat. No.04TH8753), 03 September 2004.

Szaban

and Seredynski

, Cellular Automata-Based S-Boxes vs. DES S-Boxes, In the proceedings of international conference on parallel computing technologies, Springer-Verlag, (2009), pp. 269–283.

10.

Szaban

and Seredynsi

, Improving quality of DES S-boxes by cellular automata-based S-boxes, In the proceedings of a journal of super computing 57(2) (2011), pp. 216–226.