How bad it is using the same IV twice with AES/GCM?

Question

I understand that initialization vectors (IV) should not be used twice when using AES/GCM. I am using a counter as an initialization vector. Every time I send out a new packet (I am developing an UDP based protocol that needs packet encryption) I increment the counter and use it as IV.

However, since I will generally need that protocol to transfer files and to send keepalives for very very extended periods of time, in principle for very large files it is conceivable to send more than $2^{32}$ packets, or over the years it is conceivable to send out $2^{32}$ keepalives. To keep the IVs always unique, I would probably need to use a 64 bits integer, but that is 4 bytes more of overhead per packet, that can sum up to quite large quantities which I would like to avoid if not strictly necessary.

So I wonder: how bad it is to reuse the IVs with AES/GCM? Can I have an idea of how dangerous that can be? I mean: if as soon as I repeat an IV once I get immediately so easily exposed to an attack that I could just give out my key publicly, then I have to take countermeasures. However, if that becomes dangerous only when I use the same IV a lot of times, that is completely another thing.

Answer 1

Even a single AES-GCM nonce reuse can be catastrophic.

• A single nonce reuse leaks the xor of plaintexts, so if one plaintext is known the adversary can completely decrypt the other. This is the same as for a two-time pad.
• In messages up to $\ell$ blocks long, after a single nonce reuse the adversary can narrow the authentication key down to $\ell$ possibilities with polynomial root-finding and thereby forge messages with high success probability $1/\ell$.
  • How? An $\ell$-block message is a polynomial of degree $\ell$ with zero constant term; the authenticator under secret key $r, s$ is $m \mapsto m(r) + s$, where $r$ is reused between messages and $s$ is derived as a secret function of the nonce. Find authenticators $a = m(r) + s$ and $a' = m'(r) + s$ for distinct messages under the same nonce, and only the ${\leq}\ell$ possible roots of the degree-$\ell$ polynomial $m(r) - m'(r) + a' - a$ in $r$ are possible values of the authentication key.

Use 96-bit nonces; if you don't—if, instead, you use smaller or larger nonces—it will be as if you chose nonces randomly, and the number of messages you can safely handle drops dramatically. But you can, of course, pad, say, a 64-bit nonce into 96 bits: what matters is only that the nonces be unique.

If the cost of a >32-bit nonce is prohibitive, you could periodically rekey. For example, if you first establish a long-term key $k$, you can use $\operatorname{HMAC-SHA256}_k(i)$ as the key during the $i^{\mathit{th}}$ epoch, where each epoch covers four billion messages, and $i$ is encoded into a bit string in some canonical way.

Answer 2

Reusing an IV once opens you up to someone finding the XOR of those two plaintext, seriously compromising their confidentiality. Moreover, with GCM, a single IV reuse leaks significant information about the key used for authentication; if there are even a few pairs of reused IVs (not even one IV used many times; a few IVs each of which are used twice is enough) can compromise the authentication key. GCM being a stream cipher, it is totally malleable if the authentication mechanism fails (the MAC is the only thing preventing tampering).

Moreover, there are mild concerns if you use a non-96-bit IV with NIST-spec GCM. NIST's GCM is designed for 96-bit IVs, and if you specify a different-length one there are weaknesses in the function used to compute the "real" IV.

Source.