Admin: Created page with "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..."

2019-03-21T04:11:17Z

Created page with "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..."

New page

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

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 notations:
* <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 2256.
* <math>\mathcal{k}</math> — concatenation of two blocks.
* <math>+</math> — arithmetic sum of two blocks modulo 2256
* <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}, ... , 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_{out}\ =\ f(H_{in}, m)</math>,
where <math>H_{out}</math>, <math>H_{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 + ... + m_n</math>

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

So, the algorithm works as follows.

# Initialization:
## <math>h\ := 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 iterarions: 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_{out}\ =\ f(H_{in},\ m)</math>.
It consist of three parts:

* Generating of keys <math>K_1,\ K_2,\ K_3,\ K_4</math>
* Enciphering transformation <math>\ H_{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,\ i = 0, \dots, 3,\ 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''2 =
** ''C''3 =
** ''C''4 =

The algorithm:
# <math>U\ :=\ H_{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_{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 (Note: the E transformation enciphers 64-bit data using 256-bit key). For enciphering, the <math>H_{in}</math> is split into four 64-bit blocks: <math>H_{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_{in}</math>, S and m using a [[Linear feedback shift register]]. In the result, the intermediate hash value <math>H_{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} ... \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</math>, where <math>y_{16}, y_{15}, ... , y_{2}, y_{1}</math> are 16-bit sub-blocks of the ''Y''.

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

=== Initial values ===
There are two commonly used sets of initial parameters for GOST R 34.11 94.
The starting vector for the both sets is
<math>H_1</math>=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.

==== "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 2105 time, and first and second [[preimage attack]]s in 2192 time (2''n'' 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"

GOST("The quick brown fox jumps over the lazy 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 <tt>d</tt> to <tt>c</tt>:

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

Two samples coming 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

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.


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]]
* [[List of hash functions]]

==Source==

[http://wikipedia.org/ http://wikipedia.org/]

[[Category:Cryptography]]

GOST (hash function) - Revision history

Admin: Created page with "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..."