# A Chaos-Based Authenticated Cipher with Associated Data

Authors: Je Sen Teh; Azman Samsudin
Journal: Security and Communication Networks
 (2017)

---

## Abstract

In recent years, there has been a rising interest in authenticated encryption with associated data (AEAD) which combines encryption and authentication into a unified scheme. AEAD schemes provide authentication for a message that is divided into two parts: associated data which is not encrypted and the plaintext which is encrypted. However, there is a lack of chaos-based AEAD schemes in recent literature. This paper introduces a new 128-bit chaos-based AEAD scheme based on the single-key Even-Mansour and Type-II generalized Feistel structure. The proposed scheme provides both privacy and authentication in a single-pass using only one 128-bit secret key. The chaotic tent map is used to generate whitening keys for the Even-Mansour construction, round keys, and random s-boxes for the Feistel round function. In addition, the proposed AEAD scheme can be implemented with true random number generators to map a message to multiple possible ciphertexts in a nondeterministic manner. Security and statistical evaluation indicate that the proposed scheme is highly secure for both the ciphertext and the authentication tag. Furthermore, it has multiple advantages over AES-GCM which is the current standard for authenticated encryption.


---

## Body

## 1. Introduction

Encryption and authentication of data are traditionally performed by two separate algorithms under the influence of different secret keys. This is known as generic composition which has three variations:Encrypt-and-MAC,MAC-then-Encrypt, andEncrypt-then-MAC [1]. Recently, there has been a rising interest in the field of authenticated encryption with associated data (AEAD) which combines encryption and authentication into a unified scheme. It deals with the cryptographic problem of sending a message that has to be entirely authenticated but divided into two parts: associated data (additional information such as packet headers) that must be sent in the clear and the actual plaintext that must be encrypted [2]. AEAD schemes are also more efficient and less prone to implementation errors, unlike generic composition [3]. This is because an AEAD scheme can be implemented without extensive cryptographic knowledge and is easy for interoperability [4]. As it only requires one key for both privacy and integrity, it saves on key bits and key setup time and reduces the risk of users selecting insecure parameters.The Competition for Authenticated Encryption: Security, Applicability, and Robustness (CAESAR) [5] was introduced in 2014 to identify authenticated ciphers that offer advantages over AES-GCM, which has weak key problems and is susceptible to a cyclic attack [6]. CAESAR is currently in its second round of evaluation, with 30 candidate ciphers remaining. AEAD proposals for CAESAR need to have higher level of security and be as fast as AES-GCM or faster than AES-GCM with similar security level. The design of AEAD schemes is based on various constructs such as block ciphers, stream ciphers, and sponge constructions.The aim of this paper is to construct an AEAD scheme based on chaos theory that is secure and efficient and fulfils the requirements set by CAESAR. For additional security, the AEAD scheme is designed to be able to take advantage of true random number generators (TRNG) to resist statistical-based cryptanalysis. Due to the existence of efficient and uniformly distributed software-based TRNGs, it is feasible to utilize true random numbers in cryptographic algorithms. These TRNGs take advantage of physical phenomena that occur within computing hardware such as multicore processors [7], graphics processing units [8], or hard disks [9] and quantifies them to generate nondeterministic numbers. As the inputs of AEAD schemes include secret and public message numbers, TRNGs can be implemented to generate secret message numbers to provide immunity to statistical-based cryptanalysis.In this paper, a new AEAD scheme based on the chaotic tent map is proposed. It is designed based on the single-key Even-Mansour construction [10] and utilizes key-dependent random s-boxes. Both the whitening keys for the Even-Mansour scheme and s-boxes are generated based on chaos. The proposed AEAD scheme requires only a single-pass to produce both the authentication tag (MAC) and ciphertext. The cipher is evaluated for resistance against cryptanalytic attacks and its security is also analysed based on thorough statistical testing. Although not compulsory, the AEAD scheme can be implemented alongside a TRNG to provide immunity to statistical-based cryptanalysis.The rest of this paper is structured as follows: Section2 provides an introduction to AEAD schemes and chaotic maps that are vital to understanding the rest of the paper. Section 3 describes the proposed AEAD algorithm in detail, followed by Section 4 that analysed its security. The paper is concluded in Section 5 with some closing remarks.


## 2. Preliminaries

### 2.1. Authenticated Encryption with Associated Data

The following are inputs to an authenticated encryption algorithm along with their corresponding security requirements (I=Integrity, P=Privacy):(i)
Variable-length plaintext (ip)(ii)
Variable-length associated data (i)(iii)
q-bit secret message number (ip)(iv)
p-bit public message number/nonce (i)(v)
k-bit secret keyThe output of an AEAD scheme consists of a ciphertext with the same length as the plaintext (except for schemes with secret message numbers which have extra blocks of ciphertext depending on the size ofq) and an authentication tag or MAC of t bits. AEAD schemes need not support secret message numbers (q=0) but require unique nonces for semantic security. The inputs to an authenticated decryption algorithm include the ciphertext, associated data, nonce, and secret key. The secret message number will be extracted from ciphertext. It outputs the plaintext if verification is successful; otherwise the algorithm outputs an error message.


### 2.2. Chaotic Maps

Chaotic maps are deterministic dynamical systems that have random-like behavior, sensitivity to slight changes in initial parameters, ergodicity, diffusion, and confusion characteristics. These qualities are analogous to requirements in cryptographic algorithms; thus chaotic maps have been used to design hash functions [11], encryption algorithms [12], key exchange protocols [13], and digital signature schemes [14]. Authenticated image encryption schemes based on chaos have been introduced by Bakhshandeh and Eslami [15] as well as Yang et al. [16]. However, they are both generic composition schemes with a distinct hash function and encryption algorithm. No chaos-based, unified AEAD schemes have been introduced in recent literature.The chaotic tent map is used to design the proposed AEAD scheme as shown in (1), where β is the control parameter that falls within the range of [0,2]. In addition to being a fast and simple map, the tent map is selected because it has been widely studied and applied in the field of chaotic cryptography. The behavior of the chaotic map evolves from periodic to aperiodic as β increases from 0 to 2 as shown in the tent map’s bifurcation diagram in Figure 1. The proposed AEAD sets β=1.99999 for all tent map iterations.(1)cxt+1=βxt0≤xt<0.5β1-xt,0.5≤xt≤1.Figure 1
Tent map bifurcation diagram.Recent literature has shown that unimodal chaotic maps such as the tent map are susceptible to initial condition/parameter estimation techniques using statistical tools [17, 18]. Another problem of digital chaotic systems is dynamical degradation that occurs due to finite precision, which leads to short cycle lengths [19]. These problems can be addressed by using chaotic perturbation which changes the trajectory of the chaotic map’s orbit by modifying its initial condition using external values. The proposed AEAD scheme takes advantage of chaotic perturbation in its design as discussed in Section 3.In software, chaotic map iterations involve real numbers that are usually represented by floating point variables. However, floating point operations are slower than binary operations. For faster speed and reproducibility, fixed point (FxP) representation [20] is used in the proposed AEAD scheme. A 32-bit FxP variable consists of the two most significant bits (MSB) that represent integers before the radix point and the 30 least significant bits (LSB) that represent fractional bits.


## 2.1. Authenticated Encryption with Associated Data

The following are inputs to an authenticated encryption algorithm along with their corresponding security requirements (I=Integrity, P=Privacy):(i)
Variable-length plaintext (ip)(ii)
Variable-length associated data (i)(iii)
q-bit secret message number (ip)(iv)
p-bit public message number/nonce (i)(v)
k-bit secret keyThe output of an AEAD scheme consists of a ciphertext with the same length as the plaintext (except for schemes with secret message numbers which have extra blocks of ciphertext depending on the size ofq) and an authentication tag or MAC of t bits. AEAD schemes need not support secret message numbers (q=0) but require unique nonces for semantic security. The inputs to an authenticated decryption algorithm include the ciphertext, associated data, nonce, and secret key. The secret message number will be extracted from ciphertext. It outputs the plaintext if verification is successful; otherwise the algorithm outputs an error message.


## 2.2. Chaotic Maps

Chaotic maps are deterministic dynamical systems that have random-like behavior, sensitivity to slight changes in initial parameters, ergodicity, diffusion, and confusion characteristics. These qualities are analogous to requirements in cryptographic algorithms; thus chaotic maps have been used to design hash functions [11], encryption algorithms [12], key exchange protocols [13], and digital signature schemes [14]. Authenticated image encryption schemes based on chaos have been introduced by Bakhshandeh and Eslami [15] as well as Yang et al. [16]. However, they are both generic composition schemes with a distinct hash function and encryption algorithm. No chaos-based, unified AEAD schemes have been introduced in recent literature.The chaotic tent map is used to design the proposed AEAD scheme as shown in (1), where β is the control parameter that falls within the range of [0,2]. In addition to being a fast and simple map, the tent map is selected because it has been widely studied and applied in the field of chaotic cryptography. The behavior of the chaotic map evolves from periodic to aperiodic as β increases from 0 to 2 as shown in the tent map’s bifurcation diagram in Figure 1. The proposed AEAD sets β=1.99999 for all tent map iterations.(1)cxt+1=βxt0≤xt<0.5β1-xt,0.5≤xt≤1.Figure 1
Tent map bifurcation diagram.Recent literature has shown that unimodal chaotic maps such as the tent map are susceptible to initial condition/parameter estimation techniques using statistical tools [17, 18]. Another problem of digital chaotic systems is dynamical degradation that occurs due to finite precision, which leads to short cycle lengths [19]. These problems can be addressed by using chaotic perturbation which changes the trajectory of the chaotic map’s orbit by modifying its initial condition using external values. The proposed AEAD scheme takes advantage of chaotic perturbation in its design as discussed in Section 3.In software, chaotic map iterations involve real numbers that are usually represented by floating point variables. However, floating point operations are slower than binary operations. For faster speed and reproducibility, fixed point (FxP) representation [20] is used in the proposed AEAD scheme. A 32-bit FxP variable consists of the two most significant bits (MSB) that represent integers before the radix point and the 30 least significant bits (LSB) that represent fractional bits.


## 3. Design Specifications

### 3.1. Parameters and Notations

All integers stated in the following algorithms are in hexadecimal format. Prior to modification by the nonce or secret keys, the initial values for all registers are arbitrarily chosen random numbers. The proposed 128-bit AEAD scheme has the following parameters:(i)
128-bit secret key,κ∈0,1128(ii)
64-bit nonce,η∈0,164(iii)
128-bit secret message number,τ∈{0,1}128(iv)
Associated data,A∈{0,1}∗(v)
Message,M∈{0,1}∗(vi)
128-bit tag,T∈{0,1}128The following are notations used in this paper:(i)
Length of a string,x, denoted by |x|(ii)
⊕: Bitwise XOR(iii)
∧: Bitwise AND(iv)
x∥y: Bitwise concatenation of x and y(v)
⊞n: n-bit modular addition(vi)
rotlrn(x): Bitwise left rotation by r positions on a n-bit variable, x where n=8,32,64(vii)
x≫y: Bitwise right shift of x by y bits(viii)
s(x): substitution function using an 8-bit s-box, s(ix)
ci(x): performing i-iterations of the chaotic map with an initial value x(x)
x: floor function to map a real number x to the previous largest integer(xi)
FPx: converting the FxP representation to real number(xii)
Φ: mask for the FxP fractional bitsBecause the AEAD design involves chaotic map iterations, round constants are used in several parts of the algorithms to prevent weak key problems. Weak keys can initialize the chaotic map’s initial condition to zero, which makes the system nonrandom and insecure. These round constants are taken from the list of prime numbers:rconi=2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, where 0≤i<32 is the index/round. The proposed AEAD scheme also uses a block shuffle π and its inverse as shown in Table 1.Table 1
Block shuffleπ and inverse block shuffle π-1.
x 0 1 2 3 4 5 6 7 8 9 a b c d e f π(x) 5 0 1 4 7 c 3 8 d 6 9 2 f a b e π-1(x) 1 2 b 6 3 0 9 4 7 a d e 5 8 f c


### 3.2. RandomS-Box Generation

The composition method [21] is used to generate chaos-based s-boxes for the AEAD scheme. The composition of two 8-bit permutations, f(x) and g(x), is denoted by h(x)=fgx,∀x∈I, where I is the set of all 8-bit integers. First, a set S consisting of four chaos-based s-boxes is generated by permuting the AES s-box. To obtain the final s-box, a composition of four s-boxes from S is used, where the s-boxes are selected based on randomly generated indices (repetitions are allowed). To generate the numbers used to permute AES and also as indices for the s-box composition, a chaos-based RNG is used. The initialization process and the RNG algorithm are as shown in Algorithms 1 and 2, respectively, where x and y are chaotic map initial conditions that are constantly modified by perturbation values, p and q.Algorithm 1:Initialization of the Chaos-based RNG.
(1)Input: 64-bit secret key values k0 and k1. (2)Output: Initialized variables x,y,p,q,r0,r1. (3)— (4) //Initialize variables (5)x←82dcbe4e⊕k0∧Φ,  y←49a2372c⊕k1∧Φ (6)p←(49a2372c⊕k0≫30), q←(945ae69b⊕(k1≫30)) (7)r0←3⊞8k0≫62, r1←(3⊞8(k1≫62)) (8)for  i=0  to  3  do (9)c50(x) (10)c50(y) (11)x←x⊕p⊞32rcon4i∧Φ (12)p←rotlr032p⊞32rcon4i+1 (13)y←y⊕q⊞32rcon4i+2∧Φ (14)q←rotlr132q⊞32rcon4i+3 (15)end forAlgorithm 2:Chaos-based RNG.
(1)Input: 32-bit initial values x and y, 32-bit perturbation values p and q, 8-bit rotation valuesr0 and r1. (2)Output: 32-bit random number R. (3) — (4)c50(x) (5)c50(y) (6)R←FPx⊕FPy (7)x←x⊕p∧Φ (8)p←rotlr032(p) (9)y←(y⊕q)∧Φ (10)q←rotlr132(q)The initialization process equally divides the secret key bitsκ=k1∥k0 into four registers and two rotation variables such that all key bits are used only once. During the initialization, round constants are used to ensure that values of κ that initialize all registers to zero will result in nonzero starting values for the RNG. A total of 200 iterations for each tent map are performed for transient elimination, although 48 iterations have been deemed sufficient [22].Each 8-bit s-box,sj∈S for 0≤j<4, is first initialized as the AES s-box. Next, Algorithm 2 is used to generate vij for 0≤i<256 for each sj. Each s-box is then permuted as follows:(2)sji=sjvij,sjvij=sji.To obtain the final s-box, sf, four additional values are generated by Algorithm 2. A four-modulo operation is applied on these values which are then used as s-box indices, Ii for 0≤i<4. The final s-box is a composition of the four s-boxes indexed by I: sf(x)=sI3(sI2(sI1(sI0(x)))). As sf depends only on κ, it can be precomputed by both parties. sf is later modified by τ in the actual encryption process.


