The UMAC Algorithm

The UMAC Algorithm

Introduction

UMAC is a message authentication code designed for speed. It is the standard example of the Wegman-Carter approach, in which a fast, simple hash function squeezes the message into a short string, and then a secret pad hides that string. The tag is the XOR of the two.

In UMAC, the hash is UHASH, a keyed function made only of additions and multiplications of integers. It uses no block cipher at all on the message. The only place where a cipher appears is at the start, where AES makes the keys and the pad. That is why UMAC can process long messages at a rate of about one CPU cycle per byte, as the RFC reports for a Pentium 4 with SSE2 instructions.

The speed comes with a rule. UMAC needs a nonce, a value that changes with every tag. If a nonce repeats under one key, there is no guarantee of authenticity. This guide covers the construction, the three layers of the hash, and all four tag lengths. The FAQ answers what happens when a nonce repeats and which tag length to choose.

Table of Contents

• History and Standards
• The Wegman-Carter Idea
• Keys from AES
• Layer 1, NH
• Layer 2, POLY
• Layer 3, the Inner Product
• The Pad and the Tag
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz, and Phillip Rogaway introduced UMAC at CRYPTO 1999, in a paper titled “UMAC: Fast and Secure Message Authentication”. The IETF published it as RFC 4418 in March 2006, edited by Ted Krovetz. The RFC is informational. It says that the authors make no intellectual property claims on the ideas in the design.

OpenSSH offers UMAC as a MAC for SSH connections, and some libraries, such as Nettle, include it. The Wegman-Carter idea behind it is much older. Mark Wegman and Larry Carter described it in 1981, and UMAC is a fast, practical version of it.

The Wegman-Carter Idea

A universal hash function is a keyed function with a guarantee about collisions. For two different messages, a randomly chosen key makes them collide with a very small probability. A universal hash is not a secure hash like SHA-256. It does not resist an attacker who sees its output. But if its output is hidden by a one-time pad, then no attacker can say anything about the tag:

Tag = H_K1(M)  xor  F_K2(Nonce)

Here H is the universal hash, F is a pseudorandom function, and K1 and K2 are secret keys. The nonce changes with each message, so the pad F(Nonce) is new every time. The guarantee on collisions then turns into a guarantee on forgery. In UMAC, H is UHASH, and F is AES. All keys come from one 16-byte master key.

Keys from AES

UMAC needs a lot of key material. The layer 1 key alone has 1024 bytes. The KDF, the key-derivation function, makes all of it with AES in counter mode. The input to AES is an 8-byte index, which tells what the key is for, and an 8-byte counter:

KDF(K, index, n):  AES(K, index || 1) || AES(K, index || 2) || ...   cut to n bytes

The indexes are 0 for the pad, 1 for the layer 1 key, 2 for the layer 2 key, 3 for the first layer 3 key, and 4 for the second layer 3 key. For the example key abcdefghijklmnop, the first block of the layer 1 key comes from the input 00000000000000010000000000000001, and its first four 32-bit words are acd79b4f, 6eda0d0e, 1625b603, and 84f9fc93.

Layer 1, NH

Layer 1 is where almost all of the work is done, so it has to be fast. The message is cut into 1024-byte chunks, and the last chunk is padded with zeros to a multiple of 32 bytes. Each chunk is read as 32-bit words, little-endian, which suits most processors. Then the function NH hashes the words in groups of eight:

Y = Y + (m1 + k1) * (m5 + k5)
Y = Y + (m2 + k2) * (m6 + k6)
Y = Y + (m3 + k3) * (m7 + k7)
Y = Y + (m4 + k4) * (m8 + k8)

Each message word m is added to a key word k modulo 2^32. Then pairs that are four words apart are multiplied, and the 64-bit products are added modulo 2^64. This is the whole inner loop. Each 32-bit multiplication that gives a 64-bit result is something that processors do very quickly, and the vector instructions on modern CPUs can do several at once.

At the end of a chunk, the number of bits in the chunk is added to Y. This makes sure that a message and the same message with zero bytes added give different results. The output of layer 1 has 8 bytes for each chunk, so it is up to 128 times shorter than the message.

Layer 2, POLY

If the message has at most 1024 bytes, layer 1 produces a single 8-byte value, and layer 2 is skipped. For longer messages, layer 2 shrinks the list of 8-byte values to one 16-byte value. It treats the list as the coefficients of a polynomial and evaluates it at a secret point k, modulo the prime 2^64 - 59:

y = 1
for each 64-bit word m:
    y = (k * y + m) mod (2^64 - 59)

