[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

CFRG Working Group                                           Ted Krovetz
INTERNET-DRAFT                                            CSU Sacramento
Expires October 2007                                             Wei Dai
                                                         Bitvise Limited
                                                              April 2007

       VMAC: Message Authentication Code using Universal Hashing
                      <draft-krovetz-vmac-01.txt>

   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

   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-
   Drafts.

   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
   http://www.ietf.org/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

Abstract

   This specification describes how to generate an authentication tag
   using the VMAC message authentication algorithm.  VMAC is designed to
   have exceptional performance in software on 64-bit CPU architectures
   while still performing well on 32-bit architectures.  Measured speeds
   are as fast as one-half CPU cycle per byte (cpb) on 64-bit
   architectures, under five cpb on desktop 32-bit processors, and
   around ten cpb on embedded 32-bit architectures.










Krovetz & Dai             Expires October 2007                 [Page 1]


INTERNET-DRAFT                    VMAC                        April 2007


                           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  VMAC tag generation . . . . . . . . . . . . . . . . . . . . . . .   9
   4.1  VMAC Algorithm . . . . . . . . . . . . . . . . . . . . . . .   9
   4.2  VMAC-64 and VMAC-128 . . . . . . . . . . . . . . . . . . . .  10
5  VHASH: Universal hash function  . . . . . . . . . . . . . . . . .  10
   5.1  VHASH Constants  . . . . . . . . . . . . . . . . . . . . . .  10
   5.2  VHASH Algorithm  . . . . . . . . . . . . . . . . . . . . . .  11
   5.3  L1-HASH: First-layer hash  . . . . . . . . . . . . . . . . .  11
   5.4  L2-HASH: Second-layer hash . . . . . . . . . . . . . . . . .  13
   5.5  L3-HASH: Third-layer hash  . . . . . . . . . . . . . . . . .  14
6  Security considerations . . . . . . . . . . . . . . . . . . . . .  15
   6.1  Resistance to cryptanalysis  . . . . . . . . . . . . . . . .  15
   6.2  Tag lengths and forging probability  . . . . . . . . . . . .  16
   6.3  Nonce considerations . . . . . . . . . . . . . . . . . . . .  17
   6.4  Replay attacks . . . . . . . . . . . . . . . . . . . . . . .  18
7  IANA Considerations . . . . . . . . . . . . . . . . . . . . . . .  18
Appendix - Test vectors  . . . . . . . . . . . . . . . . . . . . . .  19
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  19
Author contact information . . . . . . . . . . . . . . . . . . . . .  20
Full Copyright Statement . . . . . . . . . . . . . . . . . . . . . .  20
Intellectual Property  . . . . . . . . . . . . . . . . . . . . . . .  21
Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . . . .  21

















Krovetz & Dai             Expires October 2007                 [Page 2]


INTERNET-DRAFT                    VMAC                        April 2007


1  Introduction

   VMAC is a message authentication code (MAC) algorithm designed for
   high performance.  It is backed by a formal analysis, and there are
   no intellectual property claims made by any of the authors to any
   ideas used in its design.

   VMAC is a MAC in the style of Wegman and Carter [4, 8].  A fast
   "universal" hash function is used to hash an input message M into a
   short string.  This short string is then combined by addition with a
   pseudorandom pad, resulting in the VMAC tag.  Security depends on the
   sender and receiver sharing a randomly-chosen secret hash function
   and pseudorandom pad.  This is achieved by using keyed hash function
   H and pseudorandom function F.  A tag is generated by performing the
   computation

     Tag = H_K1(M) + F_K2(Nonce)

   where K1 and K2 are secret random keys 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
   agreeing upon the use of some other non-repeating value such as a
   sequence number.  The nonce need not be kept secret, but care needs
   to be taken to ensure that, over the lifetime of a VMAC key, a
   different nonce is used with each message.

   VMAC uses a function, called VHASH (also specified in this document),
   as the keyed hash function H and uses a pseudorandom function F whose
   default implementation uses the AES block cipher.  VMAC allows for
   tag lengths of any 64-bit multiple up to the block size of the block
   cipher in use.  When using AES, this means VMAC can produce 64- or
   128-bit tags.

   The theory of Wegman-Carter MACs and the analysis of VMAC show that
   if one "instantiates" VMAC with truly random keys and pads then the
   probability that an attacker (even a computationally unbounded one)
   produces a correct tag for messages of its choosing is less than
   1/2^60 or 1/2^120 when the tags are of length 64 or 128 bits,
   respectively (here the symbol ^ represents exponentiation).  When an
   attacker makes N forgery attempts the probability of getting one or
   more tags right increases linearly to less than N/2^60 or N/2^120.
   In a real implementation of VMAC, using AES to produce keys and pads,
   these forgery probabilities increase by a small amount related to the
   security of AES.  As long as AES is secure, this small additive term
   is insignificant for any practical attack.  See Section 6.2 for more
   details.  Analysis relevant to VMAC security is in [5, 6].



Krovetz & Dai             Expires October 2007                 [Page 3]


INTERNET-DRAFT                    VMAC                        April 2007


   VMAC performs best in environments where 64-bit quantities are
   efficiently read from memory "little-endian" and multiplied into
   128-bit results.  Performance on 32-bit architechtures suppporting
   Intel's SSE2 instruction-set is also very good.  On other 32-bit
   architectures, each 64-bit multiplication is accomplished via four
   32-bit multiplications, resulting in a corresponding slowdown.  The
   data in the following table were generated using the reference
   implementation available at the VMAC website [7]. The table shows
   sample performance on several architectures over message lengths of
   64, 512 and 4096 bytes.

                                          64-bit Tags     128-bit Tags
        Bits/Endian/Architecture         64  512   4K     64  512   4K
    ---------------------------------+-----+----+-----+-----+----+----
    64/LE/AMD Athlon 64 "Manchester" |  6.0  1.1  0.5 |  7.0  1.6  0.9
    64/LE/Intel Core 2 "Merom"       |  5.9  1.2  0.6 |  6.9  1.7  1.1
    64/BE/IBM PowerPC 970FX          | 10.1  2.5  1.6 | 11.4  3.8  3.0
    32/LE/Intel Core 2 "Merom"       |  8.3  2.2  1.4 | 11.1  3.6  2.8
    32/LE/Intel NetBurst "Nocona"    | 15.0  4.4  3.1 | 18.9  7.1  5.8
    32/BE/Freescale PowerPC 7457     | 15.3  6.4  5.3 | 22.1 11.2 10.0
    32/LE/Embedded ARM v5te core     | 39.9 13.1 10.1 | 53.6 22.9 19.8
    ---------------------------------+-----+----+-----+-----+----+----
    Table: Tag generation speed measured in CPU cycles per message
    byte, for cache-resident messages of length 64, 512 and 4K bytes.
    Architechtures are listed as register-size/endianness/model.


2  Notation and basic operations

   The specification of VMAC involves the manipulation of 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 VMAC are denoted in all upper-case letters.  Simple
   functions, such as for string-length, 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 evaluated to resolve the meaning of the variable.  For
   example, if i=2, then M_{2 * i} refers to the variable M_4.


2.1  Operations on strings

   Messages to be hashed are viewed as strings of bits.  The following
   notation is used to manipulate these strings.

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




Krovetz & Dai             Expires October 2007                 [Page 4]


INTERNET-DRAFT                    VMAC                        April 2007


     zeros(n):     The string made of n zero-bits.

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

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

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

     zeropad(S,n): The string S, padded with zero-bits to the nearest
                   multiple of n bits in length.  If S is empty or
                   already a multiple of n in length, nothing is
                   appended.  Formally, zeropad(S,n) = S || T, where T
                   is the shortest string of zero-bits so that
                   bitlength(S || T) is a multiple of n.


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 not less than x.

     floor(x): The largest integer not greater than x.

     a div b:  The largest integer i for which b * i <= a.


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.

     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} * S[1] + 2^{t-2} * S[2] +
                    ... + 2^{1} * S[t-1] + S[t].

     uint2str(n,i): The i-bit string S so that str2uint(S) = n.








