Cryptographic Services Based on Elementary and Chaotic Cellular Automata

Abstract

In this paper, a security framework based on cellular automata is proposed, which is composed of three parts: entity authentication, data encryption, and decryption. Authentication is based on a zero-knowledge protocol, and its robustness is supported by the fact that the shared secret is not only an NP-complete problem but also dynamically transformed by a two-dimensional cellular automaton into a more complex secret. Thus, the authentication’s output is the key to data encryption/decryption in the following steps. One more strength of this system is the sensibility of the cellular automata to initial conditions—which is why we must know the initial configuration in order to obtain the key and the times that cellular automata evolved. All those characteristics give the system both robustness and security.

1. Introduction

Cryptography is an ancient discipline. It is concerned with constructing robust schemes against malicious attempts to make these schemes deviate from their prescribed functionality [1]. For a long time, in order to preserve our information, cryptographic protocols, schemes and mechanisms have been created. Nowadays, it is necessary to prevent the information disclosure and ensure that an unauthorized entity cannot access the transmitted messages. Due to the development of cryptography and cryptanalysis at the same time, there is a need to create robust methods as preventive measures. The protection of data is essential, not only with cryptographic schemes but also with authentication methods. The objective of this paper was to design a security framework based on cellular automata. First, an authentication test was developed based on zero-knowledge interactive proofs using an NP-complete problem as a shared secret due to the naturalness of these problems. Then, these are connected with a stream cipher using a 2-D cellular automaton. These tools were selected due their mathematical and computational properties.

2. Related Work

There are several methods to develop cryptography such as elliptic curves [2,3,4], genetic algorithms [5,6,7], chaotic maps [8,9,10] and cellular automaton. The last mentioned is the method proposed in this paper, which is a subset of dynamic systems that have been effectively and chiefly used to construct strong cryptosystems by taking advantage of not only their randomness but also their dynamical properties [11]. There are some cryptography applications with cellular automata: an evolutionary computation approach was proposed  [12] to design a fast and secure block cipher using non-uniform second-order cellular automata. Image encryption techniques aim to protect the image’s content with higher efficiency and security than conventional cryptographic methods using an image’s unique properties. An image encryption model based on two-dimensional partitioned cellular automaton was proposed [13]. This model has the same topology as a digital image and is flexible to images with different color depths.

Image encryption is an efficient and vital way to protect classified and secret images. With the advancement of the computer’s processing power, AES, DES, or chaotic series type, just like image encryption schemes are not as secure as before [14]. For that reason, those authors [14] presented a new hybrid image encryption method for protecting secret and imperative images by employing logistic sine system (LSS) together with two-dimensional cellular automata and finite-state machine-based DNA rule generator, other authors [15] presented an authenticated image encryption algorithm based on cellular automata.

In the same fashion, a novel image encryption scheme was proposed based on permutation–diffusion architecture using cellular automata [16]. Similarly, Xingyuan Wang and Dapeng Luan [17] proposed a novel image encryption scheme based on reversible cellular automaton (RCA) combining chaos. An intertwining logistic map with complex behavior and periodic boundary reversible cellular automata was used in that algorithm.

There was another image encryption algorithm proposed in [18], in which a special kind of periodic boundary cellular automata with unity attractors was used. Furthermore, there are other applications such as a chaotic encryption algorithm based on the “Life-like” cellular automata [19], which act as a pseudo-random generator (PRNG). In [20], a non-uniform cellular automata framework is proposed.

The aim of this work was to design a cellular automata security framework. As the first step, an authentication test was developed based on zero-knowledge interactive proofs, using as a shared secret an NP-complete problem. Then, a stream cipher developed with cellular automata (CA) must be joined to it because both constitute simple formal models for complex and chaotic systems; also, all the cells synchronously update their states by applying a local rule [21,22]. In contrast to some encryption techniques such as DES, AES, RC4 and VEST [23,24], our algorithm offers an authentication service, which must be approved in order to obtain a key and the access to encrypt or decrypt a file.

3. Materials and Methods

This section is devoted to introducing the preliminaries related to information security systems and a discrete model of computation to be discussed in this paper. We explicitly define the basics of cryptography, cellular automaton, complexity, and a well-knowing np-problem called three graph coloring.

3.1. Preliminary

3.1.1. Cellular Automata

