Tweet This is a modified version of the Internet RFC suitable for machine-translating. Original version is available here: RFC6986
Ad
INFORMATIONAL
Independent Submission V. Dolmatov, Ed.
Request for Comments: 6986 A. Degtyarev
Updates: 5831 Cryptocom, Ltd.
Category: Informational August 2013
ISSN: 2070-1721
GOST R 34.11-2012: Hash Function
Abstract
This document is intended to be a source of information about the Russian Federal standard hash function (GOST R 34.11-2012), which is one of the Russian cryptographic standard algorithms (called GOST algorithms). This document updates RFC 5831.
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/rfc6986.
Copyright Notice
Copyright (c) 2013 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.
Dolmatov & Degtyarev Informational [Page 1]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
Table of Contents
1. Scope ...........................................................2 2. General Information .............................................3 3. Standard References .............................................3 4. Definitions and Notations .......................................4 4.1. Definitions ................................................4 4.2. Notations ..................................................5 5. General Provisions ..............................................6 6. Parameter Values ................................................6 6.1. Initializing Values ........................................6 6.2. Nonlinear Bijections of Binary Vector Sets .................7 6.3. Byte Permutation ...........................................8 6.4. Linear Transformations of Binary Vector Sets ...............8 6.5. Iteration Constants ........................................9 7. Transformations ................................................10 8. Round Functions ................................................11 9. Hash-Function Calculation Procedure ............................11 10. Examples (Informative) ........................................13 10.1. Example 1 ................................................13 10.1.1. For Hash Function with 512-Bit Hash Code ..........13 10.1.2. For Hash Function with 256-Bit Hash Code ..........19 10.2. Example 2 ................................................25 10.2.1. For Hash Function with 512-Bit Hash Code ..........25 10.2.2. For Hash Function with 256-Bit Hash Code ..........32 11. Security Considerations .......................................38 12. References ....................................................38 12.1. Normative References .....................................38 12.2. Informative References ...................................39
The Russian Federal standard hash function (GOST R 34.11-2012) establishes the hash-function algorithm and the hash-function calculation procedure for any sequence of binary symbols used in cryptographic methods of information processing and information security, including techniques for providing data integrity and authenticity and for digital signatures during information transfer, information processing, and information storage in computer-aided systems.
The hash function defined in the standard provides for the operation of digital signature systems using the asymmetric cryptographic algorithm in compliance with GOST R 34.10-2012 [GOST3410-2012]. GOST R 34.11-2012 applies to the creation, operation, and modernization of information systems of different purpose.
Dolmatov & Degtyarev Informational [Page 2]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
GOST R 34.11-94 is superseded by GOST R 34.11-2012 from 1st January 2013. That means that all new systems that are presented for certification MUST use GOST R 34.11-2012 and MAY use GOST R 34.11-94 also for maintaining compatibility with existing systems. Usage of GOST R 34.11-94 in current systems is allowed at least for a 5-year period.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119[RFC2119].
1. GOST R 34.11-2012 [GOST3411-2012] was developed by the Center for Information Protection and Special Communications of the Federal Security Service of the Russian Federation with participation of the open joint-stock company Information Technologies and Communication Systems (InfoTeCS JSC).
2. GOST R 34.11-2012 was approved and introduced by Decree #216 of the Federal Agency on Technical Regulating and Metrology on 07.08.2012.
3. GOST R 34.11-2012 is intended to replace GOST R 34.11-94 [GOST3411-94], a national standard of the Russian Federation.
Terms and concepts in the standard comply with the following international standards:
o ISO 2382-2 [ISO2382-2], o ISO/IEC 9796 [ISO/IEC9796-2][ISO/IEC9796-3], o series of standards ISO/IEC 14888 [ISO/IEC14888-1]
[ISO/IEC14888-2][ISO/IEC14888-3][ISO/IEC14888-3Amd], and
o series of standards ISO/IEC 10118
[ISO/IEC10118-1][ISO/IEC10118-2][ISO/IEC10118-3][ISO/IEC10118-4].
The following standards are referred to in GOST R 34.11-2012:
1. GOST 28147-89 [GOST28147-89], "Systems of information processing. Cryptographic data security. Algorithms of cryptographic transformation."
Dolmatov & Degtyarev Informational [Page 3]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
2. GOST R 34.10-2012 [GOST3410-2012], "Information technology. Cryptographic data security. Formation and verification processes of [electronic] digital signature."
Note: Users of the standard may check the validity of the referenced standards on the official Internet site of the Federal Agency on Technical Regulating and Metrology, in the annual reference book "National Standards" published on January 1 of the current year, and in corresponding monthly indices published during the current year. If the referenced standard is replaced (amended), then the replaced (amended) standard shall be used. If the referenced standard is canceled without replacement, then only the parts of this document not containing the specified reference may be used.
padding: appending extra bits to a data string (Clause 3.9 of [ISO/IEC10118-1]).
initializing value: a value used in defining the starting point of a hash function (Clause 3.7 of [ISO/IEC10118-1]).
message: string of bits of any length (Clause 3.10 of [ISO/IEC14888-1]).
round function: a function that transforms two binary strings of lengths L1 and L2 to a binary string of length L2. It is used iteratively as part of a hash function, where it combines a data string of length L1 with the previous output of length L2 (Clause 3.10 of [ISO/IEC10118-1]).
Note: In GOST R 34.11-2012, the concepts "string of bits of length L" and "binary row vector of length L" are identical.
hash code: string of bits that is the output of a hash function (Clause 3.6 of [ISO/IEC14888-1].
collision-resistant hash function: function that maps strings of bits to fixed-length strings of bits, satisfying the following properties:
1. for a given output, it is computationally infeasible to find an input that maps to this output;
Dolmatov & Degtyarev Informational [Page 4]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
2. for a given input, it is computationally infeasible to find a second input that maps to the same output; and
3. it is computationally infeasible to find any two distinct inputs that map to the same output (Clauses 3.2 and 3.7 of [ISO/IEC14888-1]).
Note: In the standard (to provide terminological compatibility with the current native standard documentation and with the published scientific and technical works), the terms "hash function" and "cryptographic hash function" are synonyms.
signature: one or more data elements resulting from the signature process (Clause 3.12 of [ISO/IEC 14888-1].
Note: In the standard (to provide terminological compatibility with the current native standard documentation and with the published scientific and technical works), the terms "digital signature", "electronic signature", and "electronic digital signature" are synonyms.
V* the set of all binary row vectors of finite length
(hereinafter referred to as vectors) including empty string
|A| the length (number of components) of the vector A belonging
to V* (if A is an empty string, then |A| = 0)
V_n the set of all binary vectors of length n, where n is a non-
negative integer; subvectors and vector components are enumerated from right to left starting from zero
(xor) exclusive-or of the two binary vectors of the same length
A||B concatenation of vectors A, B (both belong to V*), i.e., a
vector from V_(|A|+|B|), where the left subvector from
V_(|A|) is equal to the vector A and the right subvector from
V_(|B|) is equal to the vector B
A^n concatenation of n instances of the vector A
Z_(2^n) ring of residues modulo 2^n
[+] addition operation in the ring Z_(2^n) Vec_n: Z_(2^n) -> V_n bijective-mapping operation associating an element from Z_(2^n) with its binary representation, i.e., for an element z of the ring Z_(2^n), represented by the residue z_0 + (2*z_1) + ... + (2^(n-1)*z_(n-1)), where z_i in {0, 1},
Dolmatov & Degtyarev Informational [Page 5]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
j = 0, ..., n-1, the equality Vec_n(z) =
z_(n-1)||...||z_1||z_0 holds
Int_n: V_n -> Z_(2^n)
the mapping inverse to the mapping Vec_n, i.e., Int_n = Vec_n^(-1)
MSB_n: V* -> V_n
the mapping associating the vector z_(k-1)||...||z_1||z_0,
k >= n, with the vector z_(k-1)||...||z_(k-n+1)||z_(k-n)
a := b operation of assigning the value b to the variable a
PS product of mappings, where the mapping S applies first
M binary vector subject to hashing procedure, M belongs to V*,
|M| < 2^512
H: V* -> V_n
hash function mapping the vector (message) M into the vector (hash code) H(M)
The initializing value IV for a hash function with a hash-code length of 512 bits is 0^512. The initializing value IV for a hash function with a hash-code length of 256 bits is (00000001)^64.
Dolmatov & Degtyarev Informational [Page 6]
RFC 6986 GOST R 34.11-2012: Hash Function August 20136.2. Nonlinear Bijections of Binary Vector Sets
Nonlinear bijection of the binary vector set V_8 is presented by the following substitution:
Pi = (Vec_8)Pi'(Int_8): V_8 -> V_8
where Pi': Z_(2^8) -> Z_(2^8).
The values of the substitution Pi' are presented in the array form Pi' = (Pi'(0), Pi'(1), ... , Pi'(255)):
Linear transformation l of the binary vector set V_64 is specified by the right multiplication with the matrix A over the field GF(2). The matrix rows are specified sequentially in a hexadecimal form. The row with number j, j = 0, ..., 63 (specified in the form
a_(j, 15)...a_(j, 0), where a_(j, i) belongs to Z_16, i = 0, ...,
15), is Vec_4(a_(j, 15))||...||Vec_4(a_(j, 0)).
Here one string contains 4 rows of the matrix A. So, the string with number i, i = 0, ..., 15, specifies 4 rows of the matrix A (with the numbers 4i + j, j = 0, ..., 3) in the following left-to-right order: 4i + 0, 4i + 1, 4i + 2, 4i + 3. The product of the vector b = b_63...b_0 belonging to V_64 and the matrix A is the vector c belonging to V_64:
Dolmatov & Degtyarev Informational [Page 8]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
c = b_63(Vec_4(a_(0, 15))||...||Vec_4(a_(0, 0))) (xor)
... (xor)
b_0(Vec_4(a_(63, 15))||...||Vec_4(a_(63, 0)))
For calculating the hash code H(M) of the message M belonging to V*, the following transformations are used:
X[k]: V_512 -> V_512, X[k](a) = k (xor) a, k, a belongs to V_512;
S:V_512 -> V_512,
S(a) = S(a_63||...||a_0) = Pi(a_63)||...||Pi(a_0), where
a = a_63||...||a_0 belongs to V_512, a_i belongs to V_8,
i = 0, ..., 63;
Dolmatov & Degtyarev Informational [Page 10]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
P:V_512 -> V_512,
P(a) = P(a_63||...||a_0) = a_(Tau(63))||...||a_(Tau(0)), where
a = a_63||...||a_0 belongs to V_512, a_i belongs to V_8,
i = 0, ..., 63;
L:V_512 -> V_512,
L(a) = L(a_7||...||a_0) = l(a_7)||...||l(a_0), where
a = a_7||...||a_0 belongs to V_512, a_i belongs to V_64,
i = 0, ..., 7.
8. Round Functions
The hash-code value of the message M belonging to V* is calculated using the iterative procedure. Each iteration is provided using the round function:
g_N:V_512 x V_512 -> V_512, where N belongs to V_512
calculated as
g_N(h, m) = E(LPS(h (xor) N), m) (xor) h (xor) m
where
E(K, m) = X[K[13]]LPSX[K[12]]...LPSX[K[2]]LPSX[K[1]](m)
Values K[i] belonging to V_512, i = 1, ..., 13, are calculated as follows:
Initial data for the procedure of calculating the hash code H(M) are a message M belonging to V* (subject to hashing) and initializing value IV belonging to V_512. The algorithm for calculating the function H consists of the following steps.
Step 1. Assign initial values to the following variables:
1.1. h := IV
1.2. N := 0^512 belonging to V_512
1.3. EPSILON := 0^512 belonging to V_512 1.4. Go to Step 2.
Dolmatov & Degtyarev Informational [Page 11]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
Step 2.
2.1. Check the condition |M| < 512
If it is true, then go to Step 3. Else, perform the following calculations:
2.2. Calculate the subvector m belonging to V_512 of the message
M:
3.6. h := g_0(h, EPSILON), for function with 512-bit hash code
h := MSB_256(g_0(h, EPSILON)), for function with 256-bit hash code
3.7. End of the algorithm
The value of the variable h (obtained in Step 3.6) is the value of hash function H(M).
Dolmatov & Degtyarev Informational [Page 12]
RFC 6986 GOST R 34.11-2012: Hash Function August 201310. Examples (Informative)
This section is for information only and is not a normative part of the standard.
The vectors from V* are specified in a hexadecimal form. The vector
A belonging to V_(4n) (specified in the form a_(n-1)...a_0, where a_i
belongs to Z_16, i = 0, ..., n-1) is Vec_4(a_(n-1))||...||Vec_4(a_0).
10.1. Example 1
Let's calculate the hash code of the following message (represented as a hexadecimal string):
h = 5c881fd924695cf196c2e4fec20d14b6 42026f2a0b1716ebaabb7067d4d59752 3d2db69d6d3794622147a14f19a66e7f 9037e1d662d34501a8901a5de7771d7c The result of the transformation g_0(h, EPSILON) is
Dolmatov & Degtyarev Informational [Page 18]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
h = 486f64c1917879417fef082b3381a4e2 11c324f074654c38823a7b76f830ad00 fa1fbae42b1285c0352f227524bc9ab1 6254288dd6863dccd5b9f54a1ad0541b
h = 70f22bada4cfe18a6a56ec4b3f328cd4 0db8e1bf8a9d5f711d5efab11191279d 715aab7648d07eddbf87dc79c80516e6 ffcbcf5678b0ac29ea00fa85c8173cc6 The result of the transformation g_0(h, EPSILON) is
Dolmatov & Degtyarev Informational [Page 24]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
h = 00557be5e584fd52a449b16b0251d05d 27f94ab76cbaa6da890b59d8ef1e159d 2088e482e2acf564e0e9795a51e4dd26 1f3f667985a2fcc40ac8631faca1709a
h = cd7f602312faa465e3bb4ccd9795395d e2914e938f10f8e127b7ac459b0c517b 98ef779ef7c7a46aa7843b8889731f48 2e5d221e8e2cea852e816cdac407c7af
The variables N and EPSILON change their values to
N = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000200
EPSILON = fbeafaebef20fffbf0e1e0f0f520e0ed
20e8ece0ebe5f0f2f120fff0eeec20f1 20faf2fee5e2202ce8f6f3ede220e8e6 eee1e8f0f2d1202ce8f0f2e5e220e5d1 The length of the rest of the message is less than 512, so the incomplete block is padded:
Dolmatov & Degtyarev Informational [Page 30]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
m := 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 0000000000000001fbe2e5f0eee3c820
The result of the transformation g_N(h, m) is
h = c544ae6efdf14404f089c72d5faf8dc6 aca1db5e28577fc07818095f1df70661 e8b84d0706811cf92dffb8f96e61493d c382795c6ed7a17b64685902cbdc878e
The variables N and EPSILON change their values to
N = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000240
K := LPS(h (xor) N) = 23c5ee40b07b5f1523c5ee40b07b5f15 23c5ee40b07b5f1523c5ee40b07b5f15 23c5ee40b07b5f1523c5ee40b07b5f15 23c5ee40b07b5f1523c5ee40b07b5f15 Then the transformation E(K, m) is performed:
Dolmatov & Degtyarev Informational [Page 32]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
X[K[13]]...LPSX[K[1]](m) = dad73ab73b7e345f46435c690f05e94a
5cb272d242ef44f6b0a4d5d1ad888331 8b31ad01f96e709f08949cd8169f25e0 9273e8e50d2ad05b5f6de6496c0a8ca8 The result of the transformation g_N(h, m) is
Dolmatov & Degtyarev Informational [Page 36]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
h = 203cc15dd55fcaa5b7a3bd98fb2408a6 7d5b9f33a80bb50540852b204265a2c1 aaca5efe1d8d51b2e1636e34f5becc07 7d930114fefaf176b69c15ad8f2b6878
The variables N and EPSILON changed their values to:
N = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000200
The length of the rest of the message is less than 512, so the incomplete block is padded:
m = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 0000000000000001fbe2e5f0eee3c820
The result of the transformation g_N(h, m) is
h = a69049e7bd076ab775bc2873af26f098 c538b17e39a5c027d532f0a2b3b56426 c96b285fa297b9d39ae6afd8b9001d97 bb718a65fcc53c41b4ebf4991a617227
The variables N and EPSILON change their values to
N = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000240
EPSILON = fbeafaebef20fffbf0e1e0f0f520e0ed
20e8ece0ebe5f0f2f120fff0eeec20f1 20faf2fee5e2202ce8f6f3ede220e8e6 eee1e8f0f2d1202ee4d3d8d6d104adf1 The result of the transformation g_0(h, N) is
Dolmatov & Degtyarev Informational [Page 37]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
h = aee3bd55ea6f387bcf28c6dcbdbbfb3d dacc67dcc13dbd8d548c6bf808111d4b 75b8e74d2afae960835ae6a5f0357555 9c9fd839783ffcd5cf99bd61566b4818
The result of the transformation g_0(h, EPSILON) is
h = 508f7e553c06501d749a66fc28c6cac0 b005746d97537fa85d9e40904efed29d c345e53d7f84875d5068e4eb743f0793 d673f09741f9578471fb2598cb35c230
[GOST3411-94] "Information technology. Cryptographic data
security. Hashing function", GOST R 34.11-94, Federal Agency on Technical Regulating and Metrology, 1994.
[GOST28147-89] "Systems of information processing. Cryptographic
data security. Algorithms of cryptographic transformation", GOST 28147-89, Gosudarstvennyi Standard of USSR, Government Committee of the USSR for Standards, 1989. (In Russian)
[GOST3411-2012] "Information technology. Cryptographic Data
Security. Hashing function", GOST R 34.11-2012, Federal Agency on Technical Regulating and Metrology, 2012.
[GOST3410-2012] "Information technology. Cryptographic data
security. Formation and verification processes of [electronic] digital signature", GOST R 34.10-2012, Federal Agency on Technical Regulating and Metrology, 2012.
Dolmatov & Degtyarev Informational [Page 38]
RFC 6986 GOST R 34.11-2012: Hash Function August 2013
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC5831] Dolmatov, V., Ed., "GOST R 34.11-94: Hash Function
Algorithm", RFC 5831, March 2010.
[ISO2382-2] ISO, "Data processing - Vocabulary - Part 2:
Arithmetic and logic operations", ISO 2382-2, 1976.
[ISO/IEC9796-2] ISO/IEC, "Information technology - Security
techniques - Digital signature schemes giving message recovery - Part 2: Integer factorization based mechanisms", ISO/IEC 9796-2, 2010.
[ISO/IEC9796-3] ISO/IEC, "Information technology - Security
techniques - Digital signature schemes giving message recovery - Part 3: Discrete logarithm based mechanisms", ISO/IEC 9796-3, 2006.
[ISO/IEC14888-1] ISO/IEC, "Information technology - Security
techniques - Digital signatures with appendix - Part 1: General", ISO/IEC 14888-1, 2008.
[ISO/IEC14888-2] ISO/IEC, "Information technology - Security
techniques - Digital signatures with appendix - Part 2: Integer factorization based mechanisms", ISO/IEC 14888-2, 2008.
[ISO/IEC14888-3] ISO/IEC, "Information technology - Security
techniques - Digital signatures with appendix - Part 3: Discrete logarithm based mechanisms", ISO/IEC 14888-3, 2006.
[ISO/IEC14888-3Amd]
ISO/IEC, "Information technology - Security techniques - Digital signatures with appendix - Part 3: Discrete logarithm based mechanisms. Amendment 1. Elliptic Curve Russian Digital Signature Algorithm, Schnorr Digital Signature Algorithm, Elliptic Curve Schnorr Digital Signature Algorithm, and Elliptic Curve Full Schnorr Digital Signature Algorithm", ISO/IEC 14888-3:2006/Amd 1, 2010.
Translate documents to 日本語, svenska, Nederlands, Deutsch, français, русский, italiano, español, Tiếng Việt, polski, português, 中文, українська, català, norsk, فارسی, suomi, Bahasa Indonesia, العربية, čeština, 한국어, Bahasa Melayu, magyar, română, српски and other languages.
