What is the advantage of AES-GCM against CPA attack

Question

This questions is re GCM block-mode of AES. Assuming the TAG is cut to t bits, how can the strength of the cipher be calculated, that is, what is the Advantage of the cipher against CPA attack, and after how much authenticated data a new key has to be exchanged?

Answer 1

I'll use the 2012 paper: "Breaking and Repairing GCM Security Proofs" by Iwata, Ohashi and Minematsu as my primary source.

In said paper, the advantages for the privacy and authenticity game are stated. Only the latter one is being influenced by the tag length $\tau$.

Theorem 1. Let $\operatorname{Perm}(n)$ and $\tau$ be the parameters of GCM. Then for any $\mathcal A$ that makes at most $q$ encryption queries, where the total plaintext length is at most $\sigma$ blocks and the maximum nonce length is at most $l_N$ blocks, $$\textbf{Adv}^{\text{priv}}_{\operatorname{GCM}[\operatorname{Perm(n)},\tau]}(\mathcal A)\leq \frac{0.5(\sigma+q+1)^2}{2^n}+\frac{2^{22}q(\sigma+q)(l_N+1)}{2^n}$$

with $n=128$ because you pick AES here.

Theorem 2. Let $\operatorname{Perm}(n)$ and $\tau$ be the parameters of GCM. Then for any $\mathcal A$ that makes at most $q$ encryption queries and $q'$ decryption queries, where the total plaintext length is at most $\sigma$ blocks,the maximum nonce length is at most $l_N$ blocks and the maximum input length is at most $l_A$ blocks, $$\textbf{Adv}^{\text{auth}}_{\operatorname{GCM}[\operatorname{Perm(n)},\tau]}(\mathcal A)\leq \frac{0.5(\sigma+q+q'+1)^2}{2^n}+\frac{2^{22}(q+q'+1)(\sigma+q)(l_N+1)}{2^n}+\frac{q'(l_A+1)}{2^\tau}$$

In theory you could just plug-in values into the theorem until you hit a security bounds that makes you feel uncomfortable and use it.

---

Or you could just follow NIST SP 800-38D Appendix C (PDF)'s guidance on short tags with AES-GCM. It contains nice tables and explanations thereof for 32-bit and 64-bit tags. If you do not intend to shorten the tag, then section 8 has guidance on message lengths.

Answer 2

Section 8 of NIST SP 800-38D (Recommendation for Block Cipher Modes of peration: Galois/Counter Mode (GCM) and GMAC) deals with "UNIQUENESS REQUIREMENT ON IVS AND KEYS"

the initial few lines state that

The probability that the authenticated encryption function ever will be invoked with the same IV and the same key on two (or more) distinct sets of input data shall be no greater than 2^-32.

See Details here