# RK-AES: An Improved Version of AES Using a New Key Generation Process with Random Keys

Authors: Rahul Saha; G. Geetha; Gulshan Kumar; Tai-hoon Kim
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Advanced Encryption Standard (AES) is a standard algorithm for block ciphers for providing security services. A number of variations of this algorithm are available in network security domain. In spite of the strong security features, this algorithm has been recently broken down by the cryptanalysis processes. Therefore, it is required to improve the security strength of this algorithm as AES is popular in commercial use. In this paper, we have shown the reasons of the loopholes in AES and also have provided a solution by using our Symmetric Random Function Generator (SRFG). The use of randomness in the key generation process in block cipher is novel in this domain. We have also compared our results with the original AES based upon some parameters such as nonlinearity, resiliency, balancedness, propagation characteristics, and immunity. The results show that our proposed version of AES is better in withstanding attacks.


---

## Body

## 1. Introduction

Cryptology is an important domain of security measure for providing confidentiality, authentication, and other services [1]. It contains two major parts as cryptography and cryptanalysis. With the progress of technology, where the new cryptographic algorithms are emerging, the cryptanalysis processes are also getting improved; to countermeasure those more secure algorithms are getting developed. So, the cyclic process of cryptography and cryptanalysis goes on. The trend of converging to IoT exhibits an urge of improving the cryptographic algorithms for applications to be secure [2, 3]. Cryptographic algorithms are broadly categorized in two ways: (a) block ciphers and stream ciphers depending upon the format of the message processing; (b) symmetric and asymmetric depending upon number of keys used for the algorithms [1]. Designing such algorithms is another concern where a number of principles are needed to be maintained such as key size, message size, number of rounds, round function, and so on. The selection of key and its size is a major concerning factor in cryptography. A weak key can reveal the plaintext message with least time. Though we know that cryptographic algorithms face brute-force attacks problems, brute-force is not considered as its complexity is higher than any other process of cryptanalysis. The objective of a third party attacker is to break the ciphertext code or to reveal the key or part of the key to get access of the plaintext. So, the weak keys must be avoided in the algorithms. Further, it may happen that the previously considered strong key is now made weak by the sophisticated technology or large computational abilities of the attackers. So, the need of strength analysis to withstand with attacks makes the evolving changes in the cryptographic algorithms.Cryptographic algorithms primarily depend on the structure of the algorithms and their corresponding functions [4]. Apart from using basic gates such as AND, OR, NOT, and XOR in the algorithms, researchers also have shown some specialized Boolean functions for the symmetric property. The generic Boolean functions have created the basic functionalities of generating any cryptographic function. However, the technology progress and enhancing computational ability of the attackers have urged a need of introducing new features in the function generators so that they can provide more strength to the ciphers. Physical Unclonable Functions (PUFs) [5, 6] are providing solutions for this but as per the cryptographic features requirements; PUFs are not efficient for cryptographic algorithms. Further, PUF is applicable for FPGA implementation as it is more hardware oriented. Though the objective of the presented approach and PUF is same their orientation and process is totally different. Moreover, it has been shown that PUF is used as seed which again leads to the tendency of pseudorandomness in key generation process which is not desirable. Balancedness, nonlinearity, resiliency, immunity, correlation, and propagation characteristics are some of the important parameters to evaluate the strength of the ciphers. In this paper, we have considered Advanced Encryption Standard (AES) for our experimentation of randomness feature. We have attributed the key generation module of AES undergoing through our Symmetric Random Function Generator (SRFG) [7]. We have evaluated the modified AES with the parameters said above.The rest of the paper has been organized as follows. Section2 summarizes the various attacks on AES algorithm. Section 3 describes the original AES algorithm. Section 4 shows the proposed modification for AES and in Section 5 we have explained its properties. Section 6 analyses the security and Section 7 compares the related results. Finally, Section 8 concludes the paper.


## 2. Related Work

