The GMAC Algorithm

The GMAC Algorithm

Introduction

GMAC is a message authentication code built from AES. It is the authentication half of AES-GCM, the authenticated encryption mode that protects most of the web. If you use GCM and give it no plaintext, you have GMAC. The data you want to authenticate goes in as the “additional authenticated data”, and the output is just the tag.

GMAC is a polynomial MAC, like Poly1305. The message is cut into blocks, and the blocks are the coefficients of a polynomial. A secret value H is plugged in, the arithmetic uses the field GF(2^128), and the result is masked with the AES encryption of a counter block. GMAC is fast, because modern CPUs have instructions for the carry-less multiplication that this field needs. It also needs a nonce, called the IV, that must never repeat under one key.

Table of Contents

• History and Standards
• The Field GF(2^128)
• GHASH
• The Counter Block and the Tag
• When the IV Repeats
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

David McGrew and John Viega designed the Galois/Counter Mode, and they described it in a 2004 paper. NIST standardized it in 2007 as SP 800-38D, which defines both GCM and its authentication-only form, GMAC. RFC 4543 describes the use of GMAC in IPsec, where it authenticates packets that need no encryption.

GMAC has the same strengths and risks as GCM. It works with any AES key size, and its cost per block is one field multiplication. It has no padding problems, because the length of the message is part of the input. On the other side, its security depends entirely on the IV being unique.

The Field GF(2^128)

The numbers in GMAC are 128-bit blocks, and they live in the finite field GF(2^128). In this field, addition is XOR. Multiplication is the multiplication of polynomials with binary coefficients, followed by a reduction by the fixed polynomial x^128 + x^7 + x^2 + x + 1.

GCM uses an unusual bit order. A block is read from the left. The leftmost bit is the coefficient of x^0, and the rightmost bit is the coefficient of x^127. So the block 80 00 ... 00 is the number 1, and the block 40 00 ... 00 is the polynomial x. In this order, multiplying by x is a shift of the whole block to the right by one bit. If a one bit falls off the right end, the result is XORed with the constant e1000000000000000000000000000000, which stands for the reduction polynomial.

For example, multiplying H = b83b533708bf535d0aa6e52980d53b78 by x shifts it to 5c1da99b845fa9ae85537294c06a9dbc. The lowest bit of H is zero, so nothing is reduced. For the block 8a6ff5aca561c0d865805055eb728397, the lowest bit is one. Its shift is 4537fad652b0e06c32c0282af5b941cb, and after the reduction, the product with x is a437fad652b0e06c32c0282af5b941cb. A full multiplication does this 128 times, once for every bit of the first factor, and it adds up the shifted copies of the second factor.

GHASH

GHASH hashes a string of 16-byte blocks with a secret value H, which is the AES encryption of an all-zero block:

H = AES(K, 0)
Y(0) = 0
Y(i) = ( Y(i-1) xor X(i) ) * H

All operations are in GF(2^128). The result Y after the last block is the hash. This is Horner’s method for a polynomial in H. Each block is added into the state, and the sum is multiplied by H.

In GMAC, the input to GHASH is the message, padded with zeros to a multiple of 16 bytes, followed by one more block that holds two 64-bit numbers. The first is the length of the message in bits, and the second is the length of the ciphertext in bits, which is zero in GMAC. Including the length keeps messages of different lengths apart.

last block = len(A) as 64 bits  ||  len(C) as 64 bits

Here A is the authenticated data, which is the whole message in GMAC, and C is the ciphertext, which is empty. Both lengths count bits, not bytes. A 43-byte message therefore has the length 344.

The Counter Block and the Tag

The GHASH result is masked with the encryption of a counter block J0, which comes from the IV:

• If the IV has 12 bytes, which is the recommended size, then J0 is the IV followed by the 32-bit number 1.
• For any other length, the IV is itself hashed with GHASH, with a length block at the end, and the result is J0.

The tag is computed like this:

tag = GHASH( message || length block )  xor  AES( K, J0 )

The tag may be cut to fewer bytes, but 16 bytes is the normal choice. The mask AES(K, J0) is different for every IV. Without it, the tag would be a plain polynomial in H that an attacker could solve.

When the IV Repeats

