[Search] [pdf|bibtex] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 07 rfc4418                               
CFRG Working Group                                    T. Krovetz, Editor
INTERNET-DRAFT                                            CSU Sacramento
Expires December 2005                                          June 2005

       UMAC: Message Authentication Code using Universal Hashing

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at

   The list of Internet-Draft Shadow Directories can be accessed at


   This specification describes how to generate an authentication tag
   using the UMAC message authentication algorithm.  UMAC is designed to
   be very fast to compute in software on contemporary uniprocessors.
   Measured speeds are as low as one cycle per byte.  UMAC relies on
   addition of 32-bit and 64-bit numbers and multiplication of 32-bit
   numbers, operations well-supported by contemporary machines.

   To generate the authentication tag on a given message, a "universal"
   hash function is applied to the message and key to produce a short,
   fixed-length hash value, and this hash value is then xor'ed with a
   key-derived pseudorandom pad.  UMAC enjoys a rigorous security
   analysis and its only internal "cryptographic" use is a block cipher
   to generate the pseudorandom pads and internal key material.

Krovetz, et al.           Expires December 2005                [Page 1]

INTERNET-DRAFT                    UMAC                         June 2005

                           Table of Contents

1  Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . .   3
2  Notation and basic operations . . . . . . . . . . . . . . . . . .   4
   2.1  Operations on strings  . . . . . . . . . . . . . . . . . . .   4
   2.2  Operations on integers . . . . . . . . . . . . . . . . . . .   5
   2.3  String-Integer conversion operations . . . . . . . . . . . .   5
   2.4  Mathematical operations on strings . . . . . . . . . . . . .   6
   2.5  ENDIAN-SWAP: Adjusting endian orientation  . . . . . . . . .   6
3  Key and pad derivation functions  . . . . . . . . . . . . . . . .   7
   3.1  Block cipher choice  . . . . . . . . . . . . . . . . . . . .   7
   3.2  KDF: Key-derivation function . . . . . . . . . . . . . . . .   7
   3.3  PDF: Pad-derivation function . . . . . . . . . . . . . . . .   8
4  UMAC tag generation . . . . . . . . . . . . . . . . . . . . . . .   9
   4.1  UMAC Algorithm . . . . . . . . . . . . . . . . . . . . . . .   9
   4.2  UMAC-32, UMAC-64, UMAC-96 and UMAC-128 . . . . . . . . . . .  10
5  UHASH: Universal hash function  . . . . . . . . . . . . . . . . .  10
   5.1  L1-HASH: First-layer hash  . . . . . . . . . . . . . . . . .  12
   5.2  L2-HASH: Second-layer hash . . . . . . . . . . . . . . . . .  14
   5.3  L3-HASH: Third-layer hash  . . . . . . . . . . . . . . . . .  16
6  Security considerations . . . . . . . . . . . . . . . . . . . . .  17
   6.1  Resistance to cryptanalysis  . . . . . . . . . . . . . . . .  17
   6.2  Tag lengths and forging probability  . . . . . . . . . . . .  17
   6.3  Nonce considerations . . . . . . . . . . . . . . . . . . . .  19
   6.4  Guarding against replay attacks  . . . . . . . . . . . . . .  20
7  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . .  20
8  Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  20
Appendix - Test vectors  . . . . . . . . . . . . . . . . . . . . . .  21
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  21
Author contact information . . . . . . . . . . . . . . . . . . . . .  22

Krovetz, et al.           Expires December 2005                [Page 2]

INTERNET-DRAFT                    UMAC                         June 2005

1  Introduction

   UMAC is a message authentication algorithm (MAC) designed for high
   performance.  It has been rigorously proven to be secure and there
   are no intellectual property claims made to any ideas used in its

   The output of UMAC is a string called a tag.  UMAC is designed to
   produce 32-, 64-, 96- or 128-bit tags, depending on the user's
   preference, with 64 bits recommended for most applications.  When
   UMAC produces 32-, 64-, 96- or 128-bit tags, the probability that an
   attacker could produce a correct tag for any message of its choosing
   is about 1/2^30, 1/2^60, 1/2^90 or 1/2^120, respectively.  These
   probabilities remains the same for each new forgery attempt by the
   attacker.  Our analysis has shown that doing any better would imply
   that an effective attack exists for the block cipher in use.  Hence,
   assuming the block cipher is strong, so is UMAC.  Security analysis
   of UMAC is in [2, 5].

   UMAC performs best in environments where 32-bit quantities are
   efficiently multiplied into 64-bit results. In producing 64-bit tags
   on an Intel Pentium 4 using SSE2 instructions, which do two of these
   multiplications in parallel, UMAC processes messages at a peak rate
   of about one CPU cycle per byte, with the peak being achieved on
   messages of around four kilobytes and longer.  On the Pentium III,
   without the use of SSE parallelism, UMAC achieves a peak of two
   cycles per byte.  On shorter messages UMAC still performs well:
   around four cycles per byte on 256 byte messages and under two cycles
   per byte on 1500 byte messages.  The time to produce a 32-bit tag is
   a little more than half that needed to produce a 64-bit tag, while
   96- and 128-bit tags take about one-and-a-half and twice as long.

   UMAC is a MAC in the style of Wegman and Carter [3, 6].  A fast
   "universal" hash function is used to hash an input message into a
   short string.  This short string is then masked by xor'ing with a
   pseudorandom string, resulting in the UMAC tag.  Security depends on
   the sender and receiver sharing a randomly-chosen secret hash
   function and pseudorandom string.  This is achieved by using a keyed
   hash function h and pseudorandom function f.  A tag is thus generated
   by performing the computation

     tag = f_k(nonce) xor h_k(message)

   where k is a secret key shared by sender and receiver, and nonce is a
   value that changes with each generated tag.  The receiver needs to
   know which nonce was used by the sender, so some method of
   synchronizing nonces needs to be used.  This can be done by
   explicitly sending the nonce along with the message and tag, or