Words that are too close to the prime are split in two before they are used, so that every value fed to the polynomial is in range. The secret k is masked, so that some of its bits are zero. For messages larger than 16 MB, a second polynomial modulo 2^128 - 159 is used on the rest. Layer 2 is a polynomial hash, the same idea as in Poly1305 and GMAC.

Layer 3, the Inner Product

The last layer hashes 16 bytes to 4 bytes. It cuts the 16 bytes into eight pieces of 16 bits, m1 to m8, and multiplies each by a key number k1 to k8 that is reduced modulo 2^36 - 5. The sum of the products is reduced modulo the same prime and cut to 32 bits, and then it is XORed with a 4-byte key:

y = ( m1*k1 + m2*k2 + ... + m8*k8 ) mod (2^36 - 5)
output = (y mod 2^32) xor K2

The XOR with K2 adds one more secret value to the result. Because layer 1 gives 8 bytes, and layers 2 and 3 take 16 bytes, a short message puts 8 zero bytes in front of its layer 1 output.

The Pad and the Tag

The pad comes from the PDF, the pad-derivation function. It encrypts the nonce with AES, using a key derived with index 0. For a 4-byte or 8-byte tag, the last bits of the nonce choose which part of the AES output to use. That way, neighbouring nonces share one AES call: with 8-byte tags, nonces 2n and 2n + 1 use the two halves of one block. For 12 or 16 bytes, the pad is the first part of the AES output. The nonce is public, but it must never repeat under one key.

A tag of 4, 8, 12, or 16 bytes needs 1, 2, 3, or 4 iterations of the three layers. Each iteration uses its own key from the KDF output, and gives 4 bytes of UHASH. The layer 1 keys of the iterations overlap: iteration i uses the bytes from 16(i - 1) to 16(i - 1) + 1024. The pieces are joined, and the tag is:

Tag = UHASH(K, M) xor PDF(K, Nonce)

The four variants are called UMAC-32, UMAC-64, UMAC-96, and UMAC-128. For the same inputs, the 96-bit tag is the first 12 bytes of the 128-bit tag, because both use the same pad block and the same first three iterations. The 32-bit and 64-bit tags are not prefixes of the longer ones, because their pads depend on the last bits of the nonce.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose a tag length, enter an AES key and a nonce in hex, and type a message of up to 127 bytes. Then click Compute tag. The log shows the key derivation, the padding and byte swap of the message, and for each iteration the NH output, the layer 2 step, and the layer 3 output. After that come the UHASH, the pad, and the tag. Messages of up to 127 bytes use a single chunk, so layer 2 is skipped. The defaults are the key, the nonce, and the message abc from the RFC test vectors. When it ends, the page tells you how many tag bits change when one bit of your message is flipped.

A Worked Example

This follows the RFC test vector with the key abcdefghijklmnop, the nonce bcdefghi, the message abc, and a 64-bit tag. A 64-bit tag takes two iterations.

The RFC prints the key words, the layer 3 keys, the pad, and the tags of this example, and it prints the layer outputs for the long message at the end. The sums, products, and layer 3 arithmetic for the three-byte message below are not in the RFC. They are computed by the code in this guide, which gives the RFC’s tag.

The keys. For the layer 1 key, the KDF with index 1 gives the 32-bit words acd79b4f, 6eda0d0e, 1625b603, 84f9fc93, c6dfeca2, and so on up to word 256, which is 0bf0f56c. The second iteration starts 16 bytes later, so its first word is c6dfeca2, the same as word 5 of the first iteration. Its last word is 744c294f.

The message. The three bytes 61 62 63 are padded with zeros to 32 bytes, and each 4-byte word is byte-reversed. The padded message is 6162630000000000000000000000000000000000000000000000000000000000, and after reversing it is 0063626100000000000000000000000000000000000000000000000000000000. The first word is m1 = 00636261, and the other seven words are zero.

NH, iteration 1. Since m5 to m8 are zero, each product is a message word plus a key word, times a key word. The four sums m + k are ad3afdb0, 6eda0d0e, 1625b603, and 84f9fc93, and the partners are c6dfeca2, 964a710d, ad7ede4d, and a1d3935e. The 64-bit products are 869326b91d82c960, 4113ffa1dae1d7b6, 0f0275caf9a858e7, and 540f1e6ffffc26fa. They add up to 2ab8ba95f20920f7. The message has 24 bits, so adding 24 gives the layer 1 output 2ab8ba95f209210f.