Krovetz & Dai             Expires October 2007                 [Page 5]


INTERNET-DRAFT                    VMAC                        April 2007


2.4  Mathematical operations on strings

   One of the primary operations in VMAC is addition and multiplication
   of strings.  The operations "+_64", "+_128" and "*_128"  are defined

    "S +_64 T" as uint2str(str2uint(S) + str2uint(T) mod 2^64, 64),
    "S +_128 T" as uint2str(str2uint(S) + str2uint(T) mod 2^128, 128),
    "S *_128 T" as uint2str(str2uint(S) * str2uint(T) mod 2^128, 128).

   On many 64-bit architectures, these operations can each be
   implemented with one or two assembly-language instructions.


2.5  ENDIAN-SWAP: Adjusting endian orientation

   Message data is normally read little-endian to speed tag generation
   on little-endian computers.


2.5.1  ENDIAN-SWAP Algorithm

   Input:
     S, string with bitlength divisible by 64.
   Output:
     T, string S with each 64-bit substring endian-reversed.

   Compute T using the following algorithm.

     //
     // Partition S into 64-bit substrings
     //
     n = bitlength(S) / 64
     Let S_1, S_2, ..., S_n be strings of length 64 bits
        so that S_1 || S_2 || ... || S_n = S.

     //
     // Endian-reverse each, and build-up T
     //
     T = <empty string>
     for i = 1 to n do
       Let W_1, W_2, ..., W_8  be strings of length 8 bits
          so that W_1 || W_2 || ... || W_8 = S_i
       SReversed_i = W_8 || W_7 || ... || W_1
       T = T || SReversed_i
     end for

     Return T




