Developing a New Collision-Resistant Hashing Algorithm

Abstract

Today, cryptographic hash functions have numerous applications in different areas. At the same time, new collision attacks have been developed recently, making some widely used algorithms like SHA-1 vulnerable and unreliable. This article is aiming at the development of a new hashing algorithm that will be resistant to all cryptographic attacks, including quantum collision attacks that potentially pose a threat to some widely used cryptographic hash functions. This algorithm was called Nik-512. The avalanche effect is tested to ensure the cryptographic strength of the developed algorithm. The Nik-512 function is then applied to build a data integrity system which can be used to protect data from malicious users.

1. Introduction

In the modern world, information security is becoming increasingly important due to the rapid development of information technologies and the ever-growing amount of data that should be protected. According to the OWASP Web Application Security Project, the most critical security risks in 2021 included errors in implementations of cryptographic algorithms and failures in data integrity systems. Cryptographic hash functions have numerous practical applications, namely, password authentication, electronic signature schemes and blockchain proof-of-work protocols. If vulnerability is discovered in a cryptographic hash function, then it can no longer be used to provide required security.

In recent years, serious vulnerabilities have been found in some hashing algorithms that were considered reliable in the past, and these algorithms can no longer be used to ensure cryptographic security. Steady increases in computing power have already made many cryptographic attacks that were previously considered only theoretical now practical for malicious users. Recent groundbreaking achievements in quantum computing mean that in the nearest future, even more effective attacks on hashing algorithms will be possible.

Hence, there is a need for new hashing algorithms that will provide sufficient cryptographic resistance against the most modern attacks that can be accomplished with the use of supercomputers and quantum computers. Strong cryptographic hash functions make it possible to ensure the integrity of information in spite of continuous increases in the computing power that attackers have on their disposal. Improvements in common hashing algorithms have been proposed recently to make them more efficient and resistant to modern collision attacks. For instance, scientists Nada E. El-Meligy, Tamer O. Diab and Ashraf S. Mohra described and implemented a number of valuable changes to the standard SHA-512 that they concluded could be employed to enhance the security of the SHA-2 algorithm without losses in performance [1]. In another article that was published recently, Torres-Alvarado et al. investigated possible errors in the implementation of the SHA-3 standard and proposed a new architecture that can decrease the probability of failures in the algorithm, which makes it more reliable and also provides better resistance to cryptographic attacks [2]. An important application of the cryptographic hash function that has been actively researched in recent years also includes key generation. As Bai, Jiang and Wu showed in an article that examined modern approaches to key generation, utilizing hash functions is an effective way to save memory and improve the performance of such algorithms [3]. Hashing algorithms have several possible applications in machine learning. A cryptographic hash function can be effectively used in image detection systems when the security of the data involved in the detection process is indispensable. Gadamsetty et al. exhaustively researched an application of SHA2-256 to a system for recognizing ships from images [4] and managed to implement a system that ensured data integrity during the detection and further transmission of the collected data. In 2021, Alotaibi utilized a hash function based on the Miyaguchi–Preneel structure to develop an innovative machine learning technique that can be used for malware detection [5].

The object of this work is a cryptographic hash function, the subject of the work is the collision resistance of cryptographic hash functions and the aim of the research is to develop a cryptographic hash function that is resistant to modern collision attacks.

In accordance with the main aim of the research, the following objectives were determined:

−

Study the theory of modern hashing algorithms and collision attacks;

−

Build a mathematical model of a hash function resistant to collision attacks;

−

Perform an analysis of the developed hash function based on statistical methods;

−

Implement a data integrity system that is resistant to collision attacks and based on the developed hash function.

The main scientific methods that were used in the research are analysis, classification, comparison and experiment.

2. Materials and Methods

2.1. Description of Hash Function and Collision Attack

A hash function is a function that takes a string of arbitrary length as an argument and calculates a value of fixed length n. The resulting value is called a hash value of the given string [6].

Hash collision for a hash function H is defined as a pair of different messages X and Y that have the same hash value when this hash function is applied to the messages X and Y. An algorithm that calculates a collision for the hash function H is called a collision attack for this function. The number of hash function calls required to find a collision of the hash function is determined as follows:

$$C=2^{n/2},$$

(1)

where n is a hash length [7].

There are various classifications of cryptographic hash functions. In one of the possible classifications, all cryptographic hash functions can be divided into two classes: keyed and keyless. Keyless hash functions do not use an additional key and are used to confirm that there are no corruptions that may have been introduced during the transmission of a message. On other hand, keyed hash functions use a secret key K that is known to both the sender and the recipient of the message. The use of the key allows for performing message authentication (confirmation of the fact that the message was received from a trusted sender who knows the secret key K) [8].

