idnits 2.17.1 draft-irtf-cfrg-re-keying-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 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.) ** There are 18 instances of too long lines in the document, the longest one being 10 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 9, 2017) is 2388 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 1195 == Missing Reference: '2t' is mentioned on line 1168, but not defined ** Obsolete normative reference: RFC 6347 (ref. 'DTLS') (Obsoleted by RFC 9147) ** Obsolete normative reference: RFC 5246 (ref. 'TLS') (Obsoleted by RFC 8446) Summary: 4 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG S. Smyshlyaev, Ed. 3 Internet-Draft CryptoPro 4 Intended status: Informational October 9, 2017 5 Expires: April 12, 2018 7 Re-keying Mechanisms for Symmetric Keys 8 draft-irtf-cfrg-re-keying-08 10 Abstract 12 A certain maximum amount of data can be safely encrypted when 13 encryption is performed under a single key. This amount is called 14 "key lifetime". This specification describes a variety of methods to 15 increase the lifetime of symmetric keys. It provides external and 16 internal re-keying mechanisms based on hash functions and on block 17 ciphers, that can be used with modes of operations such as CTR, GCM, 18 CBC, CFB and OMAC. 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at https://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on April 12, 2018. 37 Copyright Notice 39 Copyright (c) 2017 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (https://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 55 2. Conventions Used in This Document . . . . . . . . . . . . . . 5 56 3. Basic Terms and Definitions . . . . . . . . . . . . . . . . . 5 57 4. Choosing Constructions and Security Parameters . . . . . . . 6 58 5. External Re-keying Mechanisms . . . . . . . . . . . . . . . . 9 59 5.1. Methods of Key Lifetime Control . . . . . . . . . . . . . 12 60 5.2. Parallel Constructions . . . . . . . . . . . . . . . . . 12 61 5.2.1. Parallel Construction Based on a KDF on a Block 62 Cipher . . . . . . . . . . . . . . . . . . . . . . . 13 63 5.2.2. Parallel Construction Based on HKDF . . . . . . . . . 13 64 5.2.3. Tree-based Construction . . . . . . . . . . . . . . . 14 65 5.3. Serial Constructions . . . . . . . . . . . . . . . . . . 15 66 5.3.1. Serial Construction Based on a KDF on a Block Cipher 16 67 5.3.2. Serial Construction Based on HKDF . . . . . . . . . . 17 68 6. Internal Re-keying Mechanisms . . . . . . . . . . . . . . . . 17 69 6.1. Methods of Key Lifetime Control . . . . . . . . . . . . . 20 70 6.2. Constructions that Do Not Require Master Key . . . . . . 20 71 6.2.1. ACPKM Re-keying Mechanisms . . . . . . . . . . . . . 20 72 6.2.2. CTR-ACPKM Encryption Mode . . . . . . . . . . . . . . 22 73 6.2.3. GCM-ACPKM Authenticated Encryption Mode . . . . . . . 23 74 6.3. Constructions that Require Master Key . . . . . . . . . . 26 75 6.3.1. ACPKM-Master Key Derivation from the Master Key . . . 26 76 6.3.2. CTR-ACPKM-Master Encryption Mode . . . . . . . . . . 28 77 6.3.3. GCM-ACPKM-Master Authenticated Encryption Mode . . . 30 78 6.3.4. CBC-ACPKM-Master Encryption Mode . . . . . . . . . . 32 79 6.3.5. CFB-ACPKM-Master Encryption Mode . . . . . . . . . . 35 80 6.3.6. OMAC-ACPKM-Master Authentication Mode . . . . . . . . 37 81 7. Joint Usage of External and Internal Re-keying . . . . . . . 38 82 8. Security Considerations . . . . . . . . . . . . . . . . . . . 38 83 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 39 84 9.1. Normative References . . . . . . . . . . . . . . . . . . 39 85 9.2. Informative References . . . . . . . . . . . . . . . . . 40 86 Appendix A. Test examples . . . . . . . . . . . . . . . . . . . 41 87 Appendix B. Contributors . . . . . . . . . . . . . . . . . . . . 49 88 Appendix C. Acknowledgments . . . . . . . . . . . . . . . . . . 49 89 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 49 91 1. Introduction 93 A certain maximum amount of data can be safely encrypted when 94 encryption is performed under a single key. This amount is called 95 "key lifetime" and can be calculated from the following 96 considerations: 98 1. Methods based on the combinatorial properties of the used block 99 cipher mode of operation 101 These methods do not depend on the underlying block cipher. 102 Common modes restrictions derived from such methods are of 103 order 2^{n/2}. [Sweet32] is an example of attack that is 104 based on such methods. 106 2. Methods based on side-channel analysis issues 108 In most cases these methods do not depend on the used 109 encryption modes and weakly depend on the used block cipher 110 features. Limitations resulting from these considerations are 111 usually the most restrictive ones. [TEMPEST] is an example of 112 attack that is based on such methods. 114 3. Methods based on the properties of the used block cipher 116 The most common methods of this type are linear and 117 differential cryptanalysis [LDC]. In most cases these methods 118 do not depend on the used modes of operation. In case of 119 secure block ciphers, bounds resulting from such methods are 120 roughly the same as the natural bounds of 2^n, and are 121 dominated by the other bounds above. Therefore, they can be 122 excluded from the considerations here. 124 As a result, it is important to replace a key as soon as the total 125 size of the processed plaintext under that key reaches the lifetime 126 limitation. A specific value of the key lifetime should be 127 determined in accordance with some safety margin for protocol 128 security and the methods outlined above. 130 Suppose L is a key lifetime limitation in some protocol P. For 131 simplicity, assume that all messages have the same length m. Hence, 132 the number of messages q that can be processed with a single key K 133 should be such that m * q <= L. This can be depicted graphically as 134 a rectangle with sides m and q which is enclosed by area L (see 135 Figure 1). 137 +------------------------+ 138 | L | 139 | +--------m---------+ | 140 | |==================| | 141 | |==================| | 142 | q==================| | m * q <= L 143 | |==================| | 144 | |==================| | 145 | +------------------+ | 146 +------------------------+ 148 Figure 1: Graphic display of the key lifetime limitation 150 In practice, such amount of data that corresponds to limitation L may 151 not be enough. The simplest and obvious way in this situation is a 152 regular renegotiation of an initial key after processing this 153 threshold amount of data L. However, this reduces the total 154 performance, since it usually entails termination of application data 155 transmission, additional service messages, the use of random number 156 generator and many other additional calculations, including resource- 157 intensive public key cryptography. 159 This specification presents two approaches to extend the lifetime of 160 a key while avoiding renegotiation: external and internal re-keying. 162 External re-keying is performed by a protocol, and it is independent 163 of the underlying block cipher and the mode of operation. External 164 re-keying can use parallel and serial constructions. In the parallel 165 case, data processing keys K^1, K^2, ... are generated directly from 166 the initial key K independently of each other. In the serial case, 167 every data processing key depends on the state that is updated after 168 the generation of each new data processing key. 170 Internal re-keying is built into the mode, and it depends heavily on 171 the properties of the mode of operation and the block size. 173 The re-keying approaches extend the key lifetime for a single initial 174 key by providing the possibility to limit the leakages (via side 175 channels) and by improving combinatorial properties of the used block 176 cipher mode of operation. 178 In practical applications, re-keying can be useful for protocols that 179 need to operate in hostile environments or under restricted resource 180 conditions (e.g., that require lightweight cryptography, where 181 ciphers have a small block size, that imposes strict combinatorial 182 limitations). Moreover, mechanisms that use external and internal 183 re-keying may provide some properties of forward security and 184 potentially some protection against future attacks (by limiting the 185 number of plaintext-ciphertext pairs that an adversary can collect). 187 2. Conventions Used in This Document 189 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 190 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 191 document are to be interpreted as described in [RFC2119]. 193 3. Basic Terms and Definitions 195 This document uses the following terms and definitions for the sets 196 and operations on the elements of these sets: 198 V* the set of all bit strings of a finite length (hereinafter 199 referred to as strings), including the empty string; 200 substrings and string components are enumerated from right to 201 left starting from one; 203 V_s the set of all bit strings of length s, where s is a non- 204 negative integer; 206 |X| the bit length of the bit string X; 208 A | B concatenation of strings A and B both belonging to V*, i.e., 209 a string in V_{|A|+|B|}, where the left substring in V_|A| is 210 equal to A, and the right substring in V_|B| is equal to B; 212 (xor) exclusive-or of two bit strings of the same length; 214 Z_{2^n} ring of residues modulo 2^n; 216 Int_s: V_s -> Z_{2^s} the transformation that maps a string a = 217 (a_s, ... , a_1), a in V_s, into the integer Int_s(a) = 218 2^{s-1} * a_s + ... + 2 * a_2 + a_1; 220 Vec_s: Z_{2^s} -> V_s the transformation inverse to the mapping 221 Int_s; 223 MSB_i: V_s -> V_i the transformation that maps the string a = (a_s, 224 ... , a_1) in V_s, into the string MSB_i(a) = (a_s, ... , 225 a_{s-i+1}) in V_i; 227 LSB_i: V_s -> V_i the transformation that maps the string a = (a_s, 228 ... , a_1) in V_s, into the string LSB_i(a) = (a_i, ... , 229 a_1) in V_i; 231 Inc_c: V_s -> V_s the transformation that maps the string a = (a_s, 232 ... , a_1) in V_s, into the string Inc_c(a) = MSB_{|a|- 233 c}(a) | Vec_c(Int_c(LSB_c(a)) + 1(mod 2^c)) in V_s; 235 a^s denotes the string in V_s that consists of s 'a' bits; 237 E_{K}: V_n -> V_n the block cipher permutation under the key K in 238 V_k; 240 ceil(x) the smallest integer that is greater than or equal to x; 242 floor(x) the biggest integer that is less than or equal to x; 244 k the bit-length of the K; k is assumed to be divisible by 8; 246 n the block size of the block cipher (in bits); n is assumed to 247 be divisible by 8; 249 b the number of data blocks in the plaintext P (b = 250 ceil(|P|/n)); 252 N the section size (the number of bits that are processed with 253 one section key before this key is transformed); 255 A plaintext message P and the corresponding ciphertext C are divided 256 into b = ceil(|P|/n) blocks, denoted P = P_1 | P_2 | ... | P_b and C 257 = C_1 | C_2 | ... | C_b, respectively. The first b-1 blocks P_i and 258 C_i are in V_n, for i = 1, 2, ... , b-1. The b-th block P_b, C_b may 259 be an incomplete block, i.e., in V_r, where r <= n if not otherwise 260 specified. 262 4. Choosing Constructions and Security Parameters 264 External re-keying is an approach assuming that a key is transformed 265 after encrypting a limited number of entire messages. External re- 266 keying method is chosen at the protocol level, regardless of the 267 underlying block cipher or the encryption mode. External re-keying 268 is recommended for protocols that process relatively short messages 269 or for protocols that have a way to divide a long message into 270 manageable pieces. Through external re-keying the number of messages 271 that can be securely processed with a single initial key K is 272 substantially increased without loss in message length. 274 External re-keying has the following advantages: 276 1. it increases the lifetime of an initial key by increasing the 277 number of messages processed with this key; 279 2. it has negligible affect on the performance, when the number of 280 messages processed under one initial key is sufficiently large; 282 3. it provides forward and backward security of data processing 283 keys. 285 However, the use of external re-keying has the following 286 disadvantage: in case of restrictive key lifetime limitations the 287 message sizes can become inconvenient due to impossibility of 288 processing sufficiently large messages, so it could be necessary to 289 perform additional fragmentation at the protocol level. E.g. if the 290 key lifetime L is 1 GB and the message length m = 3 GB, then this 291 message cannot be processed as a whole and it should be divided into 292 three fragments that will be processed separately. 294 Internal re-keying is an approach assuming that a key is transformed 295 during each separate message processing. Such procedures are 296 integrated into the base modes of operations, so every internal re- 297 keying mechanism is defined for the particular operation mode and the 298 block size of the used cipher. Internal re-keying is recommended for 299 protocols that process long messages: the size of each single message 300 can be substantially increased without loss in number of messages 301 that can be securely processed with a single initial key. 303 Internal re-keying has the following advantages: 305 1. it increases the lifetime of an initial key by increasing the 306 size of the messages processed with one initial key; 308 2. it has minimal impact on performance; 310 3. internal re-keying mechanisms without a master key does not 311 affect short messages transformation at all; 313 4. it is transparent (works like any mode of operation): does not 314 require changes of IV's and restarting MACing. 316 However, the use of internal re-keying has the following 317 disadvantages: 319 1. a specific method must not be chosen independently of a mode of 320 operation; 322 2. internal re-keying mechanisms without a master key do not provide 323 backward security of data processing keys. 325 Any block cipher modes of operations with internal re-keying can be 326 jointly used with any external re-keying mechanisms. Such joint 327 usage increases both the number of messages processed with one 328 initial key and their maximum possible size. 330 If the adversary has access to the data processing interface the use 331 of the same cryptographic primitives both for data processing and re- 332 keying transformation decreases the code size but can lead to some 333 possible vulnerabilities. This vulnerability can be eliminated by 334 using different primitives for data processing and re-keying, 335 however, in this case the security of the whole scheme cannot be 336 reduced to standard notions like PRF or PRP, so security estimations 337 become more difficult and unclear. 339 Summing up the above-mentioned issues briefly: 341 1. If a protocol assumes processing long records (e.g., [CMS]), 342 internal re-keying should be used. If a protocol assumes 343 processing a significant amount of ordered records, which can be 344 considered as a single data stream (e.g., [TLS], [SSH]), internal 345 re-keying may also be used. 347 2. For protocols which allow out-of-order delivery and lost records 348 (e.g., [DTLS], [ESP]) external re-keying should be used. If at 349 the same time records are long enough, internal re-keying should 350 be additionally used during each separate message processing. 352 For external re-keying: 354 1. If it is desirable to separate transformations used for data 355 processing and for key update, hash function based re-keying 356 should be used. 358 2. If parallel data processing is required, then parallel external 359 re-keying should be used. 361 3. In case of restrictive key lifetime limitations external tree- 362 based re-keying should be used. 364 For internal re-keying: 366 1. If the property of forward and backward security is desirable for 367 data processing keys and if additional key material can be easily 368 obtained for the data processing stage, internal re-keying with a 369 master key should be used. 371 5. External Re-keying Mechanisms 373 This section presents an approach to increase the initial key 374 lifetime by using a transformation of a data processing key (frame 375 key) after processing a limited number of entire messages (frame). 376 It provides external parallel and serial re-keying mechanisms (see 377 [AbBell]). These mechanisms use initial key K only for frame key 378 generation and never use it directly for data processing. Such 379 mechanisms operate outside of the base modes of operations and do not 380 change them at all, therefore they are called "external re-keying" 381 mechanisms in this document. 383 External re-keying mechanisms are recommended for usage in protocols 384 that process quite small messages, since the maximum gain in 385 increasing the initial key lifetime is achieved by increasing the 386 number of messages. 388 External re-keying increases the initial key lifetime through the 389 following approach. Suppose there is a protocol P with some mode of 390 operation (base encryption or authentication mode). Let L1 be a key 391 lifetime limitation induced by side-channel analysis methods (side- 392 channel limitation), let L2 be a key lifetime limitation induced by 393 methods based on the combinatorial properties of a used mode of 394 operation (combinatorial limitation) and let q1, q2 be the total 395 numbers of messages of length m, that can be safely processed with an 396 initial key K according to these limitations. 398 Let L = min(L1, L2), q = min (q1, q2), q * m <= L. As L1 limitation 399 is usually much stronger than L2 limitation (L1 < L2), the final key 400 lifetime restriction is equal to the most restrictive limitation L1. 401 Thus, as displayed in Figure 2, without re-keying only q1 (q1 * m <= 402 L1) messages can be safely processed. 404 <--------m-------> 405 +----------------+ ^ ^ 406 |================| | | 407 |================| | | 408 K-->|================| q1| 409 |================| | | 410 |==============L1| | | 411 +----------------+ v | 412 | | | 413 | | | 414 | | q2 415 | | | 416 | | | 417 | | | 418 | | | 419 | | | 420 | | | 421 | | | 422 | | | 423 | L2| | 424 +----------------+ v 426 Figure 2: Basic principles of message processing without external re-keying 428 Suppose that the safety margin for the protocol P is fixed and the 429 external re-keying approach is applied to the initial key K to 430 generate the sequence of frame keys. The frame keys are generated in 431 such a way that the leakage of a previous frame key does not have any 432 impact on the following one, so the side channel limitation L1 goes 433 off. Thus, the resulting key lifetime limitation of the initial key 434 K can be calculated on the basis of a new combinatorial limitation 435 L2'. It is proven (see [AbBell]) that the security of the mode of 436 operation that uses external re-keying leads to an increase when 437 compared to base mode without re-keying (thus, L2 < L2'). Hence, as 438 displayed in Figure 3, the resulting key lifetime limitation in case 439 of using external re-keying can be increased up to L2'. 441 <--------m-------> 442 K +----------------+ 443 | |================| 444 v |================| 445 K^1--> |================| 446 | |================| 447 | |==============L1| 448 | +----------------+ 449 | |================| 450 v |================| 451 K^2--> |================| 452 | |================| 453 | |==============L1| 454 | +----------------+ 455 | |================| 456 v |================| 457 ... | . . . | 458 | | 459 | | 460 | L2| 461 +----------------+ 462 | | 463 ... ... 464 | L2'| 465 +----------------+ 467 Figure 3: Basic principles of message processing with external re-keying 469 Note: the key transformation process is depicted in a simplified 470 form. A specific approach (parallel and serial) is described below. 472 Consider an example. Let the message size in a protocol P be equal 473 to 1 KB. Suppose L1 = 128 MB and L2 = 1 TB. Thus, if an external 474 re-keying mechanism is not used, the initial key K must be 475 renegotiated after processing 128 MB / 1 KB = 131072 messages. 477 If an external re-keying mechanism is used, the key lifetime 478 limitation L1 goes off. Hence the resulting key lifetime limitation 479 L2' can be set to more then 1 TB. Thus if an external re-keying 480 mechanism is used, more then 1 TB / 1 KB = 2^30 messages can be 481 processed before the initial key K is renegotiated. This is 8192 482 times greater than the number of messages that can be processed, when 483 external re-keying mechanism is not used. 485 5.1. Methods of Key Lifetime Control 487 Suppose L is an amount of data that can be safely processed with one 488 section key. For i in {1, 2, ... , t} the frame key K^i (see 489 Figure 4 and Figure 5) should be transformed after processing q_i 490 messages, where q_i can be calculated in accordance with one of the 491 following two approaches: 493 o Explicit approach: 494 q_i is such that |M^{i,1}| + ... + |M^{i,q_i}| <= L, |M^{i,1}| + 495 ... + |M^{i,q_i+1}| > L. 496 This approach allows to use the frame key K^i in almost optimal 497 way but it can be applied only in case when messages cannot be 498 lost or reordered (e.g., TLS records). 500 o Implicit approach: 501 q_i = L / m_max, i = 1, ... , t. 502 The amount of data processed with one frame key K^i is calculated 503 under the assumption that every message has the maximum length 504 m_max. Hence this amount can be considerably less than the key 505 lifetime limitation L. On the other hand, this approach can be 506 applied in case when messages may be lost or reordered (e.g., DTLS 507 records). 509 5.2. Parallel Constructions 511 The main idea behind external re-keying with a parallel construction 512 is presented in Figure 4: 514 Maximum message size = m_max. 515 _____________________________________________________________ 517 m_max 518 <----------------> 519 M^{1,1} |=== | 520 M^{1,2} |=============== | 521 +->K^1--> ... ... 522 | M^{1,q_1} |======== | 523 | 524 | 525 | M^{2,1} |================| 526 | M^{2,2} |===== | 527 K-----|->K^2--> ... ... 528 | M^{2,q_2} |========== | 529 | 530 ... 531 | M^{t,1} |============ | 532 | M^{t,2} |============= | 533 +->K^t--> ... ... 534 M^{t,q_t} |========== | 536 _____________________________________________________________ 538 Figure 4: External parallel re-keying mechanisms 540 The frame key K^i, i = 1, ... , t-1, is updated after processing a 541 certain amount of messages (see Section 5.1). 543 5.2.1. Parallel Construction Based on a KDF on a Block Cipher 545 ExtParallelC re-keying mechanism is based on the key derivation 546 function on a block cipher and is used to generate t frame keys as 547 follows: 549 K^1 | K^2 | ... | K^t = ExtParallelC(K, t * k) = MSB_{t * 550 k}(E_{K}(Vec_n(0)) | 551 E_{K}(Vec_n(1)) | ... | E_{K}(Vec_n(R - 1))), 553 where R = ceil(t * k/n). 555 5.2.2. Parallel Construction Based on HKDF 557 ExtParallelH re-keying mechanism is based on the key derivation 558 function HKDF-Expand, described in [RFC5869], and is used to generate 559 t frame keys as follows: 561 K^1 | K^2 | ... | K^t = ExtParallelH(K, t * k) = HKDF-Expand(K, 562 label, t * k), 564 where label is a string (may be a zero-length string) that is defined 565 by a specific protocol. 567 5.2.3. Tree-based Construction 569 The application of external tree-based mechanism leads to the 570 construction of the key tree with the initial key K (root key) at the 571 0-level and the frame keys K^1, K^2, ... at the last level as 572 described in Figure 6. 574 K_root = K 575 ___________|___________ 576 | ... | 577 V V 578 K{1,1} K{1,W1} 579 ______|______ ______|______ 580 | ... | | ... | 581 V V V V 582 K{2,1} K{2,W2} K{2,(W1-1)*W2+1} K{2,W1*W2} 583 __|__ __|__ __|__ __|__ 584 | ... | | ... | | ... | | ... | 585 V V V V V V V V 586 K{3,1} ... ... ... ... ... ... K{3,W1*W2*W3} 588 ... ... 589 __|__ ... __|__ 590 | ... | | ... | 591 V V V V 592 K{h,1} K{h,Wh} K{h,(W1*...*W{h-1}-1)*Wh+1} K{h,W1*...*Wh} 593 // \\ // \\ 594 K^1 K^{Wh} K^{(W1*...*W{h-1}-1)*Wh+1} K^{W1*...*Wh} 595 _______________________________________________________________________ 597 Figure 6: External Tree-based Mechanism 599 The height of tree h and the number of keys Wj, j in {1, ... , h}, 600 which can be partitioned from "parent" key, are defined in accordance 601 with a specific protocol and key lifetime limitations for a used 602 derivation functions. 604 Each j-level key K{j,w}, where j in {1, ... , h}, w in {1, ... , W1 * 605 ... * Wj}, is derived from the (j-1)-level "parent" key K{j-1,ceil(w/ 606 Wi)} (and other appropriate input data) using j-th level derivation 607 function that can be based on the block cipher function or on the 608 hash function and that is defined in accordance with a specific 609 protocol. 611 The i-th frame K^i, i in {1, 2, ... , W1*...*Wh}, can be calculated 612 as follows: 614 K^i = ExtKeyTree(K, i) = KDF_h(KDF_{h-1}(... KDF_1(K, ceil(i / (W2 615 * ... * Wh)) ... , ceil(i / Wh)), i), 617 where KDF_j is a j-th level derivation function that takes two 618 arguments (the parent key value and the integer in range from 1 to W1 619 * ... * Wj) and outputs the j-th level key value. 621 The frame key K^i is updated after processing a certain amount of 622 messages (see Section 5.1). 624 In order to create an effective implementation, during frame key K^i 625 generation the derivation functions KDF_j, j in {1, ... , h-1}, 626 should be used only in case when ceil(i / (W{j+1} * ... * Wh)) != 627 ceil((i - 1) / (W{j+1} * ... * Wh)); otherwise it is necessary to use 628 previously generated value. This approach also makes it possible to 629 take countermeasures against side channels attacks. 631 Consider an example. Suppose h = 3, W1 = W2 = W3 = W and KDF_1, 632 KDF_2, KDF_3 are key derivation functions based on 633 KDF_GOSTR3411_2012_256 (hereafter simply KDF) function described in 634 [RFC7836]. The resulting ExtKeyTree function can be defined as 635 follows: 637 ExtKeyTree(K, i) = KDF(KDF(KDF(K, "level1", ceil(i / W^2)), 638 "level2", ceil(i / W)), "level3", i). 640 where i in {1, 2, ... , W^3}. 642 The structure similar to external tree-based mechanism can be found 643 in Section 6 of [NISTSP800-108]. 645 5.3. Serial Constructions 647 The main idea behind external re-keying with a serial construction is 648 presented in Figure 5: 650 Maximum message size = m_max. 651 _____________________________________________________________ 652 m_max 653 <----------------> 654 M^{1,1} |=== | 655 M^{1,2} |=============== | 656 K*_1 = K --->K^1--> ... ... 657 | M^{1,q_1} |======== | 658 | 659 | 660 | M^{2,1} |================| 661 v M^{2,2} |===== | 662 K*_2 ------->K^2--> ... ... 663 | M^{2,q_2} |========== | 664 | 665 ... 666 | M^{t,1} |============ | 667 v M^{t,2} |============= | 668 K*_t ------->K^t--> ... ... 669 M^{t,q_t} |========== | 671 _____________________________________________________________ 673 Figure 5: External serial re-keying mechanisms 675 The frame key K^i, i = 1, ... , t - 1, is updated after processing a 676 certain amount of messages (see Section 5.1). 678 5.3.1. Serial Construction Based on a KDF on a Block Cipher 680 The frame key K^i is calculated using ExtSerialC transformation as 681 follows: 683 K^i = ExtSerialC(K, i) = 684 MSB_k(E_{K*_i}(Vec_n(0)) |E_{K*_i}(Vec_n(1)) | ... | 685 E_{K*_i}(Vec_n(J - 1))), 687 where J = ceil(k / n), i = 1, ... , t, K*_i is calculated as follows: 689 K*_1 = K, 691 K*_{j+1} = MSB_k(E_{K*_j}(Vec_n(J)) | E_{K*_j}(Vec_n(J + 1)) | 692 ... | 693 E_{K*_j}(Vec_n(2 * J - 1))), 695 where j = 1, ... , t - 1. 697 5.3.2. Serial Construction Based on HKDF 699 The frame key K^i is calculated using ExtSerialH transformation as 700 follows: 702 K^i = ExtSerialH(K, i) = HKDF-Expand(K*_i, label1, k), 704 where i = 1, ... , t, HKDF-Expand is the HMAC-based key derivation 705 function, described in [RFC5869], K*_i is calculated as follows: 707 K*_1 = K, 709 K*_{j+1} = HKDF-Expand(K*_j, label2, k), where j = 1, ... , t - 1, 711 where label1 and label2 are different strings from V* that are 712 defined by a specific protocol (see, for example, TLS 1.3 updating 713 traffic keys algorithm [TLSDraft]). 715 6. Internal Re-keying Mechanisms 717 This section presents an approach to increase the key lifetime by 718 using a transformation of a data processing key (section key) during 719 each separate message processing. Each message is processed starting 720 with the same key (the first section key) and each section key is 721 updated after processing N bits of message (section). 723 This section provides internal re-keying mechanisms called ACPKM 724 (Advanced Cryptographic Prolongation of Key Material) and ACPKM- 725 Master that do not use a master key and use a master key 726 respectively. Such mechanisms are integrated into the base modes of 727 operation and actually form new modes of operation, therefore they 728 are called "internal re-keying" mechanisms in this document. 730 Internal re-keying mechanisms are recommended to be used in protocols 731 that process large single messages (e.g., CMS messages), since the 732 maximum gain in increasing the key lifetime is achieved by increasing 733 the length of a message, while it provides almost no increase in the 734 number of messages that can be processed with one initial key. 736 Internal re-keying increases the key lifetime through the following 737 approach. Suppose protocol P uses some base mode of operation. Let 738 L1 and L2 be a side channel and combinatorial limitations 739 respectively and for some fixed amount of messages q let m1, m2 be 740 the lengths of messages, that can be safely processed with a single 741 initial key K according to these limitations. 743 Thus, by analogy with the Section 5 without re-keying the final key 744 lifetime restriction, as displayed in Figure 7, is equal to L1 and 745 only q messages of the length m1 can be safely processed. 747 K 748 | 749 v 750 ^ +----------------+------------------------------------+ 751 | |==============L1| L2| 752 | |================| | 753 q |================| | 754 | |================| | 755 | |================| | 756 v +----------------+------------------------------------+ 757 <-------m1-------> 758 <----------------------------m2-----------------------> 760 Figure 7: Basic principles of message processing without internal re-keying 762 Suppose that the safety margin for the protocol P is fixed and 763 internal re-keying approach is applied to the base mode of operation. 764 Suppose further that every message is processed with a section key, 765 which is transformed after processing N bits of data, where N is a 766 parameter. If q * N does not exceed L1 then the side channel 767 limitation L1 goes off and the resulting key lifetime limitation of 768 the initial key K can be calculated on the basis of a new 769 combinatorial limitation L2'. The security of the mode of operation 770 that uses internal re-keying increases when compared to base mode of 771 operation without re-keying (thus, L2 < L2'). Hence, as displayed in 772 Figure 8, the resulting key lifetime limitation in case of using 773 internal re-keying can be increased up to L2'. 775 K-----> K^1-------------> K^2 -----------> . . . 776 | | 777 v v 778 ^ +----------------+----------------+-------------------+--...--+ 779 | |==============L1|==============L1|====== L2| L2'| 780 | |================|================|====== | | 781 q |================|================|====== . . . | | 782 | |================|================|====== | | 783 | |================|================|====== | | 784 v +----------------+----------------+-------------------+--...--+ 785 <-------N--------> 787 Figure 8: Basic principles of message processing with internal re-keying 789 Note: the key transformation process is depicted in a simplified 790 form. A specific approach (ACPKM and ACPKM-Master re-keying 791 mechanisms) is described below. 793 Since the performance of encryption can slightly decrease for rather 794 small values of N, the parameter N should be selected for a 795 particular protocol as maximum possible to provide necessary key 796 lifetime for the security models that are considered. 798 Consider an example. Suppose L1 = 128 MB and L2 = 10 TB. Let the 799 message size in the protocol be large/unlimited (may exhaust the 800 whole key lifetime L2). The most restrictive resulting key lifetime 801 limitation is equal to 128 MB. 803 Thus, there is a need to put a limit on the maximum message size 804 m_max. For example, if m_max = 32 MB, it may happen that the 805 renegotiation of initial key K would be required after processing 806 only four messages. 808 If an internal re-keying mechanism with section size N = 1 MB is 809 used, more than L1 / N = 128 MB / 1 MB = 128 messages can be 810 processed before the renegotiation of initial key K (instead of 4 811 messages in case when an internal re-keying mechanism is not used). 812 Note that only one section of each message is processed with the 813 section key K^i, and, consequently, the key lifetime limitation L1 814 goes off. Hence the resulting key lifetime limitation L2' can be set 815 to more then 10 TB (in the case when a single large message is 816 processed using the initial key K). 818 6.1. Methods of Key Lifetime Control 820 Suppose L is an amount of data that can be safely processed with one 821 section key, N is a section size (fixed parameter). Suppose M^{i}_1 822 is the first section of message M^{i}, i = 1, ... , q (see Figure 9 823 and Figure 10), then the parameter q can be calculated in accordance 824 with one of the following two approaches: 826 o Explicit approach: 827 q_i is such that |M^{1}_1| + ... + |M^{q}_1| <= L, |M^{1}_1| + ... 828 + |M^{q+1}_1| > L 829 This approach allows to use the section key K^i in an almost 830 optimal way but it can be applied only in case when messages 831 cannot be lost or reordered (e.g., TLS records). 833 o Implicit approach: 834 q = L / N. 835 The amount of data processed with one section key K^i is 836 calculated under the assumption that the length of every message 837 is equal or greater than section size N and so it can be 838 considerably less than the key lifetime limitation L. On the 839 other hand, this approach can be applied in case when messages may 840 be lost or reordered (e.g., DTLS records). 842 6.2. Constructions that Do Not Require Master Key 844 This section describes the block cipher modes that use the ACPKM re- 845 keying mechanism, which does not use a master key: an initial key is 846 used directly for the encryption of the data. 848 6.2.1. ACPKM Re-keying Mechanisms 850 This section defines periodical key transformation without a master 851 key, which is called ACPKM re-keying mechanism. This mechanism can 852 be applied to one of the basic encryption modes (CTR and GCM block 853 cipher modes) for getting an extension of this encryption mode that 854 uses periodical key transformation without a master key. This 855 extension can be considered as a new encryption mode. 857 An additional parameter that defines functioning of base encryption 858 modes with the ACPKM re-keying mechanism is the section size N. The 859 value of N is measured in bits and is fixed within a specific 860 protocol based on the requirements of the system capacity and the key 861 lifetime. The section size N MUST be divisible by the block size n. 863 The main idea behind internal re-keying without a master key is 864 presented in Figure 9: 866 Section size = const = N, 867 maximum message size = m_max. 868 ____________________________________________________________________ 870 ACPKM ACPKM ACPKM 871 K^1 = K ---> K^2 ---...-> K^{l_max-1} ----> K^{l_max} 872 | | | | 873 | | | | 874 v v v v 875 M^{1} |==========|==========| ... |==========|=======: | 876 M^{2} |==========|==========| ... |=== | : | 877 . . . . . . : 878 : : : : : : : 879 M^{q} |==========|==========| ... |==========|===== : | 880 section : 881 <----------> m_max 882 N bit 883 ___________________________________________________________________ 884 l_max = ceil(m_max/N). 886 Figure 9: Internal re-keying without a master key 888 During the processing of the input message M with the length m in 889 some encryption mode that uses ACPKM key transformation of the 890 initial key K the message is divided into l = ceil(m / N) sections 891 (denoted as M = M_1 | M_2 | ... | M_l, where M_i is in V_N for i in 892 {1, 2, ... , l - 1} and M_l is in V_r, r <= N). The first section of 893 each message is processed with the section key K^1 = K. To process 894 the (i + 1)-th section of each message the section key K^{i+1} is 895 calculated using ACPKM transformation as follows: 897 K^{i+1} = ACPKM(K^i) = MSB_k(E_{K^i}(D_1) | ... | E_{K^i}(D_J)), 899 where J = ceil(k/n) and D_1, D_2, ... , D_J are in V_n and are 900 calculated as follows: 902 D_1 | D_2 | ... | D_J = MSB_{J * n}(D), 904 where D is the following constant in V_{1024}: 906 D = ( 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 907 | 88 | 89 | 8a | 8b | 8c | 8d | 8e | 8f 908 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 909 | 98 | 99 | 9a | 9b | 9c | 9d | 9e | 9f 910 | a0 | a1 | a2 | a3 | a4 | a5 | a6 | a7 911 | a8 | a9 | aa | ab | ac | ad | ae | af 912 | b0 | b1 | b2 | b3 | b4 | b5 | b6 | b7 913 | b8 | b9 | ba | bb | bc | bd | be | bf 914 | c0 | c1 | c2 | c3 | c4 | c5 | c6 | c7 915 | c8 | c9 | ca | cb | cc | cd | ce | cf 916 | d0 | d1 | d2 | d3 | d4 | d5 | d6 | d7 917 | d8 | d9 | da | db | dc | dd | de | df 918 | e0 | e1 | e2 | e3 | e4 | e5 | e6 | e7 919 | e8 | e9 | ea | eb | ec | ed | ee | ef 920 | f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 921 | f8 | f9 | fa | fb | fc | fd | fe | ff ) 923 N o t e : The constant D is such that D_1, ... , D_J are pairwise 924 different for any allowed n and k values. 926 N o t e : The constant D is such that the highest bit of its each 927 octet is equal to 1. This condition is important, as in conjunction 928 with message length limitation it allows to prevent collisions of 929 block cipher permutation inputs in cases of key transformation and 930 message processing. 932 6.2.2. CTR-ACPKM Encryption Mode 934 This section defines a CTR-ACPKM encryption mode that uses internal 935 ACPKM re-keying mechanism for the periodical key transformation. 937 The CTR-ACPKM mode can be considered as the basic encryption mode CTR 938 (see [MODES]) extended by the ACPKM re-keying mechanism. 940 The CTR-ACPKM encryption mode can be used with the following 941 parameters: 943 o 64 <= n <= 512; 945 o 128 <= k <= 512; 947 o the number of bits c in a specific part of the block to be 948 incremented is such that 32 <= c <= 3 / 4 n, c is a multiple of 8; 950 o the maximum message size m_max = n * 2^{c-1}. 952 The CTR-ACPKM mode encryption and decryption procedures are defined 953 as follows: 955 +----------------------------------------------------------------+ 956 | CTR-ACPKM-Encrypt(N, K, ICN, P) | 957 |----------------------------------------------------------------| 958 | Input: | 959 | - section size N, | 960 | - initial key K, | 961 | - initial counter nonce ICN in V_{n-c}, | 962 | - plaintext P = P_1 | ... | P_b, |P| <= m_max. | 963 | Output: | 964 | - ciphertext C. | 965 |----------------------------------------------------------------| 966 | 1. CTR_1 = ICN | 0^c | 967 | 2. For j = 2, 3, ... , b do | 968 | CTR_{j} = Inc_c(CTR_{j-1}) | 969 | 3. K^1 = K | 970 | 4. For i = 2, 3, ... , ceil(|P| / N) | 971 | K^i = ACPKM(K^{i-1}) | 972 | 5. For j = 1, 2, ... , b do | 973 | i = ceil(j * n / N), | 974 | G_j = E_{K^i}(CTR_j) | 975 | 6. C = P (xor) MSB_{|P|}(G_1 | ... | G_b) | 976 | 7. Return C | 977 +----------------------------------------------------------------+ 979 +----------------------------------------------------------------+ 980 | CTR-ACPKM-Decrypt(N, K, ICN, C) | 981 |----------------------------------------------------------------| 982 | Input: | 983 | - section size N, | 984 | - initial key K, | 985 | - initial counter nonce ICN in V_{n-c}, | 986 | - ciphertext C = C_1 | ... | C_b, |C| <= m_max. | 987 | Output: | 988 | - plaintext P. | 989 |----------------------------------------------------------------| 990 | 1. P = CTR-ACPKM-Encrypt(N, K, ICN, C) | 991 | 2. Return P | 992 +----------------------------------------------------------------+ 994 The initial counter nonce ICN value for each message that is 995 encrypted under the given initial key K must be chosen in a unique 996 manner. 998 6.2.3. GCM-ACPKM Authenticated Encryption Mode 1000 This section defines GCM-ACPKM authenticated encryption mode that 1001 uses internal ACPKM re-keying mechanism for the periodical key 1002 transformation. 1004 The GCM-ACPKM mode can be considered as the basic authenticated 1005 encryption mode GCM (see [GCM]) extended by the ACPKM re-keying 1006 mechanism. 1008 The GCM-ACPKM authenticated encryption mode can be used with the 1009 following parameters: 1011 o n in {128, 256}; 1013 o 128 <= k <= 512; 1015 o the number of bits c in a specific part of the block to be 1016 incremented is such that 1 / 4 n <= c <= 1 / 2 n, c is a multiple 1017 of 8; 1019 o authentication tag length t; 1021 o the maximum message size m_max = min{n * (2^{c-1} - 2), 2^{n/2} - 1022 1}. 1024 The GCM-ACPKM mode encryption and decryption procedures are defined 1025 as follows: 1027 +-------------------------------------------------------------------+ 1028 | GHASH(X, H) | 1029 |-------------------------------------------------------------------| 1030 | Input: | 1031 | - bit string X = X_1 | ... | X_m, X_1, ... , X_m in V_n. | 1032 | Output: | 1033 | - block GHASH(X, H) in V_n. | 1034 |-------------------------------------------------------------------| 1035 | 1. Y_0 = 0^n | 1036 | 2. For i = 1, ... , m do | 1037 | Y_i = (Y_{i-1} (xor) X_i) * H | 1038 | 3. Return Y_m | 1039 +-------------------------------------------------------------------+ 1041 +-------------------------------------------------------------------+ 1042 | GCTR(N, K, ICB, X) | 1043 |-------------------------------------------------------------------| 1044 | Input: | 1045 | - section size N, | 1046 | - initial key K, | 1047 | - initial counter block ICB, | 1048 | - X = X_1 | ... | X_b. | 1049 | Output: | 1050 | - Y in V_{|X|}. | 1051 |-------------------------------------------------------------------| 1052 | 1. If X in V_0 then return Y, where Y in V_0 | 1053 | 2. GCTR_1 = ICB | 1054 | 3. For i = 2, ... , b do | 1055 | GCTR_i = Inc_c(GCTR_{i-1}) | 1056 | 4. K^1 = K | 1057 | 5. For j = 2, ... , ceil(|X| / N) | 1058 | K^j = ACPKM(K^{j-1}) | 1059 | 6. For i = 1, ... , b do | 1060 | j = ceil(i * n / N), | 1061 | G_i = E_{K_j}(GCTR_i) | 1062 | 7. Y = X (xor) MSB_{|X|}(G_1 | ... | G_b) | 1063 | 8. Return Y | 1064 +-------------------------------------------------------------------+ 1066 +-------------------------------------------------------------------+ 1067 | GCM-ACPKM-Encrypt(N, K, ICN, P, A) | 1068 |-------------------------------------------------------------------| 1069 | Input: | 1070 | - section size N, | 1071 | - initial key K, | 1072 | - initial counter nonce ICN in V_{n-c}, | 1073 | - plaintext P = P_1 | ... | P_b, |P| <= m_max, | 1074 | - additional authenticated data A. | 1075 | Output: | 1076 | - ciphertext C, | 1077 | - authentication tag T. | 1078 |-------------------------------------------------------------------| 1079 | 1. H = E_{K}(0^n) | 1080 | 2. ICB_0 = ICN | 0^{c-1} | 1 | 1081 | 3. C = GCTR(N, K, Inc_c(ICB_0), P) | 1082 | 4. u = n * ceil(|C| / n) - |C| | 1083 | v = n * ceil(|A| / n) - |A| | 1084 | 5. S = GHASH(A | 0^v | C | 0^u | Vec_{n/2}(|A|) | | 1085 | | Vec_{n/2}(|C|), H) | 1086 | 6. T = MSB_t(E_{K}(ICB_0) (xor) S) | 1087 | 7. Return C | T | 1088 +-------------------------------------------------------------------+ 1090 +-------------------------------------------------------------------+ 1091 | GCM-ACPKM-Decrypt(N, K, ICN, A, C, T) | 1092 |-------------------------------------------------------------------| 1093 | Input: | 1094 | - section size N, | 1095 | - initial key K, | 1096 | - initial counter block ICN, | 1097 | - additional authenticated data A, | 1098 | - ciphertext C = C_1 | ... | C_b, |C| <= m_max, | 1099 | - authentication tag T. | 1100 | Output: | 1101 | - plaintext P or FAIL. | 1102 |-------------------------------------------------------------------| 1103 | 1. H = E_{K}(0^n) | 1104 | 2. ICB_0 = ICN | 0^{c-1} | 1 | 1105 | 3. P = GCTR(N, K, Inc_c(ICB_0), C) | 1106 | 4. u = n * ceil(|C| / n) - |C| | 1107 | v = n * ceil(|A| / n) - |A| | 1108 | 5. S = GHASH(A | 0^v | C | 0^u | Vec_{n/2}(|A|) | | 1109 | | Vec_{n/2}(|C|), H) | 1110 | 6. T' = MSB_t(E_{K}(ICB_0) (xor) S) | 1111 | 7. If T = T' then return P; else return FAIL | 1112 +-------------------------------------------------------------------+ 1114 The * operation on (pairs of) the 2^n possible blocks corresponds to 1115 the multiplication operation for the binary Galois (finite) field of 1116 2^n elements defined by the polynomial f as follows (by analogy with 1117 [GCM]): 1119 n = 128: f = a^128 + a^7 + a^2 + a^1 + 1, 1121 n = 256: f = a^256 + a^10 + a^5 + a^2 + 1. 1123 The initial vector IV value for each message that is encrypted under 1124 the given initial key K must be chosen in a unique manner. 1126 The key for computing values E_{K}(ICB_0) and H is not updated and is 1127 equal to the initial key K. 1129 6.3. Constructions that Require Master Key 1131 This section describes the block cipher modes that use the ACPKM- 1132 Master re-keying mechanism, which use the initial key K as a master 1133 key, so K is never used directly for data processing but is used for 1134 key derivation. 1136 6.3.1. ACPKM-Master Key Derivation from the Master Key 1138 This section defines periodical key transformation with a master key, 1139 which is called ACPKM-Master re-keying mechanism. This mechanism can 1140 be applied to one of the basic modes of operation (CTR, GCM, CBC, 1141 CFB, OMAC modes) for getting an extension that uses periodical key 1142 transformation with a master key. This extension can be considered 1143 as a new mode of operation. 1145 Additional parameters that define the functioning of modes of 1146 operation that use the ACPKM-Master re-keying mechanism are the 1147 section size N, the change frequency T* of the master keys K*_1, 1148 K*_2, ... (see Figure 10) and the size d of the section key material. 1149 The values of N and T* are measured in bits and are fixed within a 1150 specific protocol, based on the requirements of the system capacity 1151 and the key lifetime. The section size N MUST also be divisible by 1152 the block size n. The master key frequency T* MUST be divisible by d 1153 and by n. 1155 The main idea behind internal re-keying with a master key is 1156 presented in Figure 10: 1158 Master key frequency T*, 1159 section size N, 1160 maximum message size = m_max. 1161 __________________________________________________________________________________ 1163 ACPKM ACPKM 1164 K*_1 = K--------------> K*_2 ---------...---------> K*_l_max 1165 ___|___ ___|___ ___|___ 1166 | | | | | | 1167 v ... v v ... v v ... v 1168 K[1] K[t] K[t+1] K[2t] K[(l_max-1)t+1] K[l_max*t] 1169 | | | | | | 1170 | | | | | | 1171 v v v v v v 1172 M^{1}||========|...|========||========|...|========||...||========|...|== : || 1173 M^{2}||========|...|========||========|...|========||...||========|...|======: || 1174 ... || | | || | | || || | | : || 1175 M^{q}||========|...|========||==== |...| ||...|| |...| : || 1176 section : 1177 <--------> : 1178 N bit m_max 1179 __________________________________________________________________________________ 1180 |K[i]| = d, 1181 t = T* / d, 1182 l_max = ceil(m_max / (N * t)). 1184 Figure 10: Internal re-keying with a master key 1186 During the processing of the input message M with the length m in 1187 some mode of operation that uses ACPKM-Master key transformation with 1188 the initial key K and the master key frequency T* the message M is 1189 divided into l = ceil(m / N) sections (denoted as M = M_1 | M_2 | 1190 ... | M_l, where M_i is in V_N for i in {1, 2, ... , l - 1} and M_l 1191 is in V_r, r <= N). The j-th section of each message is processed 1192 with the key material K[j], j in {1, ... , l}, |K[j]| = d, that is 1193 calculated with the ACPKM-Master algorithm as follows: 1195 K[1] | ... | K[l] = ACPKM-Master(T*, K, d, l) = CTR-ACPKM-Encrypt 1196 (T*, K, 1^{n/2}, 0^{d*l}). 1198 Note: the parameters d and l MUST be such that d * l <= n * 1199 2^{n/2-1}. 1201 6.3.2. CTR-ACPKM-Master Encryption Mode 1203 This section defines a CTR-ACPKM-Master encryption mode that uses 1204 internal ACPKM-Master re-keying mechanism for the periodical key 1205 transformation. 1207 The CTR-ACPKM-Master encryption mode can be considered as the basic 1208 encryption mode CTR (see [MODES]) extended by the ACPKM-Master re- 1209 keying mechanism. 1211 The CTR-ACPKM-Master encryption mode can be used with the following 1212 parameters: 1214 o 64 <= n <= 512; 1216 o 128 <= k <= 512; 1218 o the number of bits c in a specific part of the block to be 1219 incremented is such that 32 <= c <= 3 / 4 n, c is a multiple of 8; 1221 o the maximum message size m_max = min{N * (n * 2^{n/2-1} / k), n * 1222 2^c}. 1224 The key material K[j] that is used for one section processing is 1225 equal to K^j, |K^j| = k bits. 1227 The CTR-ACPKM-Master mode encryption and decryption procedures are 1228 defined as follows: 1230 +----------------------------------------------------------------+ 1231 | CTR-ACPKM-Master-Encrypt(N, K, T*, ICN, P) | 1232 |----------------------------------------------------------------| 1233 | Input: | 1234 | - section size N, | 1235 | - initial key K, | 1236 | - master key frequency T*, | 1237 | - initial counter nonce ICN in V_{n-c}, | 1238 | - plaintext P = P_1 | ... | P_b, |P| <= m_max. | 1239 | Output: | 1240 | - ciphertext C. | 1241 |----------------------------------------------------------------| 1242 | 1. CTR_1 = ICN | 0^c | 1243 | 2. For j = 2, 3, ... , b do | 1244 | CTR_{j} = Inc_c(CTR_{j-1}) | 1245 | 3. l = ceil(|P| / N) | 1246 | 4. K^1 | ... | K^l = ACPKM-Master(T*, K, k, l) | 1247 | 5. For j = 1, 2, ... , b do | 1248 | i = ceil(j * n / N), | 1249 | G_j = E_{K^i}(CTR_j) | 1250 | 6. C = P (xor) MSB_{|P|}(G_1 | ... |G_b) | 1251 | 7. Return C | 1252 |----------------------------------------------------------------+ 1254 +----------------------------------------------------------------+ 1255 | CTR-ACPKM-Master-Decrypt(N, K, T*, ICN, C) | 1256 |----------------------------------------------------------------| 1257 | Input: | 1258 | - section size N, | 1259 | - initial key K, | 1260 | - master key frequency T*, | 1261 | - initial counter nonce ICN in V_{n-c}, | 1262 | - ciphertext C = C_1 | ... | C_b, |C| <= m_max. | 1263 | Output: | 1264 | - plaintext P. | 1265 |----------------------------------------------------------------| 1266 | 1. P = CTR-ACPKM-Master-Encrypt(N, K, T*, ICN, C) | 1267 | 1. Return P | 1268 +----------------------------------------------------------------+ 1270 The initial counter nonce ICN value for each message that is 1271 encrypted under the given initial key must be chosen in a unique 1272 manner. 1274 6.3.3. GCM-ACPKM-Master Authenticated Encryption Mode 1276 This section defines a GCM-ACPKM-Master authenticated encryption mode 1277 that uses internal ACPKM-Master re-keying mechanism for the 1278 periodical key transformation. 1280 The GCM-ACPKM-Master authenticated encryption mode can be considered 1281 as the basic authenticated encryption mode GCM (see [GCM]) extended 1282 by the ACPKM-Master re-keying mechanism. 1284 The GCM-ACPKM-Master authenticated encryption mode can be used with 1285 the following parameters: 1287 o n in {128, 256}; 1289 o 128 <= k <= 512; 1291 o the number of bits c in a specific part of the block to be 1292 incremented is such that 1 / 4 n <= c <= 1 / 2 n, c is a multiple 1293 of 8; 1295 o authentication tag length t; 1297 o the maximum message size m_max = min{N * ( n * 2^{n/2-1} / k), n * 1298 (2^c - 2), 2^{n/2} - 1}. 1300 The key material K[j] that is used for the j-th section processing is 1301 equal to K^j, |K^j| = k bits. 1303 The GCM-ACPKM-Master mode encryption and decryption procedures are 1304 defined as follows: 1306 +-------------------------------------------------------------------+ 1307 | GHASH(X, H) | 1308 |-------------------------------------------------------------------| 1309 | Input: | 1310 | - bit string X = X_1 | ... | X_m, X_i in V_n for i in {1, ... ,m}| 1311 | Output: | 1312 | - block GHASH(X, H) in V_n | 1313 |-------------------------------------------------------------------| 1314 | 1. Y_0 = 0^n | 1315 | 2. For i = 1, ... , m do | 1316 | Y_i = (Y_{i-1} (xor) X_i) * H | 1317 | 3. Return Y_m | 1318 +-------------------------------------------------------------------+ 1320 +-------------------------------------------------------------------+ 1321 | GCTR(N, K, T*, ICB, X) | 1322 |-------------------------------------------------------------------| 1323 | Input: | 1324 | - section size N, | 1325 | - initial key K, | 1326 | - master key frequency T*, | 1327 | - initial counter block ICB, | 1328 | - X = X_1 | ... | X_b. | 1329 | Output: | 1330 | - Y in V_{|X|}. | 1331 |-------------------------------------------------------------------| 1332 | 1. If X in V_0 then return Y, where Y in V_0 | 1333 | 2. GCTR_1 = ICB | 1334 | 3. For i = 2, ... , b do | 1335 | GCTR_i = Inc_c(GCTR_{i-1}) | 1336 | 4. l = ceil(|X| / N) | 1337 | 5. K^1 | ... | K^l = ACPKM-Master(T*, K, k, l) | 1338 | 6. For j = 1, ... , b do | 1339 | i = ceil(j * n / N), | 1340 | G_j = E_{K^i}(GCTR_j) | 1341 | 7. Y = X (xor) MSB_{|X|}(G_1 | ... | G_b) | 1342 | 8. Return Y | 1343 +-------------------------------------------------------------------+ 1345 +-------------------------------------------------------------------+ 1346 | GCM-ACPKM-Master-Encrypt(N, K, T*, ICN, P, A) | 1347 |-------------------------------------------------------------------| 1348 | Input: | 1349 | - section size N, | 1350 | - initial key K, | 1351 | - master key frequency T*, | 1352 | - initial counter nonce ICN in V_{n-c}, | 1353 | - plaintext P = P_1 | ... | P_b, |P| <= m_max. | 1354 | - additional authenticated data A. | 1355 | Output: | 1356 | - ciphertext C, | 1357 | - authentication tag T. | 1358 |-------------------------------------------------------------------| 1359 | 1. K^1 = ACPKM-Master(T*, K, k, 1) | 1360 | 2. H = E_{K^1}(0^n) | 1361 | 3. ICB_0 = ICN | 0^{c-1} | 1 | 1362 | 4. C = GCTR(N, K, T*, Inc_c(ICB_0), P) | 1363 | 5. u = n * ceil(|C| / n) - |C| | 1364 | v = n * ceil(|A| / n) - |A| | 1365 | 6. S = GHASH(A | 0^v | C | 0^u | Vec_{n/2}(|A|) | | 1366 | | Vec_{n/2}(|C|), H) | 1367 | 7. T = MSB_t(E_{K^1}(ICB_0) (xor) S) | 1368 | 8. Return C | T | 1369 +-------------------------------------------------------------------+ 1371 +-------------------------------------------------------------------+ 1372 | GCM-ACPKM-Master-Decrypt(N, K, T*, ICN, A, C, T) | 1373 |-------------------------------------------------------------------| 1374 | Input: | 1375 | - section size N, | 1376 | - initial key K, | 1377 | - master key frequency T*, | 1378 | - initial counter nonce ICN in V_{n-c}, | 1379 | - additional authenticated data A. | 1380 | - ciphertext C = C_1 | ... | C_b, |C| <= m_max, | 1381 | - authentication tag T. | 1382 | Output: | 1383 | - plaintext P or FAIL. | 1384 |-------------------------------------------------------------------| 1385 | 1. K^1 = ACPKM-Master(T*, K, k, 1) | 1386 | 2. H = E_{K^1}(0^n) | 1387 | 3. ICB_0 = ICN | 0^{c-1} | 1 | 1388 | 4. P = GCTR(N, K, T*, Inc_c(ICB_0), C) | 1389 | 5. u = n * ceil(|C| / n) - |C| | 1390 | v = n * ceil(|A| / n) - |A| | 1391 | 6. S = GHASH(A | 0^v | C | 0^u | Vec_{n/2}(|A|) | | 1392 | | Vec_{n/2}(|C|), H) | 1393 | 7. T' = MSB_t(E_{K^1}(ICB_0) (xor) S) | 1394 | 8. IF T = T' then return P; else return FAIL. | 1395 +-------------------------------------------------------------------+ 1397 The * operation on (pairs of) the 2^n possible blocks corresponds to 1398 the multiplication operation for the binary Galois (finite) field of 1399 2^n elements defined by the polynomial f as follows (by analogy with 1400 [GCM]): 1402 n = 128: f = a^128 + a^7 + a^2 + a^1 + 1, 1404 n = 256: f = a^256 + a^10 + a^5 + a^2 + 1. 1406 The initial vector IV value for each message that is encrypted under 1407 the given initial key must be chosen in a unique manner. 1409 6.3.4. CBC-ACPKM-Master Encryption Mode 1411 This section defines a CBC-ACPKM-Master encryption mode that uses 1412 internal ACPKM-Master re-keying mechanism for the periodical key 1413 transformation. 1415 The CBC-ACPKM-Master encryption mode can be considered as the basic 1416 encryption mode CBC (see [MODES]) extended by the ACPKM-Master re- 1417 keying mechanism. 1419 The CBC-ACPKM-Master encryption mode can be used with the following 1420 parameters: 1422 o 64 <= n <= 512; 1424 o 128 <= k <= 512; 1426 o the maximum message size m_max = N * (n * 2^{n/2-1} / k). 1428 In the specification of the CBC-ACPKM-Master mode the plaintext and 1429 ciphertext must be a sequence of one or more complete data blocks. 1430 If the data string to be encrypted does not initially satisfy this 1431 property, then it MUST be padded to form complete data blocks. The 1432 padding methods are out of the scope of this document. An example of 1433 a padding method can be found in Appendix A of [MODES]. 1435 The key material K[j] that is used for the j-th section processing is 1436 equal to K^j, |K^j| = k bits. 1438 We will denote by D_{K} the decryption function which is a 1439 permutation inverse to the E_{K}. 1441 The CBC-ACPKM-Master mode encryption and decryption procedures are 1442 defined as follows: 1444 +----------------------------------------------------------------+ 1445 | CBC-ACPKM-Master-Encrypt(N, K, T*, IV, P) | 1446 |----------------------------------------------------------------| 1447 | Input: | 1448 | - section size N, | 1449 | - initial key K, | 1450 | - master key frequency T*, | 1451 | - initialization vector IV in V_n, | 1452 | - plaintext P = P_1 | ... | P_b, |P_b| = n, |P| <= m_max. | 1453 | Output: | 1454 | - ciphertext C. | 1455 |----------------------------------------------------------------| 1456 | 1. l = ceil(|P| / N) | 1457 | 2. K^1 | ... | K^l = ACPKM-Master(T*, K, k, l) | 1458 | 3. C_0 = IV | 1459 | 4. For j = 1, 2, ... , b do | 1460 | i = ceil(j * n / N), | 1461 | C_j = E_{K^i}(P_j (xor) C_{j-1}) | 1462 | 5. Return C = C_1 | ... | C_b | 1463 |----------------------------------------------------------------+ 1465 +----------------------------------------------------------------+ 1466 | CBC-ACPKM-Master-Decrypt(N, K, T*, IV, C) | 1467 |----------------------------------------------------------------| 1468 | Input: | 1469 | - section size N, | 1470 | - initial key K, | 1471 | - master key frequency T*, | 1472 | - initialization vector IV in V_n, | 1473 | - ciphertext C = C_1 | ... | C_b, |C_b| = n, |C| <= m_max. | 1474 | Output: | 1475 | - plaintext P. | 1476 |----------------------------------------------------------------| 1477 | 1. l = ceil(|C| / N) | 1478 | 2. K^1 | ... | K^l = ACPKM-Master(T*, K, k, l) | 1479 | 3. C_0 = IV | 1480 | 4. For j = 1, 2, ... , b do | 1481 | i = ceil(j * n / N) | 1482 | P_j = D_{K^i}(C_j) (xor) C_{j-1} | 1483 | 5. Return P = P_1 | ... | P_b | 1484 +----------------------------------------------------------------+ 1486 The initialization vector IV for each message that is encrypted under 1487 the given initial key does not need to be secret, but must be 1488 unpredictable. 1490 6.3.5. CFB-ACPKM-Master Encryption Mode 1492 This section defines a CFB-ACPKM-Master encryption mode that uses 1493 internal ACPKM-Master re-keying mechanism for the periodical key 1494 transformation. 1496 The CFB-ACPKM-Master encryption mode can be considered as the basic 1497 encryption mode CFB (see [MODES]) extended by the ACPKM-Master re- 1498 keying mechanism. 1500 The CFB-ACPKM-Master encryption mode can be used with the following 1501 parameters: 1503 o 64 <= n <= 512; 1505 o 128 <= k <= 512; 1507 o the maximum message size m_max = N * (n * 2^{n/2-1} / k). 1509 The key material K[j] that is used for the j-th section processing is 1510 equal to K^j, |K^j| = k bits. 1512 The CFB-ACPKM-Master mode encryption and decryption procedures are 1513 defined as follows: 1515 +-------------------------------------------------------------+ 1516 | CFB-ACPKM-Master-Encrypt(N, K, T*, IV, P) | 1517 |-------------------------------------------------------------| 1518 | Input: | 1519 | - section size N, | 1520 | - initial key K, | 1521 | - master key frequency T*, | 1522 | - initialization vector IV in V_n, | 1523 | - plaintext P = P_1 | ... | P_b, |P| <= m_max. | 1524 | Output: | 1525 | - ciphertext C. | 1526 |-------------------------------------------------------------| 1527 | 1. l = ceil(|P| / N) | 1528 | 2. K^1 | ... | K^l = ACPKM-Master(T*, K, k, l) | 1529 | 3. C_0 = IV | 1530 | 4. For j = 1, 2, ... , b - 1 do | 1531 | i = ceil(j * n / N), | 1532 | C_j = E_{K^i}(C_{j-1}) (xor) P_j | 1533 | 5. C_b = MSB_{|P_b|}(E_{K^l}(C_{b-1})) (xor) P_b | 1534 | 6. Return C = C_1 | ... | C_b | 1535 |-------------------------------------------------------------+ 1537 +-------------------------------------------------------------+ 1538 | CFB-ACPKM-Master-Decrypt(N, K, T*, IV, C) | 1539 |-------------------------------------------------------------| 1540 | Input: | 1541 | - section size N, | 1542 | - initial key K, | 1543 | - master key frequency T*, | 1544 | - initialization vector IV in V_n, | 1545 | - ciphertext C = C_1 | ... | C_b, |C| <= m_max. | 1546 | Output: | 1547 | - plaintext P. | 1548 |-------------------------------------------------------------| 1549 | 1. l = ceil(|C| / N) | 1550 | 2. K^1 | ... | K^l = ACPKM-Master(T*, K, k, l) | 1551 | 3. C_0 = IV | 1552 | 4. For j = 1, 2, ... , b - 1 do | 1553 | i = ceil(j * n / N), | 1554 | P_j = E_{K^i}(C_{j-1}) (xor) C_j | 1555 | 5. P_b = MSB_{|C_b|}(E_{K^l}(C_{b-1})) (xor) C_b | 1556 | 6. Return P = P_1 | ... | P_b | 1557 +-------------------------------------------------------------+ 1559 The initialization vector IV for each message that is encrypted under 1560 the given initial key need not to be secret, but must be 1561 unpredictable. 1563 6.3.6. OMAC-ACPKM-Master Authentication Mode 1565 This section defines an OMAC-ACPKM-Master message authentication code 1566 calculation mode that uses internal ACPKM-Master re-keying mechanism 1567 for the periodical key transformation. 1569 The OMAC-ACPKM-Master mode can be considered as the basic message 1570 authentication code calculation mode OMAC, which is also known as 1571 CMAC (see [RFC4493]), extended by the ACPKM-Master re-keying 1572 mechanism. 1574 The OMAC-ACPKM-Master message authentication code calculation mode 1575 can be used with the following parameters: 1577 o n in {64, 128, 256}; 1579 o 128 <= k <= 512; 1581 o the maximum message size m_max = N * (n * 2^{n/2-1} / (k + n)). 1583 The key material K[j] that is used for one section processing is 1584 equal to K^j | K^j_1, where |K^j| = k and |K^j_1| = n. 1586 The following is a specification of the subkey generation process of 1587 OMAC: 1589 +-------------------------------------------------------------------+ 1590 | Generate_Subkey(K1, r) | 1591 |-------------------------------------------------------------------| 1592 | Input: | 1593 | - key K1. | 1594 | Output: | 1595 | - key SK. | 1596 |-------------------------------------------------------------------| 1597 | 1. If r = n then return K1 | 1598 | 2. If r < n then | 1599 | if MSB_1(K1) = 0 | 1600 | return K1 << 1 | 1601 | else | 1602 | return (K1 << 1) (xor) R_n | 1603 | | 1604 +-------------------------------------------------------------------+ 1606 Where R_n takes the following values: 1608 o n = 64: R_{64} = 0^{59} | 11011; 1609 o n = 128: R_{128} = 0^{120} | 10000111; 1611 o n = 256: R_{256} = 0^{145} | 10000100101. 1613 The OMAC-ACPKM-Master message authentication code calculation mode is 1614 defined as follows: 1616 +----------------------------------------------------------------------+ 1617 | OMAC-ACPKM-Master(K, N, T*, M) | 1618 |----------------------------------------------------------------------| 1619 | Input: | 1620 | - section size N, | 1621 | - initial key K, | 1622 | - master key frequency T*, | 1623 | - plaintext M = M_1 | ... | M_b, |M| <= m_max. | 1624 | Output: | 1625 | - message authentication code T. | 1626 |----------------------------------------------------------------------| 1627 | 1. C_0 = 0^n | 1628 | 2. l = ceil(|M| / N) | 1629 | 3. K^1 | K^1_1 | ... | K^l | K^l_1 = ACPKM-Master(T*, K, (k + n), l) | 1630 | 4. For j = 1, 2, ... , b - 1 do | 1631 | i = ceil(j * n / N), | 1632 | C_j = E_{K^i}(M_j (xor) C_{j-1}) | 1633 | 5. SK = Generate_Subkey(K^l_1, |M_b|) | 1634 | 6. If |M_b| = n then M*_b = M_b | 1635 | else M*_b = M_b | 1 | 0^{n - 1 -|M_b|} | 1636 | 7. T = E_{K^l}(M*_b (xor) C_{b-1} (xor) SK) | 1637 | 8. Return T | 1638 +----------------------------------------------------------------------+ 1640 7. Joint Usage of External and Internal Re-keying 1642 Any mechanism described in Section 5 can be used with any mechanism 1643 described in Section 6. 1645 8. Security Considerations 1647 Re-keying should be used to increase "a priori" security properties 1648 of ciphers in hostile environments (e.g., with side-channel 1649 adversaries). If some efficient attacks are known for a cipher, it 1650 must not be used. So re-keying cannot be used as a patch for 1651 vulnerable ciphers. Base cipher properties must be well analyzed, 1652 because the security of re-keying mechanisms is based on the security 1653 of a block cipher as a pseudorandom function. 1655 Re-keying is not intended to solve any post-quantum security issues 1656 for symmetric crypto, since the reduction of security caused by 1657 Grover's algorithm is not connected with a size of plaintext 1658 transformed by a cipher - only a negligible (sufficient for key 1659 uniqueness) material is needed; and the aim of re-keying is to limit 1660 a size of plaintext transformed on one initial key. 1662 Re-keying can provide backward security only if previous traffic keys 1663 are securely deleted by all parties that have the keys. 1665 9. References 1667 9.1. Normative References 1669 [CMS] Housley, R., "Cryptographic Message Syntax (CMS)", STD 70, 1670 RFC 5652, DOI 10.17487/RFC5652, September 2009, 1671 . 1673 [DTLS] Rescorla, E. and N. Modadugu, "Datagram Transport Layer 1674 Security Version 1.2", RFC 6347, DOI 10.17487/RFC6347, 1675 January 2012, . 1677 [ESP] Kent, S., "IP Encapsulating Security Payload (ESP)", 1678 RFC 4303, DOI 10.17487/RFC4303, December 2005, 1679 . 1681 [GCM] McGrew, D. and J. Viega, "The Galois/Counter Mode of 1682 Operation (GCM)", Submission to NIST 1683 http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/ 1684 gcm/gcm-spec.pdf, January 2004. 1686 [MODES] Dworkin, M., "Recommendation for Block Cipher Modes of 1687 Operation: Methods and Techniques", NIST Special 1688 Publication 800-38A, December 2001. 1690 [NISTSP800-108] 1691 National Institute of Standards and Technology, 1692 "Recommendation for Key Derivation Using Pseudorandom 1693 Functions", NIST Special Publication 800-108, November 1694 2008, . 1697 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1698 Requirement Levels", BCP 14, RFC 2119, 1699 DOI 10.17487/RFC2119, March 1997, 1700 . 1702 [RFC4493] Song, JH., Poovendran, R., Lee, J., and T. Iwata, "The 1703 AES-CMAC Algorithm", RFC 4493, DOI 10.17487/RFC4493, June 1704 2006, . 1706 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1707 Key Derivation Function (HKDF)", RFC 5869, 1708 DOI 10.17487/RFC5869, May 2010, 1709 . 1711 [RFC7836] Smyshlyaev, S., Ed., Alekseev, E., Oshkin, I., Popov, V., 1712 Leontiev, S., Podobaev, V., and D. Belyavsky, "Guidelines 1713 on the Cryptographic Algorithms to Accompany the Usage of 1714 Standards GOST R 34.10-2012 and GOST R 34.11-2012", 1715 RFC 7836, DOI 10.17487/RFC7836, March 2016, 1716 . 1718 [SSH] Ylonen, T. and C. Lonvick, Ed., "The Secure Shell (SSH) 1719 Transport Layer Protocol", RFC 4253, DOI 10.17487/RFC4253, 1720 January 2006, . 1722 [TLS] Dierks, T. and E. Rescorla, "The Transport Layer Security 1723 (TLS) Protocol Version 1.2", RFC 5246, 1724 DOI 10.17487/RFC5246, August 2008, 1725 . 1727 [TLSDraft] 1728 Rescorla, E., "The Transport Layer Security (TLS) Protocol 1729 Version 1.3", 2017, 1730 . 1732 9.2. Informative References 1734 [AbBell] Michel Abdalla and Mihir Bellare, "Increasing the Lifetime 1735 of a Key: A Comparative Analysis of the Security of Re- 1736 keying Techniques", ASIACRYPT2000, LNCS 1976, pp. 546-559, 1737 2000. 1739 [LDC] Howard M. Heys, "A Tutorial on Linear and Differential 1740 Cryptanalysis", 2017, 1741 . 1743 [Sweet32] Karthikeyan Bhargavan, Gaetan Leurent, "On the Practical 1744 (In-)Security of 64-bit Block Ciphers: Collision Attacks 1745 on HTTP over TLS and OpenVPN", Cryptology ePrint 1746 Archive Report 2016/798, 2016, 1747 . 1749 [TEMPEST] By Craig Ramsay, Jasper Lohuis, "TEMPEST attacks against 1750 AES. Covertly stealing keys for 200 euro", 2017, 1751 . 1754 Appendix A. Test examples 1756 External re-keying with a parallel construction based on AES-256 1757 **************************************************************** 1758 k = 256 1759 t = 128 1761 Initial key: 1762 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 1763 0F 0E 0D 0C 0B 0A 09 08 07 06 05 04 03 02 01 00 1765 K^1: 1766 51 16 8A B6 C8 A8 38 65 54 85 31 A5 D2 BA C3 86 1767 64 7D 5C D5 1C 3D 62 98 BC 09 B1 D8 64 EC D9 B1 1769 K^2: 1770 6F ED F5 D3 77 57 48 75 35 2B 5F 4D B6 5B E0 15 1771 B8 02 92 32 D8 D3 8D 73 FE DC DD C6 C8 36 78 BD 1773 K^3: 1774 B6 40 24 85 A4 24 BD 35 B4 26 43 13 76 26 70 B6 1775 5B F3 30 3D 3B 20 EB 14 D1 3B B7 91 74 E3 DB EC 1777 ... 1779 K^126: 1780 2F 3F 15 1B 53 88 23 CD 7D 03 FC 3D FD B3 57 5E 1781 23 E4 1C 4E 46 FF 6B 33 34 12 27 84 EF 5D 82 23 1783 K^127: 1784 8E 51 31 FB 0B 64 BB D0 BC D4 C5 7B 1C 66 EF FD 1785 97 43 75 10 6C AF 5D 5E 41 E0 17 F4 05 63 05 ED 1787 K^128: 1788 77 4F BF B3 22 60 C5 3B A3 8E FE B1 96 46 76 41 1789 94 49 AF 84 2D 84 65 A7 F4 F7 2C DC A4 9D 84 F9 1791 External re-keying with a serial construction based on SHA-256 1792 ************************************************************** 1793 k = 256 1794 t = 128 1796 Initial key: 1797 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 1798 0F 0E 0D 0C 0B 0A 09 08 07 06 05 04 03 02 01 00 1800 label1: 1801 SHA2label1 1803 label2: 1804 SHA2label2 1806 K*_1: 1807 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 1808 0F 0E 0D 0C 0B 0A 09 08 07 06 05 04 03 02 01 00 1810 K^1: 1811 2D A8 D1 37 6C FD 52 7F F7 36 A4 E2 81 C6 0A 9B 1812 F3 8E 66 97 ED 70 4F B5 FB 10 33 CC EC EE D5 EC 1814 K*_2: 1815 14 65 5A D1 7C 19 86 24 9B D3 56 DF CC BE 73 6F 1816 52 62 4A 9D E3 CC 40 6D A9 48 DA 5C D0 68 8A 04 1818 K^2: 1819 2F EA 8D 57 2B EF B8 89 42 54 1B 8C 1B 3F 8D B1 1820 84 F9 56 C7 FE 01 11 99 1D FB 98 15 FE 65 85 CF 1822 K*_3: 1823 18 F0 B5 2A D2 45 E1 93 69 53 40 55 43 70 95 8D 1824 70 F0 20 8C DF B0 5D 67 CD 1B BF 96 37 D3 E3 EB 1826 K^3: 1827 53 C7 4E 79 AE BC D1 C8 24 04 BF F6 D7 B1 AC BF 1828 F9 C0 0E FB A8 B9 48 29 87 37 E1 BA E7 8F F7 92 1830 ... 1832 K*_126: 1833 A3 6D BF 02 AA 0B 42 4A F2 C0 46 52 68 8B C7 E6 1834 5E F1 62 C3 B3 2F DD EF E4 92 79 5D BB 45 0B CA 1836 K^126: 1837 6C 4B D6 22 DC 40 48 0F 29 C3 90 B8 E5 D7 A7 34 1838 23 4D 34 65 2C CE 4A 76 2C FE 2A 42 C8 5B FE 9A 1840 K*_127: 1841 84 5F 49 3D B8 13 1D 39 36 2B BE D3 74 8F 80 A1 1842 05 A7 07 37 BA 15 72 E0 73 49 C2 67 5D 0A 28 A1 1844 K^127: 1845 57 F0 BD 5A B8 2A F3 6B 87 33 CF F7 22 62 B4 D0 1846 F0 EE EF E1 50 74 E5 BA 13 C1 23 68 87 36 29 A2 1848 K*_128: 1849 52 F2 0F 56 5C 9C 56 84 AF 69 AD 45 EE B8 DA 4E 1850 7A A6 04 86 35 16 BA 98 E4 CB 46 D2 E8 9A C1 09 1852 K^128: 1853 9B DD 24 7D F3 25 4A 75 E0 22 68 25 68 DA 9D D5 1854 C1 6D 2D 2B 4F 3F 1F 2B 5E 99 82 7F 15 A1 4F A4 1856 CTR-ACPKM mode with AES-256 1857 *************************** 1858 k = 256 1859 n = 128 1860 c = 64 1861 N = 256 1863 Initial key K: 1864 88 99 AA BB CC DD EE FF 00 11 22 33 44 55 66 77 1865 FE DC BA 98 76 54 32 10 01 23 45 67 89 AB CD EF 1867 Plain text P: 1868 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 1869 00 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 1870 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 1871 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 1872 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 22 1873 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 22 33 1874 55 66 77 88 99 AA BB CC EE FF 0A 00 11 22 33 44 1876 ICN: 1877 12 34 56 78 90 AB CE F0 A1 B2 C3 D4 E5 F0 01 12 1878 23 34 45 56 67 78 89 90 12 13 14 15 16 17 18 19 1880 D_1: 1881 80 81 82 83 84 85 86 87 88 89 8A 8B 8C 8D 8E 8F 1883 D_2: 1884 90 91 92 93 94 95 96 97 98 99 9A 9B 9C 9D 9E 9F 1886 ACPKM's iteration 1 1887 Process block 1 1888 Input block (CTR): 1889 12 34 56 78 90 AB CE F0 00 00 00 00 00 00 00 00 1891 Output block (G): 1892 FD 7E F8 9A D9 7E A4 B8 8D B8 B5 1C 1C 9D 6D D0 1894 Plain text block: 1895 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 1897 Cipher text block: 1898 EC 5C CB DE 8C 18 D3 B8 72 56 68 D0 A7 37 F4 58 1900 Process block 2 1901 Input block (CTR): 1902 12 34 56 78 90 AB CE F0 00 00 00 00 00 00 00 01 1904 Output block (G): 1905 19 98 C5 71 76 37 FB 17 11 E4 48 F0 0C 0D 60 B2 1907 Plain text block: 1908 00 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 1910 Cipher text block: 1911 19 89 E7 42 32 62 9D 60 99 7D E2 4B C0 E3 9F B8 1913 Updated key: 1914 F6 80 D1 21 2F A4 3D F4 EC 3A 91 DE 2A B1 6F 1B 1915 36 B0 48 8A 4F C1 2E 09 98 D2 E4 A8 88 E8 4F 3D 1917 ACPKM's iteration 2 1918 Process block 1 1919 Input block (CTR): 1920 12 34 56 78 90 AB CE F0 00 00 00 00 00 00 00 02 1922 Output block (G): 1923 E4 88 89 4F B6 02 87 DB 77 5A 07 D9 2C 89 46 EA 1925 Plain text block: 1926 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 1928 Cipher text block: 1929 F5 AA BA 0B E3 64 F0 53 EE F0 BC 15 C2 76 4C EA 1931 Process block 2 1932 Input block (CTR): 1933 12 34 56 78 90 AB CE F0 00 00 00 00 00 00 00 03 1935 Output block (G): 1937 BC 4F 87 23 DB F0 91 50 DD B4 06 C3 1D A9 7C A4 1939 Plain text block: 1940 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 1942 Cipher text block: 1943 9E 7C C3 76 BD 87 19 C9 77 0F CA 2D E2 A3 7C B5 1945 Updated key: 1946 8E B9 7E 43 27 1A 42 F1 CA 8E E2 5F 5C C7 C8 3B 1947 1A CE 9E 5E D0 6A A5 3B 57 B9 6A CF 36 5D 24 B8 1949 ACPKM's iteration 3 1950 Process block 1 1951 Input block (CTR): 1952 12 34 56 78 90 AB CE F0 00 00 00 00 00 00 00 04 1954 Output block (G): 1955 68 6F 22 7D 8F B2 9C BD 05 C8 C3 7D 22 FE 3B B7 1957 Plain text block: 1958 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 22 1960 Cipher text block: 1961 5B 2B 77 1B F8 3A 05 17 BE 04 2D 82 28 FE 2A 95 1963 Process block 2 1964 Input block (CTR): 1965 12 34 56 78 90 AB CE F0 00 00 00 00 00 00 00 05 1967 Output block (G): 1968 C0 1B F9 7F 75 6E 12 2F 80 59 55 BD DE 2D 45 87 1970 Plain text block: 1971 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 22 33 1973 Cipher text block: 1974 84 4E 9F 08 FD F7 B8 94 4C B7 AA B7 DE 3C 67 B4 1976 Updated key: 1977 C5 71 6C C9 67 98 BC 2D 4A 17 87 B7 8A DF 94 AC 1978 E8 16 F8 0B DB BC AD 7D 60 78 12 9C 0C B4 02 F5 1980 ACPKM's iteration 4 1981 Process block 1 1982 Input block (CTR): 1983 12 34 56 78 90 AB CE F0 00 00 00 00 00 00 00 06 1984 Output block (G): 1985 03 DE 34 74 AB 9B 65 8A 3B 54 1E F8 BD 2B F4 7D 1987 Plain text block: 1988 55 66 77 88 99 AA BB CC EE FF 0A 00 11 22 33 44 1990 Cipher text block: 1991 56 B8 43 FC 32 31 DE 46 D5 AB 14 F8 AC 09 C7 39 1993 Cipher text C: 1994 EC 5C CB DE 8C 18 D3 B8 72 56 68 D0 A7 37 F4 58 1995 19 89 E7 42 32 62 9D 60 99 7D E2 4B C0 E3 9F B8 1996 F5 AA BA 0B E3 64 F0 53 EE F0 BC 15 C2 76 4C EA 1997 9E 7C C3 76 BD 87 19 C9 77 0F CA 2D E2 A3 7C B5 1998 5B 2B 77 1B F8 3A 05 17 BE 04 2D 82 28 FE 2A 95 1999 84 4E 9F 08 FD F7 B8 94 4C B7 AA B7 DE 3C 67 B4 2000 56 B8 43 FC 32 31 DE 46 D5 AB 14 F8 AC 09 C7 39 2002 OMAC-ACPKM-Master mode with AES-256 2003 *********************************** 2004 k = 256 2005 n = 128 2006 N = 256 2007 T* = 768 2009 Initial key K: 2010 88 99 AA BB CC DD EE FF 00 11 22 33 44 55 66 77 2011 FE DC BA 98 76 54 32 10 01 23 45 67 89 AB CD EF 2013 Plaintext M: 2014 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 2015 00 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 2016 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 2017 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 2018 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 22 2020 D_1: 2021 80 81 82 83 84 85 86 87 88 89 8A 8B 8C 8D 8E 8F 2023 D_2: 2024 90 91 92 93 94 95 96 97 98 99 9A 9B 9C 9D 9E 9F 2026 K^1|K^1_1 K^2|K^2_1 K^3|K^3_1 2027 9F 10 BB F1 3A 79 FB BD 4A 4C A8 64 C4 90 74 64 2028 39 FE 50 6D 4B 86 9B 21 03 A3 B6 A4 79 28 3C 60 2029 77 91 17 50 E0 D1 77 E5 9A 13 78 2B F1 89 08 D0 2030 AB 6B 59 EE 92 49 05 B3 AB C7 A4 E3 69 65 76 C3 2031 9D CC 66 42 0D FF 45 5B 21 F3 93 F0 D4 D6 6E 67 2032 BB 1B 06 0B 87 66 6D 08 7A 9D A7 49 55 C3 5B 48 2033 F2 EE 91 45 6B DC 3D E4 91 2C 87 C3 29 CF 31 A9 2034 2F 20 2E 5A C4 9A 2A 65 31 33 D6 74 8C 4F F9 12 2035 78 21 C7 C7 6C BD 79 63 56 AC F8 8E 69 6A 00 07 2037 OMAC's iteration 1 2038 K^1: 2039 9F 10 BB F1 3A 79 FB BD 4A 4C A8 64 C4 90 74 64 2040 39 FE 50 6D 4B 86 9B 21 03 A3 B6 A4 79 28 3C 60 2042 K^1_1: 2043 77 91 17 50 E0 D1 77 E5 9A 13 78 2B F1 89 08 D0 2045 Block number 1 2046 Plain text: 2047 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 2049 Input block: 2050 11 22 33 44 55 66 77 00 FF EE DD CC BB AA 99 88 2052 Output block: 2053 0B A5 89 BF 55 C1 15 42 53 08 89 76 A0 FE 24 3E 2055 Block number 2 2056 Plain text: 2057 00 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 2059 Input block: 2060 0B B4 AB 8C 11 94 73 35 DB 91 23 CD 6C 10 DB 34 2062 Output block: 2063 1C 53 DD A3 6D DC E1 17 ED 1F 14 09 D8 6A F3 2C 2065 OMAC's iteration 2 2066 K^2: 2067 AB 6B 59 EE 92 49 05 B3 AB C7 A4 E3 69 65 76 C3 2068 9D CC 66 42 0D FF 45 5B 21 F3 93 F0 D4 D6 6E 67 2070 K^2_1: 2071 BB 1B 06 0B 87 66 6D 08 7A 9D A7 49 55 C3 5B 48 2073 Block number 3 2074 Plain text: 2075 11 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 2076 Input block: 2077 0D 71 EE E7 38 BA 96 9F 74 B5 AF C5 36 95 F9 2C 2079 Output block: 2080 4E D4 BC A6 CE 6D 6D 16 F8 63 85 13 E0 48 59 75 2082 Block number 4 2083 Plain text: 2084 22 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 2086 Input block: 2087 6C E7 F8 F3 A8 1A E5 8F 52 D8 49 FD 1F 42 59 64 2089 Output block: 2090 B6 83 E3 96 FD 30 CD 46 79 C1 8B 24 03 82 1D 81 2092 OMAC's iteration 3 2093 K^3: 2094 F2 EE 91 45 6B DC 3D E4 91 2C 87 C3 29 CF 31 A9 2095 2F 20 2E 5A C4 9A 2A 65 31 33 D6 74 8C 4F F9 12 2097 K^3_1: 2098 78 21 C7 C7 6C BD 79 63 56 AC F8 8E 69 6A 00 07 2100 MSB1(K1) == 0 -> K2 = K1 << 1 2102 Last block 2103 K1: 2104 78 21 C7 C7 6C BD 79 63 56 AC F8 8E 69 6A 00 07 2106 K2: 2107 F0 43 8F 8E D9 7A F2 C6 AD 59 F1 1C D2 D4 00 0E 2109 Block number 5 2110 Plain text: 2111 33 44 55 66 77 88 99 AA BB CC EE FF 0A 00 11 22 2113 Using K1, src doesn't require padding 2114 Input block: 2115 FD E6 71 37 E6 05 2D 8F 94 A1 9D 55 60 E8 0C A4 2117 Output block: 2118 B3 AD B8 92 18 32 05 4C 09 21 E7 B8 08 CF A0 B8 2120 Message authentication code T: 2121 B3 AD B8 92 18 32 05 4C 09 21 E7 B8 08 CF A0 B8 2123 Appendix B. Contributors 2125 o Russ Housley 2126 Vigil Security, LLC 2127 housley@vigilsec.com 2129 o Evgeny Alekseev 2130 CryptoPro 2131 alekseev@cryptopro.ru 2133 o Ekaterina Smyshlyaeva 2134 CryptoPro 2135 ess@cryptopro.ru 2137 o Shay Gueron 2138 University of Haifa, Israel 2139 Intel Corporation, Israel Development Center, Israel 2140 shay.gueron@gmail.com 2142 o Daniel Fox Franke 2143 Akamai Technologies 2144 dfoxfranke@gmail.com 2146 o Lilia Ahmetzyanova 2147 CryptoPro 2148 lah@cryptopro.ru 2150 Appendix C. Acknowledgments 2152 We thank Mihir Bellare, Scott Fluhrer, Dorothy Cooley, Yoav Nir, Jim 2153 Schaad, Paul Hoffman and Dmitry Belyavsky for their useful comments. 2155 Author's Address 2157 Stanislav Smyshlyaev (editor) 2158 CryptoPro 2159 18, Suschevsky val 2160 Moscow 127018 2161 Russian Federation 2163 Phone: +7 (495) 995-48-20 2164 Email: svs@cryptopro.ru