Krovetz & Dai             Expires October 2007                 [Page 6]


INTERNET-DRAFT                    VMAC                        April 2007


3  Key and pad derivation functions

   Pseudorandom bits are needed internally by VHASH 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

   VMAC uses the services of a block cipher.  The selection of a block
   cipher defines the following constants and functions.

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

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

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

   As an example, if AES is used with 192-bit keys, then BLOCKLEN would
   equal 128 (because AES employs 128-bit blocks), KEYLEN would equal
   192, and ENCIPHER would refer to the AES block encryption function
   for 192-bit AES keys.

   Unless specified otherwise, AES with 128-bit keys shall be assumed to
   be the chosen block cipher for VMAC.  In any case, BLOCKLEN must be
   at least 128.  AES is defined in another document [1].


3.2  KDF: Key-derivation function

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


3.2.1  KDF Algorithm

   Input:
     K, string of length KEYLEN bits.
     index, an integer in the range 0...255.
     numbits, a non-negative integer.
   Output:
     Y, string of length numbits bits.

   Compute Y using the following algorithm.

     //



Krovetz & Dai             Expires October 2007                 [Page 7]


INTERNET-DRAFT                    VMAC                        April 2007


     // Calculate number of block cipher iterations
     //
     n = ceil(numbits / BLOCKLEN)

     //
     // Build Y using block cipher in a counter mode
     //
     Y = <empty string>
     for i = 0 to (n-1) do
       T = uint2str(index, 8) || uint2str(i, BLOCKLEN-8)
       Y = Y || ENCIPHER(K, T)
     end for
     Y = Y[1...numbits]

     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.  The length of the pad can be any positive
   multiple of 64 bits, up to BLOCKLEN bits.  Notice that when the
   block-cipher block-length is twice as long as the pad, nonces that
   differ only in their last bit 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

   Input:
     K, string of length KEYLEN bits.
     Nonce, string of length less than BLOCKLEN bits.
     taglen, positive multiple of 64, no greater than BLOCKLEN.
   Output:
     Y, string of length taglen bits.

   Compute Y using the following algorithm.

      //
      // Extract and zero low bits of Nonce if needed.
      // If BLOCKLEN/taglen < 2, this step does nothing but set index=0
      //
      Let i be the smallest integer for which BLOCKLEN/taglen <= 2^i
      index = str2uint(Nonce) mod 2^i
      Nonce = Nonce[1...bitlength(Nonce)-i] || zeros(i)

      //



