Beyond birthday bound security in AES-GCM-SIV

Question

AES-GCM-SIV takes a 96 bit nonce, like the original GCM. The RFC states that "it is RECOMMENDED to use this scheme with randomly chosen nonces". It uses the random nonce to generate per-message encryption and MAC sub-keys using a PRF based on AES, and claims this construction offers beyond birthday bound security:

The AEADs defined in this document calculate fresh AES keys for each nonce. This allows a larger number of plaintexts to be encrypted under a given key. Without this step, AES-GCM-SIV encryption would be limited by the birthday bound like other standard modes (e.g., AES-GCM, AES-CCM [RFC3610], and AES-SIV [RFC5297]). This means that when 2^64 blocks have been encrypted overall, a distinguishing adversary who is trying to break the confidentiality of the scheme has an advantage of 1/2. Thus, in order to limit the adversary's advantage to 2^-32, at most 2^48 blocks can be encrypted overall. In contrast, by deriving fresh keys from each nonce, it is possible to encrypt a far larger number of messages and blocks with AES-GCM-SIV.

However, with a 96-bit random nonce, you exceed a $2^{-32}$ chance of a collision after only $2^{32}$ messages, which is why NIST SP 800-38D restricts AES-GCM with a random nonce to $2^{32}$ messages. If a nonce collides in AES-GCM-SIV then the PRF construction will derive identical encryption and MAC sub-keys, so we still have a collision. AES-GCM-SIV is misuse resistant authenticated encryption (MRAE), but like all MRAE schemes it still leaks information (equality of plaintexts) in a nonce reuse situation and is not IND-CPA-secure in that case.

I initially assumed the beyond-birthday-bound security was referring only to the limit on the total number of blocks that can be encrypted, not messages. However, the quote above explicitly says AES-GCM-SIV can encrypt "a far larger number of messages", and a later quote in the security considerations claims you can encrypt 2^61 messages, where each plaintext is at most 16 KiB for up to 256 uses of the same nonce and key. However, after generating $2^{61}$ 96-bit random nonces, we would expect around 3,355,443 nonce collisions. I think (from the reference) that the claim is that no particular nonce value will repeat more than 256 times. However, there will still be some potential loss of confidentiality for those ~3.4 million messages with colliding nonces.

I'm not really sure how to interpret these bounds. What is the relevance of limiting any particular nonce being reused to at most 256 times if the total number of colliding nonces is enormous? And am I correct to assume that if you actually want IND-CPA security (with misuse-resistance), then AES-GCM-SIV is limited to a maximum of $2^{32}$ messages?

Answer 1

AES-GCM-SIV is misuse resistant authenticated encryption (MRAE), but like all MRAE schemes it still leaks information (equality of plaintexts) in a nonce reuse situation and is not IND-CPA-secure in that case.

This is the crux of it. In the event of nonce reuse, AES-GCM-SIV fails to provide IND-CPA. From RFC 8452 (p. 12):

We stress that nonce misuse-resistant schemes guarantee that if a
nonce repeats, then the only security loss is that identical
plaintexts will produce identical ciphertexts.

I'm not really sure how to interpret these bounds.

These are not bounds on the adversary's IND-CPA advantage. They are bounds on the adversary's advantage in the mrAE game. The mrAE game is defined in Appendix A of the original GCM-SIV paper. The adversary is given two oracles:

• encrypt(nonce, ad, message)
• decrypt(nonce, ad, ciphertext)

The adversary's goal is to distinguish:

1. oracles computing AES-GCM-SIV under a uniform random key, from
2. oracles returning
   • uniform random ciphertexts of the correct length on encryption queries, and
   • unconditional failure on all decryption queries.

We assume the adversary never repeats an encryption query, and never submits the answer to an encryption query as a decryption query. The bounds reported in the RFC put additional assumptions on the adversary, for example requiring each nonce submitted to the encryption oracle to be chosen independently uniformly at random. (In practice, this assumption reflects a system where the adversary doesn't really choose the nonce; the legitimate user chooses it.)

What the bounds you quoted tell you about is roughly the probability the adversary can do more than identify repeated plaintexts—for instance, they can't forge messages and can't learn anything about messages except equality. These bounds are 'beyond birthday bound' because the notion of security takes as a premise that revealing message equality is not a problem, and they work by deriving a fresh key per message (which is, incidentally, very costly in software AES) so you're not working with a fixed 128-bit permutation per key. In contrast, even assuming messages don't repeat, bounds on the adversary's advantage against AES-SIV (RFC 5297) are limited by the 128-bit birthday bound.

What is the relevance of limiting any particular nonce being reused to at most 256 times if the total number of colliding nonces is enormous?

If a single nonce is reused across many messages, then the bounds on the adversary's advantage are essentially no better than for AES-SIV, which is limited by the 128-bit birthday bound—for $q$ queries with the same nonce the advantage bound has a $q^2\!/2^{128}$ term (actually $L q^2\!/2^{128}$ for AES-GCM-SIV, where $L$ is the maximum message length in 16-byte blocks). After a large number of reuses you might hit a tag collision in POLYVAL (GHASH with the bits reversed), which would lead to a repeated AES-CTR key stream and all sorts of bad things happen.

If the number of reuses of any particular nonce is limited, though, the adversary's advantage arising from the possibility of a tag collision is small enough not to matter.

Again, this assumes messages don't repeat or you don't care about leaking message equality.

And am I correct to assume that if you actually want IND-CPA security (with misuse-resistance), then AES-GCM-SIV is limited to a maximum of $2^{32}$ messages?

Yes.

Suppose the adversary is given oracles encrypt(ad, message) and decrypt(ad, ciphertext) for a randomized cipher, and is allowed to repeat queries. Here's an adversary to distinguish an AES-GCM-SIV oracle (with nonce chosen internally, uniformly at random, on encryption queries) from a uniform random oracle: just submit the same (ad, message) pair to the encryption oracle over and over again and check for a repeated ciphertext—a nonce collision inside AES-GCM-SIV will likely happen long before a ciphertext collision in the uniform random oracle, so this adversary achieves advantage ${\approx}q^2\!/2^{96}$ after $q$ queries, or ${\approx}2^{-32}$ after $2^{32}$ queries.

If you try to set bounds on traditional IND-CPA advantage instead of mrAE advantage, you will run into problems with nonce collisions as you found. There's no way around the birthday bound for IND-CPA: for the same message (and AD), a nonce collision means all inputs to the encryption function are identical and so the ciphertext must be the same, revealing the repeated message. If that's a problem, of course the birthday bound still applies; AES-GCM-SIV has no magic to circumvent it.

---

There is a way around the 128-bit birthday bound for higher security: have a larger space of birthdays! Daence (implementations) uses a 24-byte tag instead of a 16-byte tag so that it can:

• provide a simpler interface (no separate nonce parameter),
• let you use public or secret nonces—deterministically or randomly and of any size according to your needs!—by just putting them in the associated data or message, and
• set much tighter bounds on advantage for much larger numbers of messages and volumes of data.

For instance, you could use a compact 16-bit sequence number if you only send $2^{16}$ messages per key, or a 128-bit random UUID in long-term asynchronous applications, and just put it in the associated data or message. Still no magic to prevent message equality from leaking if your nonces collide, of course. But you can make the probability of nonce collisions negligible by using a large enough uniform random nonce for your application, or by using sequential nonces (which RFC 8452 explicitly advises against for AES-GCM-SIV!) in online interactive protocols where there's no danger of state rollback, or a combination of the two.

Bonus: much smaller code footprint on top of the primitives (Poly1305 and either Salsa20 or ChaCha), and no severe penalty for software implementations like AES-GCM-SIV has from deriving a fresh AES key per message.

Comparison of Daence, AES-SIV, and AES-GCM-SIV advantage bounds, for many message sizes, in the deterministic ('misused'), randomized, and sequential settings (source code).

(Disclosure: I designed Daence.)