One of the most popular and commercialized algorithms is AES. This algorithm provides the encryption for web security processes as used by different applications such as e-commerce, router applications, and WiFi security. Being so rigorously used in real life applications, AES faces a number of attacks. Some of the recent attacks are mentioned below.A new kind of fault base attack has been proposed in [8] which uses zero valued sensitivity model for masked AES. Combining the Faulty Sensitivity Analysis (FSA) and zero valued sensitivity, the proposed method of cryptanalysis is able to break code of the S-boxes in masked AES. The attack procedure shows that the zero value input of S-box reveals the key eventually. The authors in the paper [9] have shown a differential faulty approach used in the mix column component of AES. The results show that AES-128 is breakable by such process only using two faulty inputs of ciphertexts. This attack has been proved better as compared to other differential attacks on AES as shown in [10–12]. Another improved version of faulty attack on AES has been executed in the paper [13]. The authors show that a single random byte fault at the input of the eighth round of the AES algorithm is sufficient to deduce the block cipher key. Simulations show that when two faulty ciphertexts pairs are generated, the key can be exactly deduced without any brute-force search. The minimal fault against AES has been used in [14]. The authors show that AES-192 is breakable by using two pairs of correct and fault ciphertexts whereas AES-256 is broken by using three pairs of correct and fault ciphertexts. The work shown previously in [13] was having a key space of 232 which has been reduced by the authors in [15]. Key recovery attacks on AES have been described in [16]. In this paper, the authors have shown practical complexity based attacks against AES-256. The use of two related keys and 239 time complexity has been proved to be sufficient to recover the complete 256-bit key of a 9-round version of AES-256. Another attack works on 10 round version of AES-256 in 245 time complexity. An improved version of the previous related key attack has been shown in [17] against round transformation and key expansion module in AES. The round has been now minimized from 9th to 7th which means that AES is vulnerable even for the starting rounds. The complexity of the attack has also been reduced from 2192 to 2104. Another voltage based fault induction method has been introduced in [18]. The authors show a fault model for a constantly underfed RISC CPU. The faults are described in terms of position, recurring patterns, and timing, then the corresponding errors induced in the computation outcomes are specified. The model also support multibit patterns. The use of biased faults also provides an efficient way to for fault injection attacks in cryptanalysis. Such a procedure has been shown in [19].A collision based attack against AES-192/256 has been shown in [20]. The authors have used 4-round distinguisher for 7-round reduced AES. In the paper [21], the authors have used variable key for AES sing pseudorandom number generator for providing better security to the algorithm, but the approach faces the problem of using biased keys against AES rounds. Biased keys are able to reveal the pseudorandomness of the approach and the key is deduced further by applying differential methods or fault injection as shown before. Multiple deductions-based algebraic trace driven cache attack on AES has been shown in [22]. The behaviour of the cache reveals the input whole or partially. Same input to a particular module and the changes of the cache properties are the key features of this approach. The authors have identified the causes of a bias fault and also have compared different biased fault attacks introduced till. Quantum related key attacks have been shown in [23].A solution to the fault based injection attacks has been provided in [24]. The proposed scheme is independent of S-box and inverse S-box and achieves more than 95% fault coverage. A recent approach against fault injection or fault analysis has been shown in [25]. It combines the principles of redundancy with that of fault space transformation to achieve security against both DFA and DFIA based attacks on AES-like block ciphers.After surveying the attacks on AES, it is obvious that fault injection attacks are more efficient in revealing the key in AES. Such fault injections are using the biased input too to distinguish the subkeys or other parts of the algorithm. Moreover, as AES is depending upon finite field operations of 8-bit bytes, the attacks are also executable with finite quantified complexities as we have seen above. The biased inputs along with fault bytes create error in the process and those are denoted for performing differential analysis or linear analysis. Eventually, the key is revealed. Therefore, to overcome such problems, we have introduced the randomness and the balanced symmetric feature in the functional output, specifically in the keys. We have named this modified AES as Random Key AES (RK-AES). As a result, even though attackers are deducing a part of key or injecting a biased fault, the fault will be converted to a symmetric output rather than revealing the original key or plaintext.The main contributions of our research work are as follows:(1)
Use of randomness in key generation process of AES.(2)
Confirming high nonlinearity, resiliency, balancedness, propagation, and immunity in key generation process.(3)
Ensuring high confusion and avalanche effect in key generation.


## 3. AES Algorithm

The Advanced Encryption Standard (AES) [26] was published by the National Institute of Standards and Technology (NIST) in 2001. AES is a symmetric block cipher where a single key is used for both encryption and decryption process. The input and output for the AES algorithm each consist of sequences of 128 bits. The key used in this algorithm consists of 128, 192, or 256 bits. AES operates on 8-bit bytes. These bytes are interpreted as the elements of finite field using the following polynomial representation:(1)fx=bn-1xn-1+bn-2xn-2+⋯+b1x+b0=∑i=0n-1bixiwhere each bi is having the value of 0 or 1.The 128-bit input block of AES is arranged in a state matrix of size 4 × 4 as shown in Figure1. The elements of the matrix are represented by the variable bij where 0≤i,j≤3 and i,j denotes the row and column number, respectively. Depending upon the size of the bits in keys variables rounds are allowed for AES. For our experimentation we have used key size of 256-bit concept and therefore, the number of rounds used is 14 rounds represented as Nr. Key scheduling algorithm is also used in AES to provide keys to each of the rounds. The design of the key scheduling algorithm is such that the revealing any round key deduces the original input key from which the round keys are derived. The input state matrix is processed by the various round transforms. The state matrix evolves as it passes through the various steps of the cipher and finally produces the ciphertext. Each round in AES follows the following steps.Figure 1
State matrix representation.SubBytes. This is a nonlinear step in the AES. It uses an S-box applied to the bytes of the state matrix. Each byte of the state matrixes is replaced by its multiplicative inverse, followed by an affine mapping as follows:(2)bi′=bi⊕bi+4mod8⊕bi+5mod8⊕bi+6mod8⊕bi+7mod8⊕ci,for0≤i<8where bi is the ith bit of the byte and ci is the ith bit of a byte c with the value 63 or 01100011. Thus the input byte x is related to the output y of the S-box by the relation, y=A.x-1+B, where A and B are constant matrices [27].Shift Rows. The last three rows of the state matrix is rotated by a certain number of byte positions. It is executed as follows:(3)sr,c′=sr,c+shiftr+NbmodNbfor0<r<4and0<c<Nbwhere Nb is the number of words in the state matrix (each column in the state matrix is considered as word). In AES, Nb = 4 always as the input size is 128 bits and arranged in state matrix of size 4 × 4. Each cell in the state matrix is denoted as s with the index of row r and column c.MixColumns. This transformation operates on the state matrix column-by-column, considering each column as a four-term polynomials over GF (28) and multiplied modulo x4+1 with a fixed polynomial a(x), given by(4)ax=03x3+01x2+01x1+02The multiplication process with the columns of state matrix is given by(5)s′x=ax⊗sxwhere ⊗ is multiplication modulo of polynomials and s(x) is a state in the state matrix.AddRoundKey. In this process, a round key is added to the state by a simple bitwise XOR operation. Each round key is having the size of Nb words from the key schedule. Those Nb words are each added to the columns of the state matrix to satisfy the following condition:(6)s0,c′,s1,c′,s2,c′,s3,c′=s0,c,s1,c,s2,c,s3,c⊕wround×Nb+c,for0≤c<Nbwhere ⊕ is the bitwise XOR and round is the round number at which round key is added and 0≤round<Nr.All these steps are performed for each of the round in the AES excluding the last round. In the last round the MixColumn step is not performed. For a 14-round AES, the round function process is shown in Figure2. One of the important parts of the round function stages is adding of round keys as these keys are generated by the key expansion routine. The key expansion generates a total of Nb(Nr+1) words: the algorithm requires an initial set of Nb words, and each of the Nr rounds requires Nb words of key data. The resulting key schedule consists of a linear array of 4-byte words, denoted by [wi], 0≤i≤Nb(Nr+1). It uses a function SubWord  that takes these 4-byte words as input and applies S-box to each of these words. Another function Rotword  is used to perform a circular permutation. The round constant array Rcon[i] contains the values specified as [xi-1,{00},{00},{00}] with xi-1 powers of x in the following equation:(7)Rconi=xi-4/4modx8+x4+x3+x+1,whereiisthecurrentroundThe key expansion routine for 256-bit keys (Nk = 8) is slightly different than for 128- and 192-bit keys. If Nk = 8 and i-4 is a multiple of Nk, then SubWord  is applied to w[i-1] prior to the XOR. Nk is the number of 32-bit words of a key.Figure 2
Round function steps in 14-round AES.