### 3.3. Key Schedule Algorithm

The key scheduling algorithm generates 20 round keys from the secret keyκ. As they do not depend on η or τ, the keys can also be precomputed. The algorithm is based on the Feistel network, whereby the secret key is first divided into two halves, κ=k1∥k0. k0 and k1 are then XOR-ed into two registers that have initial values of reg0=f492e42164c7fb0d and reg1=f683d0ad038f17d. The tent map’s initial condition is set to x=0. One round of the key scheduling function is shown in Figure 2, where i is the round number.Figure 2
Key Schedule Feistel Network.TheG-function is described in Algorithm 3. The network is executed 16 times for transient elimination without producing any keys. Starting from round number i=0,20 round keys are then produced from 20 rounds of the network. Excluding transient elimination rounds, each round key is generated from a total 640 iterations of the chaotic tent map. The value of O is modified 64 times, where, each time, it is subjected to a four-bit rotation to ensure that all 64 bits are modified by x in 16 passes. reg1 is rotated by 15 bits each time to ensure that its upper and lower bits are all used in the chaotic iterations.Algorithm 3:Key schedule G-function.
(1)Input: 64-bit register reg1, 32-bit initial condition x, round number i. (2)Output: 64-bit output, O. (3) — (4)O←0 (5)for  j=0  to  63  do (6)x←x⊕reg1∧Φ (7)c10(x) (8)O←O⊕x (9)O←rotl464(O) (10)reg1←rotl1564(reg1) (11)end for (12)O←O⊕rconi


### 3.4. Masking Algorithm

The proposed AEAD scheme is based on the single-key Even-Mansour construction that has been proven to have the same level of security as the original two-key construction [10]. 16 eight-bit mask registers are first initialized based on the secret key and nonce and then modified by a chaotic function. The values of these registers are used as the prewhitening and postwhitening masking keys for each block of data. The initialization of the mask registers and variables for the chaotic function are summarized in Figure 3, where κ=k1∥k0.Figure 3
Masking Algorithm Initialization.After the mask and chaotic variables are initialized, the masking algorithm is iterated eight times for transient elimination and to diffuse the key bits into all registers. The masking algorithm is as shown in Algorithm4 where registers (x,y,p,q) are involved in chaotic perturbation. These registers are then used to modify the mask registers, λ. Round constants are only used in the transient elimination rounds to generate nonzero initial mask values. The mask registers are later modified by τ in the encryption process.Algorithm 4:Mask algorithm.
(1)Input: 8-bit mask registers λj for 0≤j<16, 32-bit initial values x and y, 32-bit perturbation valuesp and q, round/block number i. (2)Output: Modified 8-bit mask registers λj for 0≤j<16 (3) — (4)x←c1(x), y←c1(y) (5)if Transient Elimination then (6)x←x⊕p⊞32rcon4i (7)y←y⊕q⊞32rcon4i+1 (8)p←p⊕y⊞32rcon4i+2 (9)q←q⊕x⊞32rcon4i+3 (10)else (11)x←x⊕p (12)y←y⊕q (13)p←p⊕y (14)q←q⊕x (15)end if (16)for  j=0  to  3  do (17)λj←λj⊞8x≫8j∧FF (18)λj+4←λj+4⊞8y≫8j∧FF (19)λj+8←λj+8⊞8p≫8j∧FF (20)λj+12←λj+12⊞8q≫8j∧FF (21)end for (22)for  j=0  to  15  do (23)λπj←λj (24)end for (25)x←x∧Φ, y←y∧Φ


### 3.5. Algorithm Description

The overall design of the AEAD is based on the single-key Even-Mansour scheme [10] and a Type-II generalized Feistel structure (GFS) [23]. There are two main functions, aead_encrypt and aead_decrypt. aead_encrypt encrypts M and τ and also generates a tag, T, to verify A, M, and τ. aead_decrypt decrypts C to obtain M and τ and then generates T to verify the authenticity of A, M, and τ. If verification fails, the decrypted message is not released to the recipient. The aead_encrypt algorithm is shown in Figure 4, where a is the number of A blocks, m is the number of M blocks, α represents intermediate tags, ∑M‍ is the checksum, and λ[i] is the set of mask registers for block-i of data. The aead_decrypt algorithm has the same structure as aead_encrypt. However the inverse block shuffle π-1 and reversed round keys are used to decrypt C and to generate the intermediate tags, αM∗.Figure 4
Encryption Algorithm.


#### 3.5.1. Round Function

The round function,Fj, is executed 20 times for all data blocks where j denotes the number of rounds. The same 20 round keys generated by the key scheduling algorithm are used for all blocks. When processing message blocks (M∗), F20 is divided into two halves, F20=F10·F10 where the output of the first 10 rounds is used as the intermediate tag αM∗. The round function is based on the Type-II GFS as shown in Figure 5. The 64-bit round key rki is divided into 8 bytes, where its most significant byte is fed into the left most h-function. The h-function consists of two operations, XOR of the round key and substitution:(3)hx=sfXd⊕rkie,where d and e are byte indexes of the data block and round key, respectively.Figure 5
AEADF-function.


#### 3.5.2. Modification ofS-Box and Mask

For further security,τ is used to modify both sf and λ prior to processing the first block of data. To modify sf, two more indexes for s-box composition are obtained from τ, Iτ0, and Iτ1. Iτ0 is obtained by XOR-ing each of the eight most significant bytes of τ whereas Iτ1 is obtained by XOR-ing each of the eight least significant bytes. The final s-box is computed by composing two additional s-boxes: sfinal(x)=sIτ1sIτ0sfx. The modification of λ registers is performed by XOR-ing each byte of τ to each byte of λ.


#### 3.5.3. AEAD Mode

The encryption and tag generation process is as follows:(1)
Usingκ, generate rki for 0≤i<20 and sf.(2)
Initializeλ based on κ and η.(3)
Encryptτ to obtain C0 and ατ.(4)
Generatesfinal and modify λ using τ (Section 3.5.2).(5)
IfA and M are not 128-bit multiples, pad A and M with a single bit of “1,” followed by all “0” until the required length.(6)
EncryptAj for 0≤j<a and XOR results to obtain αA.(7)
EncryptM[j] to obtain αM[j] and C[j+1], where 0≤j<m.(8)
Compute∑M‍. Encrypt ∑M‍ and XOR the result with ατ, αA, and αM[∗]. Perform one final encryption to obtain T.The decryption and tag verification process is as follows:(1)
Usingκ, generate rki for 0≤i<20 and sf.(2)
Initializeλ based on κ and η.(3)
DecryptC[0] to obtain τ and ατ.(4)
Generatesfinal and modify λ using τ (Section 3.5.2).(5)
If|A| is not a 128-bit multiple, pad A with a single bit of “1" followed by all “0" until the required length.(6)
EncryptA[j] for 0≤j<a and XOR results to obtain αA.(7)
DecryptC[j+1] to obtain αM[j] and M[j], where 0≤j<m.(8)
Compute∑M‍. Encrypt ∑M‍ and XOR the result with ατ, αA, and αM[∗]. Perform one final encryption to obtain Tverify.(9)
CompareTverify with T. If they do not match, the plaintext is not released to the recipient and an error symbol, Γ, is output.


#### 3.5.4. MAC-Only Mode

The proposed AEAD scheme can also be used solely as a MAC. In the MAC-only mode, the algorithm is the same except that ciphertext blocks need not be computed. In addition, the secret message number is unused and is set toτ=0.


### 3.6. Features

Chaos-based algorithms require real number computation which is usually performed using floating point representation. FxP representation is used to ensure that the proposed AEAD scheme is not platform-specific. In addition, it contributes to better performance as basic binary operations can be used on FxP variables which require fewer clock cycles than floating point operations.The proposed cipher has several features that are advantageous for AEAD designs. Firstly, each block of data can be processed in parallel. The only overhead is the iteration of the masking algorithm which has to be performed based on the block number. It is an online, one-pass cipher whereby the encryption of one block does not depend on other blocks. The verification algorithm is highly nonce-misuse resistant due to the randomly generatedτ. The proposed AEAD scheme also has out-of-order verification; whereby if any blocks are permuted or out of order, it will result in a different MAC.To achieve high security against cryptanalytic attacks, users have the option of using a TRNG to generateτ. A TRNG depends on physical phenomena; therefore τ becomes nondeterministic in nature. Each plaintext is then randomly mapped to different ciphertexts. However, anyone with the correct secret key is able to extract τ to decrypt and verify the message successfully regardless of how τ was generated. Although the randomization of τ contributes to strong security characteristics as described in Section 4.5.4, the proposed AEAD scheme becomes nonincremental in nature. The entire associated data or message needs to be recomputed if one block is changed because τ changes upon each encryption.


## 3.1. Parameters and Notations

All integers stated in the following algorithms are in hexadecimal format. Prior to modification by the nonce or secret keys, the initial values for all registers are arbitrarily chosen random numbers. The proposed 128-bit AEAD scheme has the following parameters:(i)
128-bit secret key,κ∈0,1128(ii)
64-bit nonce,η∈0,164(iii)
128-bit secret message number,τ∈{0,1}128(iv)
Associated data,A∈{0,1}∗(v)
Message,M∈{0,1}∗(vi)
128-bit tag,T∈{0,1}128The following are notations used in this paper:(i)
Length of a string,x, denoted by |x|(ii)
⊕: Bitwise XOR(iii)
∧: Bitwise AND(iv)
x∥y: Bitwise concatenation of x and y(v)
⊞n: n-bit modular addition(vi)
rotlrn(x): Bitwise left rotation by r positions on a n-bit variable, x where n=8,32,64(vii)
x≫y: Bitwise right shift of x by y bits(viii)
s(x): substitution function using an 8-bit s-box, s(ix)
ci(x): performing i-iterations of the chaotic map with an initial value x(x)
x: floor function to map a real number x to the previous largest integer(xi)
FPx: converting the FxP representation to real number(xii)
Φ: mask for the FxP fractional bitsBecause the AEAD design involves chaotic map iterations, round constants are used in several parts of the algorithms to prevent weak key problems. Weak keys can initialize the chaotic map’s initial condition to zero, which makes the system nonrandom and insecure. These round constants are taken from the list of prime numbers:rconi=2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, where 0≤i<32 is the index/round. The proposed AEAD scheme also uses a block shuffle π and its inverse as shown in Table 1.Table 1
Block shuffleπ and inverse block shuffle π-1.
x 0 1 2 3 4 5 6 7 8 9 a b c d e f π(x) 5 0 1 4 7 c 3 8 d 6 9 2 f a b e π-1(x) 1 2 b 6 3 0 9 4 7 a d e 5 8 f c


## 3.2. RandomS-Box Generation

The composition method [21] is used to generate chaos-based s-boxes for the AEAD scheme. The composition of two 8-bit permutations, f(x) and g(x), is denoted by h(x)=fgx,∀x∈I, where I is the set of all 8-bit integers. First, a set S consisting of four chaos-based s-boxes is generated by permuting the AES s-box. To obtain the final s-box, a composition of four s-boxes from S is used, where the s-boxes are selected based on randomly generated indices (repetitions are allowed). To generate the numbers used to permute AES and also as indices for the s-box composition, a chaos-based RNG is used. The initialization process and the RNG algorithm are as shown in Algorithms 1 and 2, respectively, where x and y are chaotic map initial conditions that are constantly modified by perturbation values, p and q.Algorithm 1:Initialization of the Chaos-based RNG.
(1)Input: 64-bit secret key values k0 and k1. (2)Output: Initialized variables x,y,p,q,r0,r1. (3)— (4) //Initialize variables (5)x←82dcbe4e⊕k0∧Φ,  y←49a2372c⊕k1∧Φ (6)p←(49a2372c⊕k0≫30), q←(945ae69b⊕(k1≫30)) (7)r0←3⊞8k0≫62, r1←(3⊞8(k1≫62)) (8)for  i=0  to  3  do (9)c50(x) (10)c50(y) (11)x←x⊕p⊞32rcon4i∧Φ (12)p←rotlr032p⊞32rcon4i+1 (13)y←y⊕q⊞32rcon4i+2∧Φ (14)q←rotlr132q⊞32rcon4i+3 (15)end forAlgorithm 2:Chaos-based RNG.
(1)Input: 32-bit initial values x and y, 32-bit perturbation values p and q, 8-bit rotation valuesr0 and r1. (2)Output: 32-bit random number R. (3) — (4)c50(x) (5)c50(y) (6)R←FPx⊕FPy (7)x←x⊕p∧Φ (8)p←rotlr032(p) (9)y←(y⊕q)∧Φ (10)q←rotlr132(q)The initialization process equally divides the secret key bitsκ=k1∥k0 into four registers and two rotation variables such that all key bits are used only once. During the initialization, round constants are used to ensure that values of κ that initialize all registers to zero will result in nonzero starting values for the RNG. A total of 200 iterations for each tent map are performed for transient elimination, although 48 iterations have been deemed sufficient [22].Each 8-bit s-box,sj∈S for 0≤j<4, is first initialized as the AES s-box. Next, Algorithm 2 is used to generate vij for 0≤i<256 for each sj. Each s-box is then permuted as follows:(2)sji=sjvij,sjvij=sji.To obtain the final s-box, sf, four additional values are generated by Algorithm 2. A four-modulo operation is applied on these values which are then used as s-box indices, Ii for 0≤i<4. The final s-box is a composition of the four s-boxes indexed by I: sf(x)=sI3(sI2(sI1(sI0(x)))). As sf depends only on κ, it can be precomputed by both parties. sf is later modified by τ in the actual encryption process.


