# Block Cipher’s Substitution Box Generation Based on Natural Randomness in Underwater Acoustics and Knight’s Tour Chain

Authors: Muhammad Fahad Khan; Khalid Saleem; Tariq Shah; Mohammad Mazyad Hazzazi; Ismail Bahkali; Piyush Kumar Shukla
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

The protection of confidential information is a global issue, and block encryption algorithms are the most reliable option for securing data. The famous information theorist, Claude Shannon, has given two desirable characteristics that should exist in a strong cipher which are substitution and permutation in their fundamental research on “Communication Theory of Secrecy Systems.” block ciphers strictly follow the substitution and permutation principle in an iterative manner to generate a ciphertext. The actual strength of the block ciphers against several attacks is entirely based on its substitution characteristic, which is gained by using the substitution box (S-box). In the current literature, algebraic structure-based and chaos-based techniques are highly used for the construction of S-boxes because both these techniques have favourable features for S-box construction but also various attacks of these techniques have been identified including SAT solver, linear and differential attacks, Gröbner-based attacks, XSL attacks, interpolation attacks, XL-based attacks, finite precision effect, chaotic systems degradation, predictability, weak randomness, chaotic discontinuity, and limited control parameters. The main objective of this research is to design a novel technique for the dynamic generation of S-boxes that are safe against the cryptanalysis techniques of algebraic structure-based and chaos-based approaches. True randomness has been universally recognized as the ideal method for cipher primitives design because true random numbers are unpredictable, irreversible, and unreproducible. The biggest challenge we faced during this research was how can we generate the true random numbers and how can true random numbers utilized for strengthening the S-box construction technique. The basic concept of the proposed technique is the extraction of true random bits from underwater acoustic waves and to design a novel technique for the dynamic generation of S-boxes using the chain of knight’s tour. Rather than algebraic structure- and chaos-based techniques, our proposed technique depends on inevitable high-quality randomness which exists in underwater acoustics waves. The proposed method satisfies all standard evaluation tests of S-boxes construction and true random numbers generation. Two million bits have been analyzed using the NIST randomness test suite, and the results show that underwater sound waves are an impeccable entropy source for true randomness. Additionally, our dynamically generated S-boxes have better or equal strength, over the latest published S-boxes (2020 to 2021). According to our knowledge first time, this type of research has been conducted, in which natural randomness of underwater acoustic waves has been used for the construction of block cipher’s substitution box.


---

## Body

## 1. Introduction

Information security is the protection of secret data from illegal access, disclosure, inspection, destruction, disruption, and modification. The protection of confidential information is a global issue and block encryption algorithms are the most reliable option [1]. Block cipher is a branch of deterministic algorithm that works on the static length of bits, which is called block. Block cipher algorithms split the plaintext into various blocks of size k, to generate the same number of encrypted blocks of size n. Block ciphers encrypt one block at a time and the size of the output block is always equal to the input block and the transformation from input block to output block is done through the key whitening operation. Block cipher merged the confusion-diffusion primitives iteratively using a round function to generate an encrypted text. AES, DES, GOST, and BLOWFISH are the most prominent block ciphers of the industry that used the same strategy. For the block encryption algorithms such as AES, GOST, BLOWFISH, DES, and linear-differential attacks are the most powerful attacks [2–6]. In the differential attack, the basic purpose is to detect the sequential patterns from the encrypted text and for this purpose, the attacker tries to apply a specific set of inputs to trace the change in output. In the linear attack, the basic purpose is to find the linear relation among the plain text, cipher text with the corresponding keys. The responsibility to create a randomized relation among ciphertext and the key is on the confusion component; also, the confusion component is totally responsible to provide resistance against the linear and differential attacks [1–11]. Block cipher’s confusion component is generally known as substitution (S-box) which transforms k input bits into m output bits through S:{0,1}k⟶{0,1}m, transforms vector z = [zn-1, zn-2, zn-3 … z0] into output vector k = [kn-1, kn-2, kn-3,…, k0].As S-box is the only nonlinear primitive of block cipher, so the block cipher strength depends on its design. Cipher designers used various approaches to construct good quality S-boxes. Chaos-based and algebraic structure-based techniques are highly used for the construction of S-boxes. Chaos-based and algebraic structure-based techniques have favourable features for S-box construction, but many cryptanalysis of these techniques have been identified in the current literature. These cryptanalysis are described in Section3. Underwater acoustic is generated by a diverse nature of sound sources such as underwater volcanoes, snapping shrimp, reverberation, vibrating objects, breaking waves, marine life, man-made sources, rain, geological activities, scattering waves, reflection waves, random motion of water molecules, lightning strikes, ice cracking, earthquake, compression, and decompression of water molecules [12–22]. Due to these diverse natures of sound sources, inevitably high-quality randomness exists in the amplitude characteristic of the underwater acoustics, which was our main source of inspiration because true randomness has been universally recognized as the ideal primitive for cryptography. True random numbers (TRNs) are unpredictable, irreversible, and unreproducible that is why cipher researchers endorsed the true random number for cryptographic primitives design [23–30].The main idea of this research paper is extraction of true random bits from underwater acoustic waves and to design a novel technique for the dynamic generation of cryptographic S-boxes using the chain of knight’s tour. The main benefit of our approach is that the proposed technique depends on the natural randomness of underwater acoustic waves for the construction of S-boxes and that’s why various existing chaos and algebraic structure-based attacks are bypassed for our proposed technique.The rest of the paper is arranged as follows. Section2 presents our main contribution. Section 3 shows the potential cryptanalysis and attacks. Section 4 describes the proposed methodology for the dynamic generation of strong S-boxes. Section 5 presents results and discussion. Section 6 shows the conclusion.


## 2. Contribution

