A New S-Box Design by Applying Bat Algorithm Based Technique

Introduction

Cryptography is a branch of cryptology concerned with design of cryptosystems (Stallings, 2012).

With the advancement of communication technologies, design of encryption techniques for secure communication of confidential information over insecure channel, have attracted major attention of research community. Encryption algorithms are mainly categorized as stream and block ciphers. The principles of confusion and diffusion are ensured during design phase of block ciphers (e.g., DES, IDEA, PRESENT, RC6 and AES). An S-box is a vital and most common crypto primitive in block ciphers. The S-box employed within a block cipher imparts confusion and makes the system resilient to defend against cryptanalytic attacks applied by the cryptanalyst for breaking the crypts. In most of the block ciphers, S-box is an important nonlinear element due to fulfilling crypto characteristics like Nonlinearity, Bit-Independence Criterion, Linear Probability, Differential Uniformity and Bijectivity. The strength of the employed S-box contributes significantly in over all cryptographic security of the cryptosystem.

The cryptographic strength of block ciphers mainly depends on applied S-boxes. There are three types of S-box designing process, known as, random search-based techniques, algebraic techniques, and heuristic based techniques. Finite Field inversion scheme is used in algebraic techniques for constructing S-box satisfying required cryptographic properties. The ‘Random Search’ based techniques are easy to implement and produce large number of S-boxes. However, quality of generated S-boxes using random search are far from the S-boxes produced by algebraic techniques. The third type of designing process apply various heuristics to design S-boxes satisfying most of the cryptographic strength parameters. There is a performance gap between algebraic and heuristics-based techniques. Therefore, meta-heuristics based iterative swarm techniques are applied for constructing S-boxes with enhanced cryptographic strength.

Review of Related Work

S-box is defined as a set of Boolean functions. An n × m S-box is a function S: {0, 1} n {0, 1}m , here n and m are positive integers indicating size of input and output string respectively. This maps an input string to an output string nonlinearly. In many ciphers, deployed S-boxes have same size of i/p and o/p string. S-boxes of size (4×4) and (8×8) are utilized in many block ciphers. The S-box (8×8) are used in highly secure ciphers, like AES and S-box (4×4) is generally used in light weight cryptosystems like PRESENT Cipher (Stinson,2013).

The correlation between the input-output strings is also determined for satisfying the security criteria of the S-box. Nonlinearity is a very important cryptographic property that imparts confusion for resisting against linear cryptanalysis of block ciphers (Hussain et al.,2012) (Özkaynak & Yavuz, 2013). After development of linear and differential cryptanalytic attack on S-boxes of DES cipher, a need was felt for the design of cryptographically strong S-boxes. Consequently, several S-box design schemes were evaluated which were based on optimization techniques. Tang et.al proposed a novel technique using discrete Baker map for construction of   S-box (Tang et al.,2005).  An S-box construction method based on chaotic maps was presented by Jakimoski (Jakimoski & Kocarev,2001). Wang et.al presented a design technique based on genetic algorithm and chaos to compute improvised S-box in the proposed work (Wang et al.,2012). Ahmed and Bhatia proposed a nature-inspired swarm-based technique by applying Ant Colony optimization (ACO) for generating strong S-boxes (Ahmad et al.,2015b). Farah et.al presented a technique for achieving S-box by applying “Teaching–Learning-Based Optimization (TBLO)” swarm algorithm (Farah et al.,2017).

The firefly algorithm is an iterative, nature-inspired swarm technique developed by Yang. The algorithm has been applied by researchers to solve real world optimization problems. Many researchers have developed several variants of the algorithm in their research work (Fister et al.,2013) (Gandomi et al.,2013). Since the proposed FA, many modifications have been made in the schemes which provided many variants to solve real-world continuous and constrained optimization cases (Yang, 2015)

(Yang, 2009). Many variants of the algorithm also developed in last decades due to performance comparison between FA and other well known swarm techniques.

The Bat swarm algorithm has shown its capability in addressing various issues of optimization, however its search behavior usually depends on initial positions and controlling parameters. Performance of the algorithm can be improved further by initializing it from a suitable initial point. In meta-heuristic-based optimization techniques, generally random initialization is done in every execution of the program of the algorithm (Parpinelli & Lopes ,2011) (Tsai et al.,2012) (Yang et al.,2013)

Swarm intelligence-based techniques are also applied in cryptanalysis of several ciphers (Laskari et al.,2007) (Din et al.,2019b) (Din et al.,2019a).In last two decades, some methods have been developed to design S-boxes by employing chaotic maps due to their nonlinear chaotic behavior (Webster & Tavares, 1986) (Asim & Jeoti,2008) (Özkaynak ,2019) (Lambić ,2014) (Ahmad et al.,2015a)

(Ahmad et al.,2018). According to above reported motivating research on S-box design the authors propose a swarm technique by employing nature-inspired Bat Algorithm (BA). 

