Enhancing block cipher security with key-dependent random XOR tables generated via hadamard matrices and Sudoku game

Abstract

The XOR operator is a simple yet crucial computation in computer science, especially in cryptography. In symmetric cryptographic schemes, particularly in block ciphers, the AddRoundKey transformation is commonly used to XOR an internal state with a round key. One method to enhance the security of block ciphers is to diversify this transformation. In this paper, we propose some straightforward yet highly effective techniques for generating t-bit random XOR tables. One approach is based on the Hadamard matrix, while another draws inspiration from the popular intellectual game Sudoku. Additionally, we introduce algorithms to animate the XOR transformation for generalized block ciphers. Specifically, we apply our findings to the AES encryption standard to present the key-dependent AES algorithm. Furthermore, we conduct a security analysis and assess the randomness of the proposed key-dependent AES algorithm using NIST SP 800-22, Shannon entropy based on the ENT tool, and min-entropy based on NIST SP 800-90B. Thanks to the key-dependent random XOR tables, the key-dependent AES algorithm have become much more secure than AES, and they also achieve better results in some statistical standards than AES.

Keywords

Random XOR table AES key-dependent block cipher randomness Shannon entropy

1 Introduction

Block ciphers are among the most widely used primitive ciphers in various fields today. Recently, dynamic block ciphers have garnered significant attention from cryptographers due to their potential to enhance the robustness of block ciphers against cryptographic attacks. The distinctive feature of dynamic block ciphers is that they alter the data encryption process based on changes in a predefined factor. This significantly complicates the task of cryptanalysts when attempting to carry out attacks compared to attacking static block ciphers. Currently, there are several approaches to dynamic block ciphers, such as key-dependent, time-dependent, data-dependent, and so on. The basic components of a block cipher typically include substitution boxes (S-boxes) [4 , 31], MDS matrices [23 , 33], and key addition operations.

Regarding the approach of making block ciphers dynamic based on the key, researchers continue to propose a variety of methods to make a component within the block cipher dynamically change depending on a pre-defined secret key. For example, in [2 , 31], authors made block ciphers dynamic by generating new S-boxes depending on the key. In [3 , 36], block ciphers are made dynamic based on key-dependent MDS matrices. In [1 , 38], the authors combined multiple transformations within block ciphers to be dynamic, including S-boxes, MDS matrices, and ShiftRow transformations in AES [17, 18].

Specifically, with the dynamic S-box approach, in [9, 10], the authors made Twofish and Blowfish block ciphers dynamic by utilizing four key-dependent S-boxes. Blowfish [9] is a 64-bit block size cipher with a variable key length. The algorithm consists of two parts: key expansion and data encryption. The data encryption process employs a 16-round Feistel network. Each round includes a key-dependent permutation, a key-dependent substitution, and data mixing through dynamic S-boxes. Twofish [10] is a 16-round Feistel block cipher with a bijective F function. Twofish utilizes four 8 × 8 S-boxes that depend on the key, with distinct bijections. These S-boxes are constructed using two fixed 8 × 8 permutations and key-dependent components.

In [2], the authors presented a technique for producing key-dependent S-boxes through a dynamic strategy. They empirically assessed the key-dependent S-box, considering characteristics such as output balance, bits independence criterion (BIC), the strict avalanche criterion (SAC), non-linearity, and probabilities of differential and linear approximations. The authors in [4] introduced a novel encryption approach for images, utilizing AES and incorporating a flexible S-box. The plain image undergoes segmentation into uniform-sized blocks (128 bits each). Subsequently, each block undergoes encryption using AES, where the requisite S-box is dynamically generated through a hyperchaotic system. This implies that each block is encrypted utilizing a distinct S-box for AES. The sequence values are then arranged in ascending order, forming a sequence identified as the S-box for the AES algorithm. The final value in the preceding sequence serves as the foundation for constructing the S-box for the subsequent block, also serving as the original condition for the hyperchaotic system. In [7], the authors demonstrated the Field Programmable Gate Array (FPGA) realization of a True Random Number Generator (TRNG) that leverages dynamic key-dependent s-box architecture for processing. The suggested architecture for TRNG processing uses four autonomous 8-bit s-boxes. In [8], the authors presented an approach for creating key-dependent nxn S-boxes, influenced by an original S-box, with consistent algebraic attributes such as nonlinearity, SAC, bijection, and BIC. The technique relies on a symmetric group and its subgroup, employing group actions on Boolean functions of the S-box, affecting both columns and rows. Through the permutation of rows, the innovative approach allows the creation of 8! copies for every column arrangement. The primary innovation in [13] involves devising a method for constructing a cryptographically secured S-Box, utilizing a non-degenerate 3D map. Initially, a 3D map is formulated, and dynamic analysis showcases its ergodicity and heightened randomness within the phase space. Leveraging the 3D map, a method for constructing a dynamically secured robust S-Box is devised, fulfilling six criteria without encountering reverse fixed points, fixed points, short cycles. The security analysis and empirical statistics validate the algorithm’s security and efficacy. Furthermore, key-dependent S-boxes gained attention in block cipher design during Twofish’s candidacy as an AES finalist. The authors in [31] introduced insights into the cryptanalyst’s approach to working with key-dependent S-boxes, initiates the construction of a structure for the differential cryptanalysis of such S-boxes, and introduces fundamental techniques applied in the analysis of a limited-round Twofish variant.

In the case of dynamically constructing MDS matrices, in [3] the authors introduced an approach to enhance the AES block cipher by incorporating a new MixColumn operation. This novel MixColumn operation employs dynamic MDS matrices derived from key and DNA operations. The authors assessed the security of this updated MixColumn and subjected it to NIST tests to assess its randomness. In [15], the authors established six distinct adaptable binary diffusion models, four of which are reversible and two that are non-reversible. They proposed a binary multiplication method that utilizes a dynamic base matrix and its transpose, achieving the desired efficiency while also maintaining strong defense against modern attacks, all without compromising performance. In [27], the authors introduced a group of binary matrices of size n × n that meet various criteria, enabling the dynamic transformation of cyclic matrices and certain recursive MDS matrices with reduced software overhead. Leveraging the introduced matrix family facilitates the dynamic transformation of established diffusion layers, such as and recursive MDS diffusion layers and cyclic AES-like matrices, with minimal additional computational overhead. Consequently, this offers novel sets of MDS matrices suitable for deployment as dynamic diffusion layers, utilizing the provided matrix family. In [36], the author introduced an approach for the linear layer of substitution-permutation network (SPN) block ciphers, leveraging self-reciprocal recursive matrices with involution properties. This algorithm is capable of producing involutory matrices with multiplicative differential uniformity, enhancing their practicality in execution. They augmented the AES block cipher by integrating dynamic Mix-column transformations through devised algorithm. Additionally, they conducted a security analysis, evaluate conformity to NIST statistical standards, and measure the computational speed of the enhanced dynamic AES block cipher. The proposed algorithm demonstrates promise in fortifying the security aspects of the AES algorithm.

With the approach of combining multiple transformations dynamically in block ciphers, in [1] the authors presented an innovative key-dependent block cipher known as P-AES, which involves altering the parameters in AES for each key. To be more precise, the MixColumn, ShiftRow, and SubByte operations are adjusted according to the secret key, leading to distinct operations for each unique key. It has been demonstrated that the P-AES cipher is resistant to both linear and differential attacks. The authors in [32] introduced a conceptual framework aimed at fortifying the AES algorithm. It modifies the AES ShiftRow operation by incorporating key-dependent elements. The integration of key dependency contributes to heightened algorithmic security, with empirical findings revealing the dispersion of statistical patterns from plaintext to ciphertext. This, in turn, fortifies the plaintext against cryptanalysis. Experimental outcomes illustrate an increase in the dispersion ratio from 0.75 for AES to approximately 1 for the proposed model. Additionally, the model undergoes scrutiny using the coefficient of variation metric. In [34], an Internet data security solution using a modified AES cipher dependent on a key is presented. This cipher exhibits improved SAC and avalanche effects compared to the original AES cipher. The researchers in [37] asserted that AES was initially formulated without accounting for execution within the context of a white-box attack. Due to the fixed nature of confusion and diffusion operations, the white-box version of AES is susceptible to compromise. Consequently, they introduced an AES-like cipher by substituting AES’s S-boxes and MixColumn matrices with key-dependent elements, while preserving their favorable cryptographic attributes. Their findings demonstrate that the white-box implementation of our AES-like cipher can withstand current known attack methodologies. The authors in [38] introduced a Python-based symmetric data encryption technique designed for image encryption to ensure secure transmission. The primary computational procedures involved in this algorithm include Mix Columns, a key-dependent exclusive OR operation incorporating upper and lower triangular segments of the matrix, Shift Rows, and a tailored Sub Bytes transformation, contributing to diffusion and confusion. Outcomes from diverse analyses conducted on the algorithm substantiate its genuineness, confidentiality, and integrity.