## 4. RK-AES

The main problem in the key expansion of the AES algorithm is that the wordswi generated from the original key are related to each other. If any word is traceable, the overall key is deduced by the differential method or liner methods of cryptanalysis. Though the XOR operation, S-boxes, and the shifting in g function, shown in Figure 3, are providing the confusion characteristics to the algorithm, the reverse engineering process can easily get back to the original key space. Moreover, the biased inputs in the key space reveal the differences between the words to partially gain the key space. To solve this problem in AES, we have modified the key expansion module of AES with Symmetric Random Function Generator (SRFG) [7]. SRFG produces the symmetric balanced output in the sense of the number of 1’s and 0’s in the output string irrespective of the input string. It outputs a combined function comprised of universal GATEs (AND, OR, NOT, and XOR). The expression for the proposed combined function generator is given as(8)fc=⊗fiLwhere i=1,2,…,4, four universal GATES: AND, OR, NOT, and XOR; L represents the expression length (number of terms in the combined function fc); and ⊗ represents the random combination. In our experiments we have used L = 5. To emphasize the randomness in such combined function generator, the above equation can be further expressed in terms of N input variables’ randomness in selection, as shown in (2).(9)fcV1,V2,…,VN=⊗fiLrandV1,V2,…,VNFor, our experimentation, the above equation is rewritten as(10)fcV1,V2=⊗fi5randV1,V2The main objective of adding SRFG in AES is to enable the key expansion module with some randomness feature. This will help to prevent deducing the words of keys even though partial key is in hand. The modified key expansion module has been shown in Figure 4; the changes are highlighted in yellow colour. The randomness of SRFG has been used in three parts: first, in the function of g, secondly, the recursive word generation from key spaces, and thirdly but most prominently, addition of RCi and SRFG for generating the words from w0 to w7. According to Figure 4(a), each column in the key space is considered as wi word. As the key size is 256 bits, we shall have eight words w0,w1,w2,w3,w4,w5,w6,w7 in the very first step. The 8th word, i.e., w7, is going through a function g. This function is also using SRFG just before the output of the function as in Figure 4(b). The output of g is then used to generate the other words processing through a series of SRFGs. The same process is repeated till we get the required number of words for the 14 rounds in AES. For the decryption process, we have saved the generated words and used them reversely with the ciphertext to get back to the plaintext. In future, we shall work upon direct transmission of the keys rather than storing them for decryption.Figure 3
Key expansion for 14-round AES.
(a)
Word key generation (b)
g functionFigure 4
Proposed key expansion for 14 round AES.
(a)
Word key generation (b)
g function


## 5. Feature Analysis of RK-AES

