Galois/Counter Mode - Security

Security

GCM has been proven secure in the concrete security model. It is secure when it is used with a block cipher mode of operation 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). NIST Special Publication 800-38D includes guidelines for initialization vector selection.

The authentication strength depends on the length of the authentication tag, as with all symmetric message authentication codes. However, the use of 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 210 bytes, then the authentication decryption function should be invoked no more than 211 times; if t = 64 and the maximal packet size is 215 bytes, then the authentication decryption function should be invoked no more than 232 times).

As 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 2−t. With GCM, however, an adversary can choose tags that increase this probability, proportional to the total length of the ciphertext and additional authenticated data (AAD). Consequently, GCM is not well-suited for use with very short tag lengths or very long messages.

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 n2−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.

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 accepted as 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 weak keys This work gives some valuable insights into how polynomial hash based authentication works. More precisely, this work describes a particular way of forging a GCM message, given a valid GCM message, which works with probability of about n/2^128 for messages that are n*128 bits long. 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). Saarinen also described a GCM variant Sophie Germain Counter Mode (SGCM), continuing the GCM tradition of including a mathematician in the name of the mode.