GOST (hash function)

Template:Infobox cryptographic hash function The GOST hash function, defined in the standards GOST R 34.11-94 and GOST 34.311-95, is a 256-bit cryptographic hash function. It was initially defined in the Russian national standard GOST R 34.11-94 Information Technology - Cryptographic Information Security - Hash Function. The equivalent standard used by other member-states of the CIS is GOST 34.311-95.

The hash function is based on the GOST block cipher.

Algorithm[]

GOST processes a variable-length message into a fixed-length output of 256 bits. The input message is broken up into chunks of 256-bit blocks (eight 32-bit little endian integers); the message is padded by appending as many zeros to it as are required to bring the length of the message up to 256 bits. The remaining bits are filled up with a 256-bit integer arithmetic sum of all previously hashed blocks and then a 256-bit integer representing the length of the original message, in bits.

Basic notations[]

The algorithm descriptions uses the following notations:

• ${\displaystyle \mathcal{f}0\mathcal{g}^j}$ — j-bit block filled with zeroes.
• ${\displaystyle \mathcal{j}M\mathcal{j}}$ — length of the M block in bits modulo 2²⁵⁶.
• ${\displaystyle \mathcal{k}}$ — concatenation of two blocks.
• ${\displaystyle +}$ — arithmetic sum of two blocks modulo 2²⁵⁶
• ${\displaystyle \oplus}$ — logical xor of two blocks

Further we consider that the little-order bit is located at the left of a block, and the high-order bit at the right.

Description[]

The input message ${\displaystyle M}$ is split into 256-bit blocks ${\displaystyle m_{n}, m_{n-1}, m_{n-2}, ... , m_{1}}$. In the case the last block ${\displaystyle m_n}$ contains less than 256 bits, it is prepended left by zero bits to achieve the desired length.

Each block is processed by the step hash function ${\displaystyle H_{out}\ =\ f(H_{in}, m)}$, where ${\displaystyle H_{out}}$, ${\displaystyle H_{in}}$, ${\displaystyle m}$ are a 256-bit blocks.

Each message block, starting the first one, is processed by the step hash function ${\displaystyle f}$, to calculate intermediate hash value
${\displaystyle \!H_{i+1}=f(H_{i}, m_{i})}$
The ${\displaystyle H_1}$ value can be arbitrary chosen, and usually is ${\displaystyle 0^{256}}$.

After ${\displaystyle H_{n+1}}$ is calculated, the final hash value is obtained in the following way

• ${\displaystyle H_{n+2}\ =\ f(H_{n+1},\ L)}$, where L — is the length of the message M in bits modulo ${\displaystyle 2^{256}}$
• ${\displaystyle h\ =\ f(H_{n+2},\ K)}$, where K — is 256-bit control sum of M: ${\displaystyle m_1 + m_2 + m_3 + ... + m_n}$

The ${\displaystyle h}$ is the desired value of the hash function of the message M.

File:GOST-hash-calculation.gif

So, the algorithm works as follows.

1. Initialization:
   1. ${\displaystyle h\ := initial}$ — Initial 256-bit value of the hash function, determined by user.
   2. ${\displaystyle \Sigma\ :=\ 0}$ — Control sum
   3. ${\displaystyle L\ :=\ 0}$ — Message length
2. Compression function of internal iterarions: for i = 1 … n — 1 do the following (while ${\displaystyle |M|>256}$):
   1. ${\displaystyle h\ :=\ f(h,\ m_i)}$ - apply step hash function
   2. ${\displaystyle L\ :=\ L\ +\ 256}$ - recalculate message length
   3. ${\displaystyle \Sigma\ :=\ \Sigma\ +\ m_i}$ - calculate control sum