We have emphasized the key generation module of AES-14 round, so that the effect of biased inputs in the key bytes can be removed from deducing the overall key bytes. The keys are deducing if the cryptanalysis process is able to infer a linear or differential equation out of the words generated from the key expansion module. For the cryptanalysis process, it is not always necessary to have the whole key in hand; rather a single part of key if in the capture, the relationship between different words is sufficient in revealing the overall key space. With the progress of cryptanalysis technologies, generating such relations or deducing keys from subkeys is getting faster with less complexity as we have seen in the literature review. We have identified some of the parameters for our proposed key-expansion module for RK-AES such as nonlinearity, balancedness, resiliency, propagation criterion, and immunity. Each wordwi in the key space is comprised of 32 bits (4 bytes) which is considered as 32-bit word vector in our experimentation. Let B2 be the set of all symmetric random combined functions on two variables of all the functions from F22 into F2 where F22=(w1,w2)∣wi∈F2. F2 is the finite field of two elements 0, 1 and ⊕ is any operation of the field F2.Any combined functionfc∈B2 of five terms is expressed as a polynomial which is basically termed as Algebraic Normal Form (ANF) of the function and given as(11)fcw1,w2=⊕λu∏i=12randwiuis,λu∈F2,u∈F22andL∈Z(12)λu=⊕fcv,w⪯u,∀wi=wi1,wi2,…,wi32where(13)wi1,wi2,…,wi32⪯u1,u2,…,u32iff∀i,j,wij≤uiandj=1,2,…,32The output of fc depends on the weight of its input variables (number of 1s in the variable). As a result, fc corresponds to a function gc:{0,,1,…,32}→F2 such that ∀x∈F22,fc(x)=gc(wt(x)). The sequence gc(fc)=(gc0,gc1,…,gc(32)) for 32-bit word vector is considered as simplified value vector of fc. To establish the relation between simplified value vector and arithmetic normal form, (11) can be rewritten as shown in (13).(14)fcw1,w2=⊕λfj⊕∏i=12randwiuiL(15)=⊕λfjXj,Nwhere λf(j), u∈F22, and L∈Z,j={1,2}. Xj,N is the elementary polynomial of degree j with 2 variables. The coefficients of arithmetic normal form of fc are represented by 32-bit vector, λ(fc)={λf(0),λf(1),…,λf(32)}, called simplified vector of ANF of fc.


### 5.1. Nonlinearity

Nonlinearity is an important design characteristic for cryptographic functions used in cryptographic algorithms to prevent different types of correlation or linear attacks or even related attacks. This feature is depending on the bits of the word vectorswi. wi is also considered as the affine transformations of the functions generated from the SRFG used. The nonlinearity is calculated by the hamming distance between two affine transformations. For example, two word are wi and wj of 32 bits each.(16)Nlwik,wjk=∑k=1nwik≠wjk,wheren=32Each of the rounds in AES is using 4 words (128 bits) as subkeys. The nonlinearity between two subkeys used for any two rounds ri, rj can be measured as(17)Nlri,rj=∑k=1nrik≠rjk,wheren=128


### 5.2. Balancedness

Balanced property of our proposed key expansion functionfc exists if its simplified value vector gc follows the following condition:(18)∀i=1,2,gci=gc2-i⊞1,where⊞issumoverF2The above equation also provides the feature of trivial balancedness corresponding to symmetric functions. Therefore, fc verifies the condition D1fc=1. The functions having D1fc=1 do not exist for even values of n (here n = 32 for words and n = 128 for rounds) because for any word vector w such that wt(w)=n/2 (where wt(w) is the weight of word vector defined as number of 1s in it), we can calculate the D1fc as(19)D1fc=fcw⊞fcw+1=gcn2⊞gcn2=0


### 5.3. Resiliency

The correlation between the output of the key expansion function and a small subset of its input variables leads to the correlation attack [28], linear or differential cryptanalysis [29]. Therefore, it is necessary for the key expansion function to achieve the high resiliency property. A function fc of N variables each of having n bits is m-resilient if it remains balanced when any m input variables are fixed and remaining (n-m) bits are altered. The function is more resilient if m is higher. The property of resiliency is related to the weights of the restrictions of the fc to some subspaces.∀ f c ∈ B 2 and any affine any subspace S⊂F22, the restriction of fc to S is the function given as(20)fS:S→F2(21)x→fcx,∀x∈Swhere, fS can be determined by the with a function of dim(S) variables. The subspace S is spanned by k canonical basis vectors and its supplementary subspace is S¯. The restrictions of fc to S and to all its cosets are given by a+ S where a∈S. Being fc symmetric and balanced, S is represented as S=(s1,s2,…,sk) and fa+S becomes symmetric and balanced too. Moreover, for all s∈S, we can write the following:(22)fa+Ss=fa+s=gcwta+wtswhich actually depends upon the weight of s when a is fixed. The simplified value vector and the simplified ANF vector of fa+S can be deduced from fc as given below.(23)gcfa+Si=gci+wta,∀i,0≤i≤k(24)λcfa+Si=⊕λfi+j,∀i,0≤i≤kandj⪯wta


### 5.4. Propagation Criterion

Propagation criterion is determined by the cryptographic properties of the derivatives of the functions. For the efficiency of a cryptographic function, the function needs to propagate its properties to all its derivatives. All derivatives of the key expansion function are linearly equivalent when they have a fixed hamming weight ofn/2 [7]. Our proposed approach of key expansion N variables applied from our previous work [7] satisfies the propagation criterion of degree k and order m if any affine function obtained from the outputs by keeping m input bits constant satisfies the propagation criterion of degree k. Considering each round for experimentation, one has the following.Letfc∈B2 and let ri,rj∈F22, ∀i,j=1,2,…,14 such that wt(ri)=wt(rj)=n/2. Then, Drifc and Drjfc are linearly equivalent.This signifies that if we change the input variables with a linear permutationμ of F22, Drifc=Drjfc∘μ, where ∘ is composite function. The permutation μ exists on the variable in a way so that that rj=μ(ri). Since fc is symmetric and balanced, we can have(25)Drjfcμa=Drifca,wherea∈S¯Let k be an integer, 1≤k≤n-1,  z∈wi¯=(wi1,wi2,…,win-k), and ϵk=wn-k+1+⋯+wn. Then for any z=a+rj, with a∈S¯, then we can have the following:(26)wtz=wta+wtrj(27)wtz+ϵk=wta+wtrj+ϵk=wta+k-wtrjThus, ∀a∈V,(28)Dϵkfca+y=fca+b⊞fca+ϵk+rj=wta+wtrj+ϵk=wta+k-wtrj=gcwta+wrj⊞wta+k-wrjEquation (28) signifies that gc follows the symmetric property. This means that partial derivatives of our proposed key expansion outputs are also propagated with the propagation features.


