GOST R 34.11-2012

In accordance with the requirements expressed at the RusCrypto 2010 conference, in the work devoted to the new hash function ^[1] :

• the new hash function should not have properties that would allow the use of known attacks;
• the hash functions must use the studied constructions and transformations;
• the calculation of the hash function should be efficient, take little time;
• There should be no unnecessary conversions that complicate the construction of the hash function. Moreover, each transformation used in the hash function must be responsible for certain cryptographic properties.

In the same paper, “universal” requirements are introduced regarding the complexity of attacks on a hash function:

• In GOST R 34.11-2012, the size of message blocks and the internal state of the hash function is 512 bits versus 256 bits in GOST R 34.11-94.
• The new standard defines two hash functions with hash lengths of 256 and 512 bits, while in the old standard, the hash code length can only be 256 bits. The ability to vary the output hash can be useful in the case of embedded implementations with limited resources or the presence of some additional requirements in the field of cryptography.
• The main difference between the modern hash function and the old one is the compression function. GOST R 34.11-2012 uses the compression function, which is based on three transformations: a nonlinear bijective transformation (denoted by S), byte permutation (denoted by P), linear transformation (denoted by L). GOST R 34.11-94 uses a compression function based on the symmetric block cipher GOST R 28147-89, also this function uses mixing operations.
• When calculating a new hash function, if the message size is not a multiple of the size of the block being processed (for the modern standard - 512 bits, for the old standard - 256 bits), then such a block is supplemented with a vector (00 ... 01). When calculating the old hash function, the incomplete block is supplemented with the value (00 ... 0). It is believed that the complement (00 ... 01) is better than (00 ... 0), from a cryptographic point of view, because padding with the value (00 ... 0) leads to attacks of the padding oracle ^[2] . In the case of a non-zero addition, resistance to such attacks was proved ^[3] .
• Another difference is that the standard GOST R 34.11-94 did not determine the value of the initialization vector, while in the standard GOST R 34.11-2012 the value of the initialization vector is fixed and defined in the standard: for a hash function with an output hash size of 512 bits this is a vector (00 ... 0), for a hash function with an output hash code size of 256 bits - (000000010 ... 100000001) (all bytes are equal to 1).

In a hash function, an important element is the compression function. In GOST R 34.11-2012, the compression function is based on the Miaguchi-Prenel design . Miaguchi-Prenel design scheme: h, m are the vectors arriving at the input of the compression function; g (h, m) is the result of the compression function; E is a block cipher with a block and key length of 512 bits. An XSPL cipher was taken as a block cipher in the hash function of GOST R 34.11-2012. This cipher consists of the following transformations:

• modulo 2 addition;
• substitution or substitution conversion. S-transformation is indicated;
• permutation transformation. P conversion is indicated;
• linear transformation. The L-transformation is indicated.

The transformations used in the new hash function should be well understood. Therefore, the block cipher E uses the transformations X, S, P, L, which are well studied.

An important parameter of the block cipher is how the key is selected, which will be used on each round. In the block cipher used in GOST R 34.11-2012, the keys${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">K</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">one</span></span>}}}$ {\ displaystyle K_ {1}}   ,${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">K</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle K_ {2}}   , ...,${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">K</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">13</span></span>}}}$ {\ displaystyle K_ {13}}   for each of the 13 rounds are generated using the encryption function itself.

${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">C</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">one</span></span>}}}${\ displaystyle C_ {1}}   ,${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">C</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle C_ {2}}   , ...,${\displaystyle {\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">C</span></span>}}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">12</span></span>}}}$ {\ displaystyle C_ {12}}   - iterative constants, which are 512 bit vectors. Their values ​​are indicated in the corresponding section of the standard.

The hash function is based on the iterative Merkle-Damgor construction using MD amplification. By MD gain is meant the addition of an incomplete block when computing a hash function to a complete one by adding a vector (0 ... 01) of such a length that a complete block is obtained. Of the additional elements, the following should be noted:

• the final transformation, which consists in the fact that the compression function is applied to the checksum of all message blocks modulo 2 ⁵¹² ;
• when computing a hash code at each iteration, different compression functions are used. We can say that the compression function depends on the iteration number.

The solutions described above can withstand many well-known attacks.

A brief description of the hash function of GOST R 34.11-2012 can be represented as follows. A message of arbitrary size is fed to the input of the hash function. Further, the message is divided into blocks of 512 bits, if the message size is not a multiple of 512, then it is supplemented with the required number of bits. Then the compression function is iteratively used, as a result of which the internal state of the hash function is updated. The checksum of the blocks and the number of bits processed are also calculated. When all blocks of the original message are processed, two more calculations are performed that complete the calculation of the hash function:

• processing by the compression function of the block with the total message length.
• processing by the compression function of a block with a checksum.

The work of Alexander Kazimirov and Valentina Kazimirova ^[4] gives a graphic illustration of the calculation of the hash function.

Cryptographic Strength

Cryptanalysis of the old standard revealed some of its weaknesses from a theoretical point of view. So in one of the works ^[5] devoted to cryptanalysis GOST R 34.11-94, it was found that the complexity of the prototype algorithm is estimated at 2 ¹⁹² calculations of compression functions, collisions 2 ¹⁰⁵ , which is less than the “universal” estimates, which are for GOST R 34.11- 94 are 2 ²⁵⁶ and 2 ¹²⁸ . Although as of 2013 there is not a large number of works devoted to the cryptographic strength of the new hash function, based on the design of the new hash function, we can draw some conclusions about its cryptographic strength and suggest , that its cryptographic strength will be higher than that of GOST R 34.11-94:

• in the “Description” section of the diagram, it is seen that all message blocks are summed modulo 2 ⁵¹² and the result of summing all blocks is already fed to the input of the final stage (stage3). Due to the fact that summation is not a bitwise addition here, protection against the following attacks is obtained:

• multicollision building;
• prototype lengthening;
• differential cryptanalysis;

• the compression function uses the Miaguchi-Preneli design, this provides protection against attacks based on fixed points, since no easy methods were found for searching for fixed points for the Miaguchi-Preneli design;
• at each iteration, different constants are used to calculate the hash code. This makes it difficult to attack based on related and differential related keys, slip and reflection attacks.

In 2013, two articles on cryptanalysis of the new hash function were published on the Cryptology ePrint Archive: Listing for 2013 website. The article “Rebound attack on Stribog” ^[6] explores the stability of a hash function with respect to an attack called “The Rebound attack”; This attack is based on “rotation cryptanalysis” and differential cryptanalysis . Cryptanalysts used a method called “free-start” to search for vulnerabilities. This means that when calculating the hash code, a certain state of the hash function is fixed and further calculations can go both towards calculating the hash code and towards calculating the message. Cryptanalysts managed to achieve a collision in 5 rounds and the so-called “near collision” was received (this means that two messages were found whose hash codes are different in a small number of bits) using 7.75 rounds. It was also found that the scheme by which keys are selected for each round adds stability to the compression function. However, it was shown that collision is possible in 7.75 rounds, and “near collision” in 8.75 and 9.75, respectively.

The article “Integral Distinguishers for Reduced-round Stribog” ^[7] discusses the stability of the hash function (with a reduced number of rounds) with respect to integral cryptanalysis . The authors in the study of the compression function were able to find the differential for 4 rounds when calculating in the forward direction and for 3.5 rounds when calculating in the opposite direction. It was also found that the attack of finding the differential on a hash function with the number of rounds 6 and 7 requires 2 ⁶⁴ and 2 ¹²⁰ average round values, respectively.

To study the cryptographic strength of the new hash function, the InfoTeKS company in November 2013 announced the launch of a contest ^[8] ; It ended in May 2015 ^[9] . The winner was The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function, in which the authors presented an attack finding the second prototype for the Stribog-512 hash function, requiring ^2,266 calls of the compression function for messages longer than 2 ²⁵⁹ blocks ^[10] .

At the Crypto-2015 conference, Alex Biryukov , Leo Perrin, and Alexei Udovenko presented a report stating that the values ​​of the Grasshopper S-block cipher and the Stribog hash functions are not (pseudo) random numbers, but are generated based on a hidden algorithm , which the speakers managed to restore using reverse engineering ^{[11] [12]} .

On January 29, 2019, the study “Partitions in the S-Box of Streebog and Kuznyechik” ^[13] was published, which refutes the authors' statement about the random choice of parameters of the replacement tables in the Stribog and Kuznechik algorithms ^[14] .

Performance

The site dedicated to the VI International Conference “Parallel Computing and Control Problems” (PACO'2012) presents an article by P. A. Lebedev “Comparison of the old and new Russian standards for cryptographic hash function on CPU and NVIDIA GPUs”, which comparing the performance of a family of cryptographic hash functions GOST R 34.11-94 and GOST R 34.11-2012 on x86_64 architecture processors and NVIDIA video cards with support for CUDA technology ^[15] .

To compare the performance on the x86_64 architecture processor, 4 different hash function implementations were taken:

• implementation of GOST R 34.11-1994 from the OpenSSL cryptographic package (version 1.0.1c) with open source code. There are no algorithmic and software optimizations in this implementation;
• implementation of GOST R 34.11-1994 in the RHash program (version 1.2.9). In this implementation there are algorithmic and software optimizations, including assembler optimizations;
• implementation of GOST R 34.11-2012, written by Alexander Kazimirov ^[16] ;
• implementations of GOST R 34.11-1994 and GOST R 34.11-2012, written by P. A. Lebedev.

The processor used was an Intel Core i7-920 CPU overclocked to 2.67 GHz. Performance Results:

A comparison of the performance of the old and new hash function standards on the GPU was carried out between implementations of P. A. Lebedev. We used an NVIDIA GTX 580 graphics card. Performance results (8192 data streams over 16 KB):

Based on these results, it is concluded that the hash function of GOST R 34.11-2012 can be twice as fast as the hash function of GOST R 34.11-94 on modern processors, but slower on graphic cards and systems with limited resources.

Such performance results can be explained by the fact that when calculating a new hash function, only modulo 2 additions and data transfer instructions are used. The old hash function contains many shuffle instructions that are not best mapped to a set of CPU instructions. But the increased size of states and hash substitution tables of the GOST R 34.11-2012 hash function makes it slower on highly parallel computing tools, such as graphics processors.

Also, a study of the performance of the new hash function was conducted by its developers on a 64-bit Intel Xeon E5335 2 GHz processor. One core was used. The performance of the GOST R 34.11-2012 hash function was 51 processor cycles per 1 byte of hashed data (approximately 40 MB / s). The result is 20% better than the old hash function GOST R 34.11-94.

• At the end of the standard text examples of step-by-step calculation of a hash for several initial values ​​are given. One of these values ​​is the hexadecimal number M _{2 of} length 576 bytes from Example 2. On the x86 computer , the Little endian method is used, and a similar number in memory will be presented in an "inverted" form. If you convert this array of bytes to text according to the encoding rules of Windows-1251 , you will get: “All winds, Stribozh’s grandsons, blow arrows from the sea to the brave Igor’s plots”, which is a slightly changed line from the Word about Igor’s regiment .

• The text of the official standard GOST R 34.11-2012 in Wikisource
• RFC 6986 GOST R 34.11-2012: Hash Function
• Algebraic Aspects of the Russian Hash Standard GOST R 11/34/2012 , 2013
• Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (Full Version) , 2016