One of our model’s parts are cellular automata (CA), which are defined by four characteristics [25]. The first is a discrete cellular state space ℓ which is the discrete lattice of cells or sites upon which CAs “live” and their dynamics unfold; the second element is the local space value $\Sigma$, each cell of ℓ indexed by the elements of the ℓ’s symmetry group. Although CAs are assumed to live on infinitely large lattices, computer simulations must necessarily be run on finite sets; for this reason, boundary conditions are important. Finally, there is a dynamical rule $\varphi$; state transitions are therefore local in both space and time, individual cells evolve iteratively according to a fixed and usually deterministic function of the current state of that cell and its neighboring cells.

3.1.2. Cellular Automata in Cryptography

The use of cellular automata in cryptography is done to best confront the ability of dynamical systems to generate complexity with the cryptanalyst’s tools for cutting through such complexity [26]. Moreover, they are attractive candidates for cryptosystems since they are naturally adapted to massively parallel computation. The approach to using CA in cryptography involves applying both reversible and irreversible rules. Using that tool to build cryptosystems is flexible and powerful; it can be used to solve a wide variety of practical cryptographic problems. These applications motivate the careful investigation of the security properties of such systems.

3.1.3. Some Features of Cryptography

Let A be a finite set, which we will call alphabet, and let m be the message (a text from $A^{\ast }$ ) that Alice wants to transmit in secrecy to Bob; it is usually called the plaintext. Alice will first transform the plaintext into $C=E\left(m\right)$, the so-called ciphertext. It will be the ciphertext that she will transmit to Bob. Let A and B be two finite alphabets. Any one-to-one mapping E of $A^{\ast }$ to $B^{\ast }$ is called a cryptographic transformation [27].

Cryptography itself splits into three main branches: symmetric algorithms, asymmetric algorithms and cryptographic protocols. We will focus on symmetric cryptography, which is divided into block ciphers and stream ciphers.

3.1.4. Perfectly Secret Encryption

We imagine that an adversary who knows the probability distribution over m also knows the likelihood of sending different messages. Subsequently, he observes some ciphertext being sent by one entity to another. Ideally, keeping this ciphertext should not affect the knowledge of the adversary; in other words, the a posteriori likelihood that some message m was sent should be no different from the a priori probability that m would be sent.

3.1.5. Zero-Knowledge Proofs

Zero-knowledge proofs are interactive protocols that enable one entity (called the prover) to convince another entity (called the verifier) of the validity of a mathematical statement without revealing anything beyond the statement’s assertion [28]; that is to say, is a pair of interactive Turing machines, which satisfy two properties—namely completeness and soundness [29].

• Completeness can be expressed as
  $Prob[(P,V)\left(x\right)=1|x\in L]\ge 1-{\left|x\right|}^{-c}$$(c>0)$
• Soundness can be expressed for every interactive Turing machine $P^{\ast }$ as
  $Prob[(P^{\ast },V)\left(x\right)=0|x\notin L]\ge 1-{\left|x\right|}^{-c}$$(c>0)$

In the first place, completeness means that the verifier (V) accepts the proof if the statement is true. In the second place, soundness implies that V rejecting the proof of the fact is false. A cheating prover can convince an honest verifier that some false statement is true with only a very small probability [30].

3.1.6. NP Complexity

The class $NP$ consists of all sets S: where a verifier exists, there is ordinarily a Turing machine V such that $x\in S$ if and only if there exists a string y of polynomial length in the size of x, such that $V(x,y)$ accepts in polynomial time the span of x [31].

3.1.7. Graph Coloring

The graph coloring problem is a NP-hard problem and can be defined as follows: given an undirected graph $G=(V,E)$ with $V=v_1,...,v_n$ being the set of nodes and $E=e_{i,j}:$ any edge between $v_i$ and $v_j$ is the set of edges. The graph coloring problem is: to determine a partition of V in a minimum number (the chromatic number) of color classes $c_1,c_2,...,c_n$ such that for each edge, $e_{i,j}\in E$, $v_i$ and $v_j$ are not in the same color class [32].

3.2. Cryptography with Cellular Automata and Zero Knowledge Model

This project was divided into two parts, each part refers to different pillars of information assurance, the first one describe the authentication and the second one describing the confidentiality and integrity.

3.2.1. Authentication

