idnits 2.17.1 draft-krovetz-vmac-01.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 14. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 905. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 923. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 929. ** The document seems to lack an RFC 3979 Section 5, para. 1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard 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 "Author's Address" (or "Authors' Addresses") section title is misspelled. == Line 798 has weird spacing: '...hen the recei...' -- 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 (April 2007) is 6214 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. '1' Summary: 2 errors (**), 0 flaws (~~), 4 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG Working Group Ted Krovetz 3 INTERNET-DRAFT CSU Sacramento 4 Expires October 2007 Wei Dai 5 Bitvise Limited 6 April 2007 8 VMAC: Message Authentication Code using Universal Hashing 9 11 By submitting this Internet-Draft, each author represents that any 12 applicable patent or other IPR claims of which he or she is aware 13 have been or will be disclosed, and any of which he or she becomes 14 aware will be disclosed, in accordance with Section 6 of BCP 79. 16 Status of this Memo 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/1id-abstracts.html 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Abstract 36 This specification describes how to generate an authentication tag 37 using the VMAC message authentication algorithm. VMAC is designed to 38 have exceptional performance in software on 64-bit CPU architectures 39 while still performing well on 32-bit architectures. Measured speeds 40 are as fast as one-half CPU cycle per byte (cpb) on 64-bit 41 architectures, under five cpb on desktop 32-bit processors, and 42 around ten cpb on embedded 32-bit architectures. 44 Table of Contents 46 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 47 2 Notation and basic operations . . . . . . . . . . . . . . . . . . 4 48 2.1 Operations on strings . . . . . . . . . . . . . . . . . . . 4 49 2.2 Operations on integers . . . . . . . . . . . . . . . . . . . 5 50 2.3 String-Integer conversion operations . . . . . . . . . . . . 5 51 2.4 Mathematical operations on strings . . . . . . . . . . . . . 6 52 2.5 ENDIAN-SWAP: Adjusting endian orientation . . . . . . . . . 6 53 3 Key and pad derivation functions . . . . . . . . . . . . . . . . 7 54 3.1 Block cipher choice . . . . . . . . . . . . . . . . . . . . 7 55 3.2 KDF: Key-derivation function . . . . . . . . . . . . . . . . 7 56 3.3 PDF: Pad-derivation function . . . . . . . . . . . . . . . . 8 57 4 VMAC tag generation . . . . . . . . . . . . . . . . . . . . . . . 9 58 4.1 VMAC Algorithm . . . . . . . . . . . . . . . . . . . . . . . 9 59 4.2 VMAC-64 and VMAC-128 . . . . . . . . . . . . . . . . . . . . 10 60 5 VHASH: Universal hash function . . . . . . . . . . . . . . . . . 10 61 5.1 VHASH Constants . . . . . . . . . . . . . . . . . . . . . . 10 62 5.2 VHASH Algorithm . . . . . . . . . . . . . . . . . . . . . . 11 63 5.3 L1-HASH: First-layer hash . . . . . . . . . . . . . . . . . 11 64 5.4 L2-HASH: Second-layer hash . . . . . . . . . . . . . . . . . 13 65 5.5 L3-HASH: Third-layer hash . . . . . . . . . . . . . . . . . 14 66 6 Security considerations . . . . . . . . . . . . . . . . . . . . . 15 67 6.1 Resistance to cryptanalysis . . . . . . . . . . . . . . . . 15 68 6.2 Tag lengths and forging probability . . . . . . . . . . . . 16 69 6.3 Nonce considerations . . . . . . . . . . . . . . . . . . . . 17 70 6.4 Replay attacks . . . . . . . . . . . . . . . . . . . . . . . 18 71 7 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 18 72 Appendix - Test vectors . . . . . . . . . . . . . . . . . . . . . . 19 73 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 74 Author contact information . . . . . . . . . . . . . . . . . . . . . 20 75 Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . . 20 76 Intellectual Property . . . . . . . . . . . . . . . . . . . . . . . 21 77 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . 21 78 1 Introduction 80 VMAC is a message authentication code (MAC) algorithm designed for 81 high performance. It is backed by a formal analysis, and there are 82 no intellectual property claims made by any of the authors to any 83 ideas used in its design. 85 VMAC is a MAC in the style of Wegman and Carter [4, 8]. A fast 86 "universal" hash function is used to hash an input message M into a 87 short string. This short string is then combined by addition with a 88 pseudorandom pad, resulting in the VMAC tag. Security depends on the 89 sender and receiver sharing a randomly-chosen secret hash function 90 and pseudorandom pad. This is achieved by using keyed hash function 91 H and pseudorandom function F. A tag is generated by performing the 92 computation 94 Tag = H_K1(M) + F_K2(Nonce) 96 where K1 and K2 are secret random keys shared by sender and receiver, 97 and Nonce is a value that changes with each generated tag. The 98 receiver needs to know which nonce was used by the sender, so some 99 method of synchronizing nonces needs to be used. This can be done by 100 explicitly sending the nonce along with the message and tag, or 101 agreeing upon the use of some other non-repeating value such as a 102 sequence number. The nonce need not be kept secret, but care needs 103 to be taken to ensure that, over the lifetime of a VMAC key, a 104 different nonce is used with each message. 106 VMAC uses a function, called VHASH (also specified in this document), 107 as the keyed hash function H and uses a pseudorandom function F whose 108 default implementation uses the AES block cipher. VMAC allows for 109 tag lengths of any 64-bit multiple up to the block size of the block 110 cipher in use. When using AES, this means VMAC can produce 64- or 111 128-bit tags. 113 The theory of Wegman-Carter MACs and the analysis of VMAC show that 114 if one "instantiates" VMAC with truly random keys and pads then the 115 probability that an attacker (even a computationally unbounded one) 116 produces a correct tag for messages of its choosing is less than 117 1/2^60 or 1/2^120 when the tags are of length 64 or 128 bits, 118 respectively (here the symbol ^ represents exponentiation). When an 119 attacker makes N forgery attempts the probability of getting one or 120 more tags right increases linearly to less than N/2^60 or N/2^120. 121 In a real implementation of VMAC, using AES to produce keys and pads, 122 these forgery probabilities increase by a small amount related to the 123 security of AES. As long as AES is secure, this small additive term 124 is insignificant for any practical attack. See Section 6.2 for more 125 details. Analysis relevant to VMAC security is in [5, 6]. 127 VMAC performs best in environments where 64-bit quantities are 128 efficiently read from memory "little-endian" and multiplied into 129 128-bit results. Performance on 32-bit architechtures suppporting 130 Intel's SSE2 instruction-set is also very good. On other 32-bit 131 architectures, each 64-bit multiplication is accomplished via four 132 32-bit multiplications, resulting in a corresponding slowdown. The 133 data in the following table were generated using the reference 134 implementation available at the VMAC website [7]. The table shows 135 sample performance on several architectures over message lengths of 136 64, 512 and 4096 bytes. 138 64-bit Tags 128-bit Tags 139 Bits/Endian/Architecture 64 512 4K 64 512 4K 140 ---------------------------------+-----+----+-----+-----+----+---- 141 64/LE/AMD Athlon 64 "Manchester" | 6.0 1.1 0.5 | 7.0 1.6 0.9 142 64/LE/Intel Core 2 "Merom" | 5.9 1.2 0.6 | 6.9 1.7 1.1 143 64/BE/IBM PowerPC 970FX | 10.1 2.5 1.6 | 11.4 3.8 3.0 144 32/LE/Intel Core 2 "Merom" | 8.3 2.2 1.4 | 11.1 3.6 2.8 145 32/LE/Intel NetBurst "Nocona" | 15.0 4.4 3.1 | 18.9 7.1 5.8 146 32/BE/Freescale PowerPC 7457 | 15.3 6.4 5.3 | 22.1 11.2 10.0 147 32/LE/Embedded ARM v5te core | 39.9 13.1 10.1 | 53.6 22.9 19.8 148 ---------------------------------+-----+----+-----+-----+----+---- 149 Table: Tag generation speed measured in CPU cycles per message 150 byte, for cache-resident messages of length 64, 512 and 4K bytes. 151 Architechtures are listed as register-size/endianness/model. 153 2 Notation and basic operations 155 The specification of VMAC involves the manipulation of strings and 156 numbers. String variables are denoted with an initial upper-case 157 letter, whereas numeric variables are denoted in all lower case. The 158 algorithms of VMAC are denoted in all upper-case letters. Simple 159 functions, such as for string-length, are written in all lower case. 161 Whenever a variable is followed by an underscore ("_"), the 162 underscore is intended to denote a subscript, with the subscripted 163 expression evaluated to resolve the meaning of the variable. For 164 example, if i=2, then M_{2 * i} refers to the variable M_4. 166 2.1 Operations on strings 168 Messages to be hashed are viewed as strings of bits. The following 169 notation is used to manipulate these strings. 171 bitlength(S): The length of string S in bits. 173 zeros(n): The string made of n zero-bits. 175 S[i]: The i-th bit of the string S (indices begin at 1). 177 S[i...j]: The substring of S consisting of bits i through j. 179 S || T: The string S concatenated with string T. 181 zeropad(S,n): The string S, padded with zero-bits to the nearest 182 multiple of n bits in length. If S is empty or 183 already a multiple of n in length, nothing is 184 appended. Formally, zeropad(S,n) = S || T, where T 185 is the shortest string of zero-bits so that 186 bitlength(S || T) is a multiple of n. 188 2.2 Operations on integers 190 Standard notation is used for most mathematical operations, such as 191 "*" for multiplication, "+" for addition and "mod" for modular 192 reduction. Some less standard notations are defined here. 194 a^i: The integer a raised to the i-th power. 196 ceil(x): The smallest integer not less than x. 198 floor(x): The largest integer not greater than x. 200 a div b: The largest integer i for which b * i <= a. 202 2.3 String-Integer conversion operations 204 Conversion between strings and integers is done using the following 205 functions. Each function treats initial bits as more significant 206 than later ones. 208 str2uint(S): The non-negative integer whose binary representation 209 is the string S. More formally, if S is t bits long 210 then str2uint(S) = 2^{t-1} * S[1] + 2^{t-2} * S[2] + 211 ... + 2^{1} * S[t-1] + S[t]. 213 uint2str(n,i): The i-bit string S so that str2uint(S) = n. 215 2.4 Mathematical operations on strings 217 One of the primary operations in VMAC is addition and multiplication 218 of strings. The operations "+_64", "+_128" and "*_128" are defined 220 "S +_64 T" as uint2str(str2uint(S) + str2uint(T) mod 2^64, 64), 221 "S +_128 T" as uint2str(str2uint(S) + str2uint(T) mod 2^128, 128), 222 "S *_128 T" as uint2str(str2uint(S) * str2uint(T) mod 2^128, 128). 224 On many 64-bit architectures, these operations can each be 225 implemented with one or two assembly-language instructions. 227 2.5 ENDIAN-SWAP: Adjusting endian orientation 229 Message data is normally read little-endian to speed tag generation 230 on little-endian computers. 232 2.5.1 ENDIAN-SWAP Algorithm 234 Input: 235 S, string with bitlength divisible by 64. 236 Output: 237 T, string S with each 64-bit substring endian-reversed. 239 Compute T using the following algorithm. 241 // 242 // Partition S into 64-bit substrings 243 // 244 n = bitlength(S) / 64 245 Let S_1, S_2, ..., S_n be strings of length 64 bits 246 so that S_1 || S_2 || ... || S_n = S. 248 // 249 // Endian-reverse each, and build-up T 250 // 251 T = 252 for i = 1 to n do 253 Let W_1, W_2, ..., W_8 be strings of length 8 bits 254 so that W_1 || W_2 || ... || W_8 = S_i 255 SReversed_i = W_8 || W_7 || ... || W_1 256 T = T || SReversed_i 257 end for 259 Return T 261 3 Key and pad derivation functions 263 Pseudorandom bits are needed internally by VHASH and at the time of 264 tag generation. The functions listed in this section use a block 265 cipher to generate these bits. 267 3.1 Block cipher choice 269 VMAC uses the services of a block cipher. The selection of a block 270 cipher defines the following constants and functions. 272 BLOCKLEN The length, in bits, of the plaintext block on which 273 the block cipher operates. 275 KEYLEN The block cipher's key length, in bits. 277 ENCIPHER(K,P) The application of the block cipher on P (a string of 278 BLOCKLEN bits) using key K (a string of KEYLEN bits). 280 As an example, if AES is used with 192-bit keys, then BLOCKLEN would 281 equal 128 (because AES employs 128-bit blocks), KEYLEN would equal 282 192, and ENCIPHER would refer to the AES block encryption function 283 for 192-bit AES keys. 285 Unless specified otherwise, AES with 128-bit keys shall be assumed to 286 be the chosen block cipher for VMAC. In any case, BLOCKLEN must be 287 at least 128. AES is defined in another document [1]. 289 3.2 KDF: Key-derivation function 291 The key-derivation function generates pseudorandom bits used by the 292 hash function. 294 3.2.1 KDF Algorithm 296 Input: 297 K, string of length KEYLEN bits. 298 index, an integer in the range 0...255. 299 numbits, a non-negative integer. 300 Output: 301 Y, string of length numbits bits. 303 Compute Y using the following algorithm. 305 // 306 // Calculate number of block cipher iterations 307 // 308 n = ceil(numbits / BLOCKLEN) 310 // 311 // Build Y using block cipher in a counter mode 312 // 313 Y = 314 for i = 0 to (n-1) do 315 T = uint2str(index, 8) || uint2str(i, BLOCKLEN-8) 316 Y = Y || ENCIPHER(K, T) 317 end for 318 Y = Y[1...numbits] 320 Return Y 322 3.3 PDF: Pad-derivation function 324 This function takes a key and a nonce and returns a pseudorandom pad 325 for use in tag generation. The length of the pad can be any positive 326 multiple of 64 bits, up to BLOCKLEN bits. Notice that when the 327 block-cipher block-length is twice as long as the pad, nonces that 328 differ only in their last bit are derived from the same block cipher 329 encryption. This allows caching and sharing a single block cipher 330 invocation for sequential nonces. 332 3.3.1 PDF Algorithm 334 Input: 335 K, string of length KEYLEN bits. 336 Nonce, string of length less than BLOCKLEN bits. 337 taglen, positive multiple of 64, no greater than BLOCKLEN. 338 Output: 339 Y, string of length taglen bits. 341 Compute Y using the following algorithm. 343 // 344 // Extract and zero low bits of Nonce if needed. 345 // If BLOCKLEN/taglen < 2, this step does nothing but set index=0 346 // 347 Let i be the smallest integer for which BLOCKLEN/taglen <= 2^i 348 index = str2uint(Nonce) mod 2^i 349 Nonce = Nonce[1...bitlength(Nonce)-i] || zeros(i) 351 // 352 // Make Nonce BLOCKLEN bits by prepending zeros. 353 // At least one zero bit is prepended here. 354 // 355 Nonce = zeros(BLOCKLEN - bitlength(Nonce)) || Nonce 357 // 358 // Encipher and extract indexed substring 359 // 360 T = ENCIPHER(K, Nonce) 361 Y = T[index * taglen + 1 ... index * taglen + taglen ] 363 Return Y 365 4 VMAC tag generation 367 Tag generation for VMAC proceeds by using VHASH (defined in the next 368 section) to hash the message, applying the PDF to the nonce and then 369 computing the addition of the resulting strings. The length of the 370 pad and hash can be any positive multiple of 64 bits, up to BLOCKLEN 371 bits. 373 4.1 VMAC Algorithm 375 Input: 376 K, string of length KEYLEN bits. 377 M, string of length up to 2^64 bits. 378 Nonce, string of length less than BLOCKLEN bits. 379 taglen, positive multiple of 64, no greater than BLOCKLEN. 380 Output: 381 Tag, string of length taglen bits. 383 Compute Tag using the following algorithm. 385 HashedMessage = VHASH(K, M, taglen) 386 Pad = PDF(K, Nonce, taglen) 388 Tag = 389 for i = 0 to (taglen/64 - 1) do 390 T = Pad [1 + 64 * i ... 64 * (i + 1)] +_64 391 HashedMessage[1 + 64 * i ... 64 * (i + 1)] 392 Tag = Tag || T 393 end for 395 Return Tag 397 4.2 VMAC-64 and VMAC-128 399 The preceding VMAC definition has a parameter "taglen" which 400 specifies the length of tag generated by the algorithm. The 401 following aliases define names that make tag length explicit in the 402 name. 404 VMAC-64(K, M, Nonce) = VMAC(K, M, Nonce, 64) 405 VMAC-128(K, M, Nonce) = VMAC(K, M, Nonce, 128) 407 5 VHASH: Universal hash function 409 VHASH is a keyed hash function, which takes as input a string and 410 produces a string output with length that is a multiple of 64 bits. 411 VHASH is a three-layered hash function. A message is first hashed by 412 L1-HASH, its output is then hashed by L2-HASH, whose output is then 413 hashed by L3-HASH. This process is done once for each 64 bits of 414 output. 416 Note that VHASH has certain combinatoric properties making it 417 suitable for Wegman-Carter message authentication. VHASH is not a 418 cryptographic hash function and is not a suitable general replacement 419 for functions like SHA-1. 421 VHASH is presented here in a top-down manner. First VHASH is 422 described, then each of its component hashes are presented. 424 5.1 VHASH Constants 426 The following constants are referred to in the definition of VHASH. 427 L1KEYLEN defines how many bits of key material are generated 428 internally for the first layer of hashing. FAVOR-ENDIAN determines 429 which endian orientation is used to read messages. 431 L1KEYLEN = 1024 432 FAVOR-ENDIAN = LITTLE 434 One could change L1KEYLEN to any positive multiple of 128 or change 435 FAVOR-ENDIAN to BIG. A larger L1KEYLEN improves the speed of the 436 algorithms at the cost of increased memory usage, and changing FAVOR- 437 ENDIAN to BIG improves the speed of the algorithms on big-endian 438 machines at the cost of decreased speed on little-endian machines. 439 The resulting algorithms would be incompatible with the VMAC and 440 VHASH algorithms defined here, but might be useful in custom 441 applications. 443 5.2 VHASH Algorithm 445 Input: 446 K, string of length KEYLEN bits. 447 M, string of length up to 2^64 bits. 448 taglen, positive multiple of 64. 449 Output: 450 Y, string of length taglen bits. 452 Compute Y using the following algorithm. 454 Y = 455 for i = 0 to (taglen/64 - 1) do 456 A = L1-HASH(K, M, i) 457 B = L2-HASH(K, A, bitlength(M), i) 458 Y = Y || L3-HASH(K, B, i) 459 end for 461 Return Y 463 5.3 L1-HASH: First-layer hash 465 The first-layer hash breaks the message into blocks, each of length 466 up to L1KEYLEN (normally defined as 1024 bits), and hashes each with 467 a function called NH. Concatenating the results forms a string which 468 is shorter than the original (unless the original length was no 469 greater than 128 bits). 471 5.2.1 L1-HASH Algorithm 473 Input: 474 K, string of length KEYLEN bits. 475 M, string of any length. 476 iter, non-negative integer. 477 Output: 478 Y, string of length ceil(bitlength(M)/L1KEYLEN) * 128 bits. 480 Compute Y using the following algorithm. 482 // 483 // Set subkey for L1-HASH 484 // 485 T = KDF(K, 128, L1KEYLEN + 128 * iter) 486 K = T[1 + 128 * iter ... L1KEYLEN + 128 * iter] 487 Y = 488 if bitlength(M) > 0 then 490 // 491 // Break M into L1KEYLEN-bit segments (last one may be shorter) 492 // 493 t = ceil(bitlength(M) / L1KEYLEN) 494 Let M_1, M_2, ..., M_t be strings so that M_1 || M_2 || ... 495 || M_t = M, and bitlength(M_i) = L1KEYLEN for all 0 < i < t. 497 // 498 // For each segment: pad, endian-adjust, NH hash, and use 499 // results to build output Y. Note that padding only effects 500 // the final segment because all other segment lengths are 501 // already a multiple of 128. 502 // 503 for i = 1 to t do 504 M_i = zeropad(M_i, 128) 505 if FAVOR-ENDIAN = LITTLE then 506 ENDIAN-SWAP(M_i) 507 end if 508 Y = Y || NH(K, M_i) 509 end for 511 end if 513 Return Y 515 5.2.2 NH Algorithm 517 Because this routine is applied directly to every bit of input data, 518 an optimized implementation of it yields great benefit. 520 Input: 521 K, string with length a multiple of 128 bits. 522 M, string with length a multiple of 128 bits, but no longer than K. 523 Output: 524 Y, string of length 128 bits. 526 Compute Y using the following algorithm. 528 // 529 // Partition M and K into 64-bit substrings 530 // 531 t = bitlength(M) / 64 532 Let M_1, M_2, ..., M_t be 64-bit strings 533 so that M = M_1 || M_2 || ... || M_t. 534 Let K_1, K_2, ..., K_t be 64-bit strings 535 so that K_1 || K_2 || ... || K_t is a prefix of K. 537 // 538 // Perform NH hash on each. 539 // 540 Y = zeros(128) 541 i = 1 542 while (i < t) do 543 Y = Y +_128 ((M_i +_64 K_i) *_128 (M_{i+1} +_64 K_{i+1})) 544 i = i + 2 545 end while 546 Y = zeros(2) || Y[3...128] // Zero two bits (ie, mod 2^126) 548 Return Y 550 5.4 L2-HASH: Second-layer hash 552 The second-layer rehashes the L1-HASH output using a polynomial hash. 554 5.3.1 L2-HASH Algorithm 556 Input: 557 K, string of length KEYLEN bits. 558 M, string with length a multiple of 128 bits. 559 len, non-negative integer. 560 iter, non-negative integer. 561 Output: 562 Y, string of length 128 bits. 564 Compute y using the following algorithm. 566 // 567 // Create subkey - the (iter+1)'st 128-bit chunk of the 568 // string generated by KDF(K, 192) 569 // 570 T = KDF(K, 192, 128 * (iter + 1)) 571 T = T[1 + 128 * iter ... 128 * (iter + 1)] 572 k = str2uint(zeros(3) || T[ 4...32] || zeros(3) || T[ 36... 64] || 573 zeros(3) || T[68...96] || zeros(3) || T[100...128]) 575 n = bitlength(M) / 128 576 if n > 0 then 578 // 579 // Partition M into 128-bit substrings and polynomial hash 580 // 581 Let M_1, M_2, ..., M_n be strings of length 128 bits 582 so that M = M_1 || M_2 || ... || M_n 584 p127 = 2^127 - 1 // 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF in hex 585 y = 1 586 for i = 1 to n do 587 m_i = str2uint(M_i) 588 y = (y * k + m_i) mod p127 589 end for 591 else 593 // 594 // M is an empty string; handled as a special case 595 // 596 y = k 598 end if 600 y = (y + (len mod L1KEYLEN) * 2^64) mod p127 601 Y = uint2str(y, 128) 603 Return Y 605 5.5 L3-HASH: Third-layer hash 607 The output from L2-HASH is 128 bits long. This final hash function 608 hashes the 128-bit string to a fixed length of 64 bits. 610 5.4.1 L3-HASH Algorithm 612 Input: 613 K, string of length KEYLEN bits. 614 M, string of length 128 bits. 615 iter, non-negative integer. 616 Output: 617 Y, string of length 64 bits. 619 Compute Y using the following algorithm. 621 // 622 // Create subkey - the (iter+1)'st 128-bit chunk of the 623 // string generated by KDF(K, 224) that passes a test 624 // 625 p64 = 2^64 - 257 // 0xFFFFFFFFFFFFFEFF in hex 626 i = 0 627 need = iter + 1 628 repeat 629 T = KDF(K, 224, 128 * (i + 1)) 630 T = T[1 + 128 * i ... 128 * (i + 1)] 631 k_1 = str2uint(T[ 0... 64]) 632 k_2 = str2uint(T[65...128]) 633 i = i + 1 634 if (k_1 < p64) and (k_2 < p64) then 635 need = need - 1 636 end if 637 until (need = 0) 639 // 640 // Transform M into two integers less than p64 and hash 641 // 642 m_1 = str2uint(M) div (2^64 - 2^32) 643 m_2 = str2uint(M) mod (2^64 - 2^32) 644 y = ((m_1 + k_1) * (m_2 + k_2)) mod p64 645 Y = uint2str(y, 64) 647 Return Y 649 6 Security considerations 651 Here we describe some security considerations important for the 652 proper understanding and use of VMAC. 654 6.1 Resistance to cryptanalysis 656 The strength of VMAC depends on the strength of its underlying 657 cryptographic functions: the key-derivation function (KDF) and the 658 pad-derivation function (PDF). In this specification both operations 659 are implemented using a block cipher, by default the Advanced 660 Encryption Standard (AES). However, the core of the VMAC design, the 661 VHASH function, does not depend on cryptographic assumptions: its 662 strength is specified by a purely mathematical property stated in 663 terms of collision probability, and this property is proven 664 unconditionally [5, 6]. This means the strength of VHASH is 665 guaranteed regardless of advances in cryptanalysis and that an 666 adversarial attack on VMAC that forges with probability significantly 667 exceeding the established collision probability of VHASH will give 668 rise to an attack of comparable complexity which breaks the block 669 cipher, in the sense of distinguishing the block cipher from a family 670 of random permutations. This design approach essentially obviates 671 the need for cryptanalysis on VMAC: cryptanalytic efforts might as 672 well focus on the block cipher. 674 6.2 Tag lengths and forging probability 676 A MAC algorithm is used to authenticate messages between two parties 677 that share a secret MAC key K. An authentication tag is computed for 678 a message using K and, in some MAC algorithms such as VMAC, a nonce. 679 Messages transmitted between parties are accompanied by their tag 680 and, possibly, nonce. Breaking the MAC means that the attacker is 681 able to generate, on its own, with no knowledge of the key K, a new 682 message M (ie, one not previously transmitted between the legitimate 683 parties) and to compute on M a correct authentication tag under the 684 key K. This is called a forgery. Note that if the authentication 685 tag is specified to be of length t then the attacker can trivially 686 break the MAC with probability 1/2^t. For this the attacker can just 687 generate any message of its choice and try a random tag; obviously, 688 the tag is correct with probability 1/2^t. By repeated guesses the 689 attacker can increase linearly its probability of success. 691 In the case of VMAC-64, for example, the above guessing-attack 692 strategy is close to optimal. An adversary can correctly guess a 693 64-bit VMAC tag with probability 1/2^64 by simply guessing a random 694 value. The theory of Wegman-Carter MACs and results of [5, 6] show 695 that no attack strategy can produce a correct tag with probability 696 better than 1/2^60 if VMAC were to use a random function in its work 697 rather than AES. Another result shows that so long as AES is secure 698 as a pseudorandom permutation, it can be used instead of a random 699 function without significantly increasing the 1/2^60 forging 700 probability, assuming that no more than 2^64 messages are 701 authenticated with the same key [2]. Similarly for VMAC-128, the 702 per-message forgery probability, when using a random function rather 703 than AES to instantiate VMAC is no more than 1/2^120. 705 AES has undergone extensive study and is assumed to be very secure as 706 a pseudorandom permutation. If we assume that no attacker with 707 feasible computational power can distinguish randomly keyed AES from 708 a randomly chosen permutation with probability delta (more precisely, 709 delta is a function of the computational resources of the attacker 710 and of its ability to sample the function), then we obtain that no 711 such attacker can forge messages in VMAC with probability greater 712 than about 1/2^60 or 1/2^120, plus delta. Over N forgery attempts, 713 forgery occurs with probability no more than N/^60 or N/2^120, plus 714 delta. The value delta could possibly be greater than 1/2^60 or 715 1/2^120, in which case the probability of VMAC forging is dominated 716 by a term representing the security of AES. 718 With VMAC, off-line computation aimed at exceeding the forging 719 probability is hopeless as long as the underlying cipher is not 720 broken. An attacker attempting to forge VMAC tags will need to 721 interact with the entity that verifies message tags and try a large 722 number of forgeries before one is likely to succeed. The system 723 architecture will determine the extent to which this is possible. In 724 a well-architected system there should not be any high-bandwidth 725 capability for presenting forged MACs and determining if they are 726 valid. 728 Let us reemphasize: a forging probability of 1/2^60 does not mean 729 that there is an attack that runs in 2^60 time; to the contrary, as 730 long as the block cipher in use is not broken there is no such attack 731 for VMAC. Instead, a 1/2^60 forging probability means that if an 732 attacker could have N forgery attempts, then the attacker would have 733 no more than N/2^60 probability of getting one or more of them right. 735 It should be pointed out that once an attacker knows that an 736 attempted forgery is successful, it is possible, in principle, that 737 subsequent messages under this key may be more easily forged. This 738 is important to understand in gauging the severity of a successful 739 forgery, even though no such attack on VMAC is known to date. Due to 740 the short-lived nature of most authentication sessions, 64-bit tags 741 are appropriate for many security architectures and applications. 742 If, however, one wants a more conservative option, at a cost of about 743 double the computation, VMAC's 128-bit tags may be more appropriate. 745 6.3 Nonce considerations 747 VMAC requires a nonce with length less than BLOCKLEN bits. All 748 nonces in an authentication session must be unique and equal in 749 length. 751 The security of VMAC depends on the assumption that no nonce is ever 752 used to generate tags for more than one message under the same key. 753 If an attacker is able to observe two VMAC tags that were generated 754 using the same key, the same nonce, and different messages, he may be 755 able to easily forge other VMAC tags. While such an attack is not 756 known to date, VMAC was not designed to offer any protection in this 757 scenario, and nonce reuse must be prevented through appropriate 758 system architecture. 760 To authenticate messages over a duplex channel (where two parties 761 send messages to each other), a different key could be used for each 762 direction. If the same key is used in both directions, then it is 763 crucial that all nonces be distinct. For example, one party can use 764 even nonces while the other party uses odd ones. The receiving party 765 must verify that the sender is using a nonce of the correct form. 767 This specification does not indicate how nonce values are created, 768 updated, or communicated between the entity producing a tag and the 769 entity verifying a tag, but there are many possibilities. Nonce 770 values could be randomly generated, could come from an incrementing 771 counter, or could be co-opted from some non-repeating part of the 772 messages being authenticated (such as a sequence number). The nonce 773 can then be sent along with the message if necessary, or if the 774 receiver is able to deduce the nonce in use, the nonce need not be 775 sent. We emphasize that the nonce need not be kept secret, but that 776 no nonce should be used more than once in any session by either 777 sender or receiver. 779 Designers of systems and applications that use VMAC should be aware 780 that modern virtual machine software such as VMware may allow the 781 user of a virtual machine to roll back its state (both persistent 782 storage and volatile memory) to earlier snapshots or checkpoints. 783 This rollback may be part of an attack, or simply due to an unrelated 784 decision by an authorized user. In any case, if VMAC is used in such 785 a virtual machine, a rollback may cause a nonce to be reused, 786 intentionally or unintentionally, thus violating an important 787 security assumption. The system or application must either prevent 788 the occurrence of a state rollback, or be designed to ensure that 789 nonces are not reused on different messages even when state rollbacks 790 are possible. For example, one possible design is to generate a 791 fresh random string as the nonce for each message, after the content 792 of that message has been fixed. 794 6.4 Replay attacks 796 A replay attack occurs when an attacker repeats a message, nonce, and 797 authentication tag. If the replay of a previously authenticated 798 message would have negative consequences, then the receiver should 799 identify repeated message-nonce pairs and ignore them. One way to do 800 this is to look for a nonce that has already been used to 801 authenticate a prior message, and ignore it. On a reliable 802 connection, when the nonce is a counter, this is trivial. On an 803 unreliable connection, when the nonce is a counter, one would 804 normally cache some window of recent nonces. Out-of-order message 805 delivery in excess of what the window allows will result in rejecting 806 otherwise valid authentication tags. We emphasize that it is up to 807 the receiver to determine when a given (message, nonce, tag) triple 808 will be deemed authentic. Certainly the tag should be valid for the 809 message and nonce, as determined by VMAC, but the message may still 810 be deemed inauthentic because the nonce is detected to be a replay. 812 7 IANA Considerations 814 This document has no actions for IANA. 816 Appendix - Test vectors 818 Following are some sample VMAC outputs over a collection of input 819 values, using AES with 128-bit keys. Let key K and nonce N be 820 defined by the following ASCII strings. 822 K = "abcdefghijklmnop" // A 128-bit VMAC key 823 N = "bcdefghi" // A 64-bit nonce 825 The tags generated by VMAC using key K and nonce N are: 827 Message 64-bit Tag 128-bit Tag 828 ------- ---------- ----------- 829 2576BE1C56D8B81B 472766C70F74ED23481D6D7DE4E80DAC 830 'abc' * 1 2D376CF5B1813CE5 4EE815A06A1D71EDD36FC75D51188A42 831 'abc' * 16 E8421F61D573D298 09F2C80C8E1007A0C12FAE19FE4504AE 832 'abc' * 100 4492DF6C5CAC1BBE 66438817154850C61D8A412164803BCB 833 'abc' * 1000000 09BA597DD7601113 2B6B02288FFC461B75485DE893C629DC 835 The first column lists a small sample of messages which are strings 836 of repeated ASCII 'abc' strings. The remaining columns give in 837 hexadecimal the tags generated when VMAC is called with the 838 corresponding message, nonce N and key K. 840 References 842 Normative References 844 [1] FIPS-197, "Advanced Encryption Standard (AES)", National 845 Institute of Standards and Technology, 2001. 847 Informative References 849 [2] D. Bernstein, "Stronger security bounds for permutations", 850 unpublished manuscript, 2005. This work refines "Stronger 851 security bounds for Wegman-Carter-Shoup authenticators", 852 Advances in Cryptology - EUROCRYPT 2005, LNCS vol. 3494, pp. 853 164-180, Springer-Verlag, 2005. 855 [3] J. Black, S. Halevi, A. Hevia, H. Krawczyk, T. Krovetz, and P. 856 Rogaway, "UMAC: Message authentication code using universal 857 hashing", RFC 4418, IETF, 2006. 859 [4] L. Carter and M. Wegman, "Universal classes of hash functions", 860 Journal of Computer and System Sciences, 18 (1979), pp. 861 143-154. 863 [5] W. Dai and T. Krovetz, "VMAC high-speed message 864 authentication", in progress. 866 [6] T. Krovetz, "Message auhentication on 64-bit architectures", 867 Selected Areas in Cryptography - SAC 2006, Springer-Verlag, 868 2006. 870 [7] VMAC Website, http://fastcrypto.com/vmac, as seen April 2007. 872 [8] M. Wegman and L. Carter, "New hash functions and their use in 873 authentication and set equality", Journal of Computer and 874 System Sciences, 22 (1981), pp. 265-279. 876 Author contact information 878 Author Addresses 880 Ted Krovetz 881 Department of Computer Science 882 California State University 883 Sacramento CA 95819 884 USA 885 Email: tdk@acm.org 887 Wei Dai 888 Bitvise Limited 889 Email: rfc@weidai.com 891 Full Copyright Statement 893 Copyright (C) The IETF Trust (2007). 895 This document is subject to the rights, licenses and restrictions 896 contained in BCP 78, and except as set forth therein, the authors 897 retain all their rights. 899 This document and the information contained herein are provided on an 900 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 901 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 902 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 903 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 904 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 905 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 907 Intellectual Property 909 The IETF takes no position regarding the validity or scope of any 910 Intellectual Property Rights or other rights that might be claimed to 911 pertain to the implementation or use of the technology described in 912 this document or the extent to which any license under such rights 913 might or might not be available; nor does it represent that it has 914 made any independent effort to identify any such rights. Information 915 on the ISOC's procedures with respect to rights in ISOC Documents can 916 be found in BCP 78 and BCP 79. 918 Copies of IPR disclosures made to the IETF Secretariat and any 919 assurances of licenses to be made available, or the result of an 920 attempt made to obtain a general license or permission for the use of 921 such proprietary rights by implementers or users of this 922 specification can be obtained from the IETF on-line IPR repository at 923 http://www.ietf.org/ipr. 925 The IETF invites any interested party to bring to its attention any 926 copyrights, patents or patent applications, or other proprietary 927 rights that may cover technology that may be required to implement 928 this standard. Please address the information to the IETF at ietf- 929 ipr@ietf.org. 931 Acknowledgments 933 This document borrows much text from RFC 4418 [3]. That document 934 describes another message authentication scheme, UMAC, and was co- 935 written by John Black, Shai Halevi, Alejandro Hevia, Hugo Krawczyk, 936 Ted Krovetz and Phillip Rogaway. Funding for the RFC Editor function 937 is currently provided by the Internet Society.