# CFA: A New Family of Hybrid CA-Based PRNGs

Authors: Fatima Ezzahra Ziani; Anas Sadak; Charifa Hanin; Bouchra Echandouri; Fouzia Omary
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In this article, a new Pseudorandom Number Generator (PRNG) construction is proposed. It is based on cellular automata (CAs) and comprises other cryptographic primitives organized as blocks. Each of these blocks has a purpose and serves toward obtaining a higher level of randomness. The construction described is modular, and each of its blocks can be replaced, modified, or adapted according to the user, the application, or the level of randomness required. The authors first describe a general structure and the design principles behind each of the components. Next, a concrete example using the SHA-3 hash function, a hybrid cellular automaton, and the AES block cipher is provided. Then, the security analysis and the statistical properties for this specific instance of the scheme are presented.


---

## Body

## 1. Introduction

Designing cryptographic primitives that achieve security strength and satisfy all of the cryptographic properties is a hard task. First, the development of cryptanalysis techniques makes it difficult for designers to build new primitives with a high security level. In addition, some cryptographic properties are conflicting like, for example, nonlinearity and correlation [1]. Therefore, a compromise between cryptographic properties should be found according to the security level the designer wants to achieve.Many cryptographic applications make use of random numbers. Examples are session keys, seeds, salts, initial vectors, nonce, etc. However, for costs reasons, not all these applications use truly random bits generated from physical sources. Generally, a pseudorandom number generator is used. This cryptographic mechanism tries to generate sequences that are hard to distinguish from truly random sequences.The motivation of this work is to design a versatile, portable, and secure PRNG family based on cellular automata. Consequently, it could be adapted easily according to the different applications requiring random sequences. The design presented here is modular in the sense that all the building blocks can be modified by the system’s designer to meet specific requirements. Those building blocks are a hash function, a cellular automaton, and a block cipher. The mechanism of seeding and reseeding is also part of the design and ensures that the PRNG starting state is unpredictable. All those components were included to achieve a high degree of randomness, a high security level, and good cryptographic properties. Statistical tests, properties evaluation, and a selection procedure for the ruleset of the cellular automaton have been conducted to show that the generator proposed is a good candidate for generating high quality random sequences. The family of generators presented in this work can be used as standalone schemes to generate random sequences or as part of a bigger system, for example, within a stream cipher.The previous CA-based PRNGs, found in [2–8], based the security of their systems on only cellular automata. Consequently, their designs cannot prevent some attacks like chosen-input attacks, direct cryptanalytic attacks, and side-channel attacks. They focused more on the randomness property, which made the systems lack the security level required by a secure PRNG. Instead, CFA, the PRNGs family proposed and studied in this article, was designed by considering the randomness properties and known attacks to provide a high-security level. The main contributions of this work were to define a general design satisfying the requirements of a Cryptographically Secure PRNG, then the choice of the building blocks of this design. The construction of the cellular automaton ruleset provides good cryptographic properties (see Appendix A), which enhances the security of the PRNG in addition to the randomness properties. Secondly, the choice of the hash function and the block cipher are adequate for the proposed implementation. In addition, the seed file, the reseed, and the reseed trigger mechanisms make attacks trying to find out the initial configuration of the PRNG challenging.The rest of this article is organized as follows. In Section2, some basic notions about randomness, entropy, and cellular automata are defined. In Section 3, a brief description of related works is given. Next, in Section 4, the general scheme of the generator and a specific implementation are described. The experimental results and an analysis of that specific implementation follow in Section 5. Finally, Section 6 presents challenges, possible solutions, and future directions, followed by conclusions.


## 2. Preliminaries

### 2.1. Randomness

Random numbers are an essential component of cryptographic applications such as encryption, key generation, or content masking. The notions of random, randomness, and random numbers are often associated with unpredictability and uniform distribution.A Random Number Generator (RNG) is an algorithm that produces sequences of numbers or bits that seem to be random, from a seed or from a continuously fed input. True Radom Number Generators (TRNGs) are a class of RNGs that use physical sources to generate “true” random sequences. However, working with truly random sequences has drawbacks like the reliability of the physical sources, the availability of the data, the limited amount of data, or the high cost of getting the data. Pseudorandom Number Generators (PRNGs) are another class of RNGs that use algorithms to generate random sequences as indistinguishable as possible from “truly” random sequences [9].In general, an RNG must meet specific conditions. Its output should be independent, uniformly distributed, and unpredictable [9]. The generator should be efficient in terms of the amount of random numbers generated. In order to be used in a cryptographic environment, an RNG should additionally be resistant to well-known attacks [9]. This means that, despite having information about the input or the current/previous output of the generator, an attacker cannot guess its output (previous, current, or future).


### 2.2. Entropy

Entropy is another term associated with RNGs. The concept was first introduced in 1948 by Claude Shannon in the field of Information Theory. Entropy is the measure of randomness as it represents the uncertainty of the output generated by a data source.Entropy is denoted byH(X) and defined as [10](1)HX=−∑xPX=x⋅log2PX=x,where PX=x is the probability of X taking the value x in the sample space ΩX.As shown in [10], the maximum entropy distribution over the range is the uniform distribution. The entropy in this range is no greater than log2ΩX.In cryptographic applications, entropy is one of the measures of the quality of an RNG. Therefore, it is expected to be the highest possible as it translates into more efforts needed by an attacker to guess the output.


### 2.3. Cellular Automata (CA)

Stanislaw Ulam took an interest in self-replicating automata concepts in the 1940s and initiated the studies on cellular automata. Later on, upon suggestions by Stanislaw Ulam, John von Neumann further developed the theory on cellular automata in the 1960s to model self-reproduction in the field of Biology. CAs gain popularity in the 1970s with Martin Gardner and John Conway’s Game of Life [11].A cellular automaton represents a network of cells or finite state automaton. The state of each cell at timet changes according to a local rule and depends on the state of the surrounding cells or neighborhood at time t−1.The interest in cellular automata comes from the fact that simple local calculations, at the level of cells, result in a complex global behavior, at the level of the automaton. Even though uniform CAs (uniformity in update, in dependency to neighbors, in local rules, etc.) are suitable for modeling physical systems, nonuniform CAs are more suited and more efficient to model real life systems.A CA is formally defined as the tuple (d, L, S, N, f) [11], where(i)
d is the dimension of the cellular space(ii)
L is the d-dimensional cellular space, in which elements are called cells(iii)
S is a finite state, in which elements are called states(iv)
N=v1⟶,v2⟶,…,vN⟶ is the neighborhood vector(v)
f is the local rule of the automaton that dictates the change of state of each cell from time t to time t+1Ifc is considered to be the current configuration of the automaton, then Φ(c), Φ2(c), … represent its next configurations. Φ is called the global function.Changingd, L, S, N, and f leads to different types of CAs.A CA for which all the cells are updated by the same rulef is called uniform. Otherwise, the CA is called hybrid or nonuniform. A CA for which the boundary cells are assigned the state 0 is called a null boundary CA. A periodic boundary CA has the extreme cells adjacent to each other.Elementary Cellular Automata or ECAs were introduced in the 1980s by Wolfram. These CAs are one-dimensional, have two possible states (0 or 1), and are characterized by a three-neighborhood dependency. Extensive research related to CAs has been conducted in the field of Cryptography, especially in producing random numbers using CAs. Wolfram introduced this association between Pseudorandom Number Generators and CAs in 1985 [2].In the case of ECAs, the neighborhood of theith cell is given by Ni=si−1,si,si+1 and the local rule f for that cell is defined as sit+1=fisi−1t,sit,si+1t, sit being the current state and sit+1 the next state of the cell. Since ECAs assume two possible states and have a three-neighborhood dependency, 223=256 rules are possible. Each of these rules can be represented as a Boolean function or as a truth table, the decimal value of the truth table being the rule number. If the Boolean expression of the rule contains only the XOR (⊕) operator, then the rule is linear. Otherwise, if the Boolean expression contains also AND(⋅)/OR(+) operators, then the rule is nonlinear. Table 1 shows an example of a linear and a nonlinear rule.Table 1
An example of a linear and nonlinear ECA rule.
RuleLinear?Algebraic normal formTruth table110Nosit+1=sit⊕si+1t⊕sit⋅si+1t⊕si−1t⋅sit⋅si+1t11111010110001101000100001101110150Yessit+1=si−1t⊕sit⊕si+1t11111010110001101000100010010110


