This is a purely informative rendering of an RFC that includes verified errata. This rendering may not be used as a reference.
The following 'Verified' errata have been incorporated in this document:
EID 2303, EID 2863, EID 4262
Independent Submission V. Dolmatov, Ed.
Request for Comments: 5831 Cryptocom, Ltd.
Category: Informational March 2010
ISSN: 2070-1721
GOST R 34.11-94: Hash Function Algorithm
Abstract
This document is intended to be a source of information about the
Russian Federal standard hash function (GOST R 34.11-94), which is
one of the Russian cryptographic standard algorithms (called GOST
algorithms). Recently, Russian cryptography is being used in
Internet applications, and this document has been created as
information for developers and users of GOST R 34.11-94 for hash
computation.
Status of This Memo
This document is not an Internet Standards Track specification; it is
published for informational purposes.
This is a contribution to the RFC Series, independently of any other
RFC stream. The RFC Editor has chosen to publish this document at
its discretion and makes no statement about its value for
implementation or deployment. Documents approved for publication by
the RFC Editor are not a candidate for any level of Internet
Standard; see Section 2 of RFC 5741.
Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
http://www.rfc-editor.org/info/rfc5831.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document.
This document may not be modified, and derivative works of it may not
be created, except to format it for publication as an RFC or to
translate it into languages other than English.
Table of Contents
1. Introduction ....................................................3
1.1. General Information ........................................3
1.2. The Purpose of GOST R 34.11-94 .............................3
2. Applicability ...................................................3
3. Conventions Used in This Document ...............................4
4. General Statements ..............................................5
5. Step-by-Step Hash Function ......................................5
5.1. Key Generation .............................................5
5.2. Encryption Transformation ..................................7
5.3. Mixing Transformation ......................................7
6. The Calculation Procedure for a Hash Function ...................8
7. Test Examples (Informative) .....................................9
7.1. Usage of the Algorithm GOST 28147-89 ......................10
7.2. Representation of Vectors .................................11
7.3. Examples of the Hash Value Calculation ....................11
7.3.1. Hash Calculation for the Sample Message M ..........11
7.3.2. Hash Calculation for the Sample Message M ..........14
8. Security Considerations ........................................16
9. Normative References ...........................................16
10. Contributors ..................................................17
1. Introduction
1.1 _M_ := M.
1.2 H := h0.
2. Applicability
GOST R 34.11-94 defines an algorithm and procedure for the
calculation of a hash function for an arbitrary sequence of binary
symbols. These algorithms and procedures should be applied in
cryptographic methods of data processing and securing, including
digital signature procedures employed for data transfer and data
storage in computer-aided systems.
The hash function, defined in GOST R 34.11-94, is used for digital
signature systems based on the asymmetric cryptographic algorithm
according to GOST R 34.10-2001 (see section 3).
3. Conventions Used in This Document
The following notations are used in GOST R 34.11-94:
V_all is a set of all finite words in the alphabet V = {0,1}. The
words are read from right to left and the alphabet symbols are
numbered from right to left (i.e., the rightmost symbol of the word
has the number one, the second rightmost symbol has number two,
etc.).
Vk is a set of all words in alphabet V = {0,1} of length k bits
(k=16,64,256).
|A| is the length of a word A belonging to V_all.
A||B is a concatenation of words A, B belonging to V_all. Its length
is |A| + |B|, where the left |A| symbols come from the word A, and
the right |B| symbols come from the word B. One can also use the
notation A||B = A * B.
A^k is a concatenation of k copies of the word A (A belongs to
V_all).
<N>_k is a word of length k, containing a binary representation of
N(mod 2^k) residue, with a non-negative integer N.
A^$ is a non-negative integer with A as its binary representation.
(xor) is the bitwise modulo 2 addition of the words of the same
length.
(+)' is the addition according to the rule A (+)' B = <A^$+ B^$>_k,
where k = |A| = |B|.
M is a binary sequence to be hashed, M belongs to V_all. M is a
message in digital signature systems.
h is a hash function that maps the sequence M belonging to V_all onto
the word h(M) belonging to V_256.
E(k,A) is a result of the encryption of the word A using key K with
the encryption algorithm according to [GOST28147] in the electronic
codebook (ECB) mode (K belongs to V256, A belongs to V64).
h0 is an initial hash value.
e := g is the assignment of the value g to the parameter e.
^ is the power operator.
i = 1..8 is an interval with i being all the values from 1 to 8.
hUZ is the S-boxes described in [GOST28147].
4. General Statements
A hash function h is the mapping h : V_all -> V256, depending on the
parameter (which is the initial hash value H, H is a word from V256).
To define the hash function, it is necessary to have:
- a calculation algorithm for the step-by-step hash function
chi : V256 x V256 -> V256
- a description of an iterative procedure for calculating the hash
value h
A hash function h depends on two parameters, h0 and hUZ.
5. Step-by-Step Hash Function
A calculation algorithm for the step-by-step hash function contains
three parts, which successively do:
- key generation, here keys are 256-bit words;
- an encryption transformation, that is encryption of 64-bit
subwords of word H using keys K[i], (i = 1, 2, 3, 4) with the
algorithm according to [GOST28147] in ECB mode; and
- a mixing transformation for the result of the encryption.
5.1 Key Generation
Consider X = (b[256], b[255], ..., b[1]) belongs to V256.
Let:
X = x[4]||x[3]||x[2]||x[1] = eta[16]||[eta15]||...||eta[1]
= xi[32]||xi[31]||...||xi[1], where
x[i] = (b[i*64],...,b[(i-1)*64+1]) belongs to V64, i = 1..4,
eta[j] = (b[j*16],...,b[(j-1)*16+1]) belongs to V16, j = 1..16,
xi[k] = (b[k*8],..., b[(k-1)*8+1]) belongs to V8, k = 1..32.
Yet, another notation: A(X) = (x[1](xor)x[2])||x[4]||x[3]||x[2].
The transformation P : V256 -> V256 maps the word xi32||...||xi1
onto the word xi[phi(32)] || ... || xi[phi(1)],
where phi(i + 1 + 4 ( k - 1) ) = 8i + k , i = 0..3, k = 1..8.
For the key generation, one should use the following initial data:
- words H, M belonging to V256,
- parameters: words C[i] (i = 2, 3, 4), with values:
C[2] = C[4] = 0^256;
C[3] = 1^8||0^8||1^16||0^24||1^16||0^8||(0^8||1^8)^2||1^8||0^8
||(0^8||1^8)^4||(1^8||0^8 )^4.
The following algorithm is used for the key calculation:
1. Assign values:
i := 1, U := H , V := M.
2. Calculate:
W = U (xor) V , K[i] = P(W).
3. Assign:
i := i + 1.
4. Verify condition:
i = 5.
If it is true, go to step 7. If not, go to step 5.
5. Calculate:
U := A(U)(xor)C[i], V := A(A(V)),
W := U(xor)V, K[i] = P(W).
6. Go to step 3.
7. End.
5.2. Encryption Transformation
At this stage, 64-bit subwords of the word H are encrypted using keys
K[i] (i = 1, 2, 3, 4).
For the encryption transformation, one should use the following
initial data:
H = h[4]||h[3]||h[2]||h[1],
where h[i] belongs to V64, i = 1,2,3,4, and a key set is K[1], K[2],
K[3], K[4].
The encryption algorithm is applied and the following words are
obtained:
s[i] = E(K[i],h[i]), where: i = 1,2,3,4
As a result of the stage, the following sequence is formed:
S = s[4]||s[3]||s[2]||s[1].
5.3. Mixing Transformation
At this stage, the obtained sequence is mixed using a shift register.
The initial data includes words H, M belonging to V256 and a word S
belonging to V256 .
Let a mapping PSI(X) : V256(2) -> V256(2) transform the word:
eta[16]||eta[15]||...||eta[1], eta[i] belongs to V16, i = 1..16
into the word:
eta[1](xor)eta[2](xor)eta[3](xor)eta[4](xor)eta[13](xor)eta[16]
||eta[16]||...||eta[2].
Then, the value of the step-by-step hash function value is the word:
chi(M, H) = PSI^61(H(xor)PSI(M(xor)PSI^12(S))),
where PSI^i(X) is the transformation PSI applied i times to X.
6. The Calculation Procedure for a Hash Function
The calculation procedure for a hash function h is assumed to be
applied to a sequence M belonging to V_all. Its parameter is an
initial hash value h0, which is an arbitrarily fixed word from V256.
The calculation procedure for the function h uses the following
quantities at each step of iteration:
_M_ belonging to V_all - a part of the sequence M, which was not
hashed at previous iterations;
H belonging to V256 - the current hash value;
SIGMA belonging to V256 - the current check sum value;
L belonging to V256 - the length of the partial sequence M processed
at the previous iteration step.
The calculation algorithm for function h consists of the following
steps:
Step 1. Assign initial values to current quantities:
1.1 _M_ := M.
1.2 H := h0.
1.3 SIGMA := 0^256.
1.4 L := 0^256.
1.5 Go to step 2.
Step 2.
2.1 Verify the condition |_M_|>256.
If it is true, go to step 3.
Else, make the following calculations:
2.2 L := <L^$ + |M|>_256
2.3 M' := 0^(256 -|M|)||M
2.4 SIGMA := SIGMA (+)' M'
2.5 H := chi (M', H)
2.6 H := chi (L, H)
2.7 H := chi (SIGMA, H)
2.8 End.
Step 3.
3.1 Calculate a subword M_s belonging to V256 of the word _M_
(_M_ = M_p||M_s). Then make the following calculations:
3.2 H := chi (M_s, H)
3.3 L := <L^$ + 256>_256
3.4 SIGMA := SIGMA (+)' M[s]
3.5 _M_ = M_p
3.6 Go to step 2.
The quantity H obtained at step 2.7 is the value of the hash function
h(M).
7. Test Examples (Informative)
It is recommended to use the values for substitution units pi[1],
pi[2],..., pi[8] and the initial hash value H described in this
appendix for the GOST R 34.11-94 test examples only.
7.1. Usage of the Algorithm GOST 28147-89
The algorithm GOST 28147-89 [GOST28147] in ECB mode is used as an
encryption transformation in the following examples. The following
values of the substitution units pi[1], pi[2],..., pi[8] have been
chosen:
8 7 6 5 4 3 2 1
0 1 D 4 6 7 5 E 4
1 F B B C D 8 B A
2 D 4 A 7 A 1 4 9
3 0 1 0 1 1 D C 2
4 5 3 7 5 0 A 6 D
5 7 F 2 F 8 3 D 8
6 A 5 1 D 9 4 F 0
7 4 9 D 8 F 2 A E
8 9 0 3 4 E E 2 6
9 2 A 6 A 4 F 3 B
10 3 E 8 9 6 C 8 1
11 E 7 5 E C 7 1 C
12 6 6 9 0 B 6 0 7
13 B 8 C 3 2 0 7 F
14 8 2 F B 5 9 5 5
15 C C E 2 3 B 9 3
The hexadecimal value of pi[j](i) is given in a column number j,
j = 1..8, and in a row number i, i = 0..15.
7.2. Representation of Vectors
We will put down binary symbol sequences as hexadecimal digits
strings, where each digit corresponds to four signs of its binary
representation.
7.3 Examples of the Hash Value Calculation
A zero vector, for example, can be taken as an initial hash value:
h0 = 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
7.3.1. Hash Calculation for the Sample Message M
K[4] = 94B97995 7D141B41 C21EE2A0 040CB741
346FDA88 46D0142A BDFA81AA DC1562FD
S = D42336E0 2A0A6998 6C65478A 3D08A1B9
9FDDFF20 4808E863 94FD9D6D F776A7AD
KSI = 47E26AFD 3E7278A1 7D473785 06140773
A3D97E7E A744CB43 08AA4C24 3352C745
STEP 4.
H = 47E26AFD 3E7278A1 7D473785 06140773
A3D97E7E A744CB43 08AA4C24 3352C745
SIGMA = 73616820 65676173 73656D20 6C61E1CE
DBE2D48F 509A88B1 40CDE7D6 DED5E173
K[1] = 340E7848 83223B67 025AAAAB DDA5F1F2
5B6AF7ED 1575DE87 19E64326 D2BDF236
K[2] = 03DC0ED0 F4CD26BC 8B595F13 F5A4A55E
A8B063CB ED3D7325 6511662A 7963008D
K[3] = C954EF19 D0779A68 ED37D3FB 7DA5ADDC
4A9D0277 78EF765B C4731191 7EBB21B1
K[4] = 6D12BC47 D9363D19 1E3C696F 28F2DC02
F2137F37 64E4C18B 69CCFBF8 EF72B7E3
S = 790DD7A1 066544EA 2829563C 3C39D781
25EF9645 EE2C05DD A5ECAD92 2511A4D1
KSI = 0852F562 3B89DD57 AEB4781F E54DF14E
EAFBC135 0613763A 0D770AA6 57BA1A47
Then, the hash result is:
H = 0852F562 3B89DD57 AEB4781F E54DF14E
EAFBC135 0613763A 0D770AA6 57BA1A47
8. Security Considerations
This entire document is about security considerations.
Current cryptographic resistance of GOST R 34.11-94 hash algorithm is
estimated as 2^128 operations of computations of step hash functions.
(There is a known method to reduce this estimate to 2^105 operations,
but it demands padding the colliding message with 1024 random bit
blocks each of 256-bit length; thus, it cannot be used in any
practical implementation).
9. Normative References
[GOST28147] "Cryptographic Protection for Data Processing System",
GOST 28147-89, Gosudarstvennyi Standard of USSR,
Government Committee of the USSR for Standards, 1989.
(In Russian)
[GOST3411] "Information technology. Cryptographic Data Security.
Hashing function.", GOST R 34.11-94, Gosudarstvennyi
Standard of Russian Federation, Government Committee of
the Russia for Standards, 1994. (In Russian)
EID 2303 (Verified) is as follows:Section: 9
Original Text:
[GOST3411] "Information technology. Cryptographic Data Security.
Hashing function.", GOST R 34.10-94, Gosudarstvennyi
Standard of Russian Federation, Government Committee of
the Russia for Standards, 1994. (In Russian)
Corrected Text:
[GOST3411] "Information technology. Cryptographic Data Security.
Hashing function.", GOST R 34.11-94, Gosudarstvennyi
Standard of Russian Federation, Government Committee of
the Russia for Standards, 1994. (In Russian)