idnits 2.17.1 draft-smyshlyaev-mgm-09.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 19, 2018) is 2010 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Smyshlyaev, Ed. 3 Internet-Draft CryptoPro 4 Intended status: Informational V. Nozdrunov 5 Expires: April 22, 2019 V. Shishkin 6 TC 26 7 October 19, 2018 9 Multilinear Galois Mode (MGM) 10 draft-smyshlyaev-mgm-09 12 Abstract 14 Multilinear Galois Mode (MGM) is an authenticated encryption with 15 associated data block cipher mode based on EtM principle. MGM is 16 defined for use with 64-bit and 128-bit block ciphers. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at https://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on April 22, 2019. 35 Copyright Notice 37 Copyright (c) 2018 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (https://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 53 1.1. Existing Constructions . . . . . . . . . . . . . . . . . 2 54 2. Conventions Used in This Document . . . . . . . . . . . . . . 2 55 3. Basic Terms and Definitions . . . . . . . . . . . . . . . . . 2 56 4. Specification . . . . . . . . . . . . . . . . . . . . . . . . 4 57 4.1. MGM Encryption and Authentication Procedure . . . . . . . 4 58 4.2. MGM Decryption and Authentication Check Procedure . . . . 6 59 5. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 7 60 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 61 6.1. Normative References . . . . . . . . . . . . . . . . . . 8 62 6.2. Informative References . . . . . . . . . . . . . . . . . 8 63 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 8 64 Appendix B. Contributors . . . . . . . . . . . . . . . . . . . . 12 65 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 67 1. Introduction 69 Multilinear Galois Mode (MGM) is an authenticated encryption with 70 associated data block cipher mode based on EtM principle. MGM is 71 defined for use with 64-bit and 128-bit block. The MGM design 72 principles can easily be applied to other block sizes. 74 1.1. Existing Constructions 76 The text will be added in the future versions of the draft. 78 2. Conventions Used in This Document 80 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 81 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 82 document are to be interpreted as described in [RFC2119]. 84 3. Basic Terms and Definitions 86 This document uses the following terms and definitions for the sets 87 and operations on the elements of these sets: 89 V* the set of all bit strings of a finite length (hereinafter 90 referred to as strings), including the empty string; 91 substrings and string components are enumerated from right to 92 left starting from zero; 94 V_s the set of all bit strings of length s, where s is a non- 95 negative integer; 97 |X| the bit length of the bit string X (if X is an empty string, 98 then |X| = 0); 100 X || Y concatenation of strings X and Y both belonging to V*, i.e., 101 a string from V_{|X|+|Y|}, where the left substring from 102 V_{|X|} is equal to X, and the right substring from V_{|Y|} 103 is equal to Y; 105 a^s the string in V_s that consists of s 'a' bits: a^s = (a, a, 106 ... , a), 'a' in V_1; 108 (xor) exclusive-or of the two bit strings of the same length, 110 Z_{2^s} ring of residues modulo 2^s; 112 MSB_i: V_s -> V_i the transformation that maps the string X = 113 (x_{s-1}, ... , x_0) in V_s into the string MSB_i(X) = 114 (x_{s-1}, ... , x_{s-i}) in V_i, i <= s, (most significant 115 bits); 117 Int_s: V_s -> Z_{2^s} the transformation that maps a string X = 118 (x_{s-1}, ... , x_0) in V_s into the integer Int_s(X) = 119 2^{s-1} * x_{s-1} + ... + 2 * x_1 + x_0 (the interpretation 120 of the bit string as an integer); 122 Vec_s: Z_{2^s} -> V_s the transformation inverse to the mapping 123 Int_s (the interpretation of an integer as a bit string); 125 E_K: V_n -> V_n the block cipher permutation under the key K in V_k; 127 k the bit length of the block cipher key; 129 n the block size of the block cipher (in bits); 131 len: V_s -> V_{n/2} the transformation that maps a string X in V_s, 132 0 <= s <= 2^{n/2} - 1, into the string len(X) = 133 Vec_{n/2}(|X|) in V_{n/2}, where n is the block size of the 134 used block cipher; 136 [+] the addition operation in Z_{2^{n/2}}, where n is the block 137 size of the used block cipher; 139 (x) multiplication in GF(2^n), where n is the block size of the 140 used block cipher; if n = 64, then the field polynomial is 141 equal to f = x^64 + x^4 + x^3 + x + 1; if n = 128, then the 142 field polynomial is equal to f = x^128 + x^7 + x^2 + x + 1; 144 incr_l: V_n -> V_n the transformation that maps a string L || R, 145 where L, R in V_{n/2}, into the string incr_l(L || R ) = 146 Vec_{n/2}(Int_{n/2}(L) [+] 1) || R; 148 incr_r: V_n -> V_n the transformation that maps a string L || R, 149 where L, R in V_{n/2}, into the string incr_r(L || R ) = L || 150 Vec_{n/2}(Int_{n/2}(R) [+] 1). 152 4. Specification 154 An additional parameter that defines the functioning of MGM mode is 155 the size S of the authentication field (in bits). The value of S 156 MUST be fixed for a particular protocol, 32 <= S <= 128. The choice 157 of the value S involves a trade-off between message expansion and the 158 probability that an attacker can modify a message undetectably. 160 4.1. MGM Encryption and Authentication Procedure 162 The MGM encryption and authentication procedure takes the following 163 parameters as inputs: 165 1. Encryption key K in V_k. 167 2. Initial counter nonce ICN in V_{n-1}. 169 3. Plaintext P, 0 <= |P| < 2^{n/2}. If |P| > 0, then P = P_1 || 170 ... || P*_q, P_i in V_n, i = 1, ... , q - 1, P*_q in V_u, 1 <= u 171 <= n. If |P| = 0, then by definition P*_q is empty, q = 0, and u 172 = n. 174 4. Associated authenticated data A, 0 <= |A| < 2^{n/2}. If |A| > 0, 175 then A = A_1 || ... || A*_h, A_j in V_n, j = 1, ... , h - 1, A*_h 176 in V_t, 1 <= t <= n. If |A| = 0, then by definition A*_h is 177 empty, h = 0, and t = n. The associated data is authenticated 178 but is not encrypted. 180 The MGM encryption and authentication procedure outputs the following 181 parameters: 183 1. Initial counter nonce ICN. 185 2. Associated authenticated data A. 187 3. Ciphertext C in V_{|P|}. 189 4. Authentication tag T in V_S. 191 The MGM encryption and authentication procedure consists of the 192 following steps: 194 +----------------------------------------------------------------+ 195 | MGM-Encrypt(K, ICN, P, A) | 196 |----------------------------------------------------------------| 197 | 1. Encryption step: | 198 | - Y_1 = E_K(0^1 || ICN), | 199 | - For i = 2, 3, ... , q do | 200 | Y_i = incr_r(Y_{i-1}), | 201 | - For i = 1, 2, ... , q - 1 do | 202 | C_i = P_i (xor) E_K(Y_i), | 203 | - C*_q = P*_q (xor) MSB_u(E_K(Y_q)), | 204 | - C = C_1 || ... || C*_q. | 205 | | 206 | 2. Padding step: | 207 | - A_h = A*_h || 0^{n-t}, | 208 | - C_q = C*_q || 0^{n-u}. | 209 | | 210 | 3. Authentication tag T generation step: | 211 | - Z_1 = E_K(1^1 || ICN), | 212 | - sum = 0, | 213 | - For i = 1, 2, ..., h do | 214 | H_i = E_K(Z_i), | 215 | sum = sum (xor) H_i (x) A_i, | 216 | Z_{i+1} = incr_l(Z_i), | 217 | - For j = 1, 2, ..., q do | 218 | H_{h+j} = E_K(Z_{h+j}), | 219 | sum = sum (xor) H_{h+j} (x) C_j, | 220 | Z_{h+j+1} = incr_l(Z_{h+j}), | 221 | - H_{h+q+1} = E_K(Z_{h+q+1}), | 222 | - T = MSB_S(E_K(sum (xor) H_{h+q+1} (x) | 223 | (len(A) || len(C)))). | 224 | | 225 | 4. Return (ICN, A, C, T). | 226 |----------------------------------------------------------------+ 228 The ICN value for each message that is encrypted under the given key 229 K must be chosen in a unique manner. Using the same ICN values for 230 two different messages encrypted with the same key eliminates the 231 security properties of this mode. 233 Users who do not wish to encrypt plaintext can provide a string P of 234 length zero. Users who do not wish to authenticate associated data 235 can provide a string A of length zero. The length of the associated 236 data A and of the plaintext P MUST be such that 0 < |A| + |P| < 237 2^{n/2}. 239 4.2. MGM Decryption and Authentication Check Procedure 241 The MGM decryption and authentication procedure takes the following 242 parameters as inputs: 244 1. The encryption key K in V_k. 246 2. The initial counter nonce ICN in V_{n-1}. 248 3. The associated authenticated data A, 0 <= |A| < 2^{n/2}. A = 249 A_1 || ... || A*_h, A_j in V_n, j = 1, ... , h - 1, A*_h in V_t, 250 1 <= t <= n. 252 4. The ciphertext C, 0 <= |C| < 2^{n/2}. C = C_1 || ... || C*_q, C_i 253 in V_n, i = 1, ... , q - 1, C*_q in V_u, 1 <= u <= n. 255 5. The authenticated tag T in V_S. 257 The MGM decryption and authentication procedure outputs FAIL or the 258 following parameters: 260 1. Plaintext P in V_{|C|}. 262 2. Associated authenticated data A. 264 The MGM decryption and authentication procedure consists of the 265 following steps: 267 +----------------------------------------------------------------+ 268 | MGM-Decrypt(K, ICN, A, C, T) | 269 |----------------------------------------------------------------| 270 | 1. Padding step: | 271 | - A_h = A*_h || 0^{n-t}, | 272 | - C_q = C*_q || 0^{n-u}. | 273 | | 274 | 2. Authentication tag T' generation step: | 275 | - Z_1 = E_K(1^1 || ICN), | 276 | - sum1 = 0, sum2 = 0, | 277 | - For i = 1, 2, ..., h do | 278 | H_i = E_K(Z_i), | 279 | sum1 = sum1 (xor) H_i (x) A_i, | 280 | Z_{i+1} = incr_l(Z_i), | 281 | - For j = 1, 2, ..., q do | 282 | H_{h+j} = E_K(Z_{h+j}), | 283 | sum2 = sum2 (xor) H_{h+j} (x) C_j, | 284 | Z_{h+j+1} = incr_l(Z_{h+j}), | 285 | - H_{h+q+1} = E_K(Z_{h+q+1}), | 286 | - T' = MSB_S(E_K(sum1 (xor) sum2 (xor) | 287 | H_{h+q+1} (x) (len(A) || len(C)))), | 288 | - If T' != T then return FAIL | 289 | return FAIL. | 290 | | 291 | 3. Decryption step: | 292 | - Y_1 = E_K(0^1 || ICN), | 293 | - For i = 2, 3, ... , q do | 294 | Y_i = incr_r(Y_{i-1}), | 295 | - For i = 1, 2, ... , q - 1 do | 296 | P_i = C_i (xor) E_K(Y_i), | 297 | - P*_q = C*_q (xor) MSB_u(E_K(Y_q)), | 298 | - P = P_1 || ... || P*_q. | 299 | | 300 | 4. Return (P, A). | 301 |----------------------------------------------------------------+ 303 5. Rationale 305 The MGM mode was originally proposed in [PDMODE]. 307 The MGM mode is designed to be fast, parallelizable, inverse free, 308 online and secure. 310 The MGM is based on counters for the reasons of performance. The 311 first counter (Y_i, see Section 4.1) is used for message encryption, 312 the second counter (H_i, see Section 4.1) is used for authentication. 313 The second counter is encrypted eliminating the chance of obtaining 314 any information about the H_k value in case when the H_l value is 315 known to the adversary ( here l is not equal to k ). 317 To provide parallelizable authentication a multilinear function is 318 used. 320 To avoid attacks based on padding and linear properties of 321 multilinear function the lengths of associated data A, encrypted 322 message C, and encrypting authentication tag is added. 324 A collision of "usual" counters leads to obtaining the information 325 about the H_i values and possible authentication vulnerabilities. To 326 minimize the probability of this event we change the principle of 327 counters operating by using the functions incr_l and incr_r. To 328 counteract finding collisions we encrypt initial values of both 329 counters. 331 6. References 333 6.1. Normative References 335 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 336 Requirement Levels", BCP 14, RFC 2119, 337 DOI 10.17487/RFC2119, March 1997, 338 . 340 [RFC7801] Dolmatov, V., Ed., "GOST R 34.12-2015: Block Cipher 341 "Kuznyechik"", RFC 7801, DOI 10.17487/RFC7801, March 2016, 342 . 344 6.2. Informative References 346 [GOST3412-2015] 347 Federal Agency on Technical Regulating and Metrology, 348 "Information technology. Cryptographic data security. 349 Block ciphers", GOST R 34.12-2015, 2015. 351 [PDMODE] Vladislav Nozdrunov, "Parallel and double block cipher 352 mode of operation (PD-mode) for authenticated encryption", 353 CTCrypt 2017 proceedings, pp. 36-45, 2017. 355 Appendix A. Test Vectors 357 Test vectors for the Kuznyechik block cipher (n = 128, k = 256) 358 defined in [GOST3412-2015] (the English version can be found in 359 [RFC7801]). 361 Encryption key K: 362 00000: 88 99 AA BB CC DD EE FF 00 11 22 33 44 55 66 77 363 00010: FE DC BA 98 76 54 32 10 01 23 45 67 89 AB CD EF 365 Associated authenticated data A: 366 00000: 02 02 02 02 02 02 02 02 01 01 01 01 01 01 01 01 367 00010: 04 04 04 04 04 04 04 04 03 03 03 03 03 03 03 03 368 00020: EA 05 05 05 05 05 05 05 05 370 Plaintext P: 371 00000: 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 372 00010: 00 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 373 00020: 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 374 00030: 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 375 00040: AA BB CC 377 1. Encryption step: 379 0^1 || ICN: 380 00000: 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 382 Y_1: 383 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED CD 384 E_K(Y_1): 385 00000: B8 57 48 C5 12 F3 19 90 AA 56 7E F1 53 35 DB 74 387 Y_2: 388 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED CE 389 E_K(Y_2): 390 00000: 80 64 F0 12 6F AC 9B 2C 5B 6E AC 21 61 2F 94 33 392 Y_3: 393 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED CF 394 E_K(Y_3): 395 00000: 58 58 82 1D 40 C0 CD 0D 0A C1 E6 C2 47 09 8F 1C 397 Y_4: 398 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED D0 399 E_K(Y_4): 400 00000: E4 3F 50 81 B5 8F 0B 49 01 2F 8E E8 6A CD 6D FA 402 Y_5: 403 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED D1 404 E_K(Y_5): 405 00000: 86 CE 9E 2A 0A 12 25 E3 33 56 91 B2 0D 5A 33 48 407 C: 408 00000: A9 75 7B 81 47 95 6E 90 55 B8 A3 3D E8 9F 42 FC 409 00010: 80 75 D2 21 2B F9 FD 5B D3 F7 06 9A AD C1 6B 39 410 00020: 49 7A B1 59 15 A6 BA 85 93 6B 5D 0E A9 F6 85 1C 411 00030: C6 0C 14 D4 D3 F8 83 D0 AB 94 42 06 95 C7 6D EB 412 00040: 2C 75 52 414 2. Padding step: 416 A_1 || ... || A_h: 417 00000: 02 02 02 02 02 02 02 02 01 01 01 01 01 01 01 01 418 00010: 04 04 04 04 04 04 04 04 03 03 03 03 03 03 03 03 419 00020: EA 05 05 05 05 05 05 05 05 00 00 00 00 00 00 00 421 C_1 || ... || C_q: 422 00000: A9 75 7B 81 47 95 6E 90 55 B8 A3 3D E8 9F 42 FC 423 00010: 80 75 D2 21 2B F9 FD 5B D3 F7 06 9A AD C1 6B 39 424 00020: 49 7A B1 59 15 A6 BA 85 93 6B 5D 0E A9 F6 85 1C 425 00030: C6 0C 14 D4 D3 F8 83 D0 AB 94 42 06 95 C7 6D EB 426 00040: 2C 75 52 00 00 00 00 00 00 00 00 00 00 00 00 00 428 3. Authentication tag T generation step: 430 1^1 || ICN: 431 00000: 91 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 433 Z_1: 434 00000: 7F C2 45 A8 58 6E 66 02 A7 BB DB 27 86 BD C6 6F 435 H_1: 436 00000: 8D B1 87 D6 53 83 0E A4 BC 44 64 76 95 2C 30 0B 437 current sum: 438 00000: 4C F4 27 F4 AD B7 5C F4 C0 DA 39 D5 AB 48 CF 38 440 Z_2: 441 00000: 7F C2 45 A8 58 6E 66 03 A7 BB DB 27 86 BD C6 6F 442 H_2: 443 00000: 7A 24 F7 26 30 E3 76 37 21 C8 F3 CD B1 DA 0E 31 444 current sum: 445 00000: 94 95 44 0E F6 24 A1 DD C6 F5 D9 77 28 50 C5 73 447 Z_3: 448 00000: 7F C2 45 A8 58 6E 66 04 A7 BB DB 27 86 BD C6 6F 449 H_3: 450 00000: 44 11 96 21 17 D2 06 35 C5 25 E0 A2 4D B4 B9 0A 451 current sum: 452 00000: A4 9A 8C D8 A6 F2 74 23 DB 79 E4 4A B3 06 D9 42 454 Z_4: 455 00000: 7F C2 45 A8 58 6E 66 05 A7 BB DB 27 86 BD C6 6F 456 H_4: 457 00000: D8 C9 62 3C 4D BF E8 14 CE 7C 1C 0C EA A9 59 DB 458 current sum: 459 00000: 09 FE 3F 6A 83 3C 21 B3 90 27 D0 20 6A 84 E1 5A 461 Z_5: 462 00000: 7F C2 45 A8 58 6E 66 06 A7 BB DB 27 86 BD C6 6F 463 H_5: 464 00000: A5 E1 F1 95 33 3E 14 82 96 99 31 BF BE 6D FD 43 465 current sum: 466 00000: B5 DA 26 BB 00 EB A8 04 35 D7 97 6B C6 B5 46 4D 468 Z_6: 469 00000: 7F C2 45 A8 58 6E 66 07 A7 BB DB 27 86 BD C6 6F 470 H_6: 471 00000: B4 CA 80 8C AC CF B3 F9 17 24 E4 8A 2C 7E E9 D2 472 current sum: 473 00000: DD 1C 0E EE F7 83 C8 EB 2A 33 F3 58 D7 23 0E E5 475 Z_7: 476 00000: 7F C2 45 A8 58 6E 66 08 A7 BB DB 27 86 BD C6 6F 477 H_7: 478 00000: 72 90 8F C0 74 E4 69 E8 90 1B D1 88 EA 91 C3 31 479 current sum: 480 00000: 89 6C E1 08 32 EB EA F9 06 9F 3F 73 76 59 4D 40 482 Z_8: 483 00000: 7F C2 45 A8 58 6E 66 09 A7 BB DB 27 86 BD C6 6F 484 H_8: 485 00000: 23 CA 27 15 B0 2C 68 31 3B FD AC B3 9E 4D 0F B8 486 current sum: 487 00000: 99 1A F5 C9 D0 80 F7 63 87 FE 64 9E 7C 93 C6 42 489 Z_9: 490 00000: 7F C2 45 A8 58 6E 66 0A A7 BB DB 27 86 BD C6 6F 491 H_9: 492 00000: BC BC E6 C4 1A A3 55 A4 14 88 62 BF 64 BD 83 0D 493 len(A) || len(C): 494 00000: 00 00 00 00 00 00 01 48 00 00 00 00 00 00 02 18 495 sum (xor) H_9 (x) (len(A) || len(C)): 496 00000: C0 C7 22 DB 5E 0B D6 DB 25 76 73 83 3D 56 71 28 498 Tag T: 499 00000: CF 5D 65 6F 40 C3 4F 5C 46 E8 BB 0E 29 FC DB 4C 501 Appendix B. Contributors 503 o Evgeny Alekseev 504 CryptoPro 505 alekseev@cryptopro.ru 507 o Ekaterina Smyshlyaeva 508 CryptoPro 509 ess@cryptopro.ru 511 o Lilia Ahmetzyanova 512 CryptoPro 513 lah@cryptopro.ru 515 o Grigory Marshalko 516 TC 26 517 marshalko_gb@tc26.ru 519 o Vladimir Rudskoy 520 TC 26 521 rudskoy_vi@tc26.ru 523 o Alexey Nesterenko 524 National Research University Higher School of Economics 525 anesterenko@hse.ru 527 Authors' Addresses 529 Stanislav Smyshlyaev (editor) 530 CryptoPro 532 Phone: +7 (495) 995-48-20 533 Email: svs@cryptopro.ru 535 Vladislav Nozdrunov 536 TC 26 538 Email: nozdrunov_vi@tc26.ru 540 Vasily Shishkin 541 TC 26 543 Email: shishkin_va@tc26.ru