## 2.1. Randomness

Random numbers are an essential component of cryptographic applications such as encryption, key generation, or content masking. The notions of random, randomness, and random numbers are often associated with unpredictability and uniform distribution.A Random Number Generator (RNG) is an algorithm that produces sequences of numbers or bits that seem to be random, from a seed or from a continuously fed input. True Radom Number Generators (TRNGs) are a class of RNGs that use physical sources to generate “true” random sequences. However, working with truly random sequences has drawbacks like the reliability of the physical sources, the availability of the data, the limited amount of data, or the high cost of getting the data. Pseudorandom Number Generators (PRNGs) are another class of RNGs that use algorithms to generate random sequences as indistinguishable as possible from “truly” random sequences [9].In general, an RNG must meet specific conditions. Its output should be independent, uniformly distributed, and unpredictable [9]. The generator should be efficient in terms of the amount of random numbers generated. In order to be used in a cryptographic environment, an RNG should additionally be resistant to well-known attacks [9]. This means that, despite having information about the input or the current/previous output of the generator, an attacker cannot guess its output (previous, current, or future).


## 2.2. Entropy

Entropy is another term associated with RNGs. The concept was first introduced in 1948 by Claude Shannon in the field of Information Theory. Entropy is the measure of randomness as it represents the uncertainty of the output generated by a data source.Entropy is denoted byH(X) and defined as [10](1)HX=−∑xPX=x⋅log2PX=x,where PX=x is the probability of X taking the value x in the sample space ΩX.As shown in [10], the maximum entropy distribution over the range is the uniform distribution. The entropy in this range is no greater than log2ΩX.In cryptographic applications, entropy is one of the measures of the quality of an RNG. Therefore, it is expected to be the highest possible as it translates into more efforts needed by an attacker to guess the output.


## 2.3. Cellular Automata (CA)

Stanislaw Ulam took an interest in self-replicating automata concepts in the 1940s and initiated the studies on cellular automata. Later on, upon suggestions by Stanislaw Ulam, John von Neumann further developed the theory on cellular automata in the 1960s to model self-reproduction in the field of Biology. CAs gain popularity in the 1970s with Martin Gardner and John Conway’s Game of Life [11].A cellular automaton represents a network of cells or finite state automaton. The state of each cell at timet changes according to a local rule and depends on the state of the surrounding cells or neighborhood at time t−1.The interest in cellular automata comes from the fact that simple local calculations, at the level of cells, result in a complex global behavior, at the level of the automaton. Even though uniform CAs (uniformity in update, in dependency to neighbors, in local rules, etc.) are suitable for modeling physical systems, nonuniform CAs are more suited and more efficient to model real life systems.A CA is formally defined as the tuple (d, L, S, N, f) [11], where(i)
d is the dimension of the cellular space(ii)
L is the d-dimensional cellular space, in which elements are called cells(iii)
S is a finite state, in which elements are called states(iv)
N=v1⟶,v2⟶,…,vN⟶ is the neighborhood vector(v)
f is the local rule of the automaton that dictates the change of state of each cell from time t to time t+1Ifc is considered to be the current configuration of the automaton, then Φ(c), Φ2(c), … represent its next configurations. Φ is called the global function.Changingd, L, S, N, and f leads to different types of CAs.A CA for which all the cells are updated by the same rulef is called uniform. Otherwise, the CA is called hybrid or nonuniform. A CA for which the boundary cells are assigned the state 0 is called a null boundary CA. A periodic boundary CA has the extreme cells adjacent to each other.Elementary Cellular Automata or ECAs were introduced in the 1980s by Wolfram. These CAs are one-dimensional, have two possible states (0 or 1), and are characterized by a three-neighborhood dependency. Extensive research related to CAs has been conducted in the field of Cryptography, especially in producing random numbers using CAs. Wolfram introduced this association between Pseudorandom Number Generators and CAs in 1985 [2].In the case of ECAs, the neighborhood of theith cell is given by Ni=si−1,si,si+1 and the local rule f for that cell is defined as sit+1=fisi−1t,sit,si+1t, sit being the current state and sit+1 the next state of the cell. Since ECAs assume two possible states and have a three-neighborhood dependency, 223=256 rules are possible. Each of these rules can be represented as a Boolean function or as a truth table, the decimal value of the truth table being the rule number. If the Boolean expression of the rule contains only the XOR (⊕) operator, then the rule is linear. Otherwise, if the Boolean expression contains also AND(⋅)/OR(+) operators, then the rule is nonlinear. Table 1 shows an example of a linear and a nonlinear rule.Table 1
An example of a linear and nonlinear ECA rule.
RuleLinear?Algebraic normal formTruth table110Nosit+1=sit⊕si+1t⊕sit⋅si+1t⊕si−1t⋅sit⋅si+1t11111010110001101000100001101110150Yessit+1=si−1t⊕sit⊕si+1t11111010110001101000100010010110


## 3. Related Work

Wolfram was the first to use CAs as a source of randomness [2]. To generate pseudorandom numbers sequences (PNSs), he used a one-dimensional cellular automaton with r = 1 and rule 30. In [3], Hortensius et al. proposed a PRNG based on cellular automata for built-in self-test. Both uniform (rule 30) and nonuniform (rules 30 and 45, and rules 90 and 150) cellular automata were evaluated in the article. Nandi et al. [4] also worked on nonuniform cellular automata and proposed 5 relevant rulesets (rulesets can be found in Appendix B). Tomassini et al. [5] extended the research on nonuniform, one-dimensional CAs using four rules (90, 105, 150, and 165) selected using cellular programming, an evolutionary technique. Guan et al. introduced controllable CA [6] and self-programmable CA [7]. By using control signals and hybrid cell configurations, they managed to increase the randomness. Seredynski et al. [8] worked also on nonuniform, one-dimensional CAs with rules of radius 1 and 2. They used cellular programming to discover the relevant rules among 47 rules. The most relevant ruleset chosen for radius 1 in [8] was (86, 90, 101, 105, 153, 165). Recently, Bhattacharjee et al. [12] explored 3-state one-dimensional CA. Each of these constructions either has been attacked or presents some flaws. This is still a young field of research, and improvements are still to be made. The configuration of the cellular automaton (dimension, neighborhood, rules selection, etc.) can be seen as an optimization problem. As such, the configuration chosen must be a compromise of cryptographic properties resulting in some flaws and gaps. In this article, the authors chose to work with a hybrid one-dimensional cellular automaton combined with other cryptographic primitives to maximize the strength and the randomness quality of the sequences generated. Table 2 summarizes the previously developed CA-based PRNGs.Table 2
CA-based PRNGs.
CA- based PRNGsCellular automatonRulesetWolfram [2]2-state one-dimensional CA withr = 1 (uniform)Rule 30Hortensius et al. [3]2-state one-dimensional CA withr = 1 (uniform)Rule 302-state one-dimensional CA withr = 1 (nonuniform)30, 45, 90, 150Nandi et al. [4]2-state one-dimensional CA withr = 1 (nonuniform)153, 153, 153, 153, 51, 51, 51, 51195, 195, 195, 195, 51, 51, 51, 5151, 51, 153, 153, 153, 153, 51, 5151, 51, 195, 195, 195, 195, 51, 5151, 153, 153, 153, 153, 153, 153, 51Tomassini et al. [5]2-state one-dimensional CA withr = 1 (nonuniform)90, 105, 150, 165Guan et al [6, 7]2-state one-dimensional controllable CA and self-programmable CA90, 165, 150, 105Seredynski et al. [8]2-state one-dimensional CA withr = 1 (nonuniform)86, 90, 101, 105, 153, 165Bhattacharjee et al. [12]3-state one-dimensional CA withr = 1120021120021021120021021210


### 3.1. CFA Design Principles and Description

#### 3.1.1. Design Principles