(i)
A novel technique is proposed based on combination selection, for the generation of true random numbers from the randomness which exists in the amplitude property of underwater acoustics. As an assessment, two million bits have been analyzed using the NIST randomness test suite, and results show that underwater acoustic waves are an impeccable entropy source for TRNG.(ii)
Knight’s tour-based, a novel technique is proposed, for the dynamic generation of S-boxes and as a result attacks of algebraic- and chaos-based techniques are not applicable and irrelevant for our proposed technique.(iii)
According to our knowledge first time, this type of research has been conducted, in which natural randomness of underwater acoustic waves has been used for the construction of block cipher’s substitution box.


## 3. Potential Attacks of Existing S-Box Designs

As we said before, chaos-based and algebraic structures-based techniques are widely used for the construction of Shannon’s confusion primitive but many attacks of these techniques have been identified in the current literature including Gröbner-based attacks [2–8], SAT solver [9–11, 31–35], linear and differential attacks [36–50], XSL attacks [51–55], interpolation attacks [51, 56–58], XL-based attacks [59–61], finite precision effect [62–67], chaotic systems degradation [61–63, 68, 69], predictability [70, 71], weak randomness [62, 63, 65, 66, 72–77], chaotic discontinuity [65–67, 72, 73], and limited control parameters [78–81].The main objective of this research is to design a novel technique for the dynamic generation of S-boxes that are safe against the attacks of algebraic structure-based and chaos-based techniques. Rather than algebraic structure- and chaos-based techniques, our proposed technique depends on inevitable high-quality randomness which exists in underwater acoustics waves. The basic concept of the proposed technique is the extraction of true random bits from underwater acoustic waves and to design a novel technique for the dynamic generation of S-boxes using the chain of knight’s tour.


## 4. Proposed Methodology

The proposed method consists of two phases, the first phase is true random numbers generation based on underwater acoustics and the second phase is dynamic generation of S-boxes based on Knight’s tour chain. Architecture diagram of the proposed system is depicted in Figure1.Figure 1
Architecture diagram of the proposed system.


### 4.1. True Random Numbers Generation Based on Underwater Acoustics

In this phase, first of all, long-term underwater acoustics recordings were acquired from the doi based dataset of the Australian Antarctic Data Centre (AADC) [82]. In the dataset, the average duration of each recording is sixty minutes. Out of thousands of long-term underwater acoustic recordings, we randomly selected the 96 long-term underwater acoustic recordings but proposed technique can take any multiple of 16 files as entropy sources. Secondly, these recordings are divided into blocks of size 16 and then, the amplitude difference of every 0.5 sec is calculated. Due to the diverse nature of sound sources, the difference of each amplitude with other amplitudes is random, and this was our main source of inspiration. Other characteristics of underwater sound like frequency and timber contain low-quality randomness that is why we chose the amplitude characteristic for this research. To calculate the amplitude differences, we used the combination selection strategy by using n!/r! (n–r)! . In our case, the value of the n is 16 and the value of r is 2. The entire step-by-step process of this phase from underwater acoustic files input to the random bits generation is represented in the flowchart of Figure 2. The amplitude differences calculation step is depicted in Figure 3, and here, long-term underwater acoustic recording represented as R1, R2, … R16. Two million bits have been analyzed using the NIST randomness test suite and shown in the Table 1, and results of the NIST tests show that underwater acoustics waves are an impeccable entropy source for true randomness. There are many random extractors based on hash functions, machine learning, chaos machine, physical unclonable functions, and probabilistic methods but among all these types of random extractors. Von Neumann random extractor is the simplest and fastest method that is why we chose Von Neumann random extractor as the postprocessing method.Figure 2
Flowchart of TRNG-based underwater acoustics.Figure 3
Computation of amplitude differences.Table 1
Results of NIST randomness test suite.
Type of testP valueConclusion01. Frequency test (monobit)0.8461758819031635Random02. Frequency test within a block0.5166228701210154Random03. Run test0.2609970420138874Random04. Longest run of ones in a block0.34640251063536204Random05. Binary matrix rank test0.09949346113140206Random06. Discrete Fourier transform (spectral) test0.832838521091328Random07. Nonoverlapping template matching test0.22184797295460632Random08. Overlapping template matching test0.16413619193258017Random09. Maurer’s universal statistical test0.4051810932845413Random10. Linear complexity test0.4394606534399792Random11. Serial test:0.5703210920746249Random0.5412977586951687Random12. Approximate entropy test0.013704869478928823Random13. Cummulative sums (forward) test0.9081561792752144Random14. Cummulative sums (reverse) test0.7420961383854099Random15. Random excursions test:StateChi squaredP valueConclusion−43.19405585363397030.6700965356355721Random−38.3227043137254930.13932469392722086Random−22.2153796498023080.8186113923928053Random−110.3738562091503270.06530927491189864Random+15.492810457516340.3587348843928551Random+21.9786330993302670.8520935894148005Random+30.8729035294117620.9721522155809542Random+42.20307224930788650.8203920781040164Random16. Random excursions variant test:StateCountsP valueConclusion−9.017430.3503620748973999Random−8.017910.22313138786599762Random−7.018610.09700096546916874Random−6.018370.09426256021374013Random−5.017550.17515792247265105Random−4.016750.3218141454622986Random−3.015880.6391395377015844Random−2.016050.43375610043914314Random−1.015720.4476990724652935Random+1.016010.19931513588782468Random+2.016290.30147752489003166Random+3.016090.523032983174088Random+4.016090.589348273539888Random+5.016620.426374068680618Random+6.017830.1678955379041649Random+7.018760.0827802734496795Random+8.018690.1135773370125223Random+9.018180.20668955769990105Random


### 4.2. Dynamic Generation of S-Boxes Based on Knight’s Tour Chain