### 5.5. Immunity

The proposed key expansion module deals with the variables (words) with 32 bits (no modification has been done on bit size). Two types of immunity are in concern: correlation immunity and algebraic immunity. For, correlation immunity, considering each of the two input variableswi as 32-bit binary vector the outputs are correlation immune if(29)Probfc=wi=12,1≤i≤32The probability distribution must be equal for all the bits and therefore, the output words wo have the following property:(30)min⁡M0wo,wor-M1wo,wor=minm→0where [M0(wo,(wo)r)] is the matching of output words from the key expansion process and its reverse with respect to value 0 and [M1(wo,(wo)r)] is the matching of output words from the key expansion process and its reverse with respect to value 1. Following the above property, an interesting feature of our proposed key expansion module has been identified and the proposition has been given as follows.Proposition 1.
In AES-256, if [M0(wo,(wo)r)]=m0 and [M1(wo,(wo)r)]=m1, then Nl(wo,(wo)r)=m0+m1.Algebraic immunity is related to the annihilator of a function [30]. To evaluate this property for our proposed key expansion we can consider the following.Given,fc∈B2, any function of the set A(fc)={g∈B2∣gf=0} is defined as the annihilator of the function fc. The algebraic immunity of fc is denoted by AI(fc) is minimum degree of all nonzero annihilators of f(c) or f(c)+1. The value of AI(fc) is given as(31)AIfc=mindeggg≠0,g∈Afc∪Afc+1As we have used SRFG to generate the output words, minimum degree is always n/2. Therefore, the algebraic immunity of the outputs from it is always n/2 which is always optimal.


## 5.1. Nonlinearity

Nonlinearity is an important design characteristic for cryptographic functions used in cryptographic algorithms to prevent different types of correlation or linear attacks or even related attacks. This feature is depending on the bits of the word vectorswi. wi is also considered as the affine transformations of the functions generated from the SRFG used. The nonlinearity is calculated by the hamming distance between two affine transformations. For example, two word are wi and wj of 32 bits each.(16)Nlwik,wjk=∑k=1nwik≠wjk,wheren=32Each of the rounds in AES is using 4 words (128 bits) as subkeys. The nonlinearity between two subkeys used for any two rounds ri, rj can be measured as(17)Nlri,rj=∑k=1nrik≠rjk,wheren=128


## 5.2. Balancedness

Balanced property of our proposed key expansion functionfc exists if its simplified value vector gc follows the following condition:(18)∀i=1,2,gci=gc2-i⊞1,where⊞issumoverF2The above equation also provides the feature of trivial balancedness corresponding to symmetric functions. Therefore, fc verifies the condition D1fc=1. The functions having D1fc=1 do not exist for even values of n (here n = 32 for words and n = 128 for rounds) because for any word vector w such that wt(w)=n/2 (where wt(w) is the weight of word vector defined as number of 1s in it), we can calculate the D1fc as(19)D1fc=fcw⊞fcw+1=gcn2⊞gcn2=0


## 5.3. Resiliency

The correlation between the output of the key expansion function and a small subset of its input variables leads to the correlation attack [28], linear or differential cryptanalysis [29]. Therefore, it is necessary for the key expansion function to achieve the high resiliency property. A function fc of N variables each of having n bits is m-resilient if it remains balanced when any m input variables are fixed and remaining (n-m) bits are altered. The function is more resilient if m is higher. The property of resiliency is related to the weights of the restrictions of the fc to some subspaces.∀ f c ∈ B 2 and any affine any subspace S⊂F22, the restriction of fc to S is the function given as(20)fS:S→F2(21)x→fcx,∀x∈Swhere, fS can be determined by the with a function of dim(S) variables. The subspace S is spanned by k canonical basis vectors and its supplementary subspace is S¯. The restrictions of fc to S and to all its cosets are given by a+ S where a∈S. Being fc symmetric and balanced, S is represented as S=(s1,s2,…,sk) and fa+S becomes symmetric and balanced too. Moreover, for all s∈S, we can write the following:(22)fa+Ss=fa+s=gcwta+wtswhich actually depends upon the weight of s when a is fixed. The simplified value vector and the simplified ANF vector of fa+S can be deduced from fc as given below.(23)gcfa+Si=gci+wta,∀i,0≤i≤k(24)λcfa+Si=⊕λfi+j,∀i,0≤i≤kandj⪯wta


## 5.4. Propagation Criterion