In this research paper, related work on design of S-boxes by applying swarm-based techniques is reviewed. The next Section describes Bat Algorithm and BA based computational intelligence technique. The performance results of achieved S-box are discussed in the last Section.

Bat Algorithm

A nature-inspired Bat Swarm Algorithm was proposed by Yang X.S. in 2010 (Yang, 2010a).

BA is a population based meta-heuristic technique for solving optimization problems. It was inspired by the echolocation behavior of microbats, with varying pulse rates of emission and loudness. Each microbat of the swarm searches an optimal solution of the considered problem.  

This algorithm is naturally inspired form the social behavior of bats. The capability of the echolocations of these bats composed a great competent manner to detect prey, avoid obstacles, and to locate their rooster crevices in the dark based on sensing distances. In order to formalize the bat algorithm optimally, the following bat’s echolocation characteristics should be idealized:

(i) Object distances are always perfectly sensed by the echolocation system on bats. This makes the ability to differentiate between different objects even in darkness.

(ii) Bats are flying randomly with velocity v, fixed frequency fmin at position xi and fluctuating wavelength (λ) and loudness form large loudness (A0) to minimum loudness (Amin) to search for its prey. Wavelength or frequency can be changed instantly by adjusting the pulse emission rate   based on the closeness of the bat objective.

(iii) Variation of the loudness parameter takes values between A0 and Amin.

 The pseudo code of the bat algorithm is mentioned in figure 1. It starts with the initialization of all the echolocation system variables. Initial location of all bats swarms should be initialized as initial solutions. 

                                                                                                     (1)

                                                                                                       (2)

                                                                                                                        (3)

Here;

β: Random vector drawn from uniform distribution β [0, 1].

x*: Current global best location (solution) which is located after comparing all the solutions among all the bats.

fi: Frequency which is drawn uniformly from [fmin, fmax]

A random walk with direct exploitation is used for the local search that modifies the current best solution according to the equation:

                                                                                                                 (4)

Here;

 : is a random number [-1, 1].

At: is the average loudness of all the best at this time step.

ri: is the rate of pulse emission

For each bat, as soon as the prey found, the bat loudness decrease and the pulse emission rate increase. Both loudness and pulse emission expressed mathematically as follows:

                                                                                                                              (5)

                                                                                                        (6)

 and  as                                                                                                 (7)

Here; α : is constant 0 <α< 1 and   : is constant > 0

Figure 1. Bat Algorithm

Proposed Bat Algorithm based Technique

The BA is based on automated subdivision and have multimodality handling capacity. According to the subdivision criteria, the fireflies try to discover optimized solution applying parallel optimizations, particularly when population size is sufficiently higher compared to the modes. The proposed technique based on BA for designing 8 × 8 Substitution-boxes is as follows:

Initialization of Swarm Bats

(1)   Initialize n: No. of bats

(2)   Initialize each bat with a random permutation vector (P), having values in [0, 255] without repetition.  

(3)  Array P is reshaped into a 16 x 16 two-dimensional matrix representing initial S-box, which shows initial position of the 

ith bat .

(4)  Steps 2 to 3 are repeated for generating all n bats such that each bat represents one initial S-box.

Fitness function

Fitness value of each bat is calculated on the basis of nonlinearity of each S-box as follows:

4.2.1 Nonlinearity of S-box is calculated using following equation:

                                                                           (8)

Here, the Walsh spectrum of  is determined as per equation follows:

                                                                                      (9)

for the Eq. (4) 𝑤 ∈ GF(2n) and the dot product (x.𝑤) is computed as follows:

The fitness value of  ith bat (fi) is determined using following equation.

                                                                                                       (10)

Here, 112 is an optimal value of S-Box nonlinearity mentioned in the Block Cipher AES (Stinson, 2013), and NL function determines nonlinearity of ith bat corresponding to S-box. In the current iteration, the bat with lowest fitness value provides the best S-box.

                                                                                                       (11)

 Where, Pi,k represents kth element of the S-box corresponding to ith bat and d is set to 255.

After every movement of bats, the obtained values are checked for keeping within the specified threshold values: 0 and 255. This is ensured by satisfying Bijective property of the S-Box corresponding to the bat. 

Minor Adjustment

An S-box (8 x 8) is represented as a vector of 256 elements. As per Bijective property of an S-box, each element occurs only once in the vector. Sometime this property is not fully satisfied by computed S-box in the Bat algorithm. So, minor adjustment is required in the obtained S-box such that each item from 0 to 255 occurs only once to fully satisfy the Bijective property.

Performance Analysis of the Proposed S-box

The proposed Bat algorithm-based technique is implemented using MATLAB software (Ver. R2017a). The developed software is run on the 3.0 GHz computing machine.   Various trials are conducted for different values of the control parameters of the algorithm to compute cryptographic strong S-boxes. 