If the same IV is used twice under one key, the mask AES(K, J0) is the same for both tags, and it cancels out when you XOR them. What remains is the difference of two GHASH values, and that is a polynomial in H with known coefficients.

In general, a message of n blocks gives a polynomial of degree n + 1 in H. The attacker knows every coefficient, because the coefficients are the blocks of the two messages. The XOR of the two tags is the value of this polynomial at the secret H. Finding H means finding the roots of a polynomial over GF(2^128). This is a standard task, and the true H is among the roots. A few more tag pairs under the same IV remove the false candidates. In the simplest case, it is easy to solve by hand.

Take two messages of exactly one block each, A1 and A2. With the length block L, GHASH of a message is (A * H xor L) * H, which is A * H^2 xor L * H. So the XOR of two tags is (A1 xor A2) * H^2, because the L * H parts are the same. Dividing by A1 xor A2 gives H^2, and squaring is a reversible operation in this field, so H follows by taking the square root, which is raising to the power 2^127.

Once H is known, the attacker can compute the GHASH of any message. Given one valid tag for an IV, the attacker can forge a valid tag for any other message under the same IV, by adding the difference of the two GHASH values. This is the “forbidden attack”, first described by Antoine Joux in 2006. In 2016, researchers found real HTTPS servers that repeated GCM nonces, and they showed that this allows forgery.

The worked example below runs this attack with real numbers. The Python section has a short script that you can run yourself.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose AES-128 or AES-256, enter a key and an IV in hex, and type a message of up to 127 bytes. Then click Compute tag. The log shows the hash key H, the counter block J0, the mask, and then every GHASH step: the block, the state XORed with the block, and the product with H. The last block holds the lengths. An IV that is not 12 bytes long gets its own GHASH rows. The last row shows the tag. When it ends, the page tells you how many tag bits change when one bit of your message is flipped.

A Worked Example

This uses a 128-bit AES key and a 12-byte IV that are often used as examples for GCM. The numbers below are not a published test vector, so you cannot look them up. Two checks make them trustworthy. Every intermediate value is printed, so you can follow each step. The final tags also match the OpenSSL that ships with Node.js, and the Python section shows how to run that check. For a published reference, GCM test case 1 uses an all-zero key and an all-zero IV. The hash key is 66e94bd4ef8a2c3b884cfa59ca342b2e, and the tag of the empty message is 58e2fccefa7e3061367f1d57a4e7455a. The code in this guide reproduces both. The key is feffe9928665731c6d6a8f9467308308 and the IV is cafebabefacedbaddecaf888. The message is the sentence The quick brown fox jumps over the lazy dog, which has 43 bytes.

The hash key. Encrypting an all-zero block gives H = AES(K, 0) = b83b533708bf535d0aa6e52980d53b78.

The counter block. The IV has 12 bytes, so J0 = cafebabefacedbaddecaf88800000001. Its encryption is the mask AES(K, J0) = 3247184b3c4f69a44dbcd22887bbb418.

The blocks. The message is padded to 48 bytes, which makes three blocks, and a fourth block holds the lengths. The message has 344 bits, so the length block is 00000000000001580000000000000000, where 0x158 is 344. The four blocks are:

54686520717569636b2062726f776e20
666f78206a756d7073206f7665722074
6865206c617a7920646f670000000000
00000000000001580000000000000000

GHASH. The state starts at zero. After block 1, the sum is the block itself, 54686520717569636b2062726f776e20, and the product with H is ddb9beb23a532932b97e22e6552fabd9. For block 2, the sum is bbd6c69250264442ca5e4d90305d8bad, and the new state is 9312269d6eca61c71fd43524f095eb68. For block 3, the sum is fb7706f10fb018e77bbb5224f095eb68, and the state is c968341c88e3d912b206a9f5d2e6e330. The length block gives the sum c968341c88e3d84ab206a9f5d2e6e330, and the final state is:

7f238828ed2127565cf65d8174d5e1a5

The tag. XORing the GHASH value with the mask gives the tag:

4d649063d16e4ef2114a8fa9f36e55bd

Changing the last letter, g to t, gives the tag 106ee7b8c79da9aaa4acd57d6de62ace, which differs in 74 of the 128 bits. The empty message has a GHASH value of zero, so its tag is the mask, 3247184b3c4f69a44dbcd22887bbb418.

A repeated IV. Suppose the same key and the same IV authenticate the two one-block messages transfer 100 EUR and transfer 900 EUR. The tags are 1b51f3c96ddd75624deab1c10c231e98 and 136e1d7fa171897a3604f73e56e94884. Their XOR is 083feeb6ccacfc187bee46ff5aca561c. Dividing by the XOR of the two messages, as numbers in the field, gives H^2 = 8a6ff5aca561c0d865805055eb728397. The square root is b83b533708bf535d0aa6e52980d53b78, which is exactly H. The attacker never saw the key. With H, the attacker forges the tag 80c63354d204a520ceeb1023f8786a0b for the new message transfer 999 EUR under the same IV, and the real GMAC function accepts it.

Python Implementation

This is a complete GMAC. It supports every IV length and every tag length from 4 to 16 bytes. It uses the same small aes_core.py file as the AES-CCM guide, which has its source. The function gf_mul follows the multiplication algorithm in the NIST standard. The function ghash_blocks returns the GHASH state after every block, so you can compare it with the worked example.

# gmac.py
#
# GMAC, the authentication-only mode of AES-GCM (NIST SP 800-38D). It is GCM
# with an empty plaintext: the message to authenticate is the "additional
# authenticated data". The tag is GHASH of the message, which is a polynomial
# in a secret value H evaluated in the field GF(2^128), masked with the AES
# encryption of a counter block that comes from a nonce, the IV.
# The IV must NEVER repeat under one key. This file uses the AES in aes_core.py.

from aes_core import AES

# the field polynomial x^128 + x^7 + x^2 + x + 1, in GCM's reflected bit order
R = 0xE1 << 120


def gf_mul(x, y):
    """Multiply two 128-bit blocks in GF(2^128).

    GCM numbers its bits from the left: bit 0, the coefficient of x^0, is the
    most significant bit of the Python integer. So the loop reads x from the
    top bit down, and multiplying v by x is a shift to the right.
    """
    z, v = 0, y
    for i in range(127, -1, -1):
        if (x >> i) & 1:
            z ^= v
        v = (v >> 1) ^ R if v & 1 else v >> 1
    return z


def pad16(data):
    return data + bytes(-len(data) % 16)


def ghash_blocks(h, data):
    """Return the GHASH state after each 16-byte block of data (a multiple of 16 bytes)."""
    y = 0
    states = []
    for i in range(0, len(data), 16):
        y = gf_mul(y ^ int.from_bytes(data[i:i + 16], "big"), h)
        states.append(y)
    return states


def ghash(h, data):
    states = ghash_blocks(h, data)
    return states[-1] if states else 0


def counter_block(h, iv):
    """J0: for a 12-byte IV it is the IV followed by the counter 1. Other lengths are hashed with GHASH."""
    if len(iv) == 12:
        return iv + b"\x00\x00\x00\x01"
    return ghash(h, pad16(iv) + bytes(8) + (8 * len(iv)).to_bytes(8, "big")).to_bytes(16, "big")


def length_block(aad):
    """The last block of GHASH: the bit length of the message and the bit length of the (empty) ciphertext."""
    return (8 * len(aad)).to_bytes(8, "big") + bytes(8)


def gmac(key, iv, message, tag_len=16):
    if not iv:
        raise ValueError("the IV must not be empty")
    if not 4 <= tag_len <= 16:
        raise ValueError("a GMAC tag is 4 to 16 bytes")
    aes = AES(key)
    h = int.from_bytes(aes.encrypt_block(bytes(16)), "big")
    j0 = counter_block(h, iv)
    s = ghash(h, pad16(message) + length_block(message))
    mask = int.from_bytes(aes.encrypt_block(j0), "big")
    return (s ^ mask).to_bytes(16, "big")[:tag_len]


def verify(key, iv, message, tag):
    """Check a tag in constant time."""
    expected = gmac(key, iv, message, len(tag))
    difference = 0
    for a, b in zip(expected, tag):
        difference |= a ^ b
    return difference == 0


