Galois/Counter Mode
GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.
By contrast, the cipher block chaining (CBC) mode of operation incurs pipeline stalls that hamper its efficiency and performance.
The ciphertext blocks are considered coefficients of a polynomial which is then evaluated at a key-dependent point H, using finite field arithmetic.
The GF(2128) field used is defined by the polynomial The authentication tag is constructed by feeding blocks of data into the GHASH function and encrypting the result.
[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.
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.
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.
For any given key and initialization vector value, GCM is limited to encrypting 239 − 256 bits of plain text (64 GiB).
Appendix C in NIST SP 800-38D provides guidance for these constraints (for example, if t = 32 and the maximal packet size is 210 bytes, the authentication decryption function should be invoked no more than 211 times; if t = 64 and the maximal packet size is 215 bytes, the authentication decryption function should be invoked no more than 232 times).
Like with 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 measure 2−t.
With GCM, however, an adversary can increase their likelihood of success by choosing tags with n words – the total length of the ciphertext plus any additional authenticated data (AAD) – with probability measure 2−t by a factor of n. Although, one must bear in mind that these optimal tags are still dominated by the algorithm's survival measure 1 − n⋅2−t for arbitrarily large t. Moreover, GCM is neither well-suited for use with very short tag-lengths nor very long messages.
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.
[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.
However, this work does not show a more effective attack than was previously known; 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).
Encryption: A series of 128-bit counters is encrypted using the block cipher E with key K; this can occur in parallel. The results are combined using bitwise XOR with 128-bit plaintext blocks, producing a series of ciphertext blocks.
Authentication: The Additional Data and these ciphertext blocks are combined using multiplication with a key-dependent constant H in the Galois field GF(2 128 ) to produce the authentication tag.