The knight’s tour is more than a 1400-year-old puzzle game whose objective is to discover the legal moves on the chessboard in the way that it explores every cell only once, and in our proposed methodology, we utilized the chain of 8 × 8 knight’s tour for the generation of S-boxes. First of all, true random numbers are acquired and divided into blocks of 64 length size, and then, each 64 length block is converted into the 8 × 8 chessboard matrix. Based on the knight tour rules, we traversed each element of the chessboard matrix; however, only unique elements are considered for S-box elements, and a similar procedure is repeated for coming chessboards until the completion of required length of the S-box. Initial position of the first block of the knight’s tour chain is calculated throughr = TRNG [0] mod 8, c = TRNG [1] mod 8, and the initial positions of other knights’ tour chains are dependent on the second last and the last element of the S-box, which are calculated through r = S-box [n − 1] mod 8, c = S-box [n] mod 8. The entire step-by-step process of this phase from true random numbers input to dynamic S-boxes generation is represented in the flowchart of Figure 4. This phase is depicted in the following Figure 5. The reverse S-box algorithm is shown in the following (Algorithm 1). From the dynamically generated S-boxes stream, we picked two S-boxes randomly as sample which are shown in Tables 2 and 3, and their reverse S-boxes are also shown in Tables 4 and 5, respectively. The maximum nonlinearity score of our sample S-boxes is higher or equal to the recently published S-boxes (from 2020 to 2021).Figure 4
Flowchart of dynamic S-boxes generation based on knight’s tour chain.Figure 5
Dynamic generation of S-boxes based on knight’s tour chain.Table 2
Substitution box 1.
1062205241124201049688240170911524686197230174155761851753114210323912240113208228782121829110854370271206628189126362321381652341624323160235974890101982506453873141538171203206213525211114592238631301861801231924251891968458143325982198112224247641771781481842332002221071051952011871542361631092192541372102412042121393424824974202253524722619123114207118171911932171441692371357131301219533141991191461001661822557221520918877993511624218871321021581521506221155164801621252251331831171795120560658152136922341541764624419401561723956161227147931296716822124525136172141281676122922111539414915150216491593710127726834413442231797568108173157140191181190Table 3
Substitution box 2.
2542401871115115515310010320114407214158631802091382169276018621975210925124895191247110107582102620390168121250662265010417646659361832451348621674423820716110202991716521716780551288275200401821471741961561201921161361641884851521663362230137129102612235415934592461952131705125322912612214024198772371794719130130118185224243453622714910623968221189219150108131611541122421722317813513116023112924431255173392332051988920182158249139181212531631571272086410585142184145293717511112522241172327687843542123492352492101912041947913396321569671461908883114111917723413238742362523287822220574321122519941941971437020673162562522821881115114171113148193247214Table 4
Reverse S-box 1.
2044721358526223919312237227134146153194512201701336332265332182404043351492392152124167462366420728198244382426320113157234232189130671991792081479093191224177799919242214248196396916165127247201653224618168942418937151719875814077212229151856601661575917325710801072491153675962913613168187138155411502783518345238222213801481721852437321911848123252662491143761562111022301762311752281121920525117423554209182114180491582232151441113920625018222001001011888225415918610321811111644425525384141203109881695154105110128701211907113730163119178122195221162233142341161216106197971841322103122517245471045055113145782610120169522022171498125126618674129117160Table 5
Reverse S-box 2.
1121519225187895258165973439614013208626616331162242281461982443821226181122154207921031931291822211577623519423159128491208819646109261701017124323036104229993151755044210134209239331224122274190117227204702477321419217756191213161402011995123630206251166572009884717613235139276318414325124924884188124217824211319532185112173721521231492202055514885951816711421617823810180211782521311384906142581172141021501412421718667916941201082501451567918348218147119161687753179125232871362121218325320310680237160234759643920215924061174173723216910725516457682461372291351861001262334513024511194151189158219197223118601331115144127153541052542916643282241100155


## 4.1. True Random Numbers Generation Based on Underwater Acoustics

In this phase, first of all, long-term underwater acoustics recordings were acquired from the doi based dataset of the Australian Antarctic Data Centre (AADC) [82]. In the dataset, the average duration of each recording is sixty minutes. Out of thousands of long-term underwater acoustic recordings, we randomly selected the 96 long-term underwater acoustic recordings but proposed technique can take any multiple of 16 files as entropy sources. Secondly, these recordings are divided into blocks of size 16 and then, the amplitude difference of every 0.5 sec is calculated. Due to the diverse nature of sound sources, the difference of each amplitude with other amplitudes is random, and this was our main source of inspiration. Other characteristics of underwater sound like frequency and timber contain low-quality randomness that is why we chose the amplitude characteristic for this research. To calculate the amplitude differences, we used the combination selection strategy by using n!/r! (n–r)! . In our case, the value of the n is 16 and the value of r is 2. The entire step-by-step process of this phase from underwater acoustic files input to the random bits generation is represented in the flowchart of Figure 2. The amplitude differences calculation step is depicted in Figure 3, and here, long-term underwater acoustic recording represented as R1, R2, … R16. Two million bits have been analyzed using the NIST randomness test suite and shown in the Table 1, and results of the NIST tests show that underwater acoustics waves are an impeccable entropy source for true randomness. There are many random extractors based on hash functions, machine learning, chaos machine, physical unclonable functions, and probabilistic methods but among all these types of random extractors. Von Neumann random extractor is the simplest and fastest method that is why we chose Von Neumann random extractor as the postprocessing method.Figure 2
Flowchart of TRNG-based underwater acoustics.Figure 3
Computation of amplitude differences.Table 1
Results of NIST randomness test suite.
Type of testP valueConclusion01. Frequency test (monobit)0.8461758819031635Random02. Frequency test within a block0.5166228701210154Random03. Run test0.2609970420138874Random04. Longest run of ones in a block0.34640251063536204Random05. Binary matrix rank test0.09949346113140206Random06. Discrete Fourier transform (spectral) test0.832838521091328Random07. Nonoverlapping template matching test0.22184797295460632Random08. Overlapping template matching test0.16413619193258017Random09. Maurer’s universal statistical test0.4051810932845413Random10. Linear complexity test0.4394606534399792Random11. Serial test:0.5703210920746249Random0.5412977586951687Random12. Approximate entropy test0.013704869478928823Random13. Cummulative sums (forward) test0.9081561792752144Random14. Cummulative sums (reverse) test0.7420961383854099Random15. Random excursions test:StateChi squaredP valueConclusion−43.19405585363397030.6700965356355721Random−38.3227043137254930.13932469392722086Random−22.2153796498023080.8186113923928053Random−110.3738562091503270.06530927491189864Random+15.492810457516340.3587348843928551Random+21.9786330993302670.8520935894148005Random+30.8729035294117620.9721522155809542Random+42.20307224930788650.8203920781040164Random16. Random excursions variant test:StateCountsP valueConclusion−9.017430.3503620748973999Random−8.017910.22313138786599762Random−7.018610.09700096546916874Random−6.018370.09426256021374013Random−5.017550.17515792247265105Random−4.016750.3218141454622986Random−3.015880.6391395377015844Random−2.016050.43375610043914314Random−1.015720.4476990724652935Random+1.016010.19931513588782468Random+2.016290.30147752489003166Random+3.016090.523032983174088Random+4.016090.589348273539888Random+5.016620.426374068680618Random+6.017830.1678955379041649Random+7.018760.0827802734496795Random+8.018690.1135773370125223Random+9.018180.20668955769990105Random


