Various methods are used for statistical testing of cryptographic algorithms, for example, NIST STS (A Statistical Test Suite for the Validation of Random Number Generators and Pseudo Random Number Generators for Cryptographic Applications) and DIEHARD (Diehard Battery of Tests of Randomness). Tests consists of verification the hypothesis of randomness for sequences generated at the output of a cryptographic algorithm (for example, a keys generator, encryption algorithms, a hash function, etc.). In this paper, we use the NIST STS technique and study the statistical properties of the most common hashing functions that are used or can be used in modern blockchain networks. In particular, hashing algorithms are considered which specified in national and international standards, as well as little-known hash functions that were developed for limited use in specific applications. Thus, in this paper, we consider the most common hash functions used in more than 90% of blockchain networks. The research results are given as average by testing data of 100 sequences of 108 bytes long, which means that is, the size of the statistical sample for each algorithm was 1010 bytes. Moreover, each test (for each of the 100 sequences) was considered as an independent observation. In addition, the article presents statistical portraits for each algorithm under study (diagrams of the numbers of passing each test).
In this work, statistical studies of the output sequences of cryptographic hash functions are performed, when this functions processing excessive input data. In this case, input data are formed using a regular counter.
The NIST STS (A Statistical Test Suite for Random and Pseudorandom Number
Generators for Cryptographic Applications) methodology, which is recommended by
The National Institute of Standards and Technology, USA for the study of random
and pseudorandom number generators for cryptographic applications [
The NIST STS statistical test suite recommended by The National Institute of
Standards and Technology, USA [
The NIST Statistical Test Suite was developed during the AES competition for the study of random or pseudorandom number generators and is the most common tool for assessing the statistical security of cryptographic primitives. The use of this package allows us to estimate how closely the crypto algorithms under study approximate the generators of "random" sequences, that is, with a high probability to confirm whether the generated sequence is statistically secure. The order of testing of a single binary sequence S is as follows: the null hypothesis H0 is advanced - the assumption that this binary sequence S is random; the test statistic с(S) is calculated according to the sequence S; the probability function P f c S is calculated using a special function and test statistics; the probability value Р is compared with the threshold value [0,96; 0,99] . If so P , the hypothesis H0 is accepted. Otherwise, an alternative hypothesis is accepted.
The test suite contains 15 statistical tests, but in fact, depending on the input parameters, 188 probability values of Р are calculated, which can be considered as the result of individual tests.
Frequency (Monobits) Test. Aims to determine the relation between zeros and ones in a binary sequence of a certain length. For a truly random binary sequence, the number of zeros and ones is almost the same. The test estimates how close the unit is to 0.5.
Test for Frequency Within a Block. The essence of the test is to determine the fraction of ones inside the block with a length of m bits, i.e. it is necessary to find out whether the repetition rate of ones in the block with a length of m bits is approximately equal m 2 , as might be assumed in the case of a random sequence.
Runs Test. This test searches for rows, that is, continuous sequences of identical bits. A series (runs) of length k bits consists of k absolutely identical bits, beginning and ending with a bit containing the opposite value. In this test, you need to find out if the number of such rows really matches their number in random order. In particular, it is determined whether the ones and zeros in the initial sequence quickly or slowly alternate.
Test for The Longest Run of Ones in a Block. This test determines the longest row of ones inside the block with a length of m bits. It is necessary to find out whether the length of such a row actually meets the expectation of the length of the longest row of ones in the case of a completely random sequence.
Random Binary Matrix Rank Test. Here, we calculate the rank of non-continuous sub-matrices constructed from the initial binary sequence. The purpose of this test is to test for linear dependence of fixed length substrings that make up the initial sequence.
Discrete Fourier Transform (Spectral) Test. The essence of the test is to estimate the peak height of the discrete Fourier transform of the initial sequence. The purpose is to identify periodic properties of the input sequence, for example, closely spaced repetitive sections. The idea is that the number of peaks in excess of the 95% amplitude threshold is much greater than 5%.
Non-Overlapping (Aperiodic) Template Matching Test. This test calculates the number of predefined templates found in the original sequence. It is necessary to identify random or pseudorandom number generators that form too often non-periodic patterns. As in Overlapping Template Matching Test, a window with a length of m bits is also used to search for specific patterns with a length of m bits. If no pattern is found, the window shifts one bit. If a pattern is found, then the window moves to the bit that follows the pattern found, and the search continues.
Overlapping (Periodic) Template Matching Test. The essence of this test is to calculate the number of predefined templates that were found in the original sequence. As in Non-Overlapping Template Matching Test, a window with a length of m bits is also used to search for specific patterns with a length of m bits. The search itself is conducted in a similar way. If no pattern is found, the window shifts one bit. The difference between this test and previous test is that when the pattern is found, the window moves only one bit forward, and then the search continues.
Maurer's Universal Statistical Test. In here determines the number of bits between the same patterns in the initial sequence (a measure that is directly related to the length of the compressed sequence). It is necessary to find out whether this sequence can be significantly compressed without loss of information. If this can be done, then it is not truly random.
Linear Complexity Test. The test is based on the principle of the linear shift register feedback. You need to find out if the input sequence is complex enough to be considered completely random. Absolutely random sequences are characterized by long linear shift registers. If such a register is too short, then it is assumed that the sequence is not completely random.
Serial Test. This test is to calculate the frequency of all possible overlaps of the m bit length patterns at the initial bit sequence. The purpose is to determine whether the number of occurrences of overlapping 2m patterns by the length of the m bits is approximately the same as in the case of an absolutely random input bit sequence. The latter is known to be monotonous, that is, each pattern with a length of m bits appears in a sequence with equal probability. It is worth noting that when m 1 , so the periodicity test goes into the frequency bit test.
Approximate Entropy Test. As in the periodicity test, this test focuses on calculating the frequency of all possible overlaps of the m bit length patterns at the initial bit sequence. It is necessary to compare the overlap frequencies of two consecutive blocks of the initial sequence with the lengths m and m 1with the overlap frequencies of similar blocks in a completely random sequence.
Cumulative Sum (Cusum) Test. The test is the maximum deviation (from zero) at an arbitrary bypass determined by the cumulative sum of the given digits 1, 1 in the sequence. It is necessary to determine whether the cumulative sum of the partial sequences occurring in the input sequence is too large or too small compared to the expected behavior of such a sum for a completely random input sequence. Thus, the cumulative amount can be regarded as an arbitrary bypass. For a random sequence, the deviations from the bypass should be near zero.
Random Excursions Test. The essence of this test is to calculate the number of cycles that have strictly k excursions with an arbitrary bypass of the cumulative sum. The arbitrary bypass of a cumulative sum begins with partial sums after the sequence 0,1 is translated into the corresponding sequence 1, 1 . An arbitrary bypass cycle consists of a series of single-length steps performed in random order. In addition, such a bypass begins and ends on the same element. The purpose of this test is to determine whether the number of visits to a particular state within a cycle differs from a similar number in the case of a completely random input sequence. In fact, this test is a set consisting of eight tests that are conducted for each of the eight cycle states: 4, -3, -2, -1 and +1, +2, +3, +4.
Random Excursions Variant Test. This test calculates the total number of excursions to a given condition when you randomly bypass the cumulative sum. The purpose is to determine deviations from the expected number of visits to different states at random bypass. In fact, this test consists of 18 tests for each state: -9, -8, ..., -1 and +1, +2, ..., +9.
Thus, as a result of binary sequence testing, a vector P P1, P2...P188 of probability values Pj is formed. The analysis of the components Pj of this vector allow us to point to specific defects in the randomness of the tested sequence.
Passing each of the 15 statistical tests is an important criterion for evaluating a pseudorandom generator. Therefore, not even matching one or more criteria means that the stream cannot withstand cryptanalysis at a high level. If, on the other hand, the generator passes all the tests, this does not indicate the security of the generator, since such tests do not take into account the features of the actual design of the generator.
The accumulated experience of statistical testing shows that the number of tests
passed by the generator being tested depends directly on the selected cryptographic
algorithm output sequence. To ensure the reliability of the results of statistical testing
in the work [
When conducting statistical surveys, 100 sequences with a length of 108 bytes were generated for each algorithm, i.e. the size of the statistical sample for each algorithm reached 1010 bytes. Each testing (for each of the 100 sequences) was considered as an independent observation. Table 1 summarizes the statistical test results for each algorithm studied. "D096" and "D099" ("S096" and "S099") – estimates of the statistical dispersion (standard deviation) of the results of testing the number of statistical tests completed by the criterion Pj 0, 96 and criterion Pj 0, 99 , accordingly; "P099" – the confidence value for the number of statistical tests completed by criterion Pj 0, 99 and accuracy 2 ; "P096" – the value of the confidence probability for the number of statistical tests passed by criterion Pj 0, 96 and accuracy 1 ; "Min096" – the minimum values of the number of statistical tests passed by the criterion Pj 0, 96 .
The results of statistical studies (statistical portraits) of hashing algorithms are shown in Fig. 1-40. On the abscissa scale the statistical test number (from 1 to 188) is given, on the ordinate scale the fraction of passing of the corresponding test is given. Fig. 2. BALLOON64 Fig. 14. FUGUE224 Fig. 19. Stribog_512 Fig. 28. RIPEMD160 Fig. 36. SHAVITE
The results of statistical studies indicate that certain high-speed algorithms cannot be applied in cryptographic applications. This applies, for example, to the algorithms DJB-2, LOSELOSE, and others, because these algorithms, in fact, do not compute a cryptographic checksum. However, most of the cryptographic hashing algorithms, that have been studied, have shown high statistical properties and have high rates of indistinguishability criterion with truly random sequence.
Hashing functions are a complex and very important cryptographic primitive that is used in almost all mechanisms and protocols of cryptographic security of information (password generation, encryption, pseudorandom sequence generation, electronic signature generation, etc.). In recent years, the use of hashing has expanded significantly. In particular, with the advent and rapid spread of decentralized distributed systems based on so-called "linked lists" (blockchain) technology, there was an urgent need for fast, safe and reliable hashing functions, because of their unpredictable and irreversible features secure blockchain chains are being built. The task of choosing a hash function is much more complicated due to the proliferation of specialized computants that are being developed and practically used to look for prototypes of preformed hash values (ASIC-mining). By investing in the acquisition of ASICs, individual players can be deliberately advantaged compared to other blockchain users and can, therefore, cause non-trust and compromise of decentralized technologies (e.g., different cryptocurrencies, distributed storage, smart- contracts, etc.). Therefore, the study of the properties of modern hashing algorithms and the rationale for their recommendations for the national blockchain technology segment development is certainly an important and extremely relevant scientific task.
The results obtained shows that most hashing functions satisfy the criteria of statistical security (by the NIST STS method), that is, by different indicators the output sequences (hash values) do not differ (in the statistical sense) from the truly random sequences. These are mainly known and standardized algorithms, which are applied in various cryptographic applications and have already been substantially researched and studied in previous tests. However, among the algorithms in Table 1 there are those whose statistical certainty is either unsatisfactory or completely unacceptable. For example, the well-known hashing algorithm RIPEMD160, which is standardized in ISO/IEC 10118-3:2018 and accepted for use in the European Union, has shown low values of statistical security (the average number of statistical tests with Pj 0, 96 completed does not exceed 85). That is, if the RIPEMD160 algorithm inputs an excess sequence (in our studies, the input sequence was formed by a regular counter), the generated hash sequences differ from the random sequence, i.e. they have some determinism. Although we have not identified any specific defects in the RIPEMD160 algorithm, the results indicate that some of the generated hash codes are flawed in terms of randomness and unpredictability.
The unsatisfactory performance of the DJB-2, DJB-2 XOR, and LOSELOSE hashing algorithms should be noted separately. In terms of statistical security, they are not acceptable for practical use in cryptographic applications. This conclusion is predictable because the DJB-2, DJB-2 XOR, and LOSELOSE algorithms are essentially not cryptographic, and the calculation of the hash sequences in them is similar to a regular checksum. But, as the results show, even when using statistically dangerous algorithms as part of cascading mining schemes (for example, in the X family hash algorithms), the generated hash sequences also do not satisfy statistical security indicators (see last two lines of the Table 1).
Thus, choosing a hashing algorithm for building blockchain system elements is extremely important and painstaking. In view of the results obtained, in addition to performance, it is also necessary to consider the reliability and security of cryptocurrencies. Also important is the availability of Specialized Computers (ASICs), which greatly accelerate mining in certain consensus protocols. Therefore, to justify the choice of hashing algorithms, it is necessary to consider various factors and performance indicators, including the features of building a specific blockchain system, consensus protocols, processing and messaging algorithms, etc.
This research might be useful for the improvement of various methods of information security, as well as other practical use [17-22]. 16. I. Gorbenko, A. Kuznetsov, V. Tymchenko, Y. Gorbenko and O. Kachko, "Experimental Studies Of The Modern Symmetric Stream Ciphers," 2018 International ScientificPractical Conference Problems of Infocommunications. Science and Technology (PIC S&T), Kharkiv, Ukraine, 2018, pp. 125-128. doi: 10.1109/INFOCOMMST.2018.8632058 17. Andrushkevych A., Gorbenko Y., Kuznetsov O., Oliynykov R., Rodinko M. A (2019) “A Prospective Lightweight Block Cipher for Green IT Engineering”. In: Kharchenko V., Kondratenko Y., Kacprzyk J. (eds) Green IT Engineering: Social, Business and Industrial Applications. Studies in Systems, Decision and Control, vol 171. Springer, Cham, pp. 95112. DOI: 10.1007/978-3-030-00253-4_5 18. Krasnobayev V., Kuznetsov A., Koshman S., Moroz S. (2019) Improved Method of Determining the Alternative Set of Numbers in Residue Number System. In: Chertov O., Mylovanov T., Kondratenko Y., Kacprzyk J., Kreinovich V., Stefanuk V. (eds) Recent Developments in Data Science and Intelligent Analysis of Information. ICDSIAI 2018. Advances in Intelligent Systems and Computing, vol 836. Springer, Cham, pp. 319-328, 05 August 2018. DOI: 10.1007/978-3-319-97885-7_31 19. Hu Z., Gnatyuk S., Kovtun M., Seilova N. Method of searching birationally equivalent Edwards curves over binary fields, Advances in Intelligent Systems and Computing, Vol. 754, pp. 309-319, 2019. 20. Iavich M., Gagnidze A., Iashvili G., Gnatyuk S., Vialkova V. Lattice based Merkle, CEUR
Workshop Proceedings, Vol. 2470, pp. 13-16, 2019. 21. Gnatyuk S., Kinzeryavyy V., Kyrychenko K., Yubuzova Kh., Aleksander M., Odarchenko R. Secure Hash Function Constructing for Future Communication Systems and Networks, Advances in Intelligent Systems and Computing, Vol. 902, pp. 561-569, 2020. 22. Kuznetsov O., Potii O., Perepelitsyn A., Ivanenko D., Poluyanenko N. (2019) “Lightweight Stream Ciphers for Green IT Engineering”. In: Kharchenko V., Kondratenko Y., Kacprzyk J. (eds) Green IT Engineering: Social, Business and Industrial Applications. Studies in Systems, Decision and Control, vol 171. Springer, Cham, pp. 113-137. DOI: 10.1007/978-3-030-00253-4_6