## 3.3. Key Schedule Algorithm

The key scheduling algorithm generates 20 round keys from the secret keyκ. As they do not depend on η or τ, the keys can also be precomputed. The algorithm is based on the Feistel network, whereby the secret key is first divided into two halves, κ=k1∥k0. k0 and k1 are then XOR-ed into two registers that have initial values of reg0=f492e42164c7fb0d and reg1=f683d0ad038f17d. The tent map’s initial condition is set to x=0. One round of the key scheduling function is shown in Figure 2, where i is the round number.Figure 2
Key Schedule Feistel Network.TheG-function is described in Algorithm 3. The network is executed 16 times for transient elimination without producing any keys. Starting from round number i=0,20 round keys are then produced from 20 rounds of the network. Excluding transient elimination rounds, each round key is generated from a total 640 iterations of the chaotic tent map. The value of O is modified 64 times, where, each time, it is subjected to a four-bit rotation to ensure that all 64 bits are modified by x in 16 passes. reg1 is rotated by 15 bits each time to ensure that its upper and lower bits are all used in the chaotic iterations.Algorithm 3:Key schedule G-function.
(1)Input: 64-bit register reg1, 32-bit initial condition x, round number i. (2)Output: 64-bit output, O. (3) — (4)O←0 (5)for  j=0  to  63  do (6)x←x⊕reg1∧Φ (7)c10(x) (8)O←O⊕x (9)O←rotl464(O) (10)reg1←rotl1564(reg1) (11)end for (12)O←O⊕rconi


## 3.4. Masking Algorithm

The proposed AEAD scheme is based on the single-key Even-Mansour construction that has been proven to have the same level of security as the original two-key construction [10]. 16 eight-bit mask registers are first initialized based on the secret key and nonce and then modified by a chaotic function. The values of these registers are used as the prewhitening and postwhitening masking keys for each block of data. The initialization of the mask registers and variables for the chaotic function are summarized in Figure 3, where κ=k1∥k0.Figure 3
Masking Algorithm Initialization.After the mask and chaotic variables are initialized, the masking algorithm is iterated eight times for transient elimination and to diffuse the key bits into all registers. The masking algorithm is as shown in Algorithm4 where registers (x,y,p,q) are involved in chaotic perturbation. These registers are then used to modify the mask registers, λ. Round constants are only used in the transient elimination rounds to generate nonzero initial mask values. The mask registers are later modified by τ in the encryption process.Algorithm 4:Mask algorithm.
(1)Input: 8-bit mask registers λj for 0≤j<16, 32-bit initial values x and y, 32-bit perturbation valuesp and q, round/block number i. (2)Output: Modified 8-bit mask registers λj for 0≤j<16 (3) — (4)x←c1(x), y←c1(y) (5)if Transient Elimination then (6)x←x⊕p⊞32rcon4i (7)y←y⊕q⊞32rcon4i+1 (8)p←p⊕y⊞32rcon4i+2 (9)q←q⊕x⊞32rcon4i+3 (10)else (11)x←x⊕p (12)y←y⊕q (13)p←p⊕y (14)q←q⊕x (15)end if (16)for  j=0  to  3  do (17)λj←λj⊞8x≫8j∧FF (18)λj+4←λj+4⊞8y≫8j∧FF (19)λj+8←λj+8⊞8p≫8j∧FF (20)λj+12←λj+12⊞8q≫8j∧FF (21)end for (22)for  j=0  to  15  do (23)λπj←λj (24)end for (25)x←x∧Φ, y←y∧Φ


## 3.5. Algorithm Description

The overall design of the AEAD is based on the single-key Even-Mansour scheme [10] and a Type-II generalized Feistel structure (GFS) [23]. There are two main functions, aead_encrypt and aead_decrypt. aead_encrypt encrypts M and τ and also generates a tag, T, to verify A, M, and τ. aead_decrypt decrypts C to obtain M and τ and then generates T to verify the authenticity of A, M, and τ. If verification fails, the decrypted message is not released to the recipient. The aead_encrypt algorithm is shown in Figure 4, where a is the number of A blocks, m is the number of M blocks, α represents intermediate tags, ∑M‍ is the checksum, and λ[i] is the set of mask registers for block-i of data. The aead_decrypt algorithm has the same structure as aead_encrypt. However the inverse block shuffle π-1 and reversed round keys are used to decrypt C and to generate the intermediate tags, αM∗.Figure 4
Encryption Algorithm.


### 3.5.1. Round Function

The round function,Fj, is executed 20 times for all data blocks where j denotes the number of rounds. The same 20 round keys generated by the key scheduling algorithm are used for all blocks. When processing message blocks (M∗), F20 is divided into two halves, F20=F10·F10 where the output of the first 10 rounds is used as the intermediate tag αM∗. The round function is based on the Type-II GFS as shown in Figure 5. The 64-bit round key rki is divided into 8 bytes, where its most significant byte is fed into the left most h-function. The h-function consists of two operations, XOR of the round key and substitution:(3)hx=sfXd⊕rkie,where d and e are byte indexes of the data block and round key, respectively.Figure 5
AEADF-function.


### 3.5.2. Modification ofS-Box and Mask

For further security,τ is used to modify both sf and λ prior to processing the first block of data. To modify sf, two more indexes for s-box composition are obtained from τ, Iτ0, and Iτ1. Iτ0 is obtained by XOR-ing each of the eight most significant bytes of τ whereas Iτ1 is obtained by XOR-ing each of the eight least significant bytes. The final s-box is computed by composing two additional s-boxes: sfinal(x)=sIτ1sIτ0sfx. The modification of λ registers is performed by XOR-ing each byte of τ to each byte of λ.


### 3.5.3. AEAD Mode

The encryption and tag generation process is as follows:(1)
Usingκ, generate rki for 0≤i<20 and sf.(2)
Initializeλ based on κ and η.(3)
Encryptτ to obtain C0 and ατ.(4)
Generatesfinal and modify λ using τ (Section 3.5.2).(5)
IfA and M are not 128-bit multiples, pad A and M with a single bit of “1,” followed by all “0” until the required length.(6)
EncryptAj for 0≤j<a and XOR results to obtain αA.(7)
EncryptM[j] to obtain αM[j] and C[j+1], where 0≤j<m.(8)
Compute∑M‍. Encrypt ∑M‍ and XOR the result with ατ, αA, and αM[∗]. Perform one final encryption to obtain T.The decryption and tag verification process is as follows:(1)
Usingκ, generate rki for 0≤i<20 and sf.(2)
Initializeλ based on κ and η.(3)
DecryptC[0] to obtain τ and ατ.(4)
Generatesfinal and modify λ using τ (Section 3.5.2).(5)
If|A| is not a 128-bit multiple, pad A with a single bit of “1" followed by all “0" until the required length.(6)
EncryptA[j] for 0≤j<a and XOR results to obtain αA.(7)
DecryptC[j+1] to obtain αM[j] and M[j], where 0≤j<m.(8)
Compute∑M‍. Encrypt ∑M‍ and XOR the result with ατ, αA, and αM[∗]. Perform one final encryption to obtain Tverify.(9)
CompareTverify with T. If they do not match, the plaintext is not released to the recipient and an error symbol, Γ, is output.


### 3.5.4. MAC-Only Mode

The proposed AEAD scheme can also be used solely as a MAC. In the MAC-only mode, the algorithm is the same except that ciphertext blocks need not be computed. In addition, the secret message number is unused and is set toτ=0.


## 3.5.1. Round Function

The round function,Fj, is executed 20 times for all data blocks where j denotes the number of rounds. The same 20 round keys generated by the key scheduling algorithm are used for all blocks. When processing message blocks (M∗), F20 is divided into two halves, F20=F10·F10 where the output of the first 10 rounds is used as the intermediate tag αM∗. The round function is based on the Type-II GFS as shown in Figure 5. The 64-bit round key rki is divided into 8 bytes, where its most significant byte is fed into the left most h-function. The h-function consists of two operations, XOR of the round key and substitution:(3)hx=sfXd⊕rkie,where d and e are byte indexes of the data block and round key, respectively.Figure 5
AEADF-function.


## 3.5.2. Modification ofS-Box and Mask

For further security,τ is used to modify both sf and λ prior to processing the first block of data. To modify sf, two more indexes for s-box composition are obtained from τ, Iτ0, and Iτ1. Iτ0 is obtained by XOR-ing each of the eight most significant bytes of τ whereas Iτ1 is obtained by XOR-ing each of the eight least significant bytes. The final s-box is computed by composing two additional s-boxes: sfinal(x)=sIτ1sIτ0sfx. The modification of λ registers is performed by XOR-ing each byte of τ to each byte of λ.


## 3.5.3. AEAD Mode

The encryption and tag generation process is as follows:(1)
Usingκ, generate rki for 0≤i<20 and sf.(2)
Initializeλ based on κ and η.(3)
Encryptτ to obtain C0 and ατ.(4)
Generatesfinal and modify λ using τ (Section 3.5.2).(5)
IfA and M are not 128-bit multiples, pad A and M with a single bit of “1,” followed by all “0” until the required length.(6)
EncryptAj for 0≤j<a and XOR results to obtain αA.(7)
EncryptM[j] to obtain αM[j] and C[j+1], where 0≤j<m.(8)
Compute∑M‍. Encrypt ∑M‍ and XOR the result with ατ, αA, and αM[∗]. Perform one final encryption to obtain T.The decryption and tag verification process is as follows:(1)
Usingκ, generate rki for 0≤i<20 and sf.(2)
Initializeλ based on κ and η.(3)
DecryptC[0] to obtain τ and ατ.(4)
Generatesfinal and modify λ using τ (Section 3.5.2).(5)
If|A| is not a 128-bit multiple, pad A with a single bit of “1" followed by all “0" until the required length.(6)
EncryptA[j] for 0≤j<a and XOR results to obtain αA.(7)
DecryptC[j+1] to obtain αM[j] and M[j], where 0≤j<m.(8)
Compute∑M‍. Encrypt ∑M‍ and XOR the result with ατ, αA, and αM[∗]. Perform one final encryption to obtain Tverify.(9)
CompareTverify with T. If they do not match, the plaintext is not released to the recipient and an error symbol, Γ, is output.


## 3.5.4. MAC-Only Mode

The proposed AEAD scheme can also be used solely as a MAC. In the MAC-only mode, the algorithm is the same except that ciphertext blocks need not be computed. In addition, the secret message number is unused and is set toτ=0.


## 3.6. Features

Chaos-based algorithms require real number computation which is usually performed using floating point representation. FxP representation is used to ensure that the proposed AEAD scheme is not platform-specific. In addition, it contributes to better performance as basic binary operations can be used on FxP variables which require fewer clock cycles than floating point operations.The proposed cipher has several features that are advantageous for AEAD designs. Firstly, each block of data can be processed in parallel. The only overhead is the iteration of the masking algorithm which has to be performed based on the block number. It is an online, one-pass cipher whereby the encryption of one block does not depend on other blocks. The verification algorithm is highly nonce-misuse resistant due to the randomly generatedτ. The proposed AEAD scheme also has out-of-order verification; whereby if any blocks are permuted or out of order, it will result in a different MAC.To achieve high security against cryptanalytic attacks, users have the option of using a TRNG to generateτ. A TRNG depends on physical phenomena; therefore τ becomes nondeterministic in nature. Each plaintext is then randomly mapped to different ciphertexts. However, anyone with the correct secret key is able to extract τ to decrypt and verify the message successfully regardless of how τ was generated. Although the randomization of τ contributes to strong security characteristics as described in Section 4.5.4, the proposed AEAD scheme becomes nonincremental in nature. The entire associated data or message needs to be recomputed if one block is changed because τ changes upon each encryption.


## 4. Security Analysis

This section examines the security of all components of the proposed AEAD scheme. For all tests, inputs are set to zero (κ=0,  η=0,  τ=0) unless stated otherwise. As it is difficult to provide mathematical proof for real number-based cryptographic algorithms, the AEAD scheme is evaluated mainly using statistical means.


### 4.1. Preliminary Statistical Testing

Before other evaluation methods are used, statistical test suites such as NIST SP 800-22 [24], DIEHARD [25], and ENT [26] are used as preliminary tests for majority of the AEAD components. The minimum/maximum passing ratio (PR) for NIST and DIEHARD for a significance level of 0.01 is calculated based on (4), where N is the number of samples, as follows:(4)PR=0.99±3×0.99×0.01N.The summary of inputs required for each test suite is listed below. (i)
NIST: 1000-Mbit file generated withκ=0,  η=0,  τ=0, divided into 1000 samples(ii)
DIEHARD: 50 87.5-Mbit files generated withκ=rand,  η=0,  τ=0; each DIEHARD suite has 18 tests with multiple P values that are each taken as individual samples(iii)
ENT: 87.5-Mbit file generated withκ=0,  η=0,  τ=0.The minimum P value to indicate uniformity for each NIST test is 0.0001 whereas the DIEHARD tests require P values in the range of 0.01,0.99. The min/max PR for the NIST and DIEHARD test suites are listed in Table 6 of the Appendix. As for the ENT test suite, a number sequence fails if its results stray too far from the ideal values listed in Table 7 of the Appendix. Passing all three test suites indicates that the number sequence is pseudorandom with no obvious statistical defects.


### 4.2.S-Box Evaluation

Random s-boxes are generated based on a chaotic number sequence which is tested using the NIST, DIEHARD, and ENT test suites. It passes all three as shown in Tables8, 12, and 16 of the Appendix. In the following experiments, s-boxes are produced for κ=rand,  η=0,  τ=0 where their characteristics such as the avalanche effect, strict avalanche criterion (SAC), linear and differential probability, nonlinearity, and keyspace are examined.


#### 4.2.1. Avalanche and Strict Avalanche Criterion