## 4.2. Dynamic Generation of S-Boxes Based on Knight’s Tour Chain

The knight’s tour is more than a 1400-year-old puzzle game whose objective is to discover the legal moves on the chessboard in the way that it explores every cell only once, and in our proposed methodology, we utilized the chain of 8 × 8 knight’s tour for the generation of S-boxes. First of all, true random numbers are acquired and divided into blocks of 64 length size, and then, each 64 length block is converted into the 8 × 8 chessboard matrix. Based on the knight tour rules, we traversed each element of the chessboard matrix; however, only unique elements are considered for S-box elements, and a similar procedure is repeated for coming chessboards until the completion of required length of the S-box. Initial position of the first block of the knight’s tour chain is calculated throughr = TRNG [0] mod 8, c = TRNG [1] mod 8, and the initial positions of other knights’ tour chains are dependent on the second last and the last element of the S-box, which are calculated through r = S-box [n − 1] mod 8, c = S-box [n] mod 8. The entire step-by-step process of this phase from true random numbers input to dynamic S-boxes generation is represented in the flowchart of Figure 4. This phase is depicted in the following Figure 5. The reverse S-box algorithm is shown in the following (Algorithm 1). From the dynamically generated S-boxes stream, we picked two S-boxes randomly as sample which are shown in Tables 2 and 3, and their reverse S-boxes are also shown in Tables 4 and 5, respectively. The maximum nonlinearity score of our sample S-boxes is higher or equal to the recently published S-boxes (from 2020 to 2021).Figure 4
Flowchart of dynamic S-boxes generation based on knight’s tour chain.Figure 5
Dynamic generation of S-boxes based on knight’s tour chain.Table 2
Substitution box 1.
1062205241124201049688240170911524686197230174155761851753114210323912240113208228782121829110854370271206628189126362321381652341624323160235974890101982506453873141538171203206213525211114592238631301861801231924251891968458143325982198112224247641771781481842332002221071051952011871542361631092192541372102412042121393424824974202253524722619123114207118171911932171441692371357131301219533141991191461001661822557221520918877993511624218871321021581521506221155164801621252251331831171795120560658152136922341541764624419401561723956161227147931296716822124525136172141281676122922111539414915150216491593710127726834413442231797568108173157140191181190Table 3
Substitution box 2.
2542401871115115515310010320114407214158631802091382169276018621975210925124895191247110107582102620390168121250662265010417646659361832451348621674423820716110202991716521716780551288275200401821471741961561201921161361641884851521663362230137129102612235415934592461952131705125322912612214024198772371794719130130118185224243453622714910623968221189219150108131611541122421722317813513116023112924431255173392332051988920182158249139181212531631571272086410585142184145293717511112522241172327687843542123492352492101912041947913396321569671461908883114111917723413238742362523287822220574321122519941941971437020673162562522821881115114171113148193247214Table 4
Reverse S-box 1.
2044721358526223919312237227134146153194512201701336332265332182404043351492392152124167462366420728198244382426320113157234232189130671991792081479093191224177799919242214248196396916165127247201653224618168942418937151719875814077212229151856601661575917325710801072491153675962913613168187138155411502783518345238222213801481721852437321911848123252662491143761562111022301762311752281121920525117423554209182114180491582232151441113920625018222001001011888225415918610321811111644425525384141203109881695154105110128701211907113730163119178122195221162233142341161216106197971841322103122517245471045055113145782610120169522022171498125126618674129117160Table 5
Reverse S-box 2.
1121519225187895258165973439614013208626616331162242281461982443821226181122154207921031931291822211577623519423159128491208819646109261701017124323036104229993151755044210134209239331224122274190117227204702477321419217756191213161402011995123630206251166572009884717613235139276318414325124924884188124217824211319532185112173721521231492202055514885951816711421617823810180211782521311384906142581172141021501412421718667916941201082501451567918348218147119161687753179125232871362121218325320310680237160234759643920215924061174173723216910725516457682461372291351861001262334513024511194151189158219197223118601331115144127153541052542916643282241100155


## 5. Results and Evaluation

In the results and evaluation section, our proposed S-boxes are evaluated by standard S-box evaluation criteria which includes nonlinearity score, bit independence criterion, linear approximation probability, strict avalanche criterion, and differential approximation probability.Algorithm 1: ReverseSbox (S-box).
in: 2D array of integers, sbox [16, 16];out: 2D array of integers, ReverseSbox [16, 16];(1)
ReverseSbox ⟶ |16||16|(2)
for row ⟶ 0 … (16) do(3)
for col ⟶ 0 … (16) do(4)
rowIS ⟶ sbox row, coldiv 16(5)
colIS ⟶ sbox row, colmod 16(6)
value ⟶ row∗16 + col(7)
ReverseSbox rowIS, colIS ⟶value(8)
end for(9)
end for(10)
return ReverseSbox