The goal behind the generalCFA scheme was to develop a flexible PRNG. In other words, it can be adapted according to the design constraints and can be easily integrated in a broader system. This implies that its components are independent. It also implies that it can rely on existing cryptographic primitives or use new constructions.CFA was also designed with portability and resistance to attacks in mind. The system was conceived to be resistant to most of the known attacks against PRNGs. However, the authors also tried to make it comply with the following constraints:(i)
Flexibility(ii)
Efficiency in execution(iii)
Ease of use(iv)
Simplicity in designThe general building blocks ofCFA are as follows: (i)
A seed file containing high entropy sequences(ii)
A reseed trigger mechanism that initiates the reseed mechanism(iii)
A reseed mechanism that updates the seed file(iv)
An output generation mechanism that comprises the cryptographic primitives and other functions and generates the outputFigure1 details the general building blocks and mechanisms by which an input is generated using CFA.Figure 1
CFA block diagram.In the rest of this section, each of these components is detailed.


#### 3.1.2. Seed File

High entropy sequences are stored in the seed file before being used in the output generation mechanism. The origin of these sequences depends on the application and the designer of the system. They are appended to the seed file, stored in flash memory or hard disk, and to be used subsequently by the reseed mechanism to be fed to the output generation mechanism.


#### 3.1.3. Reseed Trigger Mechanism

The reseed trigger mechanism controls when a reseeding is necessary based on some parameter threshold. This parameter could be, for example, the period of the cellular automaton. In addition to this periodic reseed, an upon request reseed mechanism can be implemented for when the state of the PRNG is compromised by some attack.


#### 3.1.4. Reseed Mechanism

During the reseed mechanism, the seed file is updated. When the reseed mechanism is triggered, a new random sequence of fixed length is generated and prepended to the seed file. When all the sequences of the seed file are used, its content is cleared, and new sequences are generated.


#### 3.1.5. Output Generation Mechanism

The output generation mechanism is the core of the system. It uses cryptographic primitives and cellular automata configurations to generate a random sequence with entropy as high as possible.


### 3.2. Description

In this section, a more detailed description of the general scheme’s (CFA) generation mechanism and a specific implementation are presented.


#### 3.2.1. CFA Outline

CFA output generation mechanism comprises three major building blocks:(i)
A hash function,h(x), that has the properties of preimage resistance, second preimage resistance, and collision resistance(ii)
A CA evolution function,Evol(x)(iii)
A block cipher,E(x), with good statistical properties and good resistance to attacksCFA has a strength in bits of min(m, k), where m is the size in bits of the hash function digest, and k is the size in bits of the key of the block cipher. Figure 2 depicts the output generation mechanism of CFA comprising h, Evol and E.Figure 2
Output Generation Mechanism block diagram.


#### 3.2.2. A Specific Implementation: CFA-256

InCFA-256, the building blocks used are as follows: (i)
A seed generated by means of the Bouncy Castle Java library(ii)
The SHA-3-256 hash function(iii)
A one-dimensional, nonuniform two-state CA withr = 1(iv)
The AES-256 block cipher in counter mode


#### 3.2.3. Step 0: Seed File Generation

TheCFA-256 algorithm starts with the generation of a seed using the ThreadedSeedGenerator class found in the Bouncy Castle Java library. The size of the seed generated is 1024 bits. Each sequence generated is then stored in the seed file. A selected sequence from the seed file is then fed to the SHA-3 hash function.


#### 3.2.4. Step 1: SHA-3 Processing

SHA-3 relies on a sponge construction rather than a Merkle–Damgård construction like SHA-1 and SHA-2. The message is divided into blocks, and padding is applied if necessary (preprocessing phase). The sponge construction starts with an absorbing phase followed by a squeezing phase. During the absorbing phase (or input phase), the input blocksxi are processed, while, during the squeezing phase (or output phase), the output h(M) is computed. For both of these phases, the same f function is used. f is a fixed permutation function consisting of 24 rounds of 5 reversible operations (θ,ρ,π,χandι applied in this order).In Figure3, r represents the size of the input blocks, called the bitrate. c represents the capacity, which is closely related to the security level of the construction and equal to two times the digest size. The sum of these two parameters represents the width of the state or b. In SHA-3, b is equal to 1600 bits. Using SHA-3, hash values of lengths 224, 256, 384, or 512 bits can be obtained from messages of any size. For CFA-256, the parameters used are r = 1088 bits, c = 512 bits, and 256 bits for the size of the digest (Table 3, [13]). Table 3 summarizes SHA-3 parameters for different digest sizes.Figure 3
Sponge construction of SHA-3 [9].Table 3
SHA-3 parameters [13].
Digest Size224256384512Message sizeNo maximumNo maximumNo maximumNo maximumBlock size11521088832576Word size64646464Number of rounds24242424Capacity c4485127681024Collision resistance2112212821922256Second preimage resistance2224225623842512A 256-bit digest is obtained from the SHA-3 function and is then evolved using a one-dimensional elementary CA.


#### 3.2.5. Step 2: CA Evolution

The CA used in this case is a hybrid CA. The local rulef consists of the ruleset [30, 90, 150, 30, 110, 30, 90, 150] applied alternately on the cells. In order to choose those rules, the guideline provided in [1] was followed. The rule selection procedure is detailed in the Appendix. The CA is evolved using this local rule 128 times. The obtained 256 cells are then supplied to the AES encryption algorithm.


#### 3.2.6. Step 3: AES Encryption

This step encrypts the output of the second one in counter mode using a random secret key. Figure4 shows the general AES encryption process. The plaintext is the result of the CA evolutions, and the ciphertext is the random sequence generated by the whole CFA-256 algorithm. The secret key involved in the encryption is generated using ThreadedSeedGenerator.Figure 4
AES-256 encryption [9].


#### 3.2.7. CFA-256 Algorithm

Algorithm1 shows the process by which the seed file is filled with high entropy sequences.Algorithm 1: Seed file creation/filling.
Input: number_of_desired_sequencesOutput: seed_fileBeginIf seed_file existsOverride seed_fileElseCreate seed_fileend ifLetn ← 0Whilen < number_of_desired_sequences doseq[n] ← ThreadedSeedGenerator(128)While H(seq[n]) ≤ 0.9 doseq[n] ← ThreadedSeedGenerator(128)end whileseed[n] ← seq[n]n ← n+1end whileseed_file ← seedreturn seed_fileEndAlgorithm2 shows the generation mechanism of CFA-256.Algorithm 2: Pseudocode CFA-256.
Input: seedOutput: Random bits (256 bits)BeginLetj ← (-sizeOf(seed)-2) mod 256Let ruleSet ← {30, 90, 150, 30, 110, 30, 90, 150}Let keyAES ← ThreadedSeedGenerator(256)paddedSeed ← seed || 1||0j|| 1s ← SHA3(paddedSeed, 256)s[0] ← s[256]s[257] ←s [1].For it from 1 to 128Fori from 1 to 256k ← i−1 modulo sizeOf(ruleSet)If ((k = = 0) || (k = = 3) || (k = 5)) then//30evolution[i] ← s[i−1] ⊕ (s[i]+s[i+1])Else if ((k = = 1) || (k = = 6)) thenevolution[i] ← s[i−1] ⊕ s[i+1]Else if ((k = = 2) || (k = = 7)) then//150evolution[i] ← s[i−1] ⊕s[i] ⊕s[i+1]Else//110evolution[i] ← s[i−1] ⊕s[i+1] ⊕s[i−1]. s[i+1] ⊕s[i−1]. s[i]. s[i+1]End ifEnd forEnd forgenerated_bits ←AES256 (evolution, keyAES, CTR)End


## 3.1. CFA Design Principles and Description

### 3.1.1. Design Principles

The goal behind the generalCFA scheme was to develop a flexible PRNG. In other words, it can be adapted according to the design constraints and can be easily integrated in a broader system. This implies that its components are independent. It also implies that it can rely on existing cryptographic primitives or use new constructions.CFA was also designed with portability and resistance to attacks in mind. The system was conceived to be resistant to most of the known attacks against PRNGs. However, the authors also tried to make it comply with the following constraints:(i)
Flexibility(ii)
Efficiency in execution(iii)
Ease of use(iv)
Simplicity in designThe general building blocks ofCFA are as follows: (i)
A seed file containing high entropy sequences(ii)
A reseed trigger mechanism that initiates the reseed mechanism(iii)
A reseed mechanism that updates the seed file(iv)
An output generation mechanism that comprises the cryptographic primitives and other functions and generates the outputFigure1 details the general building blocks and mechanisms by which an input is generated using CFA.Figure 1
CFA block diagram.In the rest of this section, each of these components is detailed.