3. Compression function of final iteration:
   1. ${\displaystyle L\ :=\ L\ +\ \mathcal{j}\ m_n\ \mathcal{j}}$ - calculate the full message lentgh in bits
   2. ${\displaystyle m_n\ :=\ {0}^{256\ -\ \mathcal{j} m_n \mathcal{j}} \mathcal{k} m_n}$ - pad the last message with zeroes
   3. ${\displaystyle \Sigma\ :=\ \Sigma\ +\ m_n}$ - update control sum
   4. ${\displaystyle h\ :=\ f(h,\ m_n)}$ - process the last message block
   5. ${\displaystyle h\ :=\ f(h,\ L)}$ - MD - strengthen up by hashing message length
   6. ${\displaystyle h\ :=\ f(h,\ \Sigma)}$ - hash control sum
4. The output value is ${\displaystyle h}$.

The step hash function[]

The step hash function ${\displaystyle f}$ maps two 256-bit blocks into one: ${\displaystyle H_{out}\ =\ f(H_{in},\ m)}$. It consist of three parts:

• Generating of keys ${\displaystyle K_1,\ K_2,\ K_3,\ K_4}$
• Enciphering transformation ${\displaystyle \ H_{in}}$ using keys ${\displaystyle K_1,\ K_2,\ K_3,\ K_4}$
• Shuffle transformation

Generating of keys[]

The keys generating algorithm uses:

• Two transformations of 256-bit blocks:
  • Transformation ${\displaystyle A(Y)=A(y_4\ \mathcal{k}\ y_3\ \mathcal{k}\ y_2\ \mathcal{k}\ y_1) = (y_1 \oplus y_2)\ \mathcal{k}\ y_4\ \mathcal{k}\ y_3\ \mathcal{k}\ y_2}$, where ${\displaystyle y_1,\ y_2,\ y_3,\ y_4}$ are 64-bit sub-blocks of Y.
  • Transformation ${\displaystyle P(Y) = P(y_{32} \mathcal{k} y_{31} \mathcal{k} \dots \mathcal{k} y_1) = y_{\varphi(32)} \mathcal{k} y_{\varphi(31)} \mathcal{k} \dots \mathcal{k} y_{\varphi(1)}}$, where ${\displaystyle \varphi (i + 1 + 4(k - 1))= 8i + k,\ i = 0, \dots, 3,\ k = 1, \dots, 8}$, and ${\displaystyle y_{32},\ y_{31},\ \dots,\ y_{1}}$ are 8-bit sub-blocks of Y.

• Three constants:

C2 = 0
C3 = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
C4 = 0

The algorithm:

1. ${\displaystyle U\ :=\ H_{in},\quad V\ :=\ m,\quad W\ :=\ U\ \oplus\ V,\quad K_1\ =\ P(W)}$
2. For j = 2,3,4 do the following:

   ${\displaystyle U := A(U) \oplus C_j,\quad V := A(A(V)),\quad W := U \oplus V,\quad K_j = P(W)}$

Enciphering transformation[]

After the keys generation, the enciphering of ${\displaystyle H_{in}}$ is done using GOST 28147-89 in the mode of simple substitution on keys ${\displaystyle K_1, K_2, K_3, K_4}$. Let's denote the enciphering transformation as E (Note: the E transformation enciphers 64-bit data using 256-bit key). For enciphering, the ${\displaystyle H_{in}}$ is split into four 64-bit blocks: ${\displaystyle H_{in} = h_4 \mathcal{k} h_3 \mathcal{k} h_2 \mathcal{k} h_1 }$, and each of these blocks is enciphered as:

• ${\displaystyle s_1 = E(h_1, K_1)}$
• ${\displaystyle s_2 = E(h_2, K_2)}$
• ${\displaystyle s_3 = E(h_3, K_3)}$
• ${\displaystyle s_4 = E(h_4, K_4)}$

After this, the result blocks are concatenated into one 256-bit block: ${\displaystyle S = s_4 \mathcal{k} s_3 \mathcal{k} s_2 \mathcal{k} s_1}$.

Shuffle transformation[]

On the last step, the shuffle transformation is applied to ${\displaystyle H_{in}}$, S and m using a Linear feedback shift register. In the result, the intermediate hash value ${\displaystyle H_{out}}$ is obtained.

