1 2 3 4 5 6 7 8 9 Crypto Forum Research Group David A. McGrew 10 Internet Draft Cisco Systems, Inc. 11 Expires April, 2003 October, 2002 12 13 14 15 Integer Counter Mode 16 <draft-irtf-cfrg-icm-00.txt> 17 18 19 Status of this Memo 20 21 This document is an Internet Draft and is in full conformance with 22 all provisions of Section 10 of RFC-2026. Internet Drafts are working 23 documents of the Internet Engineering Task Force (IETF), its areas, 24 and working groups. Note that other groups may also distribute 25 working documents as Internet Drafts. 26 27 Internet Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet Drafts as reference 30 material or to cite them other than as "work in progress." 31 32 The list of current Internet-Drafts can be accessed at 33 http://www.ietf.org/ietf/1id-abstracts.txt 34 35 The list of Internet-Draft Shadow Directories can be accessed at 36 http://www.ietf.org/shadow.html. 37 38 39 1. Abstract 40 41 42 This document specifies Integer Counter Mode (ICM), a mode of 43 operation of a block cipher which defines an indexed keystream 44 generator (which generates a keystream segment given an index). 45 This mode is efficient, parallelizable, and has been proven secure 46 given realistic assumptions about the block cipher. Test vectors 47 are provided for AES. 48 49 Counter Mode admits many variations. The variant specified in 50 this document is secure and flexible, yet it enables a single 51 implementation of a keystream generator to suffice in different 52 application domains. 53 54 55 56 57 58 59 McGrew [Page 1] 60 61 62 Internet Draft Integer Counter Mode October, 2002 63 64 65 2. Notational Conventions 66 67 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 68 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 69 this document are to be interpreted as described in RFC-2119 [B97]. 70 71 72 3. Introduction 73 74 Counter Mode is a way to define a pseudorandom keystream generator 75 using a block cipher [CTR]. The keystream can be used for additive 76 encryption, key derivation, or any other application requiring 77 pseudorandom data. 78 79 In ICM, the keystream is logically broken into segments. Each 80 segment is identified with a segment index, and the segments have 81 equal lengths. This segmentation makes ICM especially appropriate 82 for securing packet-based protocols. 83 84 85 4. ICM 86 87 In this section, ICM keystream generation and encryption are 88 defined. 89 90 91 4.1. ICM Parameters 92 93 The following parameters are used in ICM. These parameters MUST 94 remain fixed for any given use of a key. 95 96 Parameter Meaning 97 ----------------------------------------------------------------- 98 BLOCK_LENGTH the number of octets in the cipher block 99 KEY_LENGTH the number of octets in the cipher key 100 OFFSET_LENGTH the number of octets in the offset 101 SEGMENT_INDEX_LENGTH the number of octets in the segment index 102 BLOCK_INDEX_LENGTH the number of octets in the block index 103 104 105 4.2. Keystream Segments 106 107 Conceptually, ICM is a keystream generator that takes a secret key 108 and a segment index as an input and then outputs a keystream 109 segment. The segmentation lends itself to packet encryption, as 110 each keystream segment can be used to encrypt a distinct packet. 111 112 A counter is a value containing BLOCK_LENGTH octets which is 113 114 115 116 McGrew [Page 2] 117 118 119 Internet Draft Integer Counter Mode October, 2002 120 121 122 incremented using an increment function based on integer addition, 123 to produce a sequence of distinct values which are used as inputs to 124 the block cipher. (In the context of this specification, an integer 125 is an octet string, the most significant of which is the first.) 126 The output blocks of the cipher are concatenated to form the 127 keystream segment. The first octet of the segment is the first 128 octet of the first output block, and so on. A schematic of this 129 process is shown in Figure 1. 130 131 132 Figure 1. The generation of a keystream segment given a segment 133 index and a block cipher key K. Here C[i] and S[i] denote the ith 134 counter and keystream block, respectively. 135 136 segment 137 index 138 | 139 v 140 C[0] -----> C[1] -----> C[2] -----> ... 141 | | | 142 v v v 143 +---+ +---+ +---+ 144 K->| E | K->| E | K->| E | ... 145 +---+ +---+ +---+ 146 | | | 147 v v v 148 S[0] S[1] S[2] ... 149 150 The ith counter C[i] of the keystream segment with segment index s 151 is defined as 152 153 C[i] = (i + s * (256^BLOCK_INDEX_LENGTH)) (+) r 154 155 where r denotes the shifted Offset, which is defined as the Offset 156 times 256^(BLOCK_LENGTH - OFFSET_LENGTH). (This multiplication 157 left-shifts the Offset so that it is aligned with the leftmost 158 edge of the block.) Here ^ denotes exponentiation and (+) denotes 159 the bitwise exclusive-or operation. 160 161 The number of blocks in any segment MUST NOT exceed 162 256^BLOCK_INDEX_LENGTH. The number of segments MUST NOT exceed 163 256^SEGMENT_INDEX_LENGTH. These restrictions ensure the uniqueness 164 of each block cipher input. They also imply that each segment 165 contains no more than (256^BLOCK_INDEX_LENGTH)*BLOCK_LENGTH octets. 166 167 The sum of SEGMENT_INDEX_LENGTH and BLOCK_INDEX_LENGTH MUST NOT 168 exceed BLOCK_LENGTH / 2. This requirement protects the ICM 169 keystream generator from potentially failing to be pseudorandom (see 170 171 172 173 McGrew [Page 3] 174 175 176 Internet Draft Integer Counter Mode October, 2002 177 178 179 the rationale). 180 181 Figure 2. An illustration of the structure of a counter with 182 BLOCK_LENGTH = 8, SEGMENT_INDEX_LENGTH = 2, and BLOCK_INDEX_LENGTH 183 = 2. The field marked `null' is not part of either the block 184 or segment indices. 185 186 0 1 2 3 187 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 188 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 189 | null | 190 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 191 | segment index | block index | 192 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 193 194 195 4.3. ICM Encryption 196 197 Unless otherwise specified, ICM encryption consists of bitwise 198 exclusive-oring the keystream into the plaintext to produce 199 the ciphertext. 200 201 202 4.4 ICM KEY 203 204 An ICM key consists of the block cipher key and an Offset. The 205 Offset is an integer with OFFSET_LENGTH octets, which is used to 206 `randomize' the logical starting point of keystream. The Offset is 207 crucial to providing security; see the rationale. The value of 208 OFFSET_LENGTH SHOULD be at least half that of BLOCK_LENGTH. 209 210 For the purposes of transporting an ICM key, e.g. in a signaling 211 protocol, that key SHOULD be considered a sequence of octets in 212 which the block cipher key precedes the Offset. 213 214 215 5. Implementation Considerations 216 217 Implementation of the `add one modulo 2^m' operation is simple. For 218 example, with BLOCK_LENGTH = 8 (m=64), it can be implemented in C as 219 220 if (!++x) ++y; 221 222 where x and y are 32-bit unsigned integers in network byte order. 223 The implementation of general purpose addition modulo 2^m is 224 slightly more complicated. 225 226 The fact that the Offset is left-aligned enables an implementation 227 228 229 230 McGrew [Page 4] 231 232 233 Internet Draft Integer Counter Mode October, 2002 234 235 236 to avoid propagating carry values outside of the block index and/or 237 the segment index. Choosing an OFFSET_LENGTH value equal to half 238 that of BLOCK_LENGTH avoids all of these carries, since the Offset 239 is then shifted so that it occupies the most significant octets of 240 the block, while the block and segment indices occupy the least 241 significant ones. 242 243 244 6. Parameters and Test Vectors for AES 245 246 This section provides ICM parameters and test vectors for AES 247 with a 128 bit block size and 128 bit key (that is, with a 248 BLOCK_LENGTH and KEY_LENGTH of 16). 249 250 All integers are expressed in hexadecimal. Each consecutive pair of 251 hex digits corresponds to an octet, so that the integer 252 000102030405060708090A0B0C0D0E0F corresponds to the octet sequence 253 { 00, 01, 02, 02 ... }. 254 255 BLOCK_LENGTH 16 256 KEY_LENGTH 16 257 OFFSET_LENGTH 14 258 SEGMENT_INDEX_LENGTH 6 259 BLOCK_INDEX_LENGTH 2 260 261 Block Cipher Key: 2b7e151628aed2a6abf7158809cf4f3c 262 Offset: f0f1f2f3f4f5f6f7f8f9fafbfcfd 263 Segment Index: 000000000000 264 Keystream: e03ead0935c95e80e166b16dd92b4eb4 265 d23513162b02d0f72a43a2fe4a5f97ab 266 ... 267 268 The counter values that correspond to the keystream blocks are 269 outlined below. 270 271 Counter Keystream 272 273 f0f1f2f3f4f5f6f7f8f9fafbfcfd0000 e03ead0935c95e80e166b16dd92b4eb4 274 f0f1f2f3f4f5f6f7f8f9fafbfcfd0001 d23513162b02d0f72a43a2fe4a5f97ab 275 f0f1f2f3f4f5f6f7f8f9fafbfcfd0002 41e95b3bb0a2e8dd477901e4fca894c0 276 ... ... 277 278 279 7. Security Considerations 280 281 Each block cipher input is distinct for any segment and any block 282 index. To see this fact, subtract any two counter values with 283 distinct segment or block indices; the result is non-zero. 284 285 286 287 McGrew [Page 5] 288 289 290 Internet Draft Integer Counter Mode October, 2002 291 292 293 The limitation on the number of segments which can be generated 294 ensures that the probability with which an adversary can distinguish 295 the keystream generator from random is negligible. For a 296 theoretical justification of this fact, see Bellare et. al. [BR98]. 297 Their analysis shows that if the block cipher cannot be 298 distinguished from a random permutation, then the keystream 299 generated by ICM cannot be distinguished from keystream generated by 300 a truly random process, as long as the length of keystream which is 301 generated is kept below some threshold. The threshold defined in 302 Section 4.2 is sufficient for most uses of ICM for encryption. This 303 specification refrains from dictating a lower threshold in order to 304 refrain from dictating a particular policy, and to avoid a 305 complicated digression. 306 307 The use of the Offset, a key-dependent value which randomizes the 308 starting position of the keystream, is essential for security. The 309 omission of this mechanism leaves the door open for practical 310 attacks, such as the key collision attack and Hellman's time-memory 311 tradeoff attack; see McGrew and Fluhrer [MF00] for a description of 312 these attacks which is applicable to ICM. Several counter mode 313 proposals do not include an offset, and are thus vulnerable to these 314 attacks. 315 316 317 8. Rationale 318 319 This speficiation includes input from implementation experience with 320 several counter mode variants. The goals of ICM are to provide: 321 322 o a secure keystream generator and cipher, and 323 324 o a definition flexible enough that a single implementation can be 325 used for a variety of applications (e.g., Secure RTP [SRTP], 326 IPsec ESP [KA96]). 327 328 The Offset slightly increases the key management overhead, but this 329 minor disadvantage is well outweighed by other savings. The Offset 330 is no larger than a CBC mode IV, and ICM enables the use of an 331 explicit IV (as is commonly used with CBC [MD98]) to be avoided. 332 333 334 9. History 335 336 This draft is based on draft-mcgrew-saag-icm-00.txt, which was 337 submitted to SAAG on November, 2001 and which expired in May, 2002. 338 339 The current definition of ICM has changed from the earlier one; the 340 counter formation is different and the specifications are 341 342 343 344 McGrew [Page 6] 345 346 347 Internet Draft Integer Counter Mode October, 2002 348 349 350 unfortunately not interoperable. This change was motivated by a 351 considerable amount of feedback on the desirability of admitting 352 optimizations of the sort described in Section 5, in which the carry 353 operations of counter addition need not be propagated across a large 354 register. 355 356 The current definition of ICM is interoperable with that defined in 357 Secure RTP [SRTP]. 358 359 360 10. Acknowledgements 361 362 Thanks are due to Helger Lipmaa, Jerome Etienne, Scott Fluhrer and 363 Mats Naslund for their helpful discussion and comments. 364 365 366 11. Contact Information 367 368 Questions and comments on this draft SHOULD be sent to: 369 370 David A. McGrew 371 Cisco Systems, Inc. 372 mcgrew (a] cisco.com 373 374 and copied to the Crypto Forum Research Group at: 375 376 cfrg (a] ietf.org. 377 378 379 12. References 380 381 382 [BR98] M. Bellare, A. Desai, E. Lokipii and P. Rogaway, A 383 Concrete Security Treatment of Symmetric Encryption: 384 Analysis of DES Modes of Operation, Proceedings of 385 the 38th Symposium on Foundations of Computer 386 Science, IEEE, 1997. 387 388 [B97] S. Bradner, Key words for use in RFCs to Indicate 389 Requirement Levels, RFC 2119, March 1997. 390 391 [AES] The Advanced Encryption Standard, United States 392 National Institute for Standards and Technology (NIST), 393 http://www.nist.gov/aes/. 394 395 [CTR] M. Dworkin, NIST Special Publication 800-38A, 396 "Recommendation for Block Cipher Modes of Operation: Methods 397 and Techniques", 2001. Online at 398 399 400 401 McGrew [Page 7] 402 403 404 Internet Draft Integer Counter Mode October, 2002 405 406 407 http://csrc.nist.gov/publications/nistpubs/800-38a/sp800- 408 38a.pdf. 409 410 [MD98] Madson, C., and Doraswamy, N., "The ESP DES-CBC Cipher 411 Algorithm With Explicit IV", RFC 2405, November 1998. 412 413 [MF00] D. McGrew and S. Fluhrer, Attacks on Additive Encryption and 414 Implications on Internet Security, Selected Areas in 415 Cryptography 2000. 416 417 [SRTP] The Secure Real-time Transport Protocol, Baugher et. al., 418 Internet Draft, draft-ietf-avt-srtp-05.txt. 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 McGrew [Page 8] 459 460 461