### 3.1.2. Seed File

High entropy sequences are stored in the seed file before being used in the output generation mechanism. The origin of these sequences depends on the application and the designer of the system. They are appended to the seed file, stored in flash memory or hard disk, and to be used subsequently by the reseed mechanism to be fed to the output generation mechanism.


### 3.1.3. Reseed Trigger Mechanism

The reseed trigger mechanism controls when a reseeding is necessary based on some parameter threshold. This parameter could be, for example, the period of the cellular automaton. In addition to this periodic reseed, an upon request reseed mechanism can be implemented for when the state of the PRNG is compromised by some attack.


### 3.1.4. Reseed Mechanism

During the reseed mechanism, the seed file is updated. When the reseed mechanism is triggered, a new random sequence of fixed length is generated and prepended to the seed file. When all the sequences of the seed file are used, its content is cleared, and new sequences are generated.


### 3.1.5. Output Generation Mechanism

The output generation mechanism is the core of the system. It uses cryptographic primitives and cellular automata configurations to generate a random sequence with entropy as high as possible.


## 3.1.1. Design Principles

The goal behind the generalCFA scheme was to develop a flexible PRNG. In other words, it can be adapted according to the design constraints and can be easily integrated in a broader system. This implies that its components are independent. It also implies that it can rely on existing cryptographic primitives or use new constructions.CFA was also designed with portability and resistance to attacks in mind. The system was conceived to be resistant to most of the known attacks against PRNGs. However, the authors also tried to make it comply with the following constraints:(i)
Flexibility(ii)
Efficiency in execution(iii)
Ease of use(iv)
Simplicity in designThe general building blocks ofCFA are as follows: (i)
A seed file containing high entropy sequences(ii)
A reseed trigger mechanism that initiates the reseed mechanism(iii)
A reseed mechanism that updates the seed file(iv)
An output generation mechanism that comprises the cryptographic primitives and other functions and generates the outputFigure1 details the general building blocks and mechanisms by which an input is generated using CFA.Figure 1
CFA block diagram.In the rest of this section, each of these components is detailed.


## 3.1.2. Seed File

High entropy sequences are stored in the seed file before being used in the output generation mechanism. The origin of these sequences depends on the application and the designer of the system. They are appended to the seed file, stored in flash memory or hard disk, and to be used subsequently by the reseed mechanism to be fed to the output generation mechanism.


## 3.1.3. Reseed Trigger Mechanism

The reseed trigger mechanism controls when a reseeding is necessary based on some parameter threshold. This parameter could be, for example, the period of the cellular automaton. In addition to this periodic reseed, an upon request reseed mechanism can be implemented for when the state of the PRNG is compromised by some attack.


## 3.1.4. Reseed Mechanism

During the reseed mechanism, the seed file is updated. When the reseed mechanism is triggered, a new random sequence of fixed length is generated and prepended to the seed file. When all the sequences of the seed file are used, its content is cleared, and new sequences are generated.


## 3.1.5. Output Generation Mechanism

The output generation mechanism is the core of the system. It uses cryptographic primitives and cellular automata configurations to generate a random sequence with entropy as high as possible.


## 3.2. Description

In this section, a more detailed description of the general scheme’s (CFA) generation mechanism and a specific implementation are presented.


### 3.2.1. CFA Outline

CFA output generation mechanism comprises three major building blocks:(i)
A hash function,h(x), that has the properties of preimage resistance, second preimage resistance, and collision resistance(ii)
A CA evolution function,Evol(x)(iii)
A block cipher,E(x), with good statistical properties and good resistance to attacksCFA has a strength in bits of min(m, k), where m is the size in bits of the hash function digest, and k is the size in bits of the key of the block cipher. Figure 2 depicts the output generation mechanism of CFA comprising h, Evol and E.Figure 2
Output Generation Mechanism block diagram.


### 3.2.2. A Specific Implementation: CFA-256

InCFA-256, the building blocks used are as follows: (i)
A seed generated by means of the Bouncy Castle Java library(ii)
The SHA-3-256 hash function(iii)
A one-dimensional, nonuniform two-state CA withr = 1(iv)
The AES-256 block cipher in counter mode


### 3.2.3. Step 0: Seed File Generation

TheCFA-256 algorithm starts with the generation of a seed using the ThreadedSeedGenerator class found in the Bouncy Castle Java library. The size of the seed generated is 1024 bits. Each sequence generated is then stored in the seed file. A selected sequence from the seed file is then fed to the SHA-3 hash function.


### 3.2.4. Step 1: SHA-3 Processing

SHA-3 relies on a sponge construction rather than a Merkle–Damgård construction like SHA-1 and SHA-2. The message is divided into blocks, and padding is applied if necessary (preprocessing phase). The sponge construction starts with an absorbing phase followed by a squeezing phase. During the absorbing phase (or input phase), the input blocksxi are processed, while, during the squeezing phase (or output phase), the output h(M) is computed. For both of these phases, the same f function is used. f is a fixed permutation function consisting of 24 rounds of 5 reversible operations (θ,ρ,π,χandι applied in this order).In Figure3, r represents the size of the input blocks, called the bitrate. c represents the capacity, which is closely related to the security level of the construction and equal to two times the digest size. The sum of these two parameters represents the width of the state or b. In SHA-3, b is equal to 1600 bits. Using SHA-3, hash values of lengths 224, 256, 384, or 512 bits can be obtained from messages of any size. For CFA-256, the parameters used are r = 1088 bits, c = 512 bits, and 256 bits for the size of the digest (Table 3, [13]). Table 3 summarizes SHA-3 parameters for different digest sizes.Figure 3
Sponge construction of SHA-3 [9].Table 3
SHA-3 parameters [13].
Digest Size224256384512Message sizeNo maximumNo maximumNo maximumNo maximumBlock size11521088832576Word size64646464Number of rounds24242424Capacity c4485127681024Collision resistance2112212821922256Second preimage resistance2224225623842512A 256-bit digest is obtained from the SHA-3 function and is then evolved using a one-dimensional elementary CA.


### 3.2.5. Step 2: CA Evolution

The CA used in this case is a hybrid CA. The local rulef consists of the ruleset [30, 90, 150, 30, 110, 30, 90, 150] applied alternately on the cells. In order to choose those rules, the guideline provided in [1] was followed. The rule selection procedure is detailed in the Appendix. The CA is evolved using this local rule 128 times. The obtained 256 cells are then supplied to the AES encryption algorithm.


### 3.2.6. Step 3: AES Encryption

This step encrypts the output of the second one in counter mode using a random secret key. Figure4 shows the general AES encryption process. The plaintext is the result of the CA evolutions, and the ciphertext is the random sequence generated by the whole CFA-256 algorithm. The secret key involved in the encryption is generated using ThreadedSeedGenerator.Figure 4
AES-256 encryption [9].


### 3.2.7. CFA-256 Algorithm

Algorithm1 shows the process by which the seed file is filled with high entropy sequences.Algorithm 1: Seed file creation/filling.
Input: number_of_desired_sequencesOutput: seed_fileBeginIf seed_file existsOverride seed_fileElseCreate seed_fileend ifLetn ← 0Whilen < number_of_desired_sequences doseq[n] ← ThreadedSeedGenerator(128)While H(seq[n]) ≤ 0.9 doseq[n] ← ThreadedSeedGenerator(128)end whileseed[n] ← seq[n]n ← n+1end whileseed_file ← seedreturn seed_fileEndAlgorithm2 shows the generation mechanism of CFA-256.Algorithm 2: Pseudocode CFA-256.
Input: seedOutput: Random bits (256 bits)BeginLetj ← (-sizeOf(seed)-2) mod 256Let ruleSet ← {30, 90, 150, 30, 110, 30, 90, 150}Let keyAES ← ThreadedSeedGenerator(256)paddedSeed ← seed || 1||0j|| 1s ← SHA3(paddedSeed, 256)s[0] ← s[256]s[257] ←s [1].For it from 1 to 128Fori from 1 to 256k ← i−1 modulo sizeOf(ruleSet)If ((k = = 0) || (k = = 3) || (k = 5)) then//30evolution[i] ← s[i−1] ⊕ (s[i]+s[i+1])Else if ((k = = 1) || (k = = 6)) thenevolution[i] ← s[i−1] ⊕ s[i+1]Else if ((k = = 2) || (k = = 7)) then//150evolution[i] ← s[i−1] ⊕s[i] ⊕s[i+1]Else//110evolution[i] ← s[i−1] ⊕s[i+1] ⊕s[i−1]. s[i+1] ⊕s[i−1]. s[i]. s[i+1]End ifEnd forEnd forgenerated_bits ←AES256 (evolution, keyAES, CTR)End