To exhibit the avalanche effect, one-half of the output bits should change on average whenever a single input bit is toggled. To determine if an 8-bit s-box fulfils this requirement, the28 possible inputs are first divided into 27 pairs, X,Xi, which differ only in bit i. The 8-bit avalanche vectors, Vi, are then calculated for all (0≤i<8) as follows:(5)Vi=sX⊕sXi.For 10000 random s-boxes all possible input pairs are tested. Results indicate that 50.1899% of each Vi bits are equal to one when an input differs in only bit i.To satisfy the SAC, each individual output bit should change with a probability of 50% when a single input bit is toggled. Similar to the previous test,28 possible inputs are first divided into 27 pairs, X,Xi, which differ only in bit i. The 8-bit avalanche vectors, Vi are then calculated for all (0≤i<8). For 10000 random s-boxes and all possible input pairs, the average probability that a bit location in Vi is equal to one when an input differs in only bit i is 50.1993%.Both results show that the s-boxes generated by the proposed AEAD scheme have strong avalanche effect and fulfil the SAC. Satisfying the SAC also implies that the s-box is a complete function, whereby each output bit is dependent on all input bits [27].


#### 4.2.2. Differential Distribution and Linear Approximation

For 10000 randomly generated s-boxes, the differential distribution [28] and linear approximation [29] tables are computed. These tables consist of the probabilities of differential and linear characteristics for various input/output combinations that can be used in differential and linear attacks. The worst case differential and linear probabilities are 2-4.67807 and 2-2.91254, respectively. These probabilities are sufficient to resist cryptanalytic attacks which are described in Section 4.5.


#### 4.2.3. Nonlinearity and Key Sensitivity

LetF2n be the n-dimensional vector space over the field F2. The nonlinearity of a function F:F2n→F2n is defined by(6)NLF=2n-1-12maxa∈F2n,b∈F2n⁡∑x∈F2n-1b·Fx+a·x.A perfectly nonlinear function has a nonlinearity of NLF=2n-1-2n/2-1, which is 120 for an 8-bit s-box. Out of 10000 randomly generated s-boxes, the average nonlinearity is 92.6646, which is 77.22% nonlinear. The generated s-boxes have lower nonlinearity than the AES s-box (NL(FAES)=112). However, unlike a static s-box, attackers cannot linearly approximate a randomized s-box without knowledge of the keys used to generate it. Therefore, slight changes to the secret key should generate different s-boxes. For all 128-bit secret keys with hamming weight of one, the proposed AEAD scheme generates unique s-boxes. In addition, for 2000 incrementally generated s-boxes (κ=0 to κ=7d0), all s-boxes are also unique. This shows that the random s-box algorithm is highly sensitive to slight changes to κ.


### 4.3. Mask Evaluation

The output of the masking algorithm is first tested using the NIST, DIEHARD, and ENT test suites. The 128-bit mask values generated by the AEAD scheme successfully pass all three as shown in Tables9, 13, and 17 of the Appendix.


#### 4.3.1. Mask Cycle Length

The cycle length of the masking algorithm must be sufficiently large to avoid attacks that can take advantage of any mask value cycles. Theoretically, the cycle length is limited by the precision of the fixed point representation used in chaotic iterations. This amounts to230-1, as 30 bits are used to represent the fractional bits. This is a conservative bound, as chaotic perturbation and chaotic coupling further extend the cycle length. Because there are two chaotic maps used to modify the mask registers, the total cycle length is the least common multiple of their cycle lengths. Based on this lower bound, the proposed AEAD scheme will be able to support messages of approximately 260-1 blocks before a mask cycle occurs.


### 4.4. Key Schedule Evaluation

The key schedule algorithm generates only 20 round keys for a secret key. Therefore, data for the statistical test suites are generated using incremental secret keys (incremented fromκ=0) except for the DIEHARD test which still uses randomly generated secret keys. Results in Tables 10, 14, and 18 of the Appendix indicate that the key schedule algorithm passes all test suites.


#### 4.4.1. Avalanche and Strict Avalanche Criterion

The key schedule algorithm is analysed for avalanche effect and SAC similar to the s-box evaluation in Section4.2.1. The avalanche vectors Vi are calculated using (5), where 10000 randomly generated pairs of X, Xi are used as inputs. To depict the avalanche effect, one-half of each round key should change on average whenever a single input key bit is toggled. The percentages of Vi bits that are equal to one when the input key differs in only bit i are 50.0403%, 49.99%, 50.0719%, 49.9422%, 49.9228%, 49.9047%, 50.0417%, 49.92%, 49.9942%, 49.9925%, 49.8973%, 50.0503%, 50.1373%, 50.0075%, 49.9709%, 49.9975%, 50.0342%, 50.0542%, 49.9628%, and 49.9153% for each of the 20 rounds, respectively. This has an overall average of 49.9924% per round.To fulfil the SAC, each round key bit should change with a probability of 50% when a single input key bit is toggled. For each of the 20 rounds, the average probabilities that a bit location inVi is equal to one when the input key differs in only bit i are 49.9998%, 49.9891%, 50.0914%, 49.8953%, 49.9978%, 49.9583%, 49.9866%, 50.0108%, 49.9941%, 49.9044%, 49.9095%, 49.9452%, 50.0287%, 50.0473%, 50.0302%, 50.0439%, 50.0852%, 50.017%, 50.0633%, and 49.9419%. This has an overall average of 49.997% per round.Results show that the key schedule algorithm has strong avalanche effect and fulfils the SAC. This implies that the key schedule algorithm is a complete function, where all round key bits are dependent on all input secret key bits.


### 4.5. Encryption Algorithm Security

This section analyses the security of the AEAD scheme against various cryptanalytic attacks. A lower bound of security against these attacks is first determined withτ=0. Then, additional security provided by using a TRNG to generate τ is discussed. Prior to other security analyses, the ciphertext of the AEAD scheme is tested using statistical suites with results in Tables 11, 15, and 19.


#### 4.5.1. Differential and Linear Cryptanalysis

The security bound for differential and linear cryptanalysis can be determined based on the minimum number of active s-boxes for a differential characteristic (ASDr) and linear characteristic (ASLr), where r is the number of rounds. The number of AS is dependent on the type of block shuffle used in the round function. In an early design, the number 10 block shuffle from [30] was used in the proposed AEAD scheme, supposedly with ASD20/ASL20=44. However, a branch and bound algorithm was used and found that ASD20/ASL20=37. Instead, an isomorphic shuffle to the number 10 shuffle was used, adopted from [31] with ASDr and ASLr for 1≤r≤20 shown in Table 2.Table 2
List of active S-boxes.
Round,r A S D r, ASLr 1 0 2 1 3 2 4 3 5 4 6 6 7 8 8 11 9 14 10 18 11 22 12 24 13 27 14 30 15 32 16 35 17 36 18 39 19 41 20 44The maximum differential and linear probabilities for the AEAD scheme’s s-boxes arePD=2-4.67807 and PL=2-2.91254, respectively as mentioned in Section 4.2.2. The probability for differential and linear distinguishers are calculated using(7)Pdiff-distr=PDASDr,Plin-distr=12+2ASLr-1×PLASLr.For r=14 and r=16, Pdiff-dist14=2-140.3421 and Plin-dist16=1/2+2-67.9389, where 2-67.9389 is the linear bias, denoted by εlin. The number of plaintexts required for a differential and linear distinguishing attack is then 1/Pdiff-dist14=2140.3421 and 1/εlin2=2135.8778, respectively, which are both more than the available 2128. Therefore, the full 20 rounds have a safe security margin against differential and linear cryptanalysis.


#### 4.5.2. Algebraic Attack

In an algebraic attack, s-boxes are described by an overdefined system of algebraic equations that hold true with a probability of one [32]. The use of random s-boxes increases the resistance of a cipher against this attack [33]. The proposed AEAD scheme uses key-dependent s-boxes which are further randomized by τ; therefore it is difficult to obtain a system of equations for these s-boxes. Without these equations, an algebraic attack is not feasible. The proposed cipher is thus resistant to algebraic attacks.


#### 4.5.3. Timing Attack

Timing attacks exploit operations with data-dependent execution time to reveal the secret key [34, 35]. In the proposed AEAD scheme, the secret key is used to generate s-boxes and round keys and also to initialize the mask register. The remaining operations consist of Bitwise operations that have constant execution time. Therefore, the proposed cipher is resistant to timing attacks because its encryption speed is independent of the key value.


#### 4.5.4. Security with True Random Secret Message Number

Ifτ is generated by a nondeterministic TRNG, the cipher is able to resist a wide range of statistical-based cryptanalytic attacks. A nondeterministic τ ensures that multiple encryptions of even the same (A,M) pair will involve different s-boxes and masking values. This leads to different (C,T) outputs. However, a legitimate recipient can easily decrypt and verify these ciphertext-MAC pairs as long as the secret key is correct.Randomized s-boxes prevent any cryptanalytic attacks that rely on approximating the behavior of the s-box, such as differential, linear, and algebraic attacks. Even if an approximation of the s-box is obtained for a particular plaintext-ciphertext pair, it is only applicable to that specific pair. The cipher is also immune to attacks that rely on selecting input differences that cancel out the effect of encryption keys such as the differential attack, truncated differential attack, and impossible differential attack. This is because the masking keys are modified by the truly randomτ, making them nondeterministic for each plaintext encryption. For a differential characteristic to hold, τ values for a plaintext pair have to match, which occurs with a probability of 2-128 for a uniform TRNG.Key recovery attacks based on anr-round statistical distinguisher involve the encryption of multiple plaintexts for r+g rounds to obtain their corresponding (r+g)-round ciphertexts. Attackers then guess subkey bits, decrypt the ciphertext for g rounds, and verify their guess based on the r-round statistical distinguisher. If τ is nondeterministic, attackers will not be able to obtain the correct subkey using this method as each plaintext is encrypted based on different s-boxes and masking keys. In practice, the statistical distinguisher only holds if two plaintexts are encrypted with same τ, which again occurs with a probability of 2-128 for a uniform TRNG.As previously mentioned, generatingτ using a TRNG makes the cipher misuse resistant. If the same nonce is used twice, the resulting MAC and ciphertext are still secure as long as τ is not repeated for the same (A,M,η) 3-tuple. In short, implementing the proposed AEAD scheme with a TRNG or even a hybrid RNG will strengthen its immunity against statistical-based cryptanalysis as well as user misuse.


### 4.6. MAC Security

This section analyses the statistical quality of the authentication tag produced by the proposed AEAD scheme. In the following experiments, the input parameters are set toκ=0,  η=0,  τ=0, whereby only A and M vary.


#### 4.6.1. Statistical Analysis of Diffusion and Confusion

In this test, an (A,M) pair is randomly generated and its corresponding tag, T, is computed. Next, a random bit within the (A,M) pair is toggled and its corresponding tag, T′, is computed. T and T′ values are compared and the number of changes at each bit location is stored as Xi. The following equations are then computed:Mean Changed Bit Number (8) X ¯ = 1 N ∑ i = 1 N X i .Mean Changed Probability (9) P = X ¯ 128 × 100 % .Standard Variance of the Changed Bit Number (10) Δ X = 1 N - 1 ∑ i = 1 N X i - X ¯ 2 .Standard Variance (11) Δ P = 1 N - 1 ∑ i = 1 N X i 128 - P 2 × 100 % ,where N is the number of trials. The test is performed for N=1024/2048/10000 and the results are tabulated in Table 3. The distribution plot and histogram of Xi for N=10000 are shown in Figures 7 and 6. Results show that the MAC values have a mean changed bit number, X¯, and mean changed probability, P, that are near-ideal (64 bits and 50%). Low standard variance values depict strong diffusion and confusion capabilities. In Figures 7 and 6, Xi is shown to be evenly and normally distributed centering on 64 bits. These near-ideal statistical results indicate that the slightest change to the A or M will produce a different authentication tag.Table 3
Statistical results for 128-bit hash values of the proposed hash function.
Param/N 1024 2048 10000 Mean X- 64.0010 64.0078 63.9968 64.0019 P(%) 50.0008 50.0061 49.9975 50.0015 ΔX 5.6291 5.6755 5.6291 5.6446 ΔP(%) 4.3977 4.4340 4.3978 4.4098 Xmin 47 45 45 45.67 Xmax 83 83 86 84Figure 7
Distribution plot ofXi.Figure 6
Distribution histogram ofXi.


#### 4.6.2. Analysis of Collision Resistance