Propagation criterion is determined by the cryptographic properties of the derivatives of the functions. For the efficiency of a cryptographic function, the function needs to propagate its properties to all its derivatives. All derivatives of the key expansion function are linearly equivalent when they have a fixed hamming weight ofn/2 [7]. Our proposed approach of key expansion N variables applied from our previous work [7] satisfies the propagation criterion of degree k and order m if any affine function obtained from the outputs by keeping m input bits constant satisfies the propagation criterion of degree k. Considering each round for experimentation, one has the following.Letfc∈B2 and let ri,rj∈F22, ∀i,j=1,2,…,14 such that wt(ri)=wt(rj)=n/2. Then, Drifc and Drjfc are linearly equivalent.This signifies that if we change the input variables with a linear permutationμ of F22, Drifc=Drjfc∘μ, where ∘ is composite function. The permutation μ exists on the variable in a way so that that rj=μ(ri). Since fc is symmetric and balanced, we can have(25)Drjfcμa=Drifca,wherea∈S¯Let k be an integer, 1≤k≤n-1,  z∈wi¯=(wi1,wi2,…,win-k), and ϵk=wn-k+1+⋯+wn. Then for any z=a+rj, with a∈S¯, then we can have the following:(26)wtz=wta+wtrj(27)wtz+ϵk=wta+wtrj+ϵk=wta+k-wtrjThus, ∀a∈V,(28)Dϵkfca+y=fca+b⊞fca+ϵk+rj=wta+wtrj+ϵk=wta+k-wtrj=gcwta+wrj⊞wta+k-wrjEquation (28) signifies that gc follows the symmetric property. This means that partial derivatives of our proposed key expansion outputs are also propagated with the propagation features.


## 5.5. Immunity

The proposed key expansion module deals with the variables (words) with 32 bits (no modification has been done on bit size). Two types of immunity are in concern: correlation immunity and algebraic immunity. For, correlation immunity, considering each of the two input variableswi as 32-bit binary vector the outputs are correlation immune if(29)Probfc=wi=12,1≤i≤32The probability distribution must be equal for all the bits and therefore, the output words wo have the following property:(30)min⁡M0wo,wor-M1wo,wor=minm→0where [M0(wo,(wo)r)] is the matching of output words from the key expansion process and its reverse with respect to value 0 and [M1(wo,(wo)r)] is the matching of output words from the key expansion process and its reverse with respect to value 1. Following the above property, an interesting feature of our proposed key expansion module has been identified and the proposition has been given as follows.Proposition 1.
In AES-256, if [M0(wo,(wo)r)]=m0 and [M1(wo,(wo)r)]=m1, then Nl(wo,(wo)r)=m0+m1.Algebraic immunity is related to the annihilator of a function [30]. To evaluate this property for our proposed key expansion we can consider the following.Given,fc∈B2, any function of the set A(fc)={g∈B2∣gf=0} is defined as the annihilator of the function fc. The algebraic immunity of fc is denoted by AI(fc) is minimum degree of all nonzero annihilators of f(c) or f(c)+1. The value of AI(fc) is given as(31)AIfc=mindeggg≠0,g∈Afc∪Afc+1As we have used SRFG to generate the output words, minimum degree is always n/2. Therefore, the algebraic immunity of the outputs from it is always n/2 which is always optimal.


## 6. Security Analysis of RK-AES

In the above section, we have analysed the overall features of the proposed key expansion modification in AES-256 using the SRFG. To justify the features, in this section we have performed the security analysis on our modified AES key expansion module. We have considered two attacks: related attacks and fault analysis attacks.


### 6.1. Related Key Attack Analysis

Related key attacks use the linear relations or differential relations among the keys to deduce the original key.Letnz be a known nonzero word difference for input and o be an output difference of S-box for the input difference nz. To execute the attack with this differences, the difference o can be one of 214-1 values, because of the symmetry of the XOR operation as used in generic AES-256 algorithm and the nz difference can be one of 215-1 differences including whitening of keys. Once these differences are in a bounded value region, the probability deducing of the key is also higher. In our proposed modified AES, the nonlinearity feature increases this difference and therefore, the key space of searching also increases drastically. For a 32-bit word in key space, the complexity of searching space increases with the following formula:(32)Complexityforkeyspacesearch=232.2Nlwhere Nl is the value of nonlinearity in the proposed AES key expansion and the average value of Nl=20.7. Therefore, the complexity becomes 252.7 which is more than the differential attacks key searching complexities on AES. This shows that our proposed algorithm is preventive in differential attacks.Furthermore, the attacker uses four related but unknown keys asKu1,Ku2,Ku3,Ku4. The objective of the attacker is to recover Ku1. The relation required to establish the attack is(33a)Ku2=Ku1⊕△K∗(33b)Ku3=Ku1⊕△K′(33c)Ku4=Ku1⊕△K∗⊕△K′where △K∗ is the cipher key difference used for the first related-key differential D0 for 1 to 7 round and △K′ is the cipher key difference used for the second related-key differential D1 used for 8 to 14 round. Assuming that the attacker only has the information regarding △K∗ and △K′, the back tracing probability to recover any 32-bit words (any word out of the 60 words) is calculated as(34)Pwi=12n.i.PLL.2VFor our proposed modified AES-256 key expansion, number of bits in each word is n = 32, total number of words including whitening key words is i = 60, total number of expression length L = 5, and total number variables used for each operation is V = 2. Using the values, the probability becomes as(35)Pwi=1232×60×P55×22=1239×225The above result show that the probability is too less to recover a single word of AES-256 using our proposed approach of key expansion.In Figure4, it is shown that the words are generated using SRFG rather than using simple XOR operation. Therefore, (33a), (33b), and (33c) will not be feasible for our proposed solution of AES using SRFG. It means, the proposed solution is related attack resistant. Moreover, △K∗ and △K′ are a factor in deducing the key. But, as our proposed solution provides a high nonlinearity, △K∗ and △K′ are not suitable to recover the words of the key space. From the observation of or experimentation, we have inferred a proposition as follows.Proposition 2.
Considering△K∗ is the cipher key difference used for the first related-key differential D0 and △K′ is the cipher key difference used for the second related-key differential D1, nonlinearity is inversely proportional to the nonlinearity.(36)D0⊢△K∗∝1NlandD1⊢△K′∝1Nl(37)∴D0.D1⊢△K∗.△K′∝1Nl2


