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