Similar to Section4.6.1, MACs for an (A,M) pair and a slightly modified A,M′ pair are produced and stored in ASCII format. The two MACs are compared and the number of hits (equal ASCII characters in the same position) are counted. Next, the absolute difference, D, between the two MACs is calculated as follows:(12)D=∑i=1Ndei-dei′,where ei and ei′ are the ith entry of the original and modified MAC, while the function d(∗) converts the entry to its equivalent decimal value. The test results for 10000 trials are compared against theoretical values (see [36] for calculation of theoretical values) in Tables 4 and 5. Results indicate that the proposed AEAD scheme has strong collision resistance as the experimental results are near-ideal.Table 4
Number of hits.
Hits 0 1 2 3 4 5 6 Theoretical 9416 572 12 0 0 0 0 Experimental 9428 558 13 1 0 0 0Table 5
Absolute difference.
Results Minimum Maximum Mean Theoretical — — 1360 Experimental 574 2352 1362.55Table 6
Passing Ratios for NIST and DIEHARD.
Test name Samples Min. PR Max. PR NIST (except random excursions) 1000 0.981 0.999 NIST, random excursions 625 0.978 1.000 DIEHARD, birthday spacings 500 0.977 1.000 DIEHARD, overlapping 5-permutation 100 0.961 1.000 DIEHARD, binary rank 31 × 31 matrices 50 0.949 1.000 DIEHARD, binary rank 32 × 32 matrices 50 0.949 1.000 DIEHARD, binary rank 6 × 8 matrices 1300 0.982 0.998 DIEHARD, bitstream 1000 0.981 0.999 DIEHARD, overlapping-pairs-sparse-occupancy 1150 0.981 0.999 DIEHARD, overlapping-quadruples-sparse-occupancy 1400 0.9822 0.998 DIEHARD, DNA spacings 1550 0.983 0.997 DIEHARD, Count-the-1s on a Stream of Bytes 100 0.961 1.000 DIEHARD, count-the-1s on specific bytes 1250 0.982 0.998 DIEHARD, parking lot 550 0.978 1.000 DIEHARD, minimum distance 50 0.949 1.000 DIEHARD, 3D-spheres 1050 0.984 0.999 DIEHARD, squeeze 50 0.949 1.000 DIEHARD, overlapping sums 550 0.978 1.000 DIEHARD, runs 200 0.969 1.000 DIEHARD, craps 100 0.961 1.000Table 7
Ideal values for ENT test suite.
Test name Ideal value Entropy 8.0 Chi-square 50% Arithmetic mean 127.5 Monte Carlo value forπ 3.141592653 Serial correlation coefficient 9Table 8
NIST: S-box chaotic sequence.
Test name P value Passing ratio Result Frequency 0.771469 0.993 Pass Block frequency 0.759756 0.989 Pass Cumulative sums 0.122325 0.990 Pass Runs 0.179584 0.990 Pass Longest run 0.446556 0.989 Pass Rank 0.568739 0.993 Pass FFT 0.689019 0.991 Pass Nonoverlapping templates 0.224821 0.981 Pass Overlapping templates 0.146152 0.984 Pass Universal 0.011383 0.982 Pass Approximate entropy 0.042808 0.987 Pass Random excursions 0.173679 0.987 Pass Random excursions variant 0.711017 0.981 Pass Serial 0.803720 0.981 Pass Linear complexity 0.660012 0.990 PassTable 9
NIST: Masking algorithm.
Test Name P value Passing ratio Result Frequency 0.390721 0.991 Pass Block frequency 0.530120 0.987 Pass Cumulative sums 0.259616 0.989 Pass Runs 0.406499 0.992 Pass Longest run 0.307077 0.989 Pass Rank 0.066882 0.991 Pass FFT 0.556460 0.981 Pass Nonoverlapping templates 0.238035 0.982 Pass Overlapping templates 0.676615 0.984 Pass Universal 0.834308 0.992 Pass Approximate entropy 0.915317 0.991 Pass Random excursions 0.582671 0.979 Pass Random excursions variant 0.422281 0.993 Pass Serial 0.875539 0.984 Pass Linear complexity 0.890582 0.989 PassTable 10
NIST: Key schedule.
Test Name P value Passing ratio Result Frequency 0.085587 0.991 Pass Block frequency 0.008629 0.989 Pass Cumulative sums 0.719747 0.990 Pass Runs 0.143686 0.990 Pass Longest run 0.467322 0.989 Pass Rank 0.363593 0.993 Pass FFT 0.015816 0.987 Pass Nonoverlapping templates 0.540204 0.981 Pass Overlapping templates 0.065230 0.988 Pass Universal 0.401199 0.991 Pass Approximate entropy 0.077131 0.996 Pass Random excursions 0.098397 0.982 Pass Random excursions variant 0.884892 0.984 Pass Serial 0.446556 0.989 Pass Linear complexity 0.249284 0.990 PassTable 11
NIST: ciphertext.
Test name P value Passing ratio Result Frequency 0.206629 0.989 Pass Block frequency 0.207730 0.997 Pass Cumulative sums 0.206629 0.990 Pass Runs 0.373625 0.995 Pass Longest run 0.016149 0.987 Pass Rank 0.388990 0.989 Pass FFT 0.954930 0.987 Pass Nonoverlapping templates 0.454053 0.982 Pass Overlapping templates 0.467322 0.985 Pass Universal 0.129620 0.985 Pass Approximate entropy 0.358641 0.990 Pass Random excursions 0.866173 0.986 Pass Random excursions variant 0.956262 0.991 Pass Serial 0.887645 0.992 Pass Linear complexity 0.271619 0.986 PassTable 12
DIEHARD: S-box chaotic sequence.
Test name Passing ratio Result Birthday spacings 0.978 Pass Overlapping 5-permutation 0.970 Pass Binary Rank 31 × 31 matrices 0.980 Pass Binary Rank 32 × 32 matrices 1.00 Pass Binary Rank 6 × 8 matrices 0.985 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.982 Pass Overlapping-quadruples-sparse-occupancy 0.983 Pass DNA spacings 0.985 Pass Count-the-1s on a stream of bytes 0.980 Pass Count-the-1s on specific bytes 0.983 Pass Parking lot 0.978 Pass Minimum distance 0.960 Pass 3D-spheres 0.990 Pass Squeeze 0.960 Pass Overlapping sums 0.985 Pass Runs 0.980 Pass Craps 0.990 PassTable 13
DIEHARD: masking algorithm.
Test Name Passing Ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 1.000 Pass Binary rank 32 × 32 matrices 0.960 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.983 Pass Overlapping-quadruples-sparse-occupancy 0.984 Pass DNA spacings 0.984 Pass Count-the-1s on a stream of bytes 0.990 Pass Count-the-1s on specific bytes 0.984 Pass Parking lot 0.980 Pass Minimum distance 0.960 Pass 3D-spheres 0.985 Pass Squeeze 0.980 Pass Overlapping sums 0.980 Pass Runs 0.990 Pass Craps 0.990 PassTable 14
DIEHARD: key schedule.
Test name Passing ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 0.980 Pass Binary rank 32 × 32 matrices 1.000 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.983 Pass Overlapping-quadruples-sparse-occupancy 0.982 Pass DNA spacings 0.983 Pass Count-the-1s on a stream of bytes 0.970 Pass Count-the-1s on specific bytes 0.982 Pass Parking lot 0.980 Pass Minimum distance 0.980 Pass 3D-spheres 0.984 Pass Squeeze 1.000 Pass Overlapping sums 0.987 Pass Runs 0.975 Pass Craps 0.970 PassTable 15
DIEHARD: ciphertext.
Test name Passing ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 0.980 Pass Binary rank 32 × 32 matrices 0.980 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.987 Pass Overlapping-pairs-sparse-Occupancy 0.982 Pass Overlapping-quadruples-sparse-occupancy 0.984 Pass DNA Spacings 0.985 Pass Count-the-1s on a stream of bytes 0.970 Pass Count-the-1s on specific bytes 0.983 Pass Parking lot 0.978 Pass Minimum distance 0.980 Pass 3D-spheres 0.983 Pass Squeeze 0.960 Pass Overlapping sums 0.980 Pass Runs 0.970 Pass Craps 1.000 PassTable 16
ENT: S-box chaotic sequence.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.13% Pass Arithmetic mean 127.5205 Pass Monte Carlo value forπ 3.140525649 Pass Serial correlation coefficient −0.000300 PassTable 17
ENT: masking algorithm.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.08% Pass Arithmetic mean 127.4735 Pass Monte Carlo value forπ 3.141910973 Pass Serial correlation coefficient −0.000407 PassTable 18
ENT: vey schedule.
Test Name Test value Result Entropy 7.999984 Pass Chi-square 62.61 Pass Arithmetic mean 127.4953 Pass Monte Carlo value forπ 3.140523556 Pass Serial correlation coefficient −0.000304 PassTable 19
ENT: Ciphertext.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.43% Pass Arithmetic mean 127.5039 Pass Monte Carlo value forπ 3.141705895 Pass Serial correlation coefficient 0.000032 Pass


#### 4.6.3. MAC Distribution

To resist statistical attacks, a MAC has to be evenly distributed at each bit position. Analysis of the MAC distribution starts with generating a random (A,M) pair and its modified version with one toggled bit, A,M′. The MAC of both messages is compared, and the number of changes at each bit location is counted. For N=10000, the minimum, maximum, and mean changed bit number are 4877, 5150, and 5002.3, respectively, with the distribution plot shown in Figure 8. The mean changed bit number is close to the theoretical value of 5000, where the maximum distance from ideal for each changed bit value is 150. This indicates that proposed AEAD scheme produces evenly distributed MAC values as depicted in Figure 8.Figure 8
Distribution of MAC.


### 4.7. Advantage over AES-GCM

The proposed scheme has several advantages over AES-GCM which is currently the official standard for authenticated encryption [37]. Firstly, the proposed AEAD scheme does not have any identified weak keys unlike AES-GCM [6]. It is also resistant to nonce-misuse, providing full privacy and integrity even if nonce is repeated, unlike AES-GCM which requires unique nonce values for security [37]. Most software-based AES implementations are susceptible to cache timing attacks [35], whereas the proposed cipher has a constant time implementation due to simple binary operations. AES-GCM’s security bound for integrity is equal to half the tag length [6] whereas the proposed AEAD scheme is able to provide full 128-bit security for integrity. Furthermore, the proposed AEAD scheme also has the flexibility to be implemented with a TRNG for immunity to statistical-based attacks.In terms of performance, the speed of AES-GCM was compared against the proposed cipher on a computer with an Intel i7-4700MQ processor and 8 GB of RAM. The implementation of AES-GCM was taken from the Crypto++ Library 5.6.2 [38]. The proposed AEAD scheme has a speed of 2401.73 Megabits/second compared to 1601.4 Megabits/second of AES-GCM, approximately 1.5 times faster. The algorithm can still be further optimized for improved performance.


## 4.1. Preliminary Statistical Testing

Before other evaluation methods are used, statistical test suites such as NIST SP 800-22 [24], DIEHARD [25], and ENT [26] are used as preliminary tests for majority of the AEAD components. The minimum/maximum passing ratio (PR) for NIST and DIEHARD for a significance level of 0.01 is calculated based on (4), where N is the number of samples, as follows:(4)PR=0.99±3×0.99×0.01N.The summary of inputs required for each test suite is listed below. (i)
NIST: 1000-Mbit file generated withκ=0,  η=0,  τ=0, divided into 1000 samples(ii)
DIEHARD: 50 87.5-Mbit files generated withκ=rand,  η=0,  τ=0; each DIEHARD suite has 18 tests with multiple P values that are each taken as individual samples(iii)
ENT: 87.5-Mbit file generated withκ=0,  η=0,  τ=0.The minimum P value to indicate uniformity for each NIST test is 0.0001 whereas the DIEHARD tests require P values in the range of 0.01,0.99. The min/max PR for the NIST and DIEHARD test suites are listed in Table 6 of the Appendix. As for the ENT test suite, a number sequence fails if its results stray too far from the ideal values listed in Table 7 of the Appendix. Passing all three test suites indicates that the number sequence is pseudorandom with no obvious statistical defects.


## 4.2.S-Box Evaluation

Random s-boxes are generated based on a chaotic number sequence which is tested using the NIST, DIEHARD, and ENT test suites. It passes all three as shown in Tables8, 12, and 16 of the Appendix. In the following experiments, s-boxes are produced for κ=rand,  η=0,  τ=0 where their characteristics such as the avalanche effect, strict avalanche criterion (SAC), linear and differential probability, nonlinearity, and keyspace are examined.


### 4.2.1. Avalanche and Strict Avalanche Criterion

To exhibit the avalanche effect, one-half of the output bits should change on average whenever a single input bit is toggled. To determine if an 8-bit s-box fulfils this requirement, the28 possible inputs are first divided into 27 pairs, X,Xi, which differ only in bit i. The 8-bit avalanche vectors, Vi, are then calculated for all (0≤i<8) as follows:(5)Vi=sX⊕sXi.For 10000 random s-boxes all possible input pairs are tested. Results indicate that 50.1899% of each Vi bits are equal to one when an input differs in only bit i.To satisfy the SAC, each individual output bit should change with a probability of 50% when a single input bit is toggled. Similar to the previous test,28 possible inputs are first divided into 27 pairs, X,Xi, which differ only in bit i. The 8-bit avalanche vectors, Vi are then calculated for all (0≤i<8). For 10000 random s-boxes and all possible input pairs, the average probability that a bit location in Vi is equal to one when an input differs in only bit i is 50.1993%.Both results show that the s-boxes generated by the proposed AEAD scheme have strong avalanche effect and fulfil the SAC. Satisfying the SAC also implies that the s-box is a complete function, whereby each output bit is dependent on all input bits [27].


### 4.2.2. Differential Distribution and Linear Approximation

For 10000 randomly generated s-boxes, the differential distribution [28] and linear approximation [29] tables are computed. These tables consist of the probabilities of differential and linear characteristics for various input/output combinations that can be used in differential and linear attacks. The worst case differential and linear probabilities are 2-4.67807 and 2-2.91254, respectively. These probabilities are sufficient to resist cryptanalytic attacks which are described in Section 4.5.


### 4.2.3. Nonlinearity and Key Sensitivity

LetF2n be the n-dimensional vector space over the field F2. The nonlinearity of a function F:F2n→F2n is defined by(6)NLF=2n-1-12maxa∈F2n,b∈F2n⁡∑x∈F2n-1b·Fx+a·x.A perfectly nonlinear function has a nonlinearity of NLF=2n-1-2n/2-1, which is 120 for an 8-bit s-box. Out of 10000 randomly generated s-boxes, the average nonlinearity is 92.6646, which is 77.22% nonlinear. The generated s-boxes have lower nonlinearity than the AES s-box (NL(FAES)=112). However, unlike a static s-box, attackers cannot linearly approximate a randomized s-box without knowledge of the keys used to generate it. Therefore, slight changes to the secret key should generate different s-boxes. For all 128-bit secret keys with hamming weight of one, the proposed AEAD scheme generates unique s-boxes. In addition, for 2000 incrementally generated s-boxes (κ=0 to κ=7d0), all s-boxes are also unique. This shows that the random s-box algorithm is highly sensitive to slight changes to κ.


## 4.2.1. Avalanche and Strict Avalanche Criterion

To exhibit the avalanche effect, one-half of the output bits should change on average whenever a single input bit is toggled. To determine if an 8-bit s-box fulfils this requirement, the28 possible inputs are first divided into 27 pairs, X,Xi, which differ only in bit i. The 8-bit avalanche vectors, Vi, are then calculated for all (0≤i<8) as follows:(5)Vi=sX⊕sXi.For 10000 random s-boxes all possible input pairs are tested. Results indicate that 50.1899% of each Vi bits are equal to one when an input differs in only bit i.To satisfy the SAC, each individual output bit should change with a probability of 50% when a single input bit is toggled. Similar to the previous test,28 possible inputs are first divided into 27 pairs, X,Xi, which differ only in bit i. The 8-bit avalanche vectors, Vi are then calculated for all (0≤i<8). For 10000 random s-boxes and all possible input pairs, the average probability that a bit location in Vi is equal to one when an input differs in only bit i is 50.1993%.Both results show that the s-boxes generated by the proposed AEAD scheme have strong avalanche effect and fulfil the SAC. Satisfying the SAC also implies that the s-box is a complete function, whereby each output bit is dependent on all input bits [27].


