Galois/Counter Mode

In cryptography, Galois/Counter Mode (GCM)¹ is a mode of operation for symmetric-key cryptographic block ciphers that provides both encryption and message authentication in a single pass. It belongs to the class of authenticated encryption with associated data (AEAD) algorithms. In practice, GCM gives a recipient two guarantees at once: the message content was hidden from anyone without the key, and the data arrived exactly as sent. Encrypted web connections, Wi-Fi security, and virtual private networks rely on this property through protocols such as TLS and WPA3. GCM was designed by David A. McGrew and John Viega, first published in 2005,² and standardized by NIST in Special Publication 800-38D in November 2007.³ Galois Message Authentication Code (GMAC) is an authentication-only variant that can form an incremental message authentication code.

GCM uses a 128-bit block cipher (commonly AES) run in counter mode for encryption, and uses arithmetic in the Galois field GF(2¹²⁸) to compute the authentication tag, hence its name. Because successive ciphertext blocks are produced independently, encryption and decryption can be fully parallelized, in contrast to chaining modes such as cipher block chaining (CBC). GCM was designed to be patent-free.⁴

GCM is widely deployed in network security protocols. It is used in TLS 1.2¹ and TLS 1.3,⁵ IEEE 802.1AE (MACsec) Ethernet security, IPsec,⁶ SSH,⁷ and other protocols. AES-GCM is included in the NSA's Commercial National Security Algorithm Suite.

Security depends on choosing a unique initialization vector (IV) for every encryption under the same key; reuse of an initialization vector can expose the encryption key and allow forgery. For any given key and initialization vector, GCM is limited to encrypting 2³⁹−256 bits of plaintext. The authentication strength of the mode decreases with shorter tag lengths; NIST SP 800-38D recommends tag lengths of at least 96 bits.

GCM operates as a counter mode block cipher to produce ciphertext.²

For authentication, the ciphertext blocks are treated as coefficients of a polynomial evaluated at a key-dependent point H using finite field arithmetic. The result is then encrypted to produce an authentication tag that can be used to verify the integrity of both the ciphertext and the associated data.²

GCM combines the counter mode of encryption with the Galois mode of authentication. The GF(2¹²⁸) field used is defined by the polynomial²

${\displaystyle x^{128}+x^{7}+x^{2}+x+1}$.

Because the GF(2¹²⁸) multiplications used for authentication can be computed independently, the GHASH function admits parallel implementation, in contrast to chaining modes such as CBC.²

The authentication tag is constructed by feeding blocks of data into the GHASH function and encrypting the result. This GHASH function is defined by

${\displaystyle \operatorname {GHASH} (H,A,C)=X_{m+n+1}}$,

where ${\displaystyle H=E_{k}(0^{128})}$ is the hash key, a string of 128 zero bits encrypted using the block cipher; ${\displaystyle A}$ is data that is only authenticated (not encrypted); ${\displaystyle C}$ is the ciphertext; ${\displaystyle m}$ is the number of 128-bit blocks in ${\displaystyle A}$ (rounded up); ${\displaystyle n}$ is the number of 128-bit blocks in ${\displaystyle C}$ (rounded up); and the variable ${\displaystyle X_{i}}$ for ${\displaystyle i=0,\dots ,m+n+1}$ is defined below.²

First, the authenticated text and the ciphertext are separately zero-padded to multiples of 128 bits and combined into a single message, ${\displaystyle S_{i}}$, defined as

${\displaystyle S_{i}={\begin{cases}A_{i}&{\text{for }}i=1,\ldots ,m-1\\A_{m}^{*}\parallel 0^{128-v}&{\text{for }}i=m\\C_{i-m}&{\text{for }}i=m+1,\ldots ,m+n-1\\C_{n}^{*}\parallel 0^{128-u}&{\text{for }}i=m+n\\\operatorname {len} (A)\parallel \operatorname {len} (C)&{\text{for }}i=m+n+1\end{cases}}}$,