if __name__ == "__main__":
    key = bytes.fromhex("feffe9928665731c6d6a8f9467308308")
    iv = bytes.fromhex("cafebabefacedbaddecaf888")
    # the 20 bytes of additional data from GCM test case 4 (not the pangram of the worked example)
    message =bytes.fromhex("feedfacedeadbeeffeedfacedeadbeefabaddad2")
    tag = gmac(key, iv, message)
    print("GMAC tag: " + tag.hex())
    print("Verified: " + str(verify(key, iv, message, tag)))
    print("Changed:  " + str(verify(key, iv, message + b"!", tag)))

Running it produces this output:

GMAC tag: 346434fd51d5cd0c5887ec63e39b907a
Verified: True
Changed:  False

The demo at the bottom does not use the pangram of the worked example. Its message is the 20 bytes of additional data from GCM test case 4. That published case also encrypts a plaintext, so its tag 5bc94fbc3221a5db94fae95ae7121a47 is different from the GMAC tag above. The function verify compares tags without stopping at the first difference. The rest of the code is not constant-time.

Run the Attack Yourself

Save this script next to gmac.py and aes_core.py. The attacker part uses only two messages and two tags. It never touches the key.

# gmac_attack.py
#
# The "forbidden attack" on a repeated IV, with one-block messages.
# Save this file next to gmac.py and aes_core.py. The attacker below
# uses only the two messages and the two tags. The key is used by the
# "victim" function and by the final check, never by the attacker.

from gmac import gmac, gf_mul

KEY = bytes.fromhex("feffe9928665731c6d6a8f9467308308")
IV = bytes.fromhex("cafebabefacedbaddecaf888")
ONE = 1 << 127  # the block 80 00 ... 00 is the number 1 in GCM's bit order


def victim(message):
    return int.from_bytes(gmac(KEY, IV, message), "big")


def power(a, e):
    result = ONE
    while e:
        if e & 1:
            result = gf_mul(result, a)
        a = gf_mul(a, a)
        e >>= 1
    return result


def number(block):
    return int.from_bytes(block, "big")


m1, m2, m3 = b"transfer 100 EUR", b"transfer 900 EUR", b"transfer 999 EUR"
t1, t2 = victim(m1), victim(m2)  # two tags that the attacker has seen

# (t1 xor t2) = (m1 xor m2) * H^2, so divide and take the square root
inverse = power(number(m1) ^ number(m2), (1 << 128) - 2)
h_squared = gf_mul(t1 ^ t2, inverse)
h = power(h_squared, 1 << 127)
print("H^2 = %032x" % h_squared)
print("H   = %032x" % h)

# the tag of a new message: t1 xor (m1 xor m3) * H^2
forged = t1 ^ gf_mul(number(m1) ^ number(m3), h_squared)
print("forged tag = %032x" % forged)
print("accepted   = " + str(forged == victim(m3)))

Running it produces this output:

H^2 = 8a6ff5aca561c0d865805055eb728397
H   = b83b533708bf535d0aa6e52980d53b78
forged tag = 80c63354d204a520ceeb1023f8786a0b
accepted   = True

Check the Tags with OpenSSL

Node.js has OpenSSL built in. This script computes the tags of the pangram and of the changed message with a different implementation.

const crypto = require("crypto");
const key = Buffer.from("feffe9928665731c6d6a8f9467308308", "hex");
const iv = Buffer.from("cafebabefacedbaddecaf888", "hex");
for (const text of ["The quick brown fox jumps over the lazy dog", "The quick brown fox jumps over the lazy dot"]) {
    const cipher = crypto.createCipheriv("aes-128-gcm", key, iv);
    cipher.setAAD(Buffer.from(text));
    cipher.final();
    console.log(cipher.getAuthTag().toString("hex"));
}

It prints 4d649063d16e4ef2114a8fa9f36e55bd and 106ee7b8c79da9aaa4acd57d6de62ace, which are the two tags from the worked example.

I checked this code against several independent sources before writing it up. The hash key and the tag of the empty message match test case 1 of the GCM specification. The tags match every valid case with an empty message in Project Wycheproof’s AES-GCM tests, which cover all three key sizes and IVs of many lengths. The code also agrees with the OpenSSL that ships inside Node.js on 400 random cases, with AES-128, AES-192, and AES-256, IVs of 1 to 60 bytes, messages up to 200 bytes, and tags of 4 to 16 bytes. The attack in the worked example recovers the true hash key, and the forged tag passes the real function.