Krovetz, et al.           Expires December 2005                [Page 3]

INTERNET-DRAFT                    UMAC                         June 2005

   agreeing upon the use of some other non-repeating value such as
   message number.  The nonce need not be kept secret, but care needs to
   be taken to ensure that, over the lifetime of the UMAC key, a
   different nonce is used with each message.

   Optimized source code, performance data and papers concerning UMAC
   can be found at http://www.cs.ucdavis.edu/~rogaway/umac/.

2  Notation and basic operations

   The specification of UMAC involves the manipulation of both strings
   and numbers.  String variables are denoted with an initial upper-case
   letter, whereas numeric variables are denoted in all lower case.  The
   algorithms of UMAC are denoted in all upper-case letters.  Simple
   functions, like those for string-length and string-xor, are written
   in all lower case.

   Whenever a variable is followed by an underscore ("_"), the
   underscore is intended to denote a subscript, with the subscripted
   expression needing to be evaluated to resolve the meaning of the
   variable.  For example, if i=2, then M_{2 * i} refers to the variable

2.1  Operations on strings

   Messages to be hashed are viewed as strings of bits which get zero-
   padded to an appropriate byte-length.  Once the message is padded,
   all strings are viewed as strings of bytes.  A "byte" is an 8-bit
   string.  The following notation is used to manipulate these strings.

     bytelength(S): The length of string S in bytes.

     bitlength(S):  The length of string S in bits.

     zeroes(n):     The string made of n zero-bytes.

     S xor T:       The string which is the bitwise exclusive-or of S
                    and T.  Strings S and T always have the same length.

     S and T:       The string which is the bitwise conjunction of S and
                    T.  Strings S and T always have the same length.

     S[i]:          The i-th byte of the string S (indices begin at 1).

     S[i..j]:       The substring of S consisting of bytes i through j.

Krovetz, et al.           Expires December 2005                [Page 4]

INTERNET-DRAFT                    UMAC                         June 2005

     S || T:        The string S concatenated with string T.

     zeropad(S,n):  The string S, padded with zero-bits to the nearest
                    positive multiple of n bytes.  Formally,
                    zeropad(S,n) = S || T, where T is the shortest
                    string of zero-bits (possibly empty) so that S || T
                    is non-empty and 8n divides bitlength(S || T).

2.2  Operations on integers

   Standard notation is used for most mathematical operations, such as
   "*" for multiplication, "+" for addition and "mod" for modular
   reduction.  Some less standard notations are defined here.

     a^i:      The integer a raised to the i-th power.

     ceil(x):  The smallest integer greater than or equal to x.

     prime(n): The largest prime number less than 2^n.

   The prime numbers used in UMAC are:

    |  n  | prime(n) [Decimal] | prime(n) [Hexadecimal]                |
    | 36  | 2^36  - 5          | 0x0000000F FFFFFFFB                   |
    | 64  | 2^64  - 59         | 0xFFFFFFFF FFFFFFC5                   |
    | 128 | 2^128 - 159        | 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFF61 |

2.3  String-Integer conversion operations

   Conversion between strings and integers is done using the following
   functions.  Each function treats initial bits as more significant
   than later ones.

     bit(S,n):      Returns the integer 1 if the n-th bit of the string
                    S is 1, otherwise returns the integer 0 (indices
                    begin at 1).

     str2uint(S):   The non-negative integer whose binary representation
                    is the string S.  More formally, if S is t bits long
                    then str2uint(S) = 2^{t-1} * bit(S,1) + 2^{t-2} *
                    bit(S,2) + ... + 2^{1} * bit(S,t-1) + bit(S,t).

Krovetz, et al.           Expires December 2005                [Page 5]

INTERNET-DRAFT                    UMAC                         June 2005

     uint2str(n,i): The i-byte string S such that str2uint(S) = n.

2.4  Mathematical operations on strings

   One of the primary operations in UMAC is repeated application of
   addition and multiplication on strings.  The operations "+_32",
   "+_64" and "*_64"  are defined

     "S +_32 T" as uint2str(str2uint(S) + str2uint(T) mod 2^32, 4),
     "S +_64 T" as uint2str(str2uint(S) + str2uint(T) mod 2^64, 8) and
     "S *_64 T" as uint2str(str2uint(S) * str2uint(T) mod 2^64, 8).

   These operations correspond well with the addition and multiplication
   operations which are performed efficiently on registers by modern