where ${\displaystyle \operatorname {len} (A)}$ and ${\displaystyle \operatorname {len} (C)}$ are the 64-bit representations of the bit lengths of ${\displaystyle A}$ and ${\displaystyle C}$, respectively; ${\displaystyle v=\operatorname {len} (A){\bmod {1}}28}$ is the bit length of the final block of ${\displaystyle A}$; ${\displaystyle u=\operatorname {len} (C){\bmod {1}}28}$ is the bit length of the final block of ${\displaystyle C}$; and ${\displaystyle \parallel }$ denotes concatenation of bit strings.²

Then, ${\displaystyle X_{i}}$ is defined as:

${\displaystyle X_{i}=\sum _{j=1}^{i}S_{j}\cdot H^{i-j+1}={\begin{cases}0&{\text{for }}i=0\\\left(X_{i-1}\oplus S_{i}\right)\cdot H&{\text{for }}i=1,\ldots ,m+n+1\end{cases}}}$.²

The second form is an efficient iterative algorithm (each ${\displaystyle X_{i}}$ depends on ${\displaystyle X_{i-1}}$) produced by applying Horner's method to the first. Only the final ${\displaystyle X_{m+n+1}}$ is output.²

If it is necessary to parallelize the hash computation, this can be done by interleaving ${\displaystyle k}$ times:

${\displaystyle {\begin{aligned}X'_{i}&={\begin{cases}0&{\text{for }}i\leq 0\\\left(X'_{i-k}\oplus S_{i}\right)\cdot H^{k}&{\text{for }}i=1,\ldots ,m+n+1-k\end{cases}}\\[6pt]X_{i}&=\sum _{j=1}^{k}\left(X'_{i+j-2k}\oplus S_{i+j-k}\right)\cdot H^{k-j+1}\end{aligned}}}$.²

If the length of the IV is not 96, the GHASH function is used to calculate Counter 0:

${\displaystyle {\text{Counter 0}}={\begin{cases}IV\parallel 0^{31}\parallel 1&{\text{for }}\operatorname {len} (IV)=96\\\operatorname {GHASH} \!\left(IV\parallel 0^{s}\parallel 0^{64}\parallel \operatorname {len} _{64}(IV)\right){\text{ with }}s=128-\operatorname {len} (IV){\bmod {1}}28&{\text{otherwise}}\end{cases}}}$.³

GCM was designed by Viega and McGrew as a development based on earlier counter-mode authenticated encryption designs, including Carter–Wegman counter mode (CWC mode).⁸ McGrew and Viega first published GCM in 2005.²

In November 2007, NIST released Special Publication 800-38D Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, making GCM and GMAC official standards.³

GCM mode is specified for IEEE 802.1AE (MACsec) Ethernet security, WPA3-Enterprise Wi-Fi, IEEE 802.11ad (WiGig), ANSI (INCITS) Fibre Channel Security Protocols (FC-SP), and IEEE P1619.1 tape storage. It is also used in IETF IPsec,⁶⁹ SSH,⁷ TLS 1.2,¹¹⁰ and TLS 1.3.⁵ AES-GCM is included in the NSA Suite B Cryptography and its 2018 successor Commercial National Security Algorithm (CNSA) suite.¹¹

Among VPN implementations, the SoftEther VPN server and client support AES-GCM,¹² as does OpenVPN since version 2.4, where AES-GCM cipher suites are available via configuration and cipher negotiation.¹³

GCM requires one block cipher operation and one 128-bit multiplication in the Galois field for each block (128 bits) of encrypted and authenticated data. The block cipher operations are pipelined or parallelized; the multiplication operations are pipelined and can be parallelized (either by parallelizing the actual operation, by adapting Horner's method per the original NIST submission, or both).²

Intel has added the PCLMULQDQ instruction, which supports carry-less multiplication used in GCM implementations.¹⁴ In 2011, SPARC added the XMULX and XMULXHI instructions, which also perform 64 × 64-bit carry-less multiplication.¹⁵ In 2015, SPARC added the XMPMUL instruction, which performs XOR multiplication of much larger values, up to 2048 × 2048-bit input values, producing a 4096-bit result.¹⁶ These instructions enable fast multiplication over GF(2ⁿ) and can be used with any field representation.

Performance results are published for GCM on a number of platforms. Käsper and Schwabe described a "Faster and Timing-Attack Resistant AES-GCM"¹⁷ that achieves 10.68 cycles per byte of AES-GCM authenticated encryption on 64-bit Intel processors. Gueron and Kounavis report 3.54 cycles per byte for the same algorithm when using Intel's AES-NI and PCLMULQDQ instructions on Westmere processors.¹⁴ Shay Gueron and Vlad Krasnov achieved 2.47 cycles per byte on third-generation Intel Core processors.¹⁸ Appropriate patches were prepared for the OpenSSL and NSS libraries.¹⁸

When both authentication and encryption need to be performed on a message, interleaving those operations using instruction-level parallelism can increase performance. This process is called function stitching,¹⁹ and while in principle it can be applied to any combination of cryptographic algorithms, GCM supports parallel computation which can simplify optimization on some processors. Manley and Gregg²⁰ show that function stitching can be applied to GCM with good results; they present a program generator that takes an annotated C version of a cryptographic algorithm and generates code that runs well on the target processor.

GCM has been criticized in the embedded world (for example, by Silicon Labs) because parallel processing is not well-suited to cryptographic hardware engines that process one block at a time, reducing throughput on performance-constrained devices.²¹ Specialized hardware accelerators for ChaCha20-Poly1305 are less complex compared to AES accelerators.²²

GCM is proven to be secure in the concrete security model.²³ It is secure when it is used with a block cipher that is indistinguishable from a random permutation; however, security depends on choosing a unique initialization vector for every encryption performed with the same key (see stream cipher attack). For any given key and initialization vector value, GCM is limited to encrypting 2³⁹−256 bits of plain text (64 GiB). NIST Special Publication 800-38D³ includes guidelines for initialization vector choice and limits the number of possible initialization vector values for a single key. As security assurance degrades with more data processed under the same key, the total number of blocks of plaintext and AD protected during the lifetime of a single key should be limited to 2⁶⁴.³

The authentication strength depends on the length of the authentication tag, as with all symmetric message authentication codes. Using shorter authentication tags with GCM is discouraged. The bit-length of the tag, denoted t, is a security parameter. In general, t may be any one of the following five values: 128, 120, 112, 104, or 96. For certain applications, t may be 64 or 32, but the use of these two tag lengths constrains the length of the input data and the lifetime of the key. Appendix C in NIST SP 800-38D provides guidance for these constraints (for example, if t = 32 and the maximal packet size is 2¹⁰ bytes, the authentication decryption function should be invoked no more than 2¹¹ times; if t = 64 and the maximal packet size is 2¹⁵ bytes, the authentication decryption function should be invoked no more than 2³² times).³

Like any message authentication code, if the adversary chooses a t-bit tag at random, it is expected to be correct for given data with probability 2^−t. With GCM, however, an adversary can increase their likelihood of success for a message of n blocks by a factor of n, achieving a success probability of approximately n⋅2^−t. The complement, 1 − n⋅2^−t, bounds the adversary's failure probability for arbitrarily large t. GCM is not well-suited for use with short tag lengths or long messages.²⁴

Ferguson and Saarinen independently described optimal attacks against GCM authentication that meet the lower bound on its security. Ferguson showed that, if n denotes the total number of blocks in the encoding (the input to the GHASH function), then a targeted ciphertext forgery succeeds with probability approximately n⋅2^−t. If t is shorter than 128, each successful forgery increases the probability of subsequent forgeries and leaks information about the hash subkey H; eventually H may be fully recovered, at which point authentication assurance is lost entirely.²⁴

Independent of this attack, an adversary may systematically guess many different tags for a given input to authenticated decryption. For this reason, implementations should monitor and, if necessary, limit the number of unsuccessful verification attempts for each key.³

Saarinen described GCM as having weak keys,²⁵ offering analysis into how polynomial hash-based authentication works. More precisely, this work describes a way to forge a GCM message given a valid GCM message, succeeding with probability approximately n⋅2⁻¹²⁸ for messages that are n × 128 bits long. This does not improve on prior known attacks; the success probability in observation 1 of this paper matches that of lemma 2 from the INDOCRYPT 2004 analysis (setting w = 128 and l = n × 128).²⁵ Saarinen also described a GCM variant, Sophie Germain Counter Mode (SGCM), based on Sophie Germain primes.