Security Status

With a unique IV, GMAC is secure if AES is a secure block cipher. An attacker who guesses a tag for a message of n blocks succeeds with a probability of about n / 2^128 for a full 16-byte tag. This is a very low number.

The danger lies in the rules around it. The first is the IV. A repeated IV reveals H, as shown above, and then every tag under the key can be forged. A random 96-bit IV is only safe for a limited number of messages, because of the birthday bound. NIST limits the number of random IVs per key to 2^32. The second is the tag length. Shorter tags are weaker. NIST allows 128, 120, 112, 104, and 96 bits in general, and it restricts 64-bit and 32-bit tags to special cases. The third is side channels, because a slow software multiplication can leak H. Real implementations use the carry-less multiplication instructions, PCLMULQDQ on x86 and PMULL on ARM, which are fast and constant-time. The Python code in this guide is not.

Common Implementation Mistakes

• An empty IV. GCM does not allow a zero-length IV. Wycheproof marks such cases invalid, and OpenSSL rejects them. The code above rejects an empty IV too.
• An IV that repeats across modes. The rule covers every use of the key. If one key serves both GCM and GMAC, no IV may appear twice in the two together.
• Very short tags. A 4-byte tag lets an attacker succeed after about 2^32 guesses. Keep 12 bytes or more.
• A slow multiplication. Table lookups and bit loops can leak H through timing. Use a library that has constant-time or hardware field arithmetic.
• A silent tag cut. The receiver must know the expected tag length. Never accept whatever length the sender offers.

The Standard Is Being Revised

NIST decided in March 2024 to revise SP 800-38D. The announced changes include removing support for tags shorter than 96 bits, clarifying how GCM IVs are built in TLS 1.3, and updating the IV guidance. NIST says it will ask for public comments when the draft appears. The rules in this guide may change once the revision is published.

If a nonce cannot be guaranteed, use a different MAC. HMAC and CMAC do not need a nonce. AES-GCM-SIV gives authenticated encryption that survives a repeated nonce.

FAQ

What is the difference between GMAC and GCM?

GCM encrypts data and authenticates it, while GMAC only authenticates. A GMAC is a GCM call with an empty plaintext, and all of the data goes into the authenticated, unencrypted part.

Why does GMAC need a nonce, when HMAC does not?

HMAC is a pseudorandom function of its input, so the same input gives the same tag, and there is no weakness in that. A polynomial MAC would leak its key if the same mask were used twice. The IV makes a fresh mask for each message. A GMAC tag therefore changes even for an identical message when the IV changes.

What happens when I reuse an IV?

The attacker can compute the hash key H, as the worked example shows, and then forge tags for any message under that key. This is why the IV is the first thing to check in a GCM deployment.

Why does GMAC use a strange bit order?

It comes from the design. GCM treats the leftmost bit as the lowest power of x, which makes the multiplication a right shift and fits some hardware instructions. The standard has used it since the beginning, so every implementation does the same.

Can I use GMAC instead of HMAC?

You can, when you can guarantee unique IVs and when you have fast field multiplication, such as in IPsec hardware. HMAC is simpler to use correctly, because it has no nonce to manage.

References

1. Dworkin, M. “Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC.” NIST Special Publication 800-38D, 2007.

2. McGrew, D. and Viega, J. “The Security and Performance of the Galois/Counter Mode (GCM) of Operation.” INDOCRYPT 2004, Lecture Notes in Computer Science 3348, Springer.

3. McGrew, D. and Viega, J. “The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH.” RFC 4543, 2006. Available at: https://www.rfc-editor.org/rfc/rfc4543

4. Joux, A. “Authentication Failures in NIST Version of GCM.” Comments submitted to NIST, 2006.

5. Boeck, H., Zauner, A., Devlin, S., Somorovsky, J., and Jovanovic, P. “Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS.” USENIX WOOT 2016.

6. Google. “Project Wycheproof: AES-GCM test vectors.” Available at: https://github.com/C2SP/wycheproof