Krovetz & Dai             Expires October 2007                 [Page 8]


INTERNET-DRAFT                    VMAC                        April 2007


      // Make Nonce BLOCKLEN bits by prepending zeros.
      // At least one zero bit is prepended here.
      //
      Nonce = zeros(BLOCKLEN - bitlength(Nonce)) || Nonce

      //
      // Encipher and extract indexed substring
      //
      T = ENCIPHER(K, Nonce)
      Y = T[index * taglen + 1 ... index * taglen + taglen ]

      Return Y


4  VMAC tag generation

   Tag generation for VMAC proceeds by using VHASH (defined in the next
   section) to hash the message, applying the PDF to the nonce and then
   computing the addition of the resulting strings.  The length of the
   pad and hash can be any positive multiple of 64 bits, up to BLOCKLEN
   bits.


4.1  VMAC Algorithm

   Input:
     K, string of length KEYLEN bits.
     M, string of length up to 2^64 bits.
     Nonce, string of length less than BLOCKLEN bits.
     taglen, positive multiple of 64, no greater than BLOCKLEN.
   Output:
     Tag, string of length taglen bits.

   Compute Tag using the following algorithm.

     HashedMessage = VHASH(K, M, taglen)
     Pad           = PDF(K, Nonce, taglen)

     Tag = <empty string>
     for i = 0 to (taglen/64 - 1) do
        T = Pad          [1 + 64 * i ... 64 * (i + 1)] +_64
            HashedMessage[1 + 64 * i ... 64 * (i + 1)]
        Tag = Tag || T
     end for

     Return Tag





Krovetz & Dai             Expires October 2007                 [Page 9]


INTERNET-DRAFT                    VMAC                        April 2007


4.2  VMAC-64 and VMAC-128

   The preceding VMAC definition has a parameter "taglen" which
   specifies the length of tag generated by the algorithm.  The
   following aliases define names that make tag length explicit in the
   name.

     VMAC-64(K, M, Nonce) = VMAC(K, M, Nonce, 64)
     VMAC-128(K, M, Nonce) = VMAC(K, M, Nonce, 128)


5  VHASH: Universal hash function

   VHASH is a keyed hash function, which takes as input a string and
   produces a string output with length that is a multiple of 64 bits.
   VHASH is a three-layered hash function.  A message is first hashed by
   L1-HASH, its output is then hashed by L2-HASH, whose output is then
   hashed by L3-HASH.  This process is done once for each 64 bits of
   output.

   Note that VHASH has certain combinatoric properties making it
   suitable for Wegman-Carter message authentication.  VHASH is not a
   cryptographic hash function and is not a suitable general replacement
   for functions like SHA-1.

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


5.1  VHASH Constants

   The following constants are referred to in the definition of VHASH.
   L1KEYLEN defines how many bits of key material are generated
   internally for the first layer of hashing.  FAVOR-ENDIAN determines
   which endian orientation is used to read messages.

     L1KEYLEN     = 1024
     FAVOR-ENDIAN = LITTLE

   One could change L1KEYLEN to any positive multiple of 128 or change
   FAVOR-ENDIAN to BIG.  A larger L1KEYLEN improves the speed of the
   algorithms at the cost of increased memory usage, and changing FAVOR-
   ENDIAN to BIG improves the speed of the algorithms on big-endian
   machines at the cost of decreased speed on little-endian machines.
   The resulting algorithms would be incompatible with the VMAC and
   VHASH algorithms defined here, but might be useful in custom
   applications.




