idnits 2.17.1 draft-smyshlyaev-re-keying-00.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 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 21, 2016) is 2744 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 1 error (**), 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 E. Alekseev 4 Intended status: Informational I. Oshkin 5 Expires: April 24, 2017 L. Ahmetzyanova 6 E. Smyshlyaeva 7 CryptoPro 8 October 21, 2016 10 The ACPKM internal re-keying mechanism for block cipher modes of 11 operation 12 draft-smyshlyaev-re-keying-00 14 Abstract 16 This specification presents an approach to increase the security of 17 block cipher operation modes based on re-keying (with no additional 18 keys needed) during each separate message processing. It provides an 19 internal re-keying mechanism called ACPKM. This mechanism doesn't 20 require additional secret parameters or complicated transforms - for 21 key update only the base encryption function is used. 23 Status of This Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on April 24, 2017. 40 Copyright Notice 42 Copyright (c) 2016 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 58 2. Conventions Used in This Document . . . . . . . . . . . . . . 3 59 3. Basic Terms and Definitions . . . . . . . . . . . . . . . . . 3 60 4. CTR and GCM Block Cipher Modes . . . . . . . . . . . . . . . 4 61 4.1. CTR Block Cipher Mode . . . . . . . . . . . . . . . . . . 5 62 4.2. GCM Block Cipher Mode . . . . . . . . . . . . . . . . . . 6 63 5. ACPKM re-keying mechanisms . . . . . . . . . . . . . . . . . 9 64 5.1. ACPKM internal re-keying mechanism for CTR encryption 65 mode . . . . . . . . . . . . . . . . . . . . . . . . . . 10 66 5.2. ACPKM internal re-keying mechanism for GCM encryption 67 mode . . . . . . . . . . . . . . . . . . . . . . . . . . 10 68 6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 11 69 7. Security Considerations . . . . . . . . . . . . . . . . . . . 11 70 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 71 8.1. Normative References . . . . . . . . . . . . . . . . . . 11 72 8.2. Informative References . . . . . . . . . . . . . . . . . 11 73 Appendix A. Test examples . . . . . . . . . . . . . . . . . . . 12 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 76 1. Introduction 78 An important problem related to secure functioning of any 79 cryptographic system is the control of key lifetimes. Regarding 80 symmetric keys, the main concern is constraining the key exposure. 81 It could be done by limiting the maximal amount of data processed 82 with one key. The restrictions can come either from combinatorial 83 properties of the used cipher modes of operation (for example, 84 birthday attack [BDJR]) or from particular cryptographic attacks on 85 the used block cipher (for example, linear cryptanalysis [Matsui]). 86 Moreover, most strict restrictions here follow from the need to 87 resist side-channel attacks. The adversary's opportunity to obtain 88 an essential amount of data processed with a single key leads not 89 only to theoretic but also to real vulnerabilities (see [BL]). 90 Therefore, when the total size of a plaintext processed with the same 91 key reaches threshold values, this key cannot be used anymore and 92 certain procedures on encryption keys are needed. It leads to 93 several operating limitations, e.g. the impossibility to process long 94 messages and processing overhead caused by derivation of additional 95 keys. 97 This specification presents a mechanism to increase the key lifetime, 98 which is called ACPKM. This solution ("key meshing") transforms the 99 key value each time when the given amount of data, precisely the 100 amount of plaintext section (not the total amount of separate 101 messages), is processed and proceeds with a new transformed key value 102 for a new plaintext section. Such a transformation does not require 103 any additional secret values. It is integrated into the base mode of 104 operation and can be considered as it's extension, therefore it is 105 called "internal re-keying" in this document. 107 This approach seems to be mostly useful in the case when the total 108 amount of data for an established key is not known beforehand: the 109 performance on useless operations won't be lost if the data size is 110 rather small, and the security won't be lacked when it occurs to be 111 large. The transformed keys are computed only when they are needed. 113 2. Conventions Used in This Document 115 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 116 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 117 document are to be interpreted as described in [RFC2119]. 119 3. Basic Terms and Definitions 121 This document uses the following terms and definitions for the sets 122 and operations on the elements of these sets: 124 (xor) exclusive-or of two binary vectors of the same length. 126 V* the set of all strings of a finite length (hereinafter 127 referred to as strings), including the empty string; 129 V_s the set of all binary strings of length s, where s is a non- 130 negative integer; substrings and string components are 131 enumerated from right to left starting from one; 133 |X| the bit length of the bit string X; 135 A|B concatenation of strings A and B both belonging to V*, i.e., 136 a string in V_{|A|+|B|}, where the left substring in V_|A| is 137 equal to A, and the right substring in V_|B| is equal to B; 139 Z_{2^n} ring of residues modulo 2^n; 141 Int_s: V_s -> Z_{2^s} the transformation that maps a string a = 142 (a_s, ...,a_1), a in V_s, into the integer Int_s(a) = 2^s*a_s 143 + ... + 2*a_2 + a_1; 145 Vec_s: Z_{2^s} -> V_s the transformation inverse to the mapping 146 Int_s; 148 MSB_i: V_s -> V_i the transformation that maps the string a = (a_s, 149 ...,a_1) in V_s, into the string MSB_i(a) = (a_s, 150 ...,a_{s-i+1}) in V_i; 152 LSB_i: V_s -> V_i the transformation that maps the string a = (a_s, 153 ...,a_1) in V_s, into the string LSB_i(a) = (a_i, ...,a_1) in 154 V_i; 156 Inc_c: V_s -> V_s the transformation that maps the string a = (a_s, 157 ...,a_1) in V_s, into the string Inc_c(a) = MSB_{|a|-c}(a) | 158 Vec_c(Int_c(LSB_c(a)) + 1(mod 2^c)) in V_s; 160 0^s denotes the string a in V_s that consists of s '0' bits; 162 E_K: V_n -> V_n the block cipher permutation under the key K in V_k; 164 k the key K size (in bits); 166 n the block size of the block cipher (in bits); 168 b the total number of data blocks in the plaintext; 170 N the section size (the number of bits in a data section); 172 l the number of data sections in the plaintext; 174 m the message M size (in bits); 176 phi_i: V_s -> V_s the transformation that maps a string a = (a_s, 177 ...,a_1) into the string phi_i(a) = a' = (a'_s, ...,a'_1), 1 178 <= i <= s, such that a'_i = 1 and a'_j = a_j for all j in 179 {1,...,s}/{i}; 181 ceil(x) the least integer that is not less than x. 183 4. CTR and GCM Block Cipher Modes 185 This section describes the families of block cipher modes of 186 operations that are extended by the ACPKM re-keying mechanisms as 187 described in Section 5. 189 A plaintext message P and a ciphertext C are divided into b = ceil(m/ 190 n) parts (denoted as P = P_1 | P_2 |...| P_b and C = C_1 | C_2 |...| 191 C_b, where P_i and C_i are in V_n, for i = 1, 2, ..., b-1, and P_b, 192 C_b are in V_r, where r <= n). 194 4.1. CTR Block Cipher Mode 196 The Counter (CTR) mode is a block cipher mode of operation that 197 applies the block cipher transformation E_K to a sequence of input 198 blocks, called counters, to produce a sequence of output blocks that 199 are XORed with a plaintext to produce a ciphertext, and vice versa. 200 It is defined similar to the one specified in [NIST-CTR]. 202 The ACPKM-CTR re-keying mechanisms described in Section 5.1 can be 203 used with the following block cipher and CTR mode parameters: 205 o 64 <= n <= 512; 207 o 128 <= k <= 512; 209 o the number of bits c in a specific part of the block to be 210 incremented is such that 32 <= c <= 3/4 n. 212 In the current document, the counters for a given message are denoted 213 as CTR_1, CTR_2, ..., CTR_b. 215 The CTR encryption mode is defined as follows: 217 Input: 218 Initial counter nonce ICN in V_{n-c}, 219 plaintext P, |P| < n*2^c. 221 Output: 222 Ciphertext C. 223 ___________________________________________________________________ 224 CTR Encryption: 225 1. CTR_1 = ICN | 0^c. 226 2. For j = 1, 2, ..., b-1 do 227 CTR_{j+1} = Inc_c(CTR_j). 228 3. For j = 1, 2, ..., b do 229 G_j = E_K(CTR_j). 230 4. C = P (xor) MSB_{|P|}(G_1 |...|G_b). 231 5. Return C. 233 The CTR decryption mode is defined as follows: 235 Input: 236 Initial counter nonce ICN in V_{n-c}, 237 ciphertext C, |C| < n*2^c. 239 Output: 240 Plaintext P. 241 ___________________________________________________________________ 242 CTR Decryption: 243 1. CTR_1 = ICN | 0^c. 244 2. For j = 1, 2,..., b-1 do 245 CTR_{j+1} = Inc_c(CTR_j). 246 3. For j = 1, 2, ..., b do 247 G_j = E_K(CTR_j) 248 4. P = C (xor) MSB_{|C|}(G_1 |...|G_b). 249 5. Return P. 251 The initial counter nonce ICN value for each message that is 252 encrypted under the given key must be chosen in a unique manner. 254 4.2. GCM Block Cipher Mode 256 TODO: This section describes the family of block cipher modes of 257 operation with both encryption and authentication. It is defined 258 similar to the one specified in [NIST-GCM]. 260 The ACPKM-GCM re-keying mechanisms described in Section 5.2 can be 261 used with the following GCM block cipher mode parameters: 263 o 128 <= n <= 512; 265 o 128 <= k <= 512; 267 o the number of bits c in a specific part of the block to be 268 incremented is such that 32 <= c <= 3/4 n. 270 4.2.1. GCM Subprocedures 272 This section presents three mathematical algorithms that appear in 273 the specification of the authenticated encryption and authenticated 274 decryption functions of the GCM cipher mode described in 275 Section 4.2.2 below. 277 4.2.1.1. Multiplication Operation on Blocks 279 The * operation on (pairs of) the 2^n possible blocks corresponds to 280 the multiplication operation for the binary Galois (finite) field of 281 2^n elements and is defined by a particular GCM mode. 283 4.2.1.2. GHASH Function 285 Algorithm 2: GHASH_H(X) 286 ======================= 287 Input: 288 Bit string X = X_1 |...| X_m, where X_i in V_n for i in 1,...,m. 289 Output: 290 Block GHASHH (X) in V_n 291 ___________________________________________________________________ 292 1. Y_0 = 0^n. 293 2. For i = 1,..., m do 294 Y_i = (Y_{i-1} (xor) X_i)*H. 295 3. Return Y_m. 297 4.2.1.3. GCTR Function 299 Algorithm 3: GCTR_K(ICB, X) 300 =========================== 301 Input: 302 Initial counter block ICB; 303 X = X_1 |...| X_t, X_i in V_n for i = 1,...,n-1 and X_n in V_r, 304 where r <= n. 305 Output: 306 Y in V_{|X|}. 307 ___________________________________________________________________ 308 1. If X in V_0 then return Y, where Y in V_0. 309 2. t = ceil(|X|/n). 310 3. GCTR_1 = ICB. 311 4. For i = 2,...,t do 312 GCTR_i = Inc_c(GCTR_{i-1}). 313 5. For i = 1,...,t do 314 G_i = E_K(GCTR_i). 315 6. Y = X (xor) MSB_{|X|}(G_1 |...| G_t). 316 7. Return Y. 318 4.2.2. GCM Mode Description 320 The GCM encryption mode is defined as follows: 322 Input: 323 Initialization vector IV in V_{n-c}, 324 plaintext P, |P| < n*(2^c - 2). 325 additional authenticated data A. 326 Output: 327 Ciphertext C, 328 authentication tag T. 329 ___________________________________________________________________ 330 GCM Encryption: 331 1. H = E_K(0^n). 332 2. if c = 32, then J_0 = IV | 0^31 | 1; 333 if c!= 32, then s = n*ceil(|IV|/n)-|IV|, 334 J_0 = GHASH_H(IV | 0^{s+n-64} | Vec_64(|IV|)). 335 3. C = GCTR_K(Inc_32(J_0),P). 336 4. u = n*ceil(|C|/n)-|C|, 337 v = n*ceil(|A|/n)-|A|. 338 5. S = GHASH_H(A | 0^v | C | 0^u | 0^{n-128} | 339 |Vec_64(|A|) | Vec_64(|C|)). 340 6. T = MSB_t(E_K(J_0) (xor) S). 341 7. Return C | T. 343 The GCM decryption mode is defined as follows: 345 Input: 346 Initialization vector IV in V_{n-c}, 347 ciphertext C, |C| < n*(2^c - 2), 348 authentication tag T, 349 additional authenticated data A. 350 Output: 351 Plaintext P or FAIL. 352 ___________________________________________________________________ 353 GCM decryption: 354 1. H = E_K(0^n). 355 2. if c = 32, then J_0 = IV | 0^31 | 1; 356 if c!= 32, then s = n*ceil(|IV|/n)-|IV|, 357 J_0 = GHASH_H(IV | 0^{s+n-64} | Vec_64(|IV|)). 358 3. P = GCTR_K(Inc_32(J_0),C). 359 4. u = n*ceil(|C|/n)-|C|, 360 v = n*ceil(|A|/n)-|A|. 361 5. S = GHASH_H(A | 0^v | C | 0^u | 0^{n-128}| 362 |Vec_64(|A|) | Vec_64(|C|)). 363 6. T' = MSB_t(E_K(J_0) (xor) S). 364 7. IF T=T' then return P; else return FAIL. 366 The initial vector IV value for each message that is encrypted under 367 the given key must be chosen in a unique manner. 369 N o t e : The encryption part in the GCM-ACPKM mode is the encryption 370 in the CTR-ACPKM mode with several differences: in the CTR mode the 371 counter for the plaintext encryption starts with the first CTR_1 372 value and in the GCM mode the counter starts with the second GCTR_2 373 value. 375 5. ACPKM re-keying mechanisms 377 This section defines periodical key transformations for long message 378 processing that are considered as extensions of the basic CTR and GCM 379 encryption modes and are called ACPKM-CTR and ACPKM-GCM re-keying 380 mechanisms. 382 An additional parameter that defines the functioning of CTR and GCM 383 block cipher modes with the ACPKM key transformation algorithm is the 384 section size N. The value of N is fixed within a specific protocol 385 based on the requirements of the system capacity and key lifetime 386 (some recommendations on choosing N will be provided in Section 7). 387 The section size N MUST be divisible by the block size n. 389 The main idea behind internal re-keying is presented in Fig.1: 391 Lifetime of a key = L, 392 section size = const = N, 393 maximum message size = m_max. 394 ____________________________________________________________________ 395 ACPKM ACPKM ACPKM 396 K_1 = K ----> K_2 -----...-> K_{l_max-1} ----> K_{l_max} 397 Message(1) |==========|==========|======|=== | : | 398 | | | ... | | : | 399 Message(2) |==========|==========|======|==========|=======: | 400 . . . | | | ... | | : | 401 | | | | | : | 402 Message(q) |==========|==========|======|==========|===== : | 403 | | section | ... | | : | 404 <----------> : 405 N bit m_max 406 ____________________________________________________________________ 407 l_max = ceil(m_max/N), 408 q*N <= L. 409 Figure 1: Key meshing approach 411 For the {i+1}-th section the K_{i+1} value is calculated as follows: 413 K_{i+1} = ACPKM-CTR(K_i) = MSB_k(E_{K_i}(W_1)|...|E_{K_i}(W_J)), 415 where J = ceil(k/n), W_t = phi_c(D_t) for any t in {1,...,J} and D_1, 416 D_2,...,D_J are in V_n and are calculated as follows: 418 D_1 | D_2 |...| D_J = MSB_{J*n}(D), 420 where D is the following constant in V_1024: 422 D = ( F3 | 74 | E9 | 23 | FE | AA | D6 | DD 423 | 98 | B4 | B6 | 3D | 57 | 8B | 35 | AC 424 | A9 | 0F | D7 | 31 | E4 | 1D | 64 | 5E 425 | 40 | 8C | 87 | 87 | 28 | CC | 76 | 90 426 | 37 | 76 | 49 | 9F | 7D | F3 | 3B | 06 427 | 92 | 21 | 7B | 06 | 37 | BA | 9F | B4 428 | F2 | 71 | 90 | 3F | 3C | F6 | FD | 1D 429 | 70 | BB | BB | 88 | E7 | F4 | 1B | 76 430 | 7E | 44 | F9 | 0E | 46 | 91 | 5B | 57 431 | 00 | BC | 13 | 45 | BE | 0D | BD | C7 432 | 61 | 38 | 19 | 3C | 41 | 30 | 86 | 82 433 | 1A | A0 | 45 | 79 | 23 | 4C | 4C | F3 434 | 64 | F2 | 6A | CC | EA | 48 | CB | B4 435 | 0C | B9 | A9 | 28 | C3 | B9 | 65 | CD 436 | 9A | CA | 60 | FB | 9C | A4 | 62 | C7 437 | 22 | C0 | 6C | E2 | 4A | C7 | FB | 5B). 439 N o t e : The constant D is such that phi_c(D_1),..., phi_c(D_J) are 440 pairwise different for any allowed n, k, c values. 442 5.1. ACPKM internal re-keying mechanism for CTR encryption mode 444 This section defines a ACPKM-CTR internal re-keying mechanism for the 445 CTR encryption mode that was described in Section 4.1. 447 During the processing of the input message M with the length m using 448 ACPKM-CTR internal re-keying algorithm and the key K the message is 449 divided into l = ceil(m*N) parts (denoted as M = M_1 | M_2 |...| M_l, 450 where M_i is in V_N for i = 1, 2,..., l-1 and M_l is in V_r, r <= N). 451 The first section is processed with the initial key K_1 = K. To 452 process the (i+1)-th section the K_{i+1} key value is calculated 453 using ACPKM-CTR transformation of the key K_i. The counter value 454 (CTR_{i+1}) is not changed during this process. 456 The message size m MUST NOT exceed n*2^{c-1} bits. 458 5.2. ACPKM internal re-keying mechanism for GCM encryption mode 460 This section defines a ACPKM-GCM internal re-keying mechanism for the 461 GCM encryption mode that was described in Section 4.2. 463 During the processing of the input message M with the length m using 464 ACPKM-GCM internal re-keying algorithm and the key K the message is 465 divided into l = ceil(m/N) parts (denoted as M = M_1 | M_2 |...| M_l, 466 where M_i is in V_N for i = 1, 2,..., l-1 and M_l is in V_r, r <= N). 467 The first section is processed with the initial key K_1 = K. To 468 process the (i+1)-th section the K_{i+1} key value is calculated 469 using ACPKM-GCM transformation of the key K_i. 471 The message size m MUST NOT exceed n*(2^{c-1}-2) bits. 473 The key for computing values E_K(J_0) and H is not updated and is 474 equal to the initial key. 476 6. Acknowledgments 478 TODO 480 7. Security Considerations 482 The ACPKM re-keying mechanisms provide the CTR and GCM encryption 483 modes extensions that have the following property: a compromise of a 484 key of some section does not lead to a compromise of previous keys 485 but leads to a compromise of next keys. 487 The ACPKM mechanism allows to increase the CTR and GCM encryption 488 modes security in proportion to the frequency of key changing, which 489 is inversely related to the section size N. Thus, the key lifetime 490 can be noticeably increased: an amount of material that is processed 491 with the key K increases quadratically, divided by N. 493 Since the performance of encryption can slightly decrease for rather 494 small values of N, the parameter of N SHOULD be selected for a 495 particular protocol as maximum possible to provide necessary key 496 lifetime for the adversary models that are considered. 498 8. References 500 8.1. Normative References 502 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 503 Requirement Levels", BCP 14, RFC 2119, 504 DOI 10.17487/RFC2119, March 1997, 505 . 507 8.2. Informative References 509 [BDJR] Bellare M., Desai A., Jokipii E., Rogaway P., "A concrete 510 security treatment of symmetric encryption", In 511 Proceedings of 38th Annual Symposium on Foundations of 512 Computer Science (FOCS '97), pages 394-403. 97, 1997. 514 [BL] Bhargavan K., Leurent G., "On the Practical (In-)Security 515 of 64-bit Block Ciphers: Collision Attacks on HTTP over 516 TLS and OpenVPN", Cryptology ePrint Archive Report 798, 517 2016. 519 [Matsui] Matsui M., "Linear Cryptanalysis Method for DES Cipher", 520 Advanced in Cryptology- EUROCRYPT'93. Lect. Notes in Comp. 521 Sci., Springer. V.765.P. 386-397, 1994. 523 [NIST-CTR] 524 Dworkin, M., "Recommendation for Block Cipher Modes of 525 Operation: Methods and Techniques", NIST Special 526 Publication 800-38A, December 2001. 528 [NIST-GCM] 529 McGrew, D. and J. Viega, "The Galois/Counter Mode of 530 Operation (GCM)", Submission to NIST 531 http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/ 532 gcm/gcm-spec.pdf, January 2004. 534 Appendix A. Test examples 536 TODO 538 Authors' Addresses 540 Stanislav Smyshlyaev (editor) 541 CryptoPro 542 18, Suschevsky val 543 Moscow 127018 544 Russian Federation 546 Phone: +7 (495) 995-48-20 547 Email: svs@cryptopro.ru 549 Evgeny Alekseev 550 CryptoPro 551 18, Suschevsky val 552 Moscow 127018 553 Russian Federation 555 Phone: +7 (495) 995-48-20 556 Email: alekseev@cryptopro.ru 557 Igor Oshkin 558 CryptoPro 559 18, Suschevsky val 560 Moscow 127018 561 Russian Federation 563 Phone: +7 (495) 995-48-20 564 Email: oshkin@cryptopro.ru 566 Lilia Ahmetzyanova 567 CryptoPro 568 18, Suschevsky val 569 Moscow 127018 570 Russian Federation 572 Phone: +7 (495) 995-48-20 573 Email: lah@cryptopro.ru 575 Ekaterina Smyshlyaeva 576 CryptoPro 577 18, Suschevsky val 578 Moscow 127018 579 Russian Federation 581 Phone: +7 (495) 995-48-20 582 Email: ess@cryptopro.ru