## 4.2.2. Differential Distribution and Linear Approximation

For 10000 randomly generated s-boxes, the differential distribution [28] and linear approximation [29] tables are computed. These tables consist of the probabilities of differential and linear characteristics for various input/output combinations that can be used in differential and linear attacks. The worst case differential and linear probabilities are 2-4.67807 and 2-2.91254, respectively. These probabilities are sufficient to resist cryptanalytic attacks which are described in Section 4.5.


## 4.2.3. Nonlinearity and Key Sensitivity

LetF2n be the n-dimensional vector space over the field F2. The nonlinearity of a function F:F2n→F2n is defined by(6)NLF=2n-1-12maxa∈F2n,b∈F2n⁡∑x∈F2n-1b·Fx+a·x.A perfectly nonlinear function has a nonlinearity of NLF=2n-1-2n/2-1, which is 120 for an 8-bit s-box. Out of 10000 randomly generated s-boxes, the average nonlinearity is 92.6646, which is 77.22% nonlinear. The generated s-boxes have lower nonlinearity than the AES s-box (NL(FAES)=112). However, unlike a static s-box, attackers cannot linearly approximate a randomized s-box without knowledge of the keys used to generate it. Therefore, slight changes to the secret key should generate different s-boxes. For all 128-bit secret keys with hamming weight of one, the proposed AEAD scheme generates unique s-boxes. In addition, for 2000 incrementally generated s-boxes (κ=0 to κ=7d0), all s-boxes are also unique. This shows that the random s-box algorithm is highly sensitive to slight changes to κ.


## 4.3. Mask Evaluation

The output of the masking algorithm is first tested using the NIST, DIEHARD, and ENT test suites. The 128-bit mask values generated by the AEAD scheme successfully pass all three as shown in Tables9, 13, and 17 of the Appendix.


### 4.3.1. Mask Cycle Length

The cycle length of the masking algorithm must be sufficiently large to avoid attacks that can take advantage of any mask value cycles. Theoretically, the cycle length is limited by the precision of the fixed point representation used in chaotic iterations. This amounts to230-1, as 30 bits are used to represent the fractional bits. This is a conservative bound, as chaotic perturbation and chaotic coupling further extend the cycle length. Because there are two chaotic maps used to modify the mask registers, the total cycle length is the least common multiple of their cycle lengths. Based on this lower bound, the proposed AEAD scheme will be able to support messages of approximately 260-1 blocks before a mask cycle occurs.


## 4.3.1. Mask Cycle Length

The cycle length of the masking algorithm must be sufficiently large to avoid attacks that can take advantage of any mask value cycles. Theoretically, the cycle length is limited by the precision of the fixed point representation used in chaotic iterations. This amounts to230-1, as 30 bits are used to represent the fractional bits. This is a conservative bound, as chaotic perturbation and chaotic coupling further extend the cycle length. Because there are two chaotic maps used to modify the mask registers, the total cycle length is the least common multiple of their cycle lengths. Based on this lower bound, the proposed AEAD scheme will be able to support messages of approximately 260-1 blocks before a mask cycle occurs.


## 4.4. Key Schedule Evaluation

The key schedule algorithm generates only 20 round keys for a secret key. Therefore, data for the statistical test suites are generated using incremental secret keys (incremented fromκ=0) except for the DIEHARD test which still uses randomly generated secret keys. Results in Tables 10, 14, and 18 of the Appendix indicate that the key schedule algorithm passes all test suites.


### 4.4.1. Avalanche and Strict Avalanche Criterion

The key schedule algorithm is analysed for avalanche effect and SAC similar to the s-box evaluation in Section4.2.1. The avalanche vectors Vi are calculated using (5), where 10000 randomly generated pairs of X, Xi are used as inputs. To depict the avalanche effect, one-half of each round key should change on average whenever a single input key bit is toggled. The percentages of Vi bits that are equal to one when the input key differs in only bit i are 50.0403%, 49.99%, 50.0719%, 49.9422%, 49.9228%, 49.9047%, 50.0417%, 49.92%, 49.9942%, 49.9925%, 49.8973%, 50.0503%, 50.1373%, 50.0075%, 49.9709%, 49.9975%, 50.0342%, 50.0542%, 49.9628%, and 49.9153% for each of the 20 rounds, respectively. This has an overall average of 49.9924% per round.To fulfil the SAC, each round key bit should change with a probability of 50% when a single input key bit is toggled. For each of the 20 rounds, the average probabilities that a bit location inVi is equal to one when the input key differs in only bit i are 49.9998%, 49.9891%, 50.0914%, 49.8953%, 49.9978%, 49.9583%, 49.9866%, 50.0108%, 49.9941%, 49.9044%, 49.9095%, 49.9452%, 50.0287%, 50.0473%, 50.0302%, 50.0439%, 50.0852%, 50.017%, 50.0633%, and 49.9419%. This has an overall average of 49.997% per round.Results show that the key schedule algorithm has strong avalanche effect and fulfils the SAC. This implies that the key schedule algorithm is a complete function, where all round key bits are dependent on all input secret key bits.


## 4.4.1. Avalanche and Strict Avalanche Criterion

The key schedule algorithm is analysed for avalanche effect and SAC similar to the s-box evaluation in Section4.2.1. The avalanche vectors Vi are calculated using (5), where 10000 randomly generated pairs of X, Xi are used as inputs. To depict the avalanche effect, one-half of each round key should change on average whenever a single input key bit is toggled. The percentages of Vi bits that are equal to one when the input key differs in only bit i are 50.0403%, 49.99%, 50.0719%, 49.9422%, 49.9228%, 49.9047%, 50.0417%, 49.92%, 49.9942%, 49.9925%, 49.8973%, 50.0503%, 50.1373%, 50.0075%, 49.9709%, 49.9975%, 50.0342%, 50.0542%, 49.9628%, and 49.9153% for each of the 20 rounds, respectively. This has an overall average of 49.9924% per round.To fulfil the SAC, each round key bit should change with a probability of 50% when a single input key bit is toggled. For each of the 20 rounds, the average probabilities that a bit location inVi is equal to one when the input key differs in only bit i are 49.9998%, 49.9891%, 50.0914%, 49.8953%, 49.9978%, 49.9583%, 49.9866%, 50.0108%, 49.9941%, 49.9044%, 49.9095%, 49.9452%, 50.0287%, 50.0473%, 50.0302%, 50.0439%, 50.0852%, 50.017%, 50.0633%, and 49.9419%. This has an overall average of 49.997% per round.Results show that the key schedule algorithm has strong avalanche effect and fulfils the SAC. This implies that the key schedule algorithm is a complete function, where all round key bits are dependent on all input secret key bits.


## 4.5. Encryption Algorithm Security

This section analyses the security of the AEAD scheme against various cryptanalytic attacks. A lower bound of security against these attacks is first determined withτ=0. Then, additional security provided by using a TRNG to generate τ is discussed. Prior to other security analyses, the ciphertext of the AEAD scheme is tested using statistical suites with results in Tables 11, 15, and 19.


### 4.5.1. Differential and Linear Cryptanalysis

The security bound for differential and linear cryptanalysis can be determined based on the minimum number of active s-boxes for a differential characteristic (ASDr) and linear characteristic (ASLr), where r is the number of rounds. The number of AS is dependent on the type of block shuffle used in the round function. In an early design, the number 10 block shuffle from [30] was used in the proposed AEAD scheme, supposedly with ASD20/ASL20=44. However, a branch and bound algorithm was used and found that ASD20/ASL20=37. Instead, an isomorphic shuffle to the number 10 shuffle was used, adopted from [31] with ASDr and ASLr for 1≤r≤20 shown in Table 2.Table 2
List of active S-boxes.
Round,r A S D r, ASLr 1 0 2 1 3 2 4 3 5 4 6 6 7 8 8 11 9 14 10 18 11 22 12 24 13 27 14 30 15 32 16 35 17 36 18 39 19 41 20 44The maximum differential and linear probabilities for the AEAD scheme’s s-boxes arePD=2-4.67807 and PL=2-2.91254, respectively as mentioned in Section 4.2.2. The probability for differential and linear distinguishers are calculated using(7)Pdiff-distr=PDASDr,Plin-distr=12+2ASLr-1×PLASLr.For r=14 and r=16, Pdiff-dist14=2-140.3421 and Plin-dist16=1/2+2-67.9389, where 2-67.9389 is the linear bias, denoted by εlin. The number of plaintexts required for a differential and linear distinguishing attack is then 1/Pdiff-dist14=2140.3421 and 1/εlin2=2135.8778, respectively, which are both more than the available 2128. Therefore, the full 20 rounds have a safe security margin against differential and linear cryptanalysis.


### 4.5.2. Algebraic Attack

In an algebraic attack, s-boxes are described by an overdefined system of algebraic equations that hold true with a probability of one [32]. The use of random s-boxes increases the resistance of a cipher against this attack [33]. The proposed AEAD scheme uses key-dependent s-boxes which are further randomized by τ; therefore it is difficult to obtain a system of equations for these s-boxes. Without these equations, an algebraic attack is not feasible. The proposed cipher is thus resistant to algebraic attacks.


### 4.5.3. Timing Attack

Timing attacks exploit operations with data-dependent execution time to reveal the secret key [34, 35]. In the proposed AEAD scheme, the secret key is used to generate s-boxes and round keys and also to initialize the mask register. The remaining operations consist of Bitwise operations that have constant execution time. Therefore, the proposed cipher is resistant to timing attacks because its encryption speed is independent of the key value.


### 4.5.4. Security with True Random Secret Message Number

Ifτ is generated by a nondeterministic TRNG, the cipher is able to resist a wide range of statistical-based cryptanalytic attacks. A nondeterministic τ ensures that multiple encryptions of even the same (A,M) pair will involve different s-boxes and masking values. This leads to different (C,T) outputs. However, a legitimate recipient can easily decrypt and verify these ciphertext-MAC pairs as long as the secret key is correct.Randomized s-boxes prevent any cryptanalytic attacks that rely on approximating the behavior of the s-box, such as differential, linear, and algebraic attacks. Even if an approximation of the s-box is obtained for a particular plaintext-ciphertext pair, it is only applicable to that specific pair. The cipher is also immune to attacks that rely on selecting input differences that cancel out the effect of encryption keys such as the differential attack, truncated differential attack, and impossible differential attack. This is because the masking keys are modified by the truly randomτ, making them nondeterministic for each plaintext encryption. For a differential characteristic to hold, τ values for a plaintext pair have to match, which occurs with a probability of 2-128 for a uniform TRNG.Key recovery attacks based on anr-round statistical distinguisher involve the encryption of multiple plaintexts for r+g rounds to obtain their corresponding (r+g)-round ciphertexts. Attackers then guess subkey bits, decrypt the ciphertext for g rounds, and verify their guess based on the r-round statistical distinguisher. If τ is nondeterministic, attackers will not be able to obtain the correct subkey using this method as each plaintext is encrypted based on different s-boxes and masking keys. In practice, the statistical distinguisher only holds if two plaintexts are encrypted with same τ, which again occurs with a probability of 2-128 for a uniform TRNG.As previously mentioned, generatingτ using a TRNG makes the cipher misuse resistant. If the same nonce is used twice, the resulting MAC and ciphertext are still secure as long as τ is not repeated for the same (A,M,η) 3-tuple. In short, implementing the proposed AEAD scheme with a TRNG or even a hybrid RNG will strengthen its immunity against statistical-based cryptanalysis as well as user misuse.


## 4.5.1. Differential and Linear Cryptanalysis

The security bound for differential and linear cryptanalysis can be determined based on the minimum number of active s-boxes for a differential characteristic (ASDr) and linear characteristic (ASLr), where r is the number of rounds. The number of AS is dependent on the type of block shuffle used in the round function. In an early design, the number 10 block shuffle from [30] was used in the proposed AEAD scheme, supposedly with ASD20/ASL20=44. However, a branch and bound algorithm was used and found that ASD20/ASL20=37. Instead, an isomorphic shuffle to the number 10 shuffle was used, adopted from [31] with ASDr and ASLr for 1≤r≤20 shown in Table 2.Table 2
List of active S-boxes.
Round,r A S D r, ASLr 1 0 2 1 3 2 4 3 5 4 6 6 7 8 8 11 9 14 10 18 11 22 12 24 13 27 14 30 15 32 16 35 17 36 18 39 19 41 20 44The maximum differential and linear probabilities for the AEAD scheme’s s-boxes arePD=2-4.67807 and PL=2-2.91254, respectively as mentioned in Section 4.2.2. The probability for differential and linear distinguishers are calculated using(7)Pdiff-distr=PDASDr,Plin-distr=12+2ASLr-1×PLASLr.For r=14 and r=16, Pdiff-dist14=2-140.3421 and Plin-dist16=1/2+2-67.9389, where 2-67.9389 is the linear bias, denoted by εlin. The number of plaintexts required for a differential and linear distinguishing attack is then 1/Pdiff-dist14=2140.3421 and 1/εlin2=2135.8778, respectively, which are both more than the available 2128. Therefore, the full 20 rounds have a safe security margin against differential and linear cryptanalysis.


## 4.5.2. Algebraic Attack

In an algebraic attack, s-boxes are described by an overdefined system of algebraic equations that hold true with a probability of one [32]. The use of random s-boxes increases the resistance of a cipher against this attack [33]. The proposed AEAD scheme uses key-dependent s-boxes which are further randomized by τ; therefore it is difficult to obtain a system of equations for these s-boxes. Without these equations, an algebraic attack is not feasible. The proposed cipher is thus resistant to algebraic attacks.


## 4.5.3. Timing Attack

