GOST (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.

This function must not be confused with a different Streebog hash function, which is defined in the new revision of the standard GOST R 34.11-2012.

The GOST 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 notation

The algorithm descriptions uses the following notation:

• f 0 g j {\displaystyle {\mathcal {f}}0{\mathcal {g}}^{j}} — j-bit block filled with zeroes.
• j M j {\displaystyle {\mathcal {j}}M{\mathcal {j}}} — length of the M block in bits modulo 2256.
• k {\displaystyle {\mathcal {k}}} — concatenation of two blocks.
• + {\displaystyle +} — arithmetic sum of two blocks modulo 2256.
• ⊕ {\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 M {\displaystyle M} is split into 256-bit blocks m n , m n − 1 , m n − 2 , … , m 1 {\displaystyle m_{n},\,m_{n-1},\,m_{n-2},\,\ldots ,\,m_{1}}. In the case the last block m n {\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 H out = f ( H in , m ) {\displaystyle H_{\text{out}}=f(H_{\text{in}},\,m)}, where H out {\displaystyle H_{\text{out}}}, H in {\displaystyle H_{\text{in}}}, m {\displaystyle m} are a 256-bit blocks.

Each message block, starting the first one, is processed by the step hash function f {\displaystyle f}, to calculate intermediate hash value

H i + 1 = f ( H i , m i ) {\displaystyle \!H_{i+1}=f(H_{i},\,m_{i})}

The H 1 {\displaystyle H_{1}} value can be arbitrary chosen, and usually is 0 256 {\displaystyle 0^{256}}.

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

• H n + 2 = f ( H n + 1 , L ) {\displaystyle H_{n+2}=f(H_{n+1},\,L)}, where L — is the length of the message M in bits modulo 2 256 {\displaystyle 2^{256}}
• h = f ( H n + 2 , K ) {\displaystyle h=f(H_{n+2},\,K)}, where K — is 256-bit control sum of M: m 1 + m 2 + m 3 + … + m n {\displaystyle m_{1}+m_{2}+m_{3}+\ldots +m_{n}}

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

So, the algorithm works as follows.

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

Step hash function

The step hash function f {\displaystyle f} maps two 256-bit blocks into one: H out = f ( H in , m ) {\displaystyle H_{\text{out}}=f(H_{\text{in}},\,m)}.

It consist of three parts:

• Generating of keys K 1 , K 2 , K 3 , K 4 {\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}
• Enciphering transformation H in {\displaystyle H_{\text{in}}} using keys K 1 , K 2 , K 3 , K 4 {\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}
• Shuffle transformation

Key generation

The keys generating algorithm uses:

• Two transformations of 256-bit blocks: Transformation A ( Y ) = A ( y 4 k y 3 k y 2 k y 1 ) = ( y 1 ⊕ y 2 ) k y 4 k y 3 k y 2 {\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 y 1 , y 2 , y 3 , y 4 {\displaystyle y_{1},\,y_{2},\,y_{3},\,y_{4}} are 64-bit sub-blocks of Y. Transformation P ( Y ) = P ( y 32 k y 31 k … k y 1 ) = y φ ( 32 ) k y φ ( 31 ) k … k y φ ( 1 ) {\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 φ ( i + 1 + 4 ( k − 1 ) ) = 8 i + k , i = 0 , … , 3 , k = 1 , … , 8 {\displaystyle \varphi (i+1+4(k-1))=8i+k,\quad i=0,\,\dots ,\,3,\quad k=1,\,\dots ,\,8}, and y 32 , y 31 , … , y 1 {\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. U := H in , V := m , W := U ⊕ V , K 1 = P ( W ) {\displaystyle U:=H_{\text{in}},\quad V:=m,\quad W:=U\ \oplus \ V,\quad K_{1}=P(W)}
2. For j = 2, 3, 4 do the following: U := A ( U ) ⊕ C j , V := A ( A ( V ) ) , W := U ⊕ V , K j = P ( W ) {\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 H in {\displaystyle H_{\text{in}}} is done using GOST 28147-89 in the mode of simple substitution on keys K 1 , K 2 , K 3 , K 4 {\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}. Let's denote the enciphering transformation as E (enciphering 64-bit data using 256-bit key). For enciphering, the H in {\displaystyle H_{\text{in}}} is split into four 64-bit blocks: H in = h 4 k h 3 k h 2 k h 1 {\displaystyle H_{\text{in}}=h_{4}{\mathcal {k}}h_{3}{\mathcal {k}}h_{2}{\mathcal {k}}h_{1}}, and each of these blocks is enciphered as:

• s 1 = E ( h 1 , K 1 ) {\displaystyle s_{1}=E(h_{1},\,K_{1})}
• s 2 = E ( h 2 , K 2 ) {\displaystyle s_{2}=E(h_{2},\,K_{2})}
• s 3 = E ( h 3 , K 3 ) {\displaystyle s_{3}=E(h_{3},\,K_{3})}
• s 4 = E ( h 4 , K 4 ) {\displaystyle s_{4}=E(h_{4},\,K_{4})}

After this, the result blocks are concatenated into one 256-bit block: S = s 4 k s 3 k s 2 k s 1 {\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 H in {\displaystyle H_{\text{in}}}, S and m using a linear-feedback shift register. In the result, the intermediate hash value H out {\displaystyle H_{\text{out}}} is obtained.

First we define the ψ function, doing LFSR on a 256-bit block:

ψ ( Y ) = ψ ( y 16 k y 15 k … k y 2 k y 1 ) = ( y 1 ⊕ y 2 ⊕ y 3 ⊕ y 4 ⊕ y 13 ⊕ y 16 ) k y 16 k y 15 k … k y 3 k y 2 {\displaystyle \psi (Y)=\psi (y_{16}{\mathcal {k}}y_{15}{\mathcal {k}}\ldots {\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}}\ldots {\mathcal {k}}y_{3}{\mathcal {k}}y_{2}},

where y 16 , y 15 , … , y 2 , y 1 {\displaystyle y_{16},y_{15},\ldots ,y_{2},y_{1}} are 16-bit sub-blocks of the Y.

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

Initial values

There are two commonly used sets of initial parameters for GOST R 34.11 94. The starting vector for both the sets is

H 1 {\displaystyle H_{1}} = 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.

Although the GOST R 34.11 94 standard itself doesn't specify the algorithm initial value H 1 {\displaystyle H_{1}} and S-box of the enciphering transformation E {\displaystyle E}, but uses the following "test parameters" in the samples sections.

"Test parameters" S-box

RFC 5831 specifies only these parameters, but RFC 4357 names them as "test parameters" and does not recommend them for use in production applications.

CryptoPro S-box

The CryptoPro S-box comes from "production ready" parameter set developed by CryptoPro company, it is also specified as part of RFC 4357, section 11.2.

Cryptanalysis

In 2008, an attack was published that breaks the full-round GOST hash function. The paper presents a collision attack in 2105 time, and first and second preimage attacks in 2192 time (2n time refers to the approximate number of times the algorithm was calculated in the attack).

GOST hash test vectors

Hashes for "test parameters"

The 256-bit (32-byte) GOST hashes are typically represented as 64-digit hexadecimal numbers.

Here are test vectors for the GOST hash with "test parameters"

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:

Two samples coming from the GOST R 34.11-94 standard:

More test vectors:

Hashes for CryptoPro parameters

GOST algorithm with CryptoPro S-box generates different set of hash values.

See also

• Kupyna
• Hash function security summary
• GOST standards
• List of hash functions

Further reading

• RFC–"GOST 28147-89: Encryption, Decryption, and Message Authentication Code (MAC) Algorithms,"Informational.
• . 2010-02-20. The full text of the GOST R 34.11-94 standard (in Russian).

External links

• 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 .
• [permanent dead link].
• , an open source command-line tool, which can calculate and verify GOST hash (supports both parameter sets).
• ()
• 2014-11-06 at theWayback Machine