RFC 4418
UMAC: Message Authentication Code using Universal Hashing
RFC 4418: UMAC, Message Authentication Code using Universal Hashing 🎀
Okay bestie, here's the header info you need first 💅
- Series: Request for Comments 4418, from the Network Working Group
- Author: T. Krovetz, Ed., CSU Sacramento
- Category: Informational
- Date: March 2006
- Obsoletes / Updates: This header doesn't list anything it obsoletes or updates
Status of This Memo ✨
This memo is just here to share information with the Internet community. It is not a standard of any kind 🧚 Distribution is unlimited, so share it with everyone.
Copyright Notice 💜
Copyright (C) The Internet Society (2006).
Abstract 🌸
This spec explains how to make an authentication tag using the UMAC message authentication algorithm. UMAC was built to be super fast to compute in software on normal uniprocessors, and measured speeds get as low as one cycle per byte 🔥 It mostly just uses addition of 32-bit and 64-bit numbers plus multiplication of 32-bit numbers, which contemporary machines are really good at.
So here's the vibe: a "universal" hash function gets applied to the message and key to make a short, fixed-length hash value. Then that hash value gets xor'ed with a pad that's derived from the key. UMAC has a rigorous security analysis, and its only internal "cryptographic" piece is a block cipher, which is used to generate the pseudorandom pads and internal key material 🦋
Table of Contents 🍓
1. Introduction ....................................................3
2. Notation and Basic Operations ...................................4
2.1. Operations on strings ......................................4
2.2. Operations on Integers .....................................5
2.3. String-Integer Conversion Operations .......................6
2.4. Mathematical Operations on Strings .........................6
2.5. ENDIAN-SWAP: Adjusting Endian Orientation ..................6
2.5.1. ENDIAN-SWAP Algorithm ...............................6
3. Key- and Pad-Derivation Functions ...............................7
3.1. Block Cipher Choice ........................................7
3.2. KDF: Key-Derivation Function ...............................8
3.2.1. KDF Algorithm .......................................8
3.3. PDF: Pad-Derivation Function ...............................8
3.3.1. PDF Algorithm .......................................9
4. UMAC Tag Generation ............................................10
4.1. UMAC Algorithm ............................................10
4.2. UMAC-32, UMAC-64, UMAC-96, and UMAC-128 ...................10
5. UHASH: Universal Hash Function .................................10
5.1. UHASH Algorithm ...........................................11
5.2. L1-HASH: First-Layer Hash .................................12
5.2.1. L1-HASH Algorithm ..................................12
5.2.2. NH Algorithm .......................................13
5.3. L2-HASH: Second-Layer Hash ................................14
5.3.1. L2-HASH Algorithm ..................................14
5.3.2. POLY Algorithm .....................................15
5.4. L3-HASH: Third-Layer Hash .................................16
5.4.1. L3-HASH Algorithm ..................................16
6. Security Considerations ........................................17
6.1. Resistance to Cryptanalysis ...............................17
6.2. Tag Lengths and Forging Probability .......................17
6.3. Nonce Considerations ......................................19
6.4. Replay Attacks ............................................20
6.5. Tag-Prefix Verification ...................................21
6.6. Side-Channel Attacks ......................................21
7. Acknowledgements ...............................................21
Appendix. Test Vectors ............................................22
References ........................................................24
Normative References ...........................................24
Informative References .........................................241. Introduction 💖
UMAC is a message authentication code (MAC) algorithm built for high performance 🏎️ It has a rigorous formal analysis behind it, and none of the authors make any intellectual property claims over the ideas used in its design. No IP drama here, periodt 🙌
UMAC is a MAC in the style of Wegman and Carter [4, 7]. A fast "universal" hash function hashes an input message M into a short string. That short string gets masked by xor'ing it with a pseudorandom pad, and the result is the UMAC tag. Security depends on the sender and receiver sharing a randomly-chosen secret hash function and pseudorandom pad. This works by using keyed hash function H and pseudorandom function F. The tag comes from this computation:
Tag = H_K1(M) xor F_K2(Nonce)Here K1 and K2 are secret random keys that the sender and receiver share, and Nonce is a value that changes with each tag that gets generated. The receiver has to know which nonce the sender used, so some method of synchronizing nonces is needed. You can do that by explicitly sending the nonce along with the message and tag, or by agreeing on some other non-repeating value, like a sequence number. The nonce doesn't need to be kept secret. Still, you have to be careful that, over the whole lifetime of a UMAC key, a different nonce gets used with each message 🔐
UMAC uses a keyed function called UHASH (also specified in this document) as the keyed hash function H. For the pseudorandom function F, its default implementation uses the Advanced Encryption Standard (AES) algorithm. UMAC can produce 32-, 64-, 96-, or 128-bit tags, depending on how much security you want ✨ The theory of Wegman-Carter MACs and the analysis of UMAC show that if you "instantiate" UMAC with truly random keys and pads, then the chance an attacker (even a computationally unbounded one) makes a correct tag for any message it picks is no more than 1/2^30, 1/2^60, 1/2^90, or 1/2^120 when the tags are 32, 64, 96, or 128 bits long, respectively. (Here the symbol ^ means exponentiation.) When an attacker makes N forgery attempts, the chance of getting one or more tags right goes up linearly, to at most N/2^30, N/2^60, N/2^90, or N/2^120. In a real UMAC implementation, where AES makes the keys and pads, the forgery probabilities above go up by a small amount tied to the security of AES. As long as AES is secure, that small extra term doesn't matter for any practical attack 🙈 See Section 6.2 for more details. Analysis relevant to UMAC security is in [3, 6].
UMAC is fastest where 32-bit quantities get multiplied into 64-bit results efficiently 🚀 When producing 64-bit tags on an Intel Pentium 4 using SSE2 instructions, which do two of these multiplications in parallel, UMAC processes messages at a peak rate of about one CPU cycle per byte. That peak shows up on messages around four kilobytes and longer. On the Pentium III, without SSE parallelism, UMAC peaks at two cycles per byte. Shorter messages still do great: around four cycles per byte on 256-byte messages, and under two cycles per byte on 1500-byte messages 💅 Making a 32-bit tag takes a little more than half the time it takes to make a 64-bit tag, while 96- and 128-bit tags take one-and-a-half and twice as long, respectively.
Optimized source code, performance data, errata, and papers about UMAC are all at http://www.cs.ucdavis.edu/~rogaway/umac/. Go check them out 🌈
2. Notation and Basic Operations 🦋
UMAC's spec involves working with both strings and numbers. String variables start with an uppercase letter, while numeric variables are all lowercase. UMAC's algorithms are written in all uppercase letters, and simple functions, like the ones for string-length and string-xor, are all lowercase 🍓
When a variable is followed by an underscore ("_"), the underscore marks a subscript, and the subscripted expression gets evaluated to figure out what the variable means. For example, if i=2, then M_{2 * i} refers to the variable M_4 🧠
2.1. Operations on strings 🫶
Messages to be hashed are treated as strings of bits that get zero-padded out to an appropriate byte length. Once the message is padded, all the strings are treated as strings of bytes. A "byte" is an 8-bit string. Here's the notation used to manipulate these strings:
bytelength(S): The length of string S in bytes.
bitlength(S): The length of string S in bits.
zeroes(n): The string made of n zero-bytes.
S xor T: The string that is the bitwise exclusive-or of S
and T. Strings S and T always have the same
length.
S and T: The string that is the bitwise conjunction of S
and T. Strings S and T always have the same
length.
S[i]: The i-th byte of the string S (indices begin at
1).
S[i...j]: The substring of S consisting of bytes i through
j.
S || T: The string S concatenated with string T.
zeropad(S,n): The string S, padded with zero-bits to the
nearest positive multiple of n bytes. Formally,
zeropad(S,n) = S || T, where T is the shortest
string of zero-bits (possibly empty) so that S
|| T is non-empty and 8n divides bitlength(S ||
T).2.2. Operations on Integers 🔢
Standard notation covers most math operations, like "*" for multiplication, "+" for addition, and "mod" for modular reduction. A few less standard notations get defined here:
a^i: The integer a raised to the i-th power.
ceil(x): The smallest integer greater than or equal to x.
prime(n): The largest prime number less than 2^n.The prime numbers used in UMAC are:
+-----+--------------------+---------------------------------------+
| n | prime(n) [Decimal] | prime(n) [Hexadecimal] |
+-----+--------------------+---------------------------------------+
| 36 | 2^36 - 5 | 0x0000000F FFFFFFFB |
| 64 | 2^64 - 59 | 0xFFFFFFFF FFFFFFC5 |
| 128 | 2^128 - 159 | 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFF61 |
+-----+--------------------+---------------------------------------+2.3. String-Integer Conversion Operations 🎀
Conversion between strings and integers uses the functions below. Each one treats the initial bits as more significant than the later ones ✨
bit(S,n): Returns the integer 1 if the n-th bit of the string
S is 1, otherwise returns the integer 0 (indices
begin at 1).
str2uint(S): The non-negative integer whose binary
representation is the string S. More formally, if
S is t bits long then str2uint(S) = 2^{t-1} *
bit(S,1) + 2^{t-2} * bit(S,2) + ... + 2^{1} *
bit(S,t-1) + bit(S,t).
uint2str(n,i): The i-byte string S such that str2uint(S) = n.2.4. Mathematical Operations on Strings ✨
Okay bestie, one of the main moves in UMAC is repeatedly adding and multiplying strings together 🧮💖 The spec defines three operators for this:
"S +_32 T" as uint2str(str2uint(S) + str2uint(T) mod 2^32, 4),
"S +_64 T" as uint2str(str2uint(S) + str2uint(T) mod 2^64, 8), and
"S *_64 T" as uint2str(str2uint(S) * str2uint(T) mod 2^64, 8).These operations match up really nicely with the addition and multiplication that modern computers already do super efficiently 🔥 literally main character math.
2.5. ENDIAN-SWAP: Adjusting Endian Orientation 🔄
Message data gets read little-endian so tag generation goes faster on little-endian computers 🚀 it's giving speed.
2.5.1. ENDIAN-SWAP Algorithm
Input:
S, string with length divisible by 4 bytes.
Output:
T, string S with each 4-byte word endian-reversed.Compute T using the following algorithm 💅
//
// Break S into 4-byte chunks
//
n = bytelength(S) / 4
Let S_1, S_2, ..., S_n be strings of length 4 bytes
so that S_1 || S_2 || ... || S_n = S.
//
// Byte-reverse each chunk, and build-up T
//
T = <empty string>
for i = 1 to n do
Let W_1, W_2, W_3, W_4 be bytes
so that W_1 || W_2 || W_3 || W_4 = S_i
SReversed_i = W_4 || W_3 || W_2 || W_1
T = T || SReversed_i
end for
Return T3. Key- and Pad-Derivation Functions 🗝️
Okay so UHASH and tag generation both need pseudorandom bits internally 🎀 The functions in this section use a block cipher to make those bits, and it's honestly such a clever setup.
3.1. Block Cipher Choice 🧁
UMAC uses the services of a block cipher ✨ Picking the block cipher defines the following constants and functions:
BLOCKLEN The length, in bytes, of the plaintext block on
which the block cipher operates.
KEYLEN The block cipher's key length, in bytes.
ENCIPHER(K,P) The application of the block cipher on P (a
string of BLOCKLEN bytes) using key K (a string
of KEYLEN bytes).For example, if AES is used with 16-byte keys, then BLOCKLEN would equal 16 (because AES employs 16-byte blocks), KEYLEN would equal 16, and ENCIPHER would refer to the AES function 🦋
Unless specified otherwise, AES with 128-bit keys shall be assumed to be the chosen block cipher for UMAC. Only if explicitly specified otherwise, and agreed to by communicating parties, shall some other block cipher be used. In any case, BLOCKLEN must be at least 16 and a power of two. No skipping this part, bestie! 🙈
AES is defined in another document [1].
3.2. KDF: Key-Derivation Function 🔑
The key-derivation function generates the pseudorandom bits used to key the hash functions. Iykyk 💜
3.2.1. KDF Algorithm
Input:
K, string of length KEYLEN bytes.
index, a non-negative integer less than 2^64.
numbytes, a non-negative integer less than 2^64.
Output:
Y, string of length numbytes bytes.Compute Y using the following algorithm 🌸
//
// Calculate number of block cipher iterations
//
n = ceil(numbytes / BLOCKLEN)
Y = <empty string>
//
// Build Y using block cipher in a counter mode
//
for i = 1 to n do
T = uint2str(index, BLOCKLEN-8) || uint2str(i, 8)
T = ENCIPHER(K, T)
Y = Y || T
end for
Y = Y[1...numbytes]
Return Y3.3. PDF: Pad-Derivation Function 🧚
This function takes a key and a nonce and returns a pseudorandom pad for use in tag generation. A pad of length 4, 8, 12, or 16 bytes can be generated. Notice that pads generated using nonces that differ only in their last bit (when generating 8-byte pads) or last two bits (when generating 4-byte pads) are derived from the same block cipher encryption. This allows caching and sharing a single block cipher invocation for sequential nonces. Smart, right? 🧠✨
3.3.1. PDF Algorithm
Input:
K, string of length KEYLEN bytes.
Nonce, string of length 1 to BLOCKLEN bytes.
taglen, the integer 4, 8, 12 or 16.
Output:
Y, string of length taglen bytes.Compute Y using the following algorithm 💅
//
// Extract and zero low bit(s) of Nonce if needed
//
if (taglen = 4 or taglen = 8)
index = str2uint(Nonce) mod (BLOCKLEN/taglen)
Nonce = Nonce xor uint2str(index, bytelength(Nonce))
end if
//
// Make Nonce BLOCKLEN bytes by appending zeroes if needed
//
Nonce = Nonce || zeroes(BLOCKLEN - bytelength(Nonce))
//
// Generate subkey, encipher and extract indexed substring
//
K' = KDF(K, 0, KEYLEN)
T = ENCIPHER(K', Nonce)
if (taglen = 4 or taglen = 8)
Y = T[1 + (index*taglen) ... taglen + (index*taglen)]
else
Y = T[1...taglen]
end if
Return Y4. UMAC Tag Generation 🏷️
Tag generation for UMAC goes like this: UHASH (defined in the next section) hashes the message, the PDF is applied to the nonce, and then the resulting strings get xor'd together 🎀 The pad and hash can each be 4, 8, 12, or 16 bytes long.
4.1. UMAC Algorithm 🌈
Input:
K, string of length KEYLEN bytes.
M, string of length less than 2^67 bits.
Nonce, string of length 1 to BLOCKLEN bytes.
taglen, the integer 4, 8, 12 or 16.
Output:
Tag, string of length taglen bytes.Compute Tag using the following algorithm ✨
HashedMessage = UHASH(K, M, taglen)
Pad = PDF(K, Nonce, taglen)
Tag = Pad xor HashedMessage
Return Tag4.2. UMAC-32, UMAC-64, UMAC-96, and UMAC-128 🧁
The UMAC definition above has a parameter "taglen", which says how long the generated tag is. The aliases below put the tag length right in the name, which is so much easier to read 🫶
UMAC-32(K, M, Nonce) = UMAC(K, M, Nonce, 4)
UMAC-64(K, M, Nonce) = UMAC(K, M, Nonce, 8)
UMAC-96(K, M, Nonce) = UMAC(K, M, Nonce, 12)
UMAC-128(K, M, Nonce) = UMAC(K, M, Nonce, 16)5. UHASH: Universal Hash Function 🦄
UHASH is a keyed hash function. It takes an input string of arbitrary length and produces a 4-, 8-, 12-, or 16-byte output. UHASH does its work in three stages, or layers. A message is first hashed by L1-HASH, its output is then hashed by L2-HASH, and that output is hashed by L3-HASH. If the message being hashed is no longer than 1024 bytes, then L2-HASH is skipped as an optimization ⚡ Because L3-HASH outputs a string that's only four bytes long, multiple iterations of this three-layer hash are used if a total hash output longer than four bytes is requested. To reduce memory use, L1-HASH reuses most of its key material between iterations. A significant amount of internal key is required for UHASH, but it stays constant as long as UMAC's key is unchanged. It's up to the implementer whether to generate the internal keys each time a message is hashed, or to cache them between messages 💖
Please note that UHASH has certain combinatoric properties that make it suitable for Wegman-Carter message authentication. UHASH is not a cryptographic hash function and is not a suitable general replacement for functions like SHA-1. Not a general replacement, babe, don't swap it in for SHA-1! 🚫
UHASH is presented here in a top-down manner. First, UHASH is described, then each of its component hashes is presented 🪄
5.1. UHASH Algorithm 🔮
Input:
K, string of length KEYLEN bytes.
M, string of length less than 2^67 bits.
taglen, the integer 4, 8, 12 or 16.
Output:
Y, string of length taglen bytes.Compute Y using the following algorithm 💅
//
// One internal iteration per 4 bytes of output
//
iters = taglen / 4
//
// Define total key needed for all iterations using KDF.
// L1Key reuses most key material between iterations.
//
L1Key = KDF(K, 1, 1024 + (iters - 1) * 16)
L2Key = KDF(K, 2, iters * 24)
L3Key1 = KDF(K, 3, iters * 64)
L3Key2 = KDF(K, 4, iters * 4)
//
// For each iteration, extract key and do three-layer hash.
// If bytelength(M) <= 1024, then skip L2-HASH.
//
Y = <empty string>
for i = 1 to iters do
L1Key_i = L1Key [(i-1) * 16 + 1 ... (i-1) * 16 + 1024]
L2Key_i = L2Key [(i-1) * 24 + 1 ... i * 24]
L3Key1_i = L3Key1[(i-1) * 64 + 1 ... i * 64]
L3Key2_i = L3Key2[(i-1) * 4 + 1 ... i * 4]
A = L1-HASH(L1Key_i, M)
if (bitlength(M) <= bitlength(L1Key_i)) then
B = zeroes(8) || A
else
B = L2-HASH(L2Key_i, A)
end if
C = L3-HASH(L3Key1_i, L3Key2_i, B)
Y = Y || C
end for
Return Y5.2. L1-HASH: First-Layer Hash 🍓
The first layer breaks the message into 1024-byte chunks and hashes each one with a function called NH. Concatenating the results makes a string that's up to 128 times shorter than the original. Wild compression energy 🗜️✨
5.2.1. L1-HASH Algorithm 🧩
Input:
K, string of length 1024 bytes.
M, string of length less than 2^67 bits.
Output:
Y, string of length (8 * ceil(bitlength(M)/8192)) bytes.Compute Y using the following algorithm 🌷
//
// Break M into 1024 byte chunks (final chunk may be shorter)
//
t = max(ceil(bitlength(M)/8192), 1)
Let M_1, M_2, ..., M_t be strings so that M = M_1 || M_2 || ... ||
M_t, and bytelength(M_i) = 1024 for all 0 < i < t.
//
// For each chunk, except the last: endian-adjust, NH hash
// and add bit-length. Use results to build Y.
//
Len = uint2str(1024 * 8, 8)
Y = <empty string>
for i = 1 to t-1 do
ENDIAN-SWAP(M_i)
Y = Y || (NH(K, M_i) +_64 Len)
end for
//
// For the last chunk: pad to 32-byte boundary, endian-adjust,
// NH hash and add bit-length. Concatenate the result to Y.
//
Len = uint2str(bitlength(M_t), 8)
M_t = zeropad(M_t, 32)
ENDIAN-SWAP(M_t)
Y = Y || (NH(K, M_t) +_64 Len)
return Y5.2.2. NH Algorithm 🏎️
This routine gets applied directly to every bit of input data, so an optimized implementation of it is a massive win 🔥
Input:
K, string of length 1024 bytes.
M, string with length divisible by 32 bytes.
Output:
Y, string of length 8 bytes.Compute Y using the following algorithm 💫
//
// Break M and K into 4-byte chunks
//
t = bytelength(M) / 4
Let M_1, M_2, ..., M_t be 4-byte strings
so that M = M_1 || M_2 || ... || M_t.
Let K_1, K_2, ..., K_t be 4-byte strings
so that K_1 || K_2 || ... || K_t is a prefix of K.
//
// Perform NH hash on the chunks, pairing words for multiplication
// which are 4 apart to accommodate vector-parallelism.
//
Y = zeroes(8)
i = 1
while (i < t) do
Y = Y +_64 ((M_{i+0} +_32 K_{i+0}) *_64 (M_{i+4} +_32 K_{i+4}))
Y = Y +_64 ((M_{i+1} +_32 K_{i+1}) *_64 (M_{i+5} +_32 K_{i+5}))
Y = Y +_64 ((M_{i+2} +_32 K_{i+2}) *_64 (M_{i+6} +_32 K_{i+6}))
Y = Y +_64 ((M_{i+3} +_32 K_{i+3}) *_64 (M_{i+7} +_32 K_{i+7}))
i = i + 8
end while
Return Y5.3. L2-HASH: Second-Layer Hash 🌊
The second layer rehashes the L1-HASH output using a polynomial hash called POLY. If the L1-HASH output is long, then POLY is called once on a prefix of the L1-HASH output and called with different settings on the remainder. (This two-step hashing of the L1-HASH output is needed only if the message length is greater than 16 megabytes.) Careful implementation of POLY is necessary to avoid a possible timing attack (see Section 6.6 for more information) 🙈⚠️
5.3.1. L2-HASH Algorithm ✨
okay so this is the big brain step 🧠 L2-HASH takes your key and message and squishes them down to 16 bytes. Here's the deal:
- Input:
K, string of length 24 bytes.M, string of length less than 2^64 bytes.
- Output:
Y, string of length 16 bytes.
Compute y with this algorithm. It's giving precision 💅
//
// Extract keys and restrict to special key-sets
//
Mask64 = uint2str(0x01ffffff01ffffff, 8)
Mask128 = uint2str(0x01ffffff01ffffff01ffffff01ffffff, 16)
k64 = str2uint(K[1...8] and Mask64)
k128 = str2uint(K[9...24] and Mask128)
//
// If M is no more than 2^17 bytes, hash under 64-bit prime,
// otherwise, hash first 2^17 bytes under 64-bit prime and
// remainder under 128-bit prime.
//
if (bytelength(M) <= 2^17) then // 2^14 64-bit words
//
// View M as an array of 64-bit words, and use POLY modulo
// prime(64) (and with bound 2^64 - 2^32) to hash it.
//
y = POLY(64, 2^64 - 2^32, k64, M)
else
M_1 = M[1...2^17]
M_2 = M[2^17 + 1 ... bytelength(M)]
M_2 = zeropad(M_2 || uint2str(0x80,1), 16)
y = POLY(64, 2^64 - 2^32, k64, M_1)
y = POLY(128, 2^128 - 2^96, k128, uint2str(y, 16) || M_2)
end if
Y = uint2str(y, 16)
Return YSo the key gets split up, and the message gets hashed in two different ways depending on how big it is. Small messages go through one 64-bit prime 🌸 Big ones get the first 2^17 bytes under the 64-bit prime, then the leftovers get handled under the 128-bit prime 💜
5.3.2. POLY Algorithm 🎀
POLY is the workhorse that L2-HASH calls, and it's honestly so iconic. Here's what it takes in and gives back:
- Input:
wordbits, the integer 64 or 128.maxwordrange, positive integer less than 2^wordbits.k, integer in the range 0 ... prime(wordbits) - 1.M, string with length divisible by (wordbits / 8) bytes.
- Output:
y, integer in the range 0 ... prime(wordbits) - 1.
Compute y using the following algorithm 🦋
//
// Define constants used for fixing out-of-range words
//
wordbytes = wordbits / 8
p = prime(wordbits)
offset = 2^wordbits - p
marker = p - 1
//
// Break M into chunks of length wordbytes bytes
//
n = bytelength(M) / wordbytes
Let M_1, M_2, ..., M_n be strings of length wordbytes bytes
so that M = M_1 || M_2 || ... || M_n
//
// Each input word m is compared with maxwordrange. If not smaller
// then 'marker' and (m - offset), both in range, are hashed.
//
y = 1
for i = 1 to n do
m = str2uint(M_i)
if (m >= maxwordrange) then
y = (k * y + marker) mod p
y = (k * y + (m - offset)) mod p
else
y = (k * y + m) mod p
end if
end for
Return yBasically, every word gets checked against maxwordrange. If it's too big, POLY sneaks in a marker and then the shifted value, so nothing gets dropped 😭✨
5.4. L3-HASH: Third-Layer Hash 🧚
okay the final boss 👑 The output from L2-HASH is 16 bytes long. This last hash function takes that 16-byte string and shrinks it to a fixed length of 4 bytes. Tiny, but mighty!
5.4.1. L3-HASH Algorithm 💖
- Input:
K1, string of length 64 bytes.K2, string of length 4 bytes.M, string of length 16 bytes.
- Output:
Y, string of length 4 bytes.
Compute Y using the following algorithm 🌈
y = 0
//
// Break M and K1 into 8 chunks and convert to integers
//
for i = 1 to 8 do
M_i = M [(i - 1) * 2 + 1 ... i * 2]
K_i = K1[(i - 1) * 8 + 1 ... i * 8]
m_i = str2uint(M_i)
k_i = str2uint(K_i) mod prime(36)
end for
//
// Inner-product hash, extract last 32 bits and affine-translate
//
y = (m_1 * k_1 + ... + m_8 * k_8) mod prime(36)
y = y mod 2^32
Y = uint2str(y, 4)
Y = Y xor K2
Return YSo it's an inner-product hash, then it keeps the last 32 bits, then it XORs with K2. Cute and compact 🎀
6. Security Considerations 🔥
ngl this is the part that matters most, bestie 😭 As a message authentication code specification, this entire document is about security. Here we describe some security considerations that are important for properly understanding and using UMAC.
6.1. Resistance to Cryptanalysis 🔐
The strength of UMAC depends on the strength of its underlying cryptographic functions: the key-derivation function (KDF) and the pad-derivation function (PDF). In this specification, both operations are implemented using a block cipher, by default the Advanced Encryption Standard (AES). However, the design of UMAC allows for the replacement of these components. Indeed, it is possible to use other block ciphers or other cryptographic objects, such as (properly keyed) SHA-1 or HMAC for the realization of the KDF or PDF.
The core of the UMAC design, the UHASH function, does not depend on cryptographic assumptions. Its strength is specified by a purely mathematical property stated in terms of collision probability, and this property is proven unconditionally [3, 6]. This means the strength of UHASH is guaranteed regardless of advances in cryptanalysis. Iconic, right? 💅
The analysis of UMAC [3, 6] 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 that forges with probability that significantly exceeds the established collision probability of UHASH will give rise to an attack of comparable complexity. That attack will break the block cipher, in the sense of distinguishing the block cipher from a family of random permutations. This design approach essentially obviates the need for cryptanalysis on UMAC: cryptanalytic efforts might as well focus on the block cipher, the results imply. Main character energy 👑
6.2. Tag Lengths and Forging Probability 🦋
okay this one's a big deal 🙈 A MAC algorithm is used to authenticate messages between two parties that share a secret MAC key K. An authentication tag is computed for a message using K and, in some MAC algorithms such as UMAC, a nonce. Messages transmitted between parties are accompanied by their tag and, possibly, nonce. Breaking the MAC means the attacker is able to generate, on its own, with no knowledge of the key K, a new message M (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 its probability of success linearly.
In the case of UMAC-64, for example, the guessing-attack strategy above is close to optimal. An adversary can correctly guess an 8-byte UMAC tag with probability 1/2^64 by simply guessing a random value.
The results of [3, 6] show that no attack strategy can produce a correct tag with probability better than 1/2^60 if UMAC were to use a random function in its work rather than AES. Another result [2], when combined with [3, 6], shows that so long as AES is secure as a pseudorandom permutation, it can be used instead of a random function without significantly increasing the 1/2^60 forging probability, assuming that no more than 2^64 messages are authenticated. Likewise, 32-, 96-, and 128-bit tags cannot be forged with more than 1/2^30, 1/2^90, and 1/2^120 probability plus the probability of a successful attack against AES as a pseudorandom permutation.
AES has undergone extensive study and is assumed to be very secure as a pseudorandom permutation. If we assume that no attacker with feasible computational power can distinguish randomly-keyed AES from a randomly-chosen permutation with probability delta (more precisely, delta is a function of the computational resources of the attacker and of its ability to sample the function), then no such attacker can forge UMAC with probability greater than 1/2^30, 1/^60, 1/2^90, or 1/2^120, plus 3*delta. Over N forgery attempts, forgery occurs with probability no more than N/2^30, N/^60, N/2^90, or N/2^120, plus 3*delta. The value delta may exceed 1/2^30, 1/2^60, 1/2^90, or 1/2^120, in which case the probability of UMAC forging is dominated by a term representing the security of AES.
With UMAC, off-line computation aimed at exceeding the forging probability is hopeless as long as the underlying cipher is not broken. An attacker attempting to forge UMAC tags will need to interact with the entity that verifies message tags and try a large number of forgeries before one is likely to succeed. The system architecture will determine the extent to which this is possible. In a well-architected system, there should not be any high-bandwidth capability for presenting forged MACs and determining if they are valid. In particular, the number of authentication failures at the verifying party should be limited. If a large number of such attempts are detected, the session key in use should be dropped and the event recorded in an audit log. 🚨
Let us reemphasize: a forging probability of 1/2^60 does not mean that there is an attack that runs in 2^60 time. To the contrary, as long as the block cipher in use is not broken, there is no such attack for UMAC. Instead, a 1/2^60 forging probability means that if an attacker could make N forgery attempts, then the attacker would have no more than N/2^60 probability of getting one or more of them right. 💀
It should be pointed out that once an attempted forgery is successful, it is possible, in principle, that subsequent messages under this key may be easily forged. This is important to understand when gauging the severity of a successful forgery, even though no such attack on UMAC is known to date.
In conclusion, 64-bit tags seem appropriate for many security architectures and commercial applications. If one wants a more conservative option, at a cost of about 50% or 100% more computation, UMAC can produce 96- or 128-bit tags that have basic collision probabilities of at most 1/2^90 and 1/2^120. If one needs less security, with the benefit of about 50% less computation, UMAC can produce 32-bit tags. In this case, under the same assumptions as before, one cannot forge a message with probability better than 1/2^30. Special care must be taken when using 32-bit tags because a 1/2^30 forgery probability is considered fairly high. Still, high-speed, low-security authentication can be applied usefully on low-value data or rapidly-changing key environments. 🌸
6.3. Nonce Considerations ✨
UMAC needs a nonce that's somewhere between 1 and BLOCKLEN bytes long 💅. Every nonce in one authentication session must be equal in length. For secure operation, no nonce value should ever be repeated during the life of a single UMAC session key 🔐. If a nonce gets reused, there's no guarantee the message is authentic, so messages with a repeated nonce should be considered inauthentic 🚫.
Now, if two parties are messaging each other over a duplex channel, you can use a different key for each direction 🦋. But if you're using the same key in both directions, then all nonces have to be distinct, no exceptions 😭. One fun way to do that is for one party to use even nonces while the other uses odd ones 🧚. The receiving party must verify that the sender is using a nonce of the correct form 👑.
This spec doesn't say how nonce values get created, updated, or shared between the tag-maker and the tag-checker, so here are some possibilities 🍓:
- The nonce is an 8-byte unsigned number, Counter. It starts at zero, goes up by one after each authentication tag is generated, and is always sent along with the message and the authentication tag. An error occurs at the sender if someone tries to authenticate more than 2^64 messages within a session.
- The nonce is a BLOCKLEN-byte unsigned number, Counter. It starts at zero and goes up by one after each authentication tag is generated. The Counter isn't explicitly sent between sender and receiver. Instead, they're assumed to talk over a reliable transport, and each one keeps its own counter so they both know the current nonce value 🌸.
- The nonce is a BLOCKLEN-byte random value. (Because repeats in a random n-bit value are expected at around 2^(n/2) trials, the number of messages sent in a session using n-bit nonces should not be allowed to approach 2^(n/2). Yikes 💀.)
We really want to emphasize that the nonce doesn't need to be kept secret 🤫.
When UMAC is used inside a higher-level protocol, there might already be a field, like a sequence number, that can be repurposed to be the nonce UMAC needs [5]. The application will then say how to build the nonce from that already-existing field ✨.
6.4. Replay Attacks 🔁
A replay attack is when an attacker repeats a message, its nonce, and its authentication tag 😤. In lots of applications, replay attacks can be super damaging, so they must be prevented. In UMAC, this normally gets handled at the receiver, who checks that no nonce value is used twice 🙅♀️. On a reliable connection, when the nonce is a counter, that's trivial. On an unreliable connection with a counter nonce, you'd normally cache some window of recent nonces 🪟. Out-of-order delivery that goes beyond what that window allows will end up rejecting perfectly valid authentication tags 😩.
Again, it's up to the receiver to decide when a given (message, nonce, tag) triple gets deemed authentic 👑. Sure, the tag should be valid for the message and nonce, as UMAC determines, but the message can still be deemed inauthentic if the nonce turns out to be a replay 🙈.
6.5. Tag-Prefix Verification 🎀
UMAC's definition makes it possible to implement tag-prefix verification. For example, a receiver might verify only the 32-bit prefix of a 64-bit tag if its computational load is high. Or a receiver might reject a 64-bit tag right away if its 32-bit prefix is wrong 🤏. Honestly though, these practices are potentially dangerous, and they can lead to attacks that drop the security of the session down to the length of the verified prefix 💀. A UMAC key (or session) must have an associated and immutable tag length, and the implementation should not leak information that would reveal whether a given proper prefix of a tag is valid or invalid 🔒.
6.6. Side-Channel Attacks 🕵️♀️
Side-channel attacks try to break a cryptographic system by exploiting how it's implemented 🔍. One common one is to measure how long the system takes to respond and then pull out info about the conditions met by the data being processed. These are called "timing attacks". Timing and other side-channel attacks are outside this document's scope, but we have to warn you: there are places in the UMAC algorithm where timing info could be unintentionally leaked 😱. In particular, the POLY algorithm (Section 5.3.2) tests whether a value m is out of a particular range, and the algorithm behaves differently depending on the result. If you want to avoid timing attacks, take care to equalize the computation time in both cases ⏱️. Timing attacks can also happen for more subtle reasons, including caching effects 🫠.
7. Acknowledgements 🫶
David McGrew and Scott Fluhrer, of Cisco Systems, played a big role in improving UMAC by pushing us to pay more attention to the performance of short messages 🙌. Thanks go to Jim Schaad and to everyone who shared helpful suggestions on the CFRG mailing list to improve this document during RFC consideration 💜. Black, Krovetz, and Rogaway got support for this work under NSF awards 0208842, 0240000, and 9624560, plus a gift from Cisco Systems 🎁.
Appendix. Test Vectors 🧪
Here are some sample UMAC outputs over a collection of input values, using AES with 16-byte keys ✨. Let
K = "abcdefghijklmnop" // A 16-byte UMAC key
N = "bcdefghi" // An 8-byte nonceThe tags generated by UMAC using key K and nonce N are:
Message 32-bit Tag 64-bit Tag 96-bit Tag
------- ---------- ---------- ----------
<empty> 113145FB 6E155FAD26900BE1 32FEDB100C79AD58F07FF764
'a' * 3 3B91D102 44B5CB542F220104 185E4FE905CBA7BD85E4C2DC
'a' * 2^10 599B350B 26BF2F5D60118BD9 7A54ABE04AF82D60FB298C3C
'a' * 2^15 58DCF532 27F8EF643B0D118D 7B136BD911E4B734286EF2BE
'a' * 2^20 DB6364D1 A4477E87E9F55853 F8ACFA3AC31CFEEA047F7B11
'a' * 2^25 5109A660 2E2DBC36860A0A5F 72C6388BACE3ACE6FBF062D9
'abc' * 1 ABF3A3A0 D4D7B9F6BD4FBFCF 883C3D4B97A61976FFCF2323
'abc' * 500 ABEB3C8B D4CF26DDEFD5C01A 8824A260C53C66A36C9260A6The first column lists a small sample of messages, which are strings of repeated ASCII 'a' bytes or 'abc' strings 📝. The remaining columns give, in hexadecimal, the tags generated when UMAC is called with the matching message, nonce N, and key K 🔢.
When you use key K and produce a 64-bit tag, these relevant keys get generated 🗝️:
Iteration 1 Iteration 2
----------- -----------
NH (Section 5.2.2)
K_1 ACD79B4F C6DFECA2
K_2 6EDA0D0E 964A710D
K_3 1625B603 AD7EDE4D
K_4 84F9FC93 A1D3935E
K_5 C6DFECA2 62EC8672
...
K_256 0BF0F56C 744C294F
L2-HASH (Section 5.3.1)
k64 0094B8DD0137BEF8 01036F4D000E7E72
L3-HASH (Section 5.4.1)
k_5 056533C3A8 0504BF4D4E
k_6 07591E062E 0126E922FF
k_7 0C2D30F89D 030C0399E2
k_8 046786437C 04C1CB8FED
K2 2E79F461 A74C03AA(Note that k_1 ... k_4 aren't listed in this example because they get multiplied by zero in L3-HASH 🙃.)
When generating a 64-bit tag on input "'abc' * 500", these intermediate results are produced 🧁:
Iteration 1
-----------
L1-HASH E6096F94EDC45CAC1BEDCD0E7FDAA906
L2-HASH 0000000000000000A6C537D7986FA4AA
L3-HASH 05F86309
Iteration 2
-----------
L1-HASH 2665EAD321CFAE79C82F3B90261641E5
L2-HASH 00000000000000001D79EAF247B394BF
L3-HASH DF9AD858Concatenating the two L3-HASH results gives a final UHASH result of 05F86309DF9AD858. The pad generated for nonce N is D13745D4304F1842, which, when XOR'ed with the L3-HASH result, yields a tag of D4CF26DDEFD5C01A 🎉.
References 📚
Normative References
[1] FIPS-197, "Advanced Encryption Standard (AES)", National Institute of Standards and Technology, 2001.
Informative References
[2] D. Bernstein, "Stronger security bounds for permutations", unpublished manuscript, 2005. This work refines "Stronger security bounds for Wegman-Carter-Shoup authenticators", Advances in Cryptology - EUROCRYPT 2005, LNCS vol. 3494, pp. 164-180, Springer-Verlag, 2005.
[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, Springer-Verlag, 1999.
[4] L. Carter and M. Wegman, "Universal classes of hash functions", Journal of Computer and System Sciences, 18 (1979), pp. 143-154.
[5] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303, December 2005.
[6] T. Krovetz, "Software-optimized universal hashing and message authentication", UMI Dissertation Services, 2000.
[7] 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.
Authors' Addresses 🖊️
John Black
Department of Computer Science
University of Colorado
Boulder, CO 80309
USA
EMail: jrblack@cs.colorado.eduShai Halevi
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
USA
EMail: shaih@alum.mit.eduAlejandro Hevia
Department of Computer Science
University of Chile
Santiago 837-0459
CHILE
EMail: ahevia@dcc.uchile.clHugo Krawczyk
IBM Research
19 Skyline Dr
Hawthorne, NY 10533
USA
EMail: hugo@ee.technion.ac.ilTed Krovetz (Editor)
Department of Computer Science
California State University
Sacramento, CA 95819
USA
EMail: tdk@acm.orgPhillip Rogaway
Department of Computer Science
University of California
Davis, CA 95616
USA
and
Department of Computer Science
Faculty of Science
Chiang Mai University
Chiang Mai 50200
THAILAND
EMail: rogaway@cs.ucdavis.eduFull Copyright Statement ⚖️
Copyright (C) The Internet Society (2006).
This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property ✨
okay so bestie, first things first 💅 the IETF is NOT taking a side on whether any Intellectual Property Rights (or other rights) might be claimed over the tech in this doc 🙈 It also isn't saying whether any license under those rights might or might not be available, and it isn't claiming it has done any independent effort to find those rights either 🫶 If you want the rules on rights in RFC docs, go check BCP 78 and BCP 79 📚
Lowkey the paperwork is still a whole thing 🎀 Copies of IPR disclosures sent to the IETF Secretariat, any assurances of licenses that are going to be made available, or the result of an attempt to get a general license or permission for implementers or users to use those proprietary rights can all be found on the IETF on-line IPR repository at http://www.ietf.org/ipr 🦋
And the IETF literally invites anyone interested to speak up 📣 If you know about any copyrights, patents, patent applications, or other proprietary rights that might cover tech you'd need to implement this standard, tell the IETF at ietf-ipr@ietf.org 💜 It's giving "see something, say something" 👑
Acknowledgement 🌸
Funding for the RFC Editor function comes from the IETF Administrative Support Activity (IASA) 🧚 Someone has to keep the lights on for the RFC Editor, and the IASA is that someone 💖
📦 where this page comes from
- ietf: rfc4418 2006-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms