What are the constraints on using GCM with a tag size of 96 and 128 bits? Say we want to use AES (or any other secure 128 bit block cipher) with GCM and a tag size of 96 or 128 bits. I'm assuming an AES key size of 128 bits and an IV size of 96 bits (the default).



NIST SP 800-SP 38D, Appendix C: "Requirements and Guidelines for Using Short Tags" specifies the amount of AAD and plaintext together with the number of invocations for 32 and 64 bit short tags, but not for the larger tag sizes. NIST specifies these properties using a table with the following columns set off to each other:


Maximum Combined Length of the Ciphertext and AAD  In a Single Packet (bytes)
Maximum Invocations of the  Authenticated Decryption Function


Here are the constraints for a 64 bit tag size:





Furthermore, the paper "The Galois/Counter Mode of Operation (GCM)" contains the following equation right at the end (chapter 7: "Security"):


  The results of this analysis show that GCM is secure whenever the block cipher is indistinguishable from random and the condition $q^2l^22^{−142} + q^2l^32^{−147} \ll 1$ is met, where $q$ is the number of invocations of the authentication encryption operation and $l$ is the maximum number of bits in the ﬁelds $P$, $A$, and $IV$.




The Wikipedia page on GCM also has a lot of information and references (but not this information, obviously).



I'm not sure if any subsequent analysis has put a dent into the numbers of NIST or the paper though.
I don't understand where the formula $q^2 \ell^2 2^{-142} + q^2 \ell^3 2^{-147}$ came from.  The power of $\ell$ seems too high; the fractions $2^{-142}$ and $2^{-147}$ seem awfully small; the citation is to an unpublished draft of the original security analysis that is no longer available; the final draft does not seem to support it.

First, let's assume you use sequential 96-bit nonces.  (The story is much more complicated if you have to worry about nonce collisions, and the original authors got it wrong.)  The usual approach to security analysis comes by composing two standard theorems:


Forgery probability of a Carter–Wegman universal hashing authenticator: after $f$ forgeries of messages up to $\ell$ blocks long with an authenticator tag of length $\tau$, the forgery probability is bounded by $$\frac{f \ell}{2^\tau}.$$

The forgery probability bound grows linearly with the number and length of forgery attempts, and drops exponentially in the tag length.

This is the main reason why it is more dangerous to truncate tags of universal hashing MACs like GHASH and Poly1305 than to truncate, say, CBC-MAC tags or HMAC tags, for which the analogous term $f/2^\tau$, not $f\ell/2^\tau$.
Distinguisher advantage from substituting a uniform random $b$-bit permutation for a uniform random $b$-bit function, used to derive the one-time authenticator key for each nonce (PRF/PRP switching lemma): if a random algorithm $A$ (say a forger) making $q$ queries has probability $\Pr[A(f)]$ of success on an oracle for a uniform random function $f$, then its success probability on an oracle for a uniform random permutation $\pi$ is bounded by $$\Pr[A(\pi)] \leq \Pr[A(f)] + \frac{q(q - 1)}{2\cdot 2^b} &lt; \Pr[A(f)] + \frac{q^2}{2^b},$$ or more tightly $\Pr[A(\pi)] \leq \delta\cdot\Pr[A(f)]$ where $\delta = (1 - (q - 1)/2^b)^{-q/2}$.

The forgery probability bound grows quadratically with the number of blocks fed to the oracle (in forgery attempts or encryption queries), and drops exponentially in the block length.


Add in the distinguisher advantage against AES, and note that $q = 1 + (n + f) \cdot (1 + \ell)$ since there's one AES call to derive the GHASH key, one AES call per message to derive the GHASH mask, and one AES call per block.  The result is a bound of $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}} + \frac{(1 + (n + f)\cdot(1 + \ell))^2}{2^b} + \frac{f \ell}{2^\tau}$$ on the forgery probability, or more tightly, $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}} + \biggl(1 - \frac{(n + f) \cdot (1 + \ell)}{2^b}\biggr)^{\frac{-(1 + (n + f)\cdot(1 + \ell))}{2}} \cdot \frac{f \ell}{2^\tau}.$$

What does this mean for specific volumes of data that your application might process?  First, always assume the adversary can attempt more forgeries than the legitimate users will handle data—legitimate users use only as much bandwidth as their needs require, while forgers will saturate the remaining bandwidth attempting forgeries.

Let's consider three different regimes for the volume of data your application can process: a single block-message, an IP packet-sized message, and a megabyte of data per message.  We'll consider the tighter bound.

\begin{equation}
\begin{array}{llll}
\text{max bytes} &amp;
\text{messages} &amp;
\text{forgeries} &amp;
\tau=128 &amp;
96 &amp;
64 &amp;
32 \\
\hline
\text{one block: $16$}
  &amp; 1 &amp; 1 &amp; 2^{-127} &amp; 2^{-95} &amp; 2^{-63} &amp; 2^{-31} \\