### 5.1. Nonlinearity

Among all cryptographic properties, nonlinearity is the most important one. The main purpose of S-box is to gain nonlinear change from secret message to the ciphered message. For a strong encryption scheme, the mapping between input and output in an S-box must be nonlinear. The nonlinearity of the cryptographic algorithm is represented by the nonlinearity score. Nonlinearity is defined as the smallest difference of the Boolean function to the bunch of affine functions. The nonlinearity score determine the total number of bits altered to get the closest affine function in the Boolean truth table. It calculates the distance between the set of all affine functions and Boolean function. When the initial distance is obtained, the nearest affine function is achieved by inverting the bit values in the truth table of the Boolean function. By using walsh spectrum, the nonlinearity of the Boolean function is computed through [46]:(1)Ng=2n−11−2−nmaxϕεGF2nSgϕ,Sgφ is defined as(2)Sgφ=∑ϕ∈GF2n−1gx⊕x.ϕ,where φ is a n-bit vector and φ∈GF2n.x.φ represents the bit-wise dot product of x and φ:(3)x.φ=x1⊕φ1+x2⊕φ2⋯+xn⊕φn.S-box having high nonlinearity creates difficult for attacker to perform linear cryptanalysis. The maximum nonlinearity scores of our proposed Sbox-1 and Sbox-2 are 110 and 110, respectively, which is higher or equal to the recently published S-boxes. Detailed comparative analysis is shown in Table6.Table 6
Nonlinearity of state-of-the-art S-boxes.
Recently published S-boxesMaximum nonlinearity achieved[83], 2021−108[85], 2021−110[87], 2021−108[89], 2020−108[91], 2020−110[93], 2020−108[95], 2020−108[97], 2020−108[99], 2020−104[99], 2020−108[98], 2020−106[101], 2020−108[102], 2020−110[104], 2021−108[105], 2021−110[84], 2021−110[86], 2021−110[88], 2021−108[90], 2021−110[92], 2020−102[94], 2020−107[96], 2020−104[98], 2020−106[100], 2020−105[101], 2020−106[95], 2020−108[93], 2020−108[103], 2020−108[104], 2021−108[106], 2021−108


### 5.2. Strict Avalanche Criteria (SAC)

Strict avalanche criteria is the another crucial property for evaluating and according to SAC, if a single input bit is altered, all output bits will shift with probability of 1/2. SAC examined the effects of avalanche affects in encryption scheme. The modification at the input series induces a significant change in output series. SAC computes the number of output bits altered caused by inverting a single bit of input. To make the system more reliable, the output vector needed to be deviate with half probability, when one bit of input is inverted. Dependency matrix is determined to evaluate the SAC property. For an S-box that satisfies SAC property, all values were close to the ideal value of 0.5 in its dependence matrix. Dependency matrix offsets computed through equation (4) [46]. The SAC results of S-box-1 and S-box-2 are shown in Tables 7 and 8 and scores of our S-box-1 and S-box-2 are 0.495 and 0.50, respectively, which are the ideal scores for the secure S-boxes.(4)Sg=1n2∑1≤r≤n∑1≤w≤n12−Qr,wg,where(5)Qr,wg=2−n∑xεBngwx⊕gwx⊕er,er=θr,1θr,2…θr,nT,[]T is the transpose of matrix θr,w=0,r≠w or. θr,w=1,r=w.Table 7
SAC results of S-box-1.
0.5000000.5625000.4687500.4531250.5000000.4218750.4531250.5000000.4375000.5156250.4687500.4687500.5156250.5000000.5468750.4375000.4687500.5468750.4843750.5156250.5000000.5312500.5468750.5000000.4531250.5000000.5000000.5000000.4843750.4531250.5156250.5468750.4687500.5625000.5000000.5000000.4843750.4375000.4843750.5000000.4062500.5468750.5937500.4843750.4531250.3906250.5312500.5000000.4375000.4843750.5781250.4531250.5156250.5468750.4375000.4843750.5468750.5156250.5312500.5000000.5625000.4375000.5156250.515625Table 8
SAC results of S-box-2.
0.5312500.5468750.5468750.4687500.4218750.4375000.5468750.5000000.5468750.5312500.4062500.4843750.5625000.4687500.4843750.4531250.5156250.4843750.5000000.5781250.6406250.5156250.5468750.4375000.5625000.4687500.4531250.4375000.5000000.5468750.5468750.5468750.5937500.5468750.5312500.5937500.5000000.5000000.4687500.5312500.5000000.4687500.5312500.5312500.4375000.4843750.4843750.4843750.4843750.4218750.5468750.4843750.4375000.5156250.5156250.5468750.5000000.4531250.5781250.4687500.5625000.5312500.5625000.421875


### 5.3. BIT Independent Criterion (BIC)