In [16], the authors presented a novel approach involving a variable s-box that undergoes continual alterations independently of the encryption key. The updated s-box relies on the epoch timestamp inherent in every digital system and transmitted through digital satellite communication systems. The creation of the non-linear s-box is consistent in both the transmitter and receiver. The key advantage of this proposed method lies in the variability of the ciphertext while maintaining a constant encryption key, ensuring diverse encryption outcomes for identical data. The study also explores and assesses the efficacy and quality of the updated s-box using the avalanche effect method. In [30], the RC6 block cipher employs a data-dependent rotation operation. RC6 utilizes an additional multiplication operation to make the rotation operation dependent on each bit within a word, rather than just a few least significant bits. The enhanced characteristics of RC6 encompass the utilization of four operational registers in lieu of two, along with the integration of integer multiplication as an extra fundamental operation. The incorporation of multiplication significantly amplifies the dispersion achieved in each round, resulting in heightened security, reduced round requirements, and enhanced throughput.

Another method we want to highlight in this paper is the key-dependent XOR operation method. In [5, 6], Salih et al. proposed some key-dependent XOR tables based on Chaotic 3D mappings. The fixed XOR operation in the rounds of AES is replaced by a new dynamic XOR table. In [5], the authors used a separate XOR table, while in [6], the authors alternately used two XOR tables. Additionally, [6] employed a dynamic MixColumns transformation, in which a separate dynamic MDS matrix is used with a 3D affine mapping. However, there is a lack of comprehensive security assessments, and the evaluation of randomness based on NIST statistical standards is not entirely accurate. The dynamic MDS matrix proposed in [6] is not an MDS matrix. In general, there are still many flaws in these two papers.

Our contribution. In this paper, we propose several efficient methods to generate t-bit random XOR tables. Specifically, we propose a method to generate a random XOR table based on the Hadamard matrix and a method based on the famous intellectual game Sudoku. In addition, we propose key-dependent block cipher algorithms based on our random XOR table generation methods. Key-dependent random XOR tables will greatly enhance the security of the block ciphers. We choose the AES block cipher as a specific instance to apply our proposed algorithms. We conduct a comprehensive security analysis of the key-dependent AES block cipher. To assess the randomness of the proposed dynamic AES block cipher round by round, we employ a set of tools, including NIST SP 800-22 [21], ENT [20], and NIST SP 800-90B [28]. Due to the utilization of key-dependent random XOR tables, the security of proposed key-dependent AES block cipher has been significantly enhanced compared to AES, and they also outperform AES in certain statistical benchmarks. Our results are highly significant in proposing new dynamic methods for AES based on random XOR tables, contributing to the enhancement of AES security.

The rest of the article is organized as follows. Section 3 presents various methods for generating random XOR tables and dynamic block cipher algorithms based on these tables. In Section 4, we apply our proposed dynamic algorithms using random XOR tables to AES, subsequently conducting security analysis and assessing randomness with NIST SP 800-22 [21], ENT [20], and NIST SP 800-90B [28]. Lastly, Section 5 contains the conclusion.

2 Preliminaries

2.1 Advanced Encryption Standard (AES)

AES operates based on a secret key, and the length of this key can be either 128 bits, 192 bits, or 256 bits, depending on the desired level of security. AES is an SPN block cipher with three transformations: key addition, substitution, and permutation. The key addition in AES involves XOR-ing a round key with an input state array. The XOR operation in key addition is a standard bitwise XOR. Figure 1 illustrates the XOR table used in AES.

Fig. 1

The XOR table used in AES.

Through the original XOR table of AES, we observe the properties that a 4-bit XOR table must satisfy, including the following attributes:

Each column and row of the XOR table consists of distinct numbers ranging from 0 to 15.

The XOR table must be symmetrical across the main diagonal, meaning: u XOR v = v XOR u.

For any elements u, v, t in the XOR table satisfying u XOR v = t, it is always true that u XOR t = v, and v XOR t = u.

2.2 Hadamard matrices

A Hadamard matrix is defined in [29] as follows.

Definition 1 [29]. A matrix A of size 2^d × 2^d is a Hadamard matrix over the finite field $F_{2^{s}}$ if it can be represented as follows: $A = [\begin{matrix} X & Y \\ Y & X \end{matrix}]$ where the two submatrices X and Y are matrices over $F_{2^{s}}$ .

A Hadamard matrix of size n with elements of the first row being a₀, a₁, …, a_n-1 will be denoted as follows. $H = had (a_{0}, a_{1}, \dots, a_{n - 1})$ (1)

2.3 Sudoku game

Sudoku [35], also referred to as Su Doku, is a widely popular number-based puzzle game. In its simplest and most common form, Sudoku consists of a 9 × 9 grid with numbers already filled in some of the squares. The objective of the puzzle is to complete the remaining squares by using each of the numbers 1 through 9 exactly once in every row, column, and within the nine 3 × 3 subgrids. Sudoku relies solely on logic, devoid of any arithmetic calculations, and the puzzle’s level of difficulty depends on the quantity and placement of the initially provided numbers. Interestingly, Sudoku has presented intriguing combinatorial challenges to mathematicians. In 2005, two mathematicians demonstrated that there are approximately 6.670 × 10²¹ possible Sudoku 9 × 9 grids.

These two strategies alone are often insufficient to entirely complete a Sudoku grid. Progress typically necessitates more intricate analytical techniques, and occasionally, one must resort to making educated guesses, reversing them if conflicts arise. One advanced strategy involves examining pairs or triples of cells within a row, column, or block. It’s possible to encounter a pair of cells with only two possible entries, yet their specific placements remain uncertain. However, this observation yields valuable information: those pair of numbers cannot exist elsewhere in the vicinity. Consequently, this reduces the number of potential entries for the other cells nearby, facilitating closer proximity to a solution. In a similar vein, a set of three cells with only three possible entry options among them serves to exclude those entries from all other cells within the corresponding neighborhood.

2.4 NIST SP 800-22 test suite

NIST SP 800-22 [21] stands out as a pivotal and extensively utilized tool for evaluating the statistical randomness of random or pseudorandom number generators in the field of cryptography. NIST’s comprehensive suite of randomness tests encompasses 15 distinct assessments, including the Frequency (Monobit) Test, Runs Test, Frequency Test within a Block, Test for the Longest Run of Ones in a Block, Discrete Fourier Transform (Spectral) Test, Binary Matrix Rank Test, Non-overlapping Template Matching Test, Maurer’s “Universal Statistical” Test, Overlapping Template Matching Test, Linear Complexity Test, Serial Test, Cumulative Sums (Cusum) Test, Approximate Entropy Test, Random Excursions Test, and Random Excursions Variant Test.

For a given input sequence, each test computes a corresponding p-value and compares it against the significance level α = 0.01. If p_i ≥ α, the conclusion is drawn that the sequence is random; otherwise, if p_i < α, the sequence is deemed non-random.

2.5 Shannon entropy and min-entropy

Entropy [11], or information entropy, quantifies the uncertainty in a person’s knowledge or an experiment’s output before observation, along with the associated deterministic behavior in predicting its value. Higher entropy signifies increased uncertainty in predicting observation values. Shannon entropy, introduced by Shannon in [11], is a specific measure of information entropy.

Definition 2 [11]. Consider a discrete random variable X that takes values from a finite set S. In this context, the entropy of the random variable X is formally defined as follows. $H (X) = - \sum_{x \in S} Pr [x] {log}_{2} \Pr [x]$

Shannon entropy gives the average entropy measure for a given distribution of random variables.

In 1961, R $\overset{´}{e}$ nyi [22] introduced a more general formulation for entropy, known as R $\overset{´}{e}$ nyi entropy. R $\overset{´}{e}$ nyi’s concept involves replacing the traditional entropy function with a more versatile function by introducing a parameter α. R $\overset{´}{e}$ nyi entropy of order α, with α ≥ 0, α ≠ 1, is defined as follows.

Definition 3 [22]. Consider a discrete random variable X that takes values from a finite set S ={ x₁, x₂, ⋯ , x_n } with corresponding probabilities p_i = Pr [X = x_i] for i = 1, ⋯ , n. In this context, the R $\overset{´}{e}$ nyi entropy of order α for X, where α ≥ 0, α ≠ 1, is formally defined as follows: $H^{(α)} (X) = \frac{1}{1 - α} {log}_{2} (\sum_{i = 1}^{n} p_{i}^{α}) .$

