idnits 2.17.1 draft-mcgrew-iv-gen-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 4, 2011) is 4673 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 July 4, 2011 5 Expires: January 5, 2012 7 Generation of Deterministic Initialization Vectors (IVs) and Nonces 8 draft-mcgrew-iv-gen-00.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 January 5, 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 . . . . . . . . . . . . . . 8 64 4.4. ESP . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 65 4.5. IKE . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 66 4.6. TLS . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 67 4.7. SSH . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 68 4.8. SRTP . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 69 4.9. Summary . . . . . . . . . . . . . . . . . . . . . . . . . 11 70 5. Imlementation . . . . . . . . . . . . . . . . . . . . . . . . 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 8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 79 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 80 9.1. Normative References . . . . . . . . . . . . . . . . . . . 21 81 9.2. Informative References . . . . . . . . . . . . . . . . . . 21 82 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 24 84 1. Introduction 86 This note describes deterministic IVs and nonces and how they are 87 used in cryptographic algorithms (Section 2), then describes their 88 use in protocols (Section 3), and then their use in standards 89 (Section 4). Considerations for implementation (Section 5) and 90 testing (Section 6) are presented. Issues and potential problems are 91 discussed (Section 7). The focus is on network security protocols, 92 rather than on the security of data at rest, though many of the same 93 considerations apply in both areas. 95 1.1. Conventions Used In This Document 97 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 98 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 99 document are to be interpreted as described in [RFC2119]. 101 2. Deterministic IVs in Algorithms 103 Many cryptographic algorithms use Initialization Vectors, or IVs. An 104 IV is provided to an algorithm along with a message to be processed; 105 the IV initializes the algorithm to process the message. Typically, 106 there will be many IVs that are used with a single key. Some 107 algorithms, such as the Cipher Block Chaining (CBC) encryption mode, 108 require that the IVs that it uses are completely unpredictable. Such 109 IVs are typically called random IVs, and they must be generated by a 110 cryptographically strong random or pseudorandom process [RFC4086]. 112 Another type of IVs are deterministic IVs. These IVs are generated 113 by a deterministic process. The classic example of an algorithm that 114 uses a deterministic IV is counter (CTR) mode encryption [CTR]. An 115 algorithm that uses deterministic IVs requires that each IV provided 116 as input to the algorithm be distinct, for a fixed key. 118 A deterministic IV is sometimes called a nonce, or a deterministic 119 nonce. In cryptography, a nonce is a value that is used only once. 120 Many cryptographic protocols include a nonce in a message to enable 121 its receiver to recognize whether or not the message has been 122 previously received and processed. From the point of view of a 123 cryptographic algorithm that uses deterministic IVs, calling the IV a 124 nonce emphasizes the role of the IV in the overall system. Calling 125 that value a deterministic IV emphasizes its role in initializing the 126 algorithm to process a new message. Nonetheless, these are different 127 monikers for the same thing. 129 Authenticated Encryption is a symmetric encryption method that 130 provides for the authenticity and integrity of the data that it 131 protects, as well as its confidentiality [BN00] [R02]. An 132 authenticated encryption method that uses deterministic IVs will need 133 to make sure that the IVs used for encryption are distinct. However, 134 when performing the decryption operation, there is no need to ensure 135 that the IVs are distinct; the authenticated decryption operation 136 does not impose that requirement. The Authenticated Encryption 137 methods used in standards include Galois Counter Mode [GCM] and 138 Counter and CBC MAC mode [CCM]. 140 Some Message Authentication Code (MACs) use deterministic IVs, 141 including GMAC [GCM] and UMAC [RFC4118]. The considerations for 142 Authenticated Encryption also apply to these MAC algorithms: the IVs 143 used in the generation of an authentication tag must be distinct, but 144 there is no need to verify the distinctness of an IV prior to 145 inputting that IV to a tag verification algorithm. 147 3. Deterministic IVs in Protocols 149 The simplest way to implement a deterministic IV or nonce is to use a 150 counter: initialize an integer variable to zero, then each time that 151 an IV is needed, output the integer value, then store the incremented 152 value after checking to make sure that no integer overflow occurred, 153 so that no counter value is used twice. The simplicity of this 154 method has made it popular in practice, and recommended by standards. 156 The straightforward method of using a counter is not sufficient when 157 there are multiple encryption engines that are using the same 158 encryption key. This can be the case when encryption is distributed 159 across multiple processors, or across multiple software threads, 160 processes, or virtual machines. It can also happen in cases where a 161 protocol allows group keys. In these cases, some mechanism is needed 162 that ensures that IVs are distinct across all encryption engines that 163 use the same key. This is easily accomplished by including a fixed 164 field in the IV that is distinct for each distinct encrypter. (This 165 is detailed in Section 4.1.) 167 When a deterministic IV is used to encrypt and/or authenticate a 168 message, the receiver(s) of that message needs to know that IV in 169 order to decrypt it and/or verify its authenticity. A deterministic 170 IV can be sent along with a message, which makes it plain to the 171 receiver(s), or it can be left out of a message if the receiver(s) 172 have enough information to reconstruct it. Leaving the IV out of the 173 message reduces the amount of data that must be communicated, which 174 is advantageous. On the other hand, if the IV is included in the 175 message, the receiver(s) need not be aware of the method by which the 176 sender has chosen the IVs. 178 In practice, some protocols have split the difference between the 179 implicit method (in which the IV is absent and a receiver infers its 180 value) and the explicit method (in which the entire IV is included 181 with the message). The IV is constructed out of two fields: an 182 explicit field, which is conveyed along with the message, and an 183 implicit field, which is coordinated between the encrypter and the 184 decrypter using an "out of band" method. (This is detailed in 185 Section 4.2.) In most cases, the key management protocol that 186 establishes the encryption key can also establish the implicit field. 188 In a block cipher mode of operation that use deterministic IVs, the 189 inputs to each of the block cipher invocations during the encryption 190 process are determined by the IV provided to that process. It is 191 desirable to make the inputs to the block cipher unpredictable to an 192 attacker, to the extent that is possible, to make cryptanalytic 193 attacks more difficult and costly to attackers. This is true for 194 several types of attacks, including time-memory tradeoff attacks and 195 key collision attacks [MF00], which are generic attacks that can 196 reduce the cost of attacking any cipher, and cipher-specific attacks 197 such as integral cryptanalysis [KW02]. (It is worth noting that 198 counter mode gives an attacker exactly what they want for integral 199 cryptanalysis: a complete set of block cipher inputs that differ only 200 in some bit positions.) The cost of these attacks can be 201 significantly increased by making the deterministic IV unpredictable 202 to potential attackers. This security benefit is one motivation for 203 why the implicit field of the deterministic IV is kept secret in some 204 protocols. 206 It is not hard to adapt the simple methods for constructing 207 deterministic IVs so that they produce IVs that are unpredictable. 208 An easy way to do that is to have a secret value that is bitwise 209 exclusive-ored into the IV after all of the other processing is done. 210 (This is detailed in Section 4.3.) This secret value must be known 211 to all encrypters and decrypters, and be established via some "out of 212 band" mechanism. In practice, it is typically established by the key 213 management system. 215 4. Deterministic IVs in Standards 217 Many different protocols use deterministic IVs, including ESP 218 [RFC4106], TLS [RFC5288], SSH [RFC5647], and SRTP . The way that 219 these protocols define their IVs is outlined in this section and is 220 summarized in Table 1. 222 4.1. Recommended IV/Nonce Format 224 RFC 5116 defines the interface for Authenticated Encryption, which is 225 the most common use of deterministic IVs at present. That RFC 226 recommends an IV format, which is used by ESP, IKE, TLS, and SSH. 227 The recommended format has a total length of 12 octets, and consists 228 of a Fixed Field and a Counter field, and is structured as in 229 Figure 1. (See Section 3.2 of [RFC5116] for the precise normative 230 description.) 232 +-------------------------------+------------------------+ 233 | Fixed | Counter | 234 +-------------------------------+------------------------+ 236 Figure 1: Recommended IV/Nonce format. 238 Fixed Counter 239 <------><--------------> 240 1st 5DAD87F80000000000000001 241 2nd 5DAD87F80000000000000002 242 3rd 5DAD87F80000000000000003 243 4th 5DAD87F80000000000000004 244 5th 5DAD87F80000000000000005 245 ... ... 247 Figure 2: An example output of recommended IV/nonce format, showing 248 successive IVs where the Fixed field is 5DAD87F8. 250 The Fixed field remains constant for all nonces that are generated 251 for a given encryption device. If different devices are performing 252 encryption with a single key, then each distinct device MUST use a 253 distinct Fixed field, to ensure the uniqueness of the nonces. 255 This format is suggested, but not required, by [CTR]. 257 4.2. Partially Implicit IV/Nonce Format 259 The case in which the recommended format is used with Partially 260 Implicit Nonces is further detailed. In that case, the IV is 261 structured as in Figure 3. 263 +--------------+----------------+------------------------+ 264 | Fixed-Common | Fixed-Distinct | Counter | 265 +--------------+----------------+------------------------+ 266 <- implicit -> <--------------- explicit --------------> 268 Figure 3: Partially implicit IV/Nonce format 270 Fixed Fixed 271 Common Distinct Counter 272 <------><--><----------> 273 1st 5DAD87F81E0E000000000001 274 2nd 5DAD87F81E0E000000000002 275 3rd 5DAD87F81E0E000000000003 276 4th 5DAD87F81E0E000000000004 277 5th 5DAD87F81E0E000000000005 278 ... ... 280 Figure 4: An example output of Partially Implicit IV/Nonce format, 281 showing successive IVs where the Fixed-Common field is 5DAD87F8 and 282 the Fixed-Distinct field is 1E0E. 284 The portion of the IV that is stored or sent with the ciphertext is 285 the explicit part. The portion of the IV that is not sent with the 286 ciphertext is the implicit part. 288 The Fixed field is divided into two sub-fields: a Fixed-Common field 289 and a Fixed-Distinct field. 291 If different devices are performing encryption with a single key, 292 then each distinct device MUST use a distinct Fixed-Distinct field. 293 The Fixed-Common field is common to all IVs. The Fixed-Distinct 294 field and the Counter field MUST be in the explicit part of the IV. 295 The Fixed-Common field MAY be in the implicit part of the IV. 297 ESP, IKE, TLS, and SSH conform to the RFC 5116 Partially Implicit 298 Nonces format, though they do not require that the "Counter" field 299 actually be an integer counter (instead, "anything that guarantees 300 uniqueness can be used"). 302 4.3. Unpredictable IV/Nonce Format 304 This method is shown in Figure 5, in which the symbol (+) denotes the 305 bitwise exclusive-or operation. (Here the Fixed field consists of 306 the Fixed-Common field followed by the Fixed-Distinct field.) This 307 format uses a Randomizer, which is an octet string that is combined 308 with the other fields to make the IVs unpredictable. The length of 309 the Randomizer must be no greater than the sum of the lengths of the 310 Fixed and Counter fields. 312 The next IV in sequence is computed as follows. The Fixed field and 313 the Counter field are concatenated. If the length of the Randomizer 314 is less than the combined length of the Fixed and Counter fields, 315 then the Randomizer is padded on the right with enough zeros so that 316 the padded value has a length that exactly matches that of the Fixed 317 and Counter fields together. The concatenated Fixed and Counter 318 field is bitwise exclusive-ored with the padded Randomizer, and the 319 resulting value is the IV. The Counter is incremented, treating it 320 as an unsigned integer with the most significant byte on the left, 321 and the stored Counter field is set to the incremented value. Then 322 the IV is returned. This is the method used by SRTP [RFC3711], 323 wherein the Randomizer field is called "Salt". (We do not use the 324 term Salt in this note because some other specifications use that 325 term differently, such as [RFC4309].) 327 +-----------------+-----------------+ 328 | Fixed | Counter |---+ 329 +-----------------+-----------------+ | 330 | 331 +-----------------------------------+ v 332 | Randomizer |->(+) 333 +-----------------------------------+ | 334 | 335 +-----------------------------------+ | 336 | Initialization Vector |<--+ 337 +-----------------------------------+ 339 Figure 5: Unpredictable IV/Nonce Format. 341 Fixed Fixed 342 Common Distinct Counter IV 343 <--><------><----------> <----------------------> 344 1st 000097B4AE8F000000000001 0C81C77A5DDB678EE16FA2D0 345 2nd 000097B4AE8F000000000002 0C81C77A5DDB678EE16FA2D3 346 3rd 000097B4AE8F000000000003 0C81C77A5DDB678EE16FA2D2 347 4th 000097B4AE8F000000000004 0C81C77A5DDB678EE16FA2D5 348 5th 000097B4AE8F000000000005 0C81C77A5DDB678EE16FA2D4 349 ... ... 351 Figure 6: An example output of the Unpredictable IV/nonce format, 352 showing successive IVs where the Fixed-Distinct field has the value 353 97B4AE8F and the Salt has value 0C8150CEF354678EE16FA2D1. 355 4.4. ESP 357 In the IP Encapsulating Security Payload (ESP) 358 [RFC3686][RFC4106][RFC4309] the implicit and explicit parts are four 359 and eight bytes long, respectively. The exception is [RFC4309], for 360 which the implicit part is three bytes in length. The Fixed-Common 361 field is four bytes, and its value is set by the Internet Key 362 Exchange (IKE). (This field is named inconsistently, being called 363 Nonce in [RFC3686], and Salt in [RFC4106] and [RFC4309].) When ESP 364 is used with IKE, there is exactly one entity performing encryption, 365 and the Fixed-Distinct part is usually not present (or equivalently, 366 is has a length of zero bytes). When ESP is used with a group key 367 management protocol such as GDOI, the Fixed-Distinct field may be two 368 or four bytes in length, and the value of the Fixed-Distinct field to 369 be used by an encrypter is established by the group key management 370 protocol [RFC6054]. The case in which IKE is used with ESP and there 371 are multiple encryption engines is not specifically addressed by the 372 standards, but it can be handled by the use of a nonzero Fixed- 373 Distinct field. 375 4.5. IKE 377 The Internet Key Exchange (IKE) [RFC5282] uses the recommended IV/ 378 nonce format. The Fixed-Common field is four bytes in length, and 379 its value is set from the IKE Keying Material. The Fixed-Distinct 380 part is usually zero bytes, but it may be any number of bytes if 381 there are multiple encrypters in use. 383 4.6. TLS 385 In Transport Layer Security (TLS) [RFC5288], the Fixed-Common field 386 is four bytes in length, and the Fixed-Distinct part is usually zero 387 bytes, but it may be any number of bytes when there are multiple 388 encrypters in use. Section 6.2 of [RFC5288] gives an example of TLS 389 deterministic IV formation. 391 4.7. SSH 393 In the Secure Shell (SSH) protocol [RFC5647] the Fixed-Common field 394 is not present, the Fixed-Distinct field is four bytes long, and the 395 Counter field is eight bytes in length. The implicit part is not 396 present, and the explicit part contains the entire 12 byte IV. 398 4.8. SRTP 400 In the Secure Real-time Transport Protocol (SRTP) [RFC3711] and 401 draft-ietf-avt-srtp-aes-gcm-01 the IV formation is a bit more complex 402 than RFC 5116. It is essentially RFC 5116 format with the additional 403 step of performing a bitwise exclusive-or operation with a Randomizer 404 value. (This step provides additional strength against cryptographic 405 attacks that rely on predicting all or most of the IV.) 406 draft-ietf-avt-srtp-aes-gcm-01 uses a 12-byte IV, though RFC 3711 407 uses a 14-byte IV. 409 4.9. Summary 411 The following table gives a synopsis of how standard protocols use 412 deterministic IVs. 414 +-----------+---------+--------------+----------------+-------------+ 415 | Protocol | IV | Fixed-Common | Fixed-Distinct | Counter | 416 | | (bytes) | (bytes) | (bytes) | (bytes) | 417 +-----------+---------+--------------+----------------+-------------+ 418 | ESP | 12 | 4 | 0,1,2,[4] | 8,7,6,[4] | 419 | | | | | | 420 | | | Not on wire | On wire | On wire | 421 | | | | | | 422 | | | Set by IKE | | | 423 | | | | | | 424 | ESP | 11 | 3 | 0,1,2,[4] | 8,7,6,[4] | 425 | | | | | | 426 | [RFC4309] | | Not on wire | On wire | On wire | 427 | | | | | | 428 | | | Set by IKE | | | 429 | | | | | | 430 | IKE | 12 | 4 | Unspecified | Unspecified | 431 | | | | | | 432 | | | Not on wire | On wire | On wire | 433 | | | | | | 434 | | | Set from KM | | | 435 | | | | | | 436 | TLS | 12 | 4 | 0-8 | 8-0 | 437 | | | | | | 438 | | | Not on wire | On wire | On wire | 439 | | | | | | 440 | | | Set by TLS | | | 441 | | | | | | 442 | SSH | 12 | 0 | 4 | 8 | 443 | | | | | | 444 | | | | On wire | On wire | 445 | | | | | | 446 | | | | Unspecified | | 447 | | | | | | 448 | SRTP-CTR | 14 | 4 | 4 | 6 | 449 | | | | | | 450 | | | Not on wire | Not on wire | Not on wire | 451 | | | | | | 452 | | | Set by KM | | | 453 | | | | | | 454 | SRTP-GCM | 12 | 2 | 4 | 6 | 455 | | | | | | 456 | | | Not on wire | Not on wire | Not on wire | 457 | | | | | | 458 | | | Set by KM | | | 459 +-----------+---------+--------------+----------------+-------------+ 461 Table 1: Fields in Deterministic IVs, by Protocol. 463 5. Imlementation 465 A cryptographic implementation typically consists of a self-contained 466 and testable module that implements all of the essential 467 functionality that it needs. This functionality should include the 468 generation of deterministic IVs. 470 Because of the variety of ways in which IVs are formed in different 471 protocols, implementers may be tempted to put the generation of the 472 IV under the control of the protocol implementation. That is, from 473 the point of view of the application making use of the encryption 474 algorithm, the IV is an input to that algorithm, as shown in 475 Figure 7. Regardless, it is not good for security to have the IV be 476 generated outside the crypto module. It is possible to implement an 477 IV Generator that can be used with all of the protocols outlined 478 above and use it inside of a cryptographic module. In the following 479 we outline how that can be done. 481 +----------------------+ 482 | +--------------+ | IV +-------------+ 483 | | |<-------------------| | 484 | | Encryption | | Plaintext | | 485 | | Algorithm |<-------------------| Application | 486 | | | | Ciphertext | | 487 | | |------------------->| | 488 | +--------------+ | +-------------+ 489 | | 490 | Cryptographic Module | 491 +----------------------+ 493 Figure 7: Architecture with IV generation outside of the 494 cryptographic module, showing how the IV is entered into the 495 cryptographic module during an encryption operation. 497 The internal IV generator architecture is illustrated in Figure 8. 498 The cryptographic module contains an IV Generator sub-module that 499 understands the IV formats outlined in Section 3. To initialize the 500 IV generator, the application inputs the parameter values to be used. 501 Once initialized, the IV generator will produce successive IVs on 502 request, and send these values to the algorithm and to the calling 503 application. The encryption algorithm will need the entire IV, but 504 if the partially implicit IV format is in use, only the explicit part 505 of the IV needs to be provided to the application. The IV generator 506 is responsible for ensuring the distinctness of all of the IVs that 507 it generates. 509 +----------------------+ 510 | +--------------+ | 511 | | IV Generator |-----------+ 512 | +--------------+ | | IV (explicit part) 513 | | IV | | 514 | v | | 515 | +--------------+ | | +-------------+ 516 | | | +------->| | 517 | | Encryption | | Plaintext | | 518 | | Algorithm |<-------------------| Application | 519 | | | | Ciphertext | | 520 | | |------------------->| | 521 | +--------------+ | +-------------+ 522 | | 523 | Cryptographic Module | 524 +----------------------+ 526 Figure 8: Architecture with IV generation inside of the cryptographic 527 module, showing how the IV is generated internally during an 528 encryption operation. 530 More formally, an IV generator supports the operations of Initialize 531 and Output Next IV. The Initialize operation prepares an IV 532 Generator for use with a particular set of parameters. It takes the 533 following inputs: 535 A nonnegative integer indicating the number of bytes in the IV to 536 be generated. All of the IVs output from the Generator will have 537 the same length. 539 An octet string indicating the Fixed part of the IV; this value 540 will be used as the initial part in each IV that is generated. 542 A nonnegative integer indicating the number of bytes in the Fixed 543 part of the IV. This value must be no greater than the number of 544 bytes in the IV. 546 An octet string indicating the salt value to be exclusive-ored 547 with the other fields of the IV. If no salt is to be used when 548 Generating IVs, then this parameter must not be present. 550 A nonnegative integer indicating the number of bytes in the salt 551 value. If no salt value is used, this parameter must be zero. If 552 a salt value is used, this parameter must be no greater than the 553 number of bytes in the IV. 555 The Fixed field consists of the Fixed-Common field, followed by the 556 Fixed-Distinct field. The Fixed field and Salt field are stored when 557 the IV generator is initialized; at that time, the Counter field is 558 initialized to zero. The length of the Counter field is equal to the 559 length of the IV less the length of the Fixed field. If the Salt 560 field is shorter than the IV, then it is padded on the right with 561 zeroes. If no Salt is to be used, this is conceptually equivalent to 562 having a Salt value that is the all-zero value. 564 The Output Next IV operation returns the next IV in sequence, or it 565 returns an indication that there are no more IVs that are available. 566 During that operation, the IV is computed as follows. First, the 567 Fixed field and the Counter field are concatenated, then they are 568 bitwise exclusive-ored with the Salt field, and the resulting value 569 is the IV. The Counter is incremented, treating it as an unsigned 570 integer with the most significant byte on the left, and the stored 571 Counter field is set to the incremented value. Then the IV is 572 returned. 574 The IV generator should also be able to output the length of the 575 explicit field, so that an algorithm can output only the explicit 576 part, when that is appropriate. 578 5.1. IV Verification 580 In some protocols, the IV is constructed out of fields in the 581 protocol in such a way that it is difficult to have the IVs generated 582 inside of the cryptographic module, without requiring that module to 583 contain protocol-specific logic. In this case, assurance of the 584 uniqueness of IVs can be provided by having the IVs be generated by 585 the protocol, but checked by the cryptographic module. 587 This approach is taken by many implementations of Secure RTP 588 [RFC3711]. The IV in that protocol is constructued in a way that 589 incorporates a sender identifier (the SSRC field) and the protocol's 590 sequence number. To check the sequence number for uniqueness, an 591 implementation can make use of the anti-replay checking that the 592 protocol uses to check inbound packet. An encrypter can use this 593 approach as well, to make sure that the sequence number used to 594 construct the IV is unique. (Of course, it is necessary to have an 595 IV construction method such that the uniqueness of the sequence 596 number ensures the uniqueness of the IV.) Since many cryptographic 597 protocols contain a function to perform anti-replay check based on a 598 sequence number, this is a convenient strategy. 600 6. Testing 602 The testing of a cryptographic module is an important step in 603 assessing the assurance of that module. The IV Generator defined in 604 Section 5 can be tested by an external system to verify that it is 605 operating correctly. 607 The recommended IV format can be tested by verifying that all of the 608 IVs are distinct. There are many ways that this can be done; for 609 instance, the command "sort | uniq -d" on POSIX systems can be used 610 to detect repeated lines in a file. 612 An important aspect of an IV generator is that, when it has an N byte 613 Counter field, it should not generate more than (256)^N IVs. This 614 property should be tested for small values of N (at least 1, 2, and 615 3), by calling the Output Next IV operation M times, for some M > 616 (256)^N. Note that some implementations may produce fewer than 617 (256)^N IVs, e.g. due to their handling of the all-zero IV. That 618 would not affect security. 620 6.1. Internal IV Generator 622 When a cryptographic module uses an internal IV generator, only the 623 explicit part of the IV needs to be output from the module. It is 624 possible to test this use of the IV generator by interacting with an 625 encryption algorithm that uses it (or an Authenticated Encryption 626 algorithm, or a MAC). 628 The encryption operation takes as input a plaintext, and returns a 629 ciphertext and the explicit part of the IV. To test that the IV 630 generator is working properly, call the encryption operation 631 repeatedly, each time with the same plaintext value, and verify that 632 1) all of the ciphertexts returned are distinct, and 2) all of the 633 explicit parts that are returned are distinct. The plaintext must be 634 at least 32 bytes long, in order to avoid false positives. 636 7. Issues 638 7.1. Choice of Fixed-Distinct Field 640 When considering what data should go into a Fixed-Distinct field, it 641 is tempting to use system values such as network addresses because 642 they appear to meet the criteria of uniqueness. However, there are 643 several significant problems with this idea. System values that are 644 taken from outside the cryptographic module may not actually be 645 distinct, especially if an attacker can influence the system. System 646 values can also change over time; even if they are actually distinct, 647 they may not be fixed. Lastly, the cryptographic system should have 648 the freedom to put distinct data into the Fixed-Distinct fields, so 649 that it can accommodate multiple encryption engines when they occur. 651 Internet Protocol (IP) version four addresses are four bytes in 652 length, and thus can fit into the Fixed-Distinct field of a 12-byte 653 IV. However, an IP address is highly unsuitable for this purpose. 654 Most networked devices use dynamically assigned IP addresses, with 655 address assignment via an automatic configuration protocol such as 656 the Dynamic Host Configuration Protocol (DHCP). The addresses are 657 determined by an external system and are communicated over an 658 insecure protocol; furthermore, a DHCP address is only valid for a 659 particular period of time, and may change after that lease has 660 expired. Even when an automatic configuration protocol is not in 661 use, IP addresses are determined by the networking subsystem, and are 662 not under the control of the cryptographic module. Network Address 663 Translation (NAT, [RFC1361]) is commonly used to modify the IP 664 addresses of packets as they traverse a network boundary, for 665 instance between a private address space [RFC1918] and the Internet. 666 Because of NAT, the IP address associated with a particular device 667 will not be consistent throughout the network. Multiple devices can 668 use the same addresses; this technique is utilized in order to 669 provide redundancy or load sharing (see the Virtual Router Redundancy 670 Protocol [RFC3768] for instance). Lastly, IPv4 is currently being 671 replaced by version six of that protocol. IPv6 addresses are sixteen 672 bytes long; this is too long for inclusion in an IV, and the 673 coexistence of both versions on the Internet is likely to increase 674 the use of NAT for protocol translation [RFC6146]. In summary, IP 675 addresses are neither fixed nor distinct, and should not be used in a 676 Fixed-Distinct field. 678 Similar considerations hold for link layer addresses, Domain Name 679 System (DNS) names, and TCP, UDP, and SCTP ports. 681 A much better solution is to have the Fixed-Distinct field be 682 assigned by the security system. For instance, if a cryptographic 683 module has multiple encrypters, it can assign that field 684 appropriately for each encrypter. 686 7.2. Size of the Fixed-Distinct Field 688 Deterministic IVs typically have an explicit part that is eight bytes 689 in length. (This size is natural to use with a block cipher that has 690 a 16 byte block width, because no more than (256)^8 packets can be 691 encrypted under a single key without encountering security 692 degradation due to the birthday paradox.) Because the Fixed-Distinct 693 field must appear in the explicit part, larger Fixed-Distinct fields 694 will reduce the number of IVs that can be generated. This can be 695 problematic, especially for high throughput situations. For 696 instance, the ESP protocol allows for up to 2^64 packets to be 697 encrypted under a single key, so it is desirable to use a Counter 698 field that is close to eight bytes in length; this is why [RFC6054] 699 encourages the use of short values in the Fixed-Distinct field. 700 Table 2 presents the lifetimes of a single key that can encrypt 2^32 701 packets, i.e. a key being used with a four-byte Counter field. At 702 high data rates, keys must be replaced quickly. 704 +----------+-------------------+------------------+-----------------+ 705 | | Best Case | Typical Case | Worst Case | 706 +----------+-------------------+------------------+-----------------+ 707 | | 9000 byte packets | 850 byte packets | 64 byte packets | 708 | | | | | 709 | 1 Gbps | 3 days | 8.6 hours | 66 minutes | 710 | | | | | 711 | 10 Gbps | 8.6 hours | 52 minutes | 6.6 minutes | 712 | | | | | 713 | 40 Gbps | 22 minutes | 13 minutes | 1.6 minutes | 714 | | | | | 715 | 100 Gbps | 8.9 minutes | 5.2 minutes | 0.7 minutes | 716 +----------+-------------------+------------------+-----------------+ 718 Table 2: Key Lifetimes with a four-byte Counter field 720 7.3. Security 722 As long as each deterministic IV is distinct, for each key, then 723 security is assured. However, when deterministic IVs are not 724 distinct, security suffers. 726 The number of deterministic IVs is limited, regardless of how those 727 IVs are generated. What does an encrypter do when no more IVs are 728 available? It should retire the key that it is currently using, and 729 establish another one. This is the reason that the IETF Guidelines 730 for Cryptographic Key Management [RFC4107] require that automated key 731 management be used for algorithms with deterministic IVs. For 732 network security protocols, this has proven to be an effective 733 strategy. 735 Particular care must be taken in Virtual Machine (VM) environments, 736 because the VM cloning and rollback processes can cause inadvertent 737 re-use of deterministic IVs. This is just one of many security 738 problems that can result from uncritical application of VM mechanisms 739 when cryptography is in use [GR05]. 741 8. Security Considerations 743 Cryptographic algorithms that rely on deterministic IVs or nonces 744 must ensure the uniqueness of those values. The recommendations in 745 this note aim to help implementers achieve that goal. 747 Implementations should use the nonce formats described in Section 3. 748 The way in which these formats are used in standards is summarized in 749 Table 1. 751 Implementations should use the internal IV generator described in 752 Section 5. 754 9. References 756 9.1. Normative References 758 [CCM] Dworkin, M., "NIST Special Publication 800-38C: The CCM 759 Mode for Authentication and Confidentiality", U.S. 760 National Institute of Standards and Technology http:// 761 csrc.nist.gov/publications/nistpubs/800-38C/SP800-38C.pdf. 763 [GCM] Dworkin, M., "NIST Special Publication 800-38D: 764 Recommendation for Block Cipher Modes of Operation: 765 Galois/Counter Mode (GCM) and GMAC.", U.S. National 766 Institute of Standards and Technology http:// 767 csrc.nist.gov/publications/nistpubs/800-38D/SP800-38D.pdf. 769 [MF00] McGrew, D. and S. Fluhrer, "Attacks on Additive Encryption 770 of Redundant Plaintext and Implications on Internet 771 Security", Proceedings of the Seventh Annual Workshop on 772 Selected Areas in Cryptography (SAC 2000) Spinger-Verlag. 774 [RFC1361] Mills, D., "Simple Network Time Protocol (SNTP)", 775 RFC 1361, August 1992. 777 [RFC1918] Rekhter, Y., Moskowitz, R., Karrenberg, D., Groot, G., and 778 E. Lear, "Address Allocation for Private Internets", 779 BCP 5, RFC 1918, February 1996. 781 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 782 Requirement Levels", BCP 14, RFC 2119, March 1997. 784 [RFC3768] Hinden, R., "Virtual Router Redundancy Protocol (VRRP)", 785 RFC 3768, April 2004. 787 9.2. Informative References 789 [BN00] Bellare, M. and C. Namprempre, "Authenticated encryption: 790 Relations among notions and analysis of the generic 791 composition paradigm", Proceedings of ASIACRYPT 2000, 792 Springer-Verlag, LNCS 1976, pp. 531-545 http:// 793 www-cse.ucsd.edu/users/mihir/papers/oem.html. 795 [CTR] Dworkin, M., "NIST Special Publication 800-38: 796 Recommendation for Block Cipher Modes of Operation", U.S. 797 National Institute of Standards and Technology http:// 798 csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf. 800 [GR05] Garfinkel, T. and M. Rosenblum, "When Virtual is Harder 801 than Real: Security Challenges in Virtual Machine Based 802 Computing Environments", Proceedings of the 10th Workshop 803 on Hot Topics in Operating Systems http:// 804 www.stanford.edu/~talg/papers/HOTOS05/ 805 virtual-harder-hotos05.pdf. 807 [KW02] Knudsen, L. and D. Wagner, "Integral Cryptanalysis", 9th 808 International Workshop on Fast Software Encryption (FSE 809 '02) http://eprint.iacr.org/2004/193, December 2001. 811 [R02] Rogaway, P., "Authenticated encryption with Associated- 812 Data", ACM Conference on Computer and Communication 813 Security (CCS'02), pp. 98-107, ACM Press, 814 2002. http://www.cs.ucdavis.edu/~rogaway/papers/ad.html. 816 [RFC3686] Housley, R., "Using Advanced Encryption Standard (AES) 817 Counter Mode With IPsec Encapsulating Security Payload 818 (ESP)", RFC 3686, January 2004. 820 [RFC3711] Baugher, M., McGrew, D., Naslund, M., Carrara, E., and K. 821 Norrman, "The Secure Real-time Transport Protocol (SRTP)", 822 RFC 3711, March 2004. 824 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness 825 Requirements for Security", BCP 106, RFC 4086, June 2005. 827 [RFC4106] Viega, J. and D. McGrew, "The Use of Galois/Counter Mode 828 (GCM) in IPsec Encapsulating Security Payload (ESP)", 829 RFC 4106, June 2005. 831 [RFC4107] Bellovin, S. and R. Housley, "Guidelines for Cryptographic 832 Key Management", BCP 107, RFC 4107, June 2005. 834 [RFC4118] Yang, L., Zerfos, P., and E. Sadot, "Architecture Taxonomy 835 for Control and Provisioning of Wireless Access Points 836 (CAPWAP)", RFC 4118, June 2005. 838 [RFC4309] Housley, R., "Using Advanced Encryption Standard (AES) CCM 839 Mode with IPsec Encapsulating Security Payload (ESP)", 840 RFC 4309, December 2005. 842 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated 843 Encryption", RFC 5116, January 2008. 845 [RFC5282] Black, D. and D. McGrew, "Using Authenticated Encryption 846 Algorithms with the Encrypted Payload of the Internet Key 847 Exchange version 2 (IKEv2) Protocol", RFC 5282, 848 August 2008. 850 [RFC5288] Salowey, J., Choudhury, A., and D. McGrew, "AES Galois 851 Counter Mode (GCM) Cipher Suites for TLS", RFC 5288, 852 August 2008. 854 [RFC5647] Igoe, K. and J. Solinas, "AES Galois Counter Mode for the 855 Secure Shell Transport Layer Protocol", RFC 5647, 856 August 2009. 858 [RFC6054] McGrew, D. and B. Weis, "Using Counter Modes with 859 Encapsulating Security Payload (ESP) and Authentication 860 Header (AH) to Protect Group Traffic", RFC 6054, 861 November 2010. 863 [RFC6146] Bagnulo, M., Matthews, P., and I. van Beijnum, "Stateful 864 NAT64: Network Address and Protocol Translation from IPv6 865 Clients to IPv4 Servers", RFC 6146, April 2011. 867 Author's Address 869 David A. McGrew 870 Cisco Systems, Inc. 871 510 McCarthy Blvd. 872 Milpitas, CA 95035 873 US 875 Phone: (408) 525 8651 876 Email: mcgrew@cisco.com 877 URI: http://www.mindspring.com/~dmcgrew/dam.htm