idnits 2.17.1 draft-smyshlyaev-mgm-05.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 (March 5, 2018) is 2234 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: September 6, 2018 V. Shishkin 6 TC 26 7 March 5, 2018 9 Multiline Galois Mode (MGM) 10 draft-smyshlyaev-mgm-05 12 Abstract 14 Multiline 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 September 6, 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 . . . . . . . . . . . . . . . . . . . . 8 65 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 67 1. Introduction 69 Multiline 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 140 thе used block cipher; if n = 64, then the field 141 polynomial is f = x^64 + x^4 + x^3 + x + 1; if n = 128, then 142 the field polynomial is 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 | - sum1 = 0, sum2 = 0, | 209 | - For i = 1, 2, ..., h do | 210 | H_i = E_K(Z_i), | 211 | sum1 = sum1 (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 | sum2 = sum2 (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(sum1 (xor) sum2 (xor) | 219 | H_{h+q+1} (x) (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 MGM mode our task was to create a fast, 304 parallelizable, inverse free, online and secure block cipher mode. 305 MGM is based on counters for reasons of performance. The first 306 counter is used for message encryption, the second counter is used 307 for authentication. 309 For providing parallelizable authentication we use multilinear 310 function. By encrypting 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 The text will be added in the future versions of the draft. 345 Appendix B. Contributors 347 o Evgeny Alekseev 348 CryptoPro 349 alekseev@cryptopro.ru 351 o Ekaterina Smyshlyaeva 352 CryptoPro 353 ess@cryptopro.ru 355 o Lilia Ahmetzyanova 356 CryptoPro 357 lah@cryptopro.ru 359 o Grigory Marshalko 360 TC 26 361 marshalko_gb@tc26.ru 363 o Vladimir Rudskoy 364 TC 26 365 rudskoy_vi@tc26.ru 367 Authors' Addresses 369 Stanislav Smyshlyaev (editor) 370 CryptoPro 372 Phone: +7 (495) 995-48-20 373 Email: svs@cryptopro.ru 375 Vladislav Nozdrunov 376 TC 26 378 Email: nozdrunov_vi@tc26.ru 380 Vasily Shishkin 381 TC 26 383 Email: shishkin_va@tc26.ru