When α→ ∞ we have an important quantity called min-entropy.

In cryptography, the unpredictability of secret values is crucial. The likelihood of correctly predicting a secret value on the first attempt is linked to the min-entropy of the distribution from which the secret value is generated. Consequently, min-entropy stands out as one of the paramount metrics in cryptography.

Definition 4 [28]. Consider a discrete random variable X, taking values from a finite set S ={ x₁, x₂, ⋯ , x_n } with corresponding probabilities p_i = Pr [X = x_i] for i = 1, ⋯ , n. In this context, the formal definition of the min-entropy of X is as follows. $H^{(\infty)} (X) = min_{1 \leq i \leq n} (- {log}_{2} p_{i}) .$

3 Generating random XOR tables using hadamard matrices and Sudoku game

3.1 Random XOR tables based on hadamard matrices

In this section, we propose an algorithm to create a random XOR table based on the Hadamard matrix and an algorithm for creating a dynamic block cipher using a key-dependent random XOR table derived from the Hadamard matrix.

From the Definition 1, we denote the Hadamard matrix with 2ⁿ elements a₁, a₂, ⋯ , a_2ⁿ as Had (a₁, a₂, ⋯ , a_2ⁿ), and it has the following form: $\begin{matrix} Had (a_{1}, a_{2}, \dots, a_{2^{n}}) = \\ [\begin{matrix} \begin{matrix} a_{1} & a_{2} \\ a_{2} & a_{1} \end{matrix} & \begin{matrix} a_{3} & \dots \\ a_{4} & \dots \end{matrix} & \begin{matrix} a_{2^{n} - 1} & a_{2^{n}} \\ a_{2^{n}} & a_{2^{n} - 1} \end{matrix} \\ \begin{matrix} a_{3} & a_{4} \\ ⋮ & ⋮ \end{matrix} & \begin{matrix} a_{1} & \dots \\ ⋮ & ⋮ \end{matrix} & \begin{matrix} a_{2^{n} - 3} & a_{2^{n} - 2} \\ ⋮ & ⋮ \end{matrix} \\ \begin{matrix} a_{2^{n} - 1} & a_{2^{n}} \\ a_{2^{n}} & a_{2^{n} - 1} \end{matrix} & \begin{matrix} a_{2^{n} - 3} & \dots \\ a_{2^{n} - 2} & \dots \end{matrix} & \begin{matrix} a_{1} & a_{2} \\ a_{2} & a_{1} \end{matrix} \end{matrix}] \end{matrix}$ (2)

First, we demonstrate an XOR table based on Hadamard matrix that satisfies the conditions of an XOR table through the following proposition.

Proposition 1. Let n be a positive integer and a permutation of 2ⁿ elements from 0 to 2ⁿ - 1, denoted by (a₁, a₂, ⋯ , a_2ⁿ ). A table A is constructed by adding a row to the top and a column to the left of the matrix Had (a₁, a₂, ⋯ , a_2ⁿ) as shown below:

	a ₁	a ₃	a ₃	…	a _2ⁿ-1	a _2ⁿ
a ₁	a ₁	a ₂	a ₃		a _2ⁿ-1	a _2ⁿ
a ₂	a ₂	a ₁	a ₄		a _2ⁿ	a _2ⁿ-1
a ₃	a ₃	a ₄	a ₁
				⋱	a ₄	a ₃
a _2ⁿ-1	a _2ⁿ-1	a _2ⁿ	a ₄	a ₁	a ₂
a _2ⁿ	a _2ⁿ	a _2ⁿ-1	a ₃	a ₂	a ₁

Then, A is an XOR table of n-bit values.