### 6.2. Fault Injection Analysis

In this part, we have only considered the fault injection in the key bytes. We assume that the faulty key byte is injected in the key matrix for any random original key byte. The faulty input is inferred from the biased input of all 0 bits byte or all1 bits byte. In the original AES, using such faulty and biased inputs reveals the relationship among word byte or even words of round. Therefore in original AES, the key recovery space is reduced with less complexity as we have seen in the literature review.Recollecting (11) and (12), we can have the following proposition for AES-256.Proposition 3.
For AES-256, using SRFG with two variables and t expression terms, the complexity of key recovery with any two random faulty byte is calculated as(38)ProbFI=1∑⊕λu∏i=12randwiuit.C260For any random faulty key byte, the output of the layered SRFGs is always nonlinear and balanced. Therefore according to Proposition2 the differences and/or the linear equations become invalid as the fault is not further propagated to other bytes. Therefore, our proposed key expansion is preventive even in fault injection bytes.


## 6.1. Related Key Attack Analysis

Related key attacks use the linear relations or differential relations among the keys to deduce the original key.Letnz be a known nonzero word difference for input and o be an output difference of S-box for the input difference nz. To execute the attack with this differences, the difference o can be one of 214-1 values, because of the symmetry of the XOR operation as used in generic AES-256 algorithm and the nz difference can be one of 215-1 differences including whitening of keys. Once these differences are in a bounded value region, the probability deducing of the key is also higher. In our proposed modified AES, the nonlinearity feature increases this difference and therefore, the key space of searching also increases drastically. For a 32-bit word in key space, the complexity of searching space increases with the following formula:(32)Complexityforkeyspacesearch=232.2Nlwhere Nl is the value of nonlinearity in the proposed AES key expansion and the average value of Nl=20.7. Therefore, the complexity becomes 252.7 which is more than the differential attacks key searching complexities on AES. This shows that our proposed algorithm is preventive in differential attacks.Furthermore, the attacker uses four related but unknown keys asKu1,Ku2,Ku3,Ku4. The objective of the attacker is to recover Ku1. The relation required to establish the attack is(33a)Ku2=Ku1⊕△K∗(33b)Ku3=Ku1⊕△K′(33c)Ku4=Ku1⊕△K∗⊕△K′where △K∗ is the cipher key difference used for the first related-key differential D0 for 1 to 7 round and △K′ is the cipher key difference used for the second related-key differential D1 used for 8 to 14 round. Assuming that the attacker only has the information regarding △K∗ and △K′, the back tracing probability to recover any 32-bit words (any word out of the 60 words) is calculated as(34)Pwi=12n.i.PLL.2VFor our proposed modified AES-256 key expansion, number of bits in each word is n = 32, total number of words including whitening key words is i = 60, total number of expression length L = 5, and total number variables used for each operation is V = 2. Using the values, the probability becomes as(35)Pwi=1232×60×P55×22=1239×225The above result show that the probability is too less to recover a single word of AES-256 using our proposed approach of key expansion.In Figure4, it is shown that the words are generated using SRFG rather than using simple XOR operation. Therefore, (33a), (33b), and (33c) will not be feasible for our proposed solution of AES using SRFG. It means, the proposed solution is related attack resistant. Moreover, △K∗ and △K′ are a factor in deducing the key. But, as our proposed solution provides a high nonlinearity, △K∗ and △K′ are not suitable to recover the words of the key space. From the observation of or experimentation, we have inferred a proposition as follows.Proposition 2.
Considering△K∗ is the cipher key difference used for the first related-key differential D0 and △K′ is the cipher key difference used for the second related-key differential D1, nonlinearity is inversely proportional to the nonlinearity.(36)D0⊢△K∗∝1NlandD1⊢△K′∝1Nl(37)∴D0.D1⊢△K∗.△K′∝1Nl2


## 6.2. Fault Injection Analysis

In this part, we have only considered the fault injection in the key bytes. We assume that the faulty key byte is injected in the key matrix for any random original key byte. The faulty input is inferred from the biased input of all 0 bits byte or all1 bits byte. In the original AES, using such faulty and biased inputs reveals the relationship among word byte or even words of round. Therefore in original AES, the key recovery space is reduced with less complexity as we have seen in the literature review.Recollecting (11) and (12), we can have the following proposition for AES-256.Proposition 3.
For AES-256, using SRFG with two variables and t expression terms, the complexity of key recovery with any two random faulty byte is calculated as(38)ProbFI=1∑⊕λu∏i=12randwiuit.C260For any random faulty key byte, the output of the layered SRFGs is always nonlinear and balanced. Therefore according to Proposition2 the differences and/or the linear equations become invalid as the fault is not further propagated to other bytes. Therefore, our proposed key expansion is preventive even in fault injection bytes.


## 7. Results of Comparison

