Can a zero nonce be safely used with AES-GCM if the key is random and never used again?

Question

I could generate a random nonce and prepend it to the ciphertext, but storage space is at a premium and the only constraint AES-GCM has on the nonce (if I'm reading correctly) is that the same nonce must never be paired with the same key for a second encryption.

The encryption key is randomly generated, used for a single encryption, split using Shamir's Secret Sharing Scheme, and discarded. When the key is reconstructed for decryption, there is no chance that it can be fed back through to encrypt again; a new random key is always generated for each encryption.

If that's the only constraint, then twelve zero bytes are as safe as twelve random bytes prepended to the ciphertext. I'm reading that the AES-GCM nonce is used as the IV for AES in CTR mode. It's okay to use a zero IV for AES-CTR as long as the key is never reused, but I don't want to assume without confirmation that AES-GCM does nothing relevant with the nonce besides passing it to AES CTR. Am I missing anything?

Answer 1

Usually. However, if you are using 128-bit AES in CTR mode (remember that GCM is essentially just CTR with authentication), then a kind of attack called a multi-target attack can become possible. This attack is realistic when an attacker has a huge amount of stored ciphertext, each with a random key. While breaking a specific key requires performing up to 2¹²⁸ operations, breaking any key is significantly easier. This attack can be mitigated either by using a larger key size, or by using a random nonce.

From the above-linked blog post by DJB:

What the attacker hopes to find inside the AES attack is a key collision. This means that a key guessed by the attack matches a key chosen by a user. Any particular guessed key has chance only 1/2¹²⁸ of matching any particular user key, but the attack ends up merging costs across a batch of 2⁴⁰ user keys, amplifying the effectiveness of each guess by a factor 2⁴⁰.

Answer 2

Am I missing anything?

No, you are not; if you use a key only once, that is, to encrypt a single message, and never use it to encrypt anything else, then it doesn't matter what nonce you use. An implicit 'all-00' nonce is as good as any.

BTW: AES-GCM also uses the nonce as a part of the transform that generates the integrity tag; however, that addition does not complicate the fact that an all-00 nonce is fine, as long as you use the key once.

Answer 3

Does your random generator guarantee (with sufficient confidence) that it won't generate the same random key a second time?

As you correctly stated, as long as the same nonce and key are never re-used, everything is fine. But a randomly generated key does not by itself have such an assurance.

There are two simple ways you can take:

a) accept the risk. Make a quick calculation based on your RNG what the probability is that a key will be repeated and then decide that this chance is acceptable (or not).

b) instead of using a zero nonce, use a simple counter. That's what many implementations actually do. The nonce can be predictable, that's ok.

The decision in a) largely depends on the number of messages you are going to send. If the number is low, the risk is most likely acceptable. If we're talking millions-plus messages, you might find the probability of an identical key (remember the birthday paradox!) too high for comfort.