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.
Dolmatov Informational [Page 1]
RFC 5831 GOST R 34.11-94 March 2010
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. GOST R 34.11-94 [GOST3411] was developed by the Federal Agency for Government Communication and Information and by the All-Russia Scientific and Research Institute of Standardization.
2. GOST R 34.11-94 was accepted and activated by Act 154 of 23.05.1994 issued by the Russian Federal committee for standards.
Expanding the application of information technologies when creating, processing, and storing documents requires, in some cases, confidentiality of their contents, maintenance of completeness, and authenticity.
Cryptography (cryptographic security) is one of the effective approaches for data security. It is widely applied in different areas of government and commercial activity.
Cryptographic data security methods are under serious scientific research and standardization efforts at national, regional, and international levels.
GOST R 34.11-94 defines a hash function calculation procedure for an arbitrary sequence of binary symbols.
The hash function maps an arbitrary set of data represented as a sequence of binary symbols onto its image of a fixed small length.
Thus, hash functions can be used in procedures related to the electronic digital signature, resulting in considerable reduction of elapsed time for the sign and verify stages. The effect of the reduction of time is due to the fact that only a short image of initial data is actually signed.
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.
Dolmatov Informational [Page 3]
RFC 5831 GOST R 34.11-94 March 2010
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).
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).
Dolmatov Informational [Page 4]
RFC 5831 GOST R 34.11-94 March 2010
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.
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.
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.
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.
Dolmatov Informational [Page 7]
RFC 5831 GOST R 34.11-94 March 2010
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:
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.
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:
Let M = 7365 74796220 3035203D 20687467 6E656C20 73616820 65676173 73656D20 6C616E69 6769726F 20656874 2065736F 70707553
As the length of the message to be hashed equals 400 bits (50 bytes), the message is divided into two blocks, and the second (high-order) one is padded with zeroes. During the calculations the following numbers are obtained:
STEP 1.
H = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
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.10-94, Gosudarstvennyi Standard of Russian Federation, Government Committee of the Russia for Standards, 1994. (In Russian)