Internet Draft Vladimir Popov, CRYPTO-PRO Igor Kurepkin, CRYPTO-PRO Expires September 30, 2004 Serguei Leontiev, CRYPTO-PRO Intended Category: Informational March 31, 2004 Additional cryptographic algorithms for use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 algorithms. Status of this Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or made obsolete by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract This document describes cryprographic algorithms and parameters, supplementary to GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001 and GOST R 34.11-94, for use in internet applications. Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Terminology. . . . . . . . . . . . . . . . . . . . . . . 2 2 Cipher modes and parameters. . . . . . . . . . . . . . . 3 2.1 GOST 28147-89 CBC mode . . . . . . . . . . . . . . . . . 3 2.2 GOST 28147-89 padding modes. . . . . . . . . . . . . . . 4 2.3 Key Meshing Algorithms . . . . . . . . . . . . . . . . . 4 2.3.1 Null Key Meshing . . . . . . . . . . . . . . . . . . . . 4 2.3.2 CryptoPro Key Meshing. . . . . . . . . . . . . . . . . . 4 3 HMAC_GOSTR3411 . . . . . . . . . . . . . . . . . . . . . 5 Popov,Kurepkin,Leontiev Informational [Page 1] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 4 PRF_GOSTR3411. . . . . . . . . . . . . . . . . . . . . . 5 5 Key Derivation Algorithms. . . . . . . . . . . . . . . . 5 5.1 VKO GOST R 34.10-94. . . . . . . . . . . . . . . . . . . 5 5.2 VKO GOST R 34.10-2001. . . . . . . . . . . . . . . . . . 6 6 Key Wrap algorithms. . . . . . . . . . . . . . . . . . . 6 6.1 GOST 28147-89 Key Wrap . . . . . . . . . . . . . . . . . 6 6.2 GOST 28147-89 Key Unrap. . . . . . . . . . . . . . . . . 7 6.3 CryptoPro Key Wrap . . . . . . . . . . . . . . . . . . . 7 6.4 CryptoPro Key Unwrap . . . . . . . . . . . . . . . . . . 8 6.5 CryptoPro KEK Diversification Algorithm. . . . . . . . . 8 7 Secret Key Diversification . . . . . . . . . . . . . . . 9 8 Algorithm parameters . . . . . . . . . . . . . . . . . . 9 8.1 Encryption algorithm parameters . . . . . . . . . . . . 9 8.2 Digest algorithm parameters. . . . . . . . . . . . . . . 11 8.3 GOST R 34.10-94 public key algorithm parameters . . . . 11 8.4 GOST R 34.10-2001 public key algorithm parameters. . . . 12 9 Security Considerations. . . . . . . . . . . . . . . . . 13 10 Appendix ASN.1 Modules . . . . . . . . . . . . . . . . . 14 11 References . . . . . . . . . . . . . . . . . . . . . . . 49 12 Acknowledgments. . . . . . . . . . . . . . . . . . . . . 51 Author's Address. . . . . . . . . . . . . . . . . . . . . . . . 51 Full Copyright Statement. . . . . . . . . . . . . . . . . . . . 53 1 Introduction Russian cryptographic standards defining algorithms GOST 28147-89 [GOST28147], GOST R 34.10-94 [GOSTR341094], GOST R 34.10-2001 [GOSTR34102001] and GOST R34.11-94 [GOSTR341194] (a brief english technical description of these algorithms can be found in [Schneier95]) provide basic information about how the algorithms work, but need supplemental specifications to effectively use the algorithms. This document is a proposal put forward by CRYPT-PRO Company to provide the supplemental information and specifications needed by the "Russian Cryptographic Software Compatibility Agreement" community. 1.2 Terminology In this document, the key words MUST, MUST NOT, REQUIRED, SHOULD, SHOULD NOT, RECOMMENDED, and MAY are to be interpreted as described in [RFC 2119]. The following functions and operators are also used in this document: '|' stands for concatenation encryptECB (K, D) - is D, encrypted with key K using GOST 28147-89 in Popov,Kurepkin,Leontiev Informational [Page 2] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 "prostaya zamena" (ECB) mode decryptECB (K, D) - is D, decrypted with key K using GOST 28147-89 in ECB mode encryptCFB (IV, K, D) - is D, encrypted with key K using GOST 28147-89 in "gammirovanie s obratnoj svyaziyu" (64-bit CFB) mode, and IV as initialization vector. encryptCNT (IV, K, D) - is D, encrypted with key K using GOST 28147-89 in "gammirovanie" (counter) mode, and IV as initialization vector. gostR3411 (D) - is the 256-bit result of GOST R 34.11-94 hash function, used with zero intitialization vector, and S-Box parameter, defined by gostR3411CryptoProParamSetAI (see Appendix, GostR3411-94-ParamSetSyntax module). gost28147IMIT (IV, K, D) - is the 32-bit result of GOST 28147-89 in "imitovstavka" (MAC) mode, used with D as plaintext, K as key and IV as initialization vector. Note, that standard specifies it's use in this mode only with zero initialization vector. When keys and initialization vectors are converted to/from byte arrays, little-endian byte order is assumed. 2 Cipher modes and parameters [GOST28147] defines only three cipher modes for GOST 28147-89: ECB, CFB and counter mode. This document defines an additional cipher mode CBC. When GOST 28147-89 is used to process large amounts of data, a symmetric key should be protected by key meshing algorithm. This document defines CryptoPro key meshing algorithm. The cipher mode, key meshing algorithm, padding mode and S-box are specified by algorithm parameters. 2.1 GOST 28147-89 CBC mode This section provides the supplemental information to GOST 28147-89 (a block to block primitive) needed to operate in CBC mode. Before each plaintext block is encrypted, it is combined with the cipher text of the previous block by a bitwise XOR operation. This ensures that even if the plaintext contains many identical blocks, Popov,Kurepkin,Leontiev Informational [Page 3] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 they will each encrypt to a different cipher text block. The initialization vector is combined with the first plaintext block by a bitwise XOR operation before the block is encrypted. 2.2 GOST 28147-89 padding modes This section provides the supplemental information to GOST 28147-89, needed to operate on plaintext, which length is not divisible by GOST 28147-89 block size (8 bytes). Let x (0 < x < 8) be the number of bytes in the last (possibly, incomplete) block of data. There are three padding modes: * Zero padding: 8-x remaining bytes are filled with zero * PKCS#5 padding: 8-x remaining bytes are filled with value of 8-x. If there's no incomplete block, one extra block filled with value 8 is added. * Random padding: 8-x remaining bytes of the last block are set to random. 2.3 Key Meshing Algorithms When there is a need to limit the amount of data, enciphered with the same key, several key meshing algorithms can be used. Key meshing algorithms transform the key after processing a certain amount of data. All encryption parameter sets, defined in this document, specify use of CryptoPro key meshing algorithm, except for id- Gost28147-89-TestParamSet, which specifies use of null key meshing algorithm. 2.3.1 Null Key Meshing A null key meshing algorithm never changes a key. It's OID is: id-Gost28147-89-None-KeyMeshing OBJECT IDENTIFIER ::= { id-CryptoPro-algorithms keyMeshing(14) none(0) } This algorithm has NULL parameters. 2.3.2 CryptoPro Key Meshing CryptoPro key meshing algorithm transforms the key and initialization vector every 1KB of plaintext data. It's OID is: id-Gost28147-89-CryptoPro-KeyMeshing OBJECT IDENTIFIER ::= { id-CryptoPro-algorithms keyMeshing(14) cryptoPro(1) } Popov,Kurepkin,Leontiev Informational [Page 4] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 This algorithm has NULL parameters. Encryption or decryption starts with key K[0] = K, IV0[0] = IV, i = 0. Let IV[0] be the value of initialization vector after processing 1K of data. Encryption or decryption of next 1K data block will start with K[1] and IV0[1], which are calculated using formula: K[i+1] = decryptECB (K[i], C); IV0[i+1] = encryptECB (K[i+1],IV[i]) Where C = {0x69, 0x00, 0x72, 0x22, 0x64, 0xC9, 0x04, 0x23, 0x8D, 0x3A, 0xDB, 0x96, 0x46, 0xE9, 0x2A, 0xC4, 0x18, 0xFE, 0xAC, 0x94, 0x00, 0xED, 0x07, 0x12, 0xC0, 0x86, 0xDC, 0xC2, 0xEF, 0x4C, 0xA9, 0x2B}; After processing every next 1K block, current initialization vector is stored as IV[i+1], i is incremented and the same transformation applied. 3 HMAC_GOSTR3411 HMAC_GOSTR3411 (K,text) function is based on hash function GOST R 34.11-94, as defined in [HMAC], with the following parameter values: B = 32, L = 32. 4 PRF_GOSTR3411 PRF_GOSTR3411 is a pseudorandom function, based on HMAC_GOSTR3411. It is calculated as P_hash, defined in section 5 of [TLS]. PRF_GOSTR3411(K,D) = P_GOSTR3411 (K,D) 5 Key Derivation Algorithms Standards [GOSTR341094] and [GOSTR34102001] do not define any key derivation algorithms. Section 5.1 specifies algorithm VKO GOST R 34.10-94, which generates GOST KEK using two GOST R 34.10-94 keypairs. Section 5.2 specifies algorithm VKO GOST R 34.10-2001, which generates GOST KEK using two GOST R 34.10-2001 keypairs, and synchrovector A. Keypairs MUST have identical parameters. 5.1 VKO GOST R 34.10-94 This algorithm creates a a key encryption key (KEK) using sender's Popov,Kurepkin,Leontiev Informational [Page 5] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 private key and recipient public key, or vice versa. Exchange key EK is a 256-bit hash of 1024-bit Diffie-Hellman key K(x,y); 1. Let K(x,y) = a^(x*y) (mod p), where x - sender's private key, a^x - sender's public key y - recipient's private key, a^y - recipient's public key a, p - parameters 2. Calculate a 256-bit hash of K(x,y): KEK(x,y) = gostR3411 (K(x,y)) Keypairs x and y MUST comply with [GOSTR341094]. This algorithm MUST NOT be used, when a^x = a (mod p) or a^y = a (mod p). 5.2 VKO GOST R 34.10-2001 This algorithm creates a key encryption key (KEK) using synchrovector, sender's private key and recipient public key, or vice versa. 1. Let K(x,y,IV) = ((IV*x)(mod q)) . (y.P) (512 bit), where x - sender's private key (256 bit) x.P - sender's public key (512 bit) y - recipient's private key (256 bit) y.P - recipient's public key (512 bit) IV - synchrovector (64 bit) P - base point on the elliptic curve (two 256-bit coordinates) IV*x - x multiplied by IV as integers x.P - a multiple point 2. Calculate a 256-bit hash of K(x,y,IV): KEK(x,y,IV) = gostR3411 (K(x,y,IV)) Keypairs x and y MUST comply with [GOSTR34102001]. This algorithm MUST NOT be used, when x.P = P, y.P = P 6 Key Wrap algorithms This document defines two key wrap algorithms: GOST 28147-89 Key Wrap and CryptoPro Key Wrap. 6.1 GOST 28147-89 Key Wrap This algorithm encrypts GOST 28147-89 CEK with a GOST 28147-89 KEK. Note: This algorithm MUST NOT be used with KEK produced by VKO GOST R Popov,Kurepkin,Leontiev Informational [Page 6] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 34.10-94, because such KEK is constant for every sender-recipient pair. Encrypting many different content encryption keys on the same constant KEK may reveal this KEK. Identifier for this algorithm: id-Gost28147-89-None-KeyWrap OBJECT IDENTIFIER ::= { id-CryptoPro-algorithms keyWrap(13) none(0) } The GOST 28147-89 key wrap algorithm is: 1. For unique symmetric KEK, generate 8 octets at random, call the result IV. For KEK, produced by VKO GOST R 34.10-2001, use the same IV, that was used for key derivation. 2. Compute a 4-byte checksum value, gost28147IMIT (IV, KEK, CEK), call the result CEK_MAC. 3. Encrypt CEK in ECB mode using KEK. Use IV, generated in step 1. Call the ciphertext CEK_ENC. 4. Let RES = IV | CEK_ENC | CEK_MAC. 6.2 GOST 28147-89 Key Unwrap This algorithm decrypts GOST 28147-89 CEK with a GOST 28147-89 KEK. The GOST 28147-89 key unwrap algorithm is: 1. If the wrapped content-encryption key is not 44 octets, then error. 2. Decompose the the wrapped content-encryption key into IV, CEK_ENC and CEK_MAC. IV is the most significant (first) 8 octets, CEK_ENC is next 32 octets, and CEK_MAC is the least significant (last) 4 octets. 3. Decrypt CEK_ENC in ECB mode using KEK. Use IV, obrained in step 1. Call the output CEK. 4. Compute a 4-byte checksum value, gost28147IMIT (IV, KEK, CEK), compare the result CEK_MAC. If not equal, then error. 6.3 CryptoPro Key Wrap This algorithm encrypts GOST 28147-89 CEK with a GOST 28147-89 KEK. It can be used with any KEK, e.g. produced by VKO GOST R 34.10-94 or VKO GOST R 34.10-2001, because unique initialization vector is used to diversify the KEK. Identifier for this algorithm: id-Gost28147-89-CryptoPro-KeyWrap OBJECT IDENTIFIER ::= { id-CryptoPro-algorithms keyWrap(13) cryptoPro(1) } Popov,Kurepkin,Leontiev Informational [Page 7] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 The CryptoPro key wrap algorithm is: 1. For unique symmetric KEK, or KEK produced by VKO GOST R 34.10-94, generate 8 octets at random, call the result IV. For KEK, produced by VKO GOST R 34.10-2001, use the same IV, that was used for key derivation. 2. Diversify KEK, using CryptoPro KEK Diversification Algorithm, described in section 7.2.1, call the result KEK(IV); 3. Compute a 4-byte checksum value, gost28147IMIT (IV, KEK(IV), CEK), call the result CEK_MAC. 4. Encrypt CEK in ECB mode using KEK(IV). Use IV, generated in step 1. Call the ciphertext CEK_ENC. 5. Let RES = IV | CEK_ENC | CEK_MAC. 6.4 CryptoPro Key Unrap This algorithm encrypts GOST 28147-89 CEK with a GOST 28147-89 KEK. The CryptoPro key unwrap algorithm is: 1. If the wrapped content-encryption key is not 44 octets, then error. 2. Decompose the the wrapped content-encryption key into IV, CEK_ENC and CEK_MAC. IV is the most significant (first) 8 octets, CEK_ENC is next 32 octets, and CEK_MAC is the least significant (last) 4 octets. 3. Diversify KEK, using CryptoPro KEK Diversification Algorithm, described in section 6.5, call the result KEK(IV); 4. Decrypt CEK_ENC in ECB mode using KEK(IV). Use IV, obrained in step 1. Call the output CEK. 5. Compute a 4-byte checksum value, gost28147IMIT (IV, KEK(IV), CEK), compare the result CEK_MAC. If not equal, then error. 6.5 CryptoPro KEK Diversification Algorithm Given a random 64-bit synchrovector IV, and a GOST 28147-89 key K, this algorithm creates a new GOST 28147-89 key K(IV). 1. Let K[0] = K; 2. IV is split into components a[i,j]: IV = a[0]|...|a[7] (a[i] - byte, a[i,0]..a[i,7] - it's bits) 3. Let i be 0. 4. K[1]..K[8] are calculated by repeating the following algorithm eight times: Popov,Kurepkin,Leontiev Informational [Page 8] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 A) K[i] is split into components k[i,j]: K[i] = k[i,0]|k[i,1]|...|k[i,7] (k[i,j] - 32-bit integer) B) Vector S[i] is calculated: S[i] = ((a[i,0]*k[i,0] + ... + a[i,7]*k[i,7]) mod 2^32) | ((~a[i,0]*k[i,0] + ... + ~a[i,7]*k[i,7]) mod 2^32); C) K[i+1] = encryptCFB (S[i], K[i], K[i]) D) i = i + 1 5. Let K(IV) be K[8]. 7 Secret Key Diversification This algorithm creates a GOST 28147-89 key Kd, given GOST R 34.10-94 or GOST R 34.10-2001 secret key K and diversification data D of size 4..40 bytes. 1) 40-byte blob B is created from D by cloning it enough times to fill all 40 bytes. For example, if D is 40-bytes long, B = D; If D is 4-bytes long, B = D|D|D|D|D|D|D|D|D|D. 2) B is split into 8-byte SV and 32-byte SRCKEY (B = SV|SRCKEY). 3) Algorithm from section 6.5 is used to create K(SV) from key K and synchrovector SV, with two differences. Instead of S[i], vector (0,0,0,SV[i],ff,ff,ff,ff XOR SV[i]) is used, and during each encryption step, only 8 out of 32 GOST 28147-89 steps are done. 4) Kd is calculated: Kd = encryptCFB (IV, K(IV), SRCKEY). 8 Algorithm parameters Standards [GOST28147], [GOST341194], [GOSTR341094] and [GOSTR34102001] do not define specific values for algorithm parameters. This document introduces the use of OIDs to specify algorithm parameters. Identifiers and corresponding parameter values for all of the proposed parameter sets can be found in Appendix in the form of ASN.1 modules [X.660]. 8.1 Encryption algorithm parameters GOST 28147-89 can be used in several modes, additional CBC mode is defined in section 2.1 this document. It also has an S-Box parameter (see Algorithm Parameters part in [GOST28147] in Russian, description Popov,Kurepkin,Leontiev Informational [Page 9] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 in English see in [Schneier95] ch. 14.1, p. 331). This table contains the list of proposed parameter sets for GOST 28147-89: Gost28147-89-ParamSetAlgorithms ALGORITHM-IDENTIFIER ::= { { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-TestParamSet } | { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-CryptoPro-A-ParamSet } | { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-CryptoPro-B-ParamSet } | { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-CryptoPro-C-ParamSet } | { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-CryptoPro-D-ParamSet } | { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-CryptoPro-Simple-A-ParamSet } | { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-CryptoPro-Simple-B-ParamSet } | { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-CryptoPro-Simple-C-ParamSet } | { Gost28147-89-ParamSetParameters IDENTIFIED BY id-Gost28147-89-CryptoPro-Simple-D-ParamSet } } Identifier values can be found in Appendix. Parameters for GOST 28147-89 are presented in the following form: Gost28147-89-ParamSetParameters ::= SEQUENCE { eUZ Gost28147-89-UZ, mode INTEGER { gost28147-89-CNT(0), gost28147-89-CFB(1), cryptoPro-CBC(2) }, shiftBits INTEGER { gost28147-89-block(64) }, keyWrap AlgorithmIdentifier, keyMeshing AlgorithmIdentifier } Gost28147-89-UZ ::= OCTET STRING (SIZE (64)) Gost28147-89-KeyMeshingAlgorithms ALGORITHM-IDENTIFIER ::= { { NULL IDENTIFIED BY id-Gost28147-89-CryptoPro-KeyMeshing } | { NULL IDENTIFIED BY id-Gost28147-89-None-KeyMeshing } } Gost28147-89-KeyWrapAlgorithms ALGORITHM-IDENTIFIER ::= { { NULL IDENTIFIED BY id-Gost28147-89-CryptoPro-KeyWrap } | Popov,Kurepkin,Leontiev Informational [Page 10] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 { NULL IDENTIFIED BY id-Gost28147-89-None-KeyWrap } } where eUZ - S-box value; mode - cipher mode; shiftBits - cipher parameter; keyWrap - key export algorithm identifier; keyMeshing - key meshing algorithm identifier. 8.2 Digest algorithm parameters This table contains the list of proposed parameter sets for [GOST341194]: GostR3411-94-ParamSetAlgorithms ALGORITHM-IDENTIFIER ::= { { GostR3411-94-ParamSetParameters IDENTIFIED BY id-GostR3411-94-TestParamSet } | { GostR3411-94-ParamSetParameters IDENTIFIED BY id-GostR3411-94-CryptoProParamSet } } Identifier values can be found in Appendix. Parameters for [GOST341194] are presented in the following form: GostR3411-94-ParamSetParameters ::= SEQUENCE { hUZ Gost28147-89-UZ, -- S-Box for digest h0 GostR3411-94-Digest -- start digest value } GostR3411-94-Digest ::= OCTET STRING (SIZE (32)) 6.3 GOST R 34.10-94 public key algorithm parameters This table contains the list of proposed parameter sets for GOST R 34.10-94: GostR3410-94-ParamSetAlgorithm ALGORITHM-IDENTIFIER ::= { { GostR3410-94-ParamSetParameters IDENTIFIED BY id-GostR3410-94-TestParamSet } | { GostR3410-94-ParamSetParameters IDENTIFIED BY id-GostR3410-94-CryptoPro-A-ParamSet } | { GostR3410-94-ParamSetParameters IDENTIFIED BY id-GostR3410-94-CryptoPro-B-ParamSet } | { GostR3410-94-ParamSetParameters IDENTIFIED BY Popov,Kurepkin,Leontiev Informational [Page 11] Internet-Draft Crypto-Pro cryptographic algorithms 15 February 2004 id-GostR3410-94-CryptoPro-C-ParamSet } | { GostR3410-94-ParamSetParameters IDENTIFIED BY id-GostR3410-94-CryptoPro-D-ParamSet } | { GostR3410-94-ParamSetParameters IDENTIFIED BY id-GostR3410-94-CryptoPro-XchA-ParamSet } | { GostR3410-94-ParamSetParameters IDENTIFIED BY id-GostR3410-94-CryptoPro-XchB-ParamSet } | { GostR3410-94-ParamSetParameters IDENTIFIED BY id-GostR3410-94-CryptoPro-XchC-ParamSet } } Identifier values can be found in Appendix. Parameters for GOST R 34.10-94 are presented in the following form: GostR3410-94-ParamSetParameters ::= SEQUENCE { p INTEGER, q INTEGER, a INTEGER, validationAlgorithm AlgorithmIdentifier {{ GostR3410-94-ValidationAlgorithms }} OPTIONAL } GostR3410-94-ValidationParameters ::= SEQUENCE { t INTEGER, x0 INTEGER, c INTEGER, d INTEGER OPTIONAL } Where p - modulus, prime number, 2^1023