BIC requires that all avalanche variables for a given set of avalanche vectors must be pair-wise independent. By modifying the input bits, BIC is used to study the behaviour of the output bits. When the output bits behave independent of one another, the S-box holds the BIC property. If any single input biti is inverted, BIC states that output bits j and k will alter independently. This will enhance the effectiveness of confusion function. The coefficient of correlation is used to determine the independence among pair of avalanche variables. High bit independence is required to make system design incomprehensible. The bit independence of the jth and kth bits of Bei is [46]: in Tables 9 and 10, we can see that our randomly picked S-box-1 and S-box-2 fully fill the BIT independent criterion.(6)BICbj,bk=max1≤i≤ncorrbjei,bjei.Table 9
BIC independent matrix of S-box-1.
—0.4804690.4843750.4648440.5097660.5078120.5175780.5214840.480469—0.5117190.5136720.4843750.4863280.4765620.4941410.4843750.511719—0.4980470.5078120.4941410.5039060.4863280.4648440.5136720.498047—0.4941410.5058590.5019530.4960940.5097660.4843750.5078120.494141—0.5097660.4804690.4707030.5078120.4863280.4941410.5058590.509766—0.4941410.4980470.5175780.4765620.5039060.5019530.4804690.494141—0.5097660.5214840.4941410.4863280.4960940.4707030.4980470.509766—Table 10
BIC independent matrix of S-box-2.
—0.5019530.4980470.5019530.4882810.5292970.4863280.4843750.501953—0.5000000.5019530.4843750.5136720.4667970.5097660.4980470.500000—0.5078120.5273440.4746090.5078120.4863280.5019530.5019530.507812—0.5195310.5214840.4941410.5117190.4882810.4843750.5273440.519531—0.5234380.5156250.5214840.5292970.5136720.4746090.5214840.523438—0.4785160.5039060.4863280.4667970.5078120.4941410.5156250.478516—0.5195310.4843750.5097660.4863280.5117190.5214840.5039060.519531—S-box function (h) is described as: h: {0, 1}n ⟶{0, 1}nBIC parameter for the S-box function is expressed as(7)BICh=max1≤j,k≤nBICbj,bk.The change in output bits is a crucial parameter in determining the cipher’s strength. When the changes in output bits contrast with the input bit sequence shows sufficient independence, the mapping technique will be difficult to understand.


### 5.4. Linear Approximation Probability (LP)

LP is the cryptographic property which measures the resistance of S-box against the linear attacks. LP analysis intends to measure the maximum imbalance of the event. LP is measured by determining the total number of coincident input bits with the output bits. The input bits uniformity must be identical to the output bits. Each input bit is individually evaluated, and its results are tested in the output bits.γ1 and γ2 masks are selected randomly to determine the mask of all output and input values. The mathematical expression of determining linear approximation probability is as follows [46]: the maximum LP of S-box-1 and S-box-2 is 0.125, which is also satisfies LP criteria.(8)LPf=maxγ1,γ2≠0xɛX|x.γ1=Sx.γ22n−12,where γ1 and γ2 represents the input and output mask in the above expression. Linear approximation probability is calculated by using these masks. X represents the set of all possible inputs and 2n is the total number of elements in the set. S-box with low LP value is robust enough against different linear approximation attacks.


### 5.5. Differential Approximation Probability (DP)

The resistance of S-box to the differential attacks is assessed through the DP. DP is the probability of particular change in output bits caused by the change in input bits. An S-box must possess differential uniformity which means that each input differential is connected to the specific output differential. The XOR values of all output must have equal probability to the XOR values of all input. The differential uniformity is measured by given expression [46]:(9)DPΔx⟶Δy=#xɛX|Sx⊕Sx⊕Δx=Δy2n,where X represents the set of all possible input values and 2n is the total number of elements in set. The maximum differential probability value a system could achieve is 4/256. The lowest value of DP means the high security of the S-box against differential approximation attacks. In Tables 11 and 12, we can see that our randomly picked S-box-1 and S-box-2 fully fill the DP criterion.Table 11
DP of S-box-1.
0.000000.023430.031250.031250.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.031250.031250.031250.023430.031250.023430.023430.023430.031250.023430.023430.031250.023430.023430.023430.031250.031250.031250.031250.023430.023430.031250.023430.031250.0390620.023430.023430.023430.023430.023430.023430.023430.031250.023430.031250.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.039060.023430.023430.031250.023430.031250.031250.031250.023430.023430.023430.031250.031250.031250.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.031250.031250.023430.031250.031250.031250.023430.031250.031250.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.031250.023430.023430.023430.031250.023430.031250.015620.031250.023430.023430.023430.023430.023430.023430.023430.015620.023430.023430.031250.023430.023430.023430.031250.023430.031250.015620.023430.023430.023430.031250.039060.031250.023430.031250.031250.023430.023430.031250.031250.023430.031250.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.031250.023430.031250.031250.023430.023430.023430.023430.031250.015620.023430.023430.023430.031250.023430.031250.023430.023430.039060.031250.023430.023430.031250.031250.023430.023430.023430.023430.031250.023430.023430.023430.023430.031250.023430.023430.031250.023430.039060.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.031250.015620.023430.023430.015620.02343Table 12
DP of S-box-2.
0.000000.023430.023430.031250.023430.0156250.023430.031250.039060.023430.031250.023430.031250.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.031250.023430.023430.023430.031250.0156250.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.031250.023430.031250.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.023430.031250.023430.023430.031250.031250.031250.023430.023430.023430.031250.023430.023430.039060.031250.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.023430.023430.023430.031250.023430.031250.031250.031250.039060.023430.031250.023430.023430.023430.023430.023430.031250.031250.031250.023430.023430.023430.023430.023430.031250.031250.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.031250.031250.023430.023430.031250.031250.031250.031250.023430.023430.031250.031250.031250.031250.039060.023430.031250.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.023430.031250.023430.031250.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.031250.023430.0156250.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.031250.031250.023430.023430.031250.031250.023430.031250.023430.023430.031250.023430.023430.023430.031250.023430.031250.023430.023430.023430.023430.031250.023430.031250.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.031250.023430.031250.031250.039060.023430.023430.023430.0156250.0156250.031250.023430.023430.023430.023430.039060.023430.031250.031250.031250.031250.023430.023430.023430.031250.023430.03906


## 5.1. Nonlinearity

