Gost-Hash
Encyclopedia
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.
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.
Further we consider that the little-order bit is located at the left of a block, and the high-order bit at the right.
is split into 256-bit blocks 
.
In the case the last block
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
,
where
, 
, 
are a 256-bit blocks.
Each message block, starting the first one, is processed by the step hash function
, to calculate intermediate hash value
The
value can be arbitrary chosen, and usually is 
.
After
is calculated, the final hash value is obtained in the following way
The
is the desired value of the hash function of the message M.
So, the algorithm works as follows.
maps two 256-bit blocks into one: 
.
It consist of three parts:
C2 = 0
C3 = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
C4 = 0
The algorithm:
is done using GOST 28147-89 in the mode of simple substitution on keys 
.
Let's denote the enciphering transformation as E (Note: the E transformation enciphers 64-bit data using 256-bit key). For enciphering, the
is split into four 64-bit blocks: 
, and each of these blocks is enciphered as:
After this, the result blocks are concatenated into one 256-bit block:
.
, S and m using a Linear feedback shift register
. In the result, the intermediate hash value
is obtained.
First we define the ψ function, doing LSFR on a 256-bit block:
, where 
are 16-bit sub-blocks of the Y.
The shuffle transformation is
, where 
denotes an i-th power of the 
function.
The starting vector for the both sets is
=0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.
Although the GOST R 34.11 94 standard itself doesn't specify the algorithm initial value
and S-Box of the enciphering transformation 
, but uses the following “test parameters” in the samples sections.
!S-box number
! colspan=16 | Value
|-
!1
|4> 10
9
2
13
8
0
14
6
11
1
12
7
15
5
!2
|14 11
4
12
6
13
15
10
2
3
8
1
0
7
5
!3
|5 8
1
13
10
3
4
2
14
15
12
7
6
0
9
!4
|7 13
10
1
0
8
9
15
14
4
6
12
11
2
5
!5
|6 12
7
1
5
15
13
8
4
10
9
14
0
3
11
!6
|4 11
10
0
7
2
1
13
3
6
8
5
9
12
15
!7
|13 11
4
1
3
15
5
9
0
10
14
7
6
8
2
!8
|1 15
13
0
5
7
10
4
9
2
3
14
6
11
8
!S-box number
! colspan=16 | Value
|-
!1
|10> 4
5
6
8
1
3
7
13
12
14
0
9
2
11
!2
| 5 15
4
0
2
13
11
9
1
7
6
3
12
14
10
!2
| 7 15
12
14
9
4
1
0
3
11
5
2
6
10
8
!4
| 4 10
7
12
0
15
2
8
14
1
6
5
13
11
9
!5
| 7 6
4
11
9
12
2
10
1
8
0
14
15
13
3
!6
| 7 6
2
4
13
9
15
0
10
1
5
11
8
14
12
!7
|13 14
4
1
7
0
5
10
3
12
8
15
6
2
9
!8
| 1 3
10
9
5
11
4
15
8
6
7
14
13
0
2
in 2105 time, and first and second preimage attack
s in 2192 time.
Here are test vectors for the GOST hash with “Test parameters”
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
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
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
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
. 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
Commonwealth of Independent States
The Commonwealth of Independent States is a regional organization whose participating countries are former Soviet Republics, formed during the breakup of the Soviet Union....
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 endianEndianness
In computing, the term endian or endianness refers to the ordering of individually addressable sub-components within the representation of a larger data item as stored in external memory . Each sub-component in the representation has a unique degree of significance, like the place value of digits...
integers); the message is padded
Padding (cryptography)
-Classical cryptography:Official messages often start and end in predictable ways: My dear ambassador, Weather report, Sincerely yours, etc. The primary use of padding with classical ciphers is to prevent the cryptanalyst from using that predictability to find cribs that aid in breaking the...
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:-
— j-bit block filled with zeroes. -
— length of the M block in bits modulo 2256. -
— concatenation of two blocks. -
— arithmetic sum of two blocks modulo 2256 -
— 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 is split into 256-bit blocks .In the case the last block
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
,where
, , are a 256-bit blocks.Each message block, starting the first one, is processed by the step hash function
, to calculate intermediate hash value The
value can be arbitrary chosen, and usually is .After
is calculated, the final hash value is obtained in the following way
-
, where L — is the length of the message M in bits modulo 
-
, where K — is 256-bit control sum of M: 
The
is the desired value of the hash function of the message M.So, the algorithm works as follows.
- Initialization:
-
— Initial 256-bit value of the hash function, determined by user. -
— Control sum -
— Message length
-
- Compression function of internal iterarions: for i = 1 … n — 1 do the following (while
):
-
- apply step hash function -
- recalculate message length -
- calculate control sum
-
- Compression function of final iteration:
-
- calculate the full message lentgh in bits -
- pad the last message with zeroes -
- update control sum -
- process the last message block -
- MD - strengthen up by hashing message length -
- hash control sum
-
- The output value is
.
The step hash function
The step hash function maps two 256-bit blocks into one: .It consist of three parts:
- Generating of keys
- Enciphering transformation
using keys 
- Shuffle transformation
Generating of keys
The keys generating algorithm uses:- Two transformations of 256-bit blocks:
- Transformation
, where 
are 64-bit sub-blocks of Y. - Transformation
, where 
, and 
are 8-bit sub-blocks of Y.
- Transformation
- Three constants:
C2 = 0
C3 = 0xff00ffff000000ffff0000ff00ffff0000ff00ff00ff00ffff00ff00ff00ff00
C4 = 0
The algorithm:
-
- For j = 2,3,4 do the following:
-
Enciphering transformation
After the keys generation, the enciphering of is done using GOST 28147-89 in the mode of simple substitution on keys .Let's denote the enciphering transformation as E (Note: the E transformation enciphers 64-bit data using 256-bit key). For enciphering, the
is split into four 64-bit blocks: , and each of these blocks is enciphered as:
After this, the result blocks are concatenated into one 256-bit block:
.Shuffle transformation
On the last step, the shuffle transformation is applied to, S and m using a Linear feedback shift registerLinear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
. In the result, the intermediate hash value
is obtained.First we define the ψ function, doing LSFR on a 256-bit block:
, where are 16-bit sub-blocks of the Y.The shuffle transformation is
, where denotes an i-th power of the function.Initial values
There are two commonly used sets of initial parameters.The starting vector for the both sets is
=0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.Although the GOST R 34.11 94 standard itself doesn't specify the algorithm initial value
and S-Box of the enciphering transformation , but uses the following “test parameters” in the samples sections.The ‘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.! colspan=16 | Value
|-
!1
|4>
!2
|14
!3
|5
!4
|7
!5
|6
!6
|4
!7
|13
!8
|1
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.! colspan=16 | Value
|-
!1
|10>
!2
| 5
!2
| 7
!4
| 4
!5
| 7
!6
| 7
!7
|13
!8
| 1
Cryptanalysis
In 2008, an attack was published that breaks the full-round GOST hash function. The paper presents a collision attackCollision attack
In cryptography, a collision attack on a cryptographic hash tries to find two arbitrary inputs that will produce the same hash value, i.e. a hash collision...
in 2105 time, and first and second preimage attack
Preimage attack
In cryptography, the preimage attack is a classification of attacks on hash functions for finding a message that has a specific hash value.There are two types of preimage attacks:...
s in 2192 time.
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 dog") =
77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294
Even a small change in the message will, with overwhelming probability, result in a completely different hash due to the avalanche effect
Avalanche effect
In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...
. For example, changing d to c:
GOST("The quick brown fox jumps over the lazy cog") =
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
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 http://www.autochthonous.org/crypto/.
- RHash, an open sourceOpen sourceThe term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
command-line tool, which can calculate and verify GOST hash (supports both parameter sets). - http://ideone.com/QNhxWImplementation of the GOST R 34.11-94 in JavaScriptJavaScriptJavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
] (CryptoPro parameters) - The GOST Hash Function Ecrypt page