2.5  ENDIAN-SWAP: Adjusting endian orientation

   Message data is read little-endian to speed tag generation on little-
   endian computers.  On little-endian processors, this is a free

2.5.1  ENDIAN-SWAP Algorithm

     S, string with length divisible by 4 bytes.
     T, string S with each 4-byte word endian-reversed.

   Compute T using the following algorithm.

     // Break S into 4-byte chunks
     n = bytelength(S) / 4
     Let S_1, S_2, ..., S_n be strings of length 4 bytes
        so that S_1 || S_2 || ... || S_n = S.

     // Byte-reverse each chunk, and build-up T
     T = <empty string>
     for i = 1 to n do
       Let W_1, W_2, W_3, W_4  be bytes

Krovetz, et al.           Expires December 2005                [Page 6]

INTERNET-DRAFT                    UMAC                         June 2005

          so that W_1 || W_2 || W_3 || W_4 = S_i
       SReversed_i = W_4 || W_3 || W_2 || W_1
       T = T || SReversed_i
     end for

     Return T

3  Key and pad derivation functions

   Pseudorandom bits are needed internally by UHASH and at the time of
   tag generation.  The functions listed in this section use a block
   cipher to generate these bits.

3.1  Block cipher choice

   UMAC requires the services of a block cipher.  The selection of a
   block cipher defines the following constants and functions.

     BLOCKLEN         The length, in bytes, of the plaintext block on
                      which the block cipher operates.

     KEYLEN           The block cipher's key length, in bytes.

     ENCIPHER(K,P)    The application of the block cipher on P (a string
                      of BLOCKLEN bytes) using key K (a string of KEYLEN

   As an example, if AES is used with 16-byte keys, then BLOCKLEN would
   equal 16 (because AES employs  16-byte blocks), KEYLEN would equal
   16, and ENCIPHER would refer to the AES function.

   Unless specified otherwise, AES with 128-bit keys shall be assumed to
   be the chosen block cipher for UMAC.  Only if explicitly specified
   otherwise, and agreed by communicating parties, shall some other
   block cipher be used.  In any case, BLOCKLEN must be at least 16 and
   a power of two.

   AES is defined in another document [1].

3.2  KDF: Key-derivation function

   The key-derivation function generates pseudorandom bits used to key
   the hash functions.

Krovetz, et al.           Expires December 2005                [Page 7]

INTERNET-DRAFT                    UMAC                         June 2005

3.2.1  KDF Algorithm

     K, string of length KEYLEN bytes  // block cipher key
     index, an integer in the range 0...7.
     numbytes, a positive integer.
     Y, string of length numbytes bytes.

   Compute Y using the following algorithm.

     // Calculate number of block cipher iterations, set starting point
     n = ceil(numbytes / BLOCKLEN)
     B = uint2str((2 * index + 1)^2 + index, 1) xor uint2str(90, 1)
     T = B repeated BLOCKLEN times
     Y = <empty string>

     // Build Y using block cipher in a feedback mode
     for i = 1 to n do
       T = T[1..(BLOCKLEN - 1)] || uint2str(i mod 256, 1)
       T = ENCIPHER(K, T)
       Y = Y || T
     end for

     Y = Y[1..numbytes]

     Return Y

3.3  PDF: Pad-derivation function

   This function takes a key and a nonce and returns a pseudorandom pad
   for use in tag generation.  A pad of length 4, 8, 12 or 16 bytes can
   be generated.  Notice that pads generated using nonces that differ
   only in their last bit (when generating 8-byte pads) or last two bits
   (when generating 4-byte pads) are derived from the same block cipher
   encryption.  This allows caching and sharing a single block cipher
   invocation for sequential nonces.

3.3.1  PDF Algorithm


Krovetz, et al.           Expires December 2005                [Page 8]

INTERNET-DRAFT                    UMAC                         June 2005

     K, string of length KEYLEN bytes
     Nonce, string of length 1 to BLOCKLEN bytes.
     padlen, the integer 4, 8, 12 or 16.
     Y, string of length padlen bytes.

   Compute Y using the following algorithm.

      // Extract and zero low bit(s) of Nonce if needed
      if (padlen = 4 or padlen = 8)
        index = str2uint(Nonce) mod (BLOCKLEN/padlen)
        Nonce = Nonce xor uint2str(index, bytelength(Nonce))
      end if

      // Make Nonce BLOCKLEN bytes by appending zeroes if needed
      Nonce = Nonce || zeroes(BLOCKLEN - bytelength(Nonce))

      // Generate subkey, encipher and extract indexed substring
      K' = KDF(K, 0, KEYLEN)
      T = ENCIPHER(K', Nonce)
      if (padlen = 4 or padlen = 8)
        Y = T[1 + (index*padlen) .. padlen + (index*padlen)]
        Y = T[1..padlen]
      end if

      Return Y

4  UMAC tag generation

   Tag generation for UMAC proceeds by using UHASH (defined in the next
   section) to hash the message, applying the PDF to the nonce and
   computing the xor of the resulting strings.  The length of the pad
   and hash can be either 4, 8, 12 or 16 bytes.

4.1  UMAC Algorithm

     K, string of length KEYLEN bytes.

Krovetz, et al.           Expires December 2005                [Page 9]

INTERNET-DRAFT                    UMAC                         June 2005

     M, string of length less than 2^67 bits.
     Nonce, string of length 1 to BLOCKLEN bytes.
     taglen, the integer 4, 8, 12 or 16.
     AuthTag, string of length taglen bytes.

   Compute AuthTag using the following algorithm.

     HashedMessage = UHASH(K, M, taglen)
     Pad           = PDF(K, Nonce, taglen)
     AuthTag       = Pad xor HashedMessage

     Return AuthTag

4.2  UMAC-32, UMAC-64, UMAC-96 and UMAC-128

   The preceding definition for UMAC has an input parameter "taglen"
   which specifies the length of tag generated by the algorithm.  The
   following aliases define names that make tag length explicit in the

     UMAC-32(K, M, Nonce) = UMAC(K, M, Nonce, 4)
     UMAC-64(K, M, Nonce) = UMAC(K, M, Nonce, 8)
     UMAC-96(K, M, Nonce) = UMAC(K, M, Nonce, 12)
     UMAC-128(K, M, Nonce) = UMAC(K, M, Nonce, 16)

5  UHASH: Universal hash function

   UHASH is a keyed hash function, which takes as input a string of
   arbitrary length, and produces a 4-, 8-, 12- or 16-byte output.
   UHASH does its work in three stages, or layers.  A message is first
   hashed by L1-HASH, its output is then hashed by L2-HASH, whose output
   is then hashed by L3-HASH.  If the message being hashed is no longer
   than 1024 bytes, then L2-HASH is skipped as an optimization.  Because
   L3-HASH outputs a string whose length is only four bytes long,
   multiple iterations of this three-layer hash are used if a total
   hash-output longer than four bytes is requested.  To reduce memory
   use, L1-HASH reuses most of its key material between iterations.  A
   significant amount of internal key is required for UHASH, but it
   remains constant so long as UMAC's key is unchanged.  It is the
   implementor's choice whether to generate the internal keys each time
   a message is hashed, or to cache them between messages.

   Please note that UHASH has certain combinatoric properties making it
   suitable for Wegman-Carter message authentication. UHASH is not a

Krovetz, et al.           Expires December 2005               [Page 10]

INTERNET-DRAFT                    UMAC                         June 2005

   cryptographic hash function and is not a suitable general replacement
   for functions like SHA-1.

   UHASH is presented here in a top-down manner.  First UHASH is
   described, then each of its component hashes are presented.

5.0.1  UHASH Algorithm

     K, string of length KEYLEN bytes.
     M, string of length less than 2^67 bits.
     outlen, the integer 4, 8, 12 or 16.
     Y, string of length outlen bytes.

   Compute Y using the following algorithm.

     // One internal iteration per 4 bytes of output
     iters = outlen / 4

     // Define total key needed for all iterations using KDF.
     // L1Key and L3Key1 reuse most key material between iterations.
     L1Key  = KDF(K, 1, 1024 + (iters - 1) * 16)
     L2Key  = KDF(K, 2, iters * 24)
     L3Key1 = KDF(K, 3, iters * 64)
     L3Key2 = KDF(K, 4, iters * 4)

     // For each iteration, extract key and three-layer hash.
     // If bytelength(M) <= 1024, then skip L2-HASH.
     Y = <empty string>
     for i = 1 to iters do
       L1Key_i  = L1Key [(i-1) * 16 + 1 .. (i-1) * 16 + 1024]
       L2Key_i  = L2Key [(i-1) * 24 + 1 .. i * 24]
       L3Key1_i = L3Key1[(i-1) * 64 + 1 .. i * 64]
       L3Key2_i = L3Key2[(i-1) * 4  + 1 .. i * 4]

       A = L1-HASH(L1Key_i, M)
       if (bitlength(M) <= bitlength(L1Key_i)) then
         B = zeroes(8) || A

Krovetz, et al.           Expires December 2005               [Page 11]

INTERNET-DRAFT                    UMAC                         June 2005

         B = L2-HASH(L2Key_i, A)
       end if
       C = L3-HASH(L3Key1_i, L3Key2_i, B)
       Y = Y || C
     end for

     Return Y

5.1  L1-HASH: First-layer hash

   The first-layer hash breaks the message into 1024 byte chunks and
   hashes each with a function called NH.  The concatenation of these
   hash values results in a string up to 128 times shorter than the

5.1.1  L1-HASH Algorithm

     K, string of length 1024 bytes.
     M, string of length less than 2^67 bits.
     Y, string of length (8 * ceil(bytelength(M)/1024)) bytes.

   Compute Y using the following algorithm.

     // Break M into 1024 byte chunks (final chunk may be shorter)
     t = ceil(bytelength(M) / 1024)
     Let M_1, M_2, ..., M_t be strings so that M = M_1 || M_2 || ... ||
        M_t, and bytelength(M_i) = 1024 for all 0 < i < t.

     // For each chunk, except the last: endian-adjust, NH hash
     // and add bit-length.  Use results to build Y.
     Len = uint2str(1024 * 8, 8)
     Y = <empty string>
     for i = 1 to t-1 do
       Y = Y || (NH(K, M_i) +_64 Len)
     end for

     // For the last chunk: pad to 32-byte boundary, endian-adjust,

Krovetz, et al.           Expires December 2005               [Page 12]

INTERNET-DRAFT                    UMAC                         June 2005

     // NH hash and add bit-length.  Concatenate the result to Y.
     Len = uint2str(bitlength(M_t), 8)
     M_t = zeropad(M_t, 32)
     Y = Y || (NH(K, M_t) +_64 Len)

     return Y

5.1.2  NH Algorithm

        Because this routine is applied directly to every bit of input
        data, optimized implementation of it yields great benefit.

     K, string of length 1024 bytes.
     M, string with length divisible by 32 bytes.
     Y, string of length 8 bytes.

   Compute Y using the following algorithm.

     // Break M and K into 4-byte chunks
     t = bytelength(M) / 4
     Let M_1, M_2, ..., M_t be 4-byte strings
       so that M = M_1 || M_2 || ... || M_t.
     Let K_1, K_2, ..., K_t be 4-byte strings
       so that K_1 || K_2 || ... || K_t  is a prefix of K.

     // Perform NH hash on the chunks, pairing words for multiplication
     // which are 4 apart to accommodate vector-parallelism.
     Y = zeroes(8)
     i = 1
     while (i < t) do
       Y = Y +_64 ((M_{i+0} +_32 K_{i+0}) *_64 (M_{i+4} +_32 K_{i+4}))
       Y = Y +_64 ((M_{i+1} +_32 K_{i+1}) *_64 (M_{i+5} +_32 K_{i+5}))
       Y = Y +_64 ((M_{i+2} +_32 K_{i+2}) *_64 (M_{i+6} +_32 K_{i+6}))
       Y = Y +_64 ((M_{i+3} +_32 K_{i+3}) *_64 (M_{i+7} +_32 K_{i+7}))
       i = i + 8
     end while

Krovetz, et al.           Expires December 2005               [Page 13]

INTERNET-DRAFT                    UMAC                         June 2005

     Return Y

5.2  L2-HASH: Second-layer hash

   The second-layer rehashes the L1-HASH output using a polynomial hash
   called POLY.  If the output of L1-HASH is long, then POLY is called
   once on a prefix of the L1-HASH output and then called using
   different settings on the remainder.  (This two-step hashing of the
   L1-HASH output is only needed if the initial message length is
   greater than 16 megabytes.)

5.2.1  L2-HASH Algorithm

     K, string of length 24 bytes.
     M, string of length less than 2^64 bytes.
     Y, string of length 16 bytes.

   Compute y using the following algorithm.

     //  Extract keys and restrict to special key-sets
     Mask64  = uint2str(0x01ffffff01ffffff, 8)
     Mask128 = uint2str(0x01ffffff01ffffff01ffffff01ffffff, 16)
     k64    = str2uint(K[1..8]  and Mask64)
     k128   = str2uint(K[9..24] and Mask128)

     // If M is no more than 2^17 bytes, hash under 64-bit prime,
     // otherwise, hash first 2^17 bytes under 64-bit prime and
     // remainder under 128-bit prime.
     if (bytelength(M) <= 2^17) then             // 2^14 64-bit words

        // View M as an array of 64-bit words, and use POLY modulo
        // prime(64) (and with bound 2^64 - 2^32) to hash it.
        y = POLY(64, 2^64 - 2^32,  k64, M)
        M_1 = M[1 .. 2^17]
        M_2 = M[2^17 + 1 .. bytelength(M)]
        M_2 = zeropad(M_2 || uint2str(0x80,1), 16)

Krovetz, et al.           Expires December 2005               [Page 14]

INTERNET-DRAFT                    UMAC                         June 2005

        y = POLY(64, 2^64 - 2^32, k64, M_1)
        y = POLY(128, 2^128 - 2^96, k128, uint2str(y, 16) || M_2)
      end if

     Y = uint2str(y, 16)

     Return Y

5.2.2  POLY Algorithm

     wordbits, The integer 64 or 128.
     maxwordrange, positive integer less than 2^wordbits.
     k, integer in the range 0 ... prime(wordbits) - 1.
     M, string with length divisible by (wordbits / 8) bytes.
     y, integer in the range 0 ... prime(wordbits) - 1.

   Compute y using the following algorithm.

     // Define constants used for fixing out-of-range words
     wordbytes = wordbits / 8
     p = prime(wordbits)
     offset = 2^wordbits - p
     marker = p - 1

     // Break M into chunks of length wordbytes bytes
     n = bytelength(M) / wordbytes
     Let M_1, M_2, ..., M_n be strings of length wordbytes bytes
       so that M = M_1 || M_2 || ... || M_n

     // Each input word m is compared with maxwordrange.  If not smaller
     // then 'marker' and (m - offset), both in range, are hashed.
     y = 1
     for i = 1 to n do
       m = str2uint(M_i)
       if (m >= maxwordrange) then
         y = (k * y + marker) mod p
         y = (k * y + (m - offset)) mod p

Krovetz, et al.           Expires December 2005               [Page 15]

INTERNET-DRAFT                    UMAC                         June 2005

         y = (k * y + m) mod p
       end if
     end for

     Return y

5.3  L3-HASH: Third-layer hash

   The output from L2-HASH is 16 bytes long.  This final hash function
   hashes the 16-byte string to a fixed length of 4 bytes.

5.3.1  L3-HASH Algorithm

     K1, string of length 64 bytes.
     K2, string of length 4 bytes.
     M, string of length 16 bytes.
     Y, string of length 4 bytes.

   Compute Y using the following algorithm.

     y = 0

     // Break M and K1 into 8 chunks and convert to integers
     for i = 1 to 8 do
       M_i = M [(i - 1) * 2 + 1 .. i * 2]
       K_i = K1[(i - 1) * 8 + 1 .. i * 8]
       m_i = str2uint(M_i)
       k_i = str2uint(K_i) mod prime(36)
     end for

     // Inner-product hash, extract last 32 bits and affine-translate
     y = (m_1 * k_1 + ... + m_8 * k_8) mod prime(36)
     y = y mod 2^32
     Y = uint2str(y, 4)
     Y = Y xor K2

     Return Y

Krovetz, et al.           Expires December 2005               [Page 16]

INTERNET-DRAFT                    UMAC                         June 2005

6  Security considerations

   As a specification of a message authentication code, this entire
   document is about security.  Here we describe some security
   considerations important for the proper understanding and use of

6.1  Resistance to cryptanalysis

   The strength of UMAC depends on the strength of its underlying
   cryptographic functions: the key-derivation function (KDF) and the
   pad-derivation function (PDF).  In this specification both operations
   are implemented using a block cipher, presumably the Advanced
   Encryption Standard (AES).  However, the design of UMAC allows for
   the replacement of these components.  Indeed, it is straightforward
   to use other block ciphers or other cryptographic objects, such as
   (properly keyed) SHA-1 or HMAC for the realization of the KDF or PDF.

   The core of the UMAC design, the UHASH function, does not depend on
   any cryptographic assumptions: its strength is specified by a purely
   mathematical property stated in terms of collision probability, and
   this property is proven in an absolute sense [2, 5].  In this way,
   the strength of UHASH is guaranteed regardless of future advances in
   cryptanalysis.  The UHASH function was not designed to provide
   cryptographic collision resistance properties, as does SHA-1, and so
   should not be used as a substitute for it.

   The analysis of UMAC [2, 5] shows this scheme to have provable
   security, in the sense of modern cryptography, by way of tight
   reductions.  What this means is that an adversarial attack on UMAC
   which forges with probability significantly exceeding the established
   collision probability will give rise to an attack of comparable
   complexity which breaks the block cipher, in the sense of
   distinguishing the block cipher from a family of random permutations.
   This design approach essentially obviates the need for cryptanalysis
   on UMAC: cryptanalytic efforts might as well focus on the block
   cipher, the results imply.

6.2  Tag lengths and forging probability

   A MAC algorithm is used between two parties that share a secret MAC
   key, K.  Messages transmitted between these parties are accompanied
   by authentication tags computed using K and a given nonce.  Breaking
   the MAC means that the attacker is able to generate, on its own, with
   no knowledge of the key K, a new message M (i.e. one not previously
   transmitted between the legitimate parties) and to compute on M a

Krovetz, et al.           Expires December 2005               [Page 17]

INTERNET-DRAFT                    UMAC                         June 2005

   correct authentication tag under the key K.  This is called a
   forgery.  Note that if the authentication tag is specified to be of
   length t then the attacker can trivially break the MAC with
   probability 1/2^t.  For this the attacker can just generate any
   message of its choice and try a random tag; obviously, the tag is
   correct with probability 1/2^t.  By repeated guesses the attacker can
   increase linearly its probability of success.

   UMAC is designed to make this guessing strategy the best possible
   attack against UMAC as long as the attacker does not invest the
   computational effort needed to break the underlying block cipher used
   to produce the one time pads used in UMAC computation.  More
   precisely, under the assumed strength of this cipher UMAC provides
   for close-to-optimal security with regards to forgery probability.
   An adversary could guess an 8-byte UMAC tag correctly with
   probability 1/2^64 by simply guessing a random value.  The proofs of
   [2, 5] show that an adversary being more clever in tag guessing can
   do no better than about 1/2^60.

   This means that for 8-byte tags the ideal forging probability is
   2^-64 while UMAC produces an actual forging probability of at most
   2^-60.  This probability of forging a message is well under the
   chance that a randomly guessed DES key is correct.  DES is now widely
   seen as vulnerable, but the problem has never been that some
   extraordinarily lucky attacker might, in a single guess, find the
   right key.  Instead, the problem is that large amounts of computation
   can be thrown at the problem until, off-line, the attacker finds the
   right key.

   With  UMAC, off-line computation aimed at exceeding the forging
   probability is hopeless as long as the underlying cipher is not
   broken.  The only way to forge is to interact with the entity that
   verifies the MAC and to try a huge amount of forgeries before one is
   likely to succeed.  The system architecture will determine the extent
   to which this is possible.  In a well-architected system there should
   not be any high-bandwidth capability for presenting forged MACs and
   determining if they are valid.  In particular, the number of
   authentication failures at the verifying party should be limited.  If
   a large number of such attempts are detected the session key in use
   should be dropped and the event be recorded in an audit log.

   Let us reemphasize: a forging probability of 1 / 2^60 does not mean
   that there is an attack that runs in 2^60 time - to the contrary, as
   long as the block cipher in use maintains its believed security there
   is no such attack for UMAC.  Instead, a 1 / 2^60 forging probability
   means that if an attacker could try out 2^60 MACs, then the attacker
   would probably get one right.

Krovetz, et al.           Expires December 2005               [Page 18]

INTERNET-DRAFT                    UMAC                         June 2005

   It should be pointed out that once an attempted forgery is
   successful, it is possible, in principle, that subsequent messages
   under this key may be forged, too.  This is important to understand
   in gauging the severity of a successful forgery, even though no such
   attack on UMAC is known to date.

   In conclusion, 64-bit tags seem appropriate for most security
   architectures and applications.  If one wants more security, at a
   cost of 50% more computation, UMAC can produce 96- and 128-bit tags
   which cannot be forged with probability better than 1/2^90 and
   1/2^120.  Likewise, if less security is required, with the benefit of
   50% less computation, UMAC can produce 32-bit tags which cannot be
   forged with probability better than 1/2^30.  Great care must be taken
   when using 32-bit tags because 1/2^30 forgery probability is
   considered fairly high.  Still, high-speed low-security
   authentication can be applied usefully on low-value data or rapidly-
   changing key environments.

6.3  Nonce considerations

   UMAC requires a nonce with length in the range 1 to BLOCKLEN bytes.
   All nonces in an authentication session must be equal in length.  For
   secure operation, no nonce value should be repeated within the life
   of a single UMAC session-key.

   To authenticate messages over a duplex channel (where two parties
   send messages to each other), a different key could be used for each
   direction.  If the same key is used in both directions, then it is
   crucial that all nonces be distinct.  For example, one party can use
   even nonces while the other party uses odd ones.  The receiving party
   must verify that the sender is using a nonce of the correct form.

   This specification does not indicate how nonce values are created,
   updated, or communicated between the entity producing a tag and the
   entity verifying a tag.  The following exemplify some of the

   1.  The nonce is an eight-byte [resp., four-byte] unsigned number,
       Counter, which is initialized to zero, which is incremented by
       one following the generation of each authentication tag, and
       which is always communicated along with the message and the
       authentication tag.  An error occurs at the sender if there is an
       attempt to authenticate more than 2^64 [resp., 2^32] messages
       within a session.

   2.  The nonce is a BLOCKLEN-byte unsigned number, Counter, which is
       initialized to zero and which is incremented by one following the

Krovetz, et al.           Expires December 2005               [Page 19]

INTERNET-DRAFT                    UMAC                         June 2005

       generation of each authentication tag.  The Counter is not
       explicitly communicated between the sender and receiver.
       Instead, the two are assumed to communicate over a reliable
       transport, and each maintains its own counter so as to keep track
       of what the current nonce value is.

   3.  The nonce is a BLOCKLEN-byte random value.  (Because repetitions
       in a random n-bit value are expected at around 2^(n/2) trials,
       the number of messages to be communicated in a session using n-
       bit nonces should not be allowed to approach 2^(n/2).)

   We emphasize that the value of the nonce need not be kept secret.

   When UMAC is used within a higher-level protocol there may already be
   a field, such as a sequence number, which can be co-opted so as to
   specify the nonce needed by UMAC [5].  The application will then
   specify how to construct the nonce from this already-existing field.

6.4  Guarding against replay attacks

   A replay attack entails the attacker repeating a message, nonce, and
   authentication tag.  In many applications, replay attacks may be
   quite damaging and must be prevented.  In UMAC, this would normally
   be done at the receiver by having the receiver check that no nonce
   value is used twice.  On a reliable connection, when the nonce is a
   counter, this is trivial.  On an unreliable connection, when the
   nonce is a counter, one would normally cache some window of recent
   nonces.  Out-of-order message delivery in excess of what the window
   allows will result in rejecting otherwise valid authentication tags.

   We emphasize that it is up to the receiver when a given (message,
   nonce, tag) triple will be deemed authentic.  Certainly the tag
   should be valid for the message and nonce, as determined by UMAC, but
   the message may still be deemed inauthentic because the nonce is
   detected to be a replay.

7  IANA Considerations

   This document has no actions for IANA.

8  Acknowledgments

   David McGrew and Scott Fluhrer, of Cisco Systems, played a
   significant role in improving UMAC by encouraging us to pay more
   attention to the performance of short messages.  Black, Krovetz, and

Krovetz, et al.           Expires December 2005               [Page 20]

INTERNET-DRAFT                    UMAC                         June 2005

   Rogaway have received support for this work under NSF awards 0208842,
   0240000, 9624560, and a gift from Cisco Systems.  Funding for the RFC
   Editor function is currently provided by the Internet Society.

Appendix - Test vectors

   Following are some sample UMAC outputs over a collection of input
   values, using AES with 16-byte keys.


     K  = "abcdefghijklmnop"                  // A 16-byte UMAC key
     N  = "bcdefghi"                          // An 8-byte nonce

   The tags generated by UMAC using key K and nonce N are:

     Message      32-bit Tag    64-bit Tag            96-bit Tag
     -------      ----------    ----------            ----------
     <empty>       EC085847  B9FE492F357C6DF8  3383059D11C13E532BD1E310
     'a' * 3       5DA7EE32  0851FF5A9FFA52A0  822CB3E8BB47010BAEC943F8
     'a' * 2^10    C8B389F9  9D459891837A7B7D  1738D423A7C728D603BE1725
     'a' * 2^15    7B4291BF  2EB480D7EB0EFACA  A4C9CC65CFB3A961C5456D6D
     'a' * 2^20    A1AB1E5D  F45D0F35F15E64D4  7E204387D5E3377F131EF03D
     'a' * 2^25    961CA14D  C3EAB025C055F3DB  4997FC97E4E8A0709A5842DD
     'abc' * 1     CA507696  9FA667FE61D9E4C8  15DB2B4C4564B763303B8E31
     'abc' * 500   87347438  D2C26550692E16F1  58BF29E24D93455AE5A05F07

   The first column lists a small sample of messages which are strings
   of repeated ASCII 'a' bytes or 'abc' strings.  The remaining columns
   give in hexadecimal the tags generated when UMAC is called with the
   corresponding message, nonce N and key K.


Normative References

   [1]   FIPS-197, "Advanced Encryption Standard (AES)", National
         Institute of Standards and Technology, 2001.

Informative References

   [2]   J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway,
         "UMAC: Fast and provably secure message authentication",
         Advances in Cryptology - CRYPTO '99, LNCS vol. 1666, pp.
         216-233, Springer-Verlag, 1999.

Krovetz, et al.           Expires December 2005               [Page 21]

INTERNET-DRAFT                    UMAC                         June 2005

   [3]   L. Carter and M. Wegman, "Universal classes of hash functions",
         Journal of Computer and System Sciences, 18 (1979), pp.

   [4] S. Kent and R. Atkinson, "IP Encapsulating Security Payload
         (ESP)", RFC 2406, IETF, 1998.

   [5]  T. Krovetz, "Software-optimized universal hashing and message
         authentication", UMI Dissertation Services, 2000.

   [6]  M. Wegman and L. Carter, "New hash functions and their use in
         authentication and set equality", Journal of Computer and
         System Sciences, 22 (1981), pp. 265-279.

Author contact information

   Authors' Addresses

     John Black
     Department of Computer Science
     University of Colorado
     Boulder CO 80309

     EMail: jrblack@cs.colorado.edu

     Shai Halevi
     IBM T.J. Watson Research Center
     P.O. Box 704
     Yorktown Heights NY 10598

     EMail: shaih@alum.mit.edu

     Alejandro Hevia
     Department of Computer Science
     University of Chile
     Santiago 837-0459

     EMail: ahevia@dcc.uchile.cl

     Hugo Krawczyk
     IBM Research
     19 Skyline Dr
     Hawthorne, NY 10533

Krovetz, et al.           Expires December 2005               [Page 22]

INTERNET-DRAFT                    UMAC                         June 2005

     EMail: hugo@ee.technion.ac.il

     Ted Krovetz
     Department of Computer Science
     California State University
     Sacramento CA 95819

     EMail: tdk@acm.org

     Phillip Rogaway
     Department of Computer Science
     University of California
     Davis CA 95616
     Department of Computer Science
     Faculty of Science
     Chiang Mai University
     Chiang Mai 50200

     EMail: rogaway@cs.ucdavis.edu

Krovetz, et al.           Expires December 2005               [Page 23]

INTERNET-DRAFT                    UMAC                         June 2005

Full Copyright Statement

   Copyright (C) The Internet Society (2005).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the ISOC's procedures with respect to rights in ISOC Documents can
   be found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at ietf-


   Funding for the RFC Editor function is currently provided by the
   Internet Society.

Krovetz, et al.           Expires December 2005               [Page 24]