The phrase ‘128-bit security’ is a bit glib to cover the online/offline distinction—the purpose of the explicit formulas is to quantify the forgery probability in terms of limits on the online and offline costs. The online costs depend on how scalable your application is; the offline costs depend only on how much the adversary is willing to pay to break cryptography.
First, we can sketch the asymptotic growth curves:
- The forgery probability bound grows quadratically in the number of online queries including authenticating legitimate messages and verifying attempted forgeries, and drops exponentially in the size of the block, because of the PRF/PRP-switching lemma.
- The forgery probability bound grows linearly in the number of blocks forged in online queries, and drops exponentially in the size of the tag, because of the one-time forgery probability for GHASH.
- The forgery probability also increases by whatever advantage the adversary can afford working offline to break AES. Note that the only work the adversary can do offline is to break AES—nothing else in AES-GCM admits advantage from offline work. Also make sure to use AES-256, not AES-128, if you want a ‘128-bit security level’.
As a cryptographer writing a paper for an academic conference, you might stop here, and that's what McGrew and Viega did when they published GCM[1], apparently with an error in the analysis around nonce hashing that Iwata, Ohashi, and Minematsu reassessed[2]. Side note: Use 96-bit nonces chosen by counting if you must use AES-GCM. (You picked the theorem about 96-bit nonces chosen by counting; unwary passersby might mistakenly step on the rake of other nonce sizes or of nonces chosen at random, which is what most of the Iwata–Ohashi–Minematsu paper is about.)
As a standardizer giving advice in a standard, you want to give concrete bounds for usage limits. For example, NIST SP800-38D[3] (archived in case the United States federal government self-immolates in protest of its grifter-in-chief again) only sternly limits the number of messages made with nonces chosen at random or of lengths other than 96 bits—specifically, in §8.3, it forbids processing more than $2^{32}$ messages. Side note: Did I mention that you should use 96-bit nonces chosen by counting?
Curiously, that is the only limit mandated by NIST SP800-38D. The only other limit mentioned is a ‘reasonable limit’ of $2^{64}$ blocks authenticated, with no mention of what reason went into that limit other than reference back to to §8.3.
As an application developer or protocol designer, you need to pick actual numbers for the volume of data you're willing to process, which will let you compute specific bounds. So let's do that.
\begin{equation}
\begin{array}{llll}
\text{max bytes ($16\cdot \ell_A$)} &
\text{messages ($q$)} &
\text{forgeries ($q'$)} &
\text{bound} &
\text{bound*} \\
\hline
\text{one block: $16$}
& 1 & 1 & 2^{-124} & 2^{-127} \\
\hline
\text{IP packet: $2^{11}$}
& 2^{32} & 1 & 2^{-50} & 2^{-120} \\
& 2^{32} & 2^{32} & 2^{-48} & 2^{-88} \\
& 2^{32} & 2^{40} & 2^{-34} & 2^{-80} \\
& 2^{32} & 2^{50} & 2^{-14} & 2^{-70} \\
& 2^{32} & 2^{60} & 33(?) & 2^{-14} \\
\hline
\text{IP packet: $2^{11}$}
& 2^{48} & 1 & 2^{-18} & 2^{-120} \\
& 2^{48} & 2^{48} & 2^{-16} & 2^{-72} \\
& 2^{48} & 2^{56} & 1/4 & 2^{-64} \\
& 2^{48} & 2^{60} & 33(?) & 2^{-14} \\
\hline
\text{megabyte: $2^{20}$}
& 2^{32} & 1 & 2^{-32} & 2^{-111} \\
& 2^{32} & 2^{32} & 2^{-30} & 2^{-79} \\
& 2^{32} & 2^{40} & 2^{-16} & 2^{-72} \\
& 2^{32} & 2^{50} & 9(?) & 2^{-50} \\
& 2^{32} & 2^{60} & 2^{24}(?) & 2^{12102521}(?)
\end{array}
\end{equation}
How do we interpret this?
- The forgery probability for the simplest case of a single message of a single block and a single forgery attempt is near $2^{-128}$ as we would hope.
- The row with one forgery attempt shows the forger's success probability for a single attempt. But remember that it scales quadratically, not linearly, because we're using a random permutation, AES, to choose the hash key, not a random function.
- You should assume the adversary can send at least as many messages as the legitimate users, so I didn't show any numbers of forgery attempts between 1 and the number of legitimate messages. Indeed, you should really assume the adversary can send many more messages than the legitimate users will; the adversary will saturate your available bandwidth.
- For an application that authenticates billions of IP packets in normal use, the Iwata–Ohashi–Minematsu bound you quoted suggests the adversary has to attempt trillions of forgeries before their probability of success at finding a single forgery is better than one-in-a-million ($2^{-20}$), and has to submit quadrillions for better than one-in-a-thousand.
- The bound breaks down after a certain point: bounds on probabilities above 1 are useless. Fortunately, the alternative Eq. (22) of [2] with a tighter PRF/PRP-switching lemma from Dan Bernstein[4], shown in the ‘bound*’ column, provides better confidence and works for larger numbers of messages: $$\biggl[\frac{q' (\ell_A + 1)}{2^\tau}\biggr] \cdot \delta_n(\sigma + q + q' + 1),$$ where $$\delta_n(a) = \biggl(1 - \frac{a - 1}{2^n}\biggr)^{-a/2}.$$
- Remember that this applies only if you use 96-bit nonces chosen by counting with AES-GCM. If you choose nonces at random, or use nonces of sizes other than 96 bits, the numbers above all get worse because there's a chance of nonce collision.
This is not the best you can do with an authenticator $H_r(m) + s$ built out of a universal hash family $H$ like GHASH or Poly1305. GCM uses the Carter–Wegman–Shoup construction[5][6], reusing $r$ and deriving $s = \operatorname{AES}_k(n)$ from a nonce $n$. You could skip the Carter–Wegman structure and derive $(r, s) = F_k(n)$ for some pseudorandom function family $F_k$ like XSalsa20 for each message, as suggested by Tanja Lange[7]. This is what NaCl does, and it provides the generally even better bound $8 q' \ell_A/2^{106}$ on forgery probability by all attackers who haven't broken XSalsa20—note that this is independent of the number of messages $q$ authenticated by your application.
Also XSalsa20 (and XChaCha) can handle nonces chosen at random, and are faster in software, and don't invite timing side channel attacks. So, while we're at it, consider using crypto_secretbox_xsalsa20poly1305 instead of AES-GCM. (Filling out the corresponding table above is left as an exercise for the reader.)
