idnits 2.17.1 draft-mcgrew-iv-gen-01.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 31, 2011) is 4554 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. 'CCM' -- Possible downref: Non-RFC (?) normative reference: ref. 'GCM' -- Possible downref: Non-RFC (?) normative reference: ref. 'MF00' ** Obsolete normative reference: RFC 1361 (Obsoleted by RFC 1769) ** Obsolete normative reference: RFC 3768 (Obsoleted by RFC 5798) Summary: 3 errors (**), 0 flaws (~~), 1 warning (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group D. McGrew 3 Internet-Draft Cisco Systems, Inc. 4 Intended status: Standards Track October 31, 2011 5 Expires: May 3, 2012 7 Generation of Deterministic Initialization Vectors (IVs) and Nonces 8 draft-mcgrew-iv-gen-01.txt 10 Abstract 12 Many cryptographic algorithms use deterministic IVs, including CTR, 13 GCM, CCM, GMAC. This type of IV is also called a (deterministic) 14 nonce. Deterministic IVs must be distinct, for each fixed key, to 15 guarantee the security of the algorithm. This note describes best 16 practices for the generation of such IVs, and summarizes how they are 17 generated and used in different protocols. Some problem areas are 18 highlighted, and test considerations are outlined. This note will be 19 useful to implementers of algorithms using deterministic IVs, and to 20 protocol or system designers using them. 22 Status of this Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at http://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on May 3, 2012. 39 Copyright Notice 41 Copyright (c) 2011 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (http://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 1.1. Conventions Used In This Document . . . . . . . . . . . . 3 58 2. Deterministic IVs in Algorithms . . . . . . . . . . . . . . . 4 59 3. Deterministic IVs in Protocols . . . . . . . . . . . . . . . . 5 60 4. Deterministic IVs in Standards . . . . . . . . . . . . . . . . 7 61 4.1. Recommended IV/Nonce Format . . . . . . . . . . . . . . . 7 62 4.2. Partially Implicit IV/Nonce Format . . . . . . . . . . . . 7 63 4.3. Unpredictable IV/Nonce Format . . . . . . . . . . . . . . 9 64 4.4. ESP . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 65 4.5. IKE . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 66 4.6. TLS . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 67 4.7. SSH . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 68 4.8. SRTP . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 69 4.9. Summary . . . . . . . . . . . . . . . . . . . . . . . . . 11 70 5. Implementation . . . . . . . . . . . . . . . . . . . . . . . . 13 71 5.1. IV Verification . . . . . . . . . . . . . . . . . . . . . 15 72 6. Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 73 6.1. Internal IV Generator . . . . . . . . . . . . . . . . . . 16 74 7. Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 75 7.1. Choice of Fixed-Distinct Field . . . . . . . . . . . . . . 17 76 7.2. Size of the Fixed-Distinct Field . . . . . . . . . . . . . 18 77 7.3. Security . . . . . . . . . . . . . . . . . . . . . . . . . 18 78 7.4. Bandwidth Use . . . . . . . . . . . . . . . . . . . . . . 19 79 8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 80 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 81 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 82 10.1. Normative References . . . . . . . . . . . . . . . . . . . 22 83 10.2. Informative References . . . . . . . . . . . . . . . . . . 22 84 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 25 86 1. Introduction 88 This note describes deterministic IVs and nonces and how they are 89 used in cryptographic algorithms (Section 2), then describes their 90 use in protocols (Section 3), and then their use in standards 91 (Section 4). Considerations for implementation (Section 5) and 92 testing (Section 6) are presented. Issues and potential problems are 93 discussed (Section 7). The focus is on network security protocols, 94 rather than on the security of data at rest, though many of the same 95 considerations apply in both areas. 97 1.1. Conventions Used In This Document 99 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 100 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 101 document are to be interpreted as described in [RFC2119]. 103 2. Deterministic IVs in Algorithms 105 Many cryptographic algorithms use Initialization Vectors, or IVs. An 106 IV is provided to an algorithm along with a message to be processed; 107 the IV initializes the algorithm to process the message. Typically, 108 there will be many IVs that are used with a single key. Some 109 algorithms, such as the Cipher Block Chaining (CBC) encryption mode, 110 require that the IVs that it uses are completely unpredictable. Such 111 IVs are typically called random IVs, and they must be generated by a 112 cryptographically strong random or pseudorandom process [RFC4086]. 114 Another type of IVs are deterministic IVs. These IVs are generated 115 by a deterministic process. The classic example of an algorithm that 116 uses a deterministic IV is counter (CTR) mode encryption [CTR]. An 117 algorithm that uses deterministic IVs requires that each IV provided 118 as input to the algorithm be distinct, for a fixed key. 120 A deterministic IV is sometimes called a nonce, or a deterministic 121 nonce. In cryptography, a nonce is a value that is used only once. 122 Many cryptographic protocols include a nonce in a message to enable 123 its receiver to recognize whether or not the message has been 124 previously received and processed. From the point of view of a 125 cryptographic algorithm that uses deterministic IVs, calling the IV a 126 nonce emphasizes the role of the IV in the overall system. Calling 127 that value a deterministic IV emphasizes its role in initializing the 128 algorithm to process a new message. Nonetheless, these are different 129 monikers for the same thing. 131 Authenticated Encryption is a symmetric encryption method that 132 provides for the authenticity and integrity of the data that it 133 protects, as well as its confidentiality [BN00] [R02]. An 134 authenticated encryption method that uses deterministic IVs will need 135 to make sure that the IVs used for encryption are distinct. However, 136 when performing the decryption operation, there is no need to ensure 137 that the IVs are distinct; the authenticated decryption operation 138 does not impose that requirement. The Authenticated Encryption 139 methods used in standards include Galois Counter Mode [GCM] and 140 Counter and CBC MAC mode [CCM]. 142 Some Message Authentication Code (MACs) use deterministic IVs, 143 including GMAC [GCM] and UMAC [RFC4118]. The considerations for 144 Authenticated Encryption also apply to these MAC algorithms: the IVs 145 used in the generation of an authentication tag must be distinct, but 146 there is no need to verify the distinctness of an IV prior to 147 inputting that IV to a tag verification algorithm. 149 3. Deterministic IVs in Protocols 151 The simplest way to implement a deterministic IV or nonce is to use a 152 counter: initialize an integer variable to zero, then each time that 153 an IV is needed, output the integer value, then store the incremented 154 value after checking to make sure that no integer overflow occurred, 155 so that no counter value is used twice. The simplicity of this 156 method has made it popular in practice, and recommended by standards. 158 The straightforward method of using a counter is not sufficient when 159 there are multiple encryption engines that are using the same 160 encryption key. This can be the case when encryption is distributed 161 across multiple processors, or across multiple software threads, 162 processes, or virtual machines. It can also happen in cases where a 163 protocol allows group keys. In these cases, some mechanism is needed 164 that ensures that IVs are distinct across all encryption engines that 165 use the same key. This is easily accomplished by including a fixed 166 field in the IV that is distinct for each distinct encrypter. (This 167 is detailed in Section 4.1.) 169 When a deterministic IV is used to encrypt and/or authenticate a 170 message, the receiver(s) of that message needs to know that IV in 171 order to decrypt it and/or verify its authenticity. A deterministic 172 IV can be sent along with a message, which makes it plain to the 173 receiver(s), or it can be left out of a message if the receiver(s) 174 have enough information to reconstruct it. Leaving the IV out of the 175 message reduces the amount of data that must be communicated, which 176 is advantageous. On the other hand, if the IV is included in the 177 message, the receiver(s) need not be aware of the method by which the 178 sender has chosen the IVs. 180 In practice, some protocols have split the difference between the 181 implicit method (in which the IV is absent and a receiver infers its 182 value) and the explicit method (in which the entire IV is included 183 with the message). The IV is constructed out of two fields: an 184 explicit field, which is conveyed along with the message, and an 185 implicit field, which is coordinated between the encrypter and the 186 decrypter using an "out of band" method. (This is detailed in 187 Section 4.2.) In most cases, the key management protocol that 188 establishes the encryption key can also establish the implicit field. 190 In a block cipher mode of operation that use deterministic IVs, the 191 inputs to each of the block cipher invocations during the encryption 192 process are determined by the IV provided to that process. It is 193 desirable to make the inputs to the block cipher unpredictable to an 194 attacker, to the extent that is possible, to make cryptanalytic 195 attacks more difficult and costly to attackers. This is true for 196 several types of attacks, including time-memory tradeoff attacks and 197 key collision attacks [MF00], which are generic attacks that can 198 reduce the cost of attacking any cipher, and cipher-specific attacks 199 such as integral cryptanalysis [KW02]. (It is worth noting that 200 counter mode gives an attacker exactly what they want for integral 201 cryptanalysis: a complete set of block cipher inputs that differ only 202 in some bit positions.) The cost of these attacks can be 203 significantly increased by making the deterministic IV unpredictable 204 to potential attackers. This security benefit is one motivation for 205 why the implicit field of the deterministic IV is kept secret in some 206 protocols. 208 It is not hard to adapt the simple methods for constructing 209 deterministic IVs so that they produce IVs that are unpredictable. 210 An easy way to do that is to have a secret value that is bitwise 211 exclusive-ored into the IV after all of the other processing is done. 212 (This is detailed in Section 4.3.) This secret value must be known 213 to all encrypters and decrypters, and be established via some "out of 214 band" mechanism. In practice, it is typically established by the key 215 management system. 217 4. Deterministic IVs in Standards 219 Many different protocols use deterministic IVs, including ESP 220 [RFC4106], TLS [RFC5288], SSH [RFC5647], and SRTP [RFC3711]. The way 221 that these protocols define their IVs is outlined in this section and 222 is summarized in Table 1. 224 4.1. Recommended IV/Nonce Format 226 RFC 5116 defines the interface for Authenticated Encryption, which is 227 the most common use of deterministic IVs at present. That RFC 228 recommends an IV format, which is used by ESP, IKE, TLS, and SSH. 229 The recommended format has a total length of 12 octets, and consists 230 of a Fixed Field and a Counter field, and is structured as in 231 Figure 1. (See Section 3.2 of [RFC5116] for the precise normative 232 description.) 234 +-------------------------------+------------------------+ 235 | Fixed | Counter | 236 +-------------------------------+------------------------+ 238 Figure 1: Recommended IV/Nonce format. 240 Fixed Counter 241 <------><--------------> 242 1st 5DAD87F80000000000000001 243 2nd 5DAD87F80000000000000002 244 3rd 5DAD87F80000000000000003 245 4th 5DAD87F80000000000000004 246 5th 5DAD87F80000000000000005 247 ... ... 249 Figure 2: An example output of recommended IV/nonce format, showing 250 successive IVs where the Fixed field is 5DAD87F8. 252 The Fixed field remains constant for all nonces that are generated 253 for a given encryption device. If different devices are performing 254 encryption with a single key, then each distinct device MUST use a 255 distinct Fixed field, to ensure the uniqueness of the nonces. 257 This format is suggested, but not required, by [CTR]. 259 4.2. Partially Implicit IV/Nonce Format 261 The case in which the recommended format is used with Partially 262 Implicit Nonces has further details. In that case, the IV is 263 structured as in Figure 3. 265 +--------------+----------------+------------------------+ 266 | Fixed-Common | Fixed-Distinct | Counter | 267 +--------------+----------------+------------------------+ 268 <- implicit -> <--------------- explicit --------------> 270 Figure 3: Partially implicit IV/Nonce format 272 Fixed Fixed 273 Common Distinct Counter 274 <------><--><----------> 275 1st 5DAD87F81E0E000000000001 276 2nd 5DAD87F81E0E000000000002 277 3rd 5DAD87F81E0E000000000003 278 4th 5DAD87F81E0E000000000004 279 5th 5DAD87F81E0E000000000005 280 ... ... 282 Figure 4: An example output of Partially Implicit IV/Nonce format, 283 showing successive IVs where the Fixed-Common field is 5DAD87F8 and 284 the Fixed-Distinct field is 1E0E. 286 The portion of the IV that is stored or sent with the ciphertext is 287 the explicit part. The portion of the IV that is not sent with the 288 ciphertext is the implicit part. 290 The Fixed field is divided into two sub-fields: a Fixed-Common field 291 and a Fixed-Distinct field. 293 If different devices are performing encryption with a single key, 294 then each distinct device MUST use a distinct Fixed-Distinct field. 295 The Fixed-Common field is common to all IVs. The Fixed-Distinct 296 field and the Counter field MUST be in the explicit part of the IV. 297 The Fixed-Common field MAY be in the implicit part of the IV. 299 ESP, IKE, TLS, and SSH conform to the RFC 5116 Partially Implicit 300 Nonces format, though they do not require that the "Counter" field 301 actually be an integer counter (instead, "anything that guarantees 302 uniqueness can be used"). 304 The partially implicit format can save on bandwidth or data storage 305 requirements, because it avoids sending or storing the implicit part 306 of the IV. However, it limits the number of IVs that can be 307 generated, because the implicit part is fixed, and it adds complexity 308 to the system, by making the system coordinate the implicit part 309 through out-of-band means. Thus, new protocol and system designs 310 SHOULD NOT use the partially implicit format unless a review of all 311 of the issues shows that the bandwidth or storage savings are worth 312 the complexity. (An alternative strategy for bandwidth savings is 313 discussed in Section 7.4.) 315 4.3. Unpredictable IV/Nonce Format 317 This method is shown in Figure 5, in which the symbol (+) denotes the 318 bitwise exclusive-or operation. (Here the Fixed field consists of 319 the Fixed-Common field followed by the Fixed-Distinct field.) This 320 format uses a Randomizer, which is an octet string that is combined 321 with the other fields to make the IVs unpredictable. The length of 322 the Randomizer must be no greater than the sum of the lengths of the 323 Fixed and Counter fields. 325 The next IV in sequence is computed as follows. The Fixed field and 326 the Counter field are concatenated. If the length of the Randomizer 327 is less than the combined length of the Fixed and Counter fields, 328 then the Randomizer is padded on the right with enough zeros so that 329 the padded value has a length that exactly matches that of the Fixed 330 and Counter fields together. The concatenated Fixed and Counter 331 field is bitwise exclusive-ored with the padded Randomizer, and the 332 resulting value is the IV. The Counter is incremented, treating it 333 as an unsigned integer with the most significant byte on the left, 334 and the stored Counter field is set to the incremented value. Then 335 the IV is returned. This is the method used by SRTP [RFC3711], 336 wherein the Randomizer field is called "Salt". (We use the term 337 Randomizer instead of Salt, because the latter term is used with 338 slightly different meanings in some other specifications, such as 339 [RFC4309].) 341 +-----------------+-----------------+ 342 | Fixed | Counter |---+ 343 +-----------------+-----------------+ | 344 | 345 +-----------------------------------+ v 346 | Randomizer |->(+) 347 +-----------------------------------+ | 348 | 349 +-----------------------------------+ | 350 | Initialization Vector |<--+ 351 +-----------------------------------+ 353 Figure 5: Unpredictable IV/Nonce Format. 355 Fixed Fixed 356 Common Distinct Counter IV 357 <--><------><----------> <----------------------> 358 1st 000097B4AE8F000000000001 0C81C77A5DDB678EE16FA2D0 359 2nd 000097B4AE8F000000000002 0C81C77A5DDB678EE16FA2D3 360 3rd 000097B4AE8F000000000003 0C81C77A5DDB678EE16FA2D2 361 4th 000097B4AE8F000000000004 0C81C77A5DDB678EE16FA2D5 362 5th 000097B4AE8F000000000005 0C81C77A5DDB678EE16FA2D4 363 ... ... 365 Figure 6: An example output of the Unpredictable IV/nonce format, 366 showing successive IVs where the Fixed-Distinct field has the value 367 97B4AE8F and the Salt has value 0C8150CEF354678EE16FA2D1. 369 4.4. ESP 371 In the IP Encapsulating Security Payload (ESP) 372 [RFC3686][RFC4106][RFC4309] the implicit and explicit parts are four 373 and eight bytes long, respectively. The exception is [RFC4309], for 374 which the implicit part is three bytes in length. The Fixed-Common 375 field is four bytes, and its value is set by the Internet Key 376 Exchange (IKE). (This field is named inconsistently, being called 377 Nonce in [RFC3686], and Salt in [RFC4106] and [RFC4309].) When ESP 378 is used with IKE, there is exactly one entity performing encryption, 379 and the Fixed-Distinct part is usually not present (or equivalently, 380 is has a length of zero bytes). When ESP is used with a group key 381 management protocol such as GDOI, the Fixed-Distinct field may be two 382 or four bytes in length, and the value of the Fixed-Distinct field to 383 be used by an encrypter is established by the group key management 384 protocol [RFC6054]. The case in which IKE is used with ESP and there 385 are multiple encryption engines is not specifically addressed by the 386 standards, but it can be handled by the use of a nonzero Fixed- 387 Distinct field. 389 4.5. IKE 391 The Internet Key Exchange (IKE) [RFC5282] uses the recommended IV/ 392 nonce format. The Fixed-Common field is four bytes in length, and 393 its value is set from the IKE Keying Material. The Fixed-Distinct 394 part is usually zero bytes, but it may be any number of bytes if 395 there are multiple encrypters in use. 397 4.6. TLS 399 In Transport Layer Security (TLS) [RFC5288], the Fixed-Common field 400 is four bytes in length, and the Fixed-Distinct part is usually zero 401 bytes, but it may be any number of bytes when there are multiple 402 encrypters in use. Section 6.2 of [RFC5288] gives an example of TLS 403 deterministic IV formation. 405 4.7. SSH 407 In the Secure Shell (SSH) protocol [RFC5647] the Fixed-Common field 408 is not present, the Fixed-Distinct field is four bytes long, and the 409 Counter field is eight bytes in length. The implicit part is not 410 present, and the explicit part contains the entire 12 byte IV. 412 4.8. SRTP 414 In the Secure Real-time Transport Protocol (SRTP) [RFC3711] and 415 draft-ietf-avt-srtp-aes-gcm-01 the IV formation is a bit more complex 416 than RFC 5116. It is essentially RFC 5116 format with the additional 417 step of performing a bitwise exclusive-or operation with a Randomizer 418 value. (This step provides additional strength against cryptographic 419 attacks that rely on predicting all or most of the IV.) 420 draft-ietf-avt-srtp-aes-gcm-01 uses a 12-byte IV, though RFC 3711 421 uses a 14-byte IV. 423 4.9. Summary 425 The following table gives a synopsis of how standard protocols use 426 deterministic IVs. 428 +-----------+---------+--------------+----------------+-------------+ 429 | Protocol | IV | Fixed-Common | Fixed-Distinct | Counter | 430 | | (bytes) | (bytes) | (bytes) | (bytes) | 431 +-----------+---------+--------------+----------------+-------------+ 432 | ESP | 12 | 4 | 0,1,2,[4] | 8,7,6,[4] | 433 | | | | | | 434 | | | Not on wire | On wire | On wire | 435 | | | | | | 436 | | | Set by IKE | | | 437 | | | | | | 438 | ESP | 11 | 3 | 0,1,2,[4] | 8,7,6,[4] | 439 | | | | | | 440 | [RFC4309] | | Not on wire | On wire | On wire | 441 | | | | | | 442 | | | Set by IKE | | | 443 | | | | | | 444 | IKE | 12 | 4 | Unspecified | Unspecified | 445 | | | | | | 446 | | | Not on wire | On wire | On wire | 447 | | | | | | 448 | | | Set from KM | | | 449 | | | | | | 450 | TLS | 12 | 4 | 0-8 | 8-0 | 451 | | | | | | 452 | | | Not on wire | On wire | On wire | 453 | | | | | | 454 | | | Set by TLS | | | 455 | | | | | | 456 | SSH | 12 | 0 | 4 | 8 | 457 | | | | | | 458 | | | | On wire | On wire | 459 | | | | | | 460 | | | | Unspecified | | 461 | | | | | | 462 | SRTP-CTR | 14 | 4 | 4 | 6 | 463 | | | | | | 464 | | | Not on wire | Not on wire | Not on wire | 465 | | | | | | 466 | | | Set by KM | | | 467 | | | | | | 468 | SRTP-GCM | 12 | 2 | 4 | 6 | 469 | | | | | | 470 | | | Not on wire | Not on wire | Not on wire | 471 | | | | | | 472 | | | Set by KM | | | 473 +-----------+---------+--------------+----------------+-------------+ 475 Table 1: Fields in Deterministic IVs, by Protocol. 477 5. Implementation 479 A cryptographic implementation typically consists of a self-contained 480 and testable module that implements all of the essential 481 functionality that it needs. This functionality should include the 482 generation of deterministic IVs. 484 Because of the variety of ways in which IVs are formed in different 485 protocols, implementers may be tempted to put the generation of the 486 IV under the control of the protocol implementation. That is, from 487 the point of view of the application making use of the encryption 488 algorithm, the IV is an input to that algorithm, as shown in 489 Figure 7. Regardless, it is not good for security to have the IV be 490 generated outside the crypto module. It is possible to implement an 491 IV Generator that can be used with all of the protocols outlined 492 above and use it inside of a cryptographic module. In the following 493 we outline how that can be done. 495 +----------------------+ 496 | +--------------+ | IV +-------------+ 497 | | |<-------------------| | 498 | | Encryption | | Plaintext | | 499 | | Algorithm |<-------------------| Application | 500 | | | | Ciphertext | | 501 | | |------------------->| | 502 | +--------------+ | +-------------+ 503 | | 504 | Cryptographic Module | 505 +----------------------+ 507 Figure 7: Architecture with IV generation outside of the 508 cryptographic module, showing how the IV is entered into the 509 cryptographic module during an encryption operation. 511 The internal IV generator architecture is illustrated in Figure 8. 512 The cryptographic module contains an IV Generator sub-module that 513 understands the IV formats outlined in Section 3. To initialize the 514 IV generator, the application inputs the parameter values to be used. 515 Once initialized, the IV generator will produce successive IVs on 516 request, and send these values to the algorithm and to the calling 517 application. The encryption algorithm will need the entire IV, but 518 if the partially implicit IV format is in use, only the explicit part 519 of the IV needs to be provided to the application. The IV generator 520 is responsible for ensuring the distinctness of all of the IVs that 521 it generates. 523 +----------------------+ 524 | +--------------+ | 525 | | IV Generator |-----------+ 526 | +--------------+ | | IV (explicit part) 527 | | IV | | 528 | v | | 529 | +--------------+ | | +-------------+ 530 | | | +------->| | 531 | | Encryption | | Plaintext | | 532 | | Algorithm |<-------------------| Application | 533 | | | | Ciphertext | | 534 | | |------------------->| | 535 | +--------------+ | +-------------+ 536 | | 537 | Cryptographic Module | 538 +----------------------+ 540 Figure 8: Architecture with IV generation inside of the cryptographic 541 module, showing how the IV is generated internally during an 542 encryption operation. 544 More formally, an IV generator supports the operations of Initialize 545 and Output Next IV. The Initialize operation prepares an IV 546 Generator for use with a particular set of parameters. It takes the 547 following inputs: 549 A nonnegative integer indicating the number of bytes in the IV to 550 be generated. All of the IVs output from the Generator will have 551 the same length. 553 An octet string indicating the Fixed part of the IV; this value 554 will be used as the initial part in each IV that is generated. 556 A nonnegative integer indicating the number of bytes in the Fixed 557 part of the IV. This value must be no greater than the number of 558 bytes in the IV. 560 An octet string indicating the salt value to be exclusive-ored 561 with the other fields of the IV. If no salt is to be used when 562 Generating IVs, then this parameter must not be present. 564 A nonnegative integer indicating the number of bytes in the salt 565 value. If no salt value is used, this parameter must be zero. If 566 a salt value is used, this parameter must be no greater than the 567 number of bytes in the IV. 569 The Fixed field consists of the Fixed-Common field, followed by the 570 Fixed-Distinct field. The Fixed field and Salt field are stored when 571 the IV generator is initialized; at that time, the Counter field is 572 initialized to zero. The length of the Counter field is equal to the 573 length of the IV less the length of the Fixed field. If the Salt 574 field is shorter than the IV, then it is padded on the right with 575 zeroes. If no Salt is to be used, this is conceptually equivalent to 576 having a Salt value that is the all-zero value. 578 The Output Next IV operation returns the next IV in sequence, or it 579 returns an indication that there are no more IVs that are available. 580 During that operation, the IV is computed as follows. First, the 581 stored Counter value MUST be checked to determine if an IV can be 582 generated; an IV can only be generated if the value of Counter + 1 583 does not exceed the maximum allowable value of the Counter field. If 584 an IV cannot be generated, then the operation returns an indication 585 that there are no more IVs that are available. Otherwise, the Fixed 586 field and the Counter field are concatenated, then they are bitwise 587 exclusive-ored with the Salt field, and the resulting value is the 588 IV. The Counter is incremented, treating it as an unsigned integer 589 with the most significant byte on the left, and the stored Counter 590 field is set to the incremented value. Then the IV is returned. 592 The IV generator should also be able to output the length of the 593 explicit field, so that an algorithm can output only the explicit 594 part, when that is appropriate. 596 5.1. IV Verification 598 In some protocols, the IV is constructed out of fields in the 599 protocol in such a way that it is difficult to have the IVs generated 600 inside of the cryptographic module, without requiring that module to 601 contain protocol-specific logic. In this case, assurance of the 602 uniqueness of IVs can be provided by having the IVs be generated by 603 the protocol, but checked by the cryptographic module. 605 This approach is taken by many implementations of Secure RTP 606 [RFC3711]. The IV in that protocol is constructed in a way that 607 incorporates a sender identifier (the SSRC field) and the protocol's 608 sequence number. To check the sequence number for uniqueness, an 609 implementation can make use of the anti-replay checking that the 610 protocol uses to check inbound packet. An encrypter can use this 611 approach as well, to make sure that the sequence number used to 612 construct the IV is unique. (Of course, it is necessary to have an 613 IV construction method such that the uniqueness of the sequence 614 number ensures the uniqueness of the IV.) Since many cryptographic 615 protocols contain a function to perform anti-replay check based on a 616 sequence number, this is a convenient strategy. 618 6. Testing 620 The testing of a cryptographic module is an important step in 621 assessing the assurance of that module. The IV Generator defined in 622 Section 5 can be tested by an external system to verify that it is 623 operating correctly. 625 The recommended IV format can be tested by verifying that all of the 626 IVs are distinct. There are many ways that this can be done; for 627 instance, the command "sort | uniq -d" on POSIX systems can be used 628 to detect repeated lines in a file. 630 An important aspect of an IV generator is that, when it has an N byte 631 Counter field, it should not generate more than (256)^N IVs. This 632 property should be tested for small values of N (at least 1, 2, and 633 3), by calling the Output Next IV operation M times, for some M > 634 (256)^N. Note that some implementations may produce fewer than 635 (256)^N IVs, e.g. due to their handling of the all-zero IV. That 636 would not affect security. 638 6.1. Internal IV Generator 640 When a cryptographic module uses an internal IV generator, only the 641 explicit part of the IV needs to be output from the module. It is 642 possible to test this use of the IV generator by interacting with an 643 encryption algorithm that uses it (or an Authenticated Encryption 644 algorithm, or a MAC). 646 The encryption operation takes as input a plaintext, and returns a 647 ciphertext and the explicit part of the IV. To test that the IV 648 generator is working properly, call the encryption operation 649 repeatedly, each time with the same plaintext value, and verify that 650 1) all of the ciphertexts returned are distinct, and 2) all of the 651 explicit parts that are returned are distinct. The plaintext must be 652 at least 32 bytes long, in order to avoid false positives. 654 7. Issues 656 7.1. Choice of Fixed-Distinct Field 658 When considering what data should go into a Fixed-Distinct field, it 659 is tempting to use system values such as network addresses because 660 they appear to meet the criteria of uniqueness. However, there are 661 several significant problems with this idea. System values that are 662 taken from outside the cryptographic module may not actually be 663 distinct, especially if an attacker can influence the system. System 664 values can also change over time; even if they are actually distinct, 665 they may not be fixed. Lastly, the cryptographic system should have 666 the freedom to put distinct data into the Fixed-Distinct fields, so 667 that it can accommodate multiple encryption engines when they occur. 669 Internet Protocol (IP) version four addresses are four bytes in 670 length, and thus can fit into the Fixed-Distinct field of a 12-byte 671 IV. However, an IP address is highly unsuitable for this purpose. 672 Most networked devices use dynamically assigned IP addresses, with 673 address assignment via an automatic configuration protocol such as 674 the Dynamic Host Configuration Protocol (DHCP). The addresses are 675 determined by an external system and are communicated over an 676 insecure protocol; furthermore, a DHCP address is only valid for a 677 particular period of time, and may change after that lease has 678 expired. Even when an automatic configuration protocol is not in 679 use, IP addresses are determined by the networking subsystem, and are 680 not under the control of the cryptographic module. Network Address 681 Translation (NAT, [RFC1361]) is commonly used to modify the IP 682 addresses of packets as they traverse a network boundary, for 683 instance between a private address space [RFC1918] and the Internet. 684 Because of NAT, the IP address associated with a particular device 685 will not be consistent throughout the network. Multiple devices can 686 use the same addresses; this technique is utilized in order to 687 provide redundancy or load sharing (see the Virtual Router Redundancy 688 Protocol [RFC3768] for instance). Lastly, IPv4 is currently being 689 replaced by version six of that protocol. IPv6 addresses are sixteen 690 bytes long; this is too long for inclusion in an IV, and the 691 coexistence of both versions on the Internet is likely to increase 692 the use of NAT for protocol translation [RFC6146]. In summary, IP 693 addresses are neither fixed nor distinct, and should not be used in a 694 Fixed-Distinct field. 696 Similar considerations hold for link layer addresses, Domain Name 697 System (DNS) names, and TCP, UDP, and SCTP ports. 699 A much better solution is to have the Fixed-Distinct field be 700 assigned by the security system. For instance, if a cryptographic 701 module has multiple encrypters, it can assign that field 702 appropriately for each encrypter. 704 7.2. Size of the Fixed-Distinct Field 706 Deterministic IVs typically have an explicit part that is eight bytes 707 in length. (This size is natural to use with a block cipher that has 708 a 16 byte block width, because no more than (256)^8 packets can be 709 encrypted under a single key without encountering security 710 degradation due to the birthday paradox.) Because the Fixed-Distinct 711 field must appear in the explicit part, larger Fixed-Distinct fields 712 will reduce the number of IVs that can be generated. This can be 713 problematic, especially for high throughput situations. For 714 instance, the ESP protocol allows for up to 2^64 packets to be 715 encrypted under a single key, so it is desirable to use a Counter 716 field that is close to eight bytes in length; this is why [RFC6054] 717 encourages the use of short values in the Fixed-Distinct field. 718 Table 2 presents the lifetimes of a single key that can encrypt 2^32 719 packets, i.e. a key being used with a four-byte Counter field. At 720 high data rates, keys must be replaced quickly. 722 +----------+-------------------+------------------+-----------------+ 723 | | Best Case | Typical Case | Worst Case | 724 +----------+-------------------+------------------+-----------------+ 725 | | 9000 byte packets | 850 byte packets | 64 byte packets | 726 | | | | | 727 | 1 Gbps | 3 days | 8.6 hours | 66 minutes | 728 | | | | | 729 | 10 Gbps | 8.6 hours | 52 minutes | 6.6 minutes | 730 | | | | | 731 | 40 Gbps | 22 minutes | 13 minutes | 1.6 minutes | 732 | | | | | 733 | 100 Gbps | 8.9 minutes | 5.2 minutes | 0.7 minutes | 734 +----------+-------------------+------------------+-----------------+ 736 Table 2: Key Lifetimes with a four-byte Counter field 738 7.3. Security 740 As long as each deterministic IV is distinct, for each key, then 741 security is assured. However, when deterministic IVs are not 742 distinct, security suffers. 744 The number of deterministic IVs is limited, regardless of how those 745 IVs are generated. What does an encrypter do when no more IVs are 746 available? It should retire the key that it is currently using, and 747 establish another one. This is the reason that the IETF Guidelines 748 for Cryptographic Key Management [RFC4107] require that automated key 749 management be used for algorithms with deterministic IVs. For 750 network security protocols, this has proven to be an effective 751 strategy. 753 Particular care must be taken in Virtual Machine (VM) environments, 754 because the VM cloning and rollback processes can cause inadvertent 755 re-use of deterministic IVs. This is just one of many security 756 problems that can result from uncritical application of VM mechanisms 757 when cryptography is in use [GR05]. 759 7.4. Bandwidth Use 761 An implicit or partially implicit IV uses less bandwidth than a full- 762 sized IV. But as noted above, the (partially) implicit IV format 763 reduces the number of IVs that can be generated and adds complexity 764 to the system. 766 An alternative approach to bandwidth savings in a protocol design is 767 to use a predictable IV format, such as that of Section 4.1, and then 768 apply header compression to the IV. Header compression is often used 769 on bandwidth-constrained links, and it can be applied to encrypted 770 packets [RFC3095]. The format of Section 4.1 can easily be handled 771 by header compression. This approach has several benefits: it makes 772 IV generation simpler, it allows bandwidth savings for environments 773 in which it matters while putting the complexity burden onto the 774 systems that opt to realize those savings, and it increases the 775 number of IVs that can be used. Specifications that use this design 776 alternative SHOULD require the use of the IV format in Section 4.1. 778 8. Security Considerations 780 Cryptographic algorithms that rely on deterministic IVs or nonces 781 must ensure the uniqueness of those values. The recommendations in 782 this note aim to help implementers achieve that goal. 784 Implementations should use the nonce formats described in Section 3. 785 The way in which these formats are used in standards is summarized in 786 Table 1. 788 Implementations should use the internal IV generator described in 789 Section 5. 791 Almost all cryptographic systems can implement counter-based 792 deterministic IVs. In many cases, it is straightforward to generate 793 deterministic IVs associated with a short-term key in use by a single 794 encrypter, as in a typical point-to-point protocol. Complications 795 can arise, however, when there are multiple encrypters, or when a key 796 is used for an extended period of time. Cryptographic systems that 797 cannot ensure IV distinctness should not use deterministic IVs, and 798 should instead use a misuse-resistant mode of operation such as the 799 Synthetic Initialization Vector (SIV) Authenticated Encryption mode 800 of operation [RFC5295], or a randomized algorithm such as the CBC 801 mode of operation (though an additional authentication mechanism must 802 be used with that option). If authentication but not encryption is 803 required, then it is possible to use an algorithm that does not 804 require an IV, such as HMAC [RFC2104]. 806 9. Acknowledgments 808 Thanks to Greg Zaverucha and Peter Gutmann for comments. 810 10. References 812 10.1. Normative References 814 [CCM] Dworkin, M., "NIST Special Publication 800-38C: The CCM 815 Mode for Authentication and Confidentiality", U.S. 816 National Institute of Standards and Technology http:// 817 csrc.nist.gov/publications/nistpubs/800-38C/SP800-38C.pdf. 819 [GCM] Dworkin, M., "NIST Special Publication 800-38D: 820 Recommendation for Block Cipher Modes of Operation: 821 Galois/Counter Mode (GCM) and GMAC.", U.S. National 822 Institute of Standards and Technology http:// 823 csrc.nist.gov/publications/nistpubs/800-38D/SP800-38D.pdf. 825 [MF00] McGrew, D. and S. Fluhrer, "Attacks on Additive Encryption 826 of Redundant Plaintext and Implications on Internet 827 Security", Proceedings of the Seventh Annual Workshop on 828 Selected Areas in Cryptography (SAC 2000) Spinger-Verlag. 830 [RFC1361] Mills, D., "Simple Network Time Protocol (SNTP)", 831 RFC 1361, August 1992. 833 [RFC1918] Rekhter, Y., Moskowitz, R., Karrenberg, D., Groot, G., and 834 E. Lear, "Address Allocation for Private Internets", 835 BCP 5, RFC 1918, February 1996. 837 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 838 Requirement Levels", BCP 14, RFC 2119, March 1997. 840 [RFC3768] Hinden, R., "Virtual Router Redundancy Protocol (VRRP)", 841 RFC 3768, April 2004. 843 10.2. Informative References 845 [BN00] Bellare, M. and C. Namprempre, "Authenticated encryption: 846 Relations among notions and analysis of the generic 847 composition paradigm", Proceedings of ASIACRYPT 2000, 848 Springer-Verlag, LNCS 1976, pp. 531-545 http:// 849 www-cse.ucsd.edu/users/mihir/papers/oem.html. 851 [CTR] Dworkin, M., "NIST Special Publication 800-38: 852 Recommendation for Block Cipher Modes of Operation", U.S. 853 National Institute of Standards and Technology http:// 854 csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf. 856 [GR05] Garfinkel, T. and M. Rosenblum, "When Virtual is Harder 857 than Real: Security Challenges in Virtual Machine Based 858 Computing Environments", Proceedings of the 10th Workshop 859 on Hot Topics in Operating Systems http:// 860 www.stanford.edu/~talg/papers/HOTOS05/ 861 virtual-harder-hotos05.pdf. 863 [KW02] Knudsen, L. and D. Wagner, "Integral Cryptanalysis", 9th 864 International Workshop on Fast Software Encryption (FSE 865 '02) http://eprint.iacr.org/2004/193, December 2001. 867 [R02] Rogaway, P., "Authenticated encryption with Associated- 868 Data", ACM Conference on Computer and Communication 869 Security (CCS'02), pp. 98-107, ACM Press, 870 2002. http://www.cs.ucdavis.edu/~rogaway/papers/ad.html. 872 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 873 Hashing for Message Authentication", RFC 2104, 874 February 1997. 876 [RFC3095] Bormann, C., Burmeister, C., Degermark, M., Fukushima, H., 877 Hannu, H., Jonsson, L-E., Hakenberg, R., Koren, T., Le, 878 K., Liu, Z., Martensson, A., Miyazaki, A., Svanbro, K., 879 Wiebke, T., Yoshimura, T., and H. Zheng, "RObust Header 880 Compression (ROHC): Framework and four profiles: RTP, UDP, 881 ESP, and uncompressed", RFC 3095, July 2001. 883 [RFC3686] Housley, R., "Using Advanced Encryption Standard (AES) 884 Counter Mode With IPsec Encapsulating Security Payload 885 (ESP)", RFC 3686, January 2004. 887 [RFC3711] Baugher, M., McGrew, D., Naslund, M., Carrara, E., and K. 888 Norrman, "The Secure Real-time Transport Protocol (SRTP)", 889 RFC 3711, March 2004. 891 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness 892 Requirements for Security", BCP 106, RFC 4086, June 2005. 894 [RFC4106] Viega, J. and D. McGrew, "The Use of Galois/Counter Mode 895 (GCM) in IPsec Encapsulating Security Payload (ESP)", 896 RFC 4106, June 2005. 898 [RFC4107] Bellovin, S. and R. Housley, "Guidelines for Cryptographic 899 Key Management", BCP 107, RFC 4107, June 2005. 901 [RFC4118] Yang, L., Zerfos, P., and E. Sadot, "Architecture Taxonomy 902 for Control and Provisioning of Wireless Access Points 903 (CAPWAP)", RFC 4118, June 2005. 905 [RFC4309] Housley, R., "Using Advanced Encryption Standard (AES) CCM 906 Mode with IPsec Encapsulating Security Payload (ESP)", 907 RFC 4309, December 2005. 909 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated 910 Encryption", RFC 5116, January 2008. 912 [RFC5282] Black, D. and D. McGrew, "Using Authenticated Encryption 913 Algorithms with the Encrypted Payload of the Internet Key 914 Exchange version 2 (IKEv2) Protocol", RFC 5282, 915 August 2008. 917 [RFC5288] Salowey, J., Choudhury, A., and D. McGrew, "AES Galois 918 Counter Mode (GCM) Cipher Suites for TLS", RFC 5288, 919 August 2008. 921 [RFC5295] Salowey, J., Dondeti, L., Narayanan, V., and M. Nakhjiri, 922 "Specification for the Derivation of Root Keys from an 923 Extended Master Session Key (EMSK)", RFC 5295, 924 August 2008. 926 [RFC5647] Igoe, K. and J. Solinas, "AES Galois Counter Mode for the 927 Secure Shell Transport Layer Protocol", RFC 5647, 928 August 2009. 930 [RFC6054] McGrew, D. and B. Weis, "Using Counter Modes with 931 Encapsulating Security Payload (ESP) and Authentication 932 Header (AH) to Protect Group Traffic", RFC 6054, 933 November 2010. 935 [RFC6146] Bagnulo, M., Matthews, P., and I. van Beijnum, "Stateful 936 NAT64: Network Address and Protocol Translation from IPv6 937 Clients to IPv4 Servers", RFC 6146, April 2011. 939 Author's Address 941 David A. McGrew 942 Cisco Systems, Inc. 943 510 McCarthy Blvd. 944 Milpitas, CA 95035 945 US 947 Phone: (408) 525 8651 948 Email: mcgrew@cisco.com 949 URI: http://www.mindspring.com/~dmcgrew/dam.htm