Timing attacks exploit operations with data-dependent execution time to reveal the secret key [34, 35]. In the proposed AEAD scheme, the secret key is used to generate s-boxes and round keys and also to initialize the mask register. The remaining operations consist of Bitwise operations that have constant execution time. Therefore, the proposed cipher is resistant to timing attacks because its encryption speed is independent of the key value.


## 4.5.4. Security with True Random Secret Message Number

Ifτ is generated by a nondeterministic TRNG, the cipher is able to resist a wide range of statistical-based cryptanalytic attacks. A nondeterministic τ ensures that multiple encryptions of even the same (A,M) pair will involve different s-boxes and masking values. This leads to different (C,T) outputs. However, a legitimate recipient can easily decrypt and verify these ciphertext-MAC pairs as long as the secret key is correct.Randomized s-boxes prevent any cryptanalytic attacks that rely on approximating the behavior of the s-box, such as differential, linear, and algebraic attacks. Even if an approximation of the s-box is obtained for a particular plaintext-ciphertext pair, it is only applicable to that specific pair. The cipher is also immune to attacks that rely on selecting input differences that cancel out the effect of encryption keys such as the differential attack, truncated differential attack, and impossible differential attack. This is because the masking keys are modified by the truly randomτ, making them nondeterministic for each plaintext encryption. For a differential characteristic to hold, τ values for a plaintext pair have to match, which occurs with a probability of 2-128 for a uniform TRNG.Key recovery attacks based on anr-round statistical distinguisher involve the encryption of multiple plaintexts for r+g rounds to obtain their corresponding (r+g)-round ciphertexts. Attackers then guess subkey bits, decrypt the ciphertext for g rounds, and verify their guess based on the r-round statistical distinguisher. If τ is nondeterministic, attackers will not be able to obtain the correct subkey using this method as each plaintext is encrypted based on different s-boxes and masking keys. In practice, the statistical distinguisher only holds if two plaintexts are encrypted with same τ, which again occurs with a probability of 2-128 for a uniform TRNG.As previously mentioned, generatingτ using a TRNG makes the cipher misuse resistant. If the same nonce is used twice, the resulting MAC and ciphertext are still secure as long as τ is not repeated for the same (A,M,η) 3-tuple. In short, implementing the proposed AEAD scheme with a TRNG or even a hybrid RNG will strengthen its immunity against statistical-based cryptanalysis as well as user misuse.


## 4.6. MAC Security

This section analyses the statistical quality of the authentication tag produced by the proposed AEAD scheme. In the following experiments, the input parameters are set toκ=0,  η=0,  τ=0, whereby only A and M vary.


### 4.6.1. Statistical Analysis of Diffusion and Confusion

In this test, an (A,M) pair is randomly generated and its corresponding tag, T, is computed. Next, a random bit within the (A,M) pair is toggled and its corresponding tag, T′, is computed. T and T′ values are compared and the number of changes at each bit location is stored as Xi. The following equations are then computed:Mean Changed Bit Number (8) X ¯ = 1 N ∑ i = 1 N X i .Mean Changed Probability (9) P = X ¯ 128 × 100 % .Standard Variance of the Changed Bit Number (10) Δ X = 1 N - 1 ∑ i = 1 N X i - X ¯ 2 .Standard Variance (11) Δ P = 1 N - 1 ∑ i = 1 N X i 128 - P 2 × 100 % ,where N is the number of trials. The test is performed for N=1024/2048/10000 and the results are tabulated in Table 3. The distribution plot and histogram of Xi for N=10000 are shown in Figures 7 and 6. Results show that the MAC values have a mean changed bit number, X¯, and mean changed probability, P, that are near-ideal (64 bits and 50%). Low standard variance values depict strong diffusion and confusion capabilities. In Figures 7 and 6, Xi is shown to be evenly and normally distributed centering on 64 bits. These near-ideal statistical results indicate that the slightest change to the A or M will produce a different authentication tag.Table 3
Statistical results for 128-bit hash values of the proposed hash function.
Param/N 1024 2048 10000 Mean X- 64.0010 64.0078 63.9968 64.0019 P(%) 50.0008 50.0061 49.9975 50.0015 ΔX 5.6291 5.6755 5.6291 5.6446 ΔP(%) 4.3977 4.4340 4.3978 4.4098 Xmin 47 45 45 45.67 Xmax 83 83 86 84Figure 7
Distribution plot ofXi.Figure 6
Distribution histogram ofXi.


### 4.6.2. Analysis of Collision Resistance

Similar to Section4.6.1, MACs for an (A,M) pair and a slightly modified A,M′ pair are produced and stored in ASCII format. The two MACs are compared and the number of hits (equal ASCII characters in the same position) are counted. Next, the absolute difference, D, between the two MACs is calculated as follows:(12)D=∑i=1Ndei-dei′,where ei and ei′ are the ith entry of the original and modified MAC, while the function d(∗) converts the entry to its equivalent decimal value. The test results for 10000 trials are compared against theoretical values (see [36] for calculation of theoretical values) in Tables 4 and 5. Results indicate that the proposed AEAD scheme has strong collision resistance as the experimental results are near-ideal.Table 4
Number of hits.
Hits 0 1 2 3 4 5 6 Theoretical 9416 572 12 0 0 0 0 Experimental 9428 558 13 1 0 0 0Table 5
Absolute difference.
Results Minimum Maximum Mean Theoretical — — 1360 Experimental 574 2352 1362.55Table 6
Passing Ratios for NIST and DIEHARD.
Test name Samples Min. PR Max. PR NIST (except random excursions) 1000 0.981 0.999 NIST, random excursions 625 0.978 1.000 DIEHARD, birthday spacings 500 0.977 1.000 DIEHARD, overlapping 5-permutation 100 0.961 1.000 DIEHARD, binary rank 31 × 31 matrices 50 0.949 1.000 DIEHARD, binary rank 32 × 32 matrices 50 0.949 1.000 DIEHARD, binary rank 6 × 8 matrices 1300 0.982 0.998 DIEHARD, bitstream 1000 0.981 0.999 DIEHARD, overlapping-pairs-sparse-occupancy 1150 0.981 0.999 DIEHARD, overlapping-quadruples-sparse-occupancy 1400 0.9822 0.998 DIEHARD, DNA spacings 1550 0.983 0.997 DIEHARD, Count-the-1s on a Stream of Bytes 100 0.961 1.000 DIEHARD, count-the-1s on specific bytes 1250 0.982 0.998 DIEHARD, parking lot 550 0.978 1.000 DIEHARD, minimum distance 50 0.949 1.000 DIEHARD, 3D-spheres 1050 0.984 0.999 DIEHARD, squeeze 50 0.949 1.000 DIEHARD, overlapping sums 550 0.978 1.000 DIEHARD, runs 200 0.969 1.000 DIEHARD, craps 100 0.961 1.000Table 7
Ideal values for ENT test suite.
Test name Ideal value Entropy 8.0 Chi-square 50% Arithmetic mean 127.5 Monte Carlo value forπ 3.141592653 Serial correlation coefficient 9Table 8
NIST: S-box chaotic sequence.
Test name P value Passing ratio Result Frequency 0.771469 0.993 Pass Block frequency 0.759756 0.989 Pass Cumulative sums 0.122325 0.990 Pass Runs 0.179584 0.990 Pass Longest run 0.446556 0.989 Pass Rank 0.568739 0.993 Pass FFT 0.689019 0.991 Pass Nonoverlapping templates 0.224821 0.981 Pass Overlapping templates 0.146152 0.984 Pass Universal 0.011383 0.982 Pass Approximate entropy 0.042808 0.987 Pass Random excursions 0.173679 0.987 Pass Random excursions variant 0.711017 0.981 Pass Serial 0.803720 0.981 Pass Linear complexity 0.660012 0.990 PassTable 9
NIST: Masking algorithm.
Test Name P value Passing ratio Result Frequency 0.390721 0.991 Pass Block frequency 0.530120 0.987 Pass Cumulative sums 0.259616 0.989 Pass Runs 0.406499 0.992 Pass Longest run 0.307077 0.989 Pass Rank 0.066882 0.991 Pass FFT 0.556460 0.981 Pass Nonoverlapping templates 0.238035 0.982 Pass Overlapping templates 0.676615 0.984 Pass Universal 0.834308 0.992 Pass Approximate entropy 0.915317 0.991 Pass Random excursions 0.582671 0.979 Pass Random excursions variant 0.422281 0.993 Pass Serial 0.875539 0.984 Pass Linear complexity 0.890582 0.989 PassTable 10
NIST: Key schedule.
Test Name P value Passing ratio Result Frequency 0.085587 0.991 Pass Block frequency 0.008629 0.989 Pass Cumulative sums 0.719747 0.990 Pass Runs 0.143686 0.990 Pass Longest run 0.467322 0.989 Pass Rank 0.363593 0.993 Pass FFT 0.015816 0.987 Pass Nonoverlapping templates 0.540204 0.981 Pass Overlapping templates 0.065230 0.988 Pass Universal 0.401199 0.991 Pass Approximate entropy 0.077131 0.996 Pass Random excursions 0.098397 0.982 Pass Random excursions variant 0.884892 0.984 Pass Serial 0.446556 0.989 Pass Linear complexity 0.249284 0.990 PassTable 11
NIST: ciphertext.
Test name P value Passing ratio Result Frequency 0.206629 0.989 Pass Block frequency 0.207730 0.997 Pass Cumulative sums 0.206629 0.990 Pass Runs 0.373625 0.995 Pass Longest run 0.016149 0.987 Pass Rank 0.388990 0.989 Pass FFT 0.954930 0.987 Pass Nonoverlapping templates 0.454053 0.982 Pass Overlapping templates 0.467322 0.985 Pass Universal 0.129620 0.985 Pass Approximate entropy 0.358641 0.990 Pass Random excursions 0.866173 0.986 Pass Random excursions variant 0.956262 0.991 Pass Serial 0.887645 0.992 Pass Linear complexity 0.271619 0.986 PassTable 12
DIEHARD: S-box chaotic sequence.
Test name Passing ratio Result Birthday spacings 0.978 Pass Overlapping 5-permutation 0.970 Pass Binary Rank 31 × 31 matrices 0.980 Pass Binary Rank 32 × 32 matrices 1.00 Pass Binary Rank 6 × 8 matrices 0.985 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.982 Pass Overlapping-quadruples-sparse-occupancy 0.983 Pass DNA spacings 0.985 Pass Count-the-1s on a stream of bytes 0.980 Pass Count-the-1s on specific bytes 0.983 Pass Parking lot 0.978 Pass Minimum distance 0.960 Pass 3D-spheres 0.990 Pass Squeeze 0.960 Pass Overlapping sums 0.985 Pass Runs 0.980 Pass Craps 0.990 PassTable 13
DIEHARD: masking algorithm.
Test Name Passing Ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 1.000 Pass Binary rank 32 × 32 matrices 0.960 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.983 Pass Overlapping-quadruples-sparse-occupancy 0.984 Pass DNA spacings 0.984 Pass Count-the-1s on a stream of bytes 0.990 Pass Count-the-1s on specific bytes 0.984 Pass Parking lot 0.980 Pass Minimum distance 0.960 Pass 3D-spheres 0.985 Pass Squeeze 0.980 Pass Overlapping sums 0.980 Pass Runs 0.990 Pass Craps 0.990 PassTable 14
DIEHARD: key schedule.
Test name Passing ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 0.980 Pass Binary rank 32 × 32 matrices 1.000 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.983 Pass Overlapping-quadruples-sparse-occupancy 0.982 Pass DNA spacings 0.983 Pass Count-the-1s on a stream of bytes 0.970 Pass Count-the-1s on specific bytes 0.982 Pass Parking lot 0.980 Pass Minimum distance 0.980 Pass 3D-spheres 0.984 Pass Squeeze 1.000 Pass Overlapping sums 0.987 Pass Runs 0.975 Pass Craps 0.970 PassTable 15
DIEHARD: ciphertext.
Test name Passing ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 0.980 Pass Binary rank 32 × 32 matrices 0.980 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.987 Pass Overlapping-pairs-sparse-Occupancy 0.982 Pass Overlapping-quadruples-sparse-occupancy 0.984 Pass DNA Spacings 0.985 Pass Count-the-1s on a stream of bytes 0.970 Pass Count-the-1s on specific bytes 0.983 Pass Parking lot 0.978 Pass Minimum distance 0.980 Pass 3D-spheres 0.983 Pass Squeeze 0.960 Pass Overlapping sums 0.980 Pass Runs 0.970 Pass Craps 1.000 PassTable 16
ENT: S-box chaotic sequence.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.13% Pass Arithmetic mean 127.5205 Pass Monte Carlo value forπ 3.140525649 Pass Serial correlation coefficient −0.000300 PassTable 17
ENT: masking algorithm.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.08% Pass Arithmetic mean 127.4735 Pass Monte Carlo value forπ 3.141910973 Pass Serial correlation coefficient −0.000407 PassTable 18
ENT: vey schedule.
Test Name Test value Result Entropy 7.999984 Pass Chi-square 62.61 Pass Arithmetic mean 127.4953 Pass Monte Carlo value forπ 3.140523556 Pass Serial correlation coefficient −0.000304 PassTable 19
ENT: Ciphertext.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.43% Pass Arithmetic mean 127.5039 Pass Monte Carlo value forπ 3.141705895 Pass Serial correlation coefficient 0.000032 Pass


### 4.6.3. MAC Distribution

To resist statistical attacks, a MAC has to be evenly distributed at each bit position. Analysis of the MAC distribution starts with generating a random (A,M) pair and its modified version with one toggled bit, A,M′. The MAC of both messages is compared, and the number of changes at each bit location is counted. For N=10000, the minimum, maximum, and mean changed bit number are 4877, 5150, and 5002.3, respectively, with the distribution plot shown in Figure 8. The mean changed bit number is close to the theoretical value of 5000, where the maximum distance from ideal for each changed bit value is 150. This indicates that proposed AEAD scheme produces evenly distributed MAC values as depicted in Figure 8.Figure 8
Distribution of MAC.


## 4.6.1. Statistical Analysis of Diffusion and Confusion