Based on the resistance of hashing algorithms to various cryptographic attacks, the following types of hashing algorithm are defined:

(1) Resistance to the first preimage attack, which ensures that generating a message that corresponds to a given hash value is not feasible in practice.

(2) Resistance to the attack of finding the second preimage (also known as weak collision resistance) implies the practical impossibility of generating such a message B for predetermined message A that A and B will be a collision.

(3) Resistance to collision attacks means that the implementation of a collision attack for any message is impossible in practice.

(4) Near collisions resistance means a high computational complexity of the problem of finding two messages A and B, such that for a sufficiently small value δ, the following condition will be satisfied:

$$d\left(H\left(A\right),H\left(B\right)\right)<\delta ,$$

(2)

where H is a hash function and d is the Hamming distance.

(5) Partial preimage resistance means that obtaining any part of the original message from its hash has significant computational complexity.

A collision attack allows an attacker to edit a protected file or to forge an electronic signature, for instance, a system that checks the integrity of some file A based on its hash. Let H1 be the hash value calculated for file A. If file A has been changed, then the hash value for this file will also change and will be equal to some value H2. In this case, the integrity check will fail. However, when a collision attack can be accomplished, the attacker can create a file B for which the hash value is H1, and thus, later they can replace file A with file B. This scheme of a collision attack is shown in Figure 1.

It is important to note that a collision attack allows an attacker to replace a file only if a collision for this file can be generated in advance. Creating a new file with the same hash based on an arbitrary file and a corresponding hash value requires the successful implementation of the second preimage attack. In practice, the most dangerous attack on a cryptographic hash function is the chosen-prefix collision attack, since it allows attackers to impose false information if they choose real data as the first prefix and fake data as the second prefix.

2.2. Review of Modern Hashing Algorithms and Collision Attacks

Currently, the most common cryptographic hash functions are algorithms of the SHA family, which includes three standards: SHA-1, SHA-2 and SHA-3. The SHA-1 algorithm was created in 1995 and published in the Federal Information Processing Standard FIPS PUB 180-1 [8]. In 2017, the SHAttered prefix collision attack was developed and implemented in practice [9]. This attack has a computational complexity of 263 [10]. As a consequence, SHA-1 is no longer considered resistant to collision attacks, and SHA-2 or SHA-3 should be used instead [11].

The SHA-2 algorithm is a collision-resistant hashing algorithm, and as of 2022, there is no SHA-2 modification that will allow for any collision attack that is faster than a generic attack [7]. Collision attacks on SHA-2 with a reduced number of rounds have been developed, but they hold only theoretical value since they cannot be applied to the full SHA-2 algorithm [12]. Since SHA-2 is based on the Davis–Meyer structure, there was a serious concern among theoreticians that attacks based on differential cryptanalysis can be found against it. This fact resulted in the emergence of the new SHA-3 standard [13].

The SHA-3 standard was developed by a group of four scientists led by Joan Dymen. In 2012, a special competition was held by the National Institute of Standards and Technology, and the Keccak function won the competition. This function was used for the development of the SHA-3 standard [14].

Currently, there are no collision attacks on the SHA-3 algorithm that would allow a collision faster than a generic collision attack [15]. In 2021, it was proved that the SHA-3 algorithm is resistant to quantum collision attacks. This means that there is no quantum attack on SHA-3 that would allow finding a collision faster than if the BHT quantum algorithm were utilized [16]. From detailed comparisons of SHA-1 and SHA-3, it can be concluded that differential cryptanalysis is ineffective against the SHA-3 algorithm [17].

A common approach to the implementation of collision attacks that can exploit vulnerabilities in the specific hashing algorithm is differential cryptanalysis. This method is based on the analysis of differences between input data values at various rounds of the hashing process [18]. In differential cryptanalysis, a difference is understood to be a binary sequence obtained by applying the XOR operator to the current two messages in a given round of the algorithm [19].

Another important class of collision attacks is quantum collision attacks. For a long time, quantum attacks were only theoretical. However, in recent years, working quantum computers have been developed by Google and IBM. This means that quantum attacks may become a reality in the near future, and when assessing the cryptographic strength of hash functions, it is necessary to take into consideration the possibility of implementing quantum collision attacks [20].

The computational complexity of a generic quantum attack can be calculated as follows:

$$C=2^{n/3},$$

(3)

where n denotes hash length.

In the case of using a quantum computer to accomplish a collision attack, the Brasard–Hoyer–Tappard (BHT) algorithm, which based on the application of the Grover algorithm can significantly reduce the amount of computation required. The computational complexity of the BHT algorithm is equal to the complexity of the generic quantum collision attack [21].

The BHT algorithm for finding a collision of a function H with hash length n consists of the following steps:

(1) A subset $X\subseteq {\left\{0,1\right\}}^n$ is chosen with cardinality equal to $2^{n/3}$.

(2) The value of the function f(x) is calculated for each element x from the subset X.

(3) A list L is created from elements of the form {x, f(x)} for each x.

(4) The list L is stored in quantum memory.

(5) Grover’s algorithm is used to find x′ such that the following condition will be satisfied:

$$(x^{\prime }\in {\left\{0,1\right\}}^n\backslash X) and f\left(x^{\prime }\right)=f\left(x\right)$$

(4)

Thus, the value x′ found as a result of the execution of the algorithm and the v corresponding value x will be a collision of the hash function H.

The main disadvantage of the BHT algorithm is the amount of quantum memory required to execute the algorithm. This means that in practice, providing a sufficient amount of quantum memory will be expensive to the extent of the practical impossibility of employing the BHT algorithm to find a collision [22].

The amount of quantum memory q required to apply the BHT algorithm grows exponentially with the hash length n and is calculated by the formula:

$$q=2^{n/3},$$

(5)

where n denotes the hash value length.

To solve the problem associated with memory requirements, scientists A. Chailloux, M. Naya-Plasencia and A. Schrottenloher in a paper published in 2017 proposed an innovative quantum algorithm for finding hash collisions [23]. This algorithm is called CNS. The main approach in this algorithm is the modification of the collisions search that places most of the data processed in classical memory instead of quantum memory. In this case, it is necessary to minimize the inevitable loss of computational speed [24]. The developed algorithm uses the amount of quantum memory, which linearly depends on the hash length n. In this case, the time required to perform the algorithm is determined by the formula

$$T=2^{2n/5}.$$

(6)

The required amount of classical memory can be calculated as follows:

$$c=2^{n/5}.$$

(7)

2.3. Related Works

Although most of the publications related to hashing algorithms investigate some aspects of already existing hash functions, there have been several articles that propose a completely new hashing algorithms within last three years. In the article published by K. Sakan, S. Nyssanbaeva, N. Kapalova et al. in 2022 [25], a new hashing algorithm called HBC-256 was developed and analysed. The authors used the Devis–Mayer construction to build their algorithm. They also tested an avalanche effect of the developed algorithm and proposed an implementation of the developed algorithm that utilizes parallelization to improve performance. The most notable features highlighted by the authors are the reduction of the number of rounds for improving the performance and the finding that the specific structure of the compression function increases the number of blocks that can be processed in parallel. In 2020, Tutueva, Karimov, Moysis et al. [26] described a new hashing algorithm that uses adaptive chaotic maps and provides resistance to collision attack. A similar approach was used by Yu Wang, Liquan Chen, Xinguyan Wan et al. [27], where a new keyed hash function was proposed. This function is based on the Merkle–Damgard construction with a chaotic map neural network. The authors state that their algorithm is resistant to all modern attacks including multicollision attacks, which are mentioned less frequently in articles on cryptographic hash functions than are classical collision attacks. A completely different approach to the problem was proposed in 2020 by Edimar Verissimo de Silva [28], who developed a new architecture that utilizes a complex sequence of permutations and rotations of separated blocks and leads to strong resistance against attacks at the expense of performance. From the review of related works, it can be concluded that scientists today are exploring innovative and uncommon approaches to building hashing algorithms that will be resistant to modern attacks.

3. Results

3.1. Development of the Collision-Resistant Hashing Algorithm

A cryptographic hash function that is resistant to collision attacks must be a one-way function. That means that it is easy to calculate the hash value for any message but that finding at least one message for which the hash value is equal to the given value must be computationally difficult (computation complexity depends on the hash length at least exponentially).

Another indispensable property of the cryptographic hash function is the avalanche effect. This refers to the property of a hash function that a slight change in the input message will result in a complete change of the hash value. The avalanche effect means that a change in one bit of the message will result in a change in half the bits of the hash.

