Galois/Counter Mode

In cryptography, Galois/Counter Mode (GCM)^[1] is a mode of operation for symmetric-key cryptographic block ciphers which is widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.^[2]

The GCM algorithm provides both data authenticity (integrity) and confidentiality and belongs to the class of authenticated encryption with associated data (AEAD) methods. This means that as input it takes a key K, some plaintext P, and some associated data AD; it then encrypts the plaintext using the key to produce ciphertext C, and computes an authentication tag T from the ciphertext and the associated data (which remains unencrypted). A recipient with knowledge of K, upon reception of AD, C and T, can decrypt the ciphertext to recover the plaintext P and can check the tag T to ensure that neither ciphertext nor associated data were tampered with.

GCM uses a block cipher with block size 128 bits (commonly

Galois Message Authentication Code (GMAC) is an authentication-only variant of the GCM which can form an incremental message authentication code. Both GCM and GMAC can accept initialization vectors of arbitrary length.

Different block cipher modes of operation can have significantly different performance and efficiency characteristics, even when used with the same block cipher. GCM can take full advantage of

Mathematical basis

GCM combines the well-known

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

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 H = E_k(0¹²⁸) is the hash key, a string of 128 zero bits encrypted using the block cipher, A is data which is only authenticated (not encrypted), C is the ciphertext, m is the number of 128-bit blocks in A (rounded up), n is the number of 128-bit blocks in C (rounded up), and the variable X_i for i = 0, ..., m + n + 1 is defined below.^[3]

First, the authenticated text and the cipher text are separately zero-padded to multiples of 128 bits and combined into a single message S_i:

${\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 len(A) and len(C) are the 64-bit representations of the bit lengths of A and C, respectively, v = len(A) mod 128 is the bit length of the final block of A, u = len(C) mod 128 is the bit length of the final block of C, and ${\displaystyle \parallel }$ denotes concatenation of bit strings.

Then 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 X_i depends on X_i−1) produced by applying Horner's method to the first. Only the final X_m+n+1 remains an output.

If it is necessary to parallelize the hash computation, this can be done by interleaving 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 \mathrm {Counter0} ={\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)\mod 128&{\text{otherwise}}\end{cases}}}$

GCM was designed by John Viega and David A. McGrew to be an improvement to Carter–Wegman counter mode (CWC mode).^[4]

In November 2007,

Intel has added the PCLMULQDQ instruction, highlighting its use for GCM.^[14] 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.

Impressive performance results are published for GCM on a number of platforms. Käsper and Schwabe described a "Faster and Timing-Attack Resistant AES-GCM"^[15] that achieves 10.68 cycles per byte AES-GCM authenticated encryption on 64-bit Intel processors. Dai et al. report 3.5 cycles per byte for the same algorithm when using Intel's AES-NI and PCLMULQDQ instructions. Shay Gueron and Vlad Krasnov achieved 2.47 cycles per byte on the 3rd generation Intel processors. Appropriate patches were prepared for the OpenSSL and NSS libraries.^[16]

When both authentication and encryption need to be performed on a message, a software implementation can achieve speed gains by overlapping the execution of those operations. Performance is increased by exploiting instruction-level parallelism by interleaving operations. This process is called function stitching,^[17] and while in principle it can be applied to any combination of cryptographic algorithms, GCM is especially suitable. Manley and Gregg^[18] show the ease of optimizing when using function stitching with GCM. 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 the parallel processing is not suited for performant use of cryptographic hardware engines. As a result, GCM reduces the performance of encryption for some of the most performance-sensitive devices.^[19] Specialized hardware accelerators for ChaCha20-Poly1305 are less complex compared to AES accelerators.^[20]

Patents

According to the authors' statement, GCM is unencumbered by patents.^[21]

Security

GCM is proven secure in the

Ferguson and Saarinen independently described how an attacker can perform optimal attacks against GCM authentication, which 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 there is a method of constructing a targeted ciphertext forgery that is expected to succeed with a probability of approximately n⋅2^−t. If the tag length t is shorter than 128, then each successful forgery in this attack increases the probability that subsequent targeted forgeries will succeed, and leaks information about the hash subkey, H. Eventually, H may be compromised entirely and the authentication assurance is completely lost.[23]

Independent of this attack, an adversary may attempt to systematically guess many different tags for a given input to authenticated decryption and thereby increase the probability that one (or more) of them, eventually, will be considered valid. For this reason, the system or protocol that implements GCM should monitor and, if necessary, limit the number of unsuccessful verification attempts for each key.

Saarinen described GCM

See also

• Authenticated encryption
• Block cipher mode of operation
• AES-GCM-SIV

References