Among all cryptographic properties, nonlinearity is the most important one. The main purpose of S-box is to gain nonlinear change from secret message to the ciphered message. For a strong encryption scheme, the mapping between input and output in an S-box must be nonlinear. The nonlinearity of the cryptographic algorithm is represented by the nonlinearity score. Nonlinearity is defined as the smallest difference of the Boolean function to the bunch of affine functions. The nonlinearity score determine the total number of bits altered to get the closest affine function in the Boolean truth table. It calculates the distance between the set of all affine functions and Boolean function. When the initial distance is obtained, the nearest affine function is achieved by inverting the bit values in the truth table of the Boolean function. By using walsh spectrum, the nonlinearity of the Boolean function is computed through [46]:(1)Ng=2n−11−2−nmaxϕεGF2nSgϕ,Sgφ is defined as(2)Sgφ=∑ϕ∈GF2n−1gx⊕x.ϕ,where φ is a n-bit vector and φ∈GF2n.x.φ represents the bit-wise dot product of x and φ:(3)x.φ=x1⊕φ1+x2⊕φ2⋯+xn⊕φn.S-box having high nonlinearity creates difficult for attacker to perform linear cryptanalysis. The maximum nonlinearity scores of our proposed Sbox-1 and Sbox-2 are 110 and 110, respectively, which is higher or equal to the recently published S-boxes. Detailed comparative analysis is shown in Table6.Table 6
Nonlinearity of state-of-the-art S-boxes.
Recently published S-boxesMaximum nonlinearity achieved[83], 2021−108[85], 2021−110[87], 2021−108[89], 2020−108[91], 2020−110[93], 2020−108[95], 2020−108[97], 2020−108[99], 2020−104[99], 2020−108[98], 2020−106[101], 2020−108[102], 2020−110[104], 2021−108[105], 2021−110[84], 2021−110[86], 2021−110[88], 2021−108[90], 2021−110[92], 2020−102[94], 2020−107[96], 2020−104[98], 2020−106[100], 2020−105[101], 2020−106[95], 2020−108[93], 2020−108[103], 2020−108[104], 2021−108[106], 2021−108


## 5.2. Strict Avalanche Criteria (SAC)

Strict avalanche criteria is the another crucial property for evaluating and according to SAC, if a single input bit is altered, all output bits will shift with probability of 1/2. SAC examined the effects of avalanche affects in encryption scheme. The modification at the input series induces a significant change in output series. SAC computes the number of output bits altered caused by inverting a single bit of input. To make the system more reliable, the output vector needed to be deviate with half probability, when one bit of input is inverted. Dependency matrix is determined to evaluate the SAC property. For an S-box that satisfies SAC property, all values were close to the ideal value of 0.5 in its dependence matrix. Dependency matrix offsets computed through equation (4) [46]. The SAC results of S-box-1 and S-box-2 are shown in Tables 7 and 8 and scores of our S-box-1 and S-box-2 are 0.495 and 0.50, respectively, which are the ideal scores for the secure S-boxes.(4)Sg=1n2∑1≤r≤n∑1≤w≤n12−Qr,wg,where(5)Qr,wg=2−n∑xεBngwx⊕gwx⊕er,er=θr,1θr,2…θr,nT,[]T is the transpose of matrix θr,w=0,r≠w or. θr,w=1,r=w.Table 7
SAC results of S-box-1.
0.5000000.5625000.4687500.4531250.5000000.4218750.4531250.5000000.4375000.5156250.4687500.4687500.5156250.5000000.5468750.4375000.4687500.5468750.4843750.5156250.5000000.5312500.5468750.5000000.4531250.5000000.5000000.5000000.4843750.4531250.5156250.5468750.4687500.5625000.5000000.5000000.4843750.4375000.4843750.5000000.4062500.5468750.5937500.4843750.4531250.3906250.5312500.5000000.4375000.4843750.5781250.4531250.5156250.5468750.4375000.4843750.5468750.5156250.5312500.5000000.5625000.4375000.5156250.515625Table 8
SAC results of S-box-2.
0.5312500.5468750.5468750.4687500.4218750.4375000.5468750.5000000.5468750.5312500.4062500.4843750.5625000.4687500.4843750.4531250.5156250.4843750.5000000.5781250.6406250.5156250.5468750.4375000.5625000.4687500.4531250.4375000.5000000.5468750.5468750.5468750.5937500.5468750.5312500.5937500.5000000.5000000.4687500.5312500.5000000.4687500.5312500.5312500.4375000.4843750.4843750.4843750.4843750.4218750.5468750.4843750.4375000.5156250.5156250.5468750.5000000.4531250.5781250.4687500.5625000.5312500.5625000.421875


## 5.3. BIT Independent Criterion (BIC)

BIC requires that all avalanche variables for a given set of avalanche vectors must be pair-wise independent. By modifying the input bits, BIC is used to study the behaviour of the output bits. When the output bits behave independent of one another, the S-box holds the BIC property. If any single input biti is inverted, BIC states that output bits j and k will alter independently. This will enhance the effectiveness of confusion function. The coefficient of correlation is used to determine the independence among pair of avalanche variables. High bit independence is required to make system design incomprehensible. The bit independence of the jth and kth bits of Bei is [46]: in Tables 9 and 10, we can see that our randomly picked S-box-1 and S-box-2 fully fill the BIT independent criterion.(6)BICbj,bk=max1≤i≤ncorrbjei,bjei.Table 9
BIC independent matrix of S-box-1.
—0.4804690.4843750.4648440.5097660.5078120.5175780.5214840.480469—0.5117190.5136720.4843750.4863280.4765620.4941410.4843750.511719—0.4980470.5078120.4941410.5039060.4863280.4648440.5136720.498047—0.4941410.5058590.5019530.4960940.5097660.4843750.5078120.494141—0.5097660.4804690.4707030.5078120.4863280.4941410.5058590.509766—0.4941410.4980470.5175780.4765620.5039060.5019530.4804690.494141—0.5097660.5214840.4941410.4863280.4960940.4707030.4980470.509766—Table 10
BIC independent matrix of S-box-2.
—0.5019530.4980470.5019530.4882810.5292970.4863280.4843750.501953—0.5000000.5019530.4843750.5136720.4667970.5097660.4980470.500000—0.5078120.5273440.4746090.5078120.4863280.5019530.5019530.507812—0.5195310.5214840.4941410.5117190.4882810.4843750.5273440.519531—0.5234380.5156250.5214840.5292970.5136720.4746090.5214840.523438—0.4785160.5039060.4863280.4667970.5078120.4941410.5156250.478516—0.5195310.4843750.5097660.4863280.5117190.5214840.5039060.519531—S-box function (h) is described as: h: {0, 1}n ⟶{0, 1}nBIC parameter for the S-box function is expressed as(7)BICh=max1≤j,k≤nBICbj,bk.The change in output bits is a crucial parameter in determining the cipher’s strength. When the changes in output bits contrast with the input bit sequence shows sufficient independence, the mapping technique will be difficult to understand.