For the authentication system, a zero-knowledge interactive proof (ZKIP) is proposed, which has two graphs three-coloring $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ as a shared secret. This means the graphs are only known by the prover (P) and the verifier (V). Firstly, P generates a commit message indicating that it knows about the shared graphs. Secondly, V returns a challenge; in this case, it asks P for an edge of the chosen graph in a pseudo-random way, and P returns an answer to V. Finally, the process can be repeated several times to ensure verification. Two graphs were used: to make the authentication process difficult for a eavesdropper; so if this entity wants to obtain information, it would need to know both graphs and the way both graphs are colored.

A prover (P) chooses one graph, then changes the value of the vertexes’ color. During a loop, a pseudo-string is created and is processed with the new value of the graph; the result is sent to the verifier (V), who computes the vertexes’ value as well as choose an edge in the graph. If the edge is in the graph, the prove continues—and if the test does not fail in $m^2$ iterations, then it finishes correctly. This algorithm’s output will be a vector, which will be used as a key for the encryption–decryption of files.

P and V have access to the cipher function $F:(C,R)\to C^{\xi }$; $C\oplus R\to T$ and $AC:T\to C^{\xi }$, where the variables are represented by:

• R—binary vectors set of cardinality 8;
• C—colors set;
• $C^{\xi }$—cipher colors set;
• ⊕—operator XOR;
• $AC$—one-dimensional cellular automata defined as a 4-tuple (S,N,f,d);
• S—$\{0,1\}$;
• N—it is considered radius one;
• $f:S^n\to S$—rule 30;
• $d\in {\mathbb{Z}}^{+}$—one dimensional;
• $\overrightarrow{r_i},\overrightarrow{r_j}\in R$—binary vectors of cardinality 8;

The steps in the Algorithm 1 are executed $m^2$ times where $m=\left|E\right|$ and $E=E_1$ if $E_1>E_2$, else $E=E_2$, the aim is to enable one entity to convince another entity of the validity of the mathematical statement without revealing anything beyond the assertion of the statement.

3.2.2. Encryption/Decryption

In the data encryption and decryption, a matrix has as data the value of the vector obtained in the authentication repeated n-times, one cellular automaton of 2-D, and the file to be encrypted–decrypted. The output of the Algorithms 2 and 3 will be the encrypted–decrypted file, respectively. The headers of the files are encrypted which provokes the loss of the original file.

The output of the authentication process is called $\delta$, where: $\delta =\overrightarrow{r_i·r_j}$ and $\delta$ Vector of cardinality 16.

The cipher will be an cellular automaton P, defined as a 4-tuple (S,N,f,d) where:

⋄

S—$\{0,1\}$

⋄

N—Moore neighborhood, it is considered radius one.

⋄

$d\in {\mathbb{Z}}^{+}$—two dimensional.

⋄

$f:S^n\to S$—variant of Conway’s life:

• Any live cell with one, three, five or eight live neighbors survives;
• Any dead cell with three, five or seven live neighbors becomes a live cell;
• All other live cells die in the next generation. Similarly, all other dead cells stay dead.

The frontier states of the cellular automaton P will be toroidal. For the extremes, the neighbors will be taken from the upper, lower or extreme sides, respectively, to shape a neighborhood of the adjacent cells. Moreover, the lattice of this one will be represented as eight times the file’s size to encrypt (D); it is multiplied by eight because a flow cipher will be performed and it is necessary to represent the data in bytes.

Algorithm 1: Authentication test using interactive zero-knowledge.

In order to correctly decode the files, it is necessary for both the cellular automaton encoder and decoder to have the same input and the same configuration. This is the key $\delta$, which is an essential part because this one contains the number of times that the automaton will evolve. Moreover, it contains the data which will be replicated in a matrix; this matrix will be the input of the decoder CA.

4. Results

On top of that, the implementation of the algorithm and different types of analysis were performed using Python 3 on a computer with Intel CORE i5 processor having 4 GB RAM. First of all, we simulated the authentication algorithm and after the encryption/decryption algorithm, the Appendix A shows the app developed. Figure 1 shows us the software design.

Algorithm 2: Files encoder using cellular automaton.

Algorithm 3: Files decoder using cellular automaton.

