I am encrypting multiple messages using a 256 bit key with AES in GCM mode, generating a random 96 bit nonce for each message.

The small nonce size combined with random values is worrying me:

AES-GCM takes a 96-bit nonce and NIST says that you can only encrypt $2^{32}$ messages under a single key if using random nonces. This is because if you throw $2^{32}$ balls at 2$^{96}$ buckets then you have roughly a $2^{-33}$ chance of getting two in the same bucket and NIST drew the line there. That probability might seem either high or low to you. It's pretty small in absolute terms and, unlike a work factor, an attacker can't spend resources against it, but it's a very long way from the safety margins that we usually use in cryptography.

Is this an issue? Is there something else I should prefer? For example, AES/CBC with encrypt-then-MAC construction would have a more reasonable IV/nonce size of 128 bits.

  • $\begingroup$ Related: Nonce-disrespecting adversaries: Practical forgery attacks on GCM in TLS. $\endgroup$ – yyyyyyy Jan 14 '17 at 19:18
  • 2
    $\begingroup$ Well, if random collisions are your main (and only?) concern, XSalsa20-Poly1305 offers you a 192-bit nonce... Otherwise you want something that is nonce-missuse resistant like AES-GCM-SIV. $\endgroup$ – SEJPM Jan 14 '17 at 19:40
  • $\begingroup$ You can just use a 128 bit nonce. You don't have to limit yourself to 96 bits. If you're encypting many messages with the same key, a 128 bit nonce, even after the birthday problem (relevant here!) leads to a negligible collision rate even after petablocks of data are encrypted. Finally, re-rolling your key from time to time fixes this for good. $\endgroup$ – Erik Aronesty Jul 19 '18 at 15:35

Is this an issue?

That's up to you, not us. Is 2^-33 probability of horrible cryptographic failure acceptable to you? Multiply that by the number of times you'll use this construction (or the rate and the product life time) to get a scarier picture but one you should keep in mind.

Is there something else I should prefer?

"should prefer" is again subjective based on your situation. I strongly advise you to consider AES-SIV (or AES-GCM-SIV) or XSalsa20-Poly1305.

For example, AES/CBC with encrypt-then-MAC construction would have a more reasonable IV/nonce size of 128 bits.

Sure, for another example. But if collisions bother you and you'd like a significantly lower probability then either 1. stop using random nonces 2. go for a nonce size that's greater than ~80*2 (a la XSalsa) or 3. Use a misuse resistant algorithm.

  • 2
    $\begingroup$ While (GCM)-SIV is a good choice for an encryption mode for other reasons, I don't believe it's any better than GCM (or plain CTR mode) in this respect: the relevant risk for (GCM)-SIV is collisions between the synthetic IVs (or between the incremental counter values derived from them). For AES-GCM-SIV, the synthetic IV is 95 bits long, so the probability of collisions for $2^{32}$ messages is approximately $2^{-32}$, twice as much as for plain AES-GCM with random nonces. (For the missing 96th IV bit, see eprint.iacr.org/2015/102.pdf section 4.2.) $\endgroup$ – Ilmari Karonen Jan 15 '17 at 3:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.