## 3.2.1. CFA Outline

CFA output generation mechanism comprises three major building blocks:(i)
A hash function,h(x), that has the properties of preimage resistance, second preimage resistance, and collision resistance(ii)
A CA evolution function,Evol(x)(iii)
A block cipher,E(x), with good statistical properties and good resistance to attacksCFA has a strength in bits of min(m, k), where m is the size in bits of the hash function digest, and k is the size in bits of the key of the block cipher. Figure 2 depicts the output generation mechanism of CFA comprising h, Evol and E.Figure 2
Output Generation Mechanism block diagram.


## 3.2.2. A Specific Implementation: CFA-256

InCFA-256, the building blocks used are as follows: (i)
A seed generated by means of the Bouncy Castle Java library(ii)
The SHA-3-256 hash function(iii)
A one-dimensional, nonuniform two-state CA withr = 1(iv)
The AES-256 block cipher in counter mode


## 3.2.3. Step 0: Seed File Generation

TheCFA-256 algorithm starts with the generation of a seed using the ThreadedSeedGenerator class found in the Bouncy Castle Java library. The size of the seed generated is 1024 bits. Each sequence generated is then stored in the seed file. A selected sequence from the seed file is then fed to the SHA-3 hash function.


## 3.2.4. Step 1: SHA-3 Processing

SHA-3 relies on a sponge construction rather than a Merkle–Damgård construction like SHA-1 and SHA-2. The message is divided into blocks, and padding is applied if necessary (preprocessing phase). The sponge construction starts with an absorbing phase followed by a squeezing phase. During the absorbing phase (or input phase), the input blocksxi are processed, while, during the squeezing phase (or output phase), the output h(M) is computed. For both of these phases, the same f function is used. f is a fixed permutation function consisting of 24 rounds of 5 reversible operations (θ,ρ,π,χandι applied in this order).In Figure3, r represents the size of the input blocks, called the bitrate. c represents the capacity, which is closely related to the security level of the construction and equal to two times the digest size. The sum of these two parameters represents the width of the state or b. In SHA-3, b is equal to 1600 bits. Using SHA-3, hash values of lengths 224, 256, 384, or 512 bits can be obtained from messages of any size. For CFA-256, the parameters used are r = 1088 bits, c = 512 bits, and 256 bits for the size of the digest (Table 3, [13]). Table 3 summarizes SHA-3 parameters for different digest sizes.Figure 3
Sponge construction of SHA-3 [9].Table 3
SHA-3 parameters [13].
Digest Size224256384512Message sizeNo maximumNo maximumNo maximumNo maximumBlock size11521088832576Word size64646464Number of rounds24242424Capacity c4485127681024Collision resistance2112212821922256Second preimage resistance2224225623842512A 256-bit digest is obtained from the SHA-3 function and is then evolved using a one-dimensional elementary CA.


## 3.2.5. Step 2: CA Evolution

The CA used in this case is a hybrid CA. The local rulef consists of the ruleset [30, 90, 150, 30, 110, 30, 90, 150] applied alternately on the cells. In order to choose those rules, the guideline provided in [1] was followed. The rule selection procedure is detailed in the Appendix. The CA is evolved using this local rule 128 times. The obtained 256 cells are then supplied to the AES encryption algorithm.


## 3.2.6. Step 3: AES Encryption

This step encrypts the output of the second one in counter mode using a random secret key. Figure4 shows the general AES encryption process. The plaintext is the result of the CA evolutions, and the ciphertext is the random sequence generated by the whole CFA-256 algorithm. The secret key involved in the encryption is generated using ThreadedSeedGenerator.Figure 4
AES-256 encryption [9].


## 3.2.7. CFA-256 Algorithm

Algorithm1 shows the process by which the seed file is filled with high entropy sequences.Algorithm 1: Seed file creation/filling.
Input: number_of_desired_sequencesOutput: seed_fileBeginIf seed_file existsOverride seed_fileElseCreate seed_fileend ifLetn ← 0Whilen < number_of_desired_sequences doseq[n] ← ThreadedSeedGenerator(128)While H(seq[n]) ≤ 0.9 doseq[n] ← ThreadedSeedGenerator(128)end whileseed[n] ← seq[n]n ← n+1end whileseed_file ← seedreturn seed_fileEndAlgorithm2 shows the generation mechanism of CFA-256.Algorithm 2: Pseudocode CFA-256.
Input: seedOutput: Random bits (256 bits)BeginLetj ← (-sizeOf(seed)-2) mod 256Let ruleSet ← {30, 90, 150, 30, 110, 30, 90, 150}Let keyAES ← ThreadedSeedGenerator(256)paddedSeed ← seed || 1||0j|| 1s ← SHA3(paddedSeed, 256)s[0] ← s[256]s[257] ←s [1].For it from 1 to 128Fori from 1 to 256k ← i−1 modulo sizeOf(ruleSet)If ((k = = 0) || (k = = 3) || (k = 5)) then//30evolution[i] ← s[i−1] ⊕ (s[i]+s[i+1])Else if ((k = = 1) || (k = = 6)) thenevolution[i] ← s[i−1] ⊕ s[i+1]Else if ((k = = 2) || (k = = 7)) then//150evolution[i] ← s[i−1] ⊕s[i] ⊕s[i+1]Else//110evolution[i] ← s[i−1] ⊕s[i+1] ⊕s[i−1]. s[i+1] ⊕s[i−1]. s[i]. s[i+1]End ifEnd forEnd forgenerated_bits ←AES256 (evolution, keyAES, CTR)End


## 4. Security Analysis and Results

### 4.1. Security Analysis

Here, it is assumed that the security of cryptographic primitives translates to the PRNG [14].According to [15], the following points represent some of the reasons that lead to a compromised PRNG: (i)
Entropy overestimation and guessable starting points(ii)
Chosen-Input Attacks(iii)
Side-Channel Attacks(iv)
Direct Cryptanalytic attacks


#### 4.1.1. Entropy Overestimation and Guessable Starting Points

In order to avoid this situation, a seed file has been used, and a seed/reseed mechanism has been implemented [16]. The seed file contains high entropy sequences that are used as input to the hash function. The seed/reseed mechanism is responsible for generating a new state of the PRNG from time to time or upon request. Thus, guessing the starting configuration, even in the case of entropy overestimation, is costly. In [4, 5, 8], no seed generation mechanism, reseed mechanism, or seed is mentioned.


#### 4.1.2. Chosen-Input Attacks

To resist these attacks, a cryptographic hash function is used in the generation mechanism. In [4, 5, 8], no strategy or mechanism is used to avoid or lessen the risk of chosen-input attacks.


#### 4.1.3. Side-Channel Attacks

A hybrid CA, with a carefully chosen ruleset combining linear and nonlinear rules with good cryptographic properties, has been used to protect against this kind of attacks. As shown in the next section and AppendixB, the cryptographic properties of the ruleset used in CFA-256 are better than the ones presented in [4, 5, 8].


#### 4.1.4. Direct Cryptanalytic Attacks

To prevent this kind of attacks, a secure block cipher along with a hash function has been used. It should be mentioned that attacks related to a state compromise are not considered for the design of a PRNG as these attacks can be prevented by the environment. Measures to prevent them should be handled at the system level [16]. In [4, 5, 8], no strategy or mechanism is used to avoid or lessen the risk of chosen-input attacks.


## 4.1. Security Analysis

Here, it is assumed that the security of cryptographic primitives translates to the PRNG [14].According to [15], the following points represent some of the reasons that lead to a compromised PRNG: (i)
Entropy overestimation and guessable starting points(ii)
Chosen-Input Attacks(iii)
Side-Channel Attacks(iv)
Direct Cryptanalytic attacks


### 4.1.1. Entropy Overestimation and Guessable Starting Points

