Carryless Multiplication in Galois Counter Mode GCM

Carryless multiplication is the foundational operation that enables high-throughput, hardware-accelerated authenticated encryption in Galois/Counter Mode (GCM). By eliminating the standard carry propagation found in traditional integer arithmetic, carryless multiplication allows systems to efficiently evaluate polynomial products in the binary Galois field \(\text{GF}(2^{128})\). This operation directly accelerates the GHASH authentication function inside GCM, ensuring both high performance and constant-time execution against timing side-channel attacks.

The Role of GHASH in Galois/Counter Mode

Galois/Counter Mode (GCM) combines the counter mode (CTR) for confidentiality with the GHASH universal hash function for authentication. While the underlying block cipher (typically AES) encrypts the plaintext, GHASH computes an authentication tag over the ciphertext and any associated data.

GHASH processes data in 128-bit blocks by treating each block as an element of the Galois field \(\text{GF}(2^{128})\). For every incoming block, GHASH adds the block to the current state using bitwise XOR and multiplies the result by a fixed hash subkey \(H\) within \(\text{GF}(2^{128})\). Because this field multiplication occurs once for every 128 bits of data, it is the primary computational bottleneck of the authentication process.

How Carryless Multiplication Works

In standard binary integer multiplication, when two bits are multiplied and added, any overflow triggers a “carry” to the next most significant bit position. This carry-chain creates a sequential dependency that slows down execution in hardware and software.

In contrast, carryless multiplication operates on polynomials over the binary field \(\text{GF}(2)\), where coefficients can only be 0 or 1:

Addition is XOR: Adding two bits produces their XOR sum (\(1 + 1 = 0\), \(1 + 0 = 1\), \(0 + 0 = 0\)) with no carry generated.
Multiplication is Shift-and-XOR: The multiplication of two polynomials is equivalent to shifting the multiplicand for every set bit in the multiplier and combining the results using bitwise XOR.

Accelerating \(\text{GF}(2^{128})\) Field Arithmetic

Multiplication within \(\text{GF}(2^{128})\) requires two steps: a 128-bit carryless multiplication yielding a 255-bit intermediate polynomial, followed by modular reduction using a predefined irreducible polynomial, specifically \(f(x) = x^{128} + x^7 + x^2 + x + 1\).

Carryless multiplication accelerates this pipeline in two primary ways:

Hardware Parallelism: Because there are no carries to wait for, hardware units can compute partial products in parallel using straightforward XOR trees. Modern processor architectures provide dedicated carryless multiplication instructions (such as PCLMULQDQ on x86/x64 and PMULL on ARM) that execute a 64-bit carryless multiplication in just a few clock cycles.
Fast Modular Reduction: The reduction step itself can be rewritten as a series of shifts and carryless multiplications using the specific structure of the irreducible polynomial. This avoids expensive division operations entirely.

Elimination of Timing Side-Channels

Before hardware-level carryless multiplication instructions were widely available, implementations relied on precomputed lookup tables (such as 4-bit or 8-bit table strategies) to speed up field multiplication. These software lookups often introduced variable memory access patterns vulnerable to cache-timing attacks.

Hardware-based carryless multiplication executes in fixed, predictable cycles regardless of the input data. This guarantees constant-time computation, securing the authentication tag generation against side-channel analysis while maintaining multi-gigabit-per-second encryption throughput.