5
$\begingroup$

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:

64 bit constraints


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 fields $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.

$\endgroup$
  • $\begingroup$ I've tried to fill in some values into the function of the GCM paper (using WolframAlpha) but the result did not make much sense to me. The algorithm did seem to be picked up fine, but the result for the maximum number of invocations was way too small. $\endgroup$ – Maarten Bodewes Aug 9 '15 at 21:47
  • $\begingroup$ I think the equation you cite is only applicable to 128-bit tag lengths and yields something like the above table assuming $P$ is the plaintext and $A$ is the associated data. I guess the tag length is somehow embedded into the "magic constants". $\endgroup$ – SEJPM Aug 31 '15 at 16:55
  • $\begingroup$ I've just tried to reproduce the above table. The right side is the solution to the exact stated equation for $2^{-38}$ as approximation for $\ll1$ $\endgroup$ – SEJPM Aug 31 '15 at 17:05
  • $\begingroup$ Sorry for the spam. But I just found something that may interest you: The (somewhat) original GCM paper including the security proof (although it may be the broken one) and they give a more generic equation there that may include the answer. $\endgroup$ – SEJPM Aug 31 '15 at 17:14
  • $\begingroup$ This is the kind of spam I'm looking for, although I haven't extracted the answer yet :) $\endgroup$ – Maarten Bodewes Sep 1 '15 at 7:54
3
$\begingroup$

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:

  1. 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$.

  2. 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} < \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} & \text{messages} & \text{forgeries} & \tau=128 & 96 & 64 & 32 \\ \hline \text{one block: $16$} & 1 & 1 & 2^{-127} & 2^{-95} & 2^{-63} & 2^{-31} \\ \hline \text{IP packet: $2^{11}$} & 2^{16} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\ & 2^{16} & 2^{16} & 2^{-104} & 2^{-72} & 2^{-40} & 2^{-8} \\ & 2^{16} & 2^{24} & 2^{-96} & 2^{-64} & 2^{-32} & 0.6 \\ & 2^{16} & 2^{32} & 2^{-88} & 2^{-56} & 2^{-24} & (?) \\ & 2^{16} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\ & 2^{16} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\ \hline \text{IP packet: $2^{11}$} & 2^{32} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\ & 2^{32} & 2^{32} & 2^{-88} & 2^{-56} & 2^{-24} & (?) \\ & 2^{32} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\ & 2^{32} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\ & 2^{32} & 2^{60} & 2^{-14} & (?) & (?) & (?) \\ \hline \text{IP packet: $2^{11}$} & 2^{48} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\ & 2^{48} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\ & 2^{48} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\ & 2^{48} & 2^{60} & 2^{-14} & (?) & (?) & (?) \\ \hline \text{megabyte: $2^{20}$} & 2^{32} & 1 & 2^{-111} & 2^{-79} & 2^{-47} & 2^{-15} \\ & 2^{32} & 2^{32} & 2^{-79} & 2^{-47} & 2^{-15} & (?) \\ & 2^{32} & 2^{40} & 2^{-71} & 2^{-39} & 2^{-7} & (?) \\ & 2^{32} & 2^{48} & 2^{-63} & 2^{-31} & (?) & (?) \\ & 2^{32} & 2^{50} & 2^{-50} & 2^{-18} & (?) & (?) \\ & 2^{32} & 2^{51} & 2^{-14} & (?) & (?) & (?) \\ & 2^{32} & 2^{52} & (?) & (?) & (?) & (?) \\ \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.

$\endgroup$
  • $\begingroup$ This should really be updated with a table that specifies (a) the maximum size of a message, (b) the number of messages legitimately authenticated by a sender, and (c) the maximum bandwidth of the receiver, measured as the number of messages it can process, in order to guarantee a forgery probability bound of (say) $2^{-64}$, or $2^{-32}$, over all time. $\endgroup$ – Squeamish Ossifrage Feb 27 at 0:57
  • $\begingroup$ The perspective provided by the Bitcoin network is bad, because it doesn't reflect how the probability scales with the cost. The issue with truncating tags on long messages is also a little unsatisfying because it likely costs about the same to attempt a hundred one-block forgeries as it does to attempt one hundred-block forgery, so while the forgery probability on a single hundred-block attempt is 100x the forgery probability of a single one-block attempt, that's not a fair comparison of the costs. $\endgroup$ – Squeamish Ossifrage Mar 8 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.