idnits 2.17.1 draft-smyshlyaev-mgm-08.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 (June 29, 2018) is 2126 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: December 31, 2018 V. Shishkin 6 TC 26 7 June 29, 2018 9 Multilinear Galois Mode (MGM) 10 draft-smyshlyaev-mgm-08 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 December 31, 2018. 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 . . . . . . . . . . . . . . . . . . . . 11 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}. P = P_1 || ... || P*_q, P_i in 170 V_n, i = 1, ... , q - 1, P*_q in V_u, 1 <= u <= n. 172 4. Associated authenticated data A, 0 <= |A| < 2^{n/2}. A = A_1 || 173 ... || A*_h, A_j in V_n, j = 1, ... , h - 1, A*_h in V_t, 1 <= t 174 <= n. The associated data is authenticated but is not encrypted. 176 The MGM encryption and authentication procedure outputs the following 177 parameters: 179 1. Initial counter nonce ICN. 181 2. Associated authenticated data A. 183 3. Ciphertext C in V_{|P|}. 185 4. Authentication tag T in V_S. 187 The MGM encryption and authentication procedure consists of the 188 following steps: 190 +----------------------------------------------------------------+ 191 | MGM-Encrypt(K, ICN, P, A) | 192 |----------------------------------------------------------------| 193 | 1. Encryption step: | 194 | - Y_1 = E_K(0^1 || ICN), | 195 | - For i = 2, 3, ... , q do | 196 | Y_i = incr_r(Y_{i-1}), | 197 | - For i = 1, 2, ... , q - 1 do | 198 | C_i = P_i (xor) E_K(Y_i), | 199 | - C*_q = P*_q (xor) MSB_u(E_K(Y_q)), | 200 | - C = C_1 || ... || C*_q. | 201 | | 202 | 2. Padding step: | 203 | - A_h = A*_h || 0^{n-t}, | 204 | - C_q = C*_q || 0^{n-u}. | 205 | | 206 | 3. Authentication tag T generation step: | 207 | - Z_1 = E_K(1^1 || ICN), | 208 | - sum = 0, | 209 | - For i = 1, 2, ..., h do | 210 | H_i = E_K(Z_i), | 211 | sum = sum (xor) H_i (x) A_i, | 212 | Z_{i+1} = incr_l(Z_i), | 213 | - For j = 1, 2, ..., q do | 214 | H_{h+j} = E_K(Z_{h+j}), | 215 | sum = sum (xor) H_{h+j} (x) C_j, | 216 | Z_{h+j+1} = incr_l(Z_{h+j}), | 217 | - H_{h+q+1} = E_K(Z_{h+q+1}), | 218 | - T = MSB_S(E_K(sum (xor) H_{h+q+1} (x) | 219 | (len(A) || len(C)))). | 220 | | 221 | 4. Return (ICN, A, C, T). | 222 |----------------------------------------------------------------+ 224 The ICN value for each message that is encrypted under the given key 225 K must be chosen in a unique manner. Using the same ICN values for 226 two different messages encrypted with the same key eliminates the 227 security properties of this mode. 229 Users who do not wish to encrypt plaintext can provide a string P of 230 length zero. Users who do not wish to authenticate associated data 231 can provide a string A of length zero. The length of the associated 232 data A and of the plaintext P MUST be such that 0 < |A| + |P| < 233 2^{n/2}. 235 4.2. MGM Decryption and Authentication Check Procedure 237 The MGM decryption and authentication procedure takes the following 238 parameters as inputs: 240 1. The encryption key K in V_k. 242 2. The initial counter nonce ICN in V_{n-1}. 244 3. The associated authenticated data A, 0 <= |A| < 2^{n/2}. A = 245 A_1 || ... || A*_h, A_j in V_n, j = 1, ... , h - 1, A*_h in V_t, 246 1 <= t <= n. 248 4. The ciphertext C, 0 <= |C| < 2^{n/2}. C = C_1 || ... || C*_q, C_i 249 in V_n, i = 1, ... , q - 1, C*_q in V_u, 1 <= u <= n. 251 5. The authenticated tag T in V_S. 253 The MGM decryption and authentication procedure outputs FAIL or the 254 following parameters: 256 1. Plaintext P in V_{|C|}. 258 2. Associated authenticated data A. 260 The MGM decryption and authentication procedure consists of the 261 following steps: 263 +----------------------------------------------------------------+ 264 | MGM-Decrypt(K, ICN, A, C, T) | 265 |----------------------------------------------------------------| 266 | 1. Padding step: | 267 | - A_h = A*_h || 0^{n-t}, | 268 | - C_q = C*_q || 0^{n-u}. | 269 | | 270 | 2. Authentication tag T' generation step: | 271 | - Z_1 = E_K(1^1 || ICN), | 272 | - sum1 = 0, sum2 = 0, | 273 | - For i = 1, 2, ..., h do | 274 | H_i = E_K(Z_i), | 275 | sum1 = sum1 (xor) H_i (x) A_i, | 276 | Z_{i+1} = incr_l(Z_i), | 277 | - For j = 1, 2, ..., q do | 278 | H_{h+j} = E_K(Z_{h+j}), | 279 | sum2 = sum2 (xor) H_{h+j} (x) C_j, | 280 | Z_{h+j+1} = incr_l(Z_{h+j}), | 281 | - H_{h+q+1} = E_K(Z_{h+q+1}), | 282 | - T' = MSB_S(E_K(sum1 (xor) sum2 (xor) | 283 | H_{h+q+1} (x) (len(A) || len(C)))), | 284 | - If T' != T then return FAIL | 285 | return FAIL. | 286 | | 287 | 3. Decryption step: | 288 | - Y_1 = E_K(0^1 || ICN), | 289 | - For i = 2, 3, ... , q do | 290 | Y_i = incr_r(Y_{i-1}), | 291 | - For i = 1, 2, ... , q - 1 do | 292 | P_i = C_i (xor) E_K(Y_i), | 293 | - P*_q = C*_q (xor) MSB_u(E_K(Y_q)), | 294 | - P = P_1 || ... || P*_q. | 295 | | 296 | 4. Return (P, A). | 297 |----------------------------------------------------------------+ 299 5. Rationale 301 The mode was originally proposed in [PDMODE]. 303 During the construction of the MGM mode our task was to create a 304 fast, parallelizable, inverse free, online and secure block cipher 305 mode. The MGM is based on counters for reasons of performance. The 306 first counter is used for message encryption, the second counter is 307 used for authentication. 309 For providing parallelizable authentication a multilinear function is 310 used. By encrypting the second counter we produce elements H_i with 311 the property that if one knows any information about value H_k he/she 312 can't obtain any information about value H_l ( l is not equal to k ) 313 besides that H_k is not equal to H_l. 315 By adding the length of associated data A and encrypted message C and 316 encrypting authentication tag we avoid attacks based on padding and 317 linear properties of multilinear function. 319 A collision of "usual" counters leads to obtaining information about 320 values H_i, that could be dangerous to authentication. For 321 minimizing probability of this event we change the principle of 322 counters operating by using the functions incr_l and incr_l. To 323 counteract finding collisions we encrypt initialization values of 324 both counters. 326 6. References 328 6.1. Normative References 330 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 331 Requirement Levels", BCP 14, RFC 2119, 332 DOI 10.17487/RFC2119, March 1997, 333 . 335 6.2. Informative References 337 [PDMODE] Vladislav Nozdrunov, "Parallel and double block cipher 338 mode of operation (PD-mode) for authenticated encryption", 339 CTCrypt 2017 proceedings, pp. 36-45, 2017. 341 Appendix A. Test Vectors 343 Test vectors for the Kuznyechik block cipher (n = 128, k = 256) 345 Encryption key K: 346 00000: 88 99 AA BB CC DD EE FF 00 11 22 33 44 55 66 77 347 00010: FE DC BA 98 76 54 32 10 01 23 45 67 89 AB CD EF 349 Associated authenticated data A: 350 00000: 02 02 02 02 02 02 02 02 01 01 01 01 01 01 01 01 351 00010: 04 04 04 04 04 04 04 04 03 03 03 03 03 03 03 03 352 00020: EA 05 05 05 05 05 05 05 05 354 Plaintext P: 355 00000: 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 356 00010: 00 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 357 00020: 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 358 00030: 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 359 00040: AA BB CC 361 1. Encryption step: 363 0^1 || ICN: 364 00000: 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 366 Y_1: 367 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED CD 368 E_K(Y_1): 369 00000: B8 57 48 C5 12 F3 19 90 AA 56 7E F1 53 35 DB 74 371 Y_2: 372 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED CE 373 E_K(Y_2): 374 00000: 80 64 F0 12 6F AC 9B 2C 5B 6E AC 21 61 2F 94 33 376 Y_3: 377 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED CF 378 E_K(Y_3): 379 00000: 58 58 82 1D 40 C0 CD 0D 0A C1 E6 C2 47 09 8F 1C 381 Y_4: 382 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED D0 383 E_K(Y_4): 384 00000: E4 3F 50 81 B5 8F 0B 49 01 2F 8E E8 6A CD 6D FA 386 Y_5: 387 00000: 7F 67 9D 90 BE BC 24 30 5A 46 8D 42 B9 D4 ED D1 388 E_K(Y_5): 389 00000: 86 CE 9E 2A 0A 12 25 E3 33 56 91 B2 0D 5A 33 48 391 C: 392 00000: A9 75 7B 81 47 95 6E 90 55 B8 A3 3D E8 9F 42 FC 393 00010: 80 75 D2 21 2B F9 FD 5B D3 F7 06 9A AD C1 6B 39 394 00020: 49 7A B1 59 15 A6 BA 85 93 6B 5D 0E A9 F6 85 1C 395 00030: C6 0C 14 D4 D3 F8 83 D0 AB 94 42 06 95 C7 6D EB 396 00040: 2C 75 52 398 2. Padding step: 400 A_1 || ... || A_h: 401 00000: 02 02 02 02 02 02 02 02 01 01 01 01 01 01 01 01 402 00010: 04 04 04 04 04 04 04 04 03 03 03 03 03 03 03 03 403 00020: EA 05 05 05 05 05 05 05 05 00 00 00 00 00 00 00 404 C_1 || ... || C_q: 405 00000: A9 75 7B 81 47 95 6E 90 55 B8 A3 3D E8 9F 42 FC 406 00010: 80 75 D2 21 2B F9 FD 5B D3 F7 06 9A AD C1 6B 39 407 00020: 49 7A B1 59 15 A6 BA 85 93 6B 5D 0E A9 F6 85 1C 408 00030: C6 0C 14 D4 D3 F8 83 D0 AB 94 42 06 95 C7 6D EB 409 00040: 2C 75 52 00 00 00 00 00 00 00 00 00 00 00 00 00 411 3. Authentication tag T generation step: 413 1^1 || ICN: 414 00000: 91 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 416 Z_1: 417 00000: 7F C2 45 A8 58 6E 66 02 A7 BB DB 27 86 BD C6 6F 418 H_1: 419 00000: 8D B1 87 D6 53 83 0E A4 BC 44 64 76 95 2C 30 0B 420 current sum: 421 00000: 4C F4 27 F4 AD B7 5C F4 C0 DA 39 D5 AB 48 CF 38 423 Z_2: 424 00000: 7F C2 45 A8 58 6E 66 03 A7 BB DB 27 86 BD C6 6F 425 H_2: 426 00000: 7A 24 F7 26 30 E3 76 37 21 C8 F3 CD B1 DA 0E 31 427 current sum: 428 00000: 94 95 44 0E F6 24 A1 DD C6 F5 D9 77 28 50 C5 73 430 Z_3: 431 00000: 7F C2 45 A8 58 6E 66 04 A7 BB DB 27 86 BD C6 6F 432 H_3: 433 00000: 44 11 96 21 17 D2 06 35 C5 25 E0 A2 4D B4 B9 0A 434 current sum: 435 00000: A4 9A 8C D8 A6 F2 74 23 DB 79 E4 4A B3 06 D9 42 437 Z_4: 438 00000: 7F C2 45 A8 58 6E 66 05 A7 BB DB 27 86 BD C6 6F 439 H_4: 440 00000: D8 C9 62 3C 4D BF E8 14 CE 7C 1C 0C EA A9 59 DB 441 current sum: 442 00000: 09 FE 3F 6A 83 3C 21 B3 90 27 D0 20 6A 84 E1 5A 444 Z_5: 445 00000: 7F C2 45 A8 58 6E 66 06 A7 BB DB 27 86 BD C6 6F 446 H_5: 447 00000: A5 E1 F1 95 33 3E 14 82 96 99 31 BF BE 6D FD 43 448 current sum: 449 00000: B5 DA 26 BB 00 EB A8 04 35 D7 97 6B C6 B5 46 4D 450 Z_6: 451 00000: 7F C2 45 A8 58 6E 66 07 A7 BB DB 27 86 BD C6 6F 452 H_6: 453 00000: B4 CA 80 8C AC CF B3 F9 17 24 E4 8A 2C 7E E9 D2 454 current sum: 455 00000: DD 1C 0E EE F7 83 C8 EB 2A 33 F3 58 D7 23 0E E5 457 Z_7: 458 00000: 7F C2 45 A8 58 6E 66 08 A7 BB DB 27 86 BD C6 6F 459 H_7: 460 00000: 72 90 8F C0 74 E4 69 E8 90 1B D1 88 EA 91 C3 31 461 current sum: 462 00000: 89 6C E1 08 32 EB EA F9 06 9F 3F 73 76 59 4D 40 464 Z_8: 465 00000: 7F C2 45 A8 58 6E 66 09 A7 BB DB 27 86 BD C6 6F 466 H_8: 467 00000: 23 CA 27 15 B0 2C 68 31 3B FD AC B3 9E 4D 0F B8 468 current sum: 469 00000: 99 1A F5 C9 D0 80 F7 63 87 FE 64 9E 7C 93 C6 42 471 Z_9: 472 00000: 7F C2 45 A8 58 6E 66 0A A7 BB DB 27 86 BD C6 6F 473 H_9: 474 00000: BC BC E6 C4 1A A3 55 A4 14 88 62 BF 64 BD 83 0D 475 len(A) || len(C): 476 00000: 00 00 00 00 00 00 01 48 00 00 00 00 00 00 02 18 477 sum (xor) H_9 (x) (len(A) || len(C)): 478 00000: C0 C7 22 DB 5E 0B D6 DB 25 76 73 83 3D 56 71 28 480 Tag T: 481 00000: CF 5D 65 6F 40 C3 4F 5C 46 E8 BB 0E 29 FC DB 4C 483 Appendix B. Contributors 485 o Evgeny Alekseev 486 CryptoPro 487 alekseev@cryptopro.ru 489 o Ekaterina Smyshlyaeva 490 CryptoPro 491 ess@cryptopro.ru 493 o Lilia Ahmetzyanova 494 CryptoPro 495 lah@cryptopro.ru 497 o Grigory Marshalko 498 TC 26 499 marshalko_gb@tc26.ru 501 o Vladimir Rudskoy 502 TC 26 503 rudskoy_vi@tc26.ru 505 o Alexey Nesterenko 506 National Research University Higher School of Economics 507 anesterenko@hse.ru 509 Authors' Addresses 511 Stanislav Smyshlyaev (editor) 512 CryptoPro 514 Phone: +7 (495) 995-48-20 515 Email: svs@cryptopro.ru 517 Vladislav Nozdrunov 518 TC 26 520 Email: nozdrunov_vi@tc26.ru 522 Vasily Shishkin 523 TC 26 525 Email: shishkin_va@tc26.ru