In order to avoid this situation, a seed file has been used, and a seed/reseed mechanism has been implemented [16]. The seed file contains high entropy sequences that are used as input to the hash function. The seed/reseed mechanism is responsible for generating a new state of the PRNG from time to time or upon request. Thus, guessing the starting configuration, even in the case of entropy overestimation, is costly. In [4, 5, 8], no seed generation mechanism, reseed mechanism, or seed is mentioned.


### 4.1.2. Chosen-Input Attacks

To resist these attacks, a cryptographic hash function is used in the generation mechanism. In [4, 5, 8], no strategy or mechanism is used to avoid or lessen the risk of chosen-input attacks.


### 4.1.3. Side-Channel Attacks

A hybrid CA, with a carefully chosen ruleset combining linear and nonlinear rules with good cryptographic properties, has been used to protect against this kind of attacks. As shown in the next section and AppendixB, the cryptographic properties of the ruleset used in CFA-256 are better than the ones presented in [4, 5, 8].


### 4.1.4. Direct Cryptanalytic Attacks

To prevent this kind of attacks, a secure block cipher along with a hash function has been used. It should be mentioned that attacks related to a state compromise are not considered for the design of a PRNG as these attacks can be prevented by the environment. Measures to prevent them should be handled at the system level [16]. In [4, 5, 8], no strategy or mechanism is used to avoid or lessen the risk of chosen-input attacks.


## 4.1.1. Entropy Overestimation and Guessable Starting Points

In order to avoid this situation, a seed file has been used, and a seed/reseed mechanism has been implemented [16]. The seed file contains high entropy sequences that are used as input to the hash function. The seed/reseed mechanism is responsible for generating a new state of the PRNG from time to time or upon request. Thus, guessing the starting configuration, even in the case of entropy overestimation, is costly. In [4, 5, 8], no seed generation mechanism, reseed mechanism, or seed is mentioned.


## 4.1.2. Chosen-Input Attacks

To resist these attacks, a cryptographic hash function is used in the generation mechanism. In [4, 5, 8], no strategy or mechanism is used to avoid or lessen the risk of chosen-input attacks.


## 4.1.3. Side-Channel Attacks

A hybrid CA, with a carefully chosen ruleset combining linear and nonlinear rules with good cryptographic properties, has been used to protect against this kind of attacks. As shown in the next section and AppendixB, the cryptographic properties of the ruleset used in CFA-256 are better than the ones presented in [4, 5, 8].


## 4.1.4. Direct Cryptanalytic Attacks

To prevent this kind of attacks, a secure block cipher along with a hash function has been used. It should be mentioned that attacks related to a state compromise are not considered for the design of a PRNG as these attacks can be prevented by the environment. Measures to prevent them should be handled at the system level [16]. In [4, 5, 8], no strategy or mechanism is used to avoid or lessen the risk of chosen-input attacks.


## 5. Results

### 5.1. Cryptographic Properties of CA

In this section, the cryptographic properties (algebraic degree, the nonlinearity, the correlation immunity, etc.) of the hybrid ruleset selected (see Appendix) are presented. Here,xi correspond to the cellular automaton cells. Tables 4 to 8 show some of the cryptographic properties of the cellular automaton. Here, seven cells and three iterations were used.Table 4
Algebraic degree.
Iterationx0x1x2x3x4x5x6x7121123211232244322343455433Table 5
Nonlinearity.
Iterationx0x1x2x3x4x5x6x7120021200288861088833248523640484848Table 6
Correlation immunity.
Iterationx0x1x2x3x4x5x6x7101200012202200122300000201Table 7
Resiliency.
Iterationx0x1x2x3x4x5x6x710120−101220220−1−12230000−1−1−11Table 8
Balancedness.
Iterationx0x1x2x3x4x5x6x71✓✓✓✓✕✓✓✓2✓✓✓✓✕✕✓✓3✓✓✓✓✕✕✕✓From these tables, it can be noted that the correlation immunity, the resiliency, and the balancedness decrease with the iterations. However, the nonlinearity and the algebraic degree increase with the number of clock cycles. Therefore, the ruleset selected appears to be a good compromise for the cryptographic properties (AppendixA displays the selection process). Moreover, if the design proposed in this paper is compared to other known CA-based PRNGs on the basis of cryptographic properties and the CAs evolutions (results are presented in Appendix B and Appendix C), it can be considered as better suited for cryptographic use.


#### 5.1.1. Avalanche Effect

One interesting feature sought by any cryptographic primitive is the avalanche effect [9]. This property was first introduced by Feistel [17] and can be expressed as follows: a small change in the input (plaintext or key) results in a large change in the ciphertext [9]. Mathematically, it can be formulated as(2)∀I,I′|HI,I′=1,avalancheI′=HFI,FI′lengthFI×100,where I and I’ are two inputs that differ in one bit, and F is a function applied to these inputs. In this article, F corresponds to CFA-256.In order to evaluate the avalanche effect ofCFA-256, the following steps were applied: (i)
Generate 100 high entropy seeds(ii)
For each seed, generate outputs by changing one bit each time(iii)
For each seed, calculate the hamming distances(iv)
For each biti (1 ≤  i ≤ 1024), calculate the average of the hamming distancesFigure5 shows the results obtained.Figure 5
Avalanche effect.The maximum change is 54.99%, and the minimum is 45.01%. The average of all changes is equal to 50.02%. Therefore, changing a bit in the input yields about 50% changes in the output. This shows thatCFA-256 displays a good diffusion property.


#### 5.1.2. NIST Statistical Test Suite

The NIST Statistical Test Suite (STS) is a set of tests developed by the National Institute of Standards and Technology. The goal behind this test suite is to check the random behavior and the statistical properties of PRNGs and TRNGs algorithms by derivingp-values from sequences generated by these algorithms. These p-values represent the probability that a sequence was generated by means of a TRNG. A p-value measures the difference between a given sequence and a random sequence. The algorithm passes or fails the tests depending on a significance level, set to 0.01 for the NIST STS. A more detailed description of this test suite is provided in the NIST special publication 800-22 [18].A sequence of 10 M bits was generated usingCFA-256 and was used as an input to the test suite. Table 9 shows the results of the tests. CFA-256 passes all the applicable tests. Some tests are not applicable due to the fact that the CFA-256 output size (256 bits) is too small for the requirements of those tests (1 000 000 bits are required for the nonoverlapping template matching test for example).Table 9
NIST Statistical Test Suite results.
Test namep valueInterpretationThe frequency (monobit) test0.5884PassFrequency test within a block0.4362PassThe runs test0.5381PassTests for the longest-run-of-ones in a block0.5448PassThe binary matrix rank test—Not applicableThe discrete Fourier transform (spectral) test0.4079PassThe nonoverlapping template matching test—Not applicableThe overlapping template matching test—Not applicableMaurer’s “universal statistical” test0.3946PassThe linear complexity test0.7515PassThe Serialp-value 1 test0.7857PassThe Serialp-value 2 test0.7030PassThe approximate entropy test0.7335PassThe cumulative sums (cusums) forward test0.6292PassThe cumulative sums (cusums) reverse test0.7458PassThe random excursions test—Not applicableThe random excursions variant test—Not applicable


#### 5.1.3. DIEHARDER Battery of Tests