We have compared our experimentation results of RK-AES with the original AES algorithm. The comparison is done on the basis of some features: nonlinearity, balancedness, resiliency, propagation criterion, correlation immunity, and algebraic immunity. As we have modified only the key expansion module, the results are derived only for key expansion only without involving the plaintext processing or transformations in round function. We have compared 215 data samples for each RK-AES and original AES. The comparison results are shown in Table1 by averaging all the results.Table 1
Comparison of parameters.
Order of Non-linearity Order of Balancedness Order of Resiliency Order of Propagation criterion Order of Correlation immunity Order of Algebraic immunity Original AES-256 n / 2 - l o g 2 n 0 n / 2 - 2 l o g 2 n + n / 4 n / 10 n / 6  Proposed RK-AES n / 2  ×  0.65 + l o g 2 5 n / 2 n / 2 - 2 n × 0.73 + l o g 2 5 n n / 2  n is the value of bits in a word of key spaceThe comparison results in Table1 signify that our proposed modification of key expansion is working efficiently in AES in terms of the above said features. Moreover, the balancedness and the correlation immunity are 0 in original AES. Our proposed modification is providing a higher value for balancedness which is useful for preventing bitsum attacks [31]. The high correlation immunity will also help the modified AES to prevent correlation attacks [28].Moreover, we have compared the computation time for our experiments with the original AES algorithm. In this comparison too, we have assumed the time for plaintext processing and transformations in round function are constant as no modification has done on them. Therefore, Table2 only compares the time taken for the key expansion process.Table 2
Time consumption comparison.
Hardware specification for computation: CPU: 2.6Ghz, i3 6th,Gen with 16 GB RAM  Average Time Consumption (in milliseconds)  Schemes 32 bit key wordsw0 to w7 32 bit key wordsw8 to w59 g function  Original, AES 3.67 5.73 6.32  RK-AES 6.78 8.87 9.33The time comparison results show that using the SRFG in AES key expansion modification is increasing the time consumption in generating the key words and thus contributing to the trade-off between security and time consumption. To support this trade-off and overcome with the security issues, we have also compared the attack for both the original AES and the modified AES.Table3 describes the fact that the cost of the attacks for our proposed RK-AES is much higher than the original AES due to the use of randomness with SRFG in several layer. This signifies that RK-AES is better in terms of security.Table 3
Comparison of cost of attacks.
Differential cryptanalysis Linear cryptanalysis Related key analysis Fault injection attack analysis in key space Original AES 2 32 2 14 - 1 2 32 2 26  RK-AES 2 52.7 2 60 2 52.7 ≈ 2 129Lastly, we have compared two prime evaluation parameter of encryption algorithms: confusion and avalanche effect. Confusion property requires the statistical relationship of between the ciphertext and key to be more complex. Besides, avalanche effect requires change in the ciphertext bits if any single bit is changed in the key. We have calculated confusion property in terms of nonlinearity and resiliency. The avalanche effect is measured in terms of propagation criterion, correlation immunity, and algebraic immunity. The calculation formula for confusion and avalanche effect have been given below.(39)Confusion=ω1×Nonlinearity+ω2×Resiliency+ω3×Balancedness(40)Avalanche=ω1×Propagationcriterion+ω2×Correlationimmunity+ω3×Algebraicimmunitywhere ω1,ω2, and ω3 are the weights assigned to the features. We have considered for our experimentation of RK-AES, ω1=ω2=ω3=0.33, and n = 32 bit.Therefore, following Table1, the values for confusion and avalanche effect in RK-AES are(41)ConfusionRK-AES=0.33×n2×0.65+log25+0.33×n2+0.33×n2-2≅22.621AvalancheRK-AES=0.33×n×0.73+log25+0.33×n+0.33×n2≅24.31Similarly, we have calculated the values for confusion and avalanche effect in original AES. Considering the orders in Table 1, the values are as follows:(42)ConfusionAES=0.33×n2-log2n+0.33×0+0.33×n2-2≅7.59AvalancheAES=0.33×(log2n+n/4)+(0.33×n/10)+(0.33×n/6)≅15.816. The similar result of Avalanche effect is also experimented in the bit values of the data samples. Table 4 compares the avalanche effect.Table 4
Avalanche effect comparison.
Weighted value of Avalanche Average number of bits changed Original AES 15.816 17.3 bits out of 32 bits  Proposed RK-AES 24.310 ≈ 25 bits out of 32 bitsThe comparison results of confusion property and avalanche effect also show the improvement of the parameters as compared to the original AES algorithm.


## 8. Conclusion

AES is a popular symmetric block cipher used by different commercialization sectors. But this algorithm is facing a number of cryptanalysis effects as we have seen in the literature review. Therefore, in this paper we have tried to solve the problem by incorporating the changes in key expansion module. The highlight of this work is to apply randomness in the key generation. Moreover, as per our previous work, using SRFG as a cryptographic function in AES has been proved beneficial. The justification for the same has been already shown in the paper. The results show that RK-AES is having three times better confusion property and 53.7% better avalanche effect as compared to the original AES. The limitation of our present work is about the time taken by the modified key expansion module which is actually creating a trade-off between security and time. It is also known that both these two cannot be achieved simultaneously. Therefore, if we ignore the part of the time, our proposed RK-AES is efficient in all respects of cryptographic algorithms. Furthermore, being a symmetric key algorithm AES uses the single key for both encryption and decryption. In our present work, the round keys are stored separately as each round keys are generated randomly and are used for decryption accordingly. In our future work, we shall try to work on the trade-off and also about the storing process of round keys.



---

*Source: 9802475-2018-11-06.xml*