First we define the ψ function, doing LSFR on a 256-bit block: ${\displaystyle \psi(Y) = \psi(y_{16} \mathcal{k} y_{15} \mathcal{k} ... \mathcal{k} y_2 \mathcal{k} y_1) = (y_1 \oplus y_2 \oplus y_3 \oplus y_4 \oplus y_{13} \oplus y_{16}) \mathcal{k} y_{16} \mathcal{k} y_{15} \mathcal{k} ... \mathcal{k} y_3 \mathcal{k} y_2}$, where ${\displaystyle y_{16}, y_{15}, ... , y_{2}, y_{1}}$ are 16-bit sub-blocks of the Y.

File:GOST-psi-function.gif

The shuffle transformation is ${\displaystyle H_{out} = {\psi}^{61}(H_{in} \oplus \psi(m \oplus {\psi}^{12}(S)))}$ , where ${\displaystyle {\psi}^i}$ denotes an i-th power of the ${\displaystyle \psi}$ function.

File:GOST-R-34.11-94-shuffle-transformation.gif

Initial values[]

The GOST R 34.11 94 standard itself doesn't specify the algorithm initial value ${\displaystyle h}$ and S-Box of the enciphering transformation ${\displaystyle E}$, but uses the following values in the samples sections ^[1]. It should be noted that these parameters are specified by RFC 4357 as test parameters and are not recommended for use in production applications. A "production ready" parameter set is also specified as part of RFC 4357 (see section 11.2).

The starting vector

h=0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.

The S-Box for the ${\displaystyle E}$ transformation

S-box number	Value
1	4	10	9	2	13	8	0	14	6	11	1	12	7	15	5	3
2	14	11	4	12	6	13	15	10	2	3	8	1	0	7	5	9
3	5	8	1	13	10	3	4	2	14	15	12	7	6	0	9	11
4	7	13	10	1	0	8	9	15	14	4	6	12	11	2	5	3
5	6	12	7	1	5	15	13	8	4	10	9	14	0	3	11	2
6	4	11	10	0	7	2	1	13	3	6	8	5	9	12	15	14
7	13	11	4	1	3	15	5	9	0	10	14	7	6	8	2	12
8	1	15	13	0	5	7	10	4	9	2	3	14	6	11	8	12

Cryptanalysis[]

In 2007, an attack was published by M.I.T that breaks the full-round GOST hash function. The paper presents a collision attack in 2¹⁰⁵ time, and first and second preimage attacks in 2¹⁹² time.^[2]

GOST hashes[]

The following are some examples of GOST hashes:

GOST("The quick brown fox jumps over the lazy dog") =
 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

Even a small change in the message will, with overwhelming probability, result in a completely different hash due to the avalanche effect. For example, changing d to c:

GOST("The quick brown fox jumps over the lazy cog") =
 a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

Samples from the GOST R 34.11-94 standard:

GOST("This is message, length=32 bytes") =
 b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffa

GOST("Suppose the original message has length = 50 bytes") =
 471aba57a60a770d3a76130635c1fbea4ef14de51f78b4ae57dd893b62f55208

Other samples:

GOST("") =
 ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8d

GOST("a") =
 d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314dd

GOST("message digest") =
 ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4d

GOST( 128 characters of 'U' ) =
 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4

GOST( 1000000 characters of 'a' ) =
 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

See also[]

• GOST standards
• List of hash functions

References[]

• Template:Cite web
• Template:Cite web The full text of the GOST R 34.11-94 standard (in Russian).

External links[]

• C implementation and test vectors for GOST hash function from Markku-Juhani Saarinen, also contains draft translations into English of the GOST 28147-89 and GOST R 34.11-94 standards. Bugfixed version, see [1].
• Ecrypt page
• RHash, an open source command-line tool, which can calculate and verify GOST hash.

Cryptography navbox Block ciphers AES - Blowfish - DES - Serpent - Twofish

it:GOST (hash) ru:ГОСТ Р 34.11-94