One of the possible approaches to the development of a collision-resistant hash function is iterative hash construction with a block cipher being employed as a compression function. The main advantage of this approach is the strong cryptographic properties of the developed hash function that can be achieved without additional modifications if the chosen block cipher is secure enough. Another common approach is based on sponge construction, which can be described as an algorithm with internal state that uses a permutation function to produce output (hash value) from a stream of input bits. Authors decided to build a compression function without relying on the existing block ciphers and constructed it as a set of permutations of internal state with bitwise operations applying to its elements. The advantage of this approach in comparison with SHA-1 and SHA-2 is that it allows for building a secure hash function with fewer rounds and without determining specific constants for the internal state. The shortcoming of the chosen approach is that each round requires a significant number of operations to be performed and there is a need for optimization that will take advantage of potential efficiency of bitwise operations in low-level programming languages.

As a result of the conducted research, a cryptographic hash function with a hash output length of 512 bits has been developed. This function is based on the Miyaguchi–Preneel structure. It uses two 512-bit long values A stored as an array of 16 32-bit elements. The message for which the hash should be calculated is divided into blocks of 512 bits. The last block is padded with zeros to a size of 512 bits. There is no limit to the input string length for the developed algorithm.

At the beginning of the algorithm execution, the value of S is initialized as 0 if the function works in keyless mode or as a key value if the key mode is used. The value of M is initialized with the first block of the message being processed.

For each message block, the compression function is called, which takes as parameters the current value of the internal state and the message block that should be processed. The flow chart of the hash function is shown in Figure 2.

The compression function takes A and B values of 512 bits as input and calculates a value of 512 bits. Then calculation 32 rounds is performed, during each of the rounds the following formulas are applied to the input:

(1) The input receives the current values of arrays A and B.

(2) For A_i, the transformation is performed according to formula (7) (the indexes of the elements are taken modulo 16):

$$A_i:=\left(A_i\gg 1\right) ⨁ (\neg B_i) ⨁ \left(A_{i+6}\wedge \neg B_{i+3}\right),$$

(8)

(3) The array is rotated (the i-th element becomes the (i − 1)-th element, and the zero element becomes the last element).

(4) For A_i with indices 2 ≤ i ≤ 16, the transformation is performed according to the formula:

$$A_i:=\left(\neg A_i\gg 1\right) ⨁ B_i ⨁ \left(\neg A_{i-6}\wedge B_{i-3}\right),$$

(9)

(5) For all A_i and B_i, transformations are performed according to the formula