## 5.4. Linear Approximation Probability (LP)

LP is the cryptographic property which measures the resistance of S-box against the linear attacks. LP analysis intends to measure the maximum imbalance of the event. LP is measured by determining the total number of coincident input bits with the output bits. The input bits uniformity must be identical to the output bits. Each input bit is individually evaluated, and its results are tested in the output bits.γ1 and γ2 masks are selected randomly to determine the mask of all output and input values. The mathematical expression of determining linear approximation probability is as follows [46]: the maximum LP of S-box-1 and S-box-2 is 0.125, which is also satisfies LP criteria.(8)LPf=maxγ1,γ2≠0xɛX|x.γ1=Sx.γ22n−12,where γ1 and γ2 represents the input and output mask in the above expression. Linear approximation probability is calculated by using these masks. X represents the set of all possible inputs and 2n is the total number of elements in the set. S-box with low LP value is robust enough against different linear approximation attacks.


## 5.5. Differential Approximation Probability (DP)

The resistance of S-box to the differential attacks is assessed through the DP. DP is the probability of particular change in output bits caused by the change in input bits. An S-box must possess differential uniformity which means that each input differential is connected to the specific output differential. The XOR values of all output must have equal probability to the XOR values of all input. The differential uniformity is measured by given expression [46]:(9)DPΔx⟶Δy=#xɛX|Sx⊕Sx⊕Δx=Δy2n,where X represents the set of all possible input values and 2n is the total number of elements in set. The maximum differential probability value a system could achieve is 4/256. The lowest value of DP means the high security of the S-box against differential approximation attacks. In Tables 11 and 12, we can see that our randomly picked S-box-1 and S-box-2 fully fill the DP criterion.Table 11
DP of S-box-1.
0.000000.023430.031250.031250.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.031250.031250.031250.023430.031250.023430.023430.023430.031250.023430.023430.031250.023430.023430.023430.031250.031250.031250.031250.023430.023430.031250.023430.031250.0390620.023430.023430.023430.023430.023430.023430.023430.031250.023430.031250.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.039060.023430.023430.031250.023430.031250.031250.031250.023430.023430.023430.031250.031250.031250.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.031250.031250.023430.031250.031250.031250.023430.031250.031250.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.031250.023430.023430.023430.031250.023430.031250.015620.031250.023430.023430.023430.023430.023430.023430.023430.015620.023430.023430.031250.023430.023430.023430.031250.023430.031250.015620.023430.023430.023430.031250.039060.031250.023430.031250.031250.023430.023430.031250.031250.023430.031250.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.031250.023430.031250.031250.023430.023430.023430.023430.031250.015620.023430.023430.023430.031250.023430.031250.023430.023430.039060.031250.023430.023430.031250.031250.023430.023430.023430.023430.031250.023430.023430.023430.023430.031250.023430.023430.031250.023430.039060.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.031250.015620.023430.023430.015620.02343Table 12
DP of S-box-2.
0.000000.023430.023430.031250.023430.0156250.023430.031250.039060.023430.031250.023430.031250.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.031250.023430.023430.023430.031250.0156250.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.031250.023430.031250.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.023430.031250.023430.023430.031250.031250.031250.023430.023430.023430.031250.023430.023430.039060.031250.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.023430.023430.023430.031250.023430.031250.031250.031250.039060.023430.031250.023430.023430.023430.023430.023430.031250.031250.031250.023430.023430.023430.023430.023430.031250.031250.023430.023430.023430.023430.023430.023430.031250.023430.023430.031250.031250.031250.023430.023430.031250.031250.031250.031250.023430.023430.031250.031250.031250.031250.039060.023430.031250.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.023430.031250.023430.031250.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.031250.023430.0156250.031250.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.023430.023430.023430.031250.031250.023430.023430.031250.031250.023430.031250.023430.023430.031250.023430.023430.023430.031250.023430.031250.023430.023430.023430.023430.031250.023430.031250.023430.023430.023430.023430.023430.023430.031250.023430.023430.023430.031250.023430.031250.031250.039060.023430.023430.023430.0156250.0156250.031250.023430.023430.023430.023430.039060.023430.031250.031250.031250.031250.023430.023430.023430.031250.023430.03906


## 6. Conclusion

The protection of confidential information is a global issue, and block encryption algorithms are the most reliable option. The actual strength of the block encryption algorithms against several attacks is entirely dependent on S-boxes. Currently in the literature, algebraic structure-based and chaos-based techniques are highly used for the construction of S-boxes because both these techniques have favourable features for S-box construction, but many attacks of these techniques have been identified. In this paper, we purposed a novel technique for the dynamic generation of S-boxes that is safe against the existing attacks of algebraic structure-based and chaos-based techniques. True randomness has been universally recognized as the ideal method for security primitive because true random numbers are unpredictable, irreversible, and unreproducible. Rather than algebraic structure- and chaos-based techniques, our proposed technique depends on inevitable high-quality randomness which exists in underwater acoustics waves. According to our knowledge first time, this type of research has been conducted, in which natural randomness of underwater acoustic waves and knight’s tour problem has been used for the generation of block cipher’s substitution box. The proposed method satisfies all standard evaluation tests of S-boxes construction and true random numbers generation. Additionally, our dynamically generated S-boxes have better or equal strength, over the latest published S-boxes (2020 to 2021). In the future, we will extend this research for automatic key generation and optimization using knight’s tour.



---

*Source: 8338508-2022-05-20.xml*