NH, iteration 2. With the next key window, the sums are c7434f03, 964a710d, ad7ede4d, and a1d3935e, and the NH value is 3541f5fba4244daa. After adding the length, the layer 1 output is 3541f5fba4244dc2.

Layer 3, iteration 1. The 16-byte input is 8 zero bytes and the layer 1 output, 00000000000000002ab8ba95f209210f. The first four pieces are zero, so only the last four count. They are 2ab8 ba95 f209 210f, and the matching key numbers are 056533c3a8 07591e062e 0c2d30f89d 046786437c. The sum of products is 1256422b934d4f. Modulo 2^36 - 5 it is 22b990843, and its low 32 bits are 2b990843. XOR with the key 2e79f461 gives 05e0fc22.

Layer 3, iteration 2. The pieces are 3541 f5fb a424 4dc2, the keys are 0504bf4d4e 0126e922ff 030c0399e2 04c1cb8fed, the sum modulo the prime is 52a4ca427, and the low 32 bits are 2a4ca427. XOR with a74c03aa gives 8d00a78d. Joined, the two outputs are the UHASH:

05e0fc228d00a78d

The pad. The last byte of the nonce is i, which is 0x69. For an 8-byte tag, its lowest bit is the index, which is 1. Clearing that bit gives the nonce 6263646566676868, which is padded to the block 62636465666768680000000000000000. The pad key from the KDF with index 0 is 78dc489d32a9c8a132bb4b6832c5359e. AES gives the block 817b05c9ae135f82d13745d4304f1842. The index selects the second half, so the pad is d13745d4304f1842.

The tag. The XOR of the UHASH and the pad is:

d4d7b9f6bd4fbfcf

This is the value in the RFC. The same inputs give abf3a3a0 as a 32-bit tag, 883c3d4b97a61976ffcf2323 as a 96-bit tag, and 883c3d4b97a61976ffcf232308cba5a5 as a 128-bit tag. The 96-bit tag is the first 12 bytes of the 128-bit tag. Changing the last letter of the message from c to d gives 7c72bb1d648f000b, which differs in 31 of the 64 bits. The empty message gives 6e155fad26900be1.

A long message. The RFC also lists the intermediate values for abc repeated 500 times, which has 1500 bytes. It is cut into a chunk of 1024 bytes and a chunk of 476 bytes, so layer 1 gives 16 bytes. For iteration 1 they are e6096f94edc45cac1bedcd0e7fdaa906. Layer 2 turns them into 0000000000000000a6c537d7986fa4aa, and layer 3 gives 05f86309. For iteration 2, the layer 1 output is 2665ead321cfae79c82f3b90261641e5, layer 2 gives 00000000000000001d79eaf247b394bf, and layer 3 gives df9ad858. The UHASH is 05f86309df9ad858, and with the same pad, the tag is d4cf26ddefd5c01a.

Python Implementation

This is a complete UMAC with all four tag lengths. It uses the same small aes_core.py file as the AES-CCM guide, which has its source. Each function matches a function of the RFC, so you can compare them one by one.

# umac.py
#
# UMAC (RFC 4418), a message authentication code made for speed. A universal
# hash, UHASH, squeezes the message down to 4, 8, 12 or 16 bytes in three layers:
# NH, a polynomial hash, and an inner product. UHASH uses a secret key, but not a
# cipher. The tag is the hash XOR a pad that AES makes from a nonce, so the nonce
# must NEVER repeat under one key. This file uses the AES in aes_core.py.

from aes_core import AES

P36 = 2**36 - 5
P64 = 2**64 - 59
P128 = 2**128 - 159