In this test, an (A,M) pair is randomly generated and its corresponding tag, T, is computed. Next, a random bit within the (A,M) pair is toggled and its corresponding tag, T′, is computed. T and T′ values are compared and the number of changes at each bit location is stored as Xi. The following equations are then computed:Mean Changed Bit Number (8) X ¯ = 1 N ∑ i = 1 N X i .Mean Changed Probability (9) P = X ¯ 128 × 100 % .Standard Variance of the Changed Bit Number (10) Δ X = 1 N - 1 ∑ i = 1 N X i - X ¯ 2 .Standard Variance (11) Δ P = 1 N - 1 ∑ i = 1 N X i 128 - P 2 × 100 % ,where N is the number of trials. The test is performed for N=1024/2048/10000 and the results are tabulated in Table 3. The distribution plot and histogram of Xi for N=10000 are shown in Figures 7 and 6. Results show that the MAC values have a mean changed bit number, X¯, and mean changed probability, P, that are near-ideal (64 bits and 50%). Low standard variance values depict strong diffusion and confusion capabilities. In Figures 7 and 6, Xi is shown to be evenly and normally distributed centering on 64 bits. These near-ideal statistical results indicate that the slightest change to the A or M will produce a different authentication tag.Table 3
Statistical results for 128-bit hash values of the proposed hash function.
Param/N 1024 2048 10000 Mean X- 64.0010 64.0078 63.9968 64.0019 P(%) 50.0008 50.0061 49.9975 50.0015 ΔX 5.6291 5.6755 5.6291 5.6446 ΔP(%) 4.3977 4.4340 4.3978 4.4098 Xmin 47 45 45 45.67 Xmax 83 83 86 84Figure 7
Distribution plot ofXi.Figure 6
Distribution histogram ofXi.


## 4.6.2. Analysis of Collision Resistance

Similar to Section4.6.1, MACs for an (A,M) pair and a slightly modified A,M′ pair are produced and stored in ASCII format. The two MACs are compared and the number of hits (equal ASCII characters in the same position) are counted. Next, the absolute difference, D, between the two MACs is calculated as follows:(12)D=∑i=1Ndei-dei′,where ei and ei′ are the ith entry of the original and modified MAC, while the function d(∗) converts the entry to its equivalent decimal value. The test results for 10000 trials are compared against theoretical values (see [36] for calculation of theoretical values) in Tables 4 and 5. Results indicate that the proposed AEAD scheme has strong collision resistance as the experimental results are near-ideal.Table 4
Number of hits.
Hits 0 1 2 3 4 5 6 Theoretical 9416 572 12 0 0 0 0 Experimental 9428 558 13 1 0 0 0Table 5
Absolute difference.
Results Minimum Maximum Mean Theoretical — — 1360 Experimental 574 2352 1362.55Table 6
Passing Ratios for NIST and DIEHARD.
Test name Samples Min. PR Max. PR NIST (except random excursions) 1000 0.981 0.999 NIST, random excursions 625 0.978 1.000 DIEHARD, birthday spacings 500 0.977 1.000 DIEHARD, overlapping 5-permutation 100 0.961 1.000 DIEHARD, binary rank 31 × 31 matrices 50 0.949 1.000 DIEHARD, binary rank 32 × 32 matrices 50 0.949 1.000 DIEHARD, binary rank 6 × 8 matrices 1300 0.982 0.998 DIEHARD, bitstream 1000 0.981 0.999 DIEHARD, overlapping-pairs-sparse-occupancy 1150 0.981 0.999 DIEHARD, overlapping-quadruples-sparse-occupancy 1400 0.9822 0.998 DIEHARD, DNA spacings 1550 0.983 0.997 DIEHARD, Count-the-1s on a Stream of Bytes 100 0.961 1.000 DIEHARD, count-the-1s on specific bytes 1250 0.982 0.998 DIEHARD, parking lot 550 0.978 1.000 DIEHARD, minimum distance 50 0.949 1.000 DIEHARD, 3D-spheres 1050 0.984 0.999 DIEHARD, squeeze 50 0.949 1.000 DIEHARD, overlapping sums 550 0.978 1.000 DIEHARD, runs 200 0.969 1.000 DIEHARD, craps 100 0.961 1.000Table 7
Ideal values for ENT test suite.
Test name Ideal value Entropy 8.0 Chi-square 50% Arithmetic mean 127.5 Monte Carlo value forπ 3.141592653 Serial correlation coefficient 9Table 8
NIST: S-box chaotic sequence.
Test name P value Passing ratio Result Frequency 0.771469 0.993 Pass Block frequency 0.759756 0.989 Pass Cumulative sums 0.122325 0.990 Pass Runs 0.179584 0.990 Pass Longest run 0.446556 0.989 Pass Rank 0.568739 0.993 Pass FFT 0.689019 0.991 Pass Nonoverlapping templates 0.224821 0.981 Pass Overlapping templates 0.146152 0.984 Pass Universal 0.011383 0.982 Pass Approximate entropy 0.042808 0.987 Pass Random excursions 0.173679 0.987 Pass Random excursions variant 0.711017 0.981 Pass Serial 0.803720 0.981 Pass Linear complexity 0.660012 0.990 PassTable 9
NIST: Masking algorithm.
Test Name P value Passing ratio Result Frequency 0.390721 0.991 Pass Block frequency 0.530120 0.987 Pass Cumulative sums 0.259616 0.989 Pass Runs 0.406499 0.992 Pass Longest run 0.307077 0.989 Pass Rank 0.066882 0.991 Pass FFT 0.556460 0.981 Pass Nonoverlapping templates 0.238035 0.982 Pass Overlapping templates 0.676615 0.984 Pass Universal 0.834308 0.992 Pass Approximate entropy 0.915317 0.991 Pass Random excursions 0.582671 0.979 Pass Random excursions variant 0.422281 0.993 Pass Serial 0.875539 0.984 Pass Linear complexity 0.890582 0.989 PassTable 10
NIST: Key schedule.
Test Name P value Passing ratio Result Frequency 0.085587 0.991 Pass Block frequency 0.008629 0.989 Pass Cumulative sums 0.719747 0.990 Pass Runs 0.143686 0.990 Pass Longest run 0.467322 0.989 Pass Rank 0.363593 0.993 Pass FFT 0.015816 0.987 Pass Nonoverlapping templates 0.540204 0.981 Pass Overlapping templates 0.065230 0.988 Pass Universal 0.401199 0.991 Pass Approximate entropy 0.077131 0.996 Pass Random excursions 0.098397 0.982 Pass Random excursions variant 0.884892 0.984 Pass Serial 0.446556 0.989 Pass Linear complexity 0.249284 0.990 PassTable 11
NIST: ciphertext.
Test name P value Passing ratio Result Frequency 0.206629 0.989 Pass Block frequency 0.207730 0.997 Pass Cumulative sums 0.206629 0.990 Pass Runs 0.373625 0.995 Pass Longest run 0.016149 0.987 Pass Rank 0.388990 0.989 Pass FFT 0.954930 0.987 Pass Nonoverlapping templates 0.454053 0.982 Pass Overlapping templates 0.467322 0.985 Pass Universal 0.129620 0.985 Pass Approximate entropy 0.358641 0.990 Pass Random excursions 0.866173 0.986 Pass Random excursions variant 0.956262 0.991 Pass Serial 0.887645 0.992 Pass Linear complexity 0.271619 0.986 PassTable 12
DIEHARD: S-box chaotic sequence.
Test name Passing ratio Result Birthday spacings 0.978 Pass Overlapping 5-permutation 0.970 Pass Binary Rank 31 × 31 matrices 0.980 Pass Binary Rank 32 × 32 matrices 1.00 Pass Binary Rank 6 × 8 matrices 0.985 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.982 Pass Overlapping-quadruples-sparse-occupancy 0.983 Pass DNA spacings 0.985 Pass Count-the-1s on a stream of bytes 0.980 Pass Count-the-1s on specific bytes 0.983 Pass Parking lot 0.978 Pass Minimum distance 0.960 Pass 3D-spheres 0.990 Pass Squeeze 0.960 Pass Overlapping sums 0.985 Pass Runs 0.980 Pass Craps 0.990 PassTable 13
DIEHARD: masking algorithm.
Test Name Passing Ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 1.000 Pass Binary rank 32 × 32 matrices 0.960 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.983 Pass Overlapping-quadruples-sparse-occupancy 0.984 Pass DNA spacings 0.984 Pass Count-the-1s on a stream of bytes 0.990 Pass Count-the-1s on specific bytes 0.984 Pass Parking lot 0.980 Pass Minimum distance 0.960 Pass 3D-spheres 0.985 Pass Squeeze 0.980 Pass Overlapping sums 0.980 Pass Runs 0.990 Pass Craps 0.990 PassTable 14
DIEHARD: key schedule.
Test name Passing ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 0.980 Pass Binary rank 32 × 32 matrices 1.000 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.982 Pass Overlapping-pairs-sparse-occupancy 0.983 Pass Overlapping-quadruples-sparse-occupancy 0.982 Pass DNA spacings 0.983 Pass Count-the-1s on a stream of bytes 0.970 Pass Count-the-1s on specific bytes 0.982 Pass Parking lot 0.980 Pass Minimum distance 0.980 Pass 3D-spheres 0.984 Pass Squeeze 1.000 Pass Overlapping sums 0.987 Pass Runs 0.975 Pass Craps 0.970 PassTable 15
DIEHARD: ciphertext.
Test name Passing ratio Result Birthday spacings 0.982 Pass Overlapping 5-permutation 0.970 Pass Binary rank 31 × 31 matrices 0.980 Pass Binary rank 32 × 32 matrices 0.980 Pass Binary rank 6 × 8 matrices 0.982 Pass Bitstream 0.987 Pass Overlapping-pairs-sparse-Occupancy 0.982 Pass Overlapping-quadruples-sparse-occupancy 0.984 Pass DNA Spacings 0.985 Pass Count-the-1s on a stream of bytes 0.970 Pass Count-the-1s on specific bytes 0.983 Pass Parking lot 0.978 Pass Minimum distance 0.980 Pass 3D-spheres 0.983 Pass Squeeze 0.960 Pass Overlapping sums 0.980 Pass Runs 0.970 Pass Craps 1.000 PassTable 16
ENT: S-box chaotic sequence.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.13% Pass Arithmetic mean 127.5205 Pass Monte Carlo value forπ 3.140525649 Pass Serial correlation coefficient −0.000300 PassTable 17
ENT: masking algorithm.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.08% Pass Arithmetic mean 127.4735 Pass Monte Carlo value forπ 3.141910973 Pass Serial correlation coefficient −0.000407 PassTable 18
ENT: vey schedule.
Test Name Test value Result Entropy 7.999984 Pass Chi-square 62.61 Pass Arithmetic mean 127.4953 Pass Monte Carlo value forπ 3.140523556 Pass Serial correlation coefficient −0.000304 PassTable 19
ENT: Ciphertext.
Test name Test value Result Entropy 7.999984 Pass Chi-square 55.43% Pass Arithmetic mean 127.5039 Pass Monte Carlo value forπ 3.141705895 Pass Serial correlation coefficient 0.000032 Pass


## 4.6.3. MAC Distribution

To resist statistical attacks, a MAC has to be evenly distributed at each bit position. Analysis of the MAC distribution starts with generating a random (A,M) pair and its modified version with one toggled bit, A,M′. The MAC of both messages is compared, and the number of changes at each bit location is counted. For N=10000, the minimum, maximum, and mean changed bit number are 4877, 5150, and 5002.3, respectively, with the distribution plot shown in Figure 8. The mean changed bit number is close to the theoretical value of 5000, where the maximum distance from ideal for each changed bit value is 150. This indicates that proposed AEAD scheme produces evenly distributed MAC values as depicted in Figure 8.Figure 8
Distribution of MAC.


## 4.7. Advantage over AES-GCM

The proposed scheme has several advantages over AES-GCM which is currently the official standard for authenticated encryption [37]. Firstly, the proposed AEAD scheme does not have any identified weak keys unlike AES-GCM [6]. It is also resistant to nonce-misuse, providing full privacy and integrity even if nonce is repeated, unlike AES-GCM which requires unique nonce values for security [37]. Most software-based AES implementations are susceptible to cache timing attacks [35], whereas the proposed cipher has a constant time implementation due to simple binary operations. AES-GCM’s security bound for integrity is equal to half the tag length [6] whereas the proposed AEAD scheme is able to provide full 128-bit security for integrity. Furthermore, the proposed AEAD scheme also has the flexibility to be implemented with a TRNG for immunity to statistical-based attacks.In terms of performance, the speed of AES-GCM was compared against the proposed cipher on a computer with an Intel i7-4700MQ processor and 8 GB of RAM. The implementation of AES-GCM was taken from the Crypto++ Library 5.6.2 [38]. The proposed AEAD scheme has a speed of 2401.73 Megabits/second compared to 1601.4 Megabits/second of AES-GCM, approximately 1.5 times faster. The algorithm can still be further optimized for improved performance.


## 5. Conclusion

This paper introduced a new chaos-based authenticated encryption with associated data (AEAD) scheme. It is based on the single-key Even-Mansour construction and Type-II generalized Feistel with random s-boxes. The chaotic tent map was used to generate Even-Mansour whitening keys, round keys, and s-boxes used in the Feistel round functions. Chaotic perturbations were included in the proposed design to overcome weaknesses of unimodal chaotic maps. For improved performance, the fixed point representation was used for all real number operations. Results of rigorous statistical testing have shown that the proposed AEAD scheme has no observable statistical defects. In addition, it is resistant to cryptanalytic attacks such as the differential, linear, algebraic, and timing attacks. To increase its immunity against all statistical-based attacks, the AEAD can be implemented alongside a true random number generator to map messages to various ciphertexts in an unpredictable manner. It also has better performance than AES-GCM which is the current standard in authenticated encryption, with a throughput of approximately 2401.73 Megabits/second. In short, the proposed chaos-based AEAD scheme is a viable alternative to AES-GCM in terms of providing both privacy and integrity in a unified scheme.



---

*Source: 9040518-2017-01-12.xml*