DIEHARDER is another well-known PRNGs and TRNGs test suite. It is a robust battery of tests developed by Robert G. Brown at Duke University [19]. It was designed to thoroughly test all kinds of random number generators in a systematic way. The goal is to include over time all known statistical tests and develop a universal test suite for PRNGs and TRNGs. As of the latest version available, DIEHARDER includes 17 tests from Georges Marsaglia’s DIEHARD test suite, Marsaglia and Tsang GCD test, 3 tests from the NIST STS, 5 tests developed by Brown, and 5 tests developed by David Bauer. The significance level for DIEHARDER is set to 0.005, and smaller p-values mean better test results.Table9 summarizes the results of the DIEHARDER tests for CFA-256 and other known PRNGs. Results in bold represent failed tests. Table 10 shows that CFA-256 passes all the tests included in the DIEHARDER test suite. Furthermore, it is the only design that passes all the tests. Therefore, it can be considered as a better alternative to the previously proposed designs.Table 10
DIEHARDER test suite results.
TestCFA[7] R1[7] R2[7] R3[7] R4[7] R5[8][11]10.66230.98020.84210.42370.34590.97680.43780.223220.54030.41480.47550.23830.57840.02020.22920.690530.67150.85070.79570.91240.44910.13620.24190.326440.90070.41250.00020.42930.97080.51950.82820.172650.24640.93660.36300.69420.17920.53800.89240.677860.82770.06980.54190.38990.61080.15150.90860.000170.08540.89000.46430.67560.23250.15220.80170.592680.46410.70050.15750.02620.24830.12220.50610.522790.48580.33880.01160.76400.66820.00600.25370.9393100.44700.99600.96750.63490.15200.30320.68340.1153110.20590.73040.61010.98380.30660.94270.95050.2887120.69670.76010.40230.30480.39650.10290.92100.3030130.34510.81190.98070.17760.82430.59840.89550.7754140.57530.84650.67180.70750.78770.34220.88400.0688150.59350.04810.53180.57890.20520.43970.02670.0308160.21640.94610.98680.40220.19080.02850.67560.2968170.38870.75920.33330.95960.63740.07930.70200.8279180.44940.46900.99980.99680.73070.91390.99820.4598190.88380.91090.97520.13650.25870.73080.93760.4891200.59770.19790.54490.51540.62030.99660.52260.0957210.49520.14620.99740.99860.22730.13110.95340.6477220.44340.33370.77380.99570.74800.66020.74070.2266230.42280.04750.81720.12310.96500.69830.11850.0505240.61200.40650.36400.19770.00960.52240.99920.9983250.55940.89590.99920.99600.98130.24580.93970.9961260.68160.38110.31710.69400.09000.35900.59570.6173270.40420.29680.31970.64810.96950.61800.66940.3752280.94760.76120.13610.84370.9904066700.89140.0999290.76780.24970.17380.18290.24460.72980.99670.0461300.76130.98690.13320.00010.11700.36880.92540.193310.25940.66610.84810.85850.48410.55520.82140.7918


## 5.1. Cryptographic Properties of CA

In this section, the cryptographic properties (algebraic degree, the nonlinearity, the correlation immunity, etc.) of the hybrid ruleset selected (see Appendix) are presented. Here,xi correspond to the cellular automaton cells. Tables 4 to 8 show some of the cryptographic properties of the cellular automaton. Here, seven cells and three iterations were used.Table 4
Algebraic degree.
Iterationx0x1x2x3x4x5x6x7121123211232244322343455433Table 5
Nonlinearity.
Iterationx0x1x2x3x4x5x6x7120021200288861088833248523640484848Table 6
Correlation immunity.
Iterationx0x1x2x3x4x5x6x7101200012202200122300000201Table 7
Resiliency.
Iterationx0x1x2x3x4x5x6x710120−101220220−1−12230000−1−1−11Table 8
Balancedness.
Iterationx0x1x2x3x4x5x6x71✓✓✓✓✕✓✓✓2✓✓✓✓✕✕✓✓3✓✓✓✓✕✕✕✓From these tables, it can be noted that the correlation immunity, the resiliency, and the balancedness decrease with the iterations. However, the nonlinearity and the algebraic degree increase with the number of clock cycles. Therefore, the ruleset selected appears to be a good compromise for the cryptographic properties (AppendixA displays the selection process). Moreover, if the design proposed in this paper is compared to other known CA-based PRNGs on the basis of cryptographic properties and the CAs evolutions (results are presented in Appendix B and Appendix C), it can be considered as better suited for cryptographic use.


### 5.1.1. Avalanche Effect

One interesting feature sought by any cryptographic primitive is the avalanche effect [9]. This property was first introduced by Feistel [17] and can be expressed as follows: a small change in the input (plaintext or key) results in a large change in the ciphertext [9]. Mathematically, it can be formulated as(2)∀I,I′|HI,I′=1,avalancheI′=HFI,FI′lengthFI×100,where I and I’ are two inputs that differ in one bit, and F is a function applied to these inputs. In this article, F corresponds to CFA-256.In order to evaluate the avalanche effect ofCFA-256, the following steps were applied: (i)
Generate 100 high entropy seeds(ii)
For each seed, generate outputs by changing one bit each time(iii)
For each seed, calculate the hamming distances(iv)
For each biti (1 ≤  i ≤ 1024), calculate the average of the hamming distancesFigure5 shows the results obtained.Figure 5
Avalanche effect.The maximum change is 54.99%, and the minimum is 45.01%. The average of all changes is equal to 50.02%. Therefore, changing a bit in the input yields about 50% changes in the output. This shows thatCFA-256 displays a good diffusion property.


### 5.1.2. NIST Statistical Test Suite

The NIST Statistical Test Suite (STS) is a set of tests developed by the National Institute of Standards and Technology. The goal behind this test suite is to check the random behavior and the statistical properties of PRNGs and TRNGs algorithms by derivingp-values from sequences generated by these algorithms. These p-values represent the probability that a sequence was generated by means of a TRNG. A p-value measures the difference between a given sequence and a random sequence. The algorithm passes or fails the tests depending on a significance level, set to 0.01 for the NIST STS. A more detailed description of this test suite is provided in the NIST special publication 800-22 [18].A sequence of 10 M bits was generated usingCFA-256 and was used as an input to the test suite. Table 9 shows the results of the tests. CFA-256 passes all the applicable tests. Some tests are not applicable due to the fact that the CFA-256 output size (256 bits) is too small for the requirements of those tests (1 000 000 bits are required for the nonoverlapping template matching test for example).Table 9
NIST Statistical Test Suite results.
Test namep valueInterpretationThe frequency (monobit) test0.5884PassFrequency test within a block0.4362PassThe runs test0.5381PassTests for the longest-run-of-ones in a block0.5448PassThe binary matrix rank test—Not applicableThe discrete Fourier transform (spectral) test0.4079PassThe nonoverlapping template matching test—Not applicableThe overlapping template matching test—Not applicableMaurer’s “universal statistical” test0.3946PassThe linear complexity test0.7515PassThe Serialp-value 1 test0.7857PassThe Serialp-value 2 test0.7030PassThe approximate entropy test0.7335PassThe cumulative sums (cusums) forward test0.6292PassThe cumulative sums (cusums) reverse test0.7458PassThe random excursions test—Not applicableThe random excursions variant test—Not applicable


### 5.1.3. DIEHARDER Battery of Tests

DIEHARDER is another well-known PRNGs and TRNGs test suite. It is a robust battery of tests developed by Robert G. Brown at Duke University [19]. It was designed to thoroughly test all kinds of random number generators in a systematic way. The goal is to include over time all known statistical tests and develop a universal test suite for PRNGs and TRNGs. As of the latest version available, DIEHARDER includes 17 tests from Georges Marsaglia’s DIEHARD test suite, Marsaglia and Tsang GCD test, 3 tests from the NIST STS, 5 tests developed by Brown, and 5 tests developed by David Bauer. The significance level for DIEHARDER is set to 0.005, and smaller p-values mean better test results.Table9 summarizes the results of the DIEHARDER tests for CFA-256 and other known PRNGs. Results in bold represent failed tests. Table 10 shows that CFA-256 passes all the tests included in the DIEHARDER test suite. Furthermore, it is the only design that passes all the tests. Therefore, it can be considered as a better alternative to the previously proposed designs.Table 10
DIEHARDER test suite results.
TestCFA[7] R1[7] R2[7] R3[7] R4[7] R5[8][11]10.66230.98020.84210.42370.34590.97680.43780.223220.54030.41480.47550.23830.57840.02020.22920.690530.67150.85070.79570.91240.44910.13620.24190.326440.90070.41250.00020.42930.97080.51950.82820.172650.24640.93660.36300.69420.17920.53800.89240.677860.82770.06980.54190.38990.61080.15150.90860.000170.08540.89000.46430.67560.23250.15220.80170.592680.46410.70050.15750.02620.24830.12220.50610.522790.48580.33880.01160.76400.66820.00600.25370.9393100.44700.99600.96750.63490.15200.30320.68340.1153110.20590.73040.61010.98380.30660.94270.95050.2887120.69670.76010.40230.30480.39650.10290.92100.3030130.34510.81190.98070.17760.82430.59840.89550.7754140.57530.84650.67180.70750.78770.34220.88400.0688150.59350.04810.53180.57890.20520.43970.02670.0308160.21640.94610.98680.40220.19080.02850.67560.2968170.38870.75920.33330.95960.63740.07930.70200.8279180.44940.46900.99980.99680.73070.91390.99820.4598190.88380.91090.97520.13650.25870.73080.93760.4891200.59770.19790.54490.51540.62030.99660.52260.0957210.49520.14620.99740.99860.22730.13110.95340.6477220.44340.33370.77380.99570.74800.66020.74070.2266230.42280.04750.81720.12310.96500.69830.11850.0505240.61200.40650.36400.19770.00960.52240.99920.9983250.55940.89590.99920.99600.98130.24580.93970.9961260.68160.38110.31710.69400.09000.35900.59570.6173270.40420.29680.31970.64810.96950.61800.66940.3752280.94760.76120.13610.84370.9904066700.89140.0999290.76780.24970.17380.18290.24460.72980.99670.0461300.76130.98690.13320.00010.11700.36880.92540.193310.25940.66610.84810.85850.48410.55520.82140.7918