input: Encrypted file E,$\delta$. output: Decrypted file D. The key $\delta$ is taken and replicated A times, this matrix will be the lattice of P. P evolves n-times, where n is represented with the first four digits of $\delta$ converted from binary to decimal. A vector V is created and transformation of the output from P to V is performed. E is read as a bits array.

In the second place, a general diagram to represent the functional mechanism of the proposed method is presented in Figure 2. Moreover, the diagram is divided into authentication, encryption, and decryption mechanisms. In Figure 3, the ZKIP authentication is shown and it explains how the communication is between the entities. Secondly, Figure 4 represents the block diagram of the encryption part; it is essential that the user approves the first step in order to obtain a key, whereas in the decryption part, the user must have the correct one to obtain the plaintext as shown in Figure 5.

4.1. Authentication

The ZKP algorithm satisfies three properties.:

• Completeness—if the graph is three colorable, then any pair of edges $(u,v)$ will undoubtedly be differently colored. Therefore, an honest verifier will complete all $m^2$ iterations and accept with a probability of 1;
• Soundness—if the graph is not three colorable and the verifier follows the protocol, then no matter how the prover plays and at each round, the verifier will reject with a probability of at least $\frac{1}{m}$;
• Zero-knowledge—the only information received by the verifier at each round is a pair of randomly selected elements, and the prover only answers cipher colors.

Isomorphic graphs are used when the algorithm does a nodes permutation before encrypting them to display the information at the verifier.

4.2. Encryption and Decryption

This section presents the results for the files of different categories, namely .JPG, .PDF, .MP3, .ZIP, .XLS, and .DOC. Files were chosen at random, comprising various file sizes and file types. Here, we present an analysis of 12 files, varying file sizes from 330 bytes to 8,649,167 bytes. The analysis compares encryption and decryption times, chi-square values, entropy, and avalanche achieved (%). The algorithm works for any file because conversion to byte-map is performed. In the encryption process, the header file is also modified to the cipher file which does not exhibit information about the plain file.

Table 1. File size, decryption, and encryption time.

	Source File Size (Byte)	File Type	Encryption Time (S)	Decryption Time (S)
1	159,726	.jpg	59.79029	43.2303643
2	526,241	.pdf	78.91665	78.500065
3	21,945	.jpg	6.10928	5.281383
4	42,127	.jpg	18.80239	18.437193
5	29,649	.xls	5.85605	5.5168359
6	113,630	.pdf	17.83326	18.91148
7	41,610	.doc	9.619935	10.464609
8	47,408	.jpg	14.97656	16.781949
9	8,649,167	.pdf	375.14071	364.25678
10	185,574	.mp3	12.85867	13.499593
11	757	.ZIP	0.095961	0.1871705
12	565,898	.ZIP	36.53161	35.850028

shows the file’s size, type, as well as the time of encryption and decryption for each one.

The entropy is described as the measurement of the unpredictability of data in the information source. In other words, this means the measurement of randomness in data which is calculated through Equation (1):

$$H\left(X\right)=-\sum _{i=0}^{n}P\left(x_i\right)logP\left(x_i\right)$$

(1)

where:

• x: discrete random variable;
• P(x): probability density function of x.

A completely random stream would thus have high entropy. For a stream with a highly random distribution of characters, the entropy should be close to 8 [33].

Another commonly used test to check for randomness in a stream of data is the chi-square test which calculates the degree to which two given samples of data differ from each other. The test tells the degree of confidence with which one can reject or accept a hypothesis:

$$X^2=\sum _{i=0}^{255}\frac{{(O_i-E_i)}^2}{E_i}$$

(2)

where:

• $E_i:$ the frequency of a character in the encrypted file;
• $O_i:$ the frequency of a character in a uniform distribution.

The chi-2 test in this paper is used to measure the histogram uniformity. Furthermore, the avalanche effect is measured using a statistical analysis of data. When an input is slightly changed, the output changes drastically. If a bit in the plain text is flipped or changed, then for an evident avalanche effect, almost half of the ciphertext bits are changed in the ciphertext. A good encryption algorithm should always satisfy the following relation:

$$\mathrm{Avalanche}\mathrm{effect}>\mathrm{50}\%$$

Table 2. Entropy, chi-square value, and avalanche achieved.

	Entropy		Chi-Square Value		Avalanche Achieved (%)
	Proposed Algorithm	RC4 Algorithm	Proposed Algorithm	RC4 Algorithm	Proposed Algorithm	RC4 Algorithm