Krovetz & Dai             Expires October 2007                [Page 10]


INTERNET-DRAFT                    VMAC                        April 2007


5.2  VHASH Algorithm

   Input:
     K, string of length KEYLEN bits.
     M, string of length up to 2^64 bits.
     taglen, positive multiple of 64.
   Output:
     Y, string of length taglen bits.

   Compute Y using the following algorithm.

     Y = <empty string>
     for i = 0 to (taglen/64 - 1) do
        A = L1-HASH(K, M, i)
        B = L2-HASH(K, A, bitlength(M), i)
        Y = Y || L3-HASH(K, B, i)
     end for

     Return Y


5.3  L1-HASH: First-layer hash

   The first-layer hash breaks the message into blocks, each of length
   up to L1KEYLEN (normally defined as 1024 bits), and hashes each with
   a function called NH.  Concatenating the results forms a string which
   is shorter than the original (unless the original length was no
   greater than 128 bits).


5.2.1  L1-HASH Algorithm

   Input:
     K, string of length KEYLEN bits.
     M, string of any length.
     iter, non-negative integer.
   Output:
     Y, string of length ceil(bitlength(M)/L1KEYLEN) * 128 bits.

   Compute Y using the following algorithm.

     //
     // Set subkey for L1-HASH
     //
     T = KDF(K, 128, L1KEYLEN + 128 * iter)
     K = T[1 + 128 * iter ... L1KEYLEN + 128 * iter]
     Y = <empty string>




Krovetz & Dai             Expires October 2007                [Page 11]


INTERNET-DRAFT                    VMAC                        April 2007


     if bitlength(M) > 0 then

        //
        // Break M into L1KEYLEN-bit segments (last one may be shorter)
        //
        t = ceil(bitlength(M) / L1KEYLEN)
        Let M_1, M_2, ..., M_t be strings so that M_1 || M_2 || ...
          || M_t = M, and bitlength(M_i) = L1KEYLEN for all 0 < i < t.

        //
        // For each segment: pad, endian-adjust, NH hash, and use
        // results to build output Y.  Note that padding only effects
        // the final segment because all other segment lengths are
        // already a multiple of 128.
        //
        for i = 1 to t do
           M_i = zeropad(M_i, 128)
           if FAVOR-ENDIAN = LITTLE then
              ENDIAN-SWAP(M_i)
           end if
           Y = Y || NH(K, M_i)
        end for

     end if

     Return Y


5.2.2  NH Algorithm

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

   Input:
     K, string with length a multiple of 128 bits.
     M, string with length a multiple of 128 bits, but no longer than K.
   Output:
     Y, string of length 128 bits.

   Compute Y using the following algorithm.

     //
     // Partition M and K into 64-bit substrings
     //
     t = bitlength(M) / 64
     Let M_1, M_2, ..., M_t be 64-bit strings
       so that M = M_1 || M_2 || ... || M_t.
     Let K_1, K_2, ..., K_t be 64-bit strings



Krovetz & Dai             Expires October 2007                [Page 12]


INTERNET-DRAFT                    VMAC                        April 2007


       so that K_1 || K_2 || ... || K_t  is a prefix of K.

     //
     // Perform NH hash on each.
     //
     Y = zeros(128)
     i = 1
     while (i < t) do
       Y = Y +_128 ((M_i +_64 K_i) *_128 (M_{i+1} +_64 K_{i+1}))
       i = i + 2
     end while
     Y = zeros(2) || Y[3...128] // Zero two bits (ie, mod 2^126)

     Return Y


5.4  L2-HASH: Second-layer hash

   The second-layer rehashes the L1-HASH output using a polynomial hash.


