CFRG Working Group T. Krovetz, Editor
INTERNET-DRAFT CSU Sacramento
Expires April 2005 October 2004
UMAC: Message Authentication Code using Universal Hashing
<draft-krovetz-umac-02.txt>
By submitting this Internet-Draft, we certify that any applicable
patent or other IPR claims of which we are aware have been disclosed,
or will be disclosed, and any of which we become aware will be
disclosed, in accordance with RFC 3668
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-
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 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,
AES, to generate the pseudorandom pads and internal key material.
Krovetz Expires April 2005 [Page 1]
INTERNET-DRAFT UMAC October 2004
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 KDF: Key-derivation function . . . . . . . . . . . . . . . . 7
3.2 PDF: Pad-derivation function . . . . . . . . . . . . . . . . 8
4 UMAC tag generation . . . . . . . . . . . . . . . . . . . . . . . 9
4.1 UMAC Algorithm . . . . . . . . . . . . . . . . . . . . . . . 9
4.2 UMAC-32, UMAC-64 and UMAC-96 . . . . . . . . . . . . . . . . 9
5 UHASH: Universal hash function . . . . . . . . . . . . . . . . . 10
5.1 L1-HASH: First-layer hash . . . . . . . . . . . . . . . . . 11
5.2 L2-HASH: Second-layer hash . . . . . . . . . . . . . . . . . 13
5.3 L3-HASH: Third-layer hash . . . . . . . . . . . . . . . . . 15
6 Security considerations . . . . . . . . . . . . . . . . . . . . . 16
6.1 Resistance to cryptanalysis . . . . . . . . . . . . . . . . 16
6.2 Tag lengths and forging probability . . . . . . . . . . . . 17
6.3 Nonce considerations . . . . . . . . . . . . . . . . . . . . 18
6.4 Guarding against replay attacks . . . . . . . . . . . . . . 19
7 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 20
Appendix - Test vectors . . . . . . . . . . . . . . . . . . . . . . 20
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Author contact information . . . . . . . . . . . . . . . . . . . . . 21
Krovetz Expires April 2005 [Page 2]
INTERNET-DRAFT UMAC October 2004
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
design.
The output of UMAC is a string called a tag. UMAC is designed to
produce 32-, 64- or 96-bit tags, depending on the user's preference,
with 64 bits recommended for most applications. When UMAC produces
32-, 64- or 96-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 or 1/2^90, 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 Advanced Encryption Standard (AES). Hence, assuming
AES 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-bit tags take about one-and-a-half times 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 encrypted 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
agreeing upon the use of some other non-repeating value such as
Krovetz Expires April 2005 [Page 3]
INTERNET-DRAFT UMAC October 2004
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
M_4.
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 Expires April 2005 [Page 4]
INTERNET-DRAFT UMAC October 2004
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 Expires April 2005 [Page 5]
INTERNET-DRAFT UMAC October 2004
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
computers.
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
operation.
2.5.1 ENDIAN-SWAP Algorithm
Input:
S, string with length divisible by 4 bytes.
Output:
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 Expires April 2005 [Page 6]
INTERNET-DRAFT UMAC October 2004
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 following two functions use a block cipher to
generate these bits. All references to AES refer to the 128-bit key
encryption function of the Advanced Encryption Standard (AES) [1].
3.1 KDF: Key-derivation function
The key-derivation function generates pseudorandom bits used to key
the hash functions.
3.1.1 KDF Algorithm
Input:
K, string of length 16 bytes // key to AES
index, an integer in the range 0...7.
numbytes, a positive integer.
Output:
Y, string of length numbytes bytes.
Compute Y using the following algorithm.
//
// Calculate number of AES iterations, set indexed starting point
//
n = ceil(numbytes / 16)
B = uint2str((2 * index + 1)^2 + index, 1) xor uint2str(90, 1)
T = B repeated 16 times
Y = <empty string>
//
// Build Y using AES in a feedback mode
//
for i = 1 to n do
T = T[1..15] || uint2str(i mod 256, 1)
T = AES(K, T)
Krovetz Expires April 2005 [Page 7]
INTERNET-DRAFT UMAC October 2004
Y = Y || T
end for
Y = Y[1..numbytes]
Return Y
3.2 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- or 12-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 AES
encryption. This allows caching and sharing a single AES invocation
for sequential nonces.
3.2.1 PDF Algorithm
Input:
K, string of length 16 bytes
Nonce, string of length 1 to 16 bytes.
padlen, the integer 4, 8 or 12.
Output:
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)
index = str2uint(Nonce) mod 4
Nonce = Nonce xor uint2str(index, bytelength(Nonce))
else if (padlen = 8)
index = str2uint(Nonce) mod 2
Nonce = Nonce xor uint2str(index, bytelength(Nonce))
end if
//
// Make Nonce 16 bytes by appending zeroes if needed
//
Nonce = Nonce || zeroes(16 - bytelength(Nonce))
//
Krovetz Expires April 2005 [Page 8]
INTERNET-DRAFT UMAC October 2004
// Generate subkey, AES and extract indexed substring
//
K' = KDF(K, 0, 16)
T = AES(K', Nonce)
if (padlength = 4)
Y = T[1 + (index*4) .. 4 + (index*4)]
else if (padlength = 8)
Y = T[1 + (index*8) .. 8 + (index*8)]
else
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 or 12 bytes.
4.1 UMAC Algorithm
Input:
K, string of length 16 bytes.
M, string of length less than 2^67 bits.
Nonce, string of length 1 to 16 bytes.
taglen, the integer 4, 8 or 12.
Output:
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 and UMAC-96
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
Krovetz Expires April 2005 [Page 9]
INTERNET-DRAFT UMAC October 2004
name.
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)
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- or 12-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
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
Input:
K, string of length 16 bytes.
M, string of length less than 2^67 bits.
outlen, the integer 4, 8 or 12.
Output:
Y, string of length outlen bytes.
Compute Y using the following algorithm.
//
// One internal iteration per 4 bytes of output
//
Krovetz Expires April 2005 [Page 10]
INTERNET-DRAFT UMAC October 2004
iters = outlen / 4
//
// Define total key needed for all iterations using KDF.
// L1Key and L3Key1 both reuse most key 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
else
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
original.
5.1.1 L1-HASH Algorithm
Input:
K, string of length 1024 bytes.
M, string of length less than 2^67 bits.
Krovetz Expires April 2005 [Page 11]
INTERNET-DRAFT UMAC October 2004
Output:
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
ENDIAN-SWAP(M_i) // See endian discussion in section 3.1.1
Y = Y || (NH(K, M_i) +_64 Len)
end for
//
// For the last chunk: pad to 32-byte boundary, endian-adjust,
// NH hash and add bit-length. Concatenate the result to Y.
//
Len = uint2str(bitlength(M_t), 8)
M_t = zeropad(M_t, 32)
ENDIAN-SWAP(M_t)
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.
Input:
K, string of length 1024 bytes.
M, string with length divisible by 32 bytes.
Output:
Y, string of length 8 bytes.
Krovetz Expires April 2005 [Page 12]
INTERNET-DRAFT UMAC October 2004
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
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
Input:
K, string of length 24 bytes.
M, string of length less than 2^64 bytes.
Output:
Y, string of length 16 bytes.
Compute y using the following algorithm.
Krovetz Expires April 2005 [Page 13]
INTERNET-DRAFT UMAC October 2004
//
// 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)
else
M_1 = M[1 .. 2^17]
M_2 = M[2^17 + 1 .. bytelength(M)]
M_2 = zeropad(M_2 || uint2str(0x80,1), 16)
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
Input:
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.
Output:
y, integer in the range 0 ... prime(wordbits) - 1.
Compute y using the following algorithm.
//
// Define constants used for fixing out-of-range words
Krovetz Expires April 2005 [Page 14]
INTERNET-DRAFT UMAC October 2004
//
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
else
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
Input:
K1, string of length 64 bytes.
K2, string of length 4 bytes.
M, string of length 16 bytes.
Output:
Y, string of length 4 bytes.
Compute Y using the following algorithm.
Krovetz Expires April 2005 [Page 15]
INTERNET-DRAFT UMAC October 2004
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
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
UMAC.
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 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
Krovetz Expires April 2005 [Page 16]
INTERNET-DRAFT UMAC October 2004
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 AES, in the sense of distinguishing AES
from a family of random permutations. This design approach
essentially obviates the need for cryptanalysis on UMAC:
cryptanalytic efforts might as well focus on AES, 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
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 cipher, AES, 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
Krovetz Expires April 2005 [Page 17]
INTERNET-DRAFT UMAC October 2004
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 AES 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.
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-bit tags which
cannot be forged with probability better than 1/2^90. 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 16 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
Krovetz Expires April 2005 [Page 18]
INTERNET-DRAFT UMAC October 2004
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
possibilities:
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 16-byte unsigned number, Counter, which is
initialized to zero and which is incremented by one following the
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 16-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
Krovetz Expires April 2005 [Page 19]
INTERNET-DRAFT UMAC October 2004
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 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
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.
Let
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.
Krovetz Expires April 2005 [Page 20]
INTERNET-DRAFT UMAC October 2004
References
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.
[3] L. Carter and M. Wegman, "Universal classes of hash functions",
Journal of Computer and System Sciences, 18 (1979), pp.
143-154.
[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
USA
EMail: jrblack@cs.colorado.edu
Shai Halevi
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights NY 10598
USA
EMail: shaih@alum.mit.edu
Krovetz Expires April 2005 [Page 21]
INTERNET-DRAFT UMAC October 2004
Alejandro Hevia
Department of Computer Science & Engineering
University of California at San Diego
La Jolla CA 92093
USA
EMail: ahevia@cs.ucsd.edu
Hugo Krawczyk
Department of Electrical Engineering
Technion
Haifa 32000
ISRAEL
EMail: hugo@ee.technion.ac.il
Ted Krovetz
Department of Computer Science
California State University
Sacramento CA 95819
USA
EMail: tdk@acm.org
Phillip Rogaway
Department of Computer Science
University of California
Davis CA 95616
USA
and
Department of Computer Science
Faculty of Science
Chiang Mai University
Chiang Mai 50200
THAILAND
EMail: rogaway@cs.ucdavis.edu
Full Copyright Statement
Copyright (C) The Internet Society (2004). 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 AND THE INTERNET
Krovetz Expires April 2005 [Page 22]
INTERNET-DRAFT UMAC October 2004
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 Expires April 2005 [Page 23]
