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?


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 2128 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/2128 of matching any particular user key, but the attack ends up merging costs across a batch of 240 user keys, amplifying the effectiveness of each guess by a factor 240.

  • $\begingroup$ Good to know! I'm using a 256-bit key and there is not much ciphertext per key (a few kilobytes). It sounds like my particular situation is safe, but can you quantify "huge" to shed light on the decision-making process if I find myself in a similar but different scenario? $\endgroup$ – jnm2 Apr 15 '19 at 13:48
  • $\begingroup$ And the sole benefit of a random IV is that it avoids collisions using 256+96 random bits rather than just 256 random bits (or 128+96 instead of 128)? $\endgroup$ – jnm2 Apr 15 '19 at 14:09
  • $\begingroup$ @jnm2 How huge depends on how much advantage you are OK with the attacker getting. The attack starts to become significantly easier than brute force after around $2^{40}$ keys. And if you are using a 256-bit key, then there is no reason to use a random nonce, as long as the key is unique and always random. $\endgroup$ – forest Apr 16 '19 at 1:46

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.

  • $\begingroup$ I'm not sure that this is entirely correct, due to the risk of multi-target attacks on AES128. $\endgroup$ – forest Apr 15 '19 at 8:04

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.

  • $\begingroup$ The advantage of using a fixed nonce, is that you don't need to transmit it or store it. I presume this is enough of an advantage for the OP. $\endgroup$ – Martin Bonner supports Monica Apr 15 '19 at 9:52
  • $\begingroup$ @MartinBonner You can usually derive the nonce from the same master secret that the key is derived from. $\endgroup$ – forest Apr 15 '19 at 9:53
  • $\begingroup$ @MartinBonner - as written: weigh the advantage against the risk and make a decision. The OP doesn't specify his use case, which makes it difficult to be specific on the threat level. $\endgroup$ – Tom Apr 15 '19 at 9:56
  • $\begingroup$ Good reminder. I can't use a counter since there is no context saved from one encryption to the next. This is a standalone tool with no central server to house a counter. The only options I know of are fixed nonce (e.g. zeros) and random nonce. The key is 256 bits and encryption will be occasional. The generator is BCryptGenRandom with BCRYPT_USE_SYSTEM_PREFERRED_RNG on Windows and OpenSSL on Unix. $\endgroup$ – jnm2 Apr 15 '19 at 14:01
  • $\begingroup$ @jnm2 you could use a trivial counter, such as the timestamp (rounded to full seconds or even minutes, if both systems are time-synchronized) or even just the day-of-year (if not and the edge case of one message being not decryptable because it was sent at just the right second doesn't matter). This would already dramatically reduce the chances of a chance repetition. $\endgroup$ – Tom Apr 15 '19 at 18:44

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.