5.3.1  L2-HASH Algorithm

   Input:
     K, string of length KEYLEN bits.
     M, string with length a multiple of 128 bits.
     len, non-negative integer.
     iter, non-negative integer.
   Output:
     Y, string of length 128 bits.

   Compute y using the following algorithm.

     //
     // Create subkey - the (iter+1)'st 128-bit chunk of the
     // string generated by KDF(K, 192)
     //
     T = KDF(K, 192, 128 * (iter + 1))
     T = T[1 + 128 * iter ... 128 * (iter + 1)]
     k = str2uint(zeros(3) || T[ 4...32] || zeros(3) || T[ 36... 64] ||
                  zeros(3) || T[68...96] || zeros(3) || T[100...128])

     n = bitlength(M) / 128
     if n > 0 then

        //
        // Partition M into 128-bit substrings and polynomial hash
        //



Krovetz & Dai             Expires October 2007                [Page 13]


INTERNET-DRAFT                    VMAC                        April 2007


        Let M_1, M_2, ..., M_n be strings of length 128 bits
          so that M = M_1 || M_2 || ... || M_n

        p127 = 2^127 - 1    // 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF in hex
        y = 1
        for i = 1 to n do
          m_i = str2uint(M_i)
          y = (y * k + m_i) mod p127
        end for

     else

        //
        // M is an empty string; handled as a special case
        //
        y = k

     end if

     y = (y + (len mod L1KEYLEN) * 2^64) mod p127
     Y = uint2str(y, 128)

     Return Y


5.5  L3-HASH: Third-layer hash

   The output from L2-HASH is 128 bits long.  This final hash function
   hashes the 128-bit string to a fixed length of 64 bits.


5.4.1  L3-HASH Algorithm

   Input:
     K, string of length KEYLEN bits.
     M, string of length 128 bits.
     iter, non-negative integer.
   Output:
     Y, string of length 64 bits.

   Compute Y using the following algorithm.

     //
     // Create subkey - the (iter+1)'st 128-bit chunk of the
     // string generated by KDF(K, 224) that passes a test
     //
     p64 = 2^64 - 257     // 0xFFFFFFFFFFFFFEFF in hex
     i = 0



Krovetz & Dai             Expires October 2007                [Page 14]


INTERNET-DRAFT                    VMAC                        April 2007


     need = iter + 1
     repeat
        T    = KDF(K, 224, 128 * (i + 1))
        T    = T[1 + 128 * i ... 128 * (i + 1)]
        k_1  = str2uint(T[ 0... 64])
        k_2  = str2uint(T[65...128])
        i    = i + 1
        if (k_1 < p64) and (k_2 < p64) then
           need = need - 1
        end if
     until (need = 0)

     //
     // Transform M into two integers less than p64 and hash
     //
     m_1  = str2uint(M) div (2^64 - 2^32)
     m_2  = str2uint(M) mod (2^64 - 2^32)
     y = ((m_1 + k_1) * (m_2 + k_2)) mod p64
     Y = uint2str(y, 64)

     Return Y


6  Security considerations

   Here we describe some security considerations important for the
   proper understanding and use of VMAC.


6.1  Resistance to cryptanalysis

   The strength of VMAC 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, by default the Advanced
   Encryption Standard (AES).  However, the core of the VMAC design, the
   VHASH function, does not depend on cryptographic assumptions: its
   strength is specified by a purely mathematical property stated in
   terms of collision probability, and this property is proven
   unconditionally [5, 6].  This means the strength of VHASH is
   guaranteed regardless of advances in cryptanalysis and that an
   adversarial attack on VMAC that forges with probability significantly
   exceeding the established collision probability of VHASH 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 VMAC: cryptanalytic efforts might as
   well focus on the block cipher.



Krovetz & Dai             Expires October 2007                [Page 15]


INTERNET-DRAFT                    VMAC                        April 2007