Proof. According to the construction, let the bold elements in table A be the input values, the non-bold elements in column a_i and row a_j be the output values of XOR of a_i and a_j. Then, table A has the following properties: ${\begin{matrix} A_{ii} = a_{1}, \forall i, 1 \leq i \leq 2^{n} \\ A_{ij} = A_{ji}, \forall i, j \\ A_{ij} = a_{2^{n}}, \forall i, j, i + j = 2^{n} - 1 . \end{matrix}$

To prove that table A is an XOR table, we need to show that for any two elements a_i, a_j, we have: ${\begin{matrix} a_{i} XOR a_{j} = a_{j} XOR a_{i}, \\ a_{i} XOR a_{j} = a_{k} \to a_{i} XOR a_{k} = a_{j}, a_{j} XOR a_{k} = a_{i} . \end{matrix}$

By the property A_ij = A_ji, ∀ i, j, we get a_iXORa_j = a_jXORa_i, ∀ i, j.

From the property A_ii = a₁, ∀ i, 1 ≤ i ≤ 2ⁿ, we have a_iXORa_i = a₁ → a₁XORa_i = a_i. So the first column and first row of the Hadamard matrix satisfy the properties of XOR operation.

Note that according to the construction, row (resp. column) a _2^k, values are constructed by interchanging the values a_2t-1, a_2t of row (resp. column) a _2^k-1 for 1 ≤ t ≤ 2^n-1. Row a _2^k+1, values are constructed by swapping consecutive sets of 2^k values of row a ₁ with 1 ≤ t ≤ 2^n-k-1.

Row (resp. column) a ₂, values are constructed by exchanging the values a_2t-1, a_2t of row (resp. column) a ₁ for 1 ≤ t ≤ 2^n-1. Then, the value in column a _2t (which is the value a ₂ XOR a _2t) will be a_2t-1 and the value in column a _2t-1 (which is the value a ₂ XOR a_2t-1) will be a_2t. We need to check whether a _2t-1 XOR a _2t is equal to a₂ or not. This is true because we have matrix blocks $(\begin{matrix} a_{1} & a_{2} \\ a_{2} & a_{1} \end{matrix})$ lies on the main diagonal of the Hadamard matrix. It corresponds to the equality a _2t-1 XOR a _2t = a _2t XOR a _2t-1 = a₂. Therefore, the values located in row (resp. column) a ₂ satisfy the properties of XOR operation. Dually, the values located in row (resp. column) a _2ⁿ-1 also satisfy the property of XOR operation.

Row (resp. column) a ₃, values are constructed by swapping the tuples (a_4t-3, a_4t-2) with (a_4t-1, a_4t) of row (resp. column) a ₁ with 1 ≤ t ≤ 2^n-2. hen, the value in columns a _4t-3 (that is a ₃ XOR a _4t-3), a _4t-2 (that is a ₃ XOR a _4t-2), a _4t-1 (that is a ₃ XOR a _4t-1), a _4t (that is a ₃ XOR a _4t) will be a_4t-1, a_4t, a_4t-3, a_4t-2. Then we have the following equations: ${\begin{matrix} a_{3} XOR a_{4 t - 3} = a_{4 t - 1} \\ a_{3} XOR a_{4 t - 2} = a_{4 t} \\ \begin{matrix} a_{3} XOR a_{4 t - 1} = a_{4 t - 3} \\ a_{3} XOR a_{4 t} = a_{4 t - 2} \end{matrix} \end{matrix}$

We need to check whether a _4t-1 XOR a _4t-3 and a _4t XOR a _4t-2 are equal to a₃ or not. This is true because we have matrix blocks $(\begin{matrix} \begin{matrix} a_{1} & a_{2} \\ a_{2} & a_{1} \end{matrix} & \begin{matrix} a_{3} & a_{4} \\ a_{4} & a_{3} \end{matrix} \\ \begin{matrix} a_{3} & a_{4} \\ a_{4} & a_{3} \end{matrix} & \begin{matrix} a_{1} & a_{2} \\ a_{2} & a_{1} \end{matrix} \end{matrix})$ lies on the main diagonal of the Hadamard matrix. It corresponds to the equality a _4t-3 XOR a _4t-1 = a _4t XOR a _4t-2 = a₃. herefore, the values located in row (resp. column) a ₃ satisfy the properties of XOR operation. Dually, the values located in the row (resp. column) a _2ⁿ-2 also satisfy the property of XOR operation.

Same argument for row (resp. column) a _2^k+1. Notice that it is constructed by interchanging tuples 2^k values (a_{2^k+1t-2^k+1+1}, ⋯ , a_2^k+1t-2^k) with (a_2^k+1t-2^k+1, ⋯ , a_2^k+1t) of row (resp. column) a ₁ with 1 ≤ t ≤ 2^n-k-1 Similar argument, using matrix (2^k + 1) × (2^k + 1) we have the proof.■

Please note that for convenience, we refer to the leftmost row and the topmost row of the XOR table as row 0 and column 0 of the XOR table, respectively.

From the above results, we propose an algorithm to generate a general random XOR table for t (t ≥ 2) bits as follows:

Algorithm 1. Generating a random t-bit XOR table based on the Hadamard matrix

Input: A random number generator G and a random seed (if necessary).

Output: A random XOR table.

Step 1. Randomly generate a sequence of 2^t distinct elements with values from 0 to 2^t - 1 by the random number generator G, denoted as (a₁, a₂, ⋯ , a_2^t).

Step 2. Create the matrix Had (a₁, a₂, ⋯ , a_2^t). Create the XOR table according to Proposition 1 with the matrix Had (a₁, a₂, ⋯ , a_2^t).

Step 3. Rearrange the rows and columns of the XOR table in step 2 so that row 0 and column 0 of the XOR table are arranged in ascending order from 0 to 2^t.

From Algorithm 1, it can be seen that the number of random XOR tables based on the Hadamard matrix is all XOR tables with the properties of elements on the main diagonal being equal, this number is greater than or equal to 16.

Example 1. To generate a 4-bit random XOR table, we randomly generate a sequence of 16 distinct elements by a random number generator, for example: $\begin{matrix} P = {3, 0, 2, 9, 14, 5, 1, 7, 10, 4, 12, 11, \\ 8, 13, 6, 15} . \end{matrix}$ From this, a new random XOR table is obtained based on the Hadamard matrix $\begin{matrix} Had (3, 0, 2, 9, 14, 5, 1, 7, 10, 4, 12, 11, \\ 8, 13, 6, 15) . \end{matrix}$

The new XOR table is shown in Table 1.

Table 1

A new random XOR table based on Hadamard matrix

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	3	7	9	0	10	14	15	1	13	2	4	12	11	8	5	6
1	7	3	14	1	15	9	10	0	12	5	6	13	8	11	2	4
2	9	14	3	2	11	7	8	5	6	0	12	4	10	15	1	13
3	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
4	10	15	11	4	3	8	7	6	5	12	0	2	9	14	13	1
5	14	9	7	5	8	3	11	2	4	1	13	6	15	10	0	12
6	15	10	8	6	7	11	3	4	2	13	1	5	14	9	12	0
7	1	0	5	7	6	2	4	3	11	14	15	8	13	12	9	10
8	13	12	6	8	5	4	2	11	3	15	14	7	1	0	10	9
9	2	5	0	9	12	1	13	14	15	3	11	10	4	6	7	8
10	4	6	12	10	0	13	1	15	14	11	3	9	2	5	8	7
11	12	13	4	11	2	6	5	8	7	10	9	3	0	1	15	14
12	11	8	10	12	9	15	14	13	1	4	2	0	3	7	6	5
13	8	11	15	13	14	10	9	12	0	6	5	1	7	3	4	2
14	5	2	1	14	13	0	12	9	10	7	8	15	6	4	3	11
15	6	4	13	15	1	12	0	10	9	8	7	14	5	2	11	3

From Algorithm 1, we propose a general algorithm for creating a dynamic block cipher using a key-dependent random XOR table derived from the Hadamard matrix. Please note that in Algorithm 2, we generate a random XOR table, and this XOR table is dependent on a predefined secret key. Algorithm 2 is presented as follows.

Algorithm 2. Creating a dynamic block cipher using a key-dependent random XOR table derived from the Hadamard matrix.
Input: A block cipher E (n, k) where n is the block length and k is the key length. Block cipher E consists of a key addition transformation by a t-bits XOR table. A secret random key for block cipher E is K ∈ { 0, 1 } ^k.
Output: New dynamic block cipher algorithm E′ (n, k).
Step 1. Randomly generate a sequence of 2^t distinct elements with values from 0 to 2^t - 1 from secret random key K, denoted by (a₁, a₂, ⋯ , a_2^t).
Step 2. Create the matrix Had (a₁, a₂, ⋯ , a_2^t). Create the XOR table A by adding the sequence (a₁, a₂, ⋯ , a_2^t) to be the row 0 and column 0 of this table according to Proposition 1.
Step 3. Rearrange the rows and columns of the new XOR table in step 2 so that row 0 and column 0 of this XOR table are arranged in ascending order from 0 to 2^t.
Step 4. Replace the original XOR table of E (n, k) with the new XOR table, we obtain the key-dependent dynamic block cipher algorithm E′ (n, k).

A specific instance. Step 1 of algorithm 2 will be clarified for each specific block cipher. Below, we give a concrete representation of the AES-128 block cipher.

For AES-128 block cipher, its XOR table is a 4-bit table (Fig. 1). Then we have a key-dependent dynamic block cipher algorithm, denoted DAES-128 (where D stands for Dynamic), according to Algorithm 2 as follows. In the step 1, we create a window at the first 4 bits of the key K, assigning the integer value of those 4 bits to a₁. Perform a window shift to the right by 1 bit. If the integer value of the 4 bits in the window is different from a₁, then assign that value to a₂. If not, continue to shift the window to the right by 1 bit. Continue doing this until 16 distinct elements with values from 0 to 15 are obtained, denoted as (a₁, a₂, ⋯ , a₁₆). The remaining steps are performed as in Algorithm 2. Finally, we obtain the key-dependent dynamic block cipher algorithm DAES-128.

Remark 1. The elements on the main diagonal of the random XOR table generated by Algorithm 1 are equal.

Remark 2. The sequence (a₁, a₂, ⋯ , a₁₆) generated by step 1 above with a random key will be generated with probability approximately 1. We will prove this in Proposition 2 below.

Let (a₁, a₂, ⋯ , a_s) be a sequence of s integers, where 0 ≤ a_i ≤ 2^k - 1 for 1 ≤ i ≤ s, and denote the number of distinct integers in the sequence (a₁, a₂, ⋯ , a_s) as the seed of the sequence, denoted as seed.

Proposition 2. Let (a₁, a₂, ⋯ , a_s) be a sequence of s integers, where 0 ≤ a_i ≤ 2^k - 1 vói 1 ≤ i ≤ s, and seed is the number of distinct integers in the sequence (a₁, a₂, ⋯ , a_s). Then, $Pr (seed = t) = \frac{2^{k} (2^{k} - 1) \dots (2^{k} - (t - 1))}{2^{ks}} {\begin{matrix} s \\ t \end{matrix}},$ $Pr (seed \leq t) = \sum_{i = 1}^{t} \frac{2^{k} (2^{k} - 1) \dots (2^{k} - (i - 1))}{2^{ks}} {\begin{matrix} s \\ i \end{matrix}},$ where ${\begin{matrix} s \\ i \end{matrix}}$ is the Stirling number of the second kind, which represents the number of different ways to partition a set of s elements into i non-empty subsets.

Proof. Let c_j be the jth distinct number that appears in the sequence (a₁, a₂, ⋯ , a_s), and let C_j be the set of indices corresponding to c_j. For example, if the sequence of integers is {8, 3, 8, 3, 8, 5, 3} then c₁ = 8, c₂ = 3, c₃ = 5 and C₁ ={ 1, 3, 5 } , C₂ = { 2, 4, 7 } , C₃ = { 6 }. Since the seed is t we need to consider t non-empty subsets of the set {1, 2, ⋯ , s }. The number of such arrangements (permutations) is given by ${\begin{matrix} s \\ i \end{matrix}}$ . Furthermore, we have 2^k - j + 1 ways to choose c_j for 1 ≤ j ≤ t. Therefore, the total number of possible arrangements $2^{k} (2^{k} - 1) \dots (2^{k} - (t - 1)) {\begin{matrix} s \\ t \end{matrix}}$ . To find Pr(seed = t) we need to divide this number by all possible cases, which is (2^k) ^s leading to the result that needs to be proven.■

For a key with a length of 128 bits, reading 4 bits in turn and shifting one bit at a time, we obtain a sequence of 125 integers with values ranging from 0 to 15. Then, let t be the number of distinct integers in the sequence, we have the following probability table:

So, the probability of obtaining 16 distinct elements with values from 0 to 15, denoted as (a₁, a₂, ⋯ , a₁₆) from a random key is 0.994989. More precisely, to obtain the sequence (a₁, a₂, ⋯ , a₁₆) we only need to obtain 15 distinct elements with values from 0 to 15, and then the remaining value is added to the sequence to make it 16 distinct elements. Therefore, the probability is 0.994989 + 0.00500447 = 0.99999347 ≈ 1.

Table 2

The probability of having t distinct integers in a sequence of 125 elements

t	Pr(Cov = t)	t	Pr(Cov = t)
1	4.8879×10^-150	9	6.66408×10^-28
2	1.55931×10^-111	10	2.44635×10^-22
3	7.47045×10^-89	11	1.99223×10^-17
4	1.00594×10^-72	12	4.39168×10^-13
5	3.13715×10^-60	13	2.99126×10^-9
6	4.54394×10^-50	14	6.75478×10^-6
7	1.51594×10^-41	15	0.00500447
8	3.02572×10^-34	16	0.994989
		≥17	0

3.2 Random XOR tables inspired by the Sudoku game

In this section, we propose a random XOR table generation algorithm that is more powerful than Algorithm 1 in the sense that it can generate all XOR tables for t bits. Our method is inspired by a famous intellectual game, Sudoku [35].

Fig. 2

All 2-bit XOR tables.

From Remark 1, we see that although Algorithm 1 creates a random XOR table, the resulting XOR tables have the special property that all elements on the main diagonal are equal. Therefore, the total number of randomly generated XOR tables based on the Hadamard matrix is restricted. In contrast, the randomly generated XOR tables inspired by Sudoku games are random and do not possess any specific properties like the previous method.

For 2-bit XOR tables, we can observe that only 4 out of 16 tables that have elements on the main diagonal equal to each other. Therefore, if we generate XOR tables randomly using Algorithm 1, we will only obtain 4 different 2-bit XOR tables. This number of XOR tables is relatively small compared to the total possible number (16 tables) of 2-bit XOR tables. To overcome this issue, we propose a method for generating random XOR tables inspired by the Sudoku game that can generate the maximum possible number of XOR tables

Firstly, we observe that each element in an XOR table appears exactly once in each row or column, similar to the rules of a Sudoku table. However, in Sudoku, each element also appears only once within a smaller square known as a “block”, which is a feature not present in XOR tables. Next, we propose a random XOR table generation algorithm inspired by the Sudoku game. Please note that, for the XOR table, we do not consider the condition that each element appears only once in blocks. Here, we rely on the Backtracking method to solve an XOR-Sudoku table.

Algorithm 3. Generating a random XOR table based on the Sudoku game.
Input: A random number generator G and a positive integer t.
Output: A new random XOR table A based on the Sudoku game.
Step 1. Create an empty table A of 2^t × 2^t.
Step 2. Randomly generate a sequence of 2^t different elements with values from 0 to 2^t - 1 by the random number generator, denoted as (a₁, a₂, ⋯ , a_2^t), satisfies the XOR property with element 0.
Step 3. Assign those elements to the first row of table A.
Step 4. Forj = 0 to 2^t - 1 do:
If (A [0] [j] = k) then:
A [k] [j] = 0;
A [j] [k] = 0 ;
A [j] [0] = k ;
A [k] [0] = j ;
Endif
Endfor
Step 5. Solve XOR-Sudoku Table A by using Backtracking method without block checking condition.
Step 6. If (CheckXOR (A) = = true) returnA as a new XOR Table.
Else return Step 2.
Endif

The number of random XOR tables generated by Algorithm 3 will be much larger than that by Algorithm 1 with large t. In theory, Algorithm 3 can generate all possible XOR tables. Step 6 in the algorithm ensures that the new XOR table satisfies the necessary properties of an XOR table.

Remark 3. We can randomly generate elements for the ith row of A that satisfy the XOR property with element i, but with t ≥ 4 bits of probability to produce a very random XOR table. low because randomly selecting elements for the whole table A will lead to breaking the XOR condition. Based on empirical experience, we recommend only creating random XOR-Sudoku tables with rows ≤2^t/2 with t-bit XOR tables and using the Sudoku solving algorithm (without checking the condition in the block) for that table.

Practical experiments. We choose t = 4 bits, and run Algorithm 3 using C++rand () function to generate random numbers on Asus K43SJ Laptop (Core i5-2430M, 6GB RAM, 500GB HDD, Nvidia Geforce GT 520M. Record the number of iterations and time to generate 10 random XOR tables as shown in Table 3.

Table 3

Number of iterations and run time for generating 10 XOR Random Table using Algorithm 3

No.	No. of iterations	Time (seconds)
1	43446	4.859
2	1	0
3	90982	8.341
4	44367	4.554
5	412398	42.391
6	21741	2.015
7	40236	3.923
8	1	0
9	77258	7.881
10	27798	2.801
Average	75823	7.6765

We propose a more general random XOR table generation algorithm of Algorithm 3 as follows:

Algorithm 4 (Generalized). Generating a random XOR table based on Sudoku game.
Input: A random number generator G. A positive integer t and a positive integer r < 2^t/2.
Output: A new random XOR table based on the Sudoku game.
Step 1. Create an empty table A of size 2^t × 2^t.
Step 2. Randomly create an XOR-Sudoku table for r rows and r columns of A, satisfying the XOR property with elements 0, …, r - 1.
Step 3. Solve XOR-Sudoku Table A by using Backtracking method without block checking condition.
Step 4. If (CheckXOR (A) = = true) return A as a new XOR Table.
Else return Step 2.
Endif

Experiments. We choose t = 4 bits, and run algorithm 3 using C++rand () function to generate random numbers on Asus K43SJ Laptop (Core i5-2430M, 6GB RAM, 500GB HDD, Nvidia Geforce GT 520M. Record the number of iterations and time to generate 10 random XOR tables for r = 2, 3, 4 as shown in Table 4. Some random XOR tables will be presented in the Appendix.

Table 4

Number of iterations and run time for 10 XOR Random Table Generations using Algorithm 4 with r = 2, 3, 4

No.	r = 2		r = 3		r = 4
	No. of Iterations	Time (seconds)	No. of Iterations	Time (seconds)	No. of Iterations	Time (seconds)
1	128922	11.699	56246	5.427	613157	60.137
2	1	0	57778	6.399	726934	78.106
3	2434	0.171	277966	37.493	360891	39.215
4	107119	10.756	1	0	485216	53.532
5	477612	48.947	196186	18.015	631915	77.131
6	92774	8.347	83559	7.458	304163	35.789
7	78765	7.301	278841	21.717	46271	6.112
8	1	0	19758	1.83	97973	8.825
9	29816	2.5	323338	28.238	324930	34.794
10	105893	12.094	346416	33.069	782304	81.403
Average	102334	10.1815	164009	15.9646	437375	47.5044

From Algorithm 3, we propose an algorithm to animate the XOR operation for a general key-dependent block cipher as follows.

Algorithm 5. Algorithm to animate random XOR table for block cipher based on the Sudoku game.
Input: A block cipher E (n, k) where n is the block length and k is the key length. Block cipher E consists of a key addition transformation by a t-bits XOR table. A secret random key for block cipher E is K ∈ { 0, 1 } ^k.
Output: New dynamic block cipher E′ (n, k).
Step 1. Create an empty table A of size 2^t × 2^t.
Step 2. From the secret key K, read t bits of the key in turn to obtain a sequence of 2^t different elements with values from 0 to 2^t - 1, denoted as (a₁, a₂, ⋯ , a_2^t), satisfies the XOR property with 0.
Step 3. Assign those elements to the first row of table A.
Step 4. Forj = 0 to 2^t - 1 do:
If (A [0] [j] = k) then:
A [k] [j] = 0;
A [j] [k] = 0 ;
A [j] [0] = k ;
A [k] [0] = j ;
Endif
Endfor
Step 5. Solve XOR-Sudoku Table A without using block checking condition.
Step 6. If (CheckXOR (A) = = true) returnA as a new XOR Table.
Else return Step 2.
Endif
Step 7. Replace the original XOR table of block cipher E (n, k) with the new obtained XOR table, we obtain the key-dependent dynamic block cipher algorithm E′ (n, k).

4 Applying proposed dynamic algorithms with random XOR tables to AES

4.1 Instance and parameters

As discussed above, the Random XOR Table Generation Algorithm based on Sudoku game can generate all possible XOR tables. Therefore, we choose AES-128 block cipher as a specific instance, and 4-bit XOR table. Then we have a key-dependent dynamic block cipher algorithm, denoted SDAES-128 (where SD stands for Strong Dynamic), according to Algorithm 5 as follows:

Step 1. Create an empty table A of size 16 × 16, and an empty sequence (a₁, a₂, ⋯ , a₁₆).

Step 2. We create a window at the first 4 bits of the key K, assigning the integer value of those 4 bits to a₁ and a_{a
₁}=0. Perform a window shift to the right by 1 bit. If the integer value of the 4 bits in the window is different from a₁, then assign that value to a₂ and a_{a
₂} = 1 1. If not, continue to shift the window to the right by 1 bit. Continue doing this to obtain a sequence that satisfies the XOR property with 0, denoted as (a₁, a₂, ⋯ , a₁₆).

Step 3. Assign those elements to the first row of A.

Step 4. Forj = 0 to 15 do:

If (A [0] [j] = k) then:

A [k] [j] = 0;

A [j] [k] = 0 ;

A [j] [0] = k ;

A [k] [0] = j ;

Endif

Endfor

Step 5. Solve XOR-Sudoku Table A without using block checking condition.

Step 6. If (CheckXOR (A) = = true) returnA as a new XOR Table.

Else return Step 2.

Endif

Step 7. Replace the original XOR table of AES-128 with the new XOR table we obtain the key-dependent dynamic block cipher algorithm SDAES-128.

4.2 Security analysis

For block ciphers in general and AES in particular, the strongest attacks are differential attacks [14, 39], linear attacks [14, 26], or variations thereof. In particular, differential attacks require the assumption of specific differential trails to attack. Our SDAES block cipher makes the differential trails [15] change continuously and depends on the key, this helps the SDAES block cipher improve security because it is very difficult for an attacker to calculate the differential traces to apply attacks.

Furthermore, using randomly dependent XOR tables will complicate inference in key-related attacks [19] because the substituted XOR tables no longer exhibit the property that when two different inputs have the same difference, the output difference is equal to 0. Each relationship between input differences will continuously vary depending on the random key. This property of random XOR tables also enhances the security of block ciphers that employ them.

On the other hand, to execute linear and differential attacks, the attacker needs to gather an extremely large number of plaintext/ciphertext pairs before launching the attack. For example, with the AES block cipher, to successfully carry out a linear cryptanalysis using Matsui’s Algorithm 2 [26], approximately 2⁴⁷ pairs of plaintext/ciphertext are required. However, in the case of the SDAES block cipher, we employ dynamic XOR tables that depend on the key, making it challenging for the cryptanalysts to know which XOR table SDAES is actually using. This significantly increases the difficulty of cryptanalysis compared to AES. In AES, cryptanalysts have complete knowledge of every component within AES, including the XOR tables. Consequently, to conduct linear/differential attacks, the cryptanalysts must first predict which XOR table is being used in SDAES. Only then can they proceed to collect plaintext/ciphertext pairs for the attack. For instance, to successfully execute an attack on AES, it may require 2⁹⁰ pairs of plaintext/ciphertext, so they need to gather that many pairs if their initial prediction of the XOR table is incorrect. This process repeats until they can discover the key bits.

So, if the number of dynamic XOR tables using our method is assumed to be 2¹⁰⁰, the data complexity for a successful linear/differential attack against SDAES will become 2¹⁰⁰ × 2⁹⁰ = 2¹⁹⁰, which is significantly higher compared to the 2⁹⁰ for AES.

From the analyses above, it can be observed that the dynamic AES block cipher with proposed random key-dependent XOR tables has created a much more secure dynamic AES block cipher compared to the original AES against powerful block cipher attacks.

4.3 Randomness assessment

To evaluate the randomness for dynamic block cipher SDAES-128, we perform encryption of the some types of input datasets for each round and perform some evaluations based on NIST SP 800-22, Shannon entropy [11] based on ENT [20], and min-entropy [22] based on NIST SP 800-90B.

4.3.1 Evaluation results on 15 tests of NIST SP 800-22

We use 10⁶ plaintext of 128 bit that are integer numbers from 0 to 10⁶ - 1. So the corresponding output length is 128 × 10⁶. We encrypt plaintexts with random keys using AES and SDAES, and then evaluate the output data according to NIST SP 800-22. Parameters using in NIST Test suite are presented in Table 5.

Table 5
Parameters are used in NIST Test suite

No. Test-parameters Value

1 Block Frequency Test –block length (M) 128

2 NonOverlapping Template Test –block length (m) 9

3 Overlapping Template Test –block length (m) 9

4 Approximate Entropy Test–block length (m) 10

5 Serial Test–block length (m) 16

6 Linear Complexity Test–block length (M) 500

No.	Test-parameters	Value
1	Block Frequency Test –block length (M)	128
2	NonOverlapping Template Test –block length (m)	9
3	Overlapping Template Test –block length (m)	9
4	Approximate Entropy Test–block length (m)	10
5	Serial Test–block length (m)	16
6	Linear Complexity Test–block length (M)	500

The evaluation results are presented in the following Table 6.

Table 6

Results of 10-round SDAES-128 and Original AES-128 with random key

Test	SDAES-128		Original AES-128
	P_value	Result	P_value	Result
Freq	0.435011	Pass	0.604613	Pass
BlocFreq	0.159419	Pass	0.415025	Pass
CuSum1	0.611589	Pass	0.537509	Pass
CuSum2	0.621053	Pass	0.927344	Pass
Runs	0.246571	Pass	0.369725	Pass
LongestRun	0.594282	Pass	0.748478	Pass
Rank	0.383095	Pass	0.908691	Pass
DFT	0.803981	Pass	0.307167	Pass
Non OTM	147/148 p-values ≥0.01	Pass	147/148 p-values ≥0.01	Pass
OTM	0.314717	Pass	0.000320	FAIL
Universal	0.831845	Pass	0.674145	Pass
ApproxEntropy	0.200216	Pass	0.863909	Pass
RanExcursion	8/8 p-values ≥0.01	Pass	8/8 p-values ≥0.01	Pass
RanExcursion Variant	18/18 p-values ≥0.01	Pass	18/18 p-values ≥0.01	Pass
Serial1	0.923854	Pass	0.759251	Pass
Serial2	0.940345	Pass	0.412087	Pass
Linear Complexity	0.816783	Pass	0.002433	FAIL

The results in Table 6 indicate that, for the original AES block cipher, there are two tests, namely Linear Complexity and OTM, that detect the non-randomness of the data. However, all 15 tests do not detect any non-randomness in the data corresponding to the SDAES block cipher. Thus, it is evident that the SDAES block cipher meets higher randomness standards of NIST’s tests compared to the original AES.

4.3.2 Two-levels assessment according to NIST SP 800-22 using tests for short sequences

In [12], the study investigated NIST standards suitable for short lengths that can be applied to the evaluation of block ciphers and hash functions. The non-random input datasets used included Low Weight, High Weight, Rotation, and Avalanche 1 Bit datasets. The evaluation results for SDAES-128 with LW input data are presented in Table 7. The results for HW, AV1 and Rot input data are similar so we do not present them here due to space constraints.

Table 7
Level-2 p-values assessment results for the SDAES-128 based on tests for short sequences with LW input data

No. of Freq. Runs Test for longest Serial AppEn. CuSum. Bit AutoCorr. Byte Autocor.

rouns test test run of ones test test test test test

1 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

2 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

3 0.146697 0.747972 0.094292 0.352127 0.425631 0.974591 0.490418 0.540908

4 0.529922 0.753202 0.730386 0.268524 0.254571 0.515675 0.293178 0.852172

5 0.642365 0.429452 0.263789 0.307622 0.708592 0.584804 0.191283 0.669794

6 0.545215 0.660430 0.881279 0.131595 0.120719 0.289368 0.326414 0.318065

7 0.317082 0.392049 0.407817 0.204399 0.287632 0.891869 0.119197 0.401831

8 0.691319 0.539824 0.682353 0.617482 0.917960 0.376966 0.182995 0.105491

9 0.037333 0.569039 0.821652 0.303065 0.591749 0.136815 0.507946 0.510254

10 0.921057 0.766474 0.551779 0.815933 0.664040 0.964488 0.112014 0.209991

No. of	Freq.	Runs	Test for longest	Serial	AppEn.	CuSum.	Bit AutoCorr.	Byte Autocor.
1	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000
2	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000
3	0.146697	0.747972	0.094292	0.352127	0.425631	0.974591	0.490418	0.540908
4	0.529922	0.753202	0.730386	0.268524	0.254571	0.515675	0.293178	0.852172
5	0.642365	0.429452	0.263789	0.307622	0.708592	0.584804	0.191283	0.669794
6	0.545215	0.660430	0.881279	0.131595	0.120719	0.289368	0.326414	0.318065
7	0.317082	0.392049	0.407817	0.204399	0.287632	0.891869	0.119197	0.401831
8	0.691319	0.539824	0.682353	0.617482	0.917960	0.376966	0.182995	0.105491
9	0.037333	0.569039	0.821652	0.303065	0.591749	0.136815	0.507946	0.510254
10	0.921057	0.766474	0.551779	0.815933	0.664040	0.964488	0.112014	0.209991

The summary results indicate that the SDAES-128 block cipher exhibits randomness properties with a number of rounds greater than or equal to 3. This result is entirely consistent with the original AES-128.

4.3.3 Evaluate the Shannon entropy change using the ENT tool

One of the most important measures of randomness is Shannon entropy. In this section, we evaluate the Shannon entropy change of the four data sets LW, HW, AV1 and Rot through each round of the SDAES block cipher to more clearly see its round-wise randomness. Using the ENT tool, we evaluated the datasets and obtained the results as in Fig. 3.

Fig. 3

Shanon entropy assessment for data HW, LW, AV1, Rot in rounds.

The results in Fig. 3 demonstrate that after 3 rounds, the Shannon entropy of the datasets approaches approximately 8 bits per byte. This further confirms that after 3 rounds, the SDAES-128 block cipher exhibits randomness properties equivalent to the original AES-128.

4.3.4 Evaluate the min-entropy change using NIST SP 800-90B

More accurately than Shannon entropy, min-entropy is an extremely important measure of randomness. In NIST SP 800-90B, the authors presented a min-entropy estimation strategy for entropy sources. Here we use estimates for non-iid data sets to evaluate the min-entropy change of the 4 data sets LW, HW, AV1 and Rot over rounds of the SDAES-128 block cipher. The evaluation results are shown in the Fig. 4.

Fig. 4

NIST SP 800-90B min-entropy assessment for data HW, LW, AV1, Rot in rounds.

The results in Fig. 4 demonstrate that after 3 rounds, the SDAES-128 block cipher exhibits randomness properties equivalent to the original AES-128.

5 Shortcomings and future scope

In this section, we will point out the limitations of our method, as well as indicate the scope and directions for future research.

Our method has the potential to greatly bolster the strength of the AES block cipher. Nevertheless, it is not without its drawbacks and susceptibilities, including:

In the execution phase, there is a requirement for extra memory allocation dedicated to the novel XOR table. Specifically, rather than precomputing all XOR tables, we dynamically create a fresh XOR table for every session associated with a confidential key. Subsequently, the newly generated XOR table is retained for the entire duration of the session. When progressing to a successive session with a different key, a new XOR table is created afresh. Consequently, it is imperative to secure and preserve this XOR table until the conclusion of that session.

The process of creating XOR tables based on the secret key will affect the time required for encryption and decryption. Since, in every session where a secret key is utilized, both the sender and receiver need to implement the dynamic algorithm to produce a fresh XOR table before employing it for AES, a certain amount of time will be consumed at the start of each session for both entities to create a dynamic XOR table.

The technique presented in this paper aims to bolster the strength of the AES block cipher, offering heightened resistance against formidable attacks like linear and differential cryptanalysis. Nevertheless, it is crucial to acknowledge that side-channel attacks pose a risk, as they can exploit physical system characteristics to extract information about the encryption key. Consequently, both dynamic or static block ciphers may be susceptible to this form of attacks. Thus, irrespective of the cryptographic system employed, users must implement effective safeguards to thwart side-channel attacks, such as incorporating secure hardware or deploying software-based protective measures.

Our suggested dynamic AES algorithm is suitable for applications requiring exceptionally robust security and can safeguard extremely confidential information. The dynamic AES algorithm proves most effective in systems utilizing session keys over extended durations, thereby minimizing administrative burdens. Conversely, fortifying the dynamic AES algorithm presents challenges since it evolves with the session key. Thus, users should judiciously apply the dynamic AES algorithm, considering their real-world context and application requirements, aiming to augment the robustness of their data security.

Our research direction holds significant future potential. With the emergence of quantum computers, there is a substantial threat to the security of current cryptographic algorithms. Implementing dynamic block ciphers will greatly enhance security, as it introduces significant complexity for attackers attempting various attacks. Therefore, in the upcoming period, our focus will be on researching and proposing diverse methods for dynamic block ciphering, causing more confusion for potential attackers while maintaining a balance between security, execution speed, and cost.

6 Conclusion

In this paper, we propose several efficient methods to generate t-bit random XOR tables. Specifically, we propose two methods, one based on the Hadamard matrix and the other inspired by the famous intellectual game Sudoku. Furthermore, we propose dynamic block cipher algorithms based on animating key-dependent random XOR tables. We implement and test the algorithms and statistical record for several 4-bit XOR tables. In particular, we choose the AES-128 block cipher as a specific example to apply our dynamic block cipher algorithms. We conduct a comprehensive security analysis of the key-dependent AES block cipher. We evaluate the randomness of the proposed block cipher through the NIST SP 800-22 standards as well as using a 2-level evaluation using tests for short sequences. Furthermore, we evaluate the change in Shannon entropy and min-entropy over each round of the proposed dynamic block cipher using the ENT tool and estimators in SP 800-90B. The results show that the proposed dynamic AES block cipher is more secure than the regular AES block cipher, and its statistical randomness properties are either better or equal to those of AES. This demonstrates the significance of our proposed dynamic approach based on random XOR tables, enhancing the security of the AES block cipher. In future research directions, we will explore methods to make other components of the AES block cipher dynamic.

Footnotes

The Appendix part is available in the electronic version of this article: .

References

Altigani

, Hasan

, Barry

, Naserelden

, Elsadig

M.A.

and Elshoush

H.T.

, A polymorphic advanced encryption standard–a novel approach, IEEE Access 9 (2021), 20191–20207. Doi: 10.1109/ACCESS.2021.3051556.

Ejaz

, Shoukat

I.A.

, Iqbal

, Rauf

and Kanwal

, A secure key dependent dynamic substitution method for symmetric cryptosystems, PeerJ Computer Science 7 (2021), e587.

Al-Wattar

A.H.

, Mahmod

, Zukarnain

Z.A.

and Udzir

, A new DNAbased approach of generating key dependent MixColumnstransformation,, International Journal of Computer Networks &Communications (IJCNC) 7 (2015), 93–102.

Hadj Brahim

, Ali Pacha

, Hadj Said

An image encryption scheme based on a modified AES algorithm by using a variable S-box, Journal of Optics (2023) 1–16.

Salih

A.I.

, Alabaichi

and Abbas

A.S.

, A novel approach for enhancing security of advance encryption standard using private XOR table and 3D chaotic regarding to software quality factor,, ICIC Express Letters Part B: Applications, An International Journal of Research and Surveys 10 (2019), 823–832. Doi: 10.24507/icicelb.10.09.823.

Salih

A.I.

, Alabaichi

A.M.

and Tuama

A.Y.

, Enhancing advance encryption standard security based on dual dynamic XOR table and mixcolumns transformation, Indonesian Journal of Electrical Engineering and Computer Science 19 (2020), 1574–1581. https://doi.org/10.11591/ijeecs.v19.i3.pp1574-1581.

Garipcan

A.M.

and Erdem

, FPGA modeling of a novel fully-synthesizable and secure TRNG based on key-dependent s-box, Digital Signal Processing 136 (2023), 103969.

Al-Dweik

A.Y.

, Hussain

, Saleh

and Mustafa

M.T.

, A novel method to generate key-dependent s-boxes with identical algebraic properties, Journal of Information Security and Applications 64 (2022), 103065. https://doi.org/10.1016/j.jisa.2021.103065

Schneier

Description of a newvariable-length key, 64-bit block cipher (Blowfish), In International Workshop on Fast Software Encryption, Berlin, Heidelberg: Springer Berlin Heidelberg, 1993, 191–204.

10.

Schneier

, Kelsey

, Whiting

, Wagner

, Hall

and Ferguson

, Twofish: A 128-bit block cipher,, NIST AES Proposal 15 (1998), 23–91.

11.

Shannon

C.E.

, A mathematical theory of communication,, The Bell System Technical Journal 27 (1948), 379–423.

12.

Sulak

, Doganaksoy

, Ege

, Koçak

Evaluation of randomness test results for short sequences, International Conference on Sequences and Their Applications, Springer, Berlin, Heidelberg, 2010, 309–319. DOI: 10.1007/978-3-642-15874-2_27

13.

Liu

, Liu

and Ma

, Constructing dynamic strong S-Box using 3D chaotic map and application to image encryption,, Multimedia Tools and Applications 82 (2023), 23899–23914.

14.

Heys

H.M.

and Tavares

S.E.

, The design of product ciphers resistant to differential and linear cryptanalysis,, Journal of Cryptology 9 (1996), 1–19.

15.

Noura

H.N.

, Salman

and Chehab

, Conception of efficient key-dependent binary diffusion matrix structures for dynamic cryptographic algorithms,,, Journal of Information Security and Applications 76 (2023), 103514.

16.

Assafli

H.T.

and Hashim

I.A.

, Generation and Evaluation of a New Time-Dependent Dynamic S-Box Algorithm for AES Block Cipher Cryptosystems,, In IOP Conference Series: Materials Science and Engineering (2020), 012042.

17.

Daemen

and Rijmen

, The design of Rijndael, New York: Springer-verlag 2 (2002).

18.

Daemen

, Rijmen

AES proposal: Rijndael, NIST AES website (1999).

19.

Guo

, Song

, Wang

H. Key structures: Improved related-key boomerang attack against the full AES-256. In Australasian Conference on Information Security and Privacy, Cham: Springer International Publishing, 2022, 3–23.

20.

Walker

ENT: a pseudorandom number sequence test program. Software and documentation available at/www.fourmilab. ch/random/S, 2008.

21.

Bassham

L.E.

III Rukhin

A.L.

, Soto

, Nechvatal

J.R.

, Smid

M.E.

, Barker

E.B.

S. Vo, Sp 800-22 rev. 1a. a statistical test suite for random and pseudorandom number generators for cryptographic applications, National Institute of Standards & Technology, 2010.

22.

Golshani

, Pasha

and Yari

, Some properties of Renyi entropy and Renyi entropy rate,, Information Science 179 (2009), 2426–2433.

23.

Asif

and Shah

, BCH Codes with computational approach and itsapplications in image encryption,, Journal of Intelligent &Fuzzy Systems 37 (2019), 3925–3939.

24.

Pehlivanoglu

M.K.

, Sakallí

F.B.

, Akleylek

and Sakallí

M.T.

, On the Construction of New Lightweight Involutory MDSMatrices in Generalized Subfield Form,, IEEE Access 11 (2023), 32708–32715.

25.

Khan

, Haj Ismail

A.A.K.

, Ishaque

and Hussain

, Newcombination of simple additive and entropy weighting criteria forthe selection of best substitution box,, Journal of Intelligent& Fuzzy Systems 41 (2021), 2325–2338.

26.

Matsui

Linear cryptanalysis method for DES cipher, Advances in Cryptology—EUROCRYPT’93: Workshop on the Theory and Application of Cryptographic Techniques Lofthus, Norway, Proceedings 12, Springer Berlin Heidelberg, 1994, 386–397.

27.

Shamsabad

M.R.M.

and Dehnavi

S.M.

, Dynamic MDS diffusion layers with efficient software implementation,, International Journal of Applied Cryptography 4 (2020), 36–44.

28.

Turan

M.S.

, Barker

, Kelsey

, McKay

K.A.

, Baish

M.L.

, Boyle

Recommendation for the entropy sources used for random bit generation, NIST Special Publication N 800-90B, 2018, 102.

29.

Sajadieh

, Dakhilalian

, Mala

and Omoomi

, On construction of involutory MDS matrices from Vandermonde Matrices in GF (2 q), Designs, Codes and Cryptography 64 (2012), 287–308.

30.

Rivest

R.L.

, Robshaw

M.J.

, Sidney

, Yin

Y.L.

The RC6TM block cipher, In First advanced encryption standard (AES) conference, 1998, 16.

31.

Murphy

and Robshaw

M.J.B.

, Key-dependent S-boxes and differential cryptanalysis,, Designs, Codes and Cryptography 27 (2002), 229–255.

32.

Srisakthi

and Shanthi

A.P.

, Towards the design of a stronger AES: AES with key dependent shift rows (KDSR),, Wireless Personal Communications 114 (2020), 3003–3015.

33.

Chatterjee

and Laha

, A note on semi-orthogonal (G-matrix) and semi-involutory MDS matrices., Finite Fields and Their Applications 92 (2023), 102279.

34.

Manoj Kumar

and Karthigaikumar

, A novel method of improvement in advanced encryption standard algorithm with dynamic shift rows, sub byte and mixcolumn operations for the secure communication,, International Journal of Information Technology 12 (2020), 825–830.

35.

Mantere

, Koljonen

Solving and rating sudoku puzzles with genetic algorithms, In New Developments in Artificial Intelligence and the Semantic Web, Proceedings of the 12th Finnish Artificial Intelligence Conference Step, 2006, 86–92.

36.

Luong

T.T.

A Dynamic Algorithm for the Linear Layer of SPN Block Ciphers Based on Self-Reciprocal Recursive MDS Matrices, In 2023 15th International Conference on Knowledge and Systems Engineering (KSE), IEEE, 2023, 1–6.

37.

, Liu

and Wu

, A white-box AES-like implementation based on key-dependent substitution-linear transformations, Multimedia Tools and Applications 77 (2018), 18117–18137. https://doi.org/10.1007/s11042-017-4562-8

38.

Sawant

, Solkar

, Mangrulkar

Modified Symmetric Image Encryption Approach Based on Mixed Column and Substitution Box, Journal of Applied Security Research (2022) 1–34. https://doi.org/10.1080/19361610.2022.2150498.

39.

Lai

, Massey

J.L.

, Murphy

Markov ciphers and differential cryptanalysis, Advances in Cryptology–EUROCRYPT–91: Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, April 8–11, 1991 Proceedings 10, Springer Berlin Heidelberg, 1991, 17–38.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	3	7	9	0	10	14	15	1	13	2	4	12	11	8	5	6
1	7	3	14	1	15	9	10	0	12	5	6	13	8	11	2	4
2	9	14	3	2	11	7	8	5	6	0	12	4	10	15	1	13
3	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
4	10	15	11	4	3	8	7	6	5	12	0	2	9	14	13	1
5	14	9	7	5	8	3	11	2	4	1	13	6	15	10	0	12
6	15	10	8	6	7	11	3	4	2	13	1	5	14	9	12	0
7	1	0	5	7	6	2	4	3	11	14	15	8	13	12	9	10
8	13	12	6	8	5	4	2	11	3	15	14	7	1	0	10	9
9	2	5	0	9	12	1	13	14	15	3	11	10	4	6	7	8
10	4	6	12	10	0	13	1	15	14	11	3	9	2	5	8	7
11	12	13	4	11	2	6	5	8	7	10	9	3	0	1	15	14
12	11	8	10	12	9	15	14	13	1	4	2	0	3	7	6	5
13	8	11	15	13	14	10	9	12	0	6	5	1	7	3	4	2
14	5	2	1	14	13	0	12	9	10	7	8	15	6	4	3	11
15	6	4	13	15	1	12	0	10	9	8	7	14	5	2	11	3

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	3	7	9	0	10	14	15	1	13	2	4	12	11	8	5	6
1	7	3	14	1	15	9	10	0	12	5	6	13	8	11	2	4
2	9	14	3	2	11	7	8	5	6	0	12	4	10	15	1	13
3	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
4	10	15	11	4	3	8	7	6	5	12	0	2	9	14	13	1
5	14	9	7	5	8	3	11	2	4	1	13	6	15	10	0	12
6	15	10	8	6	7	11	3	4	2	13	1	5	14	9	12	0
7	1	0	5	7	6	2	4	3	11	14	15	8	13	12	9	10
8	13	12	6	8	5	4	2	11	3	15	14	7	1	0	10	9
9	2	5	0	9	12	1	13	14	15	3	11	10	4	6	7	8
10	4	6	12	10	0	13	1	15	14	11	3	9	2	5	8	7
11	12	13	4	11	2	6	5	8	7	10	9	3	0	1	15	14
12	11	8	10	12	9	15	14	13	1	4	2	0	3	7	6	5
13	8	11	15	13	14	10	9	12	0	6	5	1	7	3	4	2
14	5	2	1	14	13	0	12	9	10	7	8	15	6	4	3	11
15	6	4	13	15	1	12	0	10	9	8	7	14	5	2	11	3

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	3	7	9	0	10	14	15	1	13	2	4	12	11	8	5	6
1	7	3	14	1	15	9	10	0	12	5	6	13	8	11	2	4
2	9	14	3	2	11	7	8	5	6	0	12	4	10	15	1	13
3	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
4	10	15	11	4	3	8	7	6	5	12	0	2	9	14	13	1
5	14	9	7	5	8	3	11	2	4	1	13	6	15	10	0	12
6	15	10	8	6	7	11	3	4	2	13	1	5	14	9	12	0
7	1	0	5	7	6	2	4	3	11	14	15	8	13	12	9	10
8	13	12	6	8	5	4	2	11	3	15	14	7	1	0	10	9
9	2	5	0	9	12	1	13	14	15	3	11	10	4	6	7	8
10	4	6	12	10	0	13	1	15	14	11	3	9	2	5	8	7
11	12	13	4	11	2	6	5	8	7	10	9	3	0	1	15	14
12	11	8	10	12	9	15	14	13	1	4	2	0	3	7	6	5
13	8	11	15	13	14	10	9	12	0	6	5	1	7	3	4	2
14	5	2	1	14	13	0	12	9	10	7	8	15	6	4	3	11
15	6	4	13	15	1	12	0	10	9	8	7	14	5	2	11	3