def kdf(key, index, numbytes):
    """Key derivation: AES in counter mode, with the index and a block counter as the plaintext."""
    aes = AES(key)
    out = b""
    for i in range(1, -(-numbytes // 16) + 1):
        out += aes.encrypt_block(index.to_bytes(8, "big") + i.to_bytes(8, "big"))
    return out[:numbytes]


def pdf(key, nonce, taglen):
    """The pad: AES of the nonce under a derived key. Short tags share one AES block between neighbouring nonces."""
    if not 1 <= len(nonce) <= 16:
        raise ValueError("a UMAC nonce is 1 to 16 bytes")
    index = 0
    if taglen in (4, 8):
        index = int.from_bytes(nonce, "big") % (16 // taglen)
        nonce = (int.from_bytes(nonce, "big") ^ index).to_bytes(len(nonce), "big")
    block = nonce + bytes(16 - len(nonce))
    t = AES(kdf(key, 0, 16)).encrypt_block(block)
    return t[index * taglen:(index + 1) * taglen] if taglen in (4, 8) else t[:taglen]


def endian_swap(s):
    """Reverse the bytes of every 4-byte word. UMAC reads its message little-endian."""
    return b"".join(s[i:i + 4][::-1] for i in range(0, len(s), 4))


def nh(key, message):
    """Layer 1 core: pairs of 32-bit words, each plus a key word, multiplied and summed modulo 2^64."""
    n = len(message) // 4
    m = [int.from_bytes(message[4 * i:4 * i + 4], "big") for i in range(n)]
    k = [int.from_bytes(key[4 * i:4 * i + 4], "big") for i in range(n)]
    y = 0
    for i in range(0, n, 8):
        for j in range(4):
            y = (y + ((m[i + j] + k[i + j]) % 2**32) * ((m[i + j + 4] + k[i + j + 4]) % 2**32)) % 2**64
    return y


def zeropad(s, n):
    return s + bytes(max(-len(s) % n, n if not s else 0))


def l1_hash(key, message):
    """Layer 1: cut the message into 1024-byte chunks, NH each chunk, and add its length in bits."""
    t = max(-(-len(message) // 1024), 1)
    chunks = [message[1024 * i:1024 * (i + 1)] for i in range(t)]
    out = b""
    for i, chunk in enumerate(chunks):
        bits = 8 * len(chunk)
        if i == t - 1:
            chunk = zeropad(chunk, 32)
        out += ((nh(key, endian_swap(chunk)) + bits) % 2**64).to_bytes(8, "big")
    return out


def poly(wordbits, maxwordrange, k, message):
    """A polynomial hash modulo the largest prime below 2^wordbits. Words that are too big are split in two."""
    wordbytes = wordbits // 8
    p = P64 if wordbits == 64 else P128
    offset = 2**wordbits - p
    marker = p - 1
    y = 1
    for i in range(0, len(message), wordbytes):
        m = int.from_bytes(message[i:i + wordbytes], "big")
        if m >= maxwordrange:
            y = (k * y + marker) % p
            y = (k * y + (m - offset)) % p
        else:
            y = (k * y + m) % p
    return y


def l2_hash(key, message):
    """Layer 2: hash the layer 1 output with POLY, with a second prime for very long messages."""
    k64 = int.from_bytes(key[:8], "big") & 0x01FFFFFF01FFFFFF
    k128 = int.from_bytes(key[8:24], "big") & 0x01FFFFFF01FFFFFF01FFFFFF01FFFFFF
    if len(message) <= 2**17:
        y = poly(64, 2**64 - 2**32, k64, message)
    else:
        first, rest = message[:2**17], message[2**17:]
        rest = zeropad(rest + b"\x80", 16)
        y = poly(64, 2**64 - 2**32, k64, first)
        y = poly(128, 2**128 - 2**96, k128, y.to_bytes(16, "big") + rest)
    return y.to_bytes(16, "big")


def l3_hash(key1, key2, message):
    """Layer 3: an inner product of eight 16-bit pieces with eight key numbers, modulo 2^36 - 5, cut to 32 bits."""
    y = 0
    for i in range(8):
        m = int.from_bytes(message[2 * i:2 * i + 2], "big")
        k = int.from_bytes(key1[8 * i:8 * i + 8], "big") % P36
        y += m * k
    y = (y % P36) % 2**32
    return bytes(a ^ b for a, b in zip(y.to_bytes(4, "big"), key2))


def uhash(key, message, taglen):
    iters = taglen // 4
    l1key = kdf(key, 1, 1024 + (iters - 1) * 16)
    l2key = kdf(key, 2, iters * 24)
    l3key1 = kdf(key, 3, iters * 64)
    l3key2 = kdf(key, 4, iters * 4)
    out = b""
    for i in range(iters):
        a = l1_hash(l1key[16 * i:16 * i + 1024], message)
        b = bytes(8) + a if len(message) <= 1024 else l2_hash(l2key[24 * i:24 * (i + 1)], a)
        out += l3_hash(l3key1[64 * i:64 * (i + 1)], l3key2[4 * i:4 * (i + 1)], b)
    return out


def umac(key, message, nonce, taglen=8):
    """UMAC-32, UMAC-64, UMAC-96 or UMAC-128, for a tag of 4, 8, 12 or 16 bytes."""
    if taglen not in (4, 8, 12, 16):
        raise ValueError("a UMAC tag is 4, 8, 12 or 16 bytes")
    if len(key) != 16:
        raise ValueError("a UMAC key is 16 bytes")
    return bytes(a ^ b for a, b in zip(uhash(key, message, taglen), pdf(key, nonce, taglen)))


if __name__ == "__main__":
    key = b"abcdefghijklmnop"
    nonce = b"bcdefghi"
    for taglen in (4, 8, 12, 16):
        print("UMAC-%d('abc' * 3) = %s" % (8 * taglen, umac(key, b"abc" * 3, nonce, taglen).hex()))

Running it produces this output:

UMAC-32('abc' * 3) = 7ec516db
UMAC-64('abc' * 3) = 01e10c8d7b4ef990
UMAC-96('abc' * 3) = 5d0a883051a75f2942052ff5
UMAC-128('abc' * 3) = 5d0a883051a75f2942052ff5c8022bc4

I checked this code against several independent sources before writing it up. It reproduces the RFC 4418 table of tags, including messages of 1 MB and 32 MB. It also reproduces every intermediate value that the RFC prints for the 64-bit tag. These are the NH keys, the layer 2 and layer 3 keys, the outputs of all three layers for both iterations, the pad, and the tag. The 32 MB line of the RFC is wrong. The author published a correction, and the corrected values match this code. It also matches 38 vectors from the test suite of Nettle, an independent library. They include all four tag lengths, nonces of 1 to 16 bytes, and 13 messages longer than 1 MB. Those use the 128-bit polynomial of layer 2. The code is slow, because it runs in pure Python, and the full test takes about eight minutes.

Security Status

UMAC has a rare property: the strength of UHASH is a mathematical fact, proven without any assumption about hard problems. The RFC states that the keys and pads would have to be truly random for this proof. Then an attacker could not forge a tag with a probability higher than 1/2^30, 1/2^60, 1/2^90, or 1/2^120 for tags of 32, 64, 96, or 128 bits, even with unlimited computing power. After N attempts, the odds rise at most to N times that. In a real implementation with AES, these numbers rise by a small amount related to the security of AES.

The RFC adds some points. A forging probability of 1/2^60 does not mean an attack of 2^60 steps. It means that an attacker needs about that many tries, each tried against the verifier. So a system should limit failed verifications and drop the key if too many fail. The RFC says that 64-bit tags seem appropriate for many uses, that 96-bit and 128-bit tags are more conservative, and that 32-bit tags need special care, because 1/2^30 is a fairly high probability.

The most important rule is the nonce. No nonce may repeat within the life of a key, and a message that comes with a repeated nonce should be treated as inauthentic. The nonce does not need to be secret. A counter is the usual choice. If both parties use one key, they must use different nonces, for example even for one party and odd for the other. The RFC also warns about side channels, because the POLY step must run in constant time. UHASH is not a cryptographic hash function. It is not a replacement for SHA-256, and it is secure only when its output is masked by the pad.

FAQ

Why is UMAC so fast?

Its main loop is NH, which uses only 32-bit additions and multiplications that give 64-bit results. That is something processors do very well. The slow parts, AES and the polynomials, only touch a tiny fraction of the data, because layer 1 shrinks the message by up to 128 times.

What is the difference between UMAC and HMAC?

HMAC is a general MAC that works with one key for any number of messages, and it needs no nonce. UMAC is a Wegman-Carter MAC with a nonce, and it can be much faster on long messages. Its guarantees are proven for a limited number of messages and with unique nonces.

What happens if a nonce repeats?

The pad is the same for two messages, so the XOR of the two tags equals the XOR of the two UHASH values. The attacker learns that, and the RFC gives no guarantee of authenticity. This is the same type of problem as a repeated IV in GMAC.

Which tag length should I use?

The RFC says that 64 bits seem appropriate for many systems. Use 96 or 128 bits for a more conservative choice, at a cost of about 50% or 100% more computation. Use 32 bits only for low-value data, because the forging probability of 1/2^30 is fairly high.

References

1. Krovetz, T., Ed. “UMAC: Message Authentication Code using Universal Hashing.” RFC 4418, 2006. Available at: https://www.rfc-editor.org/rfc/rfc4418

2. Black, J., Halevi, S., Krawczyk, H., Krovetz, T., and Rogaway, P. “UMAC: Fast and Secure Message Authentication.” CRYPTO 1999, Lecture Notes in Computer Science 1666, Springer.

3. Wegman, M. and Carter, L. “New Hash Functions and Their Use in Authentication and Set Equality.” Journal of Computer and System Sciences 22, 1981.

4. Krovetz, T. “RFC 4418 Errata.” Available at: http://fastcrypto.org/umac/rfc4418.errata.txt

5. Nettle project. “UMAC test suite.” Available at: https://git.lysator.liu.se/nettle/nettle