IPSec Working Group T. Krovetz, Intel INTERNET-DRAFT J. Black, UNR Expires April 2001 S. Halevi, IBM A. Hevia, U.C. San Diego H. Krawczyk, Technion P. Rogaway, U.C. Davis October 2000 UMAC: Message Authentication Code using Universal Hashing 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 Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This specification describes how to generate an authentication tag (also called a "MAC") using the UMAC message authentication code. UMAC is designed to be very fast to compute, in software, on contemporary processors. Measured speeds are as low as 1.0 cycles per byte. The heart of UMAC is a universal hash function, UHASH, which relies on addition and multiplication of 16-bit, 32-bit, or 64-bit numbers, operations well-supported by contemporary machines. To generate the authentication tag on a given message, UHASH 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 "cryptographic" use is a block cipher, AES, to generate the pseudorandom pads and internal key material. Krovetz et al. Expires April 2001 [Page 0] INTERNET-DRAFT UMAC October 2000 Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1 Organization . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Named parameter sets: UMAC16 and UMAC32 . . . . . . . . . . . . . 5 2.1 Named parameters . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Alternative instantiations . . . . . . . . . . . . . . . . . 6 2.3 Naming convention . . . . . . . . . . . . . . . . . . . . . 7 3 Notation and basic operations . . . . . . . . . . . . . . . . . . 7 3.1 Operations on strings . . . . . . . . . . . . . . . . . . . 8 3.2 Operations on integers . . . . . . . . . . . . . . . . . . . 10 3.3 String-Integer conversion operations . . . . . . . . . . . . 10 3.4 Mathematical operations on strings . . . . . . . . . . . . . 11 4 Key and pad derivation functions . . . . . . . . . . . . . . . . 12 4.1 KDF: Key derivation function . . . . . . . . . . . . . . . . 12 4.2 PDF: Pad-derivation function . . . . . . . . . . . . . . . . 13 5 UHASH-32: Universal hash function for a 32-bit word size . . . . 15 5.1 NH-32: NH hashing with a 32-bit word size . . . . . . . . . 16 5.2 L1-HASH-32: First-layer hash . . . . . . . . . . . . . . . . 17 5.3 POLY: Polynomial hash . . . . . . . . . . . . . . . . . . . 19 5.4 L2-HASH-32: Second-layer hash . . . . . . . . . . . . . . . 20 5.5 L3-HASH-32: Third-layer hash . . . . . . . . . . . . . . . . 22 5.6 UHASH-32: Three-layer universal hash . . . . . . . . . . . . 23 6 UHASH-16: Universal hash function for a 16-bit word size . . . . 24 6.1 NH-16: NH hashing with a 16-bit word size . . . . . . . . . 24 6.2 L1-HASH-16: First-layer hash . . . . . . . . . . . . . . . . 25 6.3 L2-HASH-16: Second-layer hash . . . . . . . . . . . . . . . 27 6.4 L3-HASH-16: Third-layer hash . . . . . . . . . . . . . . . . 28 6.5 UHASH-16: Three-layer universal hash . . . . . . . . . . . . 29 7 UMAC tag generation . . . . . . . . . . . . . . . . . . . . . . . 30 7.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . 30 7.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 30 8 Security considerations . . . . . . . . . . . . . . . . . . . . . 31 8.1 Resistance to cryptanalysis . . . . . . . . . . . . . . . . 31 8.2 Tag lengths and forging probability . . . . . . . . . . . . 31 8.3 Selective-assurance authentication . . . . . . . . . . . . . 33 8.4 Nonce considerations . . . . . . . . . . . . . . . . . . . . 34 8.5 Guarding against replay attacks . . . . . . . . . . . . . . 35 9 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 36 10 References . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 11 Author contact information . . . . . . . . . . . . . . . . . . . 37 A Suggested application programming interface (API) . . . . . . . . 38 B Reference code and test vectors . . . . . . . . . . . . . . . . . 39 Krovetz et al. Expires April 2001 [Page 1] INTERNET-DRAFT UMAC October 2000 1 Introduction This specification describes how to generate an authentication tag (also called a "MAC") 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 on the message, the nonce, and 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 a universal hash function, UHASH, which relies on addition and multiplication of 16-bit, 32-bit, and 64-bit numbers. These operations are supported well by contemporary machines. For many applications, especially ones with short-lived authentication needs, sufficient speed is already obtained by algorithms such as HMAC-SHA1 [2, 9] or the CBC-MAC of a block cipher [1, 8]. 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 (it is possible to trade forging probability for speed). UMAC has been designed so that computing the prefix of a tag can be done faster than computing the entire tag. This feature allows for a receiver to verify the authenticity of a message to various levels of assurance depending on its needs and resources. Finally, UMAC enjoys better analytical security properties than many other constructions. Closely associated to this specification are the papers [3, 4, 10, 11]. See those papers for descriptions of the ideas which underlie this algorithm, for performance data, and for proofs of the correctness and maximal forging probability of UMAC. The UMAC algorithms described in the papers [3, 4] are "parameterized". 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 fully-defined. In this document we provide two collections of parameter settings, and have named the sets UMAC16 and UMAC32. The parameter sets have been chosen based on experimentation and provide good performance on a wide variety of processors. UMAC16 is designed to excel on processors which provide small-scale SIMD parallelism of the type found in Intel's MMX and Motorola's AltiVec instruction sets, while UMAC32 is designed to do well on processors Krovetz et al. Expires April 2001 [Page 2] INTERNET-DRAFT UMAC October 2000 with good 32- and 64- bit support. UMAC32 may take advantage of SIMD parallelism in future processors. UMAC has been designed to allow implementations which accommodate "on-line" authentication. This means that pieces of the message may be presented to UMAC at different times (but in correct order) and an on-line implementation will be able to process the message correctly without the need to buffer more than a few dozen bytes of the message. For simplicity, the algorithms in this specification are presented as if the entire message being authenticated were available at once. The ideas which underlie UMAC go back to Wegman and Carter [12]. 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 concept of a universal hash function (family) is due to [5]. * 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. The concept of a pseudorandom function (family) is due to [6]. To authenticate a message, Msg, one first applies the universal hash function, resulting in a string which is typically much shorter than the original message. The pseudorandom function is applied to a nonce, and the result is used in the manner of a Vernam cipher: the authentication tag is the xor of the output from the hash function and the output from the pseudorandom function. Thus, an authentication tag is generated as AuthTag = f(Nonce) xor h(Msg). Here f is the pseudorandom function shared between the sender and the receiver, and h is a universal hash function shared by the sender and the receiver. In UMAC, a shared key is used to key the pseudorandom function f, and then f is used for both tag generation and internally to generate all of the bits needed by the universal hash function. For a general discussion of the speed and assurance advantages of this approach see, for example, [3, 7]. The universal hash function that we use is called UHASH. It combines Krovetz et al. Expires April 2001 [Page 3] INTERNET-DRAFT UMAC October 2000 several software-optimized algorithms into a multi-layered structure. The algorithm is moderately complex. Some of this complexity comes from extensive speed optimizations. For the pseudorandom function we use the block cipher of the Advanced Encryption Standard (AES). (At the time of this working draft, the AES definition process is still in progress. Here AES refers to the final blok cipher defined by this process.) Any block cipher with the same block-length (128 bits) and key-length (128 bits) could trivially be substituted in place of what we call AES. With slightly more effort one can define UMAC using a pseudorandom function other than a block cipher. One unusual feature of UMAC is that authentication-tag generation depends on a nonce (in addition to depending on the message and key) It is imperative that the nonce not be reused when generating authentication tags under the same key. Thus the nonce will normally be implemented by a counter, though any other way to achieve a non- repeating value (or almost certainly non-repeating value) is acceptable. This document specifies the procedure for generating the authentication tag from the message, key and nonce. The exact way in which the message, nonce and authentication tag are transmitted between sender and receiver is not specified here. It is the responsibility of the particular applications using UMAC to specify how the message, nonce and tag are transmitted. For example, an application may choose to send the three values concatenated by some encoding scheme while others may choose not to transmit the nonce at all if it is known to both parties (e.g., when the nonce is a shared state used to detect replay of messages), or to send only part of the bits of the nonce. Section 8 discusses security considerations that are important for the proper understanding and use of UMAC. To the authors' knowledge no ideas utilized in UMAC have been or will be patented. To the best of the authors' 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/ Other information, like timing data and papers, are distributed from the same URL. Krovetz et al. Expires April 2001 [Page 4] INTERNET-DRAFT UMAC October 2000 1.1 Organization The rest of this document is organized as follows: In Section 2 parameters of the named parameter sets UMAC16 and UMAC32 are described. In Section 3 we introduce the basic notations used throughout the rest of the document. Section 4 describes the methods used for generating the Vernam pad and the pseudorandom strings needed internally for hashing. In Sections 5 and 6 the universal hash function is described. Finally, in Section 7 we describe how all these components fit together in the UMAC construction. Some readers may prefer to read sections 4-7 backwards, in order to get a top-down description. Section 8 describes some security considerations in the use of UMAC. 2 Named parameter sets: UMAC16 and UMAC32 As described in [3, 4], a concrete instantiation of UMAC requires the setting of many parameters. We have chosen two sets of values for all of these parameters which allow for good performance on a wide variety of processors. For maximum performance we offer UMAC16 which is designed to exploit the vector-parallel instructions on the Intel MMX and Motorola AltiVec instruction sets. For good performance on processors which support 32- and 64-bit quantities well, we offer UMAC32. 2.1 Named parameters Throughout the algorithms described in this document, we have integrated most of the parameters required for a concrete UMAC instantiation as unnamed numeric constants. However, we have named six parameters and assign them the following values depending on whether one wishes to use UMAC16 or UMAC32. UMAC16 UMAC32 ------ ------ WORD-LEN 2 4 UMAC-OUTPUT-LEN 8 8 L1-KEY-LEN 1024 1024 UMAC-KEY-LEN 16 16 ENDIAN-FAVORITE LITTLE LITTLE L1-OPERATIONS-SIGN SIGNED UNSIGNED Here we give a brief explanation of the role each named parameter plays. Krovetz et al. Expires April 2001 [Page 5] INTERNET-DRAFT UMAC October 2000 WORD-LEN: Specifies the size in bytes of a "word". UMAC will be significantly faster in execution if the executing machine supports well certain operations on datatypes of this size. Note that WORD-LEN is not necessarily the native wordsize of the target machine (and on some machines a smaller value turns out to be preferable). UMAC-OUTPUT-LEN: Specifies the length of the authentication tag generated by UMAC, in bytes. L1-KEY-LEN: Specifies the "block length," in bytes, on which the hash-function initially operates. This much storage (and then some) will be needed in the run-time environment for UMAC's internal keys. UMAC-KEY-LEN: Specifies the length in bytes of the user-sup- plied UMAC key. ENDIAN-FAVORITE: Specifies which endian-orientation will be fol- lowed in the reading of data to be hashed. This need not be equal to the native endianess of any specific machine running UMAC. L1-OPERATIONS-SIGN: Specifies whether the strings manipulated in the hash-function are to be initially consid- ered as signed or unsigned integers. 2.2 Alternative instantiations Although this document only specifies two named parameter sets, the named parameters could be altered to suit specific authentication needs which are not adequately served by either UMAC16 or UMAC32. Below, we list alternatives that are supported by this specification for each of the named parameters. WORD-LEN ::= 2 | 4 UMAC-OUTPUT-LEN ::= 1 | 2 | ... | 31 | 32 L1-KEY-LEN ::= 32 | 64 | 128 | 256 | ... | 2^28 UMAC-KEY-LEN ::= 16 | 32 ENDIAN-FAVORITE ::= BIG | LITTLE L1-OPERATIONS-SIGN ::= SIGNED | UNSIGNED Roughly speaking, doubling UMAC-OUTPUT-LEN approximately doubles execution time and squares (ie. decreases) the probability of MAC Krovetz et al. Expires April 2001 [Page 6] INTERNET-DRAFT UMAC October 2000 forgery. Setting ENDIAN-FAVORITE to BIG causes UMAC to perform better on big-endian processors rather than little-endian processors. Setting L1-OPERATIONS-SIGN to UNSIGNED slightly increases UMAC security at the expense of complicating implementations on systems which do not support unsigned integers well. This effectively disallows the use of Intel's MMX instructions which only support signed integers. Finally, increasing L1-KEY-LEN tends to speed tag generation on large messages, but requires more memory for processing and could potentially slow the processor by overflowing its cache. 2.3 Naming convention A concise shorthand may be used to specify an instance of UMAC. The word "UMAC" followed by up to six parameters specifies unambiguously an instance of UMAC. If only a prefix of the six parameters are written, it is implicitly specified that those missing parameters take on default values listed below. The format of the shorthand is "UMAC-w/l/n/k/s/e", and the meaning of the letters (and their defaults) is as follows: w = WORD-LEN (4) l = UMAC-OUTPUT-LEN (8) n = L1-KEY-LEN (1024) k = UMAC-KEY-LEN (16) s = L1-OPERATIONS-SIGN (UNSIGNED) e = ENDIAN-FAVORITE (LITTLE) Some examples UMAC-4/8/1024/16/UNSIGNED/LITTLE (Same as named set "UMAC32" ) UMAC-2/8/1024/16/SIGNED/LITTLE (Same as named set "UMAC16" ) UMAC-4/12 ("UMAC32" with 96-bit output) UMAC-2/8/4096 ("UMAC16" with 4K L1-key and) (unsigned L1-OPERATIONS ) 3 Notation and basic operations The specification of UMAC involves the manipulation of both strings and numbers. String variables are denoted with initial capitals (upper-case), whereas numeric variables are denoted in all lower- case. Global parameters are denoted in all capital letters. Simple functions, like those for string-length and string-xor, are written with all lower-case, while the algorithms of UMAC are named in all upper-case. Whenever a variable is followed by an underscore ("_"), the Krovetz et al. Expires April 2001 [Page 7] INTERNET-DRAFT UMAC October 2000 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. We now define some basic operations for manipulating strings and numbers, and for converting between the two. 3.1 Operations on strings In this specification, we view the messages to be hashed (as well as the keys used for hashing) as strings of bytes. A "byte" is an 8-bit string. The algorithms have been designed so that they are easily extendable to allow arbitrary bit-strings, if necessary. We use the following notation to manipulate these strings. length(S): The length of string S in bytes. 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 must have the same length. S and T: The string which is the bitwise conjunction of S and T. Strings S and T must 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-bytes to the nearest non-zero multiple of n bytes. Formally, zeropad(S,n) = S || zeroes(i), where i is the smallest nonnegative integer such that S || zeroes(i) is non-empty and n divides length(S)+i. 3.1.1 ENDIAN-SWAP: Adjusting endian orientation This routine is used to make the data input to UMAC conform to the ENDIAN-FAVORITE global parameter. Krovetz et al. Expires April 2001 [Page 8] INTERNET-DRAFT UMAC October 2000 3.1.1.1 Discussion The most time consuming portion of many UMAC computations involves the reading of key and message data from memory. Because big- and little-endian computers will read these bytes differently, specifying a particular endian-orientation for UMAC could have significant performance ramifications. If necessary, the key-bytes can be preprocessed once during key setup to eliminate the need for their reorientation during performance-critical tag generation. But, message data presumably cannot be preprocessed. Any reorientation needed for each message must be done during tag generation, introducing a significant penalty to computers whose native endian- orientation is opposite to that specified for UMAC. Therefore, UMAC defines a parameter, ENDIAN-FAVORITE, which allows UMAC to be specified to favor big- or little-endian memory conventions. If the parameter is set to favor little-endian computers, then we specify the reversal of the bytes of every word in the input message using the following support function. By reversing the data in the specification, an implementation on a little-endian machine would in fact do nothing but read the input data using native-endian word loads. The loads would automatically reverse the bytes within each word, fulfilling the requirements of the specification. Any other endian reorientation needed to comply with the specification requires an insignificant amount of time during each tag calculation. 3.1.1.2 Interface Function Name: ENDIAN-SWAP Input: S, string with length divisible by WORD-LEN bytes. Output: T, string S with each word endian-reversed. 3.1.1.3 Algorithm Compute T using the following algorithm. // // Break S into word-size chunks // n = length(S) / WORD-LEN Let S_1, S_2, ..., S_n be strings of length WORD-LEN bytes so that S_1 || S_2 || .. || S_n = S. // // Byte-reverse each chunk, and build-up T Krovetz et al. Expires April 2001 [Page 9] INTERNET-DRAFT UMAC October 2000 // T = for i = 1 to n do Let W_1, W_2, ..., W_{WORD-LEN} be bytes so that W_1 || W_2 || ... || W_{WORD-LEN} = S_i SReversed_i = W_{WORD-LEN} || W_{WORD-LEN - 1} || ... || W_1 T = T || SReversed_i Return T 3.2 Operations on integers In this specification, we generally use standard notation for 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 integer i-th power. lg a: The base-2 logarithm of integer a. floor(x): The largest integer less than or equal to x. 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: +-----+--------------------+---------------------------------------+ | x | prime(x) [Decimal] | prime(x) [Hexadecimal] | +-----+--------------------+---------------------------------------+ | 19 | 2^19 - 1 | 0x0007FFFF | | 32 | 2^32 - 5 | 0xFFFFFFFB | | 36 | 2^36 - 5 | 0x0000000F FFFFFFFB | | 64 | 2^64 - 59 | 0xFFFFFFFF FFFFFFC5 | | 128 | 2^128 - 159 | 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFF61 | +-----+--------------------+---------------------------------------+ 3.3 String-Integer conversion operations We convert between strings and integers using the following functions. Each function treats initial bits as more significant than later ones. Krovetz et al. Expires April 2001 [Page 10] INTERNET-DRAFT UMAC October 2000 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). Here n must be between 1 and the bit- length of S. 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. If no such string exists then uint2str(n,i) is unde- fined. str2sint(S): The integer whose binary representation in two's- complement is the string S. More formally, if S is t bits long then str2sint(S) = -2^{t-1} * bit(S,1) + 2^{t-2} * bit(S,2) + ... + 2^{1} * bit(S,t-1) + bit(S,t). sint2str(n,i): The i-byte string S such that str2sint(S) = n. If no such string exists then sint2str(n,i) is unde- fined. 3.4 Mathematical operations on strings One of the primary operations in the universal hashing part of UMAC is repeated application of addition and multiplication on strings. We use "+_n" and "*_n" to denote the string operations which are equivalent to addition and multiplication modulo 2^n, respectively. These operations correspond exactly with the addition and multiplication operations which are performed efficiently on registers by modern computers. So, when n is 16, 32 or 64, these operations can be preformed by computers very quickly. There are two interpretations of the operators depending on whether the strings are interpreted as signed or unsigned integers. The global parameter L1-OPERATIONS-SIGN determines which interpretation is made. If strings S and T are interpreted as signed integers (that is, L1-OPERATIONS-SIGN == SIGNED) then "S *_n T" as uint2str(str2sint(S) * str2sint(T) mod 2^n, n/8), and "S +_n T" as uint2str(str2sint(S) + str2sint(T) mod 2^n, n/8). Krovetz et al. Expires April 2001 [Page 11] INTERNET-DRAFT UMAC October 2000 If strings S and T are interpreted as unsigned integers (that is, L1-OPERATIONS-SIGN == UNSIGNED) then we define "S *_n T" as uint2str(str2uint(S) * str2uint(T) mod 2^n, n/8), and "S +_n T" as uint2str(str2uint(S) + str2uint(T) mod 2^n, n/8). In any case, the number n must be divisible by 8. In this document we use S *_16 T, S *_32 T, S *_64 T, S +_32 T and S +_64 T, corresponding to multiplication of 2, 4 and 8 byte numbers, and the addition of 4 and 8 byte numbers. 4 Key and pad derivation functions UMAC, as described in this document, requires either a 16- or 32-byte key which is used with a key-derivation function (KDF) to produce pseudorandom bits needed within the universal hash function. 4.1 KDF: Key derivation function Stretching the user-supplied key into pseudorandom bits used internally by UMAC is done with a key-derivation function (KDF). In this section we define a KDF which is efficiently instantiated with a block cipher. The Advanced Encryption Standard (AES) is used in output-feedback mode to produce the required bits. If UMAC-KEY-LEN is 16, then the 128-bit key/128-bit block-length variant of AES is used, and if UMAC-KEY-LEN is 32, then the 256-bit key/128-bit block- length variant is used. The KDF requires an "index" parameter. Using the same key, but different indices, generates different pseudorandom outputs. 4.1.1 Interface Function Name: KDF Input: K, string of length UMAC-KEY-LEN bytes // key to AES index, a non-negative integer less than 256. numbytes, a positive integer. Output: Y, string of length numbytes bytes. Krovetz et al. Expires April 2001 [Page 12] INTERNET-DRAFT UMAC October 2000 4.1.2 Algorithm Compute Y using the following algorithm. // // Calculate number of AES iterations, set indexed starting point // n = ceil(numbytes / 16) T = zeroes(15) || uint2str(index, 1) Y = // // Build Y using AES in a feedback mode // for i = 1 to n do T = AES(K, T) Y = Y || T Y = Y[1..numbytes] Return Y 4.2 PDF: Pad-derivation function The Wegman-Carter MAC scheme used in UMAC requires the exclusive-or of a pseudorandom string with the output from the universal hash function. The pseudorandom string is obtained by applying a pad- derivation function (PDF) to a nonce which, for security reasons, must change with each authentication-tag computation. Nonces may be any number of bytes from 1 to 16, but all nonces in a single authentication session must be of equal length. In this section we define a PDF which is efficiently instantiated with a block cipher. Again we use AES with either 16- or 32-bytes keys depending on the value of UMAC-KEY-LEN. 4.2.1 Discussion The PDF output is exclusive-or'd with the result of the universal hash function. AES, however, may provide more or fewer bits per invocation than are needed for this purpose. For example, UMAC- OUTPUT-LEN is normally 8 bytes and AES produces an output of 16 bytes. It would save processing time if half of the AES output bits could be used to generate one tag, and then the second half of the same AES output could be used for the tag of the next message. For this reason, we include an optimization which allows the use of different substrings of the same AES output. This optimization is Krovetz et al. Expires April 2001 [Page 13] INTERNET-DRAFT UMAC October 2000 effective only when nonces are sequential. We do so by using the low bits of the nonce as an index into the AES output, which is generated using the higher bits of the nonce which are not used for indexing. This speeds message authentication by reducing the average time spent by AES for each authentication. Note that if a counter-variable is used to exploit this optimization, and the variable is stored in memory, then the variable must be treated as big-endian. If UMAC- OUTPUT-LEN is larger than 16, then two AES invocations are required to produce a sufficient number of bits. 4.2.2 Interface Function Name: PDF Input: K, string of length UMAC-KEY-LEN bytes // key for AES Nonce, string of length 1 to 16 bytes. Output: Y, string of length UMAC-OUTPUT-LEN bytes. 4.2.3 Algorithm Compute Y using the following algorithm. // // Make Nonce 16 bytes by prepending zeroes // Nonce = Nonce || zeroes(16 - length(Nonce)) // // If one AES invocation is enough for more than one // PDF invocation. // if (UMAC-OUTPUT-LEN <= 8) then // // Compute number of index bits needed // i = floor(16 / UMAC-OUTPUT-LEN) numlowbits = floor(lg(i)) // // Extract index bits and zero low bits of Nonce // nlowbitsnum = str2uint(Nonce) mod 2^numlowbits Nonce = Nonce xor uint2str(nlowbitsnum, 16) Krovetz et al. Expires April 2001 [Page 14] INTERNET-DRAFT UMAC October 2000 // // Generate subkey, AES and extract indexed substring // K' = KDF(K, 128, UMAC-KEY-LEN) T = AES(K', Nonce) Y = T[ nlowbitsnum * UMAC-OUTPUT-LEN + 1 .. (nlowbitsnum + 1) * UMAC-OUTPUT-LEN] else // // Repeated AES calls to build length // K_1 = KDF(K, 128, UMAC-KEY-LEN) K_2 = KDF(K, 129, UMAC-KEY-LEN) if (UMAC-OUTPUT-LEN <= 16) Y = AES(K_1, Nonce) else Y = AES(K_1, Nonce) || AES(K_2, Nonce) Y = Y[1..UMAC-OUTPUT-LEN] Return Y 5 UHASH-32: Universal hash function for a 32-bit word size UHASH is a keyed hash function, which takes as input a string of arbitrary length, and produces as output a string of fixed length (such as 8 bytes). The actual output length depends on the parameter UMAC-OUTPUT-LEN. UHASH has been shown to be epsilon-ASU ("Almost Strongly Universal"), where epsilon is a small (parameter-dependent) real number. Informally, saying that a keyed hash function is epsilon-ASU means that for any two distinct fixed input strings, the two outputs of the hash function with a random key "look almost like a pair of random strings". The number epsilon measures how non-random the output strings may be. For details, see [3, 4, 11]. UHASH has been designed to be fast by exploiting several architectural features of modern commodity processors. It was specifically designed for use in UMAC. But UHASH is useful beyond that domain, and can be easily adopted for other purposes. UHASH does its work in three layers. First, a hash function called NH [3] is used to compress input messages into strings which are typically many times smaller than the input message. Second, the compressed message is hashed with an optimized "polynomial hash Krovetz et al. Expires April 2001 [Page 15] INTERNET-DRAFT UMAC October 2000 function" into a fixed-length 16-byte string. Finally, the 16-byte string is hashed using an "inner-product hash" into a string of length WORD-LEN bytes. These three layers are repeated (with a modified key) until the outputs total UMAC-OUTPUT-LEN bytes. Note: Because the repetitions of the three-layer scheme are independent (aside from sharing some internal key), it follows that each "word" of the final output can be computed independently. Hence, to compute a prefix of a UMAC tag, one can simply repeat the three-layer scheme fewer times. Thus, computing a prefix of the tag can be done significantly faster than computing the whole tag. 5.1 NH-32: NH hashing with a 32-bit word size The first of the three hash-layers that UHASH uses is the NH hash function [3]. More than any other part of UHASH, NH is designed to be fast on modern processors, because it is where the bulk of the UHASH work is done. The NH universal hash function hashes an input string M using a key K by considering M and K to be arrays of integers, each WORD-LEN bytes in length, and performing a sequence of arithmetic operations on them. See [3] for definitions, proofs and rationale relating to NH. The NH-32 algorithm is designed to perform well on processors which support well multiplications of 32-bit operands into 64-bit results. NH-32 is also designed to exploit the recent trend of including instructions for small-scale vector parallelism in uniprocessor CPUs. Intel's Streaming SIMD 2 instruction set is a good example of this trend. It supports an instruction, which multiplies two pairs of 32-bit operands into two 64-bit results, which can be used by UHASH-32 for accelerated hashing. To accommodate this parallelism, NH-32 accesses data-words in pairs which are 4 words (16 bytes) apart. 5.1.1 Interface Function Name: NH-32 Input: K, string of length L1-KEY-LEN bytes. M, string with length divisible by 32 bytes. Output: Y, string of length 8 bytes. Krovetz et al. Expires April 2001 [Page 16] INTERNET-DRAFT UMAC October 2000 5.1.2 Algorithm Compute Y using the following algorithm. // // Break M and K into 4-byte chunks // t = length(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 Return Y 5.2 L1-HASH-32: First-layer hash To limit the length of key required in the first layer of hashing, L1-HASH-32 breaks the input message into chunks no longer than L1-KEY-LEN and NH hashes each with a key of the same length. 5.2.1 Discussion The NH hash function requires a key which is just as long as the message being hashed. To limit the amount of key used in the NH hashing layer, we use a key of fixed length (defined by the parameter L1-KEY-LEN), and process the message in chunks of this length (or less). The L1-HASH-32 algorithm takes an input message and breaks it into chunks of L1-KEY-LEN bytes (except the last chuck, which may be shorter and may need to be zero-padded to an appropriate length). Each chunk is hashed with NH-32, and the outputs from all the NH invocations are annotated with some length information and concatenated to produce the final L1-HASH-32 result. Krovetz et al. Expires April 2001 [Page 17] INTERNET-DRAFT UMAC October 2000 If ENDIAN-FAVORITE is LITTLE, then each word in the input message is required to be endian reversed. 5.2.2 Interface Function Name: L1-HASH-32 Input: K, string of length L1-KEY-LEN bytes. M, string of length less than 2^64 bytes. Output: Y, string of length (8 * ceil(length(M)/L1-KEY-LEN)) bytes. 5.2.3 Algorithm Compute Y using the following algorithm. // // Break M into L1-KEY-LEN byte chunks (final chunk may be shorter) // t = ceil(length(M) / L1-KEY-LEN) Let M_1, M_2, ..., M_t be strings so that M = M_1 || M_2 || .. || M_t, and length(M_i) = L1-KEY-LEN 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(L1-KEY-LEN * 8, 8) Y = for i = 1 to t-1 do if (ENDIAN-FAVORITE == LITTLE) then // See endian discussion ENDIAN-SWAP(M_i) // in section 3.1.1 Y = Y || (NH-32(K, M_i) +_64 Len) // // For the last chunk: pad to 32-byte boundary, endian-adjust, // NH hash and add bit-length. Concatenate the result to Y. // Len = uint2str(length(M_t) * 8, 8) M_t = zeropad(M_t, 32) if (ENDIAN-FAVORITE == LITTLE) then ENDIAN-SWAP(M_t) Y = Y || (NH-32(K, M_t) +_64 Len) return Y Krovetz et al. Expires April 2001 [Page 18] INTERNET-DRAFT UMAC October 2000 5.3 POLY: Polynomial hash The output from L1-HASH is a string which is shorter than, but still proportional to, that of its input. The POLY hash algorithm takes an arbitrary message and hashes it to a fixed length. 5.3.1 Discussion Polynomial hashing treats an input message as a sequence of coefficients of a polynomial, and the hash-key is the point at which this polynomial is evaluated. The security guarantee assured by polynomial hashing degrades linearly in the length of the message being hashed. If two messages of n words are hashed, then the probability they collide when hashed by POLY with a prime modulus of p is no more than n / p. For more information on the polynomial hashing schemes used in UMAC see [10]. The parameter 'wordbits' specifies the prime modulus used in the polynomial as well as the granularity (length of words) in which the input message should be broken. Because some strings of length wordbits are greater than prime(wordbits), a mechanism is needed to fix words which are not in the range 0 .. prime(wordbits) - 1. To this end, any word larger than 'maxwordrange' is split into two words guaranteed to be in range, and each is hashed by the polynomial hash. 5.3.2 Interface Function Name: POLY Input: wordbits, positive integer divisible by 8. 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. 5.3.3 Algorithm Compute y using the following algorithm. // // Define constants used for fixing out-of-range words // wordbytes = wordbits / 8 Krovetz et al. Expires April 2001 [Page 19] INTERNET-DRAFT UMAC October 2000 p = prime(wordbits) offset = 2^wordbits - p marker = p - 1 // // Break M into chunks of length wordbytes bytes // n = length(M) / wordbytes Let M_1, M_2, ..., M_n be strings of length wordbytes bytes so that M = M_1 || M_2 || .. || M_n // // For each input word, compare it with maxwordrange. If larger // then hash the words 'marker' and (m - offset), both in range. // 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 Return y 5.4 L2-HASH-32: Second-layer hash Because L1-HASH may produce quite long strings, and POLY's security guarantee degrades linearly, a scheme is required to allow long strings while ensuring that the collision probability never grows beyond a certain pre-set bound. This is accomplished by dynamically increasing the prime modulus used in the polynomial hashing as the collision probability bound is approached. 5.4.1 Discussion The probability of two n-word messages hashing to the same result when polynomially hashed with prime modulus p is as much as (n / p). To maintain a limit on the maximum collision probability, a scheme is needed to disallow (n / p) growing too large. The scheme used here hashes a number of words n_1 under modulus p_1 until (n_1 / p_1) reaches a critical point. The result of the hash-so-far is prepended to the remaining message needing to be hashed, and the hashing continues, but under a prime modulus p_2 which is substantially larger than p_1. Hashing continues for n_2 more words until (n_2 / Krovetz et al. Expires April 2001 [Page 20] INTERNET-DRAFT UMAC October 2000 p_2) also reaches a critical point, at which time a new larger prime p_3 could be used. Because polynomial hashing under a small prime modulus is often faster than hashing under a large one, this dynamic ramping-up of the polynomial's modulus provides a hash function which is faster on short messages, but still accommodates long ones. The keys used for polynomial hashing are restricted to particular subsets to allow for faster implementations on 32-bit architectures. The restrictions allow an implementor to disregard some potential arithmetic carries during computation. For more information see [10]. 5.4.2 Interface Function Name: L2-HASH-32 Input: K, string of length 24 bytes. M, string of length less than 2^64 bytes. Output: Y, string of length 16 bytes. 5.4.3 Algorithm Compute y using the following algorithm. // // 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 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 (length(M) <= 2^17) then // 2^14 64-bit words // // View M as an array of 64-bit words, and use POLY modulo Krovetz et al. Expires April 2001 [Page 21] INTERNET-DRAFT UMAC October 2000 // 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 .. length(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) Y = uint2str(y, 16) Return Y 5.5 L3-HASH-32: Third-layer hash The output from L2-HASH-32 is 16 bytes long. This final hash function hashes the 16-byte string to a fixed length of 4 bytes using a simple inner-product hash with affine translation. A 36-bit prime modulus is used to improve security. 5.5.1 Interface Function Name: L3-HASH-32 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. 5.5.2 Algorithm Compute Y using the following algorithm. 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] Krovetz et al. Expires April 2001 [Page 22] INTERNET-DRAFT UMAC October 2000 m_i = str2uint(M_i) k_i = str2uint(K_i) mod prime(36) // // 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 5.6 UHASH-32: Three-layer universal hash The hash functions L1-HASH, L2-HASH and L3-HASH are used together in a straightforward manner. 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 L1-KEY-LEN bytes, then L2-HASH is skipped as an optimization. Because L3-HASH outputs a string whose length is only WORD-LEN bytes long, multiple iterations of this three-layer hash are used, with different keys each time, until UMAC-OUTPUT-LEN have been generated. To reduce memory requirements, L1-HASH and L3-HASH both reuse most of their key-material between iterations. 5.6.1 Interface Function Name: UHASH-32 Input: K, string of length UMAC-KEY-LEN bytes. M, string of length less than 2^64 bytes. Output: Y, string of length UMAC-OUTPUT-LEN bytes. 5.6.2 Algorithm Compute Y using the following algorithm. // // Calculate iterations needed to make UMAC-OUTPUT-LEN bytes // streams = ceil(UMAC-OUTPUT-LEN / WORD-LEN) // Krovetz et al. Expires April 2001 [Page 23] INTERNET-DRAFT UMAC October 2000 // Define total key needed for all iterations using KDF. // L1Key and L3Key1 both reuse most key between iterations. // L1Key = KDF(K, 0, L1-KEY-LEN + (streams - 1) * 16) L2Key = KDF(K, 1, streams * 24) L3Key1 = KDF(K, 2, streams * 64) L3Key2 = KDF(K, 3, streams * 4) // // For each iteration, extract key and three-layer hash. // If length(M) <= L1-KEY-LEN, then skip L2-HASH. // Y = for i = 1 to streams do L1Key_i = L1Key [(i-1) * 16 + 1 .. (i-1) * 16 + L1-KEY-LEN] 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-32(L1Key_i, M) if (length(M) <= L1-KEY-LEN) then B = zeroes(8) || A else B = L2-HASH-32(L2Key_i, A) C = L3-HASH-32(L3Key1_i, L3Key2_i, B) Y = Y || C Y = Y[1 .. UMAC-OUTPUT-LEN] Return Y 6 UHASH-16: Universal hash function for a 16-bit word size See Section 5 (UHASH-32) for general discussion of the UHASH algorithm. Each sub-section of Section 6 will note only differences between UHASH-32 and UHASH-16. 6.1 NH-16: NH hashing with a 16-bit word size The NH-16 algorithm is designed to exploit the recent trend of including instructions for small-scale vector parallelism in uniprocessor CPUs. Intel's MMX and Mororola's AltiVec instruction sets are good examples of this trend. Both support single- instruction multiply-add instructions on vectors of 16-bit words which can be used by UHASH-16 for accelerated hashing. To accommodate this parallelism, NH-16 accesses data-words in pairs which are 8 words (16 bytes) apart. Krovetz et al. Expires April 2001 [Page 24] INTERNET-DRAFT UMAC October 2000 6.1.1 Interface Function Name: NH-16 Input: K, string of length L1-KEY-LEN bytes. M, string with length divisible by 32 bytes. Output: Y, string of length 4 bytes. 6.1.2 Algorithm Compute Y using the following algorithm. // // Break M and K into 2-byte chunks // t = length(M) / 2 Let M_1, M_2, ..., M_t be 2-byte strings so that M = M_1 || M_2 || .. || M_t. Let K_1, K_2, ..., K_t be 2-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 8 apart to accommodate vector-parallelism. // Y = zeroes(4) i = 1 while (i < t) do Y = Y +_32 ((M_{i+0} +_16 K_{i+0}) *_32 (M_{i+ 8} +_16 K_{i+ 8})) Y = Y +_32 ((M_{i+1} +_16 K_{i+1}) *_32 (M_{i+ 9} +_16 K_{i+ 9})) Y = Y +_32 ((M_{i+2} +_16 K_{i+2}) *_32 (M_{i+10} +_16 K_{i+10})) Y = Y +_32 ((M_{i+3} +_16 K_{i+3}) *_32 (M_{i+11} +_16 K_{i+11})) Y = Y +_32 ((M_{i+4} +_16 K_{i+4}) *_32 (M_{i+12} +_16 K_{i+12})) Y = Y +_32 ((M_{i+5} +_16 K_{i+5}) *_32 (M_{i+13} +_16 K_{i+13})) Y = Y +_32 ((M_{i+6} +_16 K_{i+6}) *_32 (M_{i+14} +_16 K_{i+14})) Y = Y +_32 ((M_{i+7} +_16 K_{i+7}) *_32 (M_{i+15} +_16 K_{i+15})) i = i + 16 Return Y 6.2 L1-HASH-16: First-layer hash To limit the length of key required in the first layer of hashing, L1-HASH-16 breaks the input message into chunks no longer than Krovetz et al. Expires April 2001 [Page 25] INTERNET-DRAFT UMAC October 2000 L1-KEY-LEN bytes and NH hashes each with a key of that same length. 6.2.1 Interface Function Name: L1-HASH-16 Input: K, string of length L1-KEY-LEN bytes. M, string of length less than 2^64 bytes. Output: Y, string of length (4 * ceil(length(M)/L1-KEY-LEN)) bytes. 6.2.2 Algorithm Compute Y using the following algorithm. // // Break M into L1-KEY-LEN byte chunks (final chunk may be shorter) // t = ceil(length(M) / L1-KEY-LEN) Let M_1, M_2, ..., M_t be strings so that M = M_1 || M_2 || .. || M_t, and length(M_i) = L1-KEY-LEN 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(L1-KEY-LEN * 8, 4) Y = for i = 1 to t-1 do if (ENDIAN-FAVORITE == LITTLE) then // See endian discussion ENDIAN-SWAP(M_i) // in section 3.1.1 Y = Y || (NH-16(K, M_i) +_32 Len) // // For the last chunk: pad to 32-byte boundary, endian-adjust, // NH hash and add bit-length. Concatenate the result to Y. // Len = uint2str(length(M_t) * 8, 4) M_t = zeropad(M_t, 32) if (ENDIAN-FAVORITE == LITTLE) then ENDIAN-SWAP(M_t) Y = Y || (NH-16(K, M_t) +_32 Len) return Y Krovetz et al. Expires April 2001 [Page 26] INTERNET-DRAFT UMAC October 2000 6.3 L2-HASH-16: Second-layer hash L2-HASH-16 differs from L2-HASH-32 by beginning the ramped hash with a smaller prime modulus. See Section 5.3 for the definition of POLY. 6.3.1 Interface Function Name: L2-HASH-16 Input: K, string of length 28 bytes. M, string of length less than 2^64 bytes. Output: Y, string of length 16 bytes. 6.3.2 Algorithm Compute Y using the following algorithm. // // Extract keys and restrict to special key-sets // Mask32 = uint2str(0x1fffffff, 4) Mask64 = uint2str(0x01ffffff01ffffff, 8) Mask128 = uint2str(0x01ffffff01ffffff01ffffff01ffffff, 16) k_32 = str2uint(K[1..4] and Mask32) k64 = str2uint(K[5..12] and Mask64) k128 = str2uint(K[13..28] and Mask128) // // If M no more than 2^11 bytes, hash under 32-bit prime. // Otherwise, hash under increasingly long primes. // if (length(M) <= 2^11) then // 2^9 32-bit words y = POLY(32, 2^32 - 6, k_32, M) else if (length(M) <= 2^33) then // 2^31 32-bit words M_1 = M[1 .. 2^11] M_2 = M[2^11 + 1 .. length(M)] M_2 = zeropad(M_2 || uint2str(0x80,1), 8) y = POLY(32, 2^32 - 6, k_32, M_1) y = POLY(64, 2^64 - 2^32, k64, uint2str(y, 8) || M_2) else Krovetz et al. Expires April 2001 [Page 27] INTERNET-DRAFT UMAC October 2000 M_1 = M[1 .. 2^11] M_2 = M[2^11 + 1 .. 2^33] M_3 = M[2^33 + 1 .. length(M)] M_3 = zeropad(M || uint2str(0x80,1), 16) y = POLY(32, 2^32 - 6, k_32, M_1) y = POLY(64, 2^64 - 2^32, k64, uint2str(y, 8) || M_2) y = POLY(128, 2^128 - 2^96, k128, uint2str(y, 16) || M_3) Y = uint2str(y, 16) Return Y 6.4 L3-HASH-16: Third-layer hash The L3-HASH-16 algorithm differs from L3-HASH-32 by hashing under a 19-bit prime modulus (instead of a 36-bit prime modulus) and then returning a 2-byte result (instead of a 4-byte result). 6.4.1 Interface Function Name: L3-HASH-16 Input: K1, string of length 32 bytes. K2, a string of length 2 bytes. M, a string of length 16 bytes. Output: Y, a string of length 2 bytes. 6.4.2 Algorithm Compute Y using the following algorithm. 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) * 4 + 1 .. i * 4] m_i = str2uint(M_i) k_i = str2uint(K_i) mod prime(19) // Krovetz et al. Expires April 2001 [Page 28] INTERNET-DRAFT UMAC October 2000 // Inner-product hash, extract last 32 bits and affine-translate // y = (m_1 * k_1 + ... + m_8 * k_8) mod prime(19) y = y mod 2^16 Y = uint2str(y, 2) Y = Y xor K2 Return Y 6.5 UHASH-16: Three-layer universal hash The algorithm UHASH-16 differs from UHASH-32 only in the size of its keys generated, and in that it refers to the 16-bit variants of the three-layer hash functions. 6.5.1 Interface Function Name: UHASH-16 Input: K, string of length UMAC-KEY-LEN bytes. M, string of length less than 2^64 bytes. Output: Y, string of length UMAC-OUTPUT-LEN bytes. 6.5.2 Algorithm Compute Y using the following algorithm. // // Calculate iterations needed to make UMAC-OUTPUT-LEN bytes // streams = ceil(UMAC-OUTPUT-LEN / WORD-LEN) // // Define total key needed for all iterations using KDF. // L1Key and L3Key1 both reuse most key between iterations. // L1Key = KDF(K, 0, L1-KEY-LEN + (streams - 1) * 16) L2Key = KDF(K, 1, streams * 28) L3Key1 = KDF(K, 2, streams * 32) L3Key2 = KDF(K, 3, streams * 2) // // For each iteration, extract key and three-layer hash. Krovetz et al. Expires April 2001 [Page 29] INTERNET-DRAFT UMAC October 2000 // If length(M) <= L1-KEY-LEN, then skip L2-HASH. // Y = for i = 1 to streams do L1Key_i = L1Key [(i-1) * 16 + 1 .. (i-1) * 16 + L1-KEY-LEN] L2Key_i = L2Key [(i-1) * 28 + 1 .. i * 28] L3Key1_i = L3Key1[(i-1) * 32 + 1 .. i * 32] L3Key2_i = L3Key2[(i-1) * 2 + 1 .. i * 2] A = L1-HASH-16(L1Key_i, M) if (length(M) <= L1-KEY-LEN) then B = zeroes(12) || A else B = L2-HASH-16(L2Key_i, A) C = L3-HASH-16(L3Key1_i, L3Key2_i, B) Y = Y || C Y = Y[1 .. UMAC-OUTPUT-LEN] Return Y 7 UMAC tag generation Tag generation for UMAC proceeds as follows. Use UHASH to hash the message and apply the PDF to the nonce to produce a string to xor with the UHASH output. The resulting string is the authentication- tag. 7.1 Interface Function Name: UMAC Input: K, string of length UMAC-KEY-LEN bytes. M, string of length less than 2^64 bytes. Nonce, string of length 1 to 16 bytes. Output: AuthTag, string of length UMAC-OUTPUT-LEN bytes. 7.2 Algorithm Compute AuthTag using the following algorithm. if (WORD-LEN == 2) then HashedMessage = UHASH-16(K, M) else HashedMessage = UHASH-32(K, M) Krovetz et al. Expires April 2001 [Page 30] INTERNET-DRAFT UMAC October 2000 Pad = PDF(K, Nonce) AuthTag = Pad xor HashedMessage Return AuthTag 8 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. 8.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 it is assumed that both operations are implemented using the Advanced Encryption Standard (AES). However, the full design and specification allow for the replacement of these components. Indeed, it is straightforward to use other block ciphers or other cryptographic objects, such as 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. In this way, the strength of UHASH is guaranteed regardless of future advances in cryptanalysis. The analysis of UMAC [3, 4] 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. 8.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 Krovetz et al. Expires April 2001 [Page 31] INTERNET-DRAFT UMAC October 2000 the MAC means that the attacker is able to generate, on its own, 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, e.g. 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 as represented in the next table. -------------------------------------------------------------------- UHASH-OUTPUT-LEN Forging probability Approximate actual forging (bytes) using a random tag probability in UMAC (using a clever tag) 2 2^-16 2^-15 4 2^-32 2^-30 8 2^-64 2^-60 16 2^-128 2^-120 -------------------------------------------------------------------- Recall that the parameter UHASH-OUTPUT-LEN specifies the length of the UMAC authentication tag. The above table states, for example, for the case of an 8-byte tag that the ideal forging probability would be 2^-64 while UMAC would withstand an actual forging probability of 2^-60. Note that under this tag length (which is the default length in UMAC) the 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 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, regardless of tag length, 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 Krovetz et al. Expires April 2001 [Page 32] INTERNET-DRAFT UMAC October 2000 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 - 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. But the architecture of any real system should render this infeasible. One can certainly imagine an attacker having a high bandwidth channel (e.g., 1 Gbit/second or more) over which it can continually present attempted forgeries, the attacker being signaled when a correct tag is found, but realizing such a scenario in a real system would represent a major lapse in the security architecture. It should be pointed out that once an attempted forgery is successful, it is entirely possible that all subsequent messages under this key may be forged, too. This is important to understanding in gauging the severity of a successful forgery. In conclusion, the default 64-bit tags seem appropriate for most security architectures and applications. In cases where when the consequences of an authentication failure are not extremely severe, and when the system architecture is designed to conscientiously limit the number of forgery attempts before a session is torn down, 32-bit authentication tags may be adequate. For the paranoid, or if an attacker is allowed a fantastic number of forgery tests, 96- or 128-bits may be utilized. 8.3 Selective-assurance authentication We have already remarked about the flexibility built into UMAC to use authentication tags of various lengths: shorter tags are faster to compute and one needs to transmit fewer bits, but the forging probability is higher. There is an additional degree of flexibility built into the design of UMAC: even if the sender generates and transmits a tag of 8 bytes, say, a receiver may elect to verify only the first 4 bytes of the tag, and computing that 4-byte prefix by the receiver will be substantially faster than computing what the full 8-byte tag would be. Indeed when WORD-LEN is 2 one can more quickly check the 2-byte prefix of the tag than the 4-byte prefix of the tag, one can more quickly check the 4-byte prefix of the tag than the Krovetz et al. Expires April 2001 [Page 33] INTERNET-DRAFT UMAC October 2000 6-byte prefix of the tag, and so forth. When WORD-LEN is 4 one can more quickly check the 4-byte prefix of the tag than an entire 8-byte tag, and so forth. This type of flexibility allows different parties who receive a MAC (as in a multicast setting) to authenticate the transmission to the extent deemed necessary and to the extent consistent with any computational limits of the receiver. In a scenario where receivers are allowed to verify short prefixes of longer tags, it is even more important that conservative policies are followed when a bad tag is presented to the receiver. Because short prefixes are easier to forge than are long ones, an attacker may attempt to forge short prefixes and then leverage information gained from these attacks to forge longer tags. If the attacker can learn which short tags are good and which are bad, the attacker may be able to learn enough to allow longer forgeries. One salient feature of the security-performance trade-off offered by UMAC is its usability in contexts where performance is severely constrained. In such cases, using a mild-security authentication tag can be of significant value especially if the alternative would be not to use authentication at all (a possible such scenario could be the high-speed transmission of real-time multimedia streams). Another potential scenario where short and fast-to-compute tags can be useful is for fast detection of data forgery intended as a denial of service attack. In this case, even a moderate increase in the attacker's difficulty to produce forgeries may suffice to make the attack worthless for the attacker. Moreover, being able to detect just a portion of attempted forgeries may be enough to identify the attack. 8.4 Nonce considerations The function UMAC (Section 7) 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 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 Krovetz et al. Expires April 2001 [Page 34] INTERNET-DRAFT UMAC October 2000 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. The application will then specify how to construct the nonce from this already-existing field. Note that if the nonce starts at zero and is incremented with each message then an attacker can easily ascertain the number of messages which have been sent during a session. If this is information which one wishes to deny the attacker then one might have the sender initialize the nonce to a random value, rather than to zero. Inspecting the current nonce will no longer reveal to the attacker the number of messages which have been sent during this session. This is a computationally cheaper approach than enciphering the nonce. 8.5 Guarding against replay attacks A replay attack entails the attacker repeating a message, nonce, and authentication tag. In systems, replay attacks may be quite damaging, and many applications will want to guard against them. 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 Krovetz et al. Expires April 2001 [Page 35] INTERNET-DRAFT UMAC October 2000 connection, when the nonce is a counter, this is trivial. On an unreliable connection, when the nonce is a counter, one would normally cache some "window" of recent nonces. Out-of-order message delivery in excess of what the window allows will result in rejecting otherwise valid authentication tags. We emphasize that it is up to the receiver when a given message, nonce and tag 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. 9 Acknowledgments Thanks are due to David Balenson and David Carman of NAI Labs, who suggested the advantages of allowing a receiver to verify authentication tags to various forgery probabilities. Thanks are also due to David McGrew and Scott Fluhrer of Cisco Systems for encouraging us to improve UMAC performance on short messages. 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, 98-129, and 99-103 funded by RSA Data Security, Inc., and ORINCON Corporation. Much of Rogaway's work was carried out during two sabbatical visits to Chiang Mai University. Special thanks to Prof. Darunee Smawatakul for helping to arrange these visits. 10 References [1] ANSI X9.9, "American National Standard for Financial Institution Message Authentication (Wholesale)", American Bankers Association, 1981. Revised 1986. [2] 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/ [3] 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. Full version available from http://www.cs.ucdavis.edu/~rogaway/umac [4] J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P. Rogaway, "The UMAC message authentication code", work in progress, 2000. Krovetz et al. Expires April 2001 [Page 36] INTERNET-DRAFT UMAC October 2000 To be available from http://www.cs.ucdavis.edu/~rogaway/umac [5] L. Carter and M. Wegman, "Universal classes of hash functions", Journal of Computer and System Sciences, 18 (1979), pp. 143-154. [6] O. Goldreich, S. Goldwasser and S. Micali, "How to construct random functions", Journal of the ACM, 33, No. 4 (1986), pp. 210-217. [7] 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. [8] ISO/IEC 9797-1, "Information technology - Security techniques - Data integrity mechanism using a cryptographic check function employing a block cipher algorithm", International Organization for Standardization, 1999. [9] H. Krawczyk, M. Bellare, and R. Canetti, "HMAC: Keyed-hashing for message authentication", RFC-2104, February 1997. [10] T. Krovetz, and P. Rogaway, "Fast universal hashing with small keys and no preprocessing", work in progress, 2000. To be available from http://www.cs.ucdavis.edu/~rogaway/umac [11] T. Krovetz, and P. Rogaway, "Variationally universal hashing", work in progress, 2000. To be available from http://www.cs.ucdavis.edu/~rogaway/umac [12] 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. 11 Author contact information Authors' Addresses John Black Department of Computer Science University of Nevada Reno NV 89557 USA EMail: jrb@cs.unr.edu Shai Halevi Krovetz et al. Expires April 2001 [Page 37] INTERNET-DRAFT UMAC October 2000 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 & Engineering University of California at San Diego La Jolla CA 92093 USA EMail: ahevia@cs.ucsd.edu Hugo Krawczyk Deprtment of Electrical Engineering Technion Haifa 32000 ISRAEL EMail: hugo@ee.technion.ac.il Ted Krovetz Intel Corporation 1900 Prairie City Road Folsom CA 95630 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 UMAC_CTX struct */ Krovetz et al. Expires April 2001 [Page 38] INTERNET-DRAFT UMAC October 2000 /* 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, void *params); /* After default initialization, */ /* optionally set parameters to */ /* different values and reset for */ /* new message. */ int umac_update(umac_ctx_t ctx, char *input, long len); /* Incorporate len bytes pointed to by */ /* input into context ctx. */ int umac_final(umac_ctx_t ctx, char tag[], char nonce[]); /* Incorporate nonce value and return */ /* tag. Reset ctx for next message. */ int umac(umac_ctx_t ctx, char *input, long len, char tag[], char nonce[]); /* All-in-one (non-incremental) */ /* implementation of the functions */ /* umac_update() and umac_final(). */ Each routine returns zero if unsuccessful. B Reference code and test vectors See the UMAC World Wide Web homepage for reference code and test vectors. http://www.cs.ucdavis.edu/~rogaway/umac/ Krovetz et al. Expires April 2001 [Page 39]