\hline
\text{IP packet: $2^{11}$}
 &amp; 2^{16} &amp; 1 &amp; 2^{-120} &amp; 2^{-88} &amp; 2^{-56} &amp; 2^{-24} \\
 &amp; 2^{16} &amp; 2^{16} &amp; 2^{-104} &amp; 2^{-72} &amp; 2^{-40} &amp; 2^{-8} \\
 &amp; 2^{16} &amp; 2^{24} &amp; 2^{-96} &amp; 2^{-64} &amp; 2^{-32} &amp; 0.6 \\
 &amp; 2^{16} &amp; 2^{32} &amp; 2^{-88} &amp; 2^{-56} &amp; 2^{-24} &amp; (?) \\
 &amp; 2^{16} &amp; 2^{48} &amp; 2^{-72} &amp; 2^{-40} &amp; 2^{-8} &amp; (?) \\
 &amp; 2^{16} &amp; 2^{56} &amp; 2^{-64} &amp; 2^{-32} &amp; 0.6 &amp; (?) \\
\hline
\text{IP packet: $2^{11}$}
 &amp; 2^{32} &amp; 1 &amp; 2^{-120} &amp; 2^{-88} &amp; 2^{-56} &amp; 2^{-24} \\
 &amp; 2^{32} &amp; 2^{32} &amp; 2^{-88} &amp; 2^{-56} &amp; 2^{-24} &amp; (?) \\
 &amp; 2^{32} &amp; 2^{48} &amp; 2^{-72} &amp; 2^{-40} &amp; 2^{-8} &amp; (?) \\
 &amp; 2^{32} &amp; 2^{56} &amp; 2^{-64} &amp; 2^{-32} &amp; 0.6 &amp; (?) \\
 &amp; 2^{32} &amp; 2^{60} &amp; 2^{-14} &amp; (?) &amp; (?) &amp; (?) \\
\hline
\text{IP packet: $2^{11}$}
 &amp; 2^{48} &amp; 1 &amp; 2^{-120} &amp; 2^{-88} &amp; 2^{-56} &amp; 2^{-24} \\
 &amp; 2^{48} &amp; 2^{48} &amp; 2^{-72} &amp; 2^{-40} &amp; 2^{-8} &amp; (?) \\
 &amp; 2^{48} &amp; 2^{56} &amp; 2^{-64} &amp; 2^{-32} &amp; 0.6 &amp; (?) \\
 &amp; 2^{48} &amp; 2^{60} &amp; 2^{-14} &amp; (?) &amp; (?) &amp; (?) \\
\hline
\text{megabyte: $2^{20}$}
 &amp; 2^{32} &amp; 1 &amp; 2^{-111} &amp; 2^{-79} &amp; 2^{-47} &amp; 2^{-15} \\
 &amp; 2^{32} &amp; 2^{32} &amp; 2^{-79} &amp; 2^{-47} &amp; 2^{-15} &amp; (?) \\
 &amp; 2^{32} &amp; 2^{40} &amp; 2^{-71} &amp; 2^{-39} &amp; 2^{-7} &amp; (?) \\
 &amp; 2^{32} &amp; 2^{48} &amp; 2^{-63} &amp; 2^{-31} &amp; (?) &amp; (?) \\
 &amp; 2^{32} &amp; 2^{50} &amp; 2^{-50} &amp; 2^{-18} &amp; (?) &amp; (?) \\
 &amp; 2^{32} &amp; 2^{51} &amp; 2^{-14} &amp; (?) &amp; (?) &amp; (?) \\
 &amp; 2^{32} &amp; 2^{52} &amp; (?) &amp; (?) &amp; (?) &amp; (?) \\
\end{array}
\end{equation}

Entries labeled (?) have no bound at all on forgery by the above analysis.  Note that rotating keys doesn't help: the forger's attempts at forgery for the first key are independent of the forger's attempts at forgery for the second key.  Very small tags provide almost no security for even a modest number, tens of thousands, of modestly sized packets.

To put these forgery probabilities into perspective, the Bitcoin network rolls a 1 on a $2^{64}$-sided die about once a second.

Exercise for the reader: Compute the forgery probability bounds for the volumes of data in NIST's table, and assess how sensible they are.

WARNING 1: There may be fenceposts in the above analysis and errors in the calculation of the table entries.  For better confidence, trust anonymous reviewers at meatspace crypto conferences rather than pseudonymous strangers at internet crypto forums, and/or double-check the calculations yourself.

WARNING 2: Did you remember to use sequential 96-bit nonces?  You forgot, didn't you?  Go back and use sequential 96-bit nonces, or switch to crypto_secretbox_xsalsa20poly1305 which is faster and safer in software and allows random nonces and has better bounds than the above even with random nonces.