Request for Comments: 4418 CSU Sacramento
Category: Informational March 2006
UMAC: Message Authentication Code using Universal Hashing
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2006).
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" component is a block
cipher used to generate the pseudorandom pads and internal key
material.
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 .......................6
2.4. Mathematical Operations on Strings .........................6
2.5. ENDIAN-SWAP: Adjusting Endian Orientation ..................6
2.5.1. ENDIAN-SWAP Algorithm ...............................6
3. Key- and Pad-Derivation Functions ...............................7
3.1. Block Cipher Choice ........................................7
3.2. KDF: Key-Derivation Function ...............................8
3.2.1. KDF Algorithm .......................................8
3.3. PDF: Pad-Derivation Function ...............................8
3.3.1. PDF Algorithm .......................................9
4. UMAC Tag Generation ............................................10
4.1. UMAC Algorithm ............................................10
4.2. UMAC-32, UMAC-64, UMAC-96, and UMAC-128 ...................10
5. UHASH: Universal Hash Function .................................10
5.1. UHASH Algorithm ...........................................11
5.2. L1-HASH: First-Layer Hash .................................12
5.2.1. L1-HASH Algorithm ..................................12
5.2.2. NH Algorithm .......................................13
5.3. L2-HASH: Second-Layer Hash ................................14
5.3.1. L2-HASH Algorithm ..................................14
5.3.2. POLY Algorithm .....................................15
5.4. L3-HASH: Third-Layer Hash .................................16
5.4.1. L3-HASH Algorithm ..................................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. Replay Attacks ............................................20
6.5. Tag-Prefix Verification ...................................21
6.6. Side-Channel Attacks ......................................21
7. Acknowledgements ...............................................21
Appendix. Test Vectors ............................................22
References ........................................................24
Normative References ...........................................24
Informative References .........................................24
1. Introduction
UMAC is a message authentication code (MAC) algorithm designed for
high performance. It is backed by a rigorous formal analysis, and
there are no intellectual property claims made by any of the authors
to any ideas used in its design.
UMAC is a MAC in the style of Wegman and Carter [4, 7]. A fast
"universal" hash function is used to hash an input message M into a
short string. This short string is then masked by xor’ing with a
pseudorandom pad, resulting in the UMAC 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) xor 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 UMAC key, a
different nonce is used with each message.
UMAC uses a keyed function, called UHASH (also specified in this
document), as the keyed hash function H and uses a pseudorandom
function F whose default implementation uses the Advanced Encryption
Standard (AES) algorithm. UMAC is designed to produce 32-, 64-, 96-,
or 128-bit tags, depending on the desired security level. The theory
of Wegman-Carter MACs and the analysis of UMAC show that if one
"instantiates" UMAC with truly random keys and pads then the
probability that an attacker (even a computationally unbounded one)
produces a correct tag for any message of its choosing is no more
than 1/2^30, 1/2^60, 1/2^90, or 1/2^120 if the tags output by UMAC
are of length 32, 64, 96, 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 at most N/2^30, N/2^60, N/2^90, or N/2^120. In a real
implementation of UMAC, using AES to produce keys and pads, the
forgery probabilities listed above 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 UMAC security is in
[3, 6].
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 one-and-a-half and twice as long,
respectively.
Optimized source code, performance data, errata, 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 uppercase
letter, whereas numeric variables are denoted in all lowercase. The
algorithms of UMAC are denoted in all uppercase letters. Simple
functions, like those for string-length and string-xor, are written
in all lowercase.
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 that 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 that is the bitwise exclusive-or of S
and T. Strings S and T always have the same
length.
S and T: The string that 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.
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).
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 that are performed efficiently by modern computers.
2.5. ENDIAN-SWAP: Adjusting Endian Orientation
Message data is read little-endian to speed tag generation on
little-endian computers.
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
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 uses 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 bytes).
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 to 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.
3.2.1. KDF Algorithm
Input:
K, string of length KEYLEN bytes.
index, a non-negative integer less than 2^64.
numbytes, a non-negative integer less than 2^64.
Output:
Y, string of length numbytes bytes.
Compute Y using the following algorithm.
//
// Calculate number of block cipher iterations
//
n = ceil(numbytes / BLOCKLEN)
Y = <empty string>
//
// Build Y using block cipher in a counter mode
//
for i = 1 to n do
T = uint2str(index, BLOCKLEN-8) || uint2str(i, 8)
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
Input:
K, string of length KEYLEN bytes.
Nonce, string of length 1 to BLOCKLEN bytes.
taglen, the integer 4, 8, 12 or 16.
Output:
Y, string of length taglen bytes.
Compute Y using the following algorithm.
//
// Extract and zero low bit(s) of Nonce if needed
//
if (taglen = 4 or taglen = 8)
index = str2uint(Nonce) mod (BLOCKLEN/taglen)
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 (taglen = 4 or taglen = 8)
Y = T[1 + (index*taglen) ... taglen + (index*taglen)]
else
Y = T[1...taglen]
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
Input:
K, string of length KEYLEN bytes.
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.
Output:
Tag, string of length taglen bytes.
Compute Tag using the following algorithm.
HashedMessage = UHASH(K, M, taglen)
Pad = PDF(K, Nonce, taglen)
Tag = Pad xor HashedMessage
Return Tag
4.2. UMAC-32, UMAC-64, UMAC-96, and UMAC-128
The preceding UMAC 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.
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
implementer’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 is presented.
5.1. UHASH Algorithm
Input:
K, string of length KEYLEN bytes.
M, string of length less than 2^67 bits.
taglen, the integer 4, 8, 12 or 16.
Output:
Y, string of length taglen bytes.
Compute Y using the following algorithm.
//
// One internal iteration per 4 bytes of output
//
iters = taglen / 4
//
// Define total key needed for all iterations using KDF.
// L1Key reuses 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 do 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.2. L1-HASH: First-Layer Hash
The first-layer hash breaks the message into 1024-byte chunks and
hashes each with a function called NH. Concatenating the results
forms a string, which is up to 128 times shorter than the original.
5.2.1. L1-HASH Algorithm
Input:
K, string of length 1024 bytes.
M, string of length less than 2^67 bits.
Output:
Y, string of length (8 * ceil(bitlength(M)/8192)) bytes.
Compute Y using the following algorithm.
//
// Break M into 1024 byte chunks (final chunk may be shorter)
//
t = max(ceil(bitlength(M)/8192), 1)
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)
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.2.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.
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.