$$\left\{\begin{array}{c}{A}_i:=A_i mod 2^{32}\\ B_i:=\left(B_i+A_i\times A_{\left(i+r^3\right)mod16}\right) mod 2^{32} ,\end{array}\right.$$

(10)

where r is the number of the current round (for the first round r = 0, for the last round r = 31)

The flow chart of the compression function is shown in Figure 3.

In this work, the authors have developed the hashing algorithm with hash length 512, but it is possible to build a hashing algorithm with even larger hash length following the same approach. For example, a hash function that produces 1024-bit output can be created from Nik-512 by increasing the length of the input arrays A and B (in this case, both arrays will contain 32 values instead of 16). To achieve this, the input message should be divided into blocks with the length 1024, and some adjustments to the formulas using in the compression function will be needed. It is important to note that the authors do not claim that this modification will have the same cryptographic properties as the original algorithm.

To test the avalanche effect, it is necessary to generate many message pairs that differ from each other by only one bit and calculate the hash values for these messages. After that, the Hamming distance should be calculated for each pair of received hashes. In the case of a strong cryptographic hash function, the Hamming distance for pairs of hashes can be considered a random variable with expectation equal to n/2, where n is the hash length. In the case of the hash function developed as the result of this research, the mathematical expectation was 256. Then, the deviation of the mathematical expectation and the standard deviation were calculated. As a sample, 65,536 pairs of messages were used.

The test was performed for four different hash functions:

(1) SHA512 modification of the SHA-2 algorithm.

(2) SHA3-512 modification of the SHA-3 algorithm.

(3) Hash function GOST 34.10–2018 with a hash length of 512 bits.

(4) Nik-512 (this name was given by the author to the new hashing algorithm described in this paper).

Figure 4 shows the results of testing the avalanche effect of the Nik-512 hash function.

Table 1. The avalanche effect testing results.

Hash Function	Absolute Difference between the Expected Value (256) and the Average Hamming Distance	Standard Deviation of the Hamming Distance
SHA512	0.3786	11.3647
SHA3-512	0.4921	11.3451
ΓOCT 34.11–2018	0.4515	11.2974
Nik-512	0.0467	11.2951

shows the differences between the mathematical expectations and the actual averages and standard deviations for various hash functions. Among the four algorithms examined, the Nik-512 hash function has the smallest differences between the average and expected values and the standard deviations. Based on the data obtained, it can be concluded that the avalanche effect is stronger for the developed hash function than for other algorithms. This means that the behavior of the developed function is closest to the random number generator. Thus, it provides the best collision resistance. The result obtained allows for using the developed Nik-512 algorithm as a cryptographic hash function resistant to collision attacks.

3.2. Demonstration of the Implemented Data Integrity Checking System

Based on the developed hash function, a data integrity system was implemented. The user can choose one algorithm from the list that includes SHA512, SHA3-512, the hash function described in the Russian standard GOST 34.11–2018 (a modification with a hash length of 512 bits is used) and the Nik-512 hash function.

Figure 5 shows an example of calculating the Nik-512 hash function for a file selected by the user. The resulting value can later be stored in the database.

Figure 6 shows an example of a file integrity check. The previously stored hash value is loaded from the database. The hash value is also calculated for the current version of the file, and then a comparison with the loaded value is performed. If the two values are the same, a message is displayed indicating that the verification was successful.

Figure 7 shows an example of a check in which the hash value for the uploaded file differs from the previously saved value, meaning that the file has been changed and the integrity check has failed.

Table 2. Comparison of hashing programs.

	SHA-2	SHA-3	GOST 34.11-2018	Whirlpool	Nik-512	Vulnerable (SHA-1, MD-5)
HashGenerator	+	+	−	−	−	+
HashMyFiles	+	+	−	−	−	+
HashTab	+	+	−	+	−	+
QuickHash	+	−	−	−	−	+
MultiHasher	+	−	−	−	−	+
NikitaHasher	+	+	+	−	+	−

compares the developed software with existing solutions. Supported hashing algorithms with resistance to collision attacks are shown for each program. The support of each of these algorithms is an advantage of the program. The presence of hashing algorithms with discovered vulnerabilities (MD-5, SHA-1) is a disadvantage of the program, since the user can use this algorithm to protect a file and thus make this file vulnerable to a collision attack. The developed software tool supports modifications with a hash length of 512 bits of the standard algorithms SHA-2, SHA-3 and GOST 34.10-2018. Additionally, the Nik-512 hash function that was developed as part of this work is available.

4. Discussion

The results of this research include the development of the collision-resistant cryptographic hash function Nik-512 and the implementation of the data integrity checking system NikitaHasher. Given that attacks aiming at falsifying data and forging electronic signatures pose a serious threat in the modern world, this system can be used effectively by any company to ensure data integrity. It bears mentioning that its applicability is not restricted by any type of data or any specific properties of the content of the files stored. This fact makes the implemented system promising for coming into widespread use in the nearest future. In the light of the recent advances in the development of fast and secure cryptographic hash functions, the vulnerable algorithms SHA-1 and MD-5 have no practical advantages in modern cryptography and should be replaced with more secure hash functions.

The authors give a review of modern hashing algorithms from the perspective of resistance to modern collision attacks. They conclude that today, the most dangerous type of attacks on hashing algorithms are quantum attacks because they allow for finding a collision significantly more quickly than classical attacks that do not require quantum computations. Upon investigating recent articles on quantum collision attacks and post-quantum security of hashing algorithms, the authors came to a conclusion that a cryptographic hash function could be resistant to quantum attacks if it were constructed and implemented correctly. Thanalakshmi et al., in research on a post-quantum digital signature system, discussed similar issues related to weaknesses of hashing algorithms being applied to digital signature verification taking into consideration recent advancements in quantum technologies [29]. Their research showed that it is possible to build post-quantum hash-based digital signature system.

5. Conclusions

The main result of this work is the development of a cryptographic hash function with a 512-bit hash length that is resistant to collision attacks. The cryptographic strength of the developed hash function was confirmed by testing its statistical properties and comparing them with other hashing algorithms. As a result of the comparison, it was concluded that the developed hash function better fulfills the avalanche effect requirement, and this means better resistance to collision attacks. Additionally, using the constructed hash function, a software tool for data integrity control was developed. The program provides the user with a greater choice of collision-resistant hashing algorithms than existing analogues. Another important advantage of the developed software is the lack of support for vulnerable hashing algorithms.

Further research may include constructing key derivation functions and blockchain applications based on the Nik-512 hashing algorithm and integrating the implemented software with digital signature systems.