Hash functions play a crucial role in cryptography and are used in many applications such as electronic signatures, authentication, and data integrity. Since the breakdown of the MD5 and SHA-1 algorithms, cryptographers have been looking for strong and efficient hash functions. The successor to the GOST algorithm, GOST R is the hashing standard in many countries. Similar in structure to Whirlpool, it also uses an AES-like block cipher in its compression function.
A rebound attack is a technology of using degrees of freedom that can be used to find collisions for hashing algorithms based on both permutations and block ciphers. This technology was first proposed by Mendel et al. To form collision-finding attacks for the truncated Whirlpool and Grøstl algorithms. It aims to efficiently find pairs of values that match a predefined truncated differential. The search procedure is divided into two phases: an inbound state and an outbound phase. In the internal phase, the attacker makes full use of the available degrees of freedom and generates many pairs of values that satisfy the path of the truncated differential of the internal phase, which is used as starting points. Subsequently, on the visible side, these start points are checked to find pairs of values that satisfy the path of the truncated differential of the outer form.
Lamberger et al. Have leveraged this technology and obtained improved results for Whirlpool. The available degrees of freedom in the key scheme is used to extend the internal phase of the rebound attack by up to two rounds. The best performance is near-collision for a 9.5 round compression function with a labor intensity of 2176. This result was used to construct the first discrimination algorithm for the full 10-round Whirlpool compression function. Similarly, Gilbert et al. Proposed Super-Sbox technology for a rebound attack, where two rounds of AES-like transformations were treated as one layer of extended replacement. Also, the rebound attack can be used to analyze AES and AES-like block ciphers, as well as ARX ciphers. ). Recently, using an adapted rebound attack technique, Duc et al. Constructed differential characteristics for Keccak.
As an alternative to finding collisions for hash functions, Joux proposed a method for constructing multi-collision. He showed that finding a multi-collision for an iterative hash function is no more difficult than finding a single collision. Its system is used in most cases to analyze the strength of a hash function structure.
GOST R hash function
GOST R is the hashing standard in many countries. It processes 512-bit message blocks and calculates 512- or 256-bit hash values. An l-bit message is first padded to a multiple of 512 bits. One bit is appended to the end of the message; it is followed by 512 – 1 – (l mod 512) zero bits. Let M = Mt || Mt-1 || … || M1 is a message of t blocks after padding, presented in big-endian form. Then, the calculation of H (M) is described as follows:
Where IV is a predefined initial value and denotes a ring addition operation. GN (h, m) is the GOST R compression function on a 512-bit block cipher.
The E block cipher used in GOST R is a variant of AES that updates a 64-byte state (represented as an 8 x 8 array – the state can also be interpreted as 64 x 64 in the GF (2) field) and around the key, performing 12 rounds. In each round, the state is improving by performing around transform RI.
The round conversion consists of:
- The level of nonlinear transformations S, at which a table replacement is applied to each state byte;
- Byte permutation P, permuting the elements of the state matrix;
- Linear transformation L, which is an independent multiplication on the right of each status line by 64 x 64 matrix A in the field GF (2);
- Operation X [ki + 1], which performs the XOR operation of the round key ki + 1 on the state.
Calculation of the round key:
Where Ci are constants of the GOST R algorithm, and the initial value is k1. After the last round of transformation, updating the state, the output of the block cipher E, the previous state value hj-1, and the message block Mj are XORed as the output of the compression function. Let us denote the result of the round transformation RI as Ri + 1, and the intermediate states after the transformations S, P, and L as RiS, RiP, and RL, respectively.
Rebound attack on the GOST R compression function
A rebound attack is a hash function analysis technique that was first proposed by Mendel et al. To attack Grøstl and Whirlpool with a truncated number of rounds. The main idea of this technology is to construct a different path by using the available degrees of freedom to match the fragments with low probability. It usually consists of an internal phase involving match-in-the-middle and a subsequent probabilistic external state.
Using the rebound technology, we find collisions for the 4.5 and 5.5 round GOST R compression function. Moreover, using the available degrees of freedom of the principal expansion scheme, we amplify collisions for 7.5 and 9.5 rounds.
