idnits 2.17.1 draft-krovetz-umac-03.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 1032. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1050. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1056. ** The document claims conformance with section 10 of RFC 2026, but uses some RFC 3978/3979 boilerplate. As RFC 3978/3979 replaces section 10 of RFC 2026, you should not claim conformance with it if you have changed to using RFC 3978/3979 boilerplate. ** 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 : ---------------------------------------------------------------------------- No issues found here. 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 (June 2005) is 6888 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 198 -- Looks like a reference, but probably isn't: 'Hexadecimal' on line 198 == Unused Reference: '4' is defined on line 951, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Obsolete informational reference (is this intentional?): RFC 2406 (ref. '4') (Obsoleted by RFC 4303, RFC 4305) Summary: 5 errors (**), 0 flaws (~~), 3 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG Working Group T. Krovetz, Editor 3 INTERNET-DRAFT CSU Sacramento 4 Expires December 2005 June 2005 6 UMAC: 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 This document is an Internet-Draft and is in full conformance with 17 all provisions of Section 10 of RFC2026. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/1id-abstracts.html 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 Abstract 37 This specification describes how to generate an authentication tag 38 using the UMAC message authentication algorithm. UMAC is designed to 39 be very fast to compute in software on contemporary uniprocessors. 40 Measured speeds are as low as one cycle per byte. UMAC relies on 41 addition of 32-bit and 64-bit numbers and multiplication of 32-bit 42 numbers, operations well-supported by contemporary machines. 44 To generate the authentication tag on a given message, a "universal" 45 hash function is applied to the message and key to produce a short, 46 fixed-length hash value, and this hash value is then xor'ed with a 47 key-derived pseudorandom pad. UMAC enjoys a rigorous security 48 analysis and its only internal "cryptographic" use is a block cipher 49 to generate the pseudorandom pads and internal key material. 51 Table of Contents 53 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 2 Notation and basic operations . . . . . . . . . . . . . . . . . . 4 55 2.1 Operations on strings . . . . . . . . . . . . . . . . . . . 4 56 2.2 Operations on integers . . . . . . . . . . . . . . . . . . . 5 57 2.3 String-Integer conversion operations . . . . . . . . . . . . 5 58 2.4 Mathematical operations on strings . . . . . . . . . . . . . 6 59 2.5 ENDIAN-SWAP: Adjusting endian orientation . . . . . . . . . 6 60 3 Key and pad derivation functions . . . . . . . . . . . . . . . . 7 61 3.1 Block cipher choice . . . . . . . . . . . . . . . . . . . . 7 62 3.2 KDF: Key-derivation function . . . . . . . . . . . . . . . . 7 63 3.3 PDF: Pad-derivation function . . . . . . . . . . . . . . . . 8 64 4 UMAC tag generation . . . . . . . . . . . . . . . . . . . . . . . 9 65 4.1 UMAC Algorithm . . . . . . . . . . . . . . . . . . . . . . . 9 66 4.2 UMAC-32, UMAC-64, UMAC-96 and UMAC-128 . . . . . . . . . . . 10 67 5 UHASH: Universal hash function . . . . . . . . . . . . . . . . . 10 68 5.1 L1-HASH: First-layer hash . . . . . . . . . . . . . . . . . 12 69 5.2 L2-HASH: Second-layer hash . . . . . . . . . . . . . . . . . 14 70 5.3 L3-HASH: Third-layer hash . . . . . . . . . . . . . . . . . 16 71 6 Security considerations . . . . . . . . . . . . . . . . . . . . . 17 72 6.1 Resistance to cryptanalysis . . . . . . . . . . . . . . . . 17 73 6.2 Tag lengths and forging probability . . . . . . . . . . . . 17 74 6.3 Nonce considerations . . . . . . . . . . . . . . . . . . . . 19 75 6.4 Guarding against replay attacks . . . . . . . . . . . . . . 20 76 7 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 20 77 8 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 20 78 Appendix - Test vectors . . . . . . . . . . . . . . . . . . . . . . 21 79 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 80 Author contact information . . . . . . . . . . . . . . . . . . . . . 22 81 1 Introduction 83 UMAC is a message authentication algorithm (MAC) designed for high 84 performance. It has been rigorously proven to be secure and there 85 are no intellectual property claims made to any ideas used in its 86 design. 88 The output of UMAC is a string called a tag. UMAC is designed to 89 produce 32-, 64-, 96- or 128-bit tags, depending on the user's 90 preference, with 64 bits recommended for most applications. When 91 UMAC produces 32-, 64-, 96- or 128-bit tags, the probability that an 92 attacker could produce a correct tag for any message of its choosing 93 is about 1/2^30, 1/2^60, 1/2^90 or 1/2^120, respectively. These 94 probabilities remains the same for each new forgery attempt by the 95 attacker. Our analysis has shown that doing any better would imply 96 that an effective attack exists for the block cipher in use. Hence, 97 assuming the block cipher is strong, so is UMAC. Security analysis 98 of UMAC is in [2, 5]. 100 UMAC performs best in environments where 32-bit quantities are 101 efficiently multiplied into 64-bit results. In producing 64-bit tags 102 on an Intel Pentium 4 using SSE2 instructions, which do two of these 103 multiplications in parallel, UMAC processes messages at a peak rate 104 of about one CPU cycle per byte, with the peak being achieved on 105 messages of around four kilobytes and longer. On the Pentium III, 106 without the use of SSE parallelism, UMAC achieves a peak of two 107 cycles per byte. On shorter messages UMAC still performs well: 108 around four cycles per byte on 256 byte messages and under two cycles 109 per byte on 1500 byte messages. The time to produce a 32-bit tag is 110 a little more than half that needed to produce a 64-bit tag, while 111 96- and 128-bit tags take about one-and-a-half and twice as long. 113 UMAC is a MAC in the style of Wegman and Carter [3, 6]. A fast 114 "universal" hash function is used to hash an input message into a 115 short string. This short string is then masked by xor'ing with a 116 pseudorandom string, resulting in the UMAC tag. Security depends on 117 the sender and receiver sharing a randomly-chosen secret hash 118 function and pseudorandom string. This is achieved by using a keyed 119 hash function h and pseudorandom function f. A tag is thus generated 120 by performing the computation 122 tag = f_k(nonce) xor h_k(message) 124 where k is a secret key shared by sender and receiver, and nonce is a 125 value that changes with each generated tag. The receiver needs to 126 know which nonce was used by the sender, so some method of 127 synchronizing nonces needs to be used. This can be done by 128 explicitly sending the nonce along with the message and tag, or 129 agreeing upon the use of some other non-repeating value such as 130 message number. The nonce need not be kept secret, but care needs to 131 be taken to ensure that, over the lifetime of the UMAC key, a 132 different nonce is used with each message. 134 Optimized source code, performance data and papers concerning UMAC 135 can be found at http://www.cs.ucdavis.edu/~rogaway/umac/. 137 2 Notation and basic operations 139 The specification of UMAC involves the manipulation of both strings 140 and numbers. String variables are denoted with an initial upper-case 141 letter, whereas numeric variables are denoted in all lower case. The 142 algorithms of UMAC are denoted in all upper-case letters. Simple 143 functions, like those for string-length and string-xor, are written 144 in all lower case. 146 Whenever a variable is followed by an underscore ("_"), the 147 underscore is intended to denote a subscript, with the subscripted 148 expression needing to be evaluated to resolve the meaning of the 149 variable. For example, if i=2, then M_{2 * i} refers to the variable 150 M_4. 152 2.1 Operations on strings 154 Messages to be hashed are viewed as strings of bits which get zero- 155 padded to an appropriate byte-length. Once the message is padded, 156 all strings are viewed as strings of bytes. A "byte" is an 8-bit 157 string. The following notation is used to manipulate these strings. 159 bytelength(S): The length of string S in bytes. 161 bitlength(S): The length of string S in bits. 163 zeroes(n): The string made of n zero-bytes. 165 S xor T: The string which is the bitwise exclusive-or of S 166 and T. Strings S and T always have the same length. 168 S and T: The string which is the bitwise conjunction of S and 169 T. Strings S and T always have the same length. 171 S[i]: The i-th byte of the string S (indices begin at 1). 173 S[i..j]: The substring of S consisting of bytes i through j. 175 S || T: The string S concatenated with string T. 177 zeropad(S,n): The string S, padded with zero-bits to the nearest 178 positive multiple of n bytes. Formally, 179 zeropad(S,n) = S || T, where T is the shortest 180 string of zero-bits (possibly empty) so that S || T 181 is non-empty and 8n divides bitlength(S || T). 183 2.2 Operations on integers 185 Standard notation is used for most mathematical operations, such as 186 "*" for multiplication, "+" for addition and "mod" for modular 187 reduction. Some less standard notations are defined here. 189 a^i: The integer a raised to the i-th power. 191 ceil(x): The smallest integer greater than or equal to x. 193 prime(n): The largest prime number less than 2^n. 195 The prime numbers used in UMAC are: 197 +-----+--------------------+---------------------------------------+ 198 | n | prime(n) [Decimal] | prime(n) [Hexadecimal] | 199 +-----+--------------------+---------------------------------------+ 200 | 36 | 2^36 - 5 | 0x0000000F FFFFFFFB | 201 | 64 | 2^64 - 59 | 0xFFFFFFFF FFFFFFC5 | 202 | 128 | 2^128 - 159 | 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFF61 | 203 +-----+--------------------+---------------------------------------+ 205 2.3 String-Integer conversion operations 207 Conversion between strings and integers is done using the following 208 functions. Each function treats initial bits as more significant 209 than later ones. 211 bit(S,n): Returns the integer 1 if the n-th bit of the string 212 S is 1, otherwise returns the integer 0 (indices 213 begin at 1). 215 str2uint(S): The non-negative integer whose binary representation 216 is the string S. More formally, if S is t bits long 217 then str2uint(S) = 2^{t-1} * bit(S,1) + 2^{t-2} * 218 bit(S,2) + ... + 2^{1} * bit(S,t-1) + bit(S,t). 220 uint2str(n,i): The i-byte string S such that str2uint(S) = n. 222 2.4 Mathematical operations on strings 224 One of the primary operations in UMAC is repeated application of 225 addition and multiplication on strings. The operations "+_32", 226 "+_64" and "*_64" are defined 228 "S +_32 T" as uint2str(str2uint(S) + str2uint(T) mod 2^32, 4), 229 "S +_64 T" as uint2str(str2uint(S) + str2uint(T) mod 2^64, 8) and 230 "S *_64 T" as uint2str(str2uint(S) * str2uint(T) mod 2^64, 8). 232 These operations correspond well with the addition and multiplication 233 operations which are performed efficiently on registers by modern 234 computers. 236 2.5 ENDIAN-SWAP: Adjusting endian orientation 238 Message data is read little-endian to speed tag generation on little- 239 endian computers. On little-endian processors, this is a free 240 operation. 242 2.5.1 ENDIAN-SWAP Algorithm 244 Input: 245 S, string with length divisible by 4 bytes. 246 Output: 247 T, string S with each 4-byte word endian-reversed. 249 Compute T using the following algorithm. 251 // 252 // Break S into 4-byte chunks 253 // 254 n = bytelength(S) / 4 255 Let S_1, S_2, ..., S_n be strings of length 4 bytes 256 so that S_1 || S_2 || ... || S_n = S. 258 // 259 // Byte-reverse each chunk, and build-up T 260 // 261 T = 262 for i = 1 to n do 263 Let W_1, W_2, W_3, W_4 be bytes 264 so that W_1 || W_2 || W_3 || W_4 = S_i 265 SReversed_i = W_4 || W_3 || W_2 || W_1 266 T = T || SReversed_i 267 end for 269 Return T 271 3 Key and pad derivation functions 273 Pseudorandom bits are needed internally by UHASH and at the time of 274 tag generation. The functions listed in this section use a block 275 cipher to generate these bits. 277 3.1 Block cipher choice 279 UMAC requires the services of a block cipher. The selection of a 280 block cipher defines the following constants and functions. 282 BLOCKLEN The length, in bytes, of the plaintext block on 283 which the block cipher operates. 285 KEYLEN The block cipher's key length, in bytes. 287 ENCIPHER(K,P) The application of the block cipher on P (a string 288 of BLOCKLEN bytes) using key K (a string of KEYLEN 289 bytes). 291 As an example, if AES is used with 16-byte keys, then BLOCKLEN would 292 equal 16 (because AES employs 16-byte blocks), KEYLEN would equal 293 16, and ENCIPHER would refer to the AES function. 295 Unless specified otherwise, AES with 128-bit keys shall be assumed to 296 be the chosen block cipher for UMAC. Only if explicitly specified 297 otherwise, and agreed by communicating parties, shall some other 298 block cipher be used. In any case, BLOCKLEN must be at least 16 and 299 a power of two. 301 AES is defined in another document [1]. 303 3.2 KDF: Key-derivation function 305 The key-derivation function generates pseudorandom bits used to key 306 the hash functions. 308 3.2.1 KDF Algorithm 310 Input: 311 K, string of length KEYLEN bytes // block cipher key 312 index, an integer in the range 0...7. 313 numbytes, a positive integer. 314 Output: 315 Y, string of length numbytes bytes. 317 Compute Y using the following algorithm. 319 // 320 // Calculate number of block cipher iterations, set starting point 321 // 322 n = ceil(numbytes / BLOCKLEN) 323 B = uint2str((2 * index + 1)^2 + index, 1) xor uint2str(90, 1) 324 T = B repeated BLOCKLEN times 325 Y = 327 // 328 // Build Y using block cipher in a feedback mode 329 // 330 for i = 1 to n do 331 T = T[1..(BLOCKLEN - 1)] || uint2str(i mod 256, 1) 332 T = ENCIPHER(K, T) 333 Y = Y || T 334 end for 336 Y = Y[1..numbytes] 338 Return Y 340 3.3 PDF: Pad-derivation function 342 This function takes a key and a nonce and returns a pseudorandom pad 343 for use in tag generation. A pad of length 4, 8, 12 or 16 bytes can 344 be generated. Notice that pads generated using nonces that differ 345 only in their last bit (when generating 8-byte pads) or last two bits 346 (when generating 4-byte pads) are derived from the same block cipher 347 encryption. This allows caching and sharing a single block cipher 348 invocation for sequential nonces. 350 3.3.1 PDF Algorithm 352 Input: 354 K, string of length KEYLEN bytes 355 Nonce, string of length 1 to BLOCKLEN bytes. 356 padlen, the integer 4, 8, 12 or 16. 357 Output: 358 Y, string of length padlen bytes. 360 Compute Y using the following algorithm. 362 // 363 // Extract and zero low bit(s) of Nonce if needed 364 // 365 if (padlen = 4 or padlen = 8) 366 index = str2uint(Nonce) mod (BLOCKLEN/padlen) 367 Nonce = Nonce xor uint2str(index, bytelength(Nonce)) 368 end if 370 // 371 // Make Nonce BLOCKLEN bytes by appending zeroes if needed 372 // 373 Nonce = Nonce || zeroes(BLOCKLEN - bytelength(Nonce)) 375 // 376 // Generate subkey, encipher and extract indexed substring 377 // 378 K' = KDF(K, 0, KEYLEN) 379 T = ENCIPHER(K', Nonce) 380 if (padlen = 4 or padlen = 8) 381 Y = T[1 + (index*padlen) .. padlen + (index*padlen)] 382 else 383 Y = T[1..padlen] 384 end if 386 Return Y 388 4 UMAC tag generation 390 Tag generation for UMAC proceeds by using UHASH (defined in the next 391 section) to hash the message, applying the PDF to the nonce and 392 computing the xor of the resulting strings. The length of the pad 393 and hash can be either 4, 8, 12 or 16 bytes. 395 4.1 UMAC Algorithm 397 Input: 398 K, string of length KEYLEN bytes. 400 M, string of length less than 2^67 bits. 401 Nonce, string of length 1 to BLOCKLEN bytes. 402 taglen, the integer 4, 8, 12 or 16. 403 Output: 404 AuthTag, string of length taglen bytes. 406 Compute AuthTag using the following algorithm. 408 HashedMessage = UHASH(K, M, taglen) 409 Pad = PDF(K, Nonce, taglen) 410 AuthTag = Pad xor HashedMessage 412 Return AuthTag 414 4.2 UMAC-32, UMAC-64, UMAC-96 and UMAC-128 416 The preceding definition for UMAC has an input parameter "taglen" 417 which specifies the length of tag generated by the algorithm. The 418 following aliases define names that make tag length explicit in the 419 name. 421 UMAC-32(K, M, Nonce) = UMAC(K, M, Nonce, 4) 422 UMAC-64(K, M, Nonce) = UMAC(K, M, Nonce, 8) 423 UMAC-96(K, M, Nonce) = UMAC(K, M, Nonce, 12) 424 UMAC-128(K, M, Nonce) = UMAC(K, M, Nonce, 16) 426 5 UHASH: Universal hash function 428 UHASH is a keyed hash function, which takes as input a string of 429 arbitrary length, and produces a 4-, 8-, 12- or 16-byte output. 430 UHASH does its work in three stages, or layers. A message is first 431 hashed by L1-HASH, its output is then hashed by L2-HASH, whose output 432 is then hashed by L3-HASH. If the message being hashed is no longer 433 than 1024 bytes, then L2-HASH is skipped as an optimization. Because 434 L3-HASH outputs a string whose length is only four bytes long, 435 multiple iterations of this three-layer hash are used if a total 436 hash-output longer than four bytes is requested. To reduce memory 437 use, L1-HASH reuses most of its key material between iterations. A 438 significant amount of internal key is required for UHASH, but it 439 remains constant so long as UMAC's key is unchanged. It is the 440 implementor's choice whether to generate the internal keys each time 441 a message is hashed, or to cache them between messages. 443 Please note that UHASH has certain combinatoric properties making it 444 suitable for Wegman-Carter message authentication. UHASH is not a 445 cryptographic hash function and is not a suitable general replacement 446 for functions like SHA-1. 448 UHASH is presented here in a top-down manner. First UHASH is 449 described, then each of its component hashes are presented. 451 5.0.1 UHASH Algorithm 453 Input: 454 K, string of length KEYLEN bytes. 455 M, string of length less than 2^67 bits. 456 outlen, the integer 4, 8, 12 or 16. 457 Output: 458 Y, string of length outlen bytes. 460 Compute Y using the following algorithm. 462 // 463 // One internal iteration per 4 bytes of output 464 // 465 iters = outlen / 4 467 // 468 // Define total key needed for all iterations using KDF. 469 // L1Key and L3Key1 reuse most key material between iterations. 470 // 471 L1Key = KDF(K, 1, 1024 + (iters - 1) * 16) 472 L2Key = KDF(K, 2, iters * 24) 473 L3Key1 = KDF(K, 3, iters * 64) 474 L3Key2 = KDF(K, 4, iters * 4) 476 // 477 // For each iteration, extract key and three-layer hash. 478 // If bytelength(M) <= 1024, then skip L2-HASH. 479 // 480 Y = 481 for i = 1 to iters do 482 L1Key_i = L1Key [(i-1) * 16 + 1 .. (i-1) * 16 + 1024] 483 L2Key_i = L2Key [(i-1) * 24 + 1 .. i * 24] 484 L3Key1_i = L3Key1[(i-1) * 64 + 1 .. i * 64] 485 L3Key2_i = L3Key2[(i-1) * 4 + 1 .. i * 4] 487 A = L1-HASH(L1Key_i, M) 488 if (bitlength(M) <= bitlength(L1Key_i)) then 489 B = zeroes(8) || A 490 else 491 B = L2-HASH(L2Key_i, A) 492 end if 493 C = L3-HASH(L3Key1_i, L3Key2_i, B) 494 Y = Y || C 495 end for 497 Return Y 499 5.1 L1-HASH: First-layer hash 501 The first-layer hash breaks the message into 1024 byte chunks and 502 hashes each with a function called NH. The concatenation of these 503 hash values results in a string up to 128 times shorter than the 504 original. 506 5.1.1 L1-HASH Algorithm 508 Input: 509 K, string of length 1024 bytes. 510 M, string of length less than 2^67 bits. 511 Output: 512 Y, string of length (8 * ceil(bytelength(M)/1024)) bytes. 514 Compute Y using the following algorithm. 516 // 517 // Break M into 1024 byte chunks (final chunk may be shorter) 518 // 519 t = ceil(bytelength(M) / 1024) 520 Let M_1, M_2, ..., M_t be strings so that M = M_1 || M_2 || ... || 521 M_t, and bytelength(M_i) = 1024 for all 0 < i < t. 523 // 524 // For each chunk, except the last: endian-adjust, NH hash 525 // and add bit-length. Use results to build Y. 526 // 527 Len = uint2str(1024 * 8, 8) 528 Y = 529 for i = 1 to t-1 do 530 ENDIAN-SWAP(M_i) 531 Y = Y || (NH(K, M_i) +_64 Len) 532 end for 534 // 535 // For the last chunk: pad to 32-byte boundary, endian-adjust, 536 // NH hash and add bit-length. Concatenate the result to Y. 537 // 538 Len = uint2str(bitlength(M_t), 8) 539 M_t = zeropad(M_t, 32) 540 ENDIAN-SWAP(M_t) 541 Y = Y || (NH(K, M_t) +_64 Len) 543 return Y 545 5.1.2 NH Algorithm 547 Because this routine is applied directly to every bit of input 548 data, optimized implementation of it yields great benefit. 550 Input: 551 K, string of length 1024 bytes. 552 M, string with length divisible by 32 bytes. 553 Output: 554 Y, string of length 8 bytes. 556 Compute Y using the following algorithm. 558 // 559 // Break M and K into 4-byte chunks 560 // 561 t = bytelength(M) / 4 562 Let M_1, M_2, ..., M_t be 4-byte strings 563 so that M = M_1 || M_2 || ... || M_t. 564 Let K_1, K_2, ..., K_t be 4-byte strings 565 so that K_1 || K_2 || ... || K_t is a prefix of K. 567 // 568 // Perform NH hash on the chunks, pairing words for multiplication 569 // which are 4 apart to accommodate vector-parallelism. 570 // 571 Y = zeroes(8) 572 i = 1 573 while (i < t) do 574 Y = Y +_64 ((M_{i+0} +_32 K_{i+0}) *_64 (M_{i+4} +_32 K_{i+4})) 575 Y = Y +_64 ((M_{i+1} +_32 K_{i+1}) *_64 (M_{i+5} +_32 K_{i+5})) 576 Y = Y +_64 ((M_{i+2} +_32 K_{i+2}) *_64 (M_{i+6} +_32 K_{i+6})) 577 Y = Y +_64 ((M_{i+3} +_32 K_{i+3}) *_64 (M_{i+7} +_32 K_{i+7})) 578 i = i + 8 579 end while 580 Return Y 582 5.2 L2-HASH: Second-layer hash 584 The second-layer rehashes the L1-HASH output using a polynomial hash 585 called POLY. If the output of L1-HASH is long, then POLY is called 586 once on a prefix of the L1-HASH output and then called using 587 different settings on the remainder. (This two-step hashing of the 588 L1-HASH output is only needed if the initial message length is 589 greater than 16 megabytes.) 591 5.2.1 L2-HASH Algorithm 593 Input: 594 K, string of length 24 bytes. 595 M, string of length less than 2^64 bytes. 596 Output: 597 Y, string of length 16 bytes. 599 Compute y using the following algorithm. 601 // 602 // Extract keys and restrict to special key-sets 603 // 604 Mask64 = uint2str(0x01ffffff01ffffff, 8) 605 Mask128 = uint2str(0x01ffffff01ffffff01ffffff01ffffff, 16) 606 k64 = str2uint(K[1..8] and Mask64) 607 k128 = str2uint(K[9..24] and Mask128) 609 // 610 // If M is no more than 2^17 bytes, hash under 64-bit prime, 611 // otherwise, hash first 2^17 bytes under 64-bit prime and 612 // remainder under 128-bit prime. 613 // 614 if (bytelength(M) <= 2^17) then // 2^14 64-bit words 616 // 617 // View M as an array of 64-bit words, and use POLY modulo 618 // prime(64) (and with bound 2^64 - 2^32) to hash it. 619 // 620 y = POLY(64, 2^64 - 2^32, k64, M) 621 else 622 M_1 = M[1 .. 2^17] 623 M_2 = M[2^17 + 1 .. bytelength(M)] 624 M_2 = zeropad(M_2 || uint2str(0x80,1), 16) 625 y = POLY(64, 2^64 - 2^32, k64, M_1) 626 y = POLY(128, 2^128 - 2^96, k128, uint2str(y, 16) || M_2) 627 end if 629 Y = uint2str(y, 16) 631 Return Y 633 5.2.2 POLY Algorithm 635 Input: 636 wordbits, The integer 64 or 128. 637 maxwordrange, positive integer less than 2^wordbits. 638 k, integer in the range 0 ... prime(wordbits) - 1. 639 M, string with length divisible by (wordbits / 8) bytes. 640 Output: 641 y, integer in the range 0 ... prime(wordbits) - 1. 643 Compute y using the following algorithm. 645 // 646 // Define constants used for fixing out-of-range words 647 // 648 wordbytes = wordbits / 8 649 p = prime(wordbits) 650 offset = 2^wordbits - p 651 marker = p - 1 653 // 654 // Break M into chunks of length wordbytes bytes 655 // 656 n = bytelength(M) / wordbytes 657 Let M_1, M_2, ..., M_n be strings of length wordbytes bytes 658 so that M = M_1 || M_2 || ... || M_n 660 // 661 // Each input word m is compared with maxwordrange. If not smaller 662 // then 'marker' and (m - offset), both in range, are hashed. 663 // 664 y = 1 665 for i = 1 to n do 666 m = str2uint(M_i) 667 if (m >= maxwordrange) then 668 y = (k * y + marker) mod p 669 y = (k * y + (m - offset)) mod p 670 else 671 y = (k * y + m) mod p 672 end if 673 end for 675 Return y 677 5.3 L3-HASH: Third-layer hash 679 The output from L2-HASH is 16 bytes long. This final hash function 680 hashes the 16-byte string to a fixed length of 4 bytes. 682 5.3.1 L3-HASH Algorithm 684 Input: 685 K1, string of length 64 bytes. 686 K2, string of length 4 bytes. 687 M, string of length 16 bytes. 688 Output: 689 Y, string of length 4 bytes. 691 Compute Y using the following algorithm. 693 y = 0 695 // 696 // Break M and K1 into 8 chunks and convert to integers 697 // 698 for i = 1 to 8 do 699 M_i = M [(i - 1) * 2 + 1 .. i * 2] 700 K_i = K1[(i - 1) * 8 + 1 .. i * 8] 701 m_i = str2uint(M_i) 702 k_i = str2uint(K_i) mod prime(36) 703 end for 705 // 706 // Inner-product hash, extract last 32 bits and affine-translate 707 // 708 y = (m_1 * k_1 + ... + m_8 * k_8) mod prime(36) 709 y = y mod 2^32 710 Y = uint2str(y, 4) 711 Y = Y xor K2 713 Return Y 715 6 Security considerations 717 As a specification of a message authentication code, this entire 718 document is about security. Here we describe some security 719 considerations important for the proper understanding and use of 720 UMAC. 722 6.1 Resistance to cryptanalysis 724 The strength of UMAC depends on the strength of its underlying 725 cryptographic functions: the key-derivation function (KDF) and the 726 pad-derivation function (PDF). In this specification both operations 727 are implemented using a block cipher, presumably the Advanced 728 Encryption Standard (AES). However, the design of UMAC allows for 729 the replacement of these components. Indeed, it is straightforward 730 to use other block ciphers or other cryptographic objects, such as 731 (properly keyed) SHA-1 or HMAC for the realization of the KDF or PDF. 733 The core of the UMAC design, the UHASH function, does not depend on 734 any cryptographic assumptions: its strength is specified by a purely 735 mathematical property stated in terms of collision probability, and 736 this property is proven in an absolute sense [2, 5]. In this way, 737 the strength of UHASH is guaranteed regardless of future advances in 738 cryptanalysis. The UHASH function was not designed to provide 739 cryptographic collision resistance properties, as does SHA-1, and so 740 should not be used as a substitute for it. 742 The analysis of UMAC [2, 5] shows this scheme to have provable 743 security, in the sense of modern cryptography, by way of tight 744 reductions. What this means is that an adversarial attack on UMAC 745 which forges with probability significantly exceeding the established 746 collision probability will give rise to an attack of comparable 747 complexity which breaks the block cipher, in the sense of 748 distinguishing the block cipher from a family of random permutations. 749 This design approach essentially obviates the need for cryptanalysis 750 on UMAC: cryptanalytic efforts might as well focus on the block 751 cipher, the results imply. 753 6.2 Tag lengths and forging probability 755 A MAC algorithm is used between two parties that share a secret MAC 756 key, K. Messages transmitted between these parties are accompanied 757 by authentication tags computed using K and a given nonce. Breaking 758 the MAC means that the attacker is able to generate, on its own, with 759 no knowledge of the key K, a new message M (i.e. one not previously 760 transmitted between the legitimate parties) and to compute on M a 761 correct authentication tag under the key K. This is called a 762 forgery. Note that if the authentication tag is specified to be of 763 length t then the attacker can trivially break the MAC with 764 probability 1/2^t. For this the attacker can just generate any 765 message of its choice and try a random tag; obviously, the tag is 766 correct with probability 1/2^t. By repeated guesses the attacker can 767 increase linearly its probability of success. 769 UMAC is designed to make this guessing strategy the best possible 770 attack against UMAC as long as the attacker does not invest the 771 computational effort needed to break the underlying block cipher used 772 to produce the one time pads used in UMAC computation. More 773 precisely, under the assumed strength of this cipher UMAC provides 774 for close-to-optimal security with regards to forgery probability. 775 An adversary could guess an 8-byte UMAC tag correctly with 776 probability 1/2^64 by simply guessing a random value. The proofs of 777 [2, 5] show that an adversary being more clever in tag guessing can 778 do no better than about 1/2^60. 780 This means that for 8-byte tags the ideal forging probability is 781 2^-64 while UMAC produces an actual forging probability of at most 782 2^-60. This probability of forging a message is well under the 783 chance that a randomly guessed DES key is correct. DES is now widely 784 seen as vulnerable, but the problem has never been that some 785 extraordinarily lucky attacker might, in a single guess, find the 786 right key. Instead, the problem is that large amounts of computation 787 can be thrown at the problem until, off-line, the attacker finds the 788 right key. 790 With UMAC, off-line computation aimed at exceeding the forging 791 probability is hopeless as long as the underlying cipher is not 792 broken. The only way to forge is to interact with the entity that 793 verifies the MAC and to try a huge amount of forgeries before one is 794 likely to succeed. The system architecture will determine the extent 795 to which this is possible. In a well-architected system there should 796 not be any high-bandwidth capability for presenting forged MACs and 797 determining if they are valid. In particular, the number of 798 authentication failures at the verifying party should be limited. If 799 a large number of such attempts are detected the session key in use 800 should be dropped and the event be recorded in an audit log. 802 Let us reemphasize: a forging probability of 1 / 2^60 does not mean 803 that there is an attack that runs in 2^60 time - to the contrary, as 804 long as the block cipher in use maintains its believed security there 805 is no such attack for UMAC. Instead, a 1 / 2^60 forging probability 806 means that if an attacker could try out 2^60 MACs, then the attacker 807 would probably get one right. 809 It should be pointed out that once an attempted forgery is 810 successful, it is possible, in principle, that subsequent messages 811 under this key may be forged, too. This is important to understand 812 in gauging the severity of a successful forgery, even though no such 813 attack on UMAC is known to date. 815 In conclusion, 64-bit tags seem appropriate for most security 816 architectures and applications. If one wants more security, at a 817 cost of 50% more computation, UMAC can produce 96- and 128-bit tags 818 which cannot be forged with probability better than 1/2^90 and 819 1/2^120. Likewise, if less security is required, with the benefit of 820 50% less computation, UMAC can produce 32-bit tags which cannot be 821 forged with probability better than 1/2^30. Great care must be taken 822 when using 32-bit tags because 1/2^30 forgery probability is 823 considered fairly high. Still, high-speed low-security 824 authentication can be applied usefully on low-value data or rapidly- 825 changing key environments. 827 6.3 Nonce considerations 829 UMAC requires a nonce with length in the range 1 to BLOCKLEN bytes. 830 All nonces in an authentication session must be equal in length. For 831 secure operation, no nonce value should be repeated within the life 832 of a single UMAC session-key. 834 To authenticate messages over a duplex channel (where two parties 835 send messages to each other), a different key could be used for each 836 direction. If the same key is used in both directions, then it is 837 crucial that all nonces be distinct. For example, one party can use 838 even nonces while the other party uses odd ones. The receiving party 839 must verify that the sender is using a nonce of the correct form. 841 This specification does not indicate how nonce values are created, 842 updated, or communicated between the entity producing a tag and the 843 entity verifying a tag. The following exemplify some of the 844 possibilities: 846 1. The nonce is an eight-byte [resp., four-byte] unsigned number, 847 Counter, which is initialized to zero, which is incremented by 848 one following the generation of each authentication tag, and 849 which is always communicated along with the message and the 850 authentication tag. An error occurs at the sender if there is an 851 attempt to authenticate more than 2^64 [resp., 2^32] messages 852 within a session. 854 2. The nonce is a BLOCKLEN-byte unsigned number, Counter, which is 855 initialized to zero and which is incremented by one following the 856 generation of each authentication tag. The Counter is not 857 explicitly communicated between the sender and receiver. 858 Instead, the two are assumed to communicate over a reliable 859 transport, and each maintains its own counter so as to keep track 860 of what the current nonce value is. 862 3. The nonce is a BLOCKLEN-byte random value. (Because repetitions 863 in a random n-bit value are expected at around 2^(n/2) trials, 864 the number of messages to be communicated in a session using n- 865 bit nonces should not be allowed to approach 2^(n/2).) 867 We emphasize that the value of the nonce need not be kept secret. 869 When UMAC is used within a higher-level protocol there may already be 870 a field, such as a sequence number, which can be co-opted so as to 871 specify the nonce needed by UMAC [5]. The application will then 872 specify how to construct the nonce from this already-existing field. 874 6.4 Guarding against replay attacks 876 A replay attack entails the attacker repeating a message, nonce, and 877 authentication tag. In many applications, replay attacks may be 878 quite damaging and must be prevented. In UMAC, this would normally 879 be done at the receiver by having the receiver check that no nonce 880 value is used twice. On a reliable connection, when the nonce is a 881 counter, this is trivial. On an unreliable connection, when the 882 nonce is a counter, one would normally cache some window of recent 883 nonces. Out-of-order message delivery in excess of what the window 884 allows will result in rejecting otherwise valid authentication tags. 886 We emphasize that it is up to the receiver when a given (message, 887 nonce, tag) triple will be deemed authentic. Certainly the tag 888 should be valid for the message and nonce, as determined by UMAC, but 889 the message may still be deemed inauthentic because the nonce is 890 detected to be a replay. 892 7 IANA Considerations 894 This document has no actions for IANA. 896 8 Acknowledgments 898 David McGrew and Scott Fluhrer, of Cisco Systems, played a 899 significant role in improving UMAC by encouraging us to pay more 900 attention to the performance of short messages. Black, Krovetz, and 901 Rogaway have received support for this work under NSF awards 0208842, 902 0240000, 9624560, and a gift from Cisco Systems. Funding for the RFC 903 Editor function is currently provided by the Internet Society. 905 Appendix - Test vectors 907 Following are some sample UMAC outputs over a collection of input 908 values, using AES with 16-byte keys. 910 Let 912 K = "abcdefghijklmnop" // A 16-byte UMAC key 913 N = "bcdefghi" // An 8-byte nonce 915 The tags generated by UMAC using key K and nonce N are: 917 Message 32-bit Tag 64-bit Tag 96-bit Tag 918 ------- ---------- ---------- ---------- 919 EC085847 B9FE492F357C6DF8 3383059D11C13E532BD1E310 920 'a' * 3 5DA7EE32 0851FF5A9FFA52A0 822CB3E8BB47010BAEC943F8 921 'a' * 2^10 C8B389F9 9D459891837A7B7D 1738D423A7C728D603BE1725 922 'a' * 2^15 7B4291BF 2EB480D7EB0EFACA A4C9CC65CFB3A961C5456D6D 923 'a' * 2^20 A1AB1E5D F45D0F35F15E64D4 7E204387D5E3377F131EF03D 924 'a' * 2^25 961CA14D C3EAB025C055F3DB 4997FC97E4E8A0709A5842DD 925 'abc' * 1 CA507696 9FA667FE61D9E4C8 15DB2B4C4564B763303B8E31 926 'abc' * 500 87347438 D2C26550692E16F1 58BF29E24D93455AE5A05F07 928 The first column lists a small sample of messages which are strings 929 of repeated ASCII 'a' bytes or 'abc' strings. The remaining columns 930 give in hexadecimal the tags generated when UMAC is called with the 931 corresponding message, nonce N and key K. 933 References 935 Normative References 937 [1] FIPS-197, "Advanced Encryption Standard (AES)", National 938 Institute of Standards and Technology, 2001. 940 Informative References 942 [2] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway, 943 "UMAC: Fast and provably secure message authentication", 944 Advances in Cryptology - CRYPTO '99, LNCS vol. 1666, pp. 945 216-233, Springer-Verlag, 1999. 947 [3] L. Carter and M. Wegman, "Universal classes of hash functions", 948 Journal of Computer and System Sciences, 18 (1979), pp. 949 143-154. 951 [4] S. Kent and R. Atkinson, "IP Encapsulating Security Payload 952 (ESP)", RFC 2406, IETF, 1998. 954 [5] T. Krovetz, "Software-optimized universal hashing and message 955 authentication", UMI Dissertation Services, 2000. 957 [6] M. Wegman and L. Carter, "New hash functions and their use in 958 authentication and set equality", Journal of Computer and 959 System Sciences, 22 (1981), pp. 265-279. 961 Author contact information 963 Authors' Addresses 965 John Black 966 Department of Computer Science 967 University of Colorado 968 Boulder CO 80309 969 USA 971 EMail: jrblack@cs.colorado.edu 973 Shai Halevi 974 IBM T.J. Watson Research Center 975 P.O. Box 704 976 Yorktown Heights NY 10598 977 USA 979 EMail: shaih@alum.mit.edu 981 Alejandro Hevia 982 Department of Computer Science 983 University of Chile 984 Santiago 837-0459 985 CHILE 987 EMail: ahevia@dcc.uchile.cl 989 Hugo Krawczyk 990 IBM Research 991 19 Skyline Dr 992 Hawthorne, NY 10533 993 USA 994 EMail: hugo@ee.technion.ac.il 996 Ted Krovetz 997 Department of Computer Science 998 California State University 999 Sacramento CA 95819 1000 USA 1002 EMail: tdk@acm.org 1004 Phillip Rogaway 1005 Department of Computer Science 1006 University of California 1007 Davis CA 95616 1008 USA 1009 and 1010 Department of Computer Science 1011 Faculty of Science 1012 Chiang Mai University 1013 Chiang Mai 50200 1014 THAILAND 1016 EMail: rogaway@cs.ucdavis.edu 1018 Full Copyright Statement 1020 Copyright (C) The Internet Society (2005). 1022 This document is subject to the rights, licenses and restrictions 1023 contained in BCP 78, and except as set forth therein, the authors 1024 retain all their rights. 1026 This document and the information contained herein are provided on an 1027 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1028 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1029 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1030 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1031 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1032 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1034 Intellectual Property 1036 The IETF takes no position regarding the validity or scope of any 1037 Intellectual Property Rights or other rights that might be claimed to 1038 pertain to the implementation or use of the technology described in 1039 this document or the extent to which any license under such rights 1040 might or might not be available; nor does it represent that it has 1041 made any independent effort to identify any such rights. Information 1042 on the ISOC's procedures with respect to rights in ISOC Documents can 1043 be found in BCP 78 and BCP 79. 1045 Copies of IPR disclosures made to the IETF Secretariat and any 1046 assurances of licenses to be made available, or the result of an 1047 attempt made to obtain a general license or permission for the use of 1048 such proprietary rights by implementers or users of this 1049 specification can be obtained from the IETF on-line IPR repository at 1050 http://www.ietf.org/ipr. 1052 The IETF invites any interested party to bring to its attention any 1053 copyrights, patents or patent applications, or other proprietary 1054 rights that may cover technology that may be required to implement 1055 this standard. Please address the information to the IETF at ietf- 1056 ipr@ietf.org. 1058 Acknowledgement 1060 Funding for the RFC Editor function is currently provided by the 1061 Internet Society.