## 5.1.1. Avalanche Effect

One interesting feature sought by any cryptographic primitive is the avalanche effect [9]. This property was first introduced by Feistel [17] and can be expressed as follows: a small change in the input (plaintext or key) results in a large change in the ciphertext [9]. Mathematically, it can be formulated as(2)∀I,I′|HI,I′=1,avalancheI′=HFI,FI′lengthFI×100,where I and I’ are two inputs that differ in one bit, and F is a function applied to these inputs. In this article, F corresponds to CFA-256.In order to evaluate the avalanche effect ofCFA-256, the following steps were applied: (i)
Generate 100 high entropy seeds(ii)
For each seed, generate outputs by changing one bit each time(iii)
For each seed, calculate the hamming distances(iv)
For each biti (1 ≤  i ≤ 1024), calculate the average of the hamming distancesFigure5 shows the results obtained.Figure 5
Avalanche effect.The maximum change is 54.99%, and the minimum is 45.01%. The average of all changes is equal to 50.02%. Therefore, changing a bit in the input yields about 50% changes in the output. This shows thatCFA-256 displays a good diffusion property.


## 5.1.2. NIST Statistical Test Suite

The NIST Statistical Test Suite (STS) is a set of tests developed by the National Institute of Standards and Technology. The goal behind this test suite is to check the random behavior and the statistical properties of PRNGs and TRNGs algorithms by derivingp-values from sequences generated by these algorithms. These p-values represent the probability that a sequence was generated by means of a TRNG. A p-value measures the difference between a given sequence and a random sequence. The algorithm passes or fails the tests depending on a significance level, set to 0.01 for the NIST STS. A more detailed description of this test suite is provided in the NIST special publication 800-22 [18].A sequence of 10 M bits was generated usingCFA-256 and was used as an input to the test suite. Table 9 shows the results of the tests. CFA-256 passes all the applicable tests. Some tests are not applicable due to the fact that the CFA-256 output size (256 bits) is too small for the requirements of those tests (1 000 000 bits are required for the nonoverlapping template matching test for example).Table 9
NIST Statistical Test Suite results.
Test namep valueInterpretationThe frequency (monobit) test0.5884PassFrequency test within a block0.4362PassThe runs test0.5381PassTests for the longest-run-of-ones in a block0.5448PassThe binary matrix rank test—Not applicableThe discrete Fourier transform (spectral) test0.4079PassThe nonoverlapping template matching test—Not applicableThe overlapping template matching test—Not applicableMaurer’s “universal statistical” test0.3946PassThe linear complexity test0.7515PassThe Serialp-value 1 test0.7857PassThe Serialp-value 2 test0.7030PassThe approximate entropy test0.7335PassThe cumulative sums (cusums) forward test0.6292PassThe cumulative sums (cusums) reverse test0.7458PassThe random excursions test—Not applicableThe random excursions variant test—Not applicable


## 5.1.3. DIEHARDER Battery of Tests

DIEHARDER is another well-known PRNGs and TRNGs test suite. It is a robust battery of tests developed by Robert G. Brown at Duke University [19]. It was designed to thoroughly test all kinds of random number generators in a systematic way. The goal is to include over time all known statistical tests and develop a universal test suite for PRNGs and TRNGs. As of the latest version available, DIEHARDER includes 17 tests from Georges Marsaglia’s DIEHARD test suite, Marsaglia and Tsang GCD test, 3 tests from the NIST STS, 5 tests developed by Brown, and 5 tests developed by David Bauer. The significance level for DIEHARDER is set to 0.005, and smaller p-values mean better test results.Table9 summarizes the results of the DIEHARDER tests for CFA-256 and other known PRNGs. Results in bold represent failed tests. Table 10 shows that CFA-256 passes all the tests included in the DIEHARDER test suite. Furthermore, it is the only design that passes all the tests. Therefore, it can be considered as a better alternative to the previously proposed designs.Table 10
DIEHARDER test suite results.
TestCFA[7] R1[7] R2[7] R3[7] R4[7] R5[8][11]10.66230.98020.84210.42370.34590.97680.43780.223220.54030.41480.47550.23830.57840.02020.22920.690530.67150.85070.79570.91240.44910.13620.24190.326440.90070.41250.00020.42930.97080.51950.82820.172650.24640.93660.36300.69420.17920.53800.89240.677860.82770.06980.54190.38990.61080.15150.90860.000170.08540.89000.46430.67560.23250.15220.80170.592680.46410.70050.15750.02620.24830.12220.50610.522790.48580.33880.01160.76400.66820.00600.25370.9393100.44700.99600.96750.63490.15200.30320.68340.1153110.20590.73040.61010.98380.30660.94270.95050.2887120.69670.76010.40230.30480.39650.10290.92100.3030130.34510.81190.98070.17760.82430.59840.89550.7754140.57530.84650.67180.70750.78770.34220.88400.0688150.59350.04810.53180.57890.20520.43970.02670.0308160.21640.94610.98680.40220.19080.02850.67560.2968170.38870.75920.33330.95960.63740.07930.70200.8279180.44940.46900.99980.99680.73070.91390.99820.4598190.88380.91090.97520.13650.25870.73080.93760.4891200.59770.19790.54490.51540.62030.99660.52260.0957210.49520.14620.99740.99860.22730.13110.95340.6477220.44340.33370.77380.99570.74800.66020.74070.2266230.42280.04750.81720.12310.96500.69830.11850.0505240.61200.40650.36400.19770.00960.52240.99920.9983250.55940.89590.99920.99600.98130.24580.93970.9961260.68160.38110.31710.69400.09000.35900.59570.6173270.40420.29680.31970.64810.96950.61800.66940.3752280.94760.76120.13610.84370.9904066700.89140.0999290.76780.24970.17380.18290.24460.72980.99670.0461300.76130.98690.13320.00010.11700.36880.92540.193310.25940.66610.84810.85850.48410.55520.82140.7918


## 6. Challenges, Possible Solutions, and Future Directions

The general design proposed in this article is adaptable, as mentioned before. Consequently, changing the building blocks is done according to applications. However, it is challenging in some applications like IoT systems. It is possible to choose either of the predeveloped lightweight systems (hash functions and block ciphers) together with CAs. As an alternative, irreversible and reversible CAs could be involved instead of hash functions and block ciphers, respectively, which provide the required properties and security.Future directions could include the use of CFA in banking systems security like [20]. In addition, the benefit of machine learning to find the best combination of linear and nonlinear CA rules using the classifiers is found in [21]. Moreover, an adequate extension of CFA to secure wireless sensor networks [22] will be proposed.


## 7. Conclusions

A cryptographically secure pseudorandom number generator is useful in various applications. A new family of PRNGs is described in this article. Both the general and the specific designs presented rely on three building blocks carefully selected for their cryptographic features. The generator is built upon two strong cryptographic primitives: a hash function and a block cipher. Those primitives ensure that the PRNG is resistant to several types of attacks. In addition, a hybrid cellular automaton is used to achieve better confusion and diffusion properties, as well as to increase the randomness and security criteria. Passing statistical tests (NIST STS and DIEHARDER), exhibiting a good avalanche property and using a cellular automaton with good cryptographic properties, shows thatCFA-256 can generate high quality random sequences and displays good confusion and diffusion properties.



---

*Source: 6640052-2021-05-28.xml*