View source for GOST (hash function)

{{Short description|Russian cryptographic hash function}}
{{Infobox cryptographic hash function
| name           = GOST R 34.11-94
| image          = 
| caption        = 
<!-- General -->
| designers      = [[FAPSI]] and VNIIstandart ([[USSR]])
| publish date   = 1994-05-23 (declassified)
| series         = 
| derived from   = [[GOST (block cipher)|GOST block cipher]]
| derived to     = [[Streebog]]
| related to     = 
| certification  = [[GOST|GOST standard]]
<!-- Detail -->
| digest size    = 256 bits
| structure      = 
| rounds         = 32
| cryptanalysis  = A 2008 attack breaks the full-round hash function. The paper presents a [[collision attack]] in 2<sup>105</sup> time, and [[preimage attack]]s in 2<sup>192</sup> time.<ref name=gost-2008 />
}}
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 [[Commonwealth of Independent States|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'''.<ref>[https://www.streebog.net/ GOST R 34.11-2012: Streebog Hash Function]</ref>

The GOST hash function is based on the [[GOST (block cipher)|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 [[endianness|little endian]] integers); the message is [[padding (cryptography)|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:
* <math>\mathcal{f}0\mathcal{g}^j</math> — j-bit block filled with zeroes.
* <math>\mathcal{j}M\mathcal{j}</math> — length of the M block in bits modulo 2<sup>256</sup>.
* <math>\mathcal{k}</math> — concatenation of two blocks.
* <math>+</math> — arithmetic sum of two blocks modulo 2<sup>256</sup>.
* <math>\oplus</math> — 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 <math>M</math> is split into 256-bit blocks <math>m_{n},\, m_{n-1},\, m_{n-2},\, \ldots,\, m_{1}</math>. In the case the last block <math>m_{n}</math> 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 <math>H_\text{out} = f(H_\text{in},\, m)</math>, where <math>H_\text{out}</math>, <math>H_\text{in}</math>, <math>m</math> are a 256-bit blocks.

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

After <math>H_{n+1}</math> is calculated, the final hash value is obtained in the following way
* <math>H_{n+2} = f(H_{n+1},\, L)</math>, where L — is the length of the message M in bits modulo <math>2^{256}</math>
* <math>h = f(H_{n+2},\, K)</math>, where K — is 256-bit control sum of M: <math>m_1 + m_2 + m_3 + \ldots + m_n</math>

The <math>h</math> is the desired value of the hash function of the message M.

[[File:GOST-hash-calculation.svg]]

So, the algorithm works as follows.

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

=== Step hash function ===
The step hash function <math>f</math> maps two 256-bit blocks into one: <math>H_\text{out} = f(H_\text{in},\, m)</math>.

It consist of three parts:
[[File:GOST-step-hash-function.svg|left]]
* Generating of keys <math>K_1,\, K_2,\, K_3,\, K_4</math>
* Enciphering transformation <math>H_\text{in}</math> using keys <math>K_1,\, K_2,\, K_3,\, K_4</math>
* Shuffle transformation

==== Key generation ====
The keys generating algorithm uses:

* Two transformations of 256-bit blocks:
** Transformation <math>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</math>, where <math>y_1,\, y_2,\, y_3,\, y_4</math> are 64-bit sub-blocks of ''Y''.
** Transformation <math>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)}</math>, where <math>\varphi(i + 1 + 4(k - 1)) = 8i + k,\quad i = 0,\, \dots,\, 3,\quad k = 1,\, \dots,\, 8</math>, and <math>y_{32},\, y_{31},\, \dots,\, y_{1}</math> are 8-bit sub-blocks of ''Y''.
* Three constants:
** ''C''<sub>2</sub> = {{mono|0}}
** ''C''<sub>3</sub> = {{mono|0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00}}
** ''C''<sub>4</sub> = {{mono|0}}

The algorithm:
# <math>U := H_\text{in},\quad V := m,\quad W := U\ \oplus\ V,\quad K_1 = P(W)</math>
# For ''j'' = 2, 3, 4 do the following:
#: <math>U := A(U) \oplus C_j,\quad V := A(A(V)),\quad W := U \oplus V,\quad K_j = P(W)</math>

==== Enciphering transformation ====
After the keys generation, the enciphering of <math>H_\text{in}</math> is done using [[GOST (block cipher)|GOST 28147-89]] in the mode of simple substitution on keys <math>K_1,\, K_2,\, K_3,\, K_4</math>.
Let's denote the enciphering transformation as E (enciphering 64-bit data using 256-bit key). For enciphering, the <math>H_\text{in}</math> is split into four 64-bit blocks: <math>H_\text{in} = h_4 \mathcal{k} h_3 \mathcal{k} h_2 \mathcal{k} h_1 </math>, and each of these blocks is enciphered as:
* <math>s_1 = E(h_1,\, K_1)</math>
* <math>s_2 = E(h_2,\, K_2)</math>
* <math>s_3 = E(h_3,\, K_3)</math>
* <math>s_4 = E(h_4,\, K_4)</math>
After this, the result blocks are concatenated into one 256-bit block: <math>S = s_4 \mathcal{k} s_3 \mathcal{k} s_2 \mathcal{k} s_1</math>.

==== Shuffle transformation ====
On the last step, the shuffle transformation is applied to <math>H_\text{in}</math>, S and m using a [[linear-feedback shift register]]. In the result, the intermediate hash value <math>H_\text{out}</math> is obtained.

First we define the ψ function, doing [[LFSR]] on a 256-bit block:
: <math>\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</math>,
where <math>y_{16}, y_{15}, \ldots, y_{2}, y_{1}</math> are 16-bit sub-blocks of the ''Y''.

[[File:GOST-psi-function.svg]]

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

[[File:GOST-R-34.11-94-shuffle-transformation.svg]]

=== 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
: <math>H_1</math> = {{mono|0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000}}.

Although the GOST R 34.11 94 standard itself doesn't specify the algorithm initial value <math>H_1</math> and [[S-box]] of the enciphering transformation <math>E</math>, but uses the following "test parameters" in the samples sections.<ref name=gost-94-addition-A>{{cite journal |year=1994  |title=GOST R 34.11-94 standard. Information technology. Cryptographic data security. Hashing function. Addition A. |url=http://protect.gost.ru/document.aspx?control=7&id=134550}}</ref>

==== "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.

{| class="wikitable" style="text-align: right"
 !S-box number
 ! colspan=16 | 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
 |}

==== 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.

{| class="wikitable" style="text-align: right"
 !S-box number
 ! colspan=16 | Value
 |-
 !1
 |10|| 4|| 5|| 6|| 8|| 1|| 3|| 7|| 13|| 12|| 14|| 0|| 9|| 2|| 11|| 15
 |-
 !2
 | 5|| 15|| 4|| 0|| 2|| 13|| 11|| 9|| 1|| 7|| 6|| 3|| 12|| 14|| 10|| 8
 |-
 !3
 | 7|| 15|| 12|| 14|| 9|| 4|| 1|| 0|| 3|| 11|| 5|| 2|| 6|| 10|| 8|| 13
 |-
 !4
 | 4|| 10|| 7|| 12|| 0|| 15|| 2|| 8|| 14|| 1|| 6|| 5|| 13|| 11|| 9|| 3
 |-
 !5
 | 7|| 6|| 4|| 11|| 9|| 12|| 2|| 10|| 1|| 8|| 0|| 14|| 15|| 13|| 3|| 5
 |-
 !6
 | 7|| 6|| 2|| 4|| 13|| 9|| 15|| 0|| 10|| 1|| 5|| 11|| 8|| 14|| 12|| 3
 |-
 !7
 |13|| 14|| 4|| 1|| 7|| 0|| 5|| 10|| 3|| 12|| 8|| 15|| 6|| 2|| 9|| 11
 |-
 !8
 | 1|| 3|| 10|| 9|| 5|| 11|| 4|| 15|| 8|| 6|| 7|| 14|| 13|| 0|| 2|| 12
 |}

==Cryptanalysis==
In 2008, an attack was published that breaks the full-round GOST hash function. The paper presents a [[collision attack]] in 2<sup>105</sup> time, and first and second [[preimage attack]]s in 2<sup>192</sup> time (2<sup>''n''</sup> time refers to the approximate number of times the algorithm was calculated in the attack).<ref name="gost-2008">{{cite book | title=Advances in Cryptology – CRYPTO 2008 | publisher=[[Springer Berlin Heidelberg]] | year=2008 | location=[[Germany]] | pages=162–178 | isbn=978-3-540-85173-8 | volume=5157 | doi=10.1007/978-3-540-85174-5_10 | series=Lecture Notes in Computer Science | chapter=Cryptanalysis of the GOST Hash Function | first1=Florian | last1=Mendel | first2=Norbert | last2=Pramstaller | last3=Rechberger | first3=Christian | last4=Kontak | first4=Marcin | last5=Szmidt | first5=Janusz | editor-last=Wagner | editor-first=David}}</ref>

==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"

 GOST("The quick brown fox jumps over the lazy {{Background color|#87CEEB|d}}og") =
  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 {{mono|d}} to {{mono|c}}:

 GOST("The quick brown fox jumps over the lazy {{Background color|#87CEEB|c}}og") =
  a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

Two samples coming from the GOST R 34.11-94 standard:<ref name=gost-94-addition-A/>

 GOST("This is message, length=32 bytes") =
  b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffa
 
 GOST("Suppose the original message has length = 50 bytes") =
  471aba57a60a770d3a76130635c1fbea4ef14de51f78b4ae57dd893b62f55208

More test vectors:
 GOST("") =
  ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8d
 
 GOST("a") =
  d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314dd
 
 GOST("message digest") =
  ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4d
 
 GOST( 128 characters of 'U' ) =
  53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4
 
 GOST( 1000000 characters of 'a' ) =
  5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

===Hashes for CryptoPro parameters===
GOST algorithm with CryptoPro S-box generates different set of hash values.

<!-- test vectors from gosthash.chat.ru (Rus), can be verified by programs from links section -->
 GOST("") = 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0
 
 GOST("a") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011
 
 GOST("abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42c
 
 GOST("message digest") =
   bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0
 
 GOST("The quick brown fox jumps over the lazy dog") =
   9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76
 
 GOST("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
   73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61
 
 GOST("12345678901234567890123456789012345678901234567890123456789012345678901234567890") =
   6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90
 
 GOST("This is message, length=32 bytes") =
   2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48eb
 
 GOST("Suppose the original message has length = 50 bytes") =
   c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011
 
 GOST(128 of "U") = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8
 
 GOST(1000000 of "a") = 8693287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

== See also ==
* [[Kupyna]]
* [[Hash function security summary]]
* [[GOST|GOST standards]]
* [[List of hash functions]]

==References==
{{reflist}}

===Further reading===
* {{cite journal |date=March 2010 |url=http://tools.ietf.org/html/rfc5831 |title=GOST R 34.11-94: Hash Function Algorithm |publisher=IETF |doi=10.17487/RFC5831 |editor-last1=Dolmatov |editor-first1=V |last1=Dolmatov |first1=V. |doi-access=free }}
* {{cite web |date=2010-02-20 |url=http://protect.gost.ru/document.aspx?control=7&id=134550 |title=Information technology. Cryptographic data security. Hashing function}} The full text of the GOST R 34.11-94 standard (in Russian).

==External links==
* [http://www.autochthonous.org/crypto/gosthash.tar.gz 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 [http://www.autochthonous.org/crypto/].
* [http://garbage.us.to/static/GostShifr.zip C++ implementation with STL streams]{{dead link|date=October 2017 |bot=InternetArchiveBot |fix-attempted=yes }}.
* [http://rhash.sourceforge.net/ RHash], an [[open source]] command-line tool, which can calculate and verify GOST hash (supports both parameter sets).
* [https://web.archive.org/web/20120526072318/http://ideone.com/QNhxW Implementation of the GOST R 34.11-94 in JavaScript] ([https://web.archive.org/web/20120526072333/http://ideone.com/LYNnw CryptoPro parameters])
* [http://ehash.iaik.tugraz.at/wiki/GOST The GOST Hash Function Ecrypt page]
* [https://quickhash.com/hash-gost-online Online GOST Calculator] {{Webarchive|url=https://web.archive.org/web/20141106001314/https://quickhash.com/hash-gost-online |date=2014-11-06 }}

{{Cryptography navbox | hash}}

{{DEFAULTSORT:Gost (Hash Function)}}
[[Category:Broken hash functions]]
[[Category:Cryptographic hash functions]]
[[Category:GOST standards]]