idnits 2.17.1 draft-dharkins-siv-aes-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 15. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1115. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1126. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1133. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1139. 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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 26, 2008) is 5775 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-04) exists of draft-krovetz-ocb-00 == Outdated reference: A later version (-18) exists of draft-zorn-radius-keywrap-13 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force D. Harkins 3 Internet-Draft Aruba Networks 4 Intended status: Informational June 26, 2008 5 Expires: December 28, 2008 7 SIV Authenticated Encryption using AES 8 draft-dharkins-siv-aes-05 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that any 13 applicable patent or other IPR claims of which he or she is aware 14 have been or will be disclosed, and any of which he or she becomes 15 aware will be disclosed, in accordance with Section 6 of BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on December 28, 2008. 35 Copyright Notice 37 Copyright (C) The IETF Trust (2008). 39 Abstract 41 This memo describes SIV (Synthetic Initialization Vector), a block 42 cipher mode of operation. SIV takes a key, a plaintext, and multiple 43 variable-length octet strings which will be authenticated but not 44 encrypted. It produces a ciphertext having the same length as the 45 plaintext and a synthetic initialization vector. Depending on how it 46 is used, SIV achieves either the goal of deterministic authenticated- 47 encryption or the goal of nonce-based, misuse-resistant 48 authenticated-encryption. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 1.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 3 54 1.2. Definitions . . . . . . . . . . . . . . . . . . . . . . . 4 55 1.3. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 4 56 1.3.1. Key Wrapping . . . . . . . . . . . . . . . . . . . . . 4 57 1.3.2. Resistance to Nonce Misuse/Reuse . . . . . . . . . . . 4 58 1.3.3. Key Derivation . . . . . . . . . . . . . . . . . . . . 5 59 1.3.4. Robustness versus Performance . . . . . . . . . . . . 5 60 1.3.5. Conservation of Cryptographic Primitives . . . . . . . 6 61 2. Specification of SIV . . . . . . . . . . . . . . . . . . . . . 6 62 2.1. Notation . . . . . . . . . . . . . . . . . . . . . . . . . 6 63 2.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 7 64 2.3. Doubling . . . . . . . . . . . . . . . . . . . . . . . . . 7 65 2.4. S2V . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 66 2.5. CTR . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 67 2.6. SIV Encrypt . . . . . . . . . . . . . . . . . . . . . . . 10 68 2.7. SIV Decrypt . . . . . . . . . . . . . . . . . . . . . . . 12 69 3. Nonce-based Authenticated Encryption with SIV . . . . . . . . 14 70 4. Deterministic Authenticated Encryption with SIV . . . . . . . 15 71 5. Optimizations . . . . . . . . . . . . . . . . . . . . . . . . 15 72 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 73 6.1. AEAD_AES_SIV_CMAC_256 . . . . . . . . . . . . . . . . . . 17 74 6.2. AEAD_AES_SIV_CMAC_384 . . . . . . . . . . . . . . . . . . 17 75 6.3. AEAD_AES_SIV_CMAC_512 . . . . . . . . . . . . . . . . . . 17 76 7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 77 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 19 78 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 79 9.1. Normative References . . . . . . . . . . . . . . . . . . . 19 80 9.2. Informative References . . . . . . . . . . . . . . . . . . 19 81 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 21 82 A.1. Deterministic Authenticated Encryption Example . . . . . . 21 83 A.2. Nonce-based Authenticated Encryption Example . . . . . . . 22 84 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 24 85 Intellectual Property and Copyright Statements . . . . . . . . . . 25 87 1. Introduction 89 1.1. Background 91 Various attacks have been described (e.g. [BADESP]) when data is 92 merely privacy-protected and not additionally authenticated or 93 integrity protected. Therefore combined modes of encryption and 94 authentication have been developed ([RFC5116], [CCM], [GCM], [JUTLA], 95 [OCB]). These provide conventional authenticated-encryption when 96 used with a nonce ("a number used once") and typically accept 97 additional inputs that are authenticated but not encrypted, 98 hereinafter referred to as "associated data" or AD. 100 A deterministic, nonce-less, form of authenticated-encryption has 101 been used to protect the transportation of cryptographic keys (e.g. 102 [X9F1], [RFC3217], [RFC3394]). This is generally referred to as "Key 103 Wrapping". 105 This memo describes a new block cipher mode, SIV, that provides both 106 nonce-based authenticated encryption as well as deterministic, nonce- 107 less key wrapping. It contains a PRF construction called S2V and an 108 encryption/decryption construction, called CTR. SIV was specified by 109 Phillip Rogaway and Thomas Shrimpton in [DAE]. The underlying block 110 cipher used herein for both S2V and CTR is AES with key lengths of 111 128 bits, 192 bits, or 256 bits. S2V uses AES in CMAC ([CMAC]) mode, 112 CTR uses AES in counter ([MODES]) mode. 114 Associated data is data input to an authenticated-encryption mode 115 that will be authenticated but not encrypted. [RFC5116] says that 116 associated data can include "addresses, ports, sequence numbers, 117 protocol version numbers, and other fields that indicate how the 118 plaintext or ciphertext should be handled, forwarded, or processed." 119 These are multiple, distinct inputs and may not be contiguous. Other 120 authenticated-encryption cipher modes allow only a single associated 121 data input. Such a limitation may require implementation of a 122 scatter/gather form of data marshalling to combine the multiple 123 components of the associated data into a single input or may require 124 a pre-processing step where the associated data inputs are 125 concatenated together. SIV accepts multiple variable-length octet 126 strings (hereinafter referred to as a "vector of strings") as 127 associated data inputs. This obviates the need for data marshalling 128 or pre-processing of associated data to package it into a single 129 input. 131 By allowing associated data to consist of a vector of strings SIV 132 also obviates the requirement to encode the length of component 133 fields of the associated data when those fields have variable length. 135 1.2. Definitions 137 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 138 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 139 document are to be interpreted as described in RFC 2119 [RFC2119]. 141 1.3. Motivation 143 1.3.1. Key Wrapping 145 A key distribution protocol must protect keys it is distibuting. 146 This has not always been done right. For example, RADIUS [RFC2865] 147 uses MPPE [RFC2548] to encrypt a key prior to transmission from 148 server to client. It provides no integrity checking of the encrypted 149 key. [RADKEY] specifies the use of [RFC3394] to wrap a key in a 150 RADIUS request but because of the inability to pass associated data 151 an HMAC [RFC2104] is necessary to provide authentication of the 152 entire request. 154 SIV can be used as a drop-in replacement for any specification that 155 uses [RFC3394] or [RFC3217], including the aforementioned use. It is 156 a more general purpose solution as it allows for associated data to 157 be specified. 159 1.3.2. Resistance to Nonce Misuse/Reuse 161 The nonce-based authenticated encryption schemes described above are 162 susceptible to reuse and/or misue of the nonce. Depending on the 163 specific scheme there are subtle and critical requirements placed on 164 the nonce (see [SP800-38D]). [GCM] states that it provides 165 "excellent security" if its nonce is guaranteed to be distinct but 166 provides "no security" otherwise. Confidentiality guarantees are 167 voided if a counter in [CCM] is reused. In many cases guaranteeing 168 no reuse of a nonce/counter/IV is not a problem but in others it will 169 be. 171 For example, many applications obtain access to cryptographic 172 functions via an application program interface to a cryptographic 173 library. These libraries are typically not stateful and any nonce, 174 initialization vector, or counter required by the cipher mode is 175 passed to the cryptographic library by the application. Putting the 176 construction of a security-critical datum outside the control of the 177 encryption engine places an onerous burden on the application writer 178 who may not provide the necessary cryptographic hygiene. Perhaps his 179 random number generator is not very good or maybe an application 180 fault causes a counter to be reset. The fragility of the cipher mode 181 may result in its inadvertent misuse. Also, if one's environment is 182 (knowingly or unknowingly) a virtual machine it may be possible to 183 roll back a virtual state machine and cause nonce reuse thereby 184 gutting the security of the authenticated encryption scheme (see 185 [VIRT]). 187 If the nonce is random, a requirement that it never repeat will limit 188 the amount of data that can be safely protected with a single key to 189 one block. More sensibly a random nonce is required to "almost 190 always" be non-repeating but that will drastically limit the amount 191 of data that can be safely protected. 193 SIV provides a level of resistance to nonce reuse and misuse. If the 194 nonce is never reused then the usual notion of nonce-based security 195 of an authenticated encryption mode is achieved. If, however, the 196 nonce is reused, authenticity is retained and confidentiality is only 197 compromised to the extent that an attacker can determine that the 198 same plaintext (and same associated data) was protected with the same 199 nonce and key. See Security Considerations (Section 7). 201 1.3.3. Key Derivation 203 A PRF is frequently used as a key derivation function (e.g. [WLAN]) 204 by passing it a key and a single string. Typically this single 205 string is the concatenation of a series of smaller strings--for 206 example, a label and some context to bind into the derived string. 208 These are usually multiple strings but are mapped to a single string 209 because of the way PRFs are typically defined--two inputs: a key and 210 data. Such a crude mapping is inefficient because additional data 211 must be included--the length of variable-length inputs must be 212 encoded separately--and, depending on the PRF, memory allocation and 213 copying may be needed. Also, if only one or two of the inputs 214 changed when deriving a new key it may still be necessary to process 215 all of the other constants that preceded it every time the PRF is 216 invoked. 218 When a PRF is used in this manner its input is a vector of strings 219 and not a single string and the PRF should handle the data as such. 220 The S2V ("string to vector") PRF construction accepts a vector of 221 inputs and provides a more natural mapping of input that does not 222 require additional lengths encodings and obviates the memory and 223 processing overhead to marshall inputs and their encoded lengths into 224 a single string. Constant inputs to the PRF need only be computed 225 once. 227 1.3.4. Robustness versus Performance 229 SIV cannot perform at the same high throughput rates that other 230 authenticated encryption schemes can (e.g. [GCM] or [OCB]) due to 231 the requirement for two passes of the data but for situations where 232 performance is not a limiting factor-- e.g. control plane 233 applications-- it can provide a robust alternative, especially when 234 considering its resistance to nonce re-use. 236 1.3.5. Conservation of Cryptographic Primitives 238 The cipher mode described herein can do authenticated encryption, key 239 wrapping, key derivation, and serve as a generic message 240 authentication algorithm. It is therefore possible to implement all 241 these functions with a single tool, instead of one tool for each 242 function. This is extremely attractive for devices that are memory 243 and/or processor constrained and that cannot afford to implement 244 multiple cryptographic primitives to accomplish these functions. 246 2. Specification of SIV 248 2.1. Notation 250 SIV and S2V use the following notation: 252 len(A) 253 returns the number of bits in A. 255 pad(X) 256 indicates padding of string X, len(X) < 128, out to 128 bits by 257 the concatenation of a single bit of 1 followed by as many 0 bits 258 as are necessary. 260 leftmost(A,n) 261 the n most significant bits of A. 263 rightmost(A,n) 264 the n least significant bits of A. 266 A || B 267 means concatenation of string A with string B. 269 A xor B 270 is the exclusive OR operation on two equal length strings, A and 271 B. 273 A xorend B 274 where len(A) >= len(B), means xoring a string B onto the end of 275 string A-- i.e. leftmost(A, len(A)-len(B)) || (rightmost(A, 276 len(B)) xor B) 278 A bitand B 279 is the logical AND operation on two equal equal length strings, A 280 and B. 282 dbl(S) 283 is the multiplication of S and 0...010 in a finite field 284 represented using the primitive polynomial x^128 + x^7 + x^2 + x 285 + 1. See Doubling (Section 2.3) 287 a^b 288 indicates a string that is "b" bits each having the value "a". 290 291 indicates a string that is 128 zero bits. 293 294 indicates a string that is 127 zero bits concatenated with a 295 single one bit, that is 0^127 || 1^1. 297 A/B 298 indicates the greatest integer less than or equal to the real- 299 valued quotient of A and B. 301 E(K,X) 302 indicates AES encryption of string X using key K 304 2.2. Overview 306 SIV-AES uses AES in CMAC mode (S2V) and in counter mode (CTR). SIV- 307 AES takes either a 256, 384, or 512 bit key (which is broken up into 308 two equal-sized keys, one for S2V and the other for CTR), a variable 309 length plaintext, and multiple variable length strings representing 310 associated data. It's output is a ciphertext which comprises a 311 synthetic initialization vector concatenated with the encrypted 312 plaintext. 314 2.3. Doubling 316 The doubling operation on a 128-bit input string is performed using a 317 left-shift of the input followed by a conditional xor operation on 318 the result with the constant: 320 00000000 00000000 00000000 00000087 322 The condition under which the xor operation is performed is when the 323 bit being shifted off is one. 325 Note that this is the same operation used to generate sub-keys for 326 CMAC-AES 328 2.4. S2V 330 The S2V operation consists of the doubling and xoring of the outputs 331 of a pseudo-random function, CMAC, operating over individual strings 332 in the input vector: S1, S2, ... Sn. It is bootstrapped by 333 performing CMAC on a 128-bit string of zeros. If the length of the 334 final string in the vector is greater than or equal to 128 bits the 335 output of the double/xor chain is xored onto the end of the final 336 input string. That result is input to a final CMAC operation to 337 produce the output V. If the length of the final string is less than 338 128 bits the output of the double/xor chain is doubled once more and 339 it is xored with the final string padded using the padding function 340 pad(X). That result is input to a final CMAC operation to produce 341 the output V. 343 S2V with key k on a vector of n inputs S1, S2, ..., Sn-1, Sn, and 344 len(Sn) >= 128: 346 +----+ +----+ +------+ +----+ 347 | S1 | | S2 | . . . | Sn-1 | | Sn | 348 +----+ +----+ +------+ +----+ 349 K | | | | 350 | | | | | V 351 V | V V V /----> xorend 352 +-----+ | +-----+ +-----+ +-----+ | | 353 | AES-|<----->| AES-| K-->| AES-| K--->| AES-| | | 354 | CMAC| | CMAC| | CMAC| | CMAC| | | 355 +-----+ +-----+ +-----+ +-----+ | V 356 | | | | | +-----+ 357 | | | | | K-->| AES-| 358 | | | | | | CMAC| 359 | | | | | +-----+ 360 \-> dbl -> xor -> dbl -> xor -> dbl -> xor---/ | 361 V 362 +---+ 363 | V | 364 +---+ 366 where 'dbl' is the double operation. 368 Figure 2 370 S2V with key k on a vector of n inputs S1, S2, ..., Sn-1, Sn, and 371 len(Sn) < 128: 373 +----+ +----+ +------+ +---------+ 374 | S1 | | S2 | . . . | Sn-1 | | pad(Sn) | 375 +----+ +----+ +------+ +---------+ 376 K | | | | 377 | | | | | V 378 V | V V V /------> xor 379 +-----+ | +-----+ +-----+ +-----+ | | 380 | AES-|<--->| AES-| K-->| AES-| K-->| AES-| | | 381 | CMAC| | CMAC| | CMAC| | CMAC| | | 382 +-----+ +-----+ +-----+ +-----+ | V 383 | | | | | +-----+ 384 | | | | | K-->| AES-| 385 | | | | | | CMAC| 386 | | | | | +-----+ 387 \-> dbl -> xor -> dbl -> xor -> dbl -> xor-> dbl | 388 V 389 +---+ 390 | V | 391 +---+ 393 where 'dbl' is the double operation. 395 Figure 3 397 Algorithmically S2V can be described as: 399 S2V(K, S1, ..., Sn) { 400 if n = 0 then 401 return V = AES-CMAC(K, ) 402 fi 403 D = AES-CMAC(K, ) 404 for i = 1 to n-1 do 405 D = dbl(D) xor AES-CMAC(K, Si) 406 done 407 if len(Sn) >= 128 then 408 T = Sn xorend D 409 else 410 T = dbl(D) xor pad(Sn) 411 fi 412 return V = AES-CMAC(K, T) 413 } 415 2.5. CTR 417 CTR is a counter mode of AES. It takes as input a plaintext P of 418 arbitrary length, a key K of length 128, 192 or 256 bits, and a 419 counter X that is 128 bits in length, and outputs Z which represents 420 a concatenation of a synthetic initialization vector V, and the 421 ciphertext, C, which is the same length as the plaintext. 423 The ciphertext is produced by xoring the plaintext with the first 424 len(P) bits of the following string: 426 E(K, X) || E(K, X+1) || E(K, X+2) || ... 428 Before beginning counter mode, the 31st and 63rd bits (where the 429 rightmost bit is the 0th bit) of the counter are cleared. This 430 enables implementations which support native 32 bit (64 bit) addition 431 to increment the counter modulo 2^32 (2^64). More formally, for 32 432 bit addition the counter is incremented as: 434 SALT=leftmost(X,96) 436 n=rightmost(X,32) 438 X+i = SALT || (n + i mod 2^32). 440 For 64 bit addition the counter is incremented as: 442 SALT=leftmost(X,64) 444 n=rightmost(X,64) 446 X+i = SALT || (n + i mod 2^64). 448 Performing 32 bit or 64 bit addition on the counter will limit the 449 amount of plaintext that can be safely protected by SIV-AES to 2^39 - 450 128 bits or 2^71 - 128 bits, respectively. 452 2.6. SIV Encrypt 454 SIV-encrypt takes as input a key K of length 256, 384 or 512 bits, 455 plaintext of arbitrary length, and a vector of associated data where 456 the number of components in the vector is not greater than 126 (see 457 Section 7). It produces output, Z, which is the concatenation of a 458 128-bit synthetic initialization vector and ciphertext whose length 459 is equal to the length of the plaintext. 461 The key is split into equal halves, K1 = leftmost(K, len(K)/2) and K2 462 = rightmost(K, len(K)/2). K1 is used for S2V and K2 is used for CTR. 464 In the encryption mode the associated data and plaintext represent 465 the vector of inputs to S2V, with the plaintext being the last string 466 in the vector. The output of S2V is a synthetic IV which represents 467 the initial counter to CTR. 469 The encryption construction of SIV is as follows: 471 +------+ +------+ +------+ +---+ 472 | AD 1 | | AD 2 |...| AD n | | P | 473 +------+ +------+ +------+ +---+ 474 | | | | 475 | | ... | ------------------| 476 \ | / / | 477 \ | / / +------------+ | 478 \ | / / | K = K1||K2 | | 479 \ | / / +------------+ V 480 \ | / / | | +-----+ 481 \ | / / K1 | | K2 | | 482 \ | / / ------/ \------>| CTR | 483 \ | / / / ------->| | 484 | | | | | | +-----+ 485 V V V V V | | 486 +------------+ +--------+ V 487 | S2V |------>| V | +----+ 488 +------------+ +--------+ | C | 489 | +----+ 490 | | 491 -----\ | 492 \ | 493 \ | 494 V V 495 +-----+ 496 | Z | 497 +-----+ 499 where the plaintext is P, the associated data is AD1 through ADn, V 500 is the synthetic IV, the ciphertext is C, and Z is the output. 502 Figure 8 504 Algorithmically SIV Encrypt can be described as: 506 SIV-ENCRYPT(K, P, AD1, ..., ADn) { 507 K1 = leftmost(K, len(K)/2) 508 K2 = rightmost(K, len(K)/2) 509 V = S2V(K1, AD1, ..., ADn, P) 510 Q = V bitand (1^64 || 0^1 || 1^31 || 0^1 || 1^31) 511 m = (len(P) + 127)/128 513 for i = 0 to m-1 do 514 Xi = AES(K2, Q+i) 515 done 516 X = leftmost(X0 || ... || Xm-1, len(P)) 517 C = P xor X 519 return V || C 520 } 522 where the key length used by AES in CTR and S2V is len(K)/2 and will 523 each be either 128 bits, 192 bits, or 256 bits. 525 The 31st and 63rd bit (where the rightmost bit is the 0th) of the 526 counter are zeroed out just prior to being used by CTR for 527 optimization purposes, see Section 5. 529 2.7. SIV Decrypt 531 SIV-decrypt takes as input a key K of length 256, 384 or 512 bits, Z 532 which represents a synthetic initialization vector V concatentated 533 with a ciphertext C, and a vector of associated data where the number 534 of components in the vector is not greater than 126 (see Section 7). 535 It produces either the original plaintext or the special symbol FAIL. 537 The key is split as specified in Section 2.6 539 The synthetic initialization vector acts as the initial counter to 540 CTR to decrypt the ciphertext. The associated data and the output of 541 CTR represents a vector of strings that is passed to S2V, with the 542 CTR output being the last string in the vector. The output of S2V is 543 then compared against the synthetic IV that accompanied the original 544 ciphertext. If they match the output from CTR is returned as the 545 decrypted and authenticated plaintext otherwise the special symbol 546 FAIL is returned. 548 The decryption construction of SIV is as follows: 550 +------+ +------+ +------+ +---+ 551 | AD 1 | | AD 2 |...| AD n | | P | 552 +------+ +------+ +------+ +---+ 553 | | | ^ 554 | | ... / | 555 | | / /----------------| 556 | | / / | 557 \ | / / +------------+ | 558 \ | / / | K = K1||k2 | | 559 \ | / / +------------+ | 560 \ | / / | | +-----+ 561 \ | / / K1 | | K2 | | 562 \ | | | /-----/ \----->| CTR | 563 \ | | | | ------->| | 564 | | | | | | +-----+ 565 V V V V V | ^ 566 +-------------+ +--------+ | 567 | S2V | | V | +---+ 568 +-------------+ +--------+ | C | 569 | | ^ +---+ 570 | | | ^ 571 | | \ | 572 | | \___ | 573 V V \ | 574 +-------+ +---------+ +---+ 575 | T |----->| if != | | Z | 576 +-------+ +---------+ +---+ 577 | 578 | 579 V 580 FAIL 582 Figure 10 584 Algorithmically SIV-Decrypt can be described as: 586 SIV-DECRYPT(K, Z, AD1, ..., ADn) { 587 V = leftmost(Z, 128) 588 C = rightmost(Z, len(Z)-128) 589 K1 = leftmost(K, len(K)/2) 590 K2 = rightmost(K, len(K)/2) 591 Q = V bitand (1^64 || 0^1 || 1^31 || 0^1 || 1^31) 593 m = (len(C) + 127)/128 594 for i = 0 to m-1 do 595 Xi = AES(K2, Q+i) 596 done 597 X = leftmost(X0 || ... || Xm-1, len(C)) 598 P = C xor X 599 T = S2V(K1, AD1, ..., ADn, P) 601 if T = V then 602 return P 603 else 604 return FAIL 605 fi 606 } 608 where the key length used by AES in CTR and S2V is len(K)/2 and will 609 each be either 128 bits, 192 bits, or 256 bits. 611 The 31st and 63rd bit (where the rightmost bit is the 0th) of the 612 counter are zeroed out just prior to being used in CTR mode for 613 optimization purposes, see Section 5. 615 3. Nonce-based Authenticated Encryption with SIV 617 SIV performs nonce-based authenticated encryption when a component of 618 the associated data is a nonce. For purposes of interoperability the 619 final component-- i.e. the string immediately preceding the plaintext 620 in the vector input to S2V-- is used for the nonce. Other associated 621 data are optional. It is up to the specific application of SIV to 622 specify how the rest of the associated data are input. 624 If the nonce is random it SHOULD be at least 128 bits in length and 625 be harvested from a pool having at least 128 bits of entropy. A non- 626 random source MAY also be used, for instance a time stamp, or a 627 counter. The definition of a nonce precludes reuse but SIV is 628 resistant to nonce reuse. See Section 1.3.2 for a discussion on the 629 security implications of nonce reuse. 631 It MAY be necessary to transport this nonce with the output generated 632 by S2V. 634 4. Deterministic Authenticated Encryption with SIV 636 When the plaintext to encrypt and authenticate contains data that is 637 unpredictible to an adversary-- for example, a secret key-- SIV can 638 be used in a deterministic mode to perform "key wrapping". Because 639 S2V allows for associated data and imposes no unnatural size 640 restrictions on the data it is protecting it is a more useful and 641 general purpose solution than [RFC3394]. Protocols which use SIV for 642 deterministic authenticated encryption (i.e. for more than just 643 wrapping of keys) MAY define associated data inputs to SIV. It is 644 not necessary to add a nonce component to the AD in this case. 646 5. Optimizations 648 Implementations which cannot or do not wish to support addition 649 modulo 2^128 can take advantage of the fact that the 31st and 63rd 650 bits (where the rightmost bit is the 0th bit) in the counter are 651 cleared before being used by CTR. This allows implementations which 652 natively support 32 bit or 64 bit addition to increment the counter 653 naturally. Of course in this case the amount of plaintext that can 654 be safely protected by SIV is reduced by a commensurate amount-- 655 addition modulo 2^32 limits plaintext to (2^32 - 1) blocks, addition 656 modulo 2^64 limits plaintext to (2^64 - 1) blocks. 658 It is possible to optimize an implementation of S2V when it is being 659 used as a key derivation function (KDF), for example in [WLAN]. This 660 is because S2V operates on a vector of distinct strings and typically 661 the data passed to a KDF contains constant strings. Depending on the 662 location of variant components of the input different optimizations 663 are possible. The CMAC'd output of intermediate and invariant 664 components can be computed once and cached. This can then be doubled 665 and xor'd with the running sum to produce the output. Or an 666 intermediate value that represents the doubled and xor'd output of 667 multiple components, up to the variant component, can be computed 668 once and cached. 670 6. IANA Considerations 672 [RFC5116] defines a uniform interface to cipher modes which provide 673 nonce-based authenticated encryption with associated data (AEAD). It 674 does this via a registry of AEAD algorithms. 676 The Internet Assigned Numbers Authority (IANA) will assign three 677 entries from the AEAD Registry for AES-SIV-CMAC-256, AES-SIV-CMAC- 678 384, AES-SIV-CMAC-512 based upon the following AEAD algorithm 679 definitions. [RFC5116] defines operations in octets, not bits. 680 Limits in this section will therefore be specified in octets. The 681 security analysis for each of these algorithms is in [DAE]. 683 Unfortunately [RFC5116] restricts AD input to a single component and 684 limits the benefit SIV offers for dealing in a natural fashion with 685 AD consisting of multiple distinct components. Therefore when it is 686 required to access SIV through the interface defined in [RFC5116] it 687 is necessary to marshall multiple AD inputs into a single string (see 688 Section 1.1) prior to invoking SIV. Note that this requirement is 689 not unique to SIV. All cipher modes using [RFC5116] MUST similarly 690 marshall multiple AD inputs into a single string and any technique 691 used for any other AEAD mode (e.g. a scatter/gather technique) can be 692 used with SIV. 694 [RFC5116] requires AEAD algorithm specifications to include maximal 695 limits to the amount of plaintext, the amount of associated data, and 696 the size of a nonce that the AEAD algorithm can accept. 698 SIV uses AES in counter mode and the security guarantees of SIV would 699 be lost if the counter was allowed to repeat. Since the counter is 700 128 bits, a limit to the amount of plaintext that can be safely 701 protected by a single invocation of SIV is 2^128 blocks. Multiple 702 invocations of SIV with the same key, though, can increase the 703 possibility of distinct invocations having overlapping counter-space 704 so the limit on the amount of plaintext that can be safely protected 705 by SIV is set at 2^64 blocks. 707 To prevent the possibility of collisions [CMAC] recommends that no 708 more than 2^48 invocations be made to CMAC with the same key. This 709 is not a limit on the amount of data that can be passed to CMAC 710 though. There is no practical limit to the amount of data that can 711 be made to a single invocation of CMAC, and likewise there is no 712 practical limit to the amount of associated data or nonce material 713 that can be passed to SIV. 715 A collision in the output of S2V would mean the same counter would be 716 used with different plaintext in counter mode. This would void the 717 security guarantees of SIV. The "Birthday Paradox" (see [APPCRY]) 718 would imply that no more than 2^64 distinct invocations to SIV be 719 made with the same key. It is prudent to follow the example of 720 [CMAC] though and further limit the number of distinct invocations of 721 SIV using the same key to 2^48. Note that [RFC5116] does not provide 722 a variable to describe this limit. 724 6.1. AEAD_AES_SIV_CMAC_256 726 The AES-SIV-CMAC-256 AEAD algorithm works as specified in Section 2.6 727 and Section 2.7. The input and output lengths for AES-SIV-CMAC-256 728 as defined by [RFC5116] are: 730 K_LEN is 32 octets. 732 P_MAX is 2^68 octets. 734 A_MAX is unlimited. 736 N_MIN is 1 octet. 738 N_MAX is unlimited. 740 C_MAX is 2^68 + 16 octets. 742 The security implications of nonce re-use and/or mis-use are 743 described in Section 1.3.2. 745 6.2. AEAD_AES_SIV_CMAC_384 747 The AES-SIV-CMAC-384 AEAD algorithm works as specified in Section 2.6 748 and Section 2.7. The input and output lengths for AES-SIV-CMAC-384 749 as defined by [RFC5116] are: 751 K_LEN is 48 octets. 753 P_MAX is 2^68 octets. 755 A_MAX is unlimited. 757 N_MIN is 1 octet. 759 N_MAX is unlimited. 761 C_MAX is 2^68 + 16 octets. 763 The security implications of nonce re-use and/or mis-use are 764 described in Section 1.3.2. 766 6.3. AEAD_AES_SIV_CMAC_512 768 The AES-SIV-CMAC-512 AEAD algorithm works as specified in Section 2.6 769 and Section 2.7. The input and output lengths for AES-SIV-CMAC-512 770 as defined by [RFC5116] are: 772 K_LEN is 64 octets. 774 P_MAX is 2^68 octets. 776 A_MAX is unlimited. 778 N_MIN is 1 octet. 780 N_MAX is unlimited. 782 C_MAX is 2^68 + 16 octets. 784 The security implications of nonce re-use and/or mis-use are 785 described in Section 1.3.2. 787 7. Security Considerations 789 SIV provides confidentiality in the sense that the output of SIV- 790 Encrypt is indistinguishable from a random string of bits. It 791 provides authenticity in the sense that an attacker is unable to 792 construct a string of bits that will return other than FAIL when 793 input to SIV-Decrypt. A proof of the security of SIV with an "all in 794 one" notion of security for an authenticated encryption scheme is 795 provided in [DAE]. 797 SIV provides deterministic "key wrapping" when the plaintext contains 798 data that is unpredictable to an adversary (for instance, a 799 cryptographic key). Even when this key is made available to an 800 attacker the output of SIV-Encrypt is indistinguishable from random 801 bits. Similarly, even when this key is made available to an 802 attacker, she is unable to construct a string of bits that when input 803 to SIV-Decrypt will return anything other than FAIL. 805 When the nonce used in the nonce-based authenticated encryption mode 806 of SIV-AES is treated with the care afforded a nonce or counter in 807 other conventional nonce-based authenticated encryption schemes-- 808 i.e. guarantee that it will never be used with the same key for two 809 distinct invocations-- then SIV achieves the level of security 810 described above. If, however, the nonce is reused SIV continues to 811 provide the level of authenticity described above but with a slightly 812 reduced amount of privacy (see Section 1.3.2). 814 If S2V is used as a key derivation function, the secret input MUST be 815 generated uniformly at random. S2V is a pseudo-random function and 816 is not suitable for use as a random oracle as defined in [RANDORCL]. 818 The security bound set by the proof of security of S2V in [DAE] 819 depends on the number of vector-based queries made by an adversary 820 and the total number of all components in those queries. The 821 security is only proven when the number of components in each query 822 is limited to n-1, where n is the blocksize of the underlying pseudo- 823 random function. The underlying pseudo-random function used here is 824 based on AES whose blocksize is 128 bits. Therefore S2V must not be 825 passed more than 127 components. Since SIV includes the plaintext as 826 a component to S2V that limits the number of components of associated 827 data that can be safely passed to SIV to 126. 829 8. Acknowledgments 831 Thanks to Phil Rogaway for patiently answering numerous questions on 832 SIV and S2V and for useful critiques of earlier versions of this 833 paper. Thanks also to David McGrew for numerous helpful comments and 834 suggestions for improving this paper. Thanks to Jouni Malinen for 835 reviewing this paper and producing another independent implementation 836 of SIV, thereby confirming the correctness of the test vectors. 838 9. References 840 9.1. Normative References 842 [CMAC] Dworkin, M., "Recommendation for Block Cipher Modes of 843 Operation: The CMAC Mode for Authentication", NIST Special 844 Pulication 800-38B, May 2005. 846 [MODES] Dworkin, M., "Recommendation for Block Cipher Modes of 847 Operation: Methods and Techniques", NIST Special 848 Pulication 800-38A, 2001 edition. 850 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 851 Requirement Levels", BCP 14, RFC 2119, March 1997. 853 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated 854 Encryption", RFC 5116, January 2008. 856 9.2. Informative References 858 [APPCRY] Menezes, A., van Oorshot, P., and S. Vanstone, "Handbook 859 of Applied Cryptography", CRC Press Series on Discrete 860 Mathematics and Its Applications, 1996. 862 [BADESP] Bellovin, S., "Problem Areas for the IP Security 863 Protocols", July 1996. 865 [CCM] Whiting, D., Housley, R., and N. Ferguson, "Counter With 866 CBC-MAC (CCM)", June 2002. 868 [DAE] Rogaway, P. and T. Shrimpton, "Deterministic Authenticated 869 Encryption, A Provable-Security Treatment of the Key-Wrap 870 Problem", Advances in Cryptology -- EUROCRYPT '06 St. 871 Petersburg, Russia, 2006. 873 [GCM] McGrew, D. and J. Viega, "The Galois/Counter Mode of 874 Operation (GCM)". 876 [JUTLA] Jutla, C., "Encryption Modes With Almost Free Message 877 Integrity", Proceedings of the International Conference on 878 the Theory and Application of Cryptographic Techniques: 879 Advances in Cryptography. 881 [OCB] Korvetz, T. and P. Rogaway, "The OCB Authenticated 882 Encryption Algorithm", 883 Internet-Draft: draft-krovetz-ocb-00.txt (a work in 884 progress). 886 [RADKEY] Zorn, G., "RADIUS Attributes for the Delivery of Keying 887 Material", 888 Internet-Draft: draft-zorn-radius-keywrap-13.txt (a work 889 in progress). 891 [RANDORCL] 892 Bellare, M. and P. Rogaway, "Random Oracles are Practicle: 893 A Paradigm for Designing Efficient Protocols", Proceeding 894 of the First ACM Conference on Computer and COmmunications 895 Security ACM, November 1993. 897 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 898 Hashing for Message Authentication", RFC 2104, 899 February 1997. 901 [RFC2548] Zorn, G., "Microsoft Vendor-specific RADIUS Attributes", 902 RFC 2548, March 1999. 904 [RFC2865] Rigney, C., Williams, S., Rubens, A., and W. Simpson, 905 "Remote Authentication Dial In User Service", RFC 2865, 906 June 2000. 908 [RFC3217] Housley, R., "Triple-DES and RC2 Key Wrapping", RFC 3217, 909 December 2001. 911 [RFC3394] Schaad, J. and R. Housley, "Advanced Encryption Standard 912 (AES) Key Wrap Algorithm", RFC 3394, February 2005. 914 [SP800-38D] 915 Dworkin, M., "Recommendations for Block Cipher Modes of 916 Operation: Galois Counter Mode (GCM) and GMAC", NIST 917 Special Pulication 800-38D, June 2007. 919 [VIRT] Garfinkel, T. and M. Rosenblum, "When Virtual is Harder 920 than Real: Security Challenges in Virtual Machine Based 921 Computing Environments". 923 [WLAN] "Draft Standard for IEEE802.11: Wireless LAN Medium Access 924 Control (MAC) and Physical Layer (PHY) Specification", 925 2007. 927 [X9F1] Dworkin, M., "Wrapping of Keys and Associated Data", 928 Request for review of key wrap algorithms. Cryptology 929 ePrint report 2004/340, 2004. Contents are excerpts from a 930 draft standard of the Accredited Standards Committee, X9, 931 entitled ANS X9.102. 933 Appendix A. Test Vectors 935 The following test vectors are for the mode defined in Section 6.1. 937 A.1. Deterministic Authenticated Encryption Example 939 Input: 940 ----- 941 Key: 942 fffefdfc fbfaf9f8 f7f6f5f4 f3f2f1f0 943 f0f1f2f3 f4f5f6f7 f8f9fafb fcfdfeff 945 AD: 946 10111213 14151617 18191a1b 1c1d1e1f 947 20212223 24252627 949 Plaintext: 950 11223344 55667788 99aabbcc ddee 952 S2V-CMAC-AES 953 ------------ 954 CMAC(zero): 955 0e04dfaf c1efbf04 01405828 59bf073a 957 double(): 958 1c09bf5f 83df7e08 0280b050 b37e0e74 960 CMAC(ad): 962 f1f922b7 f5193ce6 4ff80cb4 7d93f23b 964 xor: 965 edf09de8 76c642ee 4d78bce4 ceedfc4f 967 double(): 968 dbe13bd0 ed8c85dc 9af179c9 9ddbf819 970 pad: 971 11223344 55667788 99aabbcc ddee8000 973 xor: 974 cac30894 b8eaf254 035bc205 40357819 976 CMAC(final): 977 85632d07 c6e8f37f 950acd32 0a2ecc93 979 CTR-AES 980 ------- 981 CTR: 982 85632d07 c6e8f37f 150acd32 0a2ecc93 984 E(K,CTR): 985 51e218d2 c5a2ab8c 4345c4a6 23b2f08f 987 ciphertext: 988 40c02b96 90c4dc04 daef7f6a fe5c 990 output 991 ------ 992 IV || C: 993 85632d07 c6e8f37f 950acd32 0a2ecc93 994 40c02b96 90c4dc04 daef7f6a fe5c 996 A.2. Nonce-based Authenticated Encryption Example 998 Input: 999 ----- 1000 Key: 1001 7f7e7d7c 7b7a7978 77767574 73727170 1002 40414243 44454647 48494a4b 4c4d4e4f 1004 AD1: 1005 00112233 44556677 8899aabb ccddeeff 1006 deaddada deaddada ffeeddcc bbaa9988 1007 77665544 33221100 1009 AD2: 1011 10203040 50607080 90a0 1013 Nonce: 1014 09f91102 9d74e35b d84156c5 635688c0 1016 Plaintext: 1017 74686973 20697320 736f6d65 20706c61 1018 696e7465 78742074 6f20656e 63727970 1019 74207573 696e6720 5349562d 414553 1021 S2V-CMAC-AES 1022 ------------ 1023 CMAC(zero): 1024 c8b43b59 74960e7c e6a5dd85 231e591a 1026 double(): 1027 916876b2 e92c1cf9 cd4bbb0a 463cb2b3 1029 CMAC(ad1) 1030 3c9b689a b41102e4 80954714 1dd0d15a 1032 xor: 1033 adf31e28 5d3d1e1d 4ddefc1e 5bec63e9 1035 double(): 1036 5be63c50 ba7a3c3a 9bbdf83c b7d8c755 1038 CMAC(ad2) 1039 d98c9b0b e42cb2d7 aa98478e d11eda1b 1041 xor: 1042 826aa75b 5e568eed 3125bfb2 66c61d4e 1044 double(): 1045 04d54eb6 bcad1dda 624b7f64 cd8c3a1b 1047 CMAC(nonce) 1048 128c62a1 ce3747a8 372c1c05 a538b96d 1050 xor: 1051 16592c17 729a5a72 55676361 68b48376 1053 xorend: 1054 74686973 20697320 736f6d65 20706c61 1055 696e7465 78742074 6f20656e 63727966 1056 2d0c6201 f3341575 342a3745 f5c625 1058 CMAC(final) 1059 7bdb6e3b 432667eb 06f4d14b ff2fbd0f 1061 CTR-AES 1062 ------- 1063 CTR: 1064 7bdb6e3b 432667eb 06f4d14b 7f2fbd0f 1066 E(K,CTR): 1067 bff8665c fdd73363 550f7400 e8f9d376 1069 CTR+1: 1070 7bdb6e3b 432667eb 06f4d14b 7f2fbd10 1072 E(K,CTR+1): 1073 b2c9088e 713b8617 d8839226 d9f88159 1075 CTR+2 1076 7bdb6e3b 432667eb 06f4d14b 7f2fbd11 1078 E(K,CTR+2): 1079 9e44d827 234949bc 1b12348e bc195ec7 1081 ciphertext: 1082 cb900f2f ddbe4043 26601965 c889bf17 1083 dba77ceb 094fa663 b7a3f748 ba8af829 1084 ea64ad54 4a272e9c 485b62a3 fd5c0d 1086 output 1087 ------ 1088 IV || C: 1089 7bdb6e3b 432667eb 06f4d14b ff2fbd0f 1090 cb900f2f ddbe4043 26601965 c889bf17 1091 dba77ceb 094fa663 b7a3f748 ba8af829 1092 ea64ad54 4a272e9c 485b62a3 fd5c0d 1094 Author's Address 1096 Dan Harkins 1097 Aruba Networks 1099 Email: dharkins@arubanetworks.com 1101 Full Copyright Statement 1103 Copyright (C) The IETF Trust (2008). 1105 This document is subject to the rights, licenses and restrictions 1106 contained in BCP 78, and except as set forth therein, the authors 1107 retain all their rights. 1109 This document and the information contained herein are provided on an 1110 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1111 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1112 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1113 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1114 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1115 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1117 Intellectual Property 1119 The IETF takes no position regarding the validity or scope of any 1120 Intellectual Property Rights or other rights that might be claimed to 1121 pertain to the implementation or use of the technology described in 1122 this document or the extent to which any license under such rights 1123 might or might not be available; nor does it represent that it has 1124 made any independent effort to identify any such rights. Information 1125 on the procedures with respect to rights in RFC documents can be 1126 found in BCP 78 and BCP 79. 1128 Copies of IPR disclosures made to the IETF Secretariat and any 1129 assurances of licenses to be made available, or the result of an 1130 attempt made to obtain a general license or permission for the use of 1131 such proprietary rights by implementers or users of this 1132 specification can be obtained from the IETF on-line IPR repository at 1133 http://www.ietf.org/ipr. 1135 The IETF invites any interested party to bring to its attention any 1136 copyrights, patents or patent applications, or other proprietary 1137 rights that may cover technology that may be required to implement 1138 this standard. Please address the information to the IETF at 1139 ietf-ipr@ietf.org. 1141 Acknowledgment 1143 Funding for the RFC Editor function is provided by the IETF 1144 Administrative Support Activity (IASA).