The parameters of proposed technique are taken as:  ,  ,  ,  iterations = 750, swarm size (N) = 20. The obtained S-box is shown in the following Table:

Table 1. The S-Box Computed by Proposed Technique

Many performance measures for S-box are defined by expert designers for examining cryptographic security strengths of an S-box. Biham and Shamir proposed the differential uniformity criteria through its differential cryptanalysis of DES block cipher based on differential probability, calculated using I/O XOR distribution (Menezes et al.,2018) (Biham & Shamir, 1991). Matsui proposed linear cryptanalysis based on linear approximation probability (Matsui ,1993). Dawson et.al applied information theoretic concepts for designing and evaluation of cryptographic strong S-boxes (Dawson & Tavares ,1991). Therefore, cryptographic security of designed S-boxes is ensured by nonlinearity, bijectivity, strict avalanche criterion (SAC), bit-independence criterion (BIC), differential uniformity and linear-approximation probability (LP) (Wang et al., 2009).

Bijective Property

The bijectivity implies that each item of the S-box occurs only once.

                                                                                                             (12)

Where   is the Hamming weight. As per equation (13), bijectivity is fulfilled when all Hamming weights are equal to 128 for the designed S-box.

Nonlinearity

Nonlinearity of S-box is calculated using equation (3). The non-linearity is connected to immunity of block cipher and plain text confusion. This is computed using Walsh spectrum as mentioned in equation (4). The computed nonlinearity corresponding to the Boolean functions of the obtained S-box is shown in following table and depicted in Figure 2.

Table 2. Nonlinearity of S-box

Figure 2. Nonlinearity of 8 Boolean Functions of S-box

Strict Avalanche Criteria 

Webster and Tavares (Webster & Tavares ,1986) defined SAC by ensuring that there is a probability of ½ for a change in all the output bits when single input bit is flipped. SAC is ensured through dependence matrix and offset values of SAC are computed using following equation:

                                                                                                        (13)

Bit Independence Criteria (BIC)

This stipulates the pair-wise independence of all avalanche variables for any avalanche vector generated by the complementing of a single plaintext. The criteria was defined by Webster and Tavares (Webster & Tavares ,1986).

I/O XOR distribution

For an ideal S-box, the obtained XOR distribution table should be balanced since imbalance distribution table helps in applying differential cryptanalytic attack. A cryptographic strong S-box should be differential uniform. For a given S-box, differential uniformity is measured using equation (14).

                                                                                        (14)

Here, X contains all the input values and total number of elements is shown by 2n. Table 3 shows the I/O XOR distribution for the obtained S-box.

Table 3. I/O XOR Distribution

Linear approximation probability

The LP probability is determined as the maximum imbalance value. Thus, mask a selects input bits that have parity equal to the output bits selected by mask b. The equation (15) is applied for computing LP.

                                                 (15)

For a given S-box, LP should be as small as possible. An S-box with lower LP has more resistance against linear cryptanalysis than other S-box with higher LP.

Table 4. The Dependence Matrix for the Computed S-Box

A swarm technique applying Bat Algorithm is proposed for designing strong S-boxes. The above-mentioned results of the S-box obtained by the swarm technique have shown that most of the criteria of a good S-box are fulfilled. The obtained S-box has high immunity against differential cryptanalytic attacks. The computed S-box is free from the fixed points. The maximum nonlinearity of the S-box is 112 and minimum is 110. The average nonlinearity stands at 110.75. The average SAC value for the S-box is 0.506.

According to the Table of Input / Output XOR distribution, DP values are approximately uniformly distributed and most of the values are 4.

Table 5. Performance Comparison of the New S-box

According to the Table 5, the performance indicators for the constructed S-box are compared with some recently reported S-boxes. The maximum nonlinearity of the S-box is 112 and minimum is 108. The computed average nonlinearity is 110.75. The average SAC value for the S-box is 0.506. The obtained maximum DP value in the I/O XOR distribution table is 6. The proposed new S-box is also free from the fixed points. 

Authors addressed the issues of designing cryptographic strong S-boxes. An efficient Bat algorithm-based technique is proposed to generate S-boxes. The computed S-box has better performance as compared with some of the existing S-boxes. The achieved S-Box meets most of the cryptographic requirements. Authors plan to focus on designing strong S-boxes having different sizes of inputs and outputs by developing efficient swarm techniques based on other meta-heuristics and swarm intelligence. 

Acknowledgements

My sincere thanks to the co-authors for their valuable technical guidance and motivation in carrying out the proposed research work and supporting me in research paper submission.

Conflict of interest

The authors declare no potential conflict of interest regarding the publication of this work. In addition, the ethical issues including plagiarism, informed consent, misconduct, data fabrication and, or falsification, double publication and, or submission, and redundancy have been completely witnessed by the authors.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.