idnits 2.17.1 draft-krovetz-umac-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 12. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1102. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1120. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1126. ** 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 (September 2005) is 6799 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 197 -- Looks like a reference, but probably isn't: 'Hexadecimal' on line 197 -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Obsolete informational reference (is this intentional?): RFC 2406 (ref. '5') (Obsoleted by RFC 4303, RFC 4305) Summary: 4 errors (**), 0 flaws (~~), 2 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 March 2006 September 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 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 UMAC message authentication algorithm. UMAC is designed to 36 be very fast to compute in software on contemporary uniprocessors. 37 Measured speeds are as low as one cycle per byte. UMAC relies on 38 addition of 32-bit and 64-bit numbers and multiplication of 32-bit 39 numbers, operations well-supported by contemporary machines. 41 To generate the authentication tag on a given message, a "universal" 42 hash function is applied to the message and key to produce a short, 43 fixed-length hash value, and this hash value is then xor'ed with a 44 key-derived pseudorandom pad. UMAC enjoys a rigorous security 45 analysis and its only internal "cryptographic" use is a block cipher 46 to generate the pseudorandom pads and internal key material. 48 Table of Contents 50 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 51 2 Notation and basic operations . . . . . . . . . . . . . . . . . . 4 52 2.1 Operations on strings . . . . . . . . . . . . . . . . . . . 4 53 2.2 Operations on integers . . . . . . . . . . . . . . . . . . . 5 54 2.3 String-Integer conversion operations . . . . . . . . . . . . 5 55 2.4 Mathematical operations on strings . . . . . . . . . . . . . 6 56 2.5 ENDIAN-SWAP: Adjusting endian orientation . . . . . . . . . 6 57 3 Key and pad derivation functions . . . . . . . . . . . . . . . . 7 58 3.1 Block cipher choice . . . . . . . . . . . . . . . . . . . . 7 59 3.2 KDF: Key-derivation function . . . . . . . . . . . . . . . . 7 60 3.3 PDF: Pad-derivation function . . . . . . . . . . . . . . . . 8 61 4 UMAC tag generation . . . . . . . . . . . . . . . . . . . . . . . 9 62 4.1 UMAC Algorithm . . . . . . . . . . . . . . . . . . . . . . . 9 63 4.2 UMAC-32, UMAC-64, UMAC-96 and UMAC-128 . . . . . . . . . . . 10 64 5 UHASH: Universal hash function . . . . . . . . . . . . . . . . . 10 65 5.1 UHASH Algorithm . . . . . . . . . . . . . . . . . . . . . . 11 66 5.2 L1-HASH: First-layer hash . . . . . . . . . . . . . . . . . 12 67 5.3 L2-HASH: Second-layer hash . . . . . . . . . . . . . . . . . 14 68 5.4 L3-HASH: Third-layer hash . . . . . . . . . . . . . . . . . 16 69 6 Security considerations . . . . . . . . . . . . . . . . . . . . . 17 70 6.1 Resistance to cryptanalysis . . . . . . . . . . . . . . . . 17 71 6.2 Tag lengths and forging probability . . . . . . . . . . . . 17 72 6.3 Nonce considerations . . . . . . . . . . . . . . . . . . . . 19 73 6.4 Replay attacks . . . . . . . . . . . . . . . . . . . . . . . 20 74 6.5 Tag-prefix verification . . . . . . . . . . . . . . . . . . 20 75 6.6 Side-channel attacks . . . . . . . . . . . . . . . . . . . . 20 76 7 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 21 77 8 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 21 78 Appendix - Test vectors . . . . . . . . . . . . . . . . . . . . . . 21 79 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 80 Author contact information . . . . . . . . . . . . . . . . . . . . . 23 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 can produce a correct tag for any message of its choosing is 93 no more than 1/2^30, 1/2^60, 1/2^90 or 1/2^120, respectively (the 94 symbol ^ represents exponentiation). This probability increases 95 linearly with the number of forgery attempts, namely, during N 96 forgery attempts the probability of getting at least one tag right is 97 at most N times the above numbers. See Section 6.2 for further 98 information. Analysis relevant to UMAC security is in [3, 6]. 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 one-and-a-half and twice as long. 113 UMAC is a MAC in the style of Wegman and Carter [4, 7]. A fast 114 "universal" hash function is used to hash an input message M 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 keyed 119 hash function H and pseudorandom function F. A tag is generated by 120 performing the computation 122 Tag = H_K1(M) xor F_K2(Nonce) 124 where K1 and K2 are secret keys shared by sender and receiver, and 125 Nonce is a value that changes with each generated tag. The receiver 126 needs to 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 evaluated to resolve the meaning of the variable. For 149 example, if i=2, then M_{2 * i} refers to the variable M_4. 151 2.1 Operations on strings 153 Messages to be hashed are viewed as strings of bits which get zero- 154 padded to an appropriate byte-length. Once the message is padded, 155 all strings are viewed as strings of bytes. A "byte" is an 8-bit 156 string. The following notation is used to manipulate these strings. 158 bytelength(S): The length of string S in bytes. 160 bitlength(S): The length of string S in bits. 162 zeroes(n): The string made of n zero-bytes. 164 S xor T: The string which is the bitwise exclusive-or of S 165 and T. Strings S and T always have the same length. 167 S and T: The string which is the bitwise conjunction of S and 168 T. Strings S and T always have the same length. 170 S[i]: The i-th byte of the string S (indices begin at 1). 172 S[i...j]: The substring of S consisting of bytes i through j. 174 S || T: The string S concatenated with string T. 176 zeropad(S,n): The string S, padded with zero-bits to the nearest 177 positive multiple of n bytes. Formally, 178 zeropad(S,n) = S || T, where T is the shortest 179 string of zero-bits (possibly empty) so that S || T 180 is non-empty and 8n divides bitlength(S || T). 182 2.2 Operations on integers 184 Standard notation is used for most mathematical operations, such as 185 "*" for multiplication, "+" for addition and "mod" for modular 186 reduction. Some less standard notations are defined here. 188 a^i: The integer a raised to the i-th power. 190 ceil(x): The smallest integer greater than or equal to x. 192 prime(n): The largest prime number less than 2^n. 194 The prime numbers used in UMAC are: 196 +-----+--------------------+---------------------------------------+ 197 | n | prime(n) [Decimal] | prime(n) [Hexadecimal] | 198 +-----+--------------------+---------------------------------------+ 199 | 36 | 2^36 - 5 | 0x0000000F FFFFFFFB | 200 | 64 | 2^64 - 59 | 0xFFFFFFFF FFFFFFC5 | 201 | 128 | 2^128 - 159 | 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFF61 | 202 +-----+--------------------+---------------------------------------+ 204 2.3 String-Integer conversion operations 206 Conversion between strings and integers is done using the following 207 functions. Each function treats initial bits as more significant 208 than later ones. 210 bit(S,n): Returns the integer 1 if the n-th bit of the string 211 S is 1, otherwise returns the integer 0 (indices 212 begin at 1). 214 str2uint(S): The non-negative integer whose binary representation 215 is the string S. More formally, if S is t bits long 216 then str2uint(S) = 2^{t-1} * bit(S,1) + 2^{t-2} * 217 bit(S,2) + ... + 2^{1} * bit(S,t-1) + bit(S,t). 219 uint2str(n,i): The i-byte string S such that str2uint(S) = n. 221 2.4 Mathematical operations on strings 223 One of the primary operations in UMAC is repeated application of 224 addition and multiplication on strings. The operations "+_32", 225 "+_64" and "*_64" are defined 227 "S +_32 T" as uint2str(str2uint(S) + str2uint(T) mod 2^32, 4), 228 "S +_64 T" as uint2str(str2uint(S) + str2uint(T) mod 2^64, 8) and 229 "S *_64 T" as uint2str(str2uint(S) * str2uint(T) mod 2^64, 8). 231 These operations correspond well with the addition and multiplication 232 operations which are performed efficiently by modern computers. 234 2.5 ENDIAN-SWAP: Adjusting endian orientation 236 Message data is read little-endian to speed tag generation on little- 237 endian computers. 239 2.5.1 ENDIAN-SWAP Algorithm 241 Input: 242 S, string with length divisible by 4 bytes. 243 Output: 244 T, string S with each 4-byte word endian-reversed. 246 Compute T using the following algorithm. 248 // 249 // Break S into 4-byte chunks 250 // 251 n = bytelength(S) / 4 252 Let S_1, S_2, ..., S_n be strings of length 4 bytes 253 so that S_1 || S_2 || ... || S_n = S. 255 // 256 // Byte-reverse each chunk, and build-up T 257 // 258 T = 259 for i = 1 to n do 260 Let W_1, W_2, W_3, W_4 be bytes 261 so that W_1 || W_2 || W_3 || W_4 = S_i 262 SReversed_i = W_4 || W_3 || W_2 || W_1 263 T = T || SReversed_i 264 end for 266 Return T 268 3 Key and pad derivation functions 270 Pseudorandom bits are needed internally by UHASH and at the time of 271 tag generation. The functions listed in this section use a block 272 cipher to generate these bits. 274 3.1 Block cipher choice 276 UMAC uses the services of a block cipher. The selection of a block 277 cipher defines the following constants and functions. 279 BLOCKLEN The length, in bytes, of the plaintext block on 280 which the block cipher operates. 282 KEYLEN The block cipher's key length, in bytes. 284 ENCIPHER(K,P) The application of the block cipher on P (a string 285 of BLOCKLEN bytes) using key K (a string of KEYLEN 286 bytes). 288 As an example, if AES is used with 16-byte keys, then BLOCKLEN would 289 equal 16 (because AES employs 16-byte blocks), KEYLEN would equal 290 16, and ENCIPHER would refer to the AES function. 292 Unless specified otherwise, AES with 128-bit keys shall be assumed to 293 be the chosen block cipher for UMAC. Only if explicitly specified 294 otherwise, and agreed by communicating parties, shall some other 295 block cipher be used. In any case, BLOCKLEN must be at least 16 and 296 a power of two. 298 AES is defined in another document [1]. 300 3.2 KDF: Key-derivation function 302 The key-derivation function generates pseudorandom bits used to key 303 the hash functions. 305 3.2.1 KDF Algorithm 306 Input: 307 K, string of length KEYLEN bytes // block cipher key 308 index, an integer in the range 0...7. 309 numbytes, a positive integer. 310 Output: 311 Y, string of length numbytes bytes. 313 Compute Y using the following algorithm. 315 // 316 // Calculate number of block cipher iterations, set starting point 317 // 318 n = ceil(numbytes / BLOCKLEN) 319 B = uint2str((2 * index + 1)^2 + index, 1) xor uint2str(90, 1) 320 T = B repeated BLOCKLEN times 321 Y = 323 // 324 // Build Y using block cipher in a feedback mode 325 // 326 for i = 1 to n do 327 T = T[1...(BLOCKLEN - 1)] || uint2str(i mod 256, 1) 328 T = ENCIPHER(K, T) 329 Y = Y || T 330 end for 332 Y = Y[1...numbytes] 334 Return Y 336 3.3 PDF: Pad-derivation function 338 This function takes a key and a nonce and returns a pseudorandom pad 339 for use in tag generation. A pad of length 4, 8, 12 or 16 bytes can 340 be generated. Notice that pads generated using nonces that differ 341 only in their last bit (when generating 8-byte pads) or last two bits 342 (when generating 4-byte pads) are derived from the same block cipher 343 encryption. This allows caching and sharing a single block cipher 344 invocation for sequential nonces. 346 3.3.1 PDF Algorithm 348 Input: 349 K, string of length KEYLEN bytes 350 Nonce, string of length 1 to BLOCKLEN bytes. 352 taglen, the integer 4, 8, 12 or 16. 353 Output: 354 Y, string of length taglen bytes. 356 Compute Y using the following algorithm. 358 // 359 // Extract and zero low bit(s) of Nonce if needed 360 // 361 if (taglen = 4 or taglen = 8) 362 index = str2uint(Nonce) mod (BLOCKLEN/taglen) 363 Nonce = Nonce xor uint2str(index, bytelength(Nonce)) 364 end if 366 // 367 // Make Nonce BLOCKLEN bytes by appending zeroes if needed 368 // 369 Nonce = Nonce || zeroes(BLOCKLEN - bytelength(Nonce)) 371 // 372 // Generate subkey, encipher and extract indexed substring 373 // 374 K' = KDF(K, 0, KEYLEN) 375 T = ENCIPHER(K', Nonce) 376 if (taglen = 4 or taglen = 8) 377 Y = T[1 + (index*taglen) ... taglen + (index*taglen)] 378 else 379 Y = T[1...taglen] 380 end if 382 Return Y 384 4 UMAC tag generation 386 Tag generation for UMAC proceeds by using UHASH (defined in the next 387 section) to hash the message, applying the PDF to the nonce and 388 computing the xor of the resulting strings. The length of the pad 389 and hash can be either 4, 8, 12 or 16 bytes. 391 4.1 UMAC Algorithm 393 Input: 394 K, string of length KEYLEN bytes. 395 M, string of length less than 2^67 bits. 396 Nonce, string of length 1 to BLOCKLEN bytes. 398 taglen, the integer 4, 8, 12 or 16. 399 Output: 400 Tag, string of length taglen bytes. 402 Compute Tag using the following algorithm. 404 HashedMessage = UHASH(K, M, taglen) 405 Pad = PDF(K, Nonce, taglen) 406 Tag = Pad xor HashedMessage 408 Return Tag 410 4.2 UMAC-32, UMAC-64, UMAC-96 and UMAC-128 412 The preceding UMAC definition has a parameter "taglen" which 413 specifies the length of tag generated by the algorithm. The 414 following aliases define names that make tag length explicit in the 415 name. 417 UMAC-32(K, M, Nonce) = UMAC(K, M, Nonce, 4) 418 UMAC-64(K, M, Nonce) = UMAC(K, M, Nonce, 8) 419 UMAC-96(K, M, Nonce) = UMAC(K, M, Nonce, 12) 420 UMAC-128(K, M, Nonce) = UMAC(K, M, Nonce, 16) 422 5 UHASH: Universal hash function 424 UHASH is a keyed hash function, which takes as input a string of 425 arbitrary length, and produces a 4-, 8-, 12- or 16-byte output. 426 UHASH does its work in three stages, or layers. A message is first 427 hashed by L1-HASH, its output is then hashed by L2-HASH, whose output 428 is then hashed by L3-HASH. If the message being hashed is no longer 429 than 1024 bytes, then L2-HASH is skipped as an optimization. Because 430 L3-HASH outputs a string whose length is only four bytes long, 431 multiple iterations of this three-layer hash are used if a total 432 hash-output longer than four bytes is requested. To reduce memory 433 use, L1-HASH reuses most of its key material between iterations. A 434 significant amount of internal key is required for UHASH, but it 435 remains constant so long as UMAC's key is unchanged. It is the 436 implementor's choice whether to generate the internal keys each time 437 a message is hashed, or to cache them between messages. 439 Please note that UHASH has certain combinatoric properties making it 440 suitable for Wegman-Carter message authentication. UHASH is not a 441 cryptographic hash function and is not a suitable general replacement 442 for functions like SHA-1. 444 UHASH is presented here in a top-down manner. First UHASH is 445 described, then each of its component hashes are presented. 447 5.1 UHASH Algorithm 449 Input: 450 K, string of length KEYLEN bytes. 451 M, string of length less than 2^67 bits. 452 taglen, the integer 4, 8, 12 or 16. 453 Output: 454 Y, string of length taglen bytes. 456 Compute Y using the following algorithm. 458 // 459 // One internal iteration per 4 bytes of output 460 // 461 iters = taglen / 4 463 // 464 // Define total key needed for all iterations using KDF. 465 // L1Key and L3Key1 reuse most key material between iterations. 466 // 467 L1Key = KDF(K, 1, 1024 + (iters - 1) * 16) 468 L2Key = KDF(K, 2, iters * 24) 469 L3Key1 = KDF(K, 3, iters * 64) 470 L3Key2 = KDF(K, 4, iters * 4) 472 // 473 // For each iteration, extract key and three-layer hash. 474 // If bytelength(M) <= 1024, then skip L2-HASH. 475 // 476 Y = 477 for i = 1 to iters do 478 L1Key_i = L1Key [(i-1) * 16 + 1 ... (i-1) * 16 + 1024] 479 L2Key_i = L2Key [(i-1) * 24 + 1 ... i * 24] 480 L3Key1_i = L3Key1[(i-1) * 64 + 1 ... i * 64] 481 L3Key2_i = L3Key2[(i-1) * 4 + 1 ... i * 4] 483 A = L1-HASH(L1Key_i, M) 484 if (bitlength(M) <= bitlength(L1Key_i)) then 485 B = zeroes(8) || A 486 else 487 B = L2-HASH(L2Key_i, A) 488 end if 489 C = L3-HASH(L3Key1_i, L3Key2_i, B) 490 Y = Y || C 491 end for 493 Return Y 495 5.2 L1-HASH: First-layer hash 497 The first-layer hash breaks the message into 1024-byte chunks and 498 hashes each with a function called NH. Concatenating the results 499 forms a string which is up to 128 times shorter than the original. 501 5.2.1 L1-HASH Algorithm 503 Input: 504 K, string of length 1024 bytes. 505 M, string of length less than 2^67 bits. 506 Output: 507 Y, string of length (8 * ceil(bytelength(M)/1024)) bytes. 509 Compute Y using the following algorithm. 511 // 512 // Break M into 1024 byte chunks (final chunk may be shorter) 513 // 514 t = ceil(bytelength(M) / 1024) 515 Let M_1, M_2, ..., M_t be strings so that M = M_1 || M_2 || ... || 516 M_t, and bytelength(M_i) = 1024 for all 0 < i < t. 518 // 519 // For each chunk, except the last: endian-adjust, NH hash 520 // and add bit-length. Use results to build Y. 521 // 522 Len = uint2str(1024 * 8, 8) 523 Y = 524 for i = 1 to t-1 do 525 ENDIAN-SWAP(M_i) 526 Y = Y || (NH(K, M_i) +_64 Len) 527 end for 529 // 530 // For the last chunk: pad to 32-byte boundary, endian-adjust, 531 // NH hash and add bit-length. Concatenate the result to Y. 532 // 533 Len = uint2str(bitlength(M_t), 8) 534 M_t = zeropad(M_t, 32) 535 ENDIAN-SWAP(M_t) 536 Y = Y || (NH(K, M_t) +_64 Len) 538 return Y 540 5.2.2 NH Algorithm 542 Because this routine is applied directly to every bit of input 543 data, optimized implementation of it yields great benefit. 545 Input: 546 K, string of length 1024 bytes. 547 M, string with length divisible by 32 bytes. 548 Output: 549 Y, string of length 8 bytes. 551 Compute Y using the following algorithm. 553 // 554 // Break M and K into 4-byte chunks 555 // 556 t = bytelength(M) / 4 557 Let M_1, M_2, ..., M_t be 4-byte strings 558 so that M = M_1 || M_2 || ... || M_t. 559 Let K_1, K_2, ..., K_t be 4-byte strings 560 so that K_1 || K_2 || ... || K_t is a prefix of K. 562 // 563 // Perform NH hash on the chunks, pairing words for multiplication 564 // which are 4 apart to accommodate vector-parallelism. 565 // 566 Y = zeroes(8) 567 i = 1 568 while (i < t) do 569 Y = Y +_64 ((M_{i+0} +_32 K_{i+0}) *_64 (M_{i+4} +_32 K_{i+4})) 570 Y = Y +_64 ((M_{i+1} +_32 K_{i+1}) *_64 (M_{i+5} +_32 K_{i+5})) 571 Y = Y +_64 ((M_{i+2} +_32 K_{i+2}) *_64 (M_{i+6} +_32 K_{i+6})) 572 Y = Y +_64 ((M_{i+3} +_32 K_{i+3}) *_64 (M_{i+7} +_32 K_{i+7})) 573 i = i + 8 574 end while 576 Return Y 578 5.3 L2-HASH: Second-layer hash 580 The second-layer rehashes the L1-HASH output using a polynomial hash 581 called POLY. If the L1-HASH output is long, then POLY is called once 582 on a prefix of the L1-HASH output and called using different settings 583 on the remainder. (This two-step hashing of the L1-HASH output is 584 only needed if the message length is greater than 16 megabytes.) 585 Careful implementation of POLY is necessary to avoid a possible 586 timing attack (see Section 6.6 for more information). 588 5.3.1 L2-HASH Algorithm 590 Input: 591 K, string of length 24 bytes. 592 M, string of length less than 2^64 bytes. 593 Output: 594 Y, string of length 16 bytes. 596 Compute y using the following algorithm. 598 // 599 // Extract keys and restrict to special key-sets 600 // 601 Mask64 = uint2str(0x01ffffff01ffffff, 8) 602 Mask128 = uint2str(0x01ffffff01ffffff01ffffff01ffffff, 16) 603 k64 = str2uint(K[1...8] and Mask64) 604 k128 = str2uint(K[9...24] and Mask128) 606 // 607 // If M is no more than 2^17 bytes, hash under 64-bit prime, 608 // otherwise, hash first 2^17 bytes under 64-bit prime and 609 // remainder under 128-bit prime. 610 // 611 if (bytelength(M) <= 2^17) then // 2^14 64-bit words 613 // 614 // View M as an array of 64-bit words, and use POLY modulo 615 // prime(64) (and with bound 2^64 - 2^32) to hash it. 616 // 617 y = POLY(64, 2^64 - 2^32, k64, M) 618 else 619 M_1 = M[1...2^17] 620 M_2 = M[2^17 + 1 ... bytelength(M)] 621 M_2 = zeropad(M_2 || uint2str(0x80,1), 16) 622 y = POLY(64, 2^64 - 2^32, k64, M_1) 623 y = POLY(128, 2^128 - 2^96, k128, uint2str(y, 16) || M_2) 625 end if 627 Y = uint2str(y, 16) 629 Return Y 631 5.3.2 POLY Algorithm 633 Input: 634 wordbits, The integer 64 or 128. 635 maxwordrange, positive integer less than 2^wordbits. 636 k, integer in the range 0 ... prime(wordbits) - 1. 637 M, string with length divisible by (wordbits / 8) bytes. 638 Output: 639 y, integer in the range 0 ... prime(wordbits) - 1. 641 Compute y using the following algorithm. 643 // 644 // Define constants used for fixing out-of-range words 645 // 646 wordbytes = wordbits / 8 647 p = prime(wordbits) 648 offset = 2^wordbits - p 649 marker = p - 1 651 // 652 // Break M into chunks of length wordbytes bytes 653 // 654 n = bytelength(M) / wordbytes 655 Let M_1, M_2, ..., M_n be strings of length wordbytes bytes 656 so that M = M_1 || M_2 || ... || M_n 658 // 659 // Each input word m is compared with maxwordrange. If not smaller 660 // then 'marker' and (m - offset), both in range, are hashed. 661 // 662 y = 1 663 for i = 1 to n do 664 m = str2uint(M_i) 665 if (m >= maxwordrange) then 666 y = (k * y + marker) mod p 667 y = (k * y + (m - offset)) mod p 668 else 669 y = (k * y + m) mod p 670 end if 672 end for 674 Return y 676 5.4 L3-HASH: Third-layer hash 678 The output from L2-HASH is 16 bytes long. This final hash function 679 hashes the 16-byte string to a fixed length of 4 bytes. 681 5.4.1 L3-HASH Algorithm 683 Input: 684 K1, string of length 64 bytes. 685 K2, string of length 4 bytes. 686 M, string of length 16 bytes. 687 Output: 688 Y, string of length 4 bytes. 690 Compute Y using the following algorithm. 692 y = 0 694 // 695 // Break M and K1 into 8 chunks and convert to integers 696 // 697 for i = 1 to 8 do 698 M_i = M [(i - 1) * 2 + 1 ... i * 2] 699 K_i = K1[(i - 1) * 8 + 1 ... i * 8] 700 m_i = str2uint(M_i) 701 k_i = str2uint(K_i) mod prime(36) 702 end for 704 // 705 // Inner-product hash, extract last 32 bits and affine-translate 706 // 707 y = (m_1 * k_1 + ... + m_8 * k_8) mod prime(36) 708 y = y mod 2^32 709 Y = uint2str(y, 4) 710 Y = Y xor K2 712 Return Y 714 6 Security considerations 716 As a message authentication code specification, this entire document 717 is about security. Here we describe some security considerations 718 important for the proper understanding and use of UMAC. 720 6.1 Resistance to cryptanalysis 722 The strength of UMAC depends on the strength of its underlying 723 cryptographic functions: the key-derivation function (KDF) and the 724 pad-derivation function (PDF). In this specification both operations 725 are implemented using a block cipher, presumably the Advanced 726 Encryption Standard (AES). However, the design of UMAC allows for 727 the replacement of these components. Indeed, it is straightforward 728 to use other block ciphers or other cryptographic objects, such as 729 (properly keyed) SHA-1 or HMAC for the realization of the KDF or PDF. 731 The core of the UMAC design, the UHASH function, does not depend on 732 cryptographic assumptions: its strength is specified by a purely 733 mathematical property stated in terms of collision probability, and 734 this property is proven in an absolute sense [3, 6]. This means the 735 strength of UHASH is guaranteed regardless of advances in 736 cryptanalysis. 738 The analysis of UMAC [3, 6] shows this scheme to have provable 739 security, in the sense of modern cryptography, by way of tight 740 reductions. What this means is that an adversarial attack on UMAC 741 that forges with probability significantly exceeding the established 742 collision probability will give rise to an attack of comparable 743 complexity which breaks the block cipher, in the sense of 744 distinguishing the block cipher from a family of random permutations. 745 This design approach essentially obviates the need for cryptanalysis 746 on UMAC: cryptanalytic efforts might as well focus on the block 747 cipher, the results imply. 749 6.2 Tag lengths and forging probability 751 A MAC algorithm is used between two parties that share a secret MAC 752 key, K. Messages transmitted between these parties are accompanied 753 by authentication tags computed using K and a given nonce. Breaking 754 the MAC means that the attacker is able to generate, on its own, with 755 no knowledge of the key K, a new message M (i.e. one not previously 756 transmitted between the legitimate parties) and to compute on M a 757 correct authentication tag under the key K. This is called a 758 forgery. Note that if the authentication tag is specified to be of 759 length t then the attacker can trivially break the MAC with 760 probability 1/2^t. For this the attacker can just generate any 761 message of its choice and try a random tag; obviously, the tag is 762 correct with probability 1/2^t. By repeated guesses the attacker can 763 increase linearly its probability of success. 765 In the case of UMAC the above guessing-attack strategy is close to 766 optimal. For example, in the case of UMAC-64 an adversary can 767 correctly guess an 8-byte UMAC tag with probability 1/2^64 by simply 768 guessing a random value. The results of [3, 6] show that no feasible 769 attack strategy can produce a correct tag with probability better 770 than 1/2^60 if UMAC were to use a random function in its work rather 771 than AES. Another result [2], when combined with [3, 6], shows that 772 so long as AES is secure as a pseudorandom permutation, it can be 773 used instead of a random function without losing the 1/2^60 forging 774 probability, assuming that no more than 2^64 messages are 775 authenticated. Likewise 32-, 96- and 128-bit tags cannot be forged 776 with more than 1/2^30, 1/2^90 and 1/2^120 probability. 778 With UMAC, off-line computation aimed at exceeding the forging 779 probability is hopeless as long as the underlying cipher is not 780 broken. The only way to forge is to interact with the entity that 781 verifies the MAC and to try a huge number of forgeries before one is 782 likely to succeed. The system architecture will determine the extent 783 to which this is possible. In a well-architected system there should 784 not be any high-bandwidth capability for presenting forged MACs and 785 determining if they are valid. In particular, the number of 786 authentication failures at the verifying party should be limited. If 787 a large number of such attempts are detected the session key in use 788 should be dropped and the event be recorded in an audit log. 790 Let us reemphasize: a forging probability of 1/2^60 does not mean 791 that there is an attack that runs in 2^60 time; to the contrary, as 792 long as the block cipher in use maintains its believed security there 793 is no such attack for UMAC. Instead, a 1/2^60 forging probability 794 means that if an attacker could have N forgery attempts, then the 795 attacker would have no more than N/2^60 probability of getting one or 796 more of them right. In conclusion, 64-bit tags seem appropriate for 797 most security architectures and applications. 799 If one wants more security, at a cost of about 50% or 100% more 800 computation, UMAC can produce 96- or 128-bit tags that have collision 801 probabilities of at most 1/2^90 and 1/2^120. If one needs less 802 security, with the benefit of about 50% less computation, UMAC can 803 produce 32-bit tags. In this case, under the same assumptions as 804 before, one can not forge a message with probability better than 805 1/2^30. Special care must be taken when using 32-bit tags because 806 1/2^30 forgery probability is considered fairly high. Still, high- 807 speed low-security authentication can be applied usefully on low- 808 value data or rapidly-changing key environments. 810 It should be pointed out that once an attempted forgery is 811 successful, it is possible, in principle, that subsequent messages 812 under this key may be forged, too. This is important to understand 813 in gauging the severity of a successful forgery, even though no such 814 attack on UMAC is known to date. 816 6.3 Nonce considerations 818 UMAC requires a nonce with length in the range 1 to BLOCKLEN bytes. 819 All nonces in an authentication session must be equal in length. For 820 secure operation, no nonce value should be repeated within the life 821 of a single UMAC session-key. 823 To authenticate messages over a duplex channel (where two parties 824 send messages to each other), a different key could be used for each 825 direction. If the same key is used in both directions, then it is 826 crucial that all nonces be distinct. For example, one party can use 827 even nonces while the other party uses odd ones. The receiving party 828 must verify that the sender is using a nonce of the correct form. 830 This specification does not indicate how nonce values are created, 831 updated, or communicated between the entity producing a tag and the 832 entity verifying a tag. The following are possibilities: 834 1. The nonce is an eight-byte unsigned number, Counter, which is 835 initialized to zero, which is incremented by one following the 836 generation of each authentication tag, and which is always 837 communicated along with the message and the authentication tag. 838 An error occurs at the sender if there is an attempt to 839 authenticate more than 2^64 messages within a session. 841 2. The nonce is a BLOCKLEN-byte unsigned number, Counter, which is 842 initialized to zero and which is incremented by one following the 843 generation of each authentication tag. The Counter is not 844 explicitly communicated between the sender and receiver. 845 Instead, the two are assumed to communicate over a reliable 846 transport, and each maintains its own counter so as to keep track 847 of what the current nonce value is. 849 3. The nonce is a BLOCKLEN-byte random value. (Because repetitions 850 in a random n-bit value are expected at around 2^(n/2) trials, 851 the number of messages to be communicated in a session using n- 852 bit nonces should not be allowed to approach 2^(n/2).) 854 We emphasize that the value of the nonce need not be kept secret. 856 When UMAC is used within a higher-level protocol there may already be 857 a field, such as a sequence number, which can be co-opted so as to 858 specify the nonce needed by UMAC [5]. The application will then 859 specify how to construct the nonce from this already-existing field. 861 6.4 Replay attacks 863 A replay attack entails the attacker repeating a message, nonce, and 864 authentication tag. In many applications, replay attacks may be 865 quite damaging and must be prevented. In UMAC, this would normally 866 be done at the receiver by having the receiver check that no nonce 867 value is used twice. On a reliable connection, when the nonce is a 868 counter, this is trivial. On an unreliable connection, when the 869 nonce is a counter, one would normally cache some window of recent 870 nonces. Out-of-order message delivery in excess of what the window 871 allows will result in rejecting otherwise valid authentication tags. 872 We emphasize that it is up to the receiver when a given (message, 873 nonce, tag) triple will be deemed authentic. Certainly the tag 874 should be valid for the message and nonce, as determined by UMAC, but 875 the message may still be deemed inauthentic because the nonce is 876 detected to be a replay. 878 6.5 Tag-prefix verification 880 UMAC's definition makes it possible to implement tag-prefix 881 verification; for example, a receiver might verify only the 32-bit 882 prefix of a 64-bit tag if its computational load is high. Or a 883 receiver might reject out-of-hand a 64-bit tag whose 32-bit prefix is 884 incorrect. Such practices are potentially dangerous and can lead to 885 attacks that reduce the security of the session to the length of the 886 verified prefix. A UMAC key (or session) must have an associated and 887 immutable tag length and the implementation should not leak 888 information that would reveal if a given proper prefix of a tag is 889 valid or invalid. 891 6.6 Side-channel attacks 893 Side-channel attacks have the goal of subverting the security of a 894 cryptographic system by exploiting its implementation 895 characteristics. One common side-channel attack is to measure system 896 response time and derive information regarding conditions met by the 897 data being processed. Such attacks are known as "timing attacks". 898 Discussion of timing and other side-channel attacks is outside of 899 this document's scope. However, we warn that there are places in the 900 UMAC algorithm where timing information could be unintentionally 901 leaked. In particular, the POLY algorithm (Section 5.3.2) tests 902 whether a value m is out of a particular range, and the behavior of 903 the algorithm differs depending on the result. If timing attacks are 904 to be avoided, care should be given to equalize the computation time 905 in both cases. Timing attacks can also occur for more subtle 906 reasons, including caching effects. 908 7 IANA Considerations 910 This document has no actions for IANA. 912 8 Acknowledgments 914 David McGrew and Scott Fluhrer, of Cisco Systems, played a 915 significant role in improving UMAC by encouraging us to pay more 916 attention to the performance of short messages. Black, Krovetz, and 917 Rogaway have received support for this work under NSF awards 0208842, 918 0240000, 9624560, and a gift from Cisco Systems. Funding for the RFC 919 Editor function is currently provided by the Internet Society. 921 Appendix - Test vectors 923 Following are some sample UMAC outputs over a collection of input 924 values, using AES with 16-byte keys. Let 926 K = "abcdefghijklmnop" // A 16-byte UMAC key 927 N = "bcdefghi" // An 8-byte nonce 929 The tags generated by UMAC using key K and nonce N are: 931 Message 32-bit Tag 64-bit Tag 96-bit Tag 932 ------- ---------- ---------- ---------- 933 EC085847 B9FE492F357C6DF8 3383059D11C13E532BD1E310 934 'a' * 3 5DA7EE32 0851FF5A9FFA52A0 822CB3E8BB47010BAEC943F8 935 'a' * 2^10 C8B389F9 9D459891837A7B7D 1738D423A7C728D603BE1725 936 'a' * 2^15 7B4291BF 2EB480D7EB0EFACA A4C9CC65CFB3A961C5456D6D 937 'a' * 2^20 A1AB1E5D F45D0F35F15E64D4 7E204387D5E3377F131EF03D 938 'a' * 2^25 961CA14D C3EAB025C055F3DB 4997FC97E4E8A0709A5842DD 939 'abc' * 1 CA507696 9FA667FE61D9E4C8 15DB2B4C4564B763303B8E31 940 'abc' * 500 87347438 D2C26550692E16F1 58BF29E24D93455AE5A05F07 942 The first column lists a small sample of messages which are strings 943 of repeated ASCII 'a' bytes or 'abc' strings. The remaining columns 944 give in hexadecimal the tags generated when UMAC is called with the 945 corresponding message, nonce N and key K. 947 When using key K and producing a 64-bit tag, the following relevant 948 keys are generated: 950 Iteration 1 Iteration 2 951 ----------- ----------- 952 NH (Sec 5.2.2) 954 K_1 6A4CCAC8 45B6482B 955 K_2 7D284F5D A1D1EEE0 956 K_3 574E8F49 588794C4 957 K_4 6CF44825 D7B6EE25 958 K_5 45B6482B 6496AA93 959 ... 960 K_256 E0FB2534 D1D8FCA2 962 L2-HASH (Sec 5.3.1) 964 k64 019B156C01BC4DB9 01323C7B0131A9AA 966 L3-HASH (Sec 5.4.1) 968 k_5 3851BD978 232452052 969 k_6 9BE0BCC94 2C6BE19F3 970 k_7 E9AADA709 03F8215DA 971 k_8 73E9A9BD5 91779998C 972 K2 C289A7F1 EF65916D 974 (Note that k_1 ... k_4 are not used in this example because they are 975 multiplied by zero.) 977 When generating a 64-bit tag on input "'abc' * 500", the following 978 intermediate results are produced: 980 Iteration 1 981 ----------- 982 L1-HASH 96658AFE85E951B0C7C22E940AC965FC 983 L2-HASH 0000000000000000FF0048B71C1C3A14 984 L3-HASH 7CC9A8E1 986 Iteration 2 987 ----------- 988 L1-HASH F75648691D2CD179B2AA9169138CA69F 989 L2-HASH 00000000000000006171E964AA02F73F 990 L3-HASH EA25DB2B 992 Concatenating the two L3-HASH results produces a final UHASH result 993 of 7CC9A8E1EA25DB2B. The pad generated for nonce N is 994 AE0BCDB1830BCDDA, which when xor'ed with the L3-HASH result yields a 995 Tag of D2C26550692E16F1. 997 References 999 Normative References 1001 [1] FIPS-197, "Advanced Encryption Standard (AES)", National 1002 Institute of Standards and Technology, 2001. 1004 Informative References 1006 [2] D. Bernstein, "Stronger security bounds for permutations", 1007 unpublished manuscript, 2005. This work refines "Stronger 1008 security bounds for Wegman-Carter-Shoup authenticators", 1009 Advances in Cryptology - EUROCRYPT 2005, LNCS vol. 3494, pp. 1010 164-180, Springer-Verlag, 2005. 1012 [3] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway, 1013 "UMAC: Fast and provably secure message authentication", 1014 Advances in Cryptology - CRYPTO '99, LNCS vol. 1666, pp. 1015 216-233, Springer-Verlag, 1999. 1017 [4] L. Carter and M. Wegman, "Universal classes of hash functions", 1018 Journal of Computer and System Sciences, 18 (1979), pp. 1019 143-154. 1021 [5] S. Kent and R. Atkinson, "IP Encapsulating Security Payload 1022 (ESP)", RFC 2406, IETF, 1998. 1024 [6] T. Krovetz, "Software-optimized universal hashing and message 1025 authentication", UMI Dissertation Services, 2000. 1027 [7] M. Wegman and L. Carter, "New hash functions and their use in 1028 authentication and set equality", Journal of Computer and 1029 System Sciences, 22 (1981), pp. 265-279. 1031 Author contact information 1033 Authors' Addresses 1035 John Black 1036 Department of Computer Science 1037 University of Colorado 1038 Boulder CO 80309 1039 USA 1040 EMail: jrblack@cs.colorado.edu 1042 Shai Halevi 1043 IBM T.J. Watson Research Center 1044 P.O. Box 704 1045 Yorktown Heights NY 10598 1046 USA 1048 EMail: shaih@alum.mit.edu 1050 Alejandro Hevia 1051 Department of Computer Science 1052 University of Chile 1053 Santiago 837-0459 1054 CHILE 1056 EMail: ahevia@dcc.uchile.cl 1058 Hugo Krawczyk 1059 IBM Research 1060 19 Skyline Dr 1061 Hawthorne, NY 10533 1062 USA 1064 EMail: hugo@ee.technion.ac.il 1066 Ted Krovetz 1067 Department of Computer Science 1068 California State University 1069 Sacramento CA 95819 1070 USA 1072 EMail: tdk@acm.org 1074 Phillip Rogaway 1075 Department of Computer Science 1076 University of California 1077 Davis CA 95616 1078 USA 1079 and 1080 Department of Computer Science 1081 Faculty of Science 1082 Chiang Mai University 1083 Chiang Mai 50200 1084 THAILAND 1086 EMail: rogaway@cs.ucdavis.edu 1088 Full Copyright Statement 1090 Copyright (C) The Internet Society (2005). 1092 This document is subject to the rights, licenses and restrictions 1093 contained in BCP 78, and except as set forth therein, the authors 1094 retain all their rights. 1096 This document and the information contained herein are provided on an 1097 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1098 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1099 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1100 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1101 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1102 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1104 Intellectual Property 1106 The IETF takes no position regarding the validity or scope of any 1107 Intellectual Property Rights or other rights that might be claimed to 1108 pertain to the implementation or use of the technology described in 1109 this document or the extent to which any license under such rights 1110 might or might not be available; nor does it represent that it has 1111 made any independent effort to identify any such rights. Information 1112 on the ISOC's procedures with respect to rights in ISOC Documents can 1113 be found in BCP 78 and BCP 79. 1115 Copies of IPR disclosures made to the IETF Secretariat and any 1116 assurances of licenses to be made available, or the result of an 1117 attempt made to obtain a general license or permission for the use of 1118 such proprietary rights by implementers or users of this 1119 specification can be obtained from the IETF on-line IPR repository at 1120 http://www.ietf.org/ipr. 1122 The IETF invites any interested party to bring to its attention any 1123 copyrights, patents or patent applications, or other proprietary 1124 rights that may cover technology that may be required to implement 1125 this standard. Please address the information to the IETF at ietf- 1126 ipr@ietf.org. 1128 Acknowledgment 1130 Funding for the RFC Editor function is currently provided by the 1131 Internet Society.