============================================================================
UMAC -- Message Authentication Code using Universal Hashing
Version 0.25 (July 8, 1999) -- DRAFT
Black, Halevi, Hevia, Krawczyk, Krovetz, Rogaway
============================================================================
Contents
1. Introduction
1.1 UMAC overview
2. Notation and Basic Operations
2.1 Strings and Integers
3. Key setup
3.1 External Interface
3.2 Key setup based on a block cipher
3.3 Key setup based on a cryptographic hash function
4. Pseudorandom Function (PRF)
4.1 External Interface
4.2 PRF based on a block cipher
4.3 PRF based on a cryptographic hash function
5. Universal Hash Function
5.1 External Interface
5.2 Hashing based on the NH primitive
5.2.1 Parameters
5.2.2 Mathematical Operations
5.2.3 Endian Re-Orientation
5.2.4 The NH hashing primitive
5.2.5 The NHx hashing primitive
5.2.6 The 2NHx hashing primitive
5.2.7 Universal Hash Function Based on NH
6. Encoding
7. UMAC Tag Computation
8. Acknowledgments
9. References
10. Author Contact Information
Appendices
A. Suggested Application Programming Interface (API)
B. Parameter Specifications
C. Reference Code
D. Test Vectors
============================================================================
1. Introduction
This specification describes how to generate an authentication tag (also
called a "MAC" or "tag") using the UMAC message authentication code.
Typically the authentication tag will be transmitted along with a message
and a nonce to allow the receiver of the message to verify the message's
authenticity. Generation and verification of the authentication tag depends,
in addition to the message and nonce, on a secret key (typically, shared
by sender and receiver).
UMAC is designed to be very fast to compute in software on contemporary
processors. The heart of UMAC is addition and multiplication of 16-bit,
32-bit, or 64-bit numbers. These are operations well-supported by
contemporary machines.
For many applications, sufficient speed is already obtained from an
algorithm such as HMAC-SHA1 [RFC-2104, BCK] or the CBC-MAC of a block
cipher [ANSI-9.9, ISO-9797]. But for the most speed-demanding applications,
UMAC may be a better choice: An optimized implementation of UMAC can
achieve peak performance which is about an order of magnitude faster
than what can be achieved with HMAC or CBC-MAC. Moreover, UMAC offers
a tradeoff between forging probability and speed, by which it is possible
to trade forging probability for speed. Such a tradeoff is not present
in other constructions. Finally, UMAC also enjoys better analytical
security properties than other constructions.
Closely associated to this specification is the paper [BHKKR]. See that
paper for a description of the ideas which underlie this algorithm, for
performance data, and for a proof of the correctness and maximal forging
probability of UMAC.
UMAC is a "parameterized" algorithm. This means that various low-level
choices, like the endian convention and the underlying cryptographic
primitive, have not been fixed. One must choose values for these
parameters before the authentication tag generated by UMAC (for a given
message, key, and nonce) becomes well-defined. The advantage of giving
a parameterized algorithm is that we have not been forced to make "generic"
compromises. Instead, an application that uses UMAC can choose the parameters
which best suit its requirements or implementation environment. Examples of
specific parameter choices are provided in this document for common
environments; in particular, this can help the adoption of the algorithm by
standardized applications and protocols. A concrete specification,
including reference code is provided in [TO-BE-WRITTEN].
The ideas which underlie UMAC go back to Wegman and Carter [WC]. The Sender
and Receiver share a secret key (the MAC key) which determines:
* The key for a "universal hash function". This hash function is
"non-cryptographic", in the sense that it does not need to have any
cryptographic "hardness" property. Rather, it needs to satisfy some
combinatorial property, which can be proven to hold without relying
on unproven hardness assumptions.
* The key for a pseudorandom function. This is where one needs a
cryptographic hardness assumption. The pseudorandom function may be
obtained (for example) from a block cipher or cryptographic hash function.
To authenticate a message m, one first applies the non-cryptographic hash
function, resulting in a string Hm which is typically much shorter than the
original message m. The pseudorandom function is then applied to a string
which includes Hm. The result is the authentication tag. For a general
discussion of the speed and assurance advantages of this approach see, for
example, [BHKKR, HK, R].
One features of UMAC is that tag generation depends on a nonce. The
authentication tag is not only a function of the message, but also of a
nonce which is selected by the sender. It is imperative that the nonce not
be re-used when generating authentication tags of different messages under
the same key. Thus the nonce will normally be implemented by a counter,
though any other way to achieve a non-repeating value is also acceptable.
To authenticate messages over a duplex channel (where two parties send
messages to each others), a different key could be used for each direction.
If the same key is used in both directions, then it is crucial that the
nonces be all distinct. For example, in this case one party can use even
nonces while the other party uses odd ones.
The exact encoding by which the message, nonce, and authentication tag
are combined to form an authenticated message is outside the scope of
this document. Specifying such an encoding is left to individual or
standardized applications.
To the authors' knowledge no ideas utilized in UMAC have been or will be
patented. To the best of the author's knowledge, it should be possible to
use UMAC immediately, without any intellectual property concerns.
Public-domain reference code for UMAC is available from the UMAC homepage:
http://www.cs.ucdavis.edu/~rogaway/umac/
1.1 UMAC overview
As was described above, the two main components of the UMAC construction
are universal hashing and pseudorandom functions. In a nutshell, the
authentication tag is computed from the message and the nonce by setting
Tag = prf( hash(Msg), Nonce )
Two other components are a key-setup procedure, by which an initial
key is stretched to provide enough key material for both the universal
hashing and the pseudorandom function, and an encoding scheme which is
used to "pack together" the hashing result and the nonce before applying
to them the pseudorandom function.
The rest of this document is organized as follows: In Section 2 we
introduce the basic notations used throughout the rest of the document.
In the next four sections we describe the four components of the UMAC
construction: Section 3 describes the key-setup function, Section 4
describes the pseudorandom function, Section 5 describes the universal
hash function, and Section 6 describes the encoding scheme. Finally, in
Section 7 we describe how all these components fit together in the UMAC
construction. In the appendix we suggest a programming interface and
name four sets of UMAC parameters.
============================================================================
2. Notation and Basic Operations
In this specification, we view the messages to be authenticated (as well
as the keys used for authentication) as strings of bytes. We use the
following notation to manipulate these strings.
+ Let "length(S)" be the length of string S in bytes.
+ Let "zeroes(n)" be the string of n zero-bytes.
+ Let "S[a]" be the a-th byte of the string S (indices begin at 1).
+ Let "S[a..b]" be the substring of bytes a through b of S.
+ Let "S[a..]" be the substring of bytes a through length(S) of S.
+ Let "||" be string concatenation.
zero_pad(S,n): appends the minimum number of zero-bytes to the string S
such that the resulting string has a length which is a multiple of
the integer n. Formally, if we let ln = length(S) mod n, then if
ln > 0 then zero_pad(S,n) = S || zeroes(n - ln). If ln == 0 then
zero_pad(S,n) = S.
2.1 Strings and Integers
The construction of UMAC often uses arithmetic operations which are
applied to integers of various bit-lengths. This necessitates encoding
integers as byte-strings and vice-versa. We use the following notations
for this encoding:
str2uint(S): is the non-negative integer whose binary representation
is the string S. Here we use the standard convention that the first
bit in S is the most-significant bit and the last bit in S is the
least-significant bit (ie, big-endian convention).
Formally, if the j-th bit of S is S_j (S = S_1 ... S_t) then
str2uint(S) ::= 2**{t-1} * S_1
+ 2**{t-2} * S_2
...
+ 2 * S_{t-1}
+ S_t
(where 2**x denotes 2 raised to the x'th power)
uint2str(n, i): is the i-byte string S such that str2uint(S) = n.
If no such string exists then uint2str(n,i) is undefined.
str2sint(S): is the integer whose binary representation in two's-complement
is the string S.
Formally, if the j-th bit of S is S_j (S = S_1 ... S_t) then
str2sint(S) ::= - 2**{t-1} * S_1
+ 2**{t-2} * S_2
...
+ 2 * S_{t-1}
+ S_t
sint2str(n,i): is the i-byte string S such that str2sint(S) = n.
If no such string exists then sint2str(n,i) is undefined.
============================================================================
3. Key setup
A mechanism is required to stretch the user-supplied MAC key into the
keys used internally. This is done with a "key setup" function. It
is expected that the key setup be defined using some underlying block
cipher, BLOCK_CIPHER, or some cryptographic hash function, HASH_FN.
Example block ciphers are DES, RC6 and MARS. Example hash functions
are MD5, SHA-1, and RIPEMD-160. Although not specified here, other
key setup functions are possible (e.g. stream cipher).
3.1 External Interface
The interface for any key setup function used in this MAC is
KEY_SETUP
---------
EXPORTS: - SETUP_KEY_LENGTH ::= length of key in bytes (before expansion)
- KEY_SETUP ::= name of key setup function to use
INPUT: - K, string of length SETUP_KEY_LENGTH
- index, a non-negative integer < 2**31
- len, positive integer < 2**31
OUTPUT: - Y, string of length len bytes
Here K is a user supplied random key, index is a number used to select
one of 2**31 different key setup functions associated with key K, len is the
number of bytes of output required, and SETUP_KEY_LENGTH is a parameter
associated with the underlying key setup function.
Any key setup function which conforms to this external interface can be
used in the MAC. Below we describe two implementations of key setup functions,
one using a block cipher, and the other using a cryptographic hash function.
3.2 Key setup based on a block cipher.
Given a block cipher BLOCK_CIPHER with a block length of BC_BLOCK_LENGTH
bytes and a key length of BC_KEY_LENGTH bytes, we define BC_KEY_SETUP, using
the cipher in a feedback mode, as:
BC_KEY_SETUP
------------
EXPORTS: - SETUP_KEY_LENGTH ::= BC_KEY_LENGTH
- KEY_SETUP ::= BC_KEY_SETUP
INPUT: - K, string of length BC_KEY_LENGTH
- index, a non-negative integer < 2**31
- len, positive integer < 2**31
OUTPUT: - Y, string of length len
t = ceiling(len/BC_BLOCK_LENGTH)
Y_0 = uint2str(index, BC_BLOCK_LENGTH)
for i = 1 to t do
Y_i = BLOCK_CIPHER(K, Y_(i-1))
Y = (Y_1 || Y_2 || ... || Y_t)[1..len]
3.3 Key setup based on a cryptographic hash function.
Given a cryptographic hash function HASH_FN which produces output
of length HF_OUTPUT_LENGTH bytes, we define HF_KEY_SETUP as:
HF_KEY_SETUP
------------
EXPORTS: - SETUP_KEY_LENGTH ::= HF_OUTPUT_LENGTH
- KEY_SETUP ::= HF_KEY_SETUP
INPUT: - K, string of length HF_OUTPUT_LENGTH
- index, a non-negative integer < 2**31
- len, positive integer < 2**31
OUTPUT: - Y, string of length len
t = ceiling(len/HF_OUTPUT_LENGTH)
Y_0 = uint2str(index, HF_OUTPUT_LENGTH)
for i = 1 to t do
Y_i = HASH_FN(K || Y_(i-1))
Y = (Y_1 || Y_2 || ... || Y_t)[1..len]
============================================================================
4. Pseudorandom Function (PRF)
A method for turning the variable-length output from the hash function
(Section 5) into a fixed length MAC tag is required. A "pseudorandom
function" (PRF) is defined for this purpose. It is expected that the
PRF be defined using some underlying block cipher, BLOCK_CIPHER, or
some cryptographic hash function, HASH_FN.
4.1 External Interface
The interface for any PRF used in this MAC is
PRF
---
EXPORTS: - PRF_KEY_LENGTH ::= Key length associated with PRF in bytes
- PRF_OUTPUT_LENGTH ::= Output length of PRF in bytes
- PRF ::= Name of PRF function to use
INPUT: - K, string of length PRF_KEY_LENGTH
- index, a non-negative integer < 2**31
- M, string of arbitrary length
OUTPUT: - Y, string of length PRF_OUTPUT_LENGTH
Here K is a random key, index is number used to select one of 2**31 different
PRFs associated with key K, M is the input message, and PRF_KEY_LENGTH and
PRF_OUTPUT_LENGTH are parameters associated with the underlying PRF.
Any PRF which conforms to this external interface can be used in the MAC.
We describe two implementations of PRF, one using a block cipher, and the
other using a cryptographic hash function.
4.2 PRF based on a block cipher.
Given a block cipher BLOCK_CIPHER with a block length of BC_BLOCK_LENGTH bytes
and a key length of BC_KEY_LENGTH bytes, we define BC_PRF as:
BC_PRF
------
EXPORTS: - PRF_KEY_LENGTH ::= 3 * BC_KEY_LENGTH
- PRF_OUTPUT_LENGTH ::= BC_BLOCK_LENGTH
- PRF ::= BC_PRF
INPUT: - K, string of length 3 * BC_KEY_LENGTH
- index, a non-negative integer < 2**31
- M, string of arbitrary length
OUTPUT: - Y, string of length BC_BLOCK_LENGTH
// If the length of M is a multiple of BC_BLOCK_LENGTH, we use the
// cipher in CBC mode on M, using a different key for the final block.
// Otherwise, we first pad M and then use the cipher in CBC mode, but
// using yet another key for the last block. Prepend 'index' to
// differentiate input classes.
M = uint2str(index, BC_BLOCK_LENGTH) || M
K1 = K[1 .. BC_KEY_LENGTH]
if (length(M) mod BC_BLOCK_LENGTH != 0) then
M = M || uint2str(128,1)
M = zero_pad(M, BC_BLOCK_LENGTH)
K2 = K[BC_KEY_LENGTH + 1 .. 2 * BC_KEY_LENGTH]
else
K2 = K[2 * BC_KEY_LENGTH + 1 .. 3 * BC_KEY_LENGTH]
t = length(M) / BC_BLOCK_LENGTH
Let M_1, M_2, .., M_t be strings of length BC_BLOCK_LENGTH such
that M_1 || M_2 || .. || M_t = M.
Chain = zeroes(BC_BLOCK_LENGTH)
for i = 1 to (t - 1) do
Chain = BLOCK_CIPHER(K1, Chain XOR M_i)
Y = BLOCK_CIPHER(K2, Chain XOR M_t)
4.3 PRF based on a cryptographic hash function.
Given a cryptographic hash function HASH_FN which produces output of
length HF_OUTPUT_LENGTH bytes and has a block length of HF_BLOCK_LENGTH,
we define HF_PRF as follows.
Notice that HF_PRF is based on the HMAC construction of [RFC-2104, BCK].
HF_PRF
------
EXPORTS: - PRF_KEY_LENGTH ::= HF_BLOCK_LENGTH
- PRF_OUTPUT_LENGTH ::= HF_OUTPUT_LENGTH
- PRF ::= HF_PRF
INPUT: - K, string of length HF_BLOCK_LENGTH
- index, a non-negative integer < 2**31
- M, string of arbitrary length
OUTPUT: - Y, string of length HF_OUTPUT_LENGTH
K1 = K XOR 0x363636...
K2 = K XOR 0x5c5c5c...
Y = HASH_FN( K1 || HASH_FN(K2 || uint2str(index, HF_BLOCK_LENGTH) || M) )
============================================================================
5. Universal Hash Function
The MAC uses a keyed universal hash function, to hash and shorten the
length of the data acted on by the PRF.
5.1 External Interface
The interface for any hash function used in this MAC is
UHASH
-----
EXPORTS: - UHASH_KEY_LENGTH ::= length of universal hashing key in bytes
- UHASH ::= name of universal hash function to use
INPUT: - Hk, string of length HASH_KEY_LENGTH
- M, string of arbitrary length
OUTPUT: - Hm, string of variable length related to length(M)
Here Hk is a random key, M is the message being hashed, and HASH_KEY_LENGTH
is a parameter associated with the underlying hash family. The length of
the output string depends on the length of the input string, and on the
hash function itself. Any universal hash function which conforms to this
external interface can be used in UMAC. We describe one (parameterized)
implementation below, based on the NH hashing primitive.
5.2 Hashing based on the NH primitive
5.2.1 Parameters
Since the universal hash function handles the (potentially long) data
string, this is where the bulk of the authentication work is likely to
occur. It is therefore this function that is most important to optimize
to obtain fast authentication. Accordingly, in this document we identify
several parameters that can be adjusted to increase the performance of UMAC
in different environments. To fully specify the implementation below,
one needs to specify the following parameters:
BYTES_PER_WORD ::= 2 | 4 | 8
// Specifies the size (in bytes) of a "word" in this implementation.
// This need not be equal to the native word size of any specific machine.
L1_RATIO ::= 16 | 32 | 64 | 128 | 256 | 512 | 1024 | ...
L2_RATIO ::= 1 | 16 | 32 | 64 | 128 | 256 | 512 | ...
// Specifies the compression ratio of the NH hashing primitive. The
// implementation can use two levels of compression, and the compression
// ratio in each one can be adjusted separately.
OPERATIONS ::= SIGNED | UNSIGNED
// Are the arithmetic operations applied to signed or unsigned integers
SECURITY ::= 32 | 64 | 96 | ...
// The maximum forging probability that an adversary can achieve is
// approximately 2**{-SECURITY} for each attempt. Halving SECURITY
// causes UMAC to execute nearly twice as fast. The choice of SECURITY
// must be divisible by (8 * BYTES_PER_WORD).
L1_WORD_STRIDE ::= 1 | 2 | 4 | 8 | 16
L2_WORD_STRIDE ::= 1 | 2 | 4 | 8 | 16
// The implementation below takes a vector of integers and multiplies
// its elements in pairs. The WORD_STRIDE parameter determines which
// words are multiplied. For example, with WORD_STRIDE = 1, we multiply
// v[1]*v[2], v[3]*v[4], v[5]*v[6], etc. With WORD_STRIDE = 2, instead,
// we multiply v[1]*v[3], v[2]*v[4], v[5]*v[7], etc.
// See Subsections 5.2.3 and 5.2.4.
ENDIANESS ::= BIG_ENDIAN | LITTLE_ENDIAN
// When a message initially resides in memory, then the loading
// of the message from memory to registers is done differently
// depending on the endian orientation of the host computer. This
// parameter specifies which endian convention should be used
// for the loading of message from memory.
The options selected determine the following derived parameters
OUTPUT_LEN = 2 * BYTES_PER_WORD
// Each application of the NH primitive outputs two words.
L1_PAD_BOUNDARY = 2 * L1_WORD_STRIDE * BYTES_PER_WORD
L2_PAD_BOUNDARY = 2 * L2_WORD_STRIDE * BYTES_PER_WORD
// The input message may have to be padded to some boundary
NUM_HASH_KEYS = SECURITY / (BYTES_PER_WORD * 8)
// To reduce the forging probability of an adversary, we apply the NH
// hashing primitive several times, each time with a different key.
L1_KEY_SHIFT = max(2, L1_WORD_STRIDE) * BYTES_PER_WORD
L2_KEY_SHIFT = max(2, L2_WORD_STRIDE) * BYTES_PER_WORD
// The keys used in the different applications of the "basic NH hashing"
// are not disjoint. Rather, they are shifted versions of each other
// (the Toeplitz construction).
L1_KEY_LENGTH = OUTPUT_LEN * L1_RATIO
// How much key material is needed for one application of the first
// NH compression level.
TOTAL_L1_KEY_LENGTH = L1_KEY_LENGTH + (NUM_HASH_KEYS-1) * L1_KEY_SHIFT
// How much key material is needed for all the applications of the
// first NH compression level.
if (L2_RATIO > 1) then
L2_KEY_LENGTH = OUTPUT_LEN * L2_RATIO
TOTAL_L2_KEY_LENGTH = L2_KEY_LENGTH + (NUM_HASH_KEYS-1) * L2_KEY_SHIFT
else
L2_KEY_LENGTH = 0
TOTAL_L2_KEY_LENGTH = 0
// How much key material needed for one application/all applications
// of the second NH compression level.
HASH_KEY_LENGTH = TOTAL_L1_KEY_LENGTH + TOTAL_L2_KEY_LENGTH
// The key length (in bytes) that is needed for the entire hashing scheme.
BYTES_PER_HASHBLOCK = OUTPUT_LEN * L1_RATIO * L2_RATIO
BITS_PER_HASHBLOCK = 8 * BYTES_PER_HASHBLOCK
// The NH-based hashing scheme hashes the message in "blocks",
// each of length BYTES_PER_HASHBLOCK
MLEN_BYTES = ceiling(log_2(BITS_PER_HASHBLOCK) / 8)
// The number of bytes needed to represent the length (in bits) of a block
5.2.2 Mathematical Operations
The primary operations in the hashing of data are repeated applications
of multiplication and addition. Below, we use `+_n' and `*_n' to denote
the string operations which are equivalent to addition and multiplication
modulo 2**n, respectively. Note that in this specification, *_n is only
applied to operands of length n/2 bits and +_n is only applied to operands
of length n-bits.
Formally, for a number n (divisible by 8), and strings S and T, we denote
if (OPERATIONS == UNSIGNED) then
S *_n T ::= uint2str(str2uint(S) * str2uint(T) mod 2**n, n/8)
else
S *_n T ::= uint2str(str2sint(S) * str2sint(T) mod 2**n, n/8)
+_n is defined as above except all occurrences of '*' are replaced with '+'.
5.2.3 Endian Re-Orientation
The following reverses the endian-orientation of a string. This operation
is needed if a string is assembled by reading a message from memory and
the endian-orientation of the host computer is different from the orientation
specified for the UMAC.
BSWAP
-----
INPUT: - n, positive integer
- X, string of length divisible by n
OUTPUT: - Y, string of length length(X)
M = length(x) / n
Let X_1, X_2, ..., X_m be strings of length n such that
X_1 || X_2 || .. || X_m = X.
for i = 1 to M do
Y_i = X_i[n] || X_i[n-1] || .. || X_i[1]
Y = Y_1 || ... || Y_m
5.2.4 The NH hashing primitive
Given the parameters from above, the NH hashing primitive is defined
as follows:
NH
--
INPUT: - K, string of length at least length(M)
- M, string of length divisible by 2 * BYTES_PER_WORD * stride
- stride, positive integer
OUTPUT: - Y, string of length OUTPUT_LEN
num_words = length(M) / BYTES_PER_WORD
Let M_1, M_2, ..., M_{num_words} be strings of length BYTES_PER_WORD
such that M_1 || M_2 || .. || M_{num_words} = M.
Let K_1, K_2, ..., K_{num_words} be strings of length BYTES_PER_WORD
such that K_1 || K_2 || ... || K_{num_words} is a prefix of K
Compute Y as follows:
acc = zeroes(OUTPUT_LEN)
i = 1
while (i <= num_words) do
for c = i to i+stride-1 do
case (BYTES_PER_WORD) of
8: tmp1 = M_c +_64 K_c
tmp2 = M_(c+stride) +_64 K_(c+stride)
acc = acc +_128 (tmp1 *_128 tmp2)
4: tmp1 = M_c +_32 K_c
tmp2 = M_(c+stride) +_32 K_(c+stride)
acc = acc +_64 (tmp1 *_64 tmp2)
2: tmp1 = M_c +_16 K_c
tmp2 = M_(c+stride) +_16 K_(c+stride)
acc = acc +_32 (tmp1 *_32 tmp2)
i = i + 2 * stride
Y = acc
5.2.5 The NHx hashing primitive
NHx
---
INPUT: - K, string of length HASH_KEY_LENGTH bytes
- M, string of length divisible by L1_PAD_BOUNDARY
and no longer than BYTES_PER_HASHBLOCK bytes
OUTPUT: - Y, string of length OUTPUT_LEN * NUM_HASH_KEYS
Compute Y as follows:
Y =
for c = 1 to NUM_HASH_KEYS do
K' = K[(c-1)*L1_KEY_SHIFT + 1 .. ]
Y = Y || NH(K', M, L1_WORD_STRIDE)
5.2.6 The 2NHx hashing primitive
2NHx
----
INPUT: - K, string of length HASH_KEY_LENGTH bytes
- M, string of length divisible by L1_PAD_BOUNDARY
and no longer than BYTES_PER_HASHBLOCK bytes
OUTPUT: - Y, string of length OUTPUT_LEN * NUM_HASH_KEYS
t = ceiling(length(M) / L1_KEY_LENGTH)
Let M_1, M_2, .., M_t be strings such that M_1 || M_2 || .. || M_t = M
and length(M_j) = L1_KEY_LENGTH for all 1 <= j < t.
Compute Y as follows:
Y =
for a = 1 to NUM_HASH_KEYS do
M' =
K1 = K[(a-1)*L1_KEY_SHIFT + 1 .. ]
K2 = K[(a-1)*L2_KEY_SHIFT + TOTAL_L1_KEY_LENGTH + 1 .. ]
for b = 1 to t do
M' = M' || NH(K1, M_b, L1_WORD_STRIDE)
M' = zero_pad(M', L2_PAD_BOUNDARY)
Y = Y || NH(K2, M', L2_WORD_STRIDE)
5.2.7 Universal Hash Function Based on NH
The top-level hashing scheme consists of breaking the message into
appropriately sized blocks, hashing each block with either NHx or 2NHx,
concatenating the results and encoding the concatenation along with
the original message length modulo the hashing block-length.
Formally, we define:
NH_UHASH
--------
EXPORTS: - UHASH_KEY_LENGTH ::= HASH_KEY_LENGTH // see section 5.2.1
- UHASH ::= NH_UHASH
INPUT: - Hk, string of length HASH_KEY_LENGTH
- M, string of arbitrary length
OUTPUT: - Hm, string of length ceil(length(M) / BYTES_PER_HASHBLOCK) *
OUTPUT_LEN * NUM_HASH_KEYS + MLEN_BYTES
Mlen = uint2str(8 * (length(M) mod BYTES_PER_HASHBLOCK), MLEN_BYTES)
M = zero_pad(M, L1_PAD_BOUNDARY) // Pad to L1_PAD_BOUNDARY multiple
t = ceiling(length(M) / BYTES_PER_HASHBLOCK)
if (ENDIANESS == LITTLE_ENDIAN) then // Re-orient bytes if needed
M = BSWAP(BYTES_PER_WORD, M)
Let M_1, M_2, .., M_t be strings such that M_1 || M_2 || .. || M_t = M
and length(M_j) = BYTES_PER_HASHBLOCK for all 1 <= j < t.
Out = // NH-hash each block M_1, ... , M_t
for i = 1 to t do
if (L2_RATIO > 1)
Out = Out || 2NHx(Hk, M_i)
else
Out = Out || NHx(Hk, M_i)
Hm = Out || Mlen
============================================================================
6. Encoding
The output of the hash function along with the nonce value must be packaged
into an argument to the PRF function, using a reversible encoding.
ENCODE
------
INPUT: - Hm, string of arbitrary length
- Nonce, string of length 8
OUTPUT: - Ehm, string of length n, where length(Hm) + 2 <= n <= length(Hm) + 9
Compute string Ehm as follows:
// eliminate leading zeros
i = 1;
while ((Nonce[i] = zeroes(1)) AND (i < 8)) do
i = i + 1
Nonce = Nonce[i..8]
nonce_len = length(Nonce)
Nonce = Nonce || uint2str(nonce_len, 1)
Ehm = Hm || Nonce.
============================================================================
7. UMAC Tag Computation
The UMAC message authentication scheme uses a key-setup function (as
described in Section 3), a PRF (as described in Section 4), a universal
hash function (as described in Section 5) and an encoding function (as
described in Section 6) to produce a tag. Given all these functions
(with the parameters that they export), UMAC is defined as follows:
Parameter: - MIN_LEN_TO_HASH ::= 1 | 2 | 3 | ...
// MIN_LEN_TO_HASH allows for optimization of the performance of UMAC on
// messages of small length: In some implementations, it may be faster
// to apply the PRF function directly to short messages, rather than
// hashing them first with the UHASH function.
UMAC
----
EXPORTS: - MAC_KEY_LENGTH ::= SETUP_KEY_LENGTH
- TAG_LENGTH ::= PRF_OUTPUT_LENGTH
INPUT: - M, string of arbitrary length
- K, string of length SETUP_KEY_LENGTH
- Nonce, string of length 8 bytes
OUTPUT: - Tag, string of length TAG_LENGTH
PRF_Key = KEY_SETUP(K, 0, PRF_KEY_LENGTH)
Hash_Key = KEY_SETUP(K, 1, UHASH_KEY_LENGTH)
if (length(M) >= MIN_LEN_TO_HASH) then
Hm = UHASH(Hash_Key, M)
Ehm = ENCODE(Hm, Nonce)
Tag = PRF(PRF_Key, 0, Ehm)
else
Tag = PRF(PRF_Key, 1, M)
============================================================================
8. Acknowledgments
Phillip Rogaway, John Black, and Ted Krovetz were supported in this work
under Rogaway'S NSF CAREER Award CCR-962540, and under MICRO grants 97-150
and 98-129, funded by RSA Data Security, Inc., and ORINCON Corporation.
Much of Rogaway'S work was carried out while on sabbatical at
Chiang Mai University, hosted by the Computer Service Center, under
Prof. Krisorn Jittorntrum and Prof. Darunee Smawatakul.
============================================================================
9. References
[ANSI-9.9] ANSI X9.9, American National Standard for Financial Institution
Message Authentication (Wholesale),'' American Bankers Association,
1981. Revised 1986.
[BCK] M. Bellare, R. Canetti, and H. Krawczyk, "Keyed Hash Functions and
Message Authentication", Advances in Cryptology - CRYPTO'96,
LNCS vol. 1109, pp. 1-15. Full version available from
http://www.research.ibm.com/security/keyed-md5.html/
[BHKKR] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway,
"UMAC: Fast and Provably Secure Message Authentication".
Manuscript associated to this spec, 1998.
[FIPS-180] FIPS PUB 180-1, "Secure Hash Standard," April 1995.
[HK] S. Halevi and H. Krawczyk, "MMH: Software Message Authentication
in the Gbit/second Rates", Fast Software Encryption, LNCS Vol.1267,
Springer-Verlag, pp. 172-189, 1997.
[ISO-9797] ISO/IEC 9797, "Information technology - Security techniques -
Data integrity mechanism using a cryptographic check function
employing a block cipher algorithm", International Organization for
Standardization, 1994 (second edition).
[RFC-2104] H. Krawczyk, M. Bellare, and R. Canetti, "HMAC: Keyed-Hashing for
Message Authentication", RFC-2104, February 1997.
[RFC-1321] Ronald Rivest, "The MD5 Message-Digest Algorithm",
RFC-1321, April 1992.
[R] P. Rogaway, "Bucket Hashing and it Application
to Fast Message Authentication." Advances in Cryptology -
CRYPTO '95, LNCS vol. 963, pp. 29-42, 1995. Full version
availble from http://www.cs.ucdavis.edu/~rogaway/
[VW] P. van Oorschot and M. Wiener, "Parallel Collision
Search with Applications to Hash Functions and Discrete
Logarithms", Proceedings of the 2nd ACM Conf. Computer and
Communications Security, Fairfax, VA, November 1994.
[WC] 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.
============================================================================
10. Author Contact Information
Authors' Addresses
John Black
Department of Computer Science
University of California
Davis CA 95616
USA
EMail: blackj@cs.ucdavis.edu
Shai Halevi
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights NY 10598
USA
EMail: shaih@watson.ibm.com
Alejandro Hevia
Department of Computer Science (DCC)
University of Chile
Av. Blanco Encalada 2120, Casilla 2777, Santiago
CHILE
EMail: ahevia@dcc.uchile.cl
Hugo Krawczyk
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights NY 10598
USA
EMail: hugo@watson.ibm.com
Ted Krovetz
Department of Computer Science
University of California
Davis CA 95616
USA
EMail: tdk@acm.org
Phillip Rogaway
Department of Computer Science
University of California
Davis CA 95616
USA
EMail: rogaway@cs.ucdavis.edu
============================================================================
A. Suggested Application Programming Interface (API)
/* umac.h */
typedef struct UMAC_CTX *umac_ctx_t;
umac_ctx_t umac_alloc(char key[]); /* Dynamically allocate MAC_CTX struct */
/* initialize variables and generate */
/* subkeys for default parameters. */
int umac_free(umac_ctx_t ctx); /* Deallocate the context structure. */
int umac_set_params(umac_ctx_t ctx, /* After default initialization, */
void *params); /* optionally set parameters to */
/* different values and reset for */
/* new message. */
int umac_reset(umac_ctx_t ctx); /* Reset for new message without */
/* calculating a tag. */
int umac_update(umac_ctx_t ctx, /* Incorporate len bytes pointed to by */
char *input, /* input into context ctx. */
long len);
int umac_final(umac_ctx_t ctx, /* Incorporate nonce value and return */
char tag[], /* tag. Reset ctx for next message. */
char nonce[8]);
int umac(umac_ctx_t ctx, /* All-in-one (non-incremental) */
char *input, /* implementation of the functions */
long len, /* umac_update() and umac_final(). */
char tag[],
char nonce[8]);
Each routine returns zero if unsuccessful.
============================================================================
B. Parameter Specifications
Although many combinations of parameter settings are possible, we have
selected the following four sets as candidate standards. The UMAC-MMX
variants offer maximum performance but only on processors equipped
with SIMD vector units (e.g. Intel MMX and Motorola AltiVec). The UMAC-STD
variants offer good performance on a wide variety of non-vector
processors.
UMAC-MMX-15
KEY_SETUP ::= BC_KEY_SETUP
PRF ::= BC_PRF
BLOCK_CIPHER ::= RC6-32/20/16
UHASH ::= NH_UHASH
BYTES_PER_WORD ::= 2
L1_RATIO ::= 1024
L2_RATIO ::= 1
OPERATIONS ::= SIGNED
SECURITY ::= 16
L1_WORD_STRIDE ::= 8
L2_WORD_STRIDE ::= n/a
ENDIANESS ::= LITTLE_ENDIAN
MIN_LEN_TO_HASH ::= 33
UMAC-MMX-30
Same as UMAC-MMX-15 except
SECURITY ::= 32
UMAC-MMX-60
Same as UMAC-MMX-15 except
SECURITY ::= 64
UMAC-STD-30
KEY_SETUP ::= HF_KEY_SETUP
PRF ::= HF_PRF
HASH_FN ::= SHA-1
UHASH ::= NH_UHASH
BYTES_PER_WORD ::= 4
L1_RATIO ::= 32
L2_RATIO ::= 16
OPERATIONS ::= SIGNED
SECURITY ::= 32
L1_WORD_STRIDE ::= 1
L2_WORD_STRIDE ::= 1
ENDIANESS ::= LITTLE_ENDIAN
MIN_LEN_TO_HASH ::= 56
UMAC-STD-60
Same as UMAC-STD-30 except
SECURITY ::= 64
============================================================================
C. Reference Code
See the UMAC World Wide Web homepage for implementations of the
versions of UMAC specified in Appendix B.
http://www.cs.ucdavis.edu/~rogaway/umac/
============================================================================
D. Test Vectors
To be written once implementation teams have interoperable versions,
and we have convinced ourselves that the implementations match the spec.