6.2  Tag lengths and forging probability

   A MAC algorithm is used to authenticate messages between two parties
   that share a secret MAC key K.  An authentication tag is computed for
   a message using K and, in some MAC algorithms such as VMAC, a nonce.
   Messages transmitted between parties are accompanied by their tag
   and, possibly, 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 (ie, one not previously transmitted between the legitimate
   parties) and to compute on M a 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.

   In the case of VMAC-64, for example, the above guessing-attack
   strategy is close to optimal.  An adversary can correctly guess a
   64-bit VMAC tag with probability 1/2^64 by simply guessing a random
   value.  The theory of Wegman-Carter MACs and results of [5, 6] show
   that no attack strategy can produce a correct tag with probability
   better than 1/2^60 if VMAC were to use a random function in its work
   rather than AES.  Another result shows that so long as AES is secure
   as a pseudorandom permutation, it can be used instead of a random
   function without significantly increasing the 1/2^60 forging
   probability, assuming that no more than 2^64 messages are
   authenticated with the same key [2].  Similarly for VMAC-128, the
   per-message forgery probability, when using a random function rather
   than AES to instantiate VMAC is no more than 1/2^120.

   AES has undergone extensive study and is assumed to be very secure as
   a pseudorandom permutation.  If we assume that no attacker with
   feasible computational power can distinguish randomly keyed AES from
   a randomly chosen permutation with probability delta (more precisely,
   delta is a function of the computational resources of the attacker
   and of its ability to sample the function), then we obtain that no
   such attacker can forge messages in VMAC with probability greater
   than about 1/2^60 or 1/2^120, plus delta.  Over N forgery attempts,
   forgery occurs with probability no more than N/^60 or N/2^120, plus
   delta.  The value delta could possibly be greater than 1/2^60 or
   1/2^120, in which case the probability of VMAC forging is dominated
   by a term representing the security of AES.

   With VMAC, off-line computation aimed at exceeding the forging
   probability is hopeless as long as the underlying cipher is not
   broken.  An attacker attempting to forge VMAC tags will need to
   interact with the entity that verifies message tags and try a large



Krovetz & Dai             Expires October 2007                [Page 16]


INTERNET-DRAFT                    VMAC                        April 2007


   number 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.

   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 is not broken there is no such attack
   for VMAC.  Instead, a 1/2^60 forging probability means that if an
   attacker could have N forgery attempts, then the attacker would have
   no more than N/2^60 probability of getting one or more of them right.

   It should be pointed out that once an attacker knows that an
   attempted forgery is successful, it is possible, in principle, that
   subsequent messages under this key may be more easily forged.  This
   is important to understand in gauging the severity of a successful
   forgery, even though no such attack on VMAC is known to date.  Due to
   the short-lived nature of most authentication sessions, 64-bit tags
   are appropriate for many security architectures and applications.
   If, however, one wants a more conservative option, at a cost of about
   double the computation, VMAC's 128-bit tags may be more appropriate.


6.3  Nonce considerations

   VMAC requires a nonce with length less than BLOCKLEN bits.  All
   nonces in an authentication session must be unique and equal in
   length.

   The security of VMAC depends on the assumption that no nonce is ever
   used to generate tags for more than one message under the same key.
   If an attacker is able to observe two VMAC tags that were generated
   using the same key, the same nonce, and different messages, he may be
   able to easily forge other VMAC tags.  While such an attack is not
   known to date, VMAC was not designed to offer any protection in this
   scenario, and nonce reuse must be prevented through appropriate
   system architecture.

   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



Krovetz & Dai             Expires October 2007                [Page 17]


INTERNET-DRAFT                    VMAC                        April 2007


   entity verifying a tag, but there are many possibilities.  Nonce
   values could be randomly generated, could come from an incrementing
   counter, or could be co-opted from some non-repeating part of the
   messages being authenticated (such as a sequence number).  The nonce
   can then be sent along with the message if necessary, or if the
   receiver is able to deduce the nonce in use, the nonce need not be
   sent.  We emphasize that the nonce need not be kept secret, but that
   no nonce should be used more than once in any session by either
   sender or receiver.

   Designers of systems and applications that use VMAC should be aware
   that modern virtual machine software such as VMware may allow the
   user of a virtual machine to roll back its state (both persistent
   storage and volatile memory) to earlier snapshots or checkpoints.
   This rollback may be part of an attack, or simply due to an unrelated
   decision by an authorized user.  In any case, if VMAC is used in such
   a virtual machine, a rollback may cause a nonce to be reused,
   intentionally or unintentionally, thus violating an important
   security assumption.  The system or application must either prevent
   the occurrence of a state rollback, or be designed to ensure that
   nonces are not reused on different messages even when state rollbacks
   are possible.  For example, one possible design is to generate a
   fresh random string as the nonce for each message, after the content
   of that message has been fixed.

6.4  Replay attacks

   A replay attack occurs when an attacker repeats a message, nonce, and
   authentication tag.  If the replay of a previously authenticated
   message would have negative consequences, then the  receiver should
   identify repeated message-nonce pairs and ignore them.  One way to do
   this is to look for a nonce that has already been used to
   authenticate a prior message, and ignore it.  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 to determine 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 VMAC, 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.




Krovetz & Dai             Expires October 2007                [Page 18]


INTERNET-DRAFT                    VMAC                        April 2007


Appendix - Test vectors

   Following are some sample VMAC outputs over a collection of input
   values, using AES with 128-bit keys.  Let key K and nonce N be
   defined by the following ASCII strings.

     K  = "abcdefghijklmnop"              // A 128-bit VMAC key
     N  = "bcdefghi"                      // A 64-bit nonce

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

     Message           64-bit Tag              128-bit Tag
     -------           ----------              -----------
    <empty>         2576BE1C56D8B81B  472766C70F74ED23481D6D7DE4E80DAC
    'abc' * 1       2D376CF5B1813CE5  4EE815A06A1D71EDD36FC75D51188A42
    'abc' * 16      E8421F61D573D298  09F2C80C8E1007A0C12FAE19FE4504AE
    'abc' * 100     4492DF6C5CAC1BBE  66438817154850C61D8A412164803BCB
    'abc' * 1000000 09BA597DD7601113  2B6B02288FFC461B75485DE893C629DC

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


References

Normative References

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

Informative References

   [2]   D. Bernstein, "Stronger security bounds for permutations",
         unpublished manuscript, 2005.  This work refines "Stronger
         security bounds for Wegman-Carter-Shoup authenticators",
         Advances in Cryptology - EUROCRYPT 2005, LNCS vol. 3494, pp.
         164-180, Springer-Verlag, 2005.

   [3]   J. Black, S. Halevi, A. Hevia, H. Krawczyk, T. Krovetz, and P.
         Rogaway, "UMAC: Message authentication code using universal
         hashing", RFC 4418, IETF, 2006.

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




Krovetz & Dai             Expires October 2007                [Page 19]


INTERNET-DRAFT                    VMAC                        April 2007


   [5]   W. Dai and T. Krovetz, "VMAC high-speed message
         authentication", in progress.

   [6]   T. Krovetz, "Message auhentication on 64-bit architectures",
         Selected Areas in Cryptography - SAC 2006, Springer-Verlag,
         2006.

   [7]   VMAC Website, http://fastcrypto.com/vmac, as seen April 2007.

   [8]   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

   Author Addresses

     Ted Krovetz
     Department of Computer Science
     California State University
     Sacramento CA 95819
     USA
     Email: tdk@acm.org

     Wei Dai
     Bitvise Limited
     Email: rfc@weidai.com


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   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
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.






Krovetz & Dai             Expires October 2007                [Page 20]


INTERNET-DRAFT                    VMAC                        April 2007


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
   http://www.ietf.org/ipr.

   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-
   ipr@ietf.org.


Acknowledgments

   This document borrows much text from RFC 4418 [3].  That document
   describes another message authentication scheme, UMAC, and was co-
   written by John Black, Shai Halevi, Alejandro Hevia, Hugo Krawczyk,
   Ted Krovetz and Phillip Rogaway. Funding for the RFC Editor function
   is currently provided by the Internet Society.



















Krovetz & Dai             Expires October 2007                [Page 21]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/