idnits 2.17.1 draft-krovetz-vmac-00.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 12. -- Found old boilerplate from RFC 3978, Section 5.5 on line 866. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 884. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 890. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. ** 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 : ---------------------------------------------------------------------------- ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 378: '...BLOCKLEN bits // first bit MUST be 0....' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 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 (November 2006) is 6372 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) -- Looks like a reference, but probably isn't: 'Decimal' on line 196 -- Looks like a reference, but probably isn't: 'Hexadecimal' on line 196 -- Possible downref: Non-RFC (?) normative reference: ref. '1' Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG Working Group T. Krovetz 3 INTERNET-DRAFT CSU Sacramento 4 Expires May 2007 November 2006 6 VMAC: Message Authentication Code using Universal Hashing 7 9 By submitting this Internet-Draft, each author represents that any 10 applicable patent or other IPR claims of which he or she is aware 11 have been or will be disclosed, and any of which he or she becomes 12 aware will be disclosed, in accordance with Section 6 of BCP 79. 14 Status of this Memo 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as Internet- 19 Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet-Drafts as reference 24 material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/1id-abstracts.html 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 Abstract 34 This specification describes how to generate an authentication tag 35 using the VMAC message authentication algorithm. VMAC is designed to 36 have exceptional performance in software on 64-bit CPU architectures 37 while performing well on 32-bit architectures. Measured speeds are 38 as low as one-half CPU cycle per byte on the 64-bit Intel Core 2 39 architecture, and under five cycles per byte on recent 32-bit PowerPC 40 and Intel processors. 42 To generate the authentication tag on a given message, a "universal" 43 hash function is applied to the message and key to produce a short, 44 fixed-length hash value, and this hash value is then xor'ed with a 45 key-derived pseudorandom pad. VMAC tags can be either 64 or 128 bits 46 in length and have proven forgery probabilities on the order of 47 1/2^59 and 1/2^94, respectively. 49 Table of Contents 51 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 52 2 Notation and basic operations . . . . . . . . . . . . . . . . . . 4 53 2.1 Operations on strings . . . . . . . . . . . . . . . . . . . 4 54 2.2 Operations on integers . . . . . . . . . . . . . . . . . . . 5 55 2.3 String-Integer conversion operations . . . . . . . . . . . . 5 56 2.4 Mathematical operations on strings . . . . . . . . . . . . . 5 57 2.5 ENDIAN-SWAP: Adjusting endian orientation . . . . . . . . . 6 58 3 Key and pad derivation functions . . . . . . . . . . . . . . . . 6 59 3.1 Block cipher choice . . . . . . . . . . . . . . . . . . . . 7 60 3.2 KDF: Key-derivation function . . . . . . . . . . . . . . . . 7 61 3.3 PDF: Pad-derivation function . . . . . . . . . . . . . . . . 8 62 4 VMAC tag generation . . . . . . . . . . . . . . . . . . . . . . . 9 63 4.1 VMAC Algorithm . . . . . . . . . . . . . . . . . . . . . . . 9 64 4.2 VMAC-64 and VMAC-128 . . . . . . . . . . . . . . . . . . . . 9 65 5 VHASH: Universal hash function . . . . . . . . . . . . . . . . . 10 66 5.1 VHASH Algorithm . . . . . . . . . . . . . . . . . . . . . . 10 67 5.2 L1-HASH: First-layer hash . . . . . . . . . . . . . . . . . 10 68 5.3 L2-HASH: Second-layer hash . . . . . . . . . . . . . . . . . 13 69 5.4 L3-HASH: Third-layer hash . . . . . . . . . . . . . . . . . 13 70 6 Security considerations . . . . . . . . . . . . . . . . . . . . . 14 71 6.1 Resistance to cryptanalysis . . . . . . . . . . . . . . . . 14 72 6.2 Tag lengths and forging probability . . . . . . . . . . . . 15 73 6.3 Nonce considerations . . . . . . . . . . . . . . . . . . . . 16 74 6.4 Replay attacks . . . . . . . . . . . . . . . . . . . . . . . 17 75 7 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 18 76 Appendix - Test vectors . . . . . . . . . . . . . . . . . . . . . . 18 77 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 78 Author contact information . . . . . . . . . . . . . . . . . . . . . 19 79 Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . . 19 80 Intellectual Property . . . . . . . . . . . . . . . . . . . . . . . 20 81 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . 20 82 1 Introduction 84 VMAC is a message authentication code (MAC) algorithm designed for 85 high performance. It is backed by a rigorous formal analysis, and 86 there are no intellectual property claims made by any of the authors 87 to any ideas used in its design. 89 VMAC is a MAC in the style of Wegman and Carter [4, 6]. A fast 90 "universal" hash function is used to hash an input message M into a 91 short string. This short string is then masked by xor'ing with a 92 pseudorandom pad, resulting in the VMAC tag. Security depends on the 93 sender and receiver sharing a randomly-chosen secret hash function 94 and pseudorandom pad. This is achieved by using keyed hash function 95 H and pseudorandom function F. A tag is generated by performing the 96 computation 98 Tag = H_K1(M) xor F_K2(Nonce) 100 where K1 and K2 are secret random keys shared by sender and receiver, 101 and Nonce is a value that changes with each generated tag. The 102 receiver needs to know which nonce was used by the sender, so some 103 method of synchronizing nonces needs to be used. This can be done by 104 explicitly sending the nonce along with the message and tag, or 105 agreeing upon the use of some other non-repeating value such as a 106 sequence number. The nonce need not be kept secret, but care needs 107 to be taken to ensure that, over the lifetime of a VMAC key, a 108 different nonce is used with each message. 110 VMAC uses a function, called VHASH (also specified in this document), 111 as the keyed hash function H and uses a pseudorandom function F whose 112 default implementation uses the AES algorithm. VMAC is designed to 113 produce 64- or 128-bit tags, depending on the desired security level. 114 The theory of Wegman-Carter MACs and the analysis of VMAC show that 115 if one "instantiates" VMAC with truly random keys and pads then the 116 probability that an attacker (even a computationally unbounded one) 117 produces a correct tag for messages of its choosing upto j bits in 118 length is less than 1/2^59 or 1/2^117 when the tags output by VMAC 119 are of length 64 or 128 bits, respectively (here the symbol ^ 120 represents exponentiation). When an attacker makes N forgery 121 attempts the probability of getting one or more tags right increases 122 linearly to about N/2^59 or Nj/2^117. In a real implementation of 123 VMAC, using AES to produce keys and pads, the forgery probabilities 124 listed above increase by a small amount related to the security of 125 AES. As long as AES is secure this small additive term is 126 insignificant for any practical attack. See Section 6.2 for more 127 details. Analysis relevant to VMAC security is in [5]. 129 VMAC performs best in environments where 64-bit quantities are 130 efficiently multiplied into 128-bit results. In producing 64-bit 131 tags on an Intel Core 2 CPU, VMAC processes messages at a rate of 132 about one-half CPU cycle per byte on messages of two kilobytes. On a 133 32-bit Intel Core CPU, which does not support 64-bit multiplication 134 well, VMAC achieves a rate of under five cycles per byte. On shorter 135 messages VMAC still performs well: about two cycles per byte on 64 136 byte messages on the Core 2. Tags of 128 bits require slightly less 137 than twice the computation as 64-bit tags. 139 Optimized source code, performance data and papers concerning VMAC 140 can be found at http://www.fastcrypto.org/vmac. 142 2 Notation and basic operations 144 The specification of VMAC involves the manipulation of strings and 145 numbers. String variables are denoted with an initial upper-case 146 letter, whereas numeric variables are denoted in all lower case. The 147 algorithms of VMAC are denoted in all upper-case letters. Simple 148 functions, like those for string-length and string-xor, are written 149 in all lower case. 151 Whenever a variable is followed by an underscore ("_"), the 152 underscore is intended to denote a subscript, with the subscripted 153 expression evaluated to resolve the meaning of the variable. For 154 example, if i=2, then M_{2 * i} refers to the variable M_4. 156 2.1 Operations on strings 158 Messages to be hashed are viewed as strings of bits. The following 159 notation is used to manipulate these strings. 161 bitlength(S): The length of string S in bits. 163 zeros(n): The string made of n zero-bits. 165 S xor T: The string which is the bitwise exclusive-or of S and 166 T. Strings S and T always have the same length. 168 S[i]: The i-th bit of the string S (indices begin at 1). 170 S[i...j]: The substring of S consisting of bits i through j. 172 S || T: The string S concatenated with string T. 174 zeropad(S,n): The string S, padded with zero-bits to the nearest 175 multiple of n bits in length. If S is empty or 176 already a multiple of n in length, nothing is 177 appended. Formally, zeropad(S,n) = S || T, where T 178 is the shortest string of zero-bits so that 179 bitlength(S || T) is a multiple of n. 181 2.2 Operations on integers 183 Standard notation is used for most mathematical operations, such as 184 "*" for multiplication, "+" for addition and "mod" for modular 185 reduction. Some less standard notations are defined here. 187 a^i: The integer a raised to the i-th power. 189 ceil(x): The smallest integer not less than x. 191 prime(n): The largest prime number less than 2^n. 193 The prime numbers used in VMAC are: 195 +-----+--------------------+---------------------------------------+ 196 | n | prime(n) [Decimal] | prime(n) [Hexadecimal] | 197 +-----+--------------------+---------------------------------------+ 198 | 61 | 2^61 - 1 | 0x1FFFFFFF FFFFFFFF | 199 | 127 | 2^127 - 1 | 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF | 200 +-----+--------------------+---------------------------------------+ 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 These operations correspond well with addition and multiplication 225 operations which are performed efficiently by modern computers. 227 2.5 ENDIAN-SWAP: Adjusting endian orientation 229 Message data is read little-endian to speed tag generation on little- 230 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_4 || W_3 || ... || 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 function for 192-bit AES 283 keys. 285 Unless specified otherwise, AES with 128-bit keys shall be assumed to 286 be the chosen block cipher for VMAC. Only if explicitly specified 287 otherwise, and agreed by communicating parties, shall some other 288 block cipher be used. In any case, BLOCKLEN must be at least 128. 289 AES is defined in another document [1]. 291 3.2 KDF: Key-derivation function 293 The key-derivation function generates pseudorandom bits used to key 294 the hash functions. 296 3.2.1 KDF Algorithm 298 Input: 299 K, string with bitlength KEYLEN. 300 index, an integer in the range 0...255. 301 numbits, a non-negative integer. 302 Output: 303 Y, string with bitlength numbits. 305 Compute Y using the following algorithm. 307 // 308 // Calculate number of block cipher iterations 309 // 310 n = ceil(numbits / BLOCKLEN) 311 Y = 312 // 313 // Build Y using block cipher in a counter mode 314 // 315 for i = 0 to (n-1) do 316 T = uint2str(index, 8) || uint2str(i, BLOCKLEN-8) 317 Y = Y || ENCIPHER(K, T) 318 end for 319 Y = Y[1...numbits] 321 Return Y 323 3.3 PDF: Pad-derivation function 325 This function takes a key and a nonce and returns a pseudorandom pad 326 for use in tag generation. A pad of length 64 or 128 bits can be 327 generated. Notice that when the block-cipher block-length is twice 328 as long as the pad, nonces that differ only in their last bit are 329 derived from the same block cipher encryption. This allows caching 330 and sharing a single block cipher invocation for sequential nonces. 332 3.3.1 PDF Algorithm 334 Input: 335 K, string with bitlength KEYLEN. 336 Nonce, string of length in the range 1...BLOCKLEN bits. 337 taglen, the integer 64 or 128. 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 greatest integer for which BLOCKLEN/taglen <= 2^i 348 index = str2uint(Nonce) mod 2^i 349 Nonce = Nonce xor uint2str(index, bitlength(Nonce)) 351 // 352 // Make Nonce BLOCKLEN bits by appending zeros if needed 353 // 354 Nonce = Nonce || zeros(BLOCKLEN - bitlength(Nonce)) 356 // 357 // Generate subkey, encipher and extract indexed substring 358 // 359 T = ENCIPHER(K, Nonce) 360 Y = T[index * taglen + 1 ... index * taglen + taglen ] 362 Return Y 364 4 VMAC tag generation 366 Tag generation for VMAC proceeds by using VHASH (defined in the next 367 section) to hash the message, applying the PDF to the nonce and 368 computing the xor of the resulting strings. The first bit of the 369 nonce must be zero to ensure the KDF and PDF functions do not pass 370 the same values to the block cipher. The length of the pad and hash 371 can be either 64 or 128 bits. 373 4.1 VMAC Algorithm 375 Input: 376 K, string of length KEYLEN bits. 377 M, string of any length. 378 Nonce, string of length 1 to BLOCKLEN bits // first bit MUST be 0. 379 taglen, the integer 64 or 128. 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) 387 if taglen = 64 then 388 Tag = Pad +_64 HashedMessage 389 else 390 Tag = Pad +_128 HashedMessage 391 end if 393 Return Tag 395 4.2 VMAC-64 and VMAC-128 397 The preceding VMAC definition has a parameter "taglen" which 398 specifies the length of tag generated by the algorithm. The 399 following aliases define names that make tag length explicit in the 400 name. 402 VMAC-64(K, M, Nonce) = VMAC(K, M, Nonce, 64) 403 VMAC-128(K, M, Nonce) = VMAC(K, M, Nonce, 128) 405 5 VHASH: Universal hash function 407 VHASH is a keyed hash function, which takes as input a string, and 408 produces an 64- or 128-bit output. VHASH does its work in two or 409 three stages, or layers, depending on whether an 64- or 128-bit 410 output is requested. A message is first hashed by L1-HASH, its 411 output is then hashed by L2-HASH, whose output is then hashed by 412 L3-HASH if taglen is eight. 414 Please note that VHASH has certain combinatoric properties making it 415 suitable for Wegman-Carter message authentication. VHASH is not a 416 cryptographic hash function and is not a suitable general replacement 417 for functions like SHA-1. 419 VHASH is presented here in a top-down manner. First VHASH is 420 described, then each of its component hashes are presented. 422 5.1 VHASH Algorithm 424 Input: 425 K, string of length KEYLEN bits. 426 M, string of any length. 427 taglen, the integer 64 or 128. 428 Output: 429 Y, string of length taglen bits. 431 Compute Y using the following algorithm. 433 A = L1-HASH(K, M, taglen) 434 B = L2-HASH(K, A, taglen) 435 if taglen = 64 then 436 Y = L3-HASH(K, B) 437 else 438 Y = B 439 end if 441 Return Y 443 5.2 L1-HASH: First-layer hash 445 The first-layer hash breaks the message into blocks, each of length 446 L1KEYLEN (defined as 128 bytes), and hashes each with a function 447 called NH. Concatenating the results forms a string which is shorter 448 than the original. One could customize VHASH by changing L1KEYLEN to 449 any multiple of 128, achieving different performance characteristics, 450 but the resulting algorithm would not be interoperable with the 451 standard algorithm defined in this document. 453 5.2.1 L1-HASH Algorithm 455 Input: 456 K, string of length KEYLEN bits. 457 M, string of any length. 458 taglen, the integer 64 or 128. 459 Output: 460 Y, string of length (2 * taglen * ceil(bitlength(M)/L1KEYLEN)) 461 bits. 463 Compute Y using the following algorithm. 465 // 466 // Set subkey for L1-HASH 467 // 468 L1KEYLEN = 1024 469 T = KDF(K, 128, L1KEYLEN+128) 470 K_1 = T[1 ... L1KEYLEN] 471 K_2 = T[129 ... L1KEYLEN + 128] // Only used when taglen = 128 473 // 474 // Partition M into L1KEYLEN-bit sgements (last one may be shorter) 475 // 476 t = max(ceil(bitlength(M) / L1KEYLEN), 1) 477 Let M_1, M_2, ..., M_t be strings so that M = M_1 || M_2 || ... || 478 M_t, and bitlength(M_i) = L1KEYLEN for all 0 < i < t. 480 // 481 // For each segment, except the last: endian-adjust, NH hash, 482 // and use the results to build output Y. 483 // 484 Y = 485 for i = 1 to t-1 do 486 ENDIAN-SWAP(M_i) 487 Y = Y || NH(K_1, M_i) 488 if taglen = 128 then 489 Y = Y || NH(K_2, M_i) // Hash twice for 128-bit outputs 490 end if 491 end for 493 // 494 // For the last block: pad to 128-bit multiple, endian-adjust, 495 // NH hash and add bit-length. Concatenate the result to Y. 496 // 497 Len = uint2str(bitlength(M_t), 64) || zeros(64) 498 M_t = zeropad(M_t, 128) 499 ENDIAN-SWAP(M_t) 500 Y = Y || (NH(K_1, M_t) +_128 Len) 501 if taglen = 128 then 502 Y = Y || NH(K_2, M_t) 503 end if 505 Return Y 507 5.2.2 NH Algorithm 509 Because this routine is applied directly to every bit of input 510 data, an optimized implementation of it yields great benefit. 512 Input: 513 K, string with length a multiple of 128 bits. 514 M, string with length a multiple of 128 bits, but no longer than K. 515 Output: 516 Y, string of length 128 bits. 518 Compute Y using the following algorithm. 520 // 521 // Partition M and K into 64-bit substrings 522 // 523 t = bitlength(M) / 64 524 Let M_1, M_2, ..., M_t be 64-bit strings 525 so that M = M_1 || M_2 || ... || M_t. 526 Let K_1, K_2, ..., K_t be 64-bit strings 527 so that K_1 || K_2 || ... || K_t is a prefix of K. 529 // 530 // Perform NH hash on each. 531 // 532 Y = zeros(128) 533 i = 1 534 while (i < t) do 535 Y = Y +_128 ((M_i +_64 K_i) *_128 (M_{i+1} +_64 K_{i+1})) 536 i = i + 2 537 end while 538 Y = zeros(2) || Y[3...128] // Zero first two bits 540 Return Y 542 5.3 L2-HASH: Second-layer hash 544 The second-layer rehashes the L1-HASH output using a polynomial hash. 546 5.3.1 L2-HASH Algorithm 548 Input: 549 K, string of length KEYLEN bits. 550 M, string with length a multiple of 128 bits. 551 Output: 552 Y, string of length 128 bits. 554 Compute y using the following algorithm. 556 // 557 // Create subkey 558 // 559 T = KDF(K, 192, 128) 560 k = str2uint(zeros(2) || T[ 3...32] || zeros(2) || T[35... 64] || 561 zeros(2) || T[67...96] || zeros(2) || T[99...128]) 563 // 564 // Partition M into 128-bit substrings 565 // 566 n = bitlength(M) / 128 567 Let M_1, M_2, ..., M_n be strings of length 128 bits 568 so that M = M_1 || M_2 || ... || M_n 570 // 571 // Polynomial hash M 572 // 573 y = 1 574 for i = 1 to n do 575 m_i = str2uint(M_i) 576 y = (k * y + m_i) mod prime(127) 577 end for 578 y = (k * y) mod prime(127) 579 Y = uint2str(y, 128) 581 Return Y 583 5.4 L3-HASH: Third-layer hash 585 The output from L2-HASH is 128 bits long. This final hash function 586 hashes the 128-bit string to a fixed length of 64 bits. Note that 587 the "do" loop during subkey generation has less than 1/2^58 588 probability of requiring more than one iteration. 590 5.4.1 L3-HASH Algorithm 592 Input: 593 K, string of length KEYLEN bits. 594 M, string of length 128 bits. 595 Output: 596 Y, string of length 64 bits. 598 Compute Y using the following algorithm. 600 i = 0 601 repeat 602 T = KDF(K, 224+i, 128) 603 k_1 = str2uint(T[ 4... 64]) 604 k_2 = str2uint(T[68...128]) 605 i = i + 1 606 until (k_1 < prime(61)) and (k_2 < prime(61)) 608 m_1 = str2uint(M[ 5... 64]) 609 m_2 = str2uint(M[69...128]) 610 y = (m_1 * k_1 + m_2 * k_2) mod prime(61) 612 Y = uint2str(y, 64) 614 Return Y 616 6 Security considerations 618 Here we describe some security considerations important for the 619 proper understanding and use of VMAC. 621 6.1 Resistance to cryptanalysis 623 The strength of VMAC depends on the strength of its underlying 624 cryptographic functions: the key-derivation function (KDF) and the 625 pad-derivation function (PDF). In this specification both operations 626 are implemented using a block cipher, by default the Advanced 627 Encryption Standard (AES). However, the core of the VMAC design, the 628 VHASH function, does not depend on cryptographic assumptions: its 629 strength is specified by a purely mathematical property stated in 630 terms of collision probability, and this property is proven 631 unconditionally [5]. This means the strength of VHASH is guaranteed 632 regardless of advances in cryptanalysis and that an adversarial 633 attack on VMAC that forges with probability significantly exceeding 634 the established collision probability of VHASH will give rise to an 635 attack of comparable complexity which breaks the block cipher, in the 636 sense of distinguishing the block cipher from a family of random 637 permutations. This design approach essentially obviates the need for 638 cryptanalysis on VMAC: cryptanalytic efforts might as well focus on 639 the block cipher. 641 6.2 Tag lengths and forging probability 643 A MAC algorithm is used to authenticate messages between two parties 644 that share a secret MAC key K. An authentication tag is computed for 645 a message using K and, in some MAC algorithms such as VMAC, a nonce. 646 Messages transmitted between parties are accompanied by their tag 647 and, possibly, nonce. Breaking the MAC means that the attacker is 648 able to generate, on its own, with no knowledge of the key K, a new 649 message M (ie, one not previously transmitted between the legitimate 650 parties) and to compute on M a correct authentication tag under the 651 key K. This is called a forgery. Note that if the authentication 652 tag is specified to be of length t then the attacker can trivially 653 break the MAC with probability 1/2^t. For this the attacker can just 654 generate any message of its choice and try a random tag; obviously, 655 the tag is correct with probability 1/2^t. By repeated guesses the 656 attacker can increase linearly its probability of success. 658 In the case of VMAC-64, for example, the above guessing-attack 659 strategy is close to optimal. An adversary can correctly guess a 660 64-bit VMAC tag with probability 1/2^64 by simply guessing a random 661 value. The theory of Wegman-Carter MACs and results of [5] show that 662 no attack strategy can produce a correct tag with probability better 663 than about 1/2^59 if VMAC were to use a random function in its work 664 rather than AES. Another result shows that so long as AES is secure 665 as a pseudorandom permutation, it can be used instead of a random 666 function without significantly increasing the 1/2^59 forging 667 probability, assuming that no more than 2^64 messages are 668 authenticated with the same key [2]. Similarly for VMAC-128, the 669 per-message forgery probability, when using a random function rather 670 than AES to instantiate VMAC and limiting messages to j bits, is no 671 more than j/2^117. 673 AES has undergone extensive study and is assumed to be very secure as 674 a pseudorandom permutation. If we assume that no attacker with 675 feasible computational power can distinguish randomly keyed AES from 676 a randomly chosen permutation with probability delta (more precisely, 677 delta is a function of the computational resources of the attacker 678 and of its ability to sample the function), then we obtain that no 679 such attacker can forge j-bit messages in VMAC with probability 680 greater than about 1/2^59 or j/2^117, plus delta. Over N forgery 681 attempts, forgery occurs with probability no more than N/^59 or 682 N/2^117, plus delta. The value delta could possibly be greater than 683 1/2^59 or 1/2^88, in which case the probability of VMAC forging is 684 dominated by a term representing the security of AES. 686 With VMAC, off-line computation aimed at exceeding the forging 687 probability is hopeless as long as the underlying cipher is not 688 broken. An attacker attempting to forge VMAC tags will need to 689 interact with the entity that verifies message tags and try a large 690 number of forgeries before one is likely to succeed. The system 691 architecture will determine the extent to which this is possible. In 692 a well-architected system there should not be any high-bandwidth 693 capability for presenting forged MACs and determining if they are 694 valid. In particular, the number of authentication failures at the 695 verifying party should be limited. If a large number of such 696 attempts are detected the session key in use should be dropped and 697 the event reported. 699 Let us reemphasize: a forging probability of 1/2^59 does not mean 700 that there is an attack that runs in 2^59 time; to the contrary, as 701 long as the block cipher in use is not broken there is no such attack 702 for VMAC. Instead, a 1/2^59 forging probability means that if an 703 attacker could have N forgery attempts, then the attacker would have 704 no more than N/2^59 probability of getting one or more of them right. 706 It should be pointed out that once an attempted forgery is 707 successful, it is possible, in principle, that subsequent messages 708 under this key may be more easily forged. This is important to 709 understand in gauging the severity of a successful forgery, even 710 though no such attack on VMAC is known to date. Due to the short- 711 lived nature of most authentication sessions, 64-bit tags seem 712 appropriate for many security architectures and commercial 713 applications. If, however, one wants a more conservative option, at 714 a cost of about double the computation, VMAC's 128-bit tags may be 715 more appropriate. 717 6.3 Nonce considerations 719 VMAC requires a nonce with length upto BLOCKLEN bits. (For technical 720 reasons, the first bit of every nonce must be zero.) All nonces in 721 an authentication session must be equal in length. For secure 722 operation, no nonce value should be repeated within the life of a 723 single VMAC session-key. There is no guarantee of message 724 authenticity when a nonce is repeated, and so messages accompanied by 725 a repeated nonce should be considered not authenticated. 727 To authenticate messages over a duplex channel (where two parties 728 send messages to each other), a different key could be used for each 729 direction. If the same key is used in both directions, then it is 730 crucial that all nonces be distinct. For example, one party can use 731 even nonces while the other party uses odd ones. The receiving party 732 must verify that the sender is using a nonce of the correct form. 734 This specification does not indicate how nonce values are created, 735 updated, or communicated between the entity producing a tag and the 736 entity verifying a tag. The following are possibilities: 738 1. The nonce is a 64-bit unsigned number, Counter, which is 739 initialized to zero, which is incremented by one following the 740 generation of each authentication tag, and which is always 741 communicated along with the message and the authentication tag. 742 An error occurs at the sender if there is an attempt to 743 authenticate more than 2^63 messages within a session. 745 2. The nonce is a BLOCKLEN-bit unsigned number, Counter, which is 746 initialized to zero and which is incremented by one following the 747 generation of each authentication tag. The Counter is not 748 explicitly communicated between the sender and receiver. 749 Instead, the two are assumed to communicate over a reliable 750 transport, and each maintains its own counter so as to keep track 751 of what the current nonce value is. 753 3. The nonce is a BLOCKLEN-bit random value with first bit zero, 754 communicated along with the messgae and tag. Because repetitions 755 in a random n-bit value are expected at around 2^(n/2) trials, 756 the number of messages to be communicated in a session using n- 757 bit random nonces should not be allowed to approach 2^(n/2). 759 We emphasize that the value of the nonce need not be kept secret. 760 When VMAC is used within a higher-level protocol there may already be 761 a field, such as a sequence number, which can be co-opted so as to 762 specify the nonce needed by VMAC. 764 6.4 Replay attacks 766 A replay attack entails the attacker repeating a message, nonce, and 767 authentication tag. In many applications, replay attacks may be 768 quite damaging and must be prevented. In VMAC, this would normally 769 be done at the receiver by having the receiver check that no nonce 770 value is used twice. On a reliable connection, when the nonce is a 771 counter, this is trivial. On an unreliable connection, when the 772 nonce is a counter, one would normally cache some window of recent 773 nonces. Out-of-order message delivery in excess of what the window 774 allows will result in rejecting otherwise valid authentication tags. 775 We emphasize that it is up to the receiver to determine when a given 776 (message, nonce, tag) triple will be deemed authentic. Certainly the 777 tag should be valid for the message and nonce, as determined by VMAC, 778 but the message may still be deemed inauthentic because the nonce is 779 detected to be a replay. 781 7 IANA Considerations 783 This document has no actions for IANA. 785 Appendix - Test vectors 787 Following are some sample VMAC outputs over a collection of input 788 values, using AES with 128-bit keys. Let key K and nonce N be 789 defined by the following ASCII strings. 791 K = "abcdefghijklmnop" // A 128-bit VMAC key 792 N = "bcdefghi" // A 64-bit nonce 794 The tags generated by VMAC using key K and nonce N are: 796 Message 64-bit Tag 128-bit Tag 797 ------- ---------- ----------- 798 4EDE4AE94EDD87E1 E87569084EFF3E1CCA1500C5A6A89CE6 799 'abc' * 1 4157A6D46E3EC1A1 E5B10669E5B61668A11E3351CC1A7211 800 'abc' * 16 4D3C8A9C2A09E2DE 12A64330F81D8B6407CE90667303FEE2 801 'abc' * 100 4FD5EC2FCFE31FBE 10A63F27D4B292723739B4BB6F17A4C1 802 'abc' * 10^6 4E13F57841D33D58 22C65CC2CFE9BED72E485CA6EB8A48BE 804 The first column lists a small sample of messages which are strings 805 of repeated ASCII 'abc' strings. The remaining columns give in 806 hexadecimal the tags generated when VMAC is called with the 807 corresponding message, nonce N and key K. 809 References 811 Normative References 813 [1] FIPS-197, "Advanced Encryption Standard (AES)", National 814 Institute of Standards and Technology, 2001. 816 Informative References 818 [2] D. Bernstein, "Stronger security bounds for permutations", 819 unpublished manuscript, 2005. This work refines "Stronger 820 security bounds for Wegman-Carter-Shoup authenticators", 821 Advances in Cryptology - EUROCRYPT 2005, LNCS vol. 3494, pp. 822 164-180, Springer-Verlag, 2005. 824 [3] J. Black, S. Halevi, A. Hevia, H. Krawczyk, T. Krovetz, and P. 825 Rogaway, "UMAC: Message authentication code using universal 826 hashing", RFC 4418, IETF, 2006. 828 [4] L. Carter and M. Wegman, "Universal classes of hash functions", 829 Journal of Computer and System Sciences, 18 (1979), pp. 830 143-154. 832 [5] T. Krovetz, "Message auhentication on 64-bit architectures", 833 Selected Areas in Cryptography - SAC 2006, Springer-Verlag, 834 2006. 836 [6] M. Wegman and L. Carter, "New hash functions and their use in 837 authentication and set equality", Journal of Computer and 838 System Sciences, 22 (1981), pp. 265-279. 840 Author contact information 842 Author's Address 844 Ted Krovetz 845 Department of Computer Science 846 California State University 847 Sacramento CA 95819 848 USA 850 EMail: tdk@acm.org 852 Full Copyright Statement 854 Copyright (C) The Internet Society (2006). 856 This document is subject to the rights, licenses and restrictions 857 contained in BCP 78, and except as set forth therein, the authors 858 retain all their rights. 860 This document and the information contained herein are provided on an 861 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 862 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 863 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 864 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 865 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 866 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 868 Intellectual Property 870 The IETF takes no position regarding the validity or scope of any 871 Intellectual Property Rights or other rights that might be claimed to 872 pertain to the implementation or use of the technology described in 873 this document or the extent to which any license under such rights 874 might or might not be available; nor does it represent that it has 875 made any independent effort to identify any such rights. Information 876 on the ISOC's procedures with respect to rights in ISOC Documents can 877 be found in BCP 78 and BCP 79. 879 Copies of IPR disclosures made to the IETF Secretariat and any 880 assurances of licenses to be made available, or the result of an 881 attempt made to obtain a general license or permission for the use of 882 such proprietary rights by implementers or users of this 883 specification can be obtained from the IETF on-line IPR repository at 884 http://www.ietf.org/ipr. 886 The IETF invites any interested party to bring to its attention any 887 copyrights, patents or patent applications, or other proprietary 888 rights that may cover technology that may be required to implement 889 this standard. Please address the information to the IETF at ietf- 890 ipr@ietf.org. 892 Acknowledgments 894 This document borrows much text from RFC 4418 [3]. That document 895 describes another message authentication scheme, UMAC, and was co- 896 written by John Black, Shai Halevi, Alejandro Hevia, Hugo Krawczyk, 897 Ted Krovetz and Phillip Rogaway. Funding for the RFC Editor function 898 is currently provided by the Internet Society.