1	7.98975191	7.9989	284.13432	240.19504	0.9959	0.9962
2	7.969346	7.99964	2664.0657	256.7372	0.996579	0.99613
3	7.8431466	7.9898	1670.2065	305.894	0.9951658	0.9965
4	7.9851687	7.9956	111.0691367	258.230	0.9958783	0.99582
5	7.9852211	7.99301	77.9890465	278.5256	0.99503	0.99568
6	7.9765496	7.9985	496.9716	225.897	0.9960992	0.995819
7	7.98867428	7.99846	85.1835	241.59396	0.99655	0.99582
8	7.927068	7.9963	858.9643723	238.8663	0.996365	0.99603
9	7.998741	7.990145	1930.6058	242.231	0.996062	0.99521
10	7.9934784	7.99905	216.205678	241.885	0.996068	0.99609
11	7.576585	7.9902	61.680728	236.2147	1.0	0.99761
12	7.9985631	7.996	140.576965	251.6407	0.9962466	0.99619

shows the results obtained by using our system and RC4 algorithm. Most of the entropy values are close to 8 and this means that, even if the previous symbols are known, it is still impossible to predict the next character in the sequence. However, the entropy decreases if the number of bytes to be encrypted is small. The avalanche values obtained were greater than 0.5, which indicates that the output has drastic changes when the input is slightly changed. Finally, the execution time is high when there is an extensive input file or a big amount of evolution times of the CA.

Decrypt

As a consequence of encrypting, we obtain a key file and an encrypted file. However, if we want to decrypt, it is necessary to solve the authentication process, and subsequently, with the key and the encrypted file, we can obtain the plain text. In Figure 6, a decrypt diagram is shown.

5. Discussion

In this paper, a security system with good cryptographic properties because of the tools used was developed. The amount of computer time it takes to run this algorithm is $O\left(m^{2}n\right)$; this makes it computationally efficient. It has a high-security level because the authentication problems are NP-complete (in this case, graph 3 coloring); it is, we can verify the solution in polynomial time, while for finding a solution an exponential time is necessary.

All the algorithms are linked; if an eavesdropper wanted to obtain the plain text, they would need to have the ciphertext, the key, and pass the zero-knowledge proof. Moreover, they would need to know the evolution rules and the number of times that the cellular automata evolve; for this reason, the algorithm is better than some stream algorithms [34,35,36].

Some applications for this work can be as a captcha; in another case, it can be used when someone forgets their password and the person needs to prove that whoever is not an impostor. In addition, if we wanted to send a private message, we only cipher the text, and a correct entity could obtain the decrypted text; also, it can be a secure channel for sharing information.

The algorithm works for any file because conversion to byte-map is performed. In the encryption process, the header file is also modified to the cipher file which does not exhibit information about the plain file; should we want to decrypt it, it is also necessary to solve the authentication process, and subsequently, with the key and the encrypted file, we can obtain the plain text.

6. Conclusions

In this paper, a novel framework was presented, in which the key to solving an NP-complete problem is obtained; this provides not only authentication but also confidentiality in security services. Another point is that, as shown in Table 1, the framework encrypts different types of files, unlike in [13,37], but similarly, it works with cellular automata. Moreover, the encryption time depends on the file size; in comparison with, [38] is faster and has better avalanche achieved percentages (Table 2), so it is better because of the efficiency of the diffusion mechanism. In other words, the encryption algorithm possesses good diffusion characteristics. In the future, this concept may be extended to introduce other services such as integrity and non-repudiation to build a complete network security software service that helps provide absolute security for data transmission.

Compared to the RC4 algorithm (Table 2), we obtained better results in avalanche values; i.e., diffusion efficiency is better. The proposed system has better results in chi-square values when the file size is small because the bytes are more uniformly distributed by the CA. The advantage of this framework is that the user must authenticate with a secret, and the key is dynamically created for all files. If someone obtains the key of a previous cipher file, they will only be able to decrypt the file if they pass the authentication test, and the key will only work for that file. Entities that want to encrypt/decrypt similar files must know the secret in order to be authenticated. In the case that multiple entities are required to be present to perform the encryption process, the secret can be shared; each user has a part necessary to do this.