7
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Related: Nonce-disrespecting adversaries: Practical forgery attacks on GCM in TLS. $\endgroup$
    – yyyyyyy
    Jan 14, 2017 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, 2017 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, 2018 at 15:35

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 4
    $\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, 2017 at 3:29
  • $\begingroup$ Random nonce is usually fine if the encryption key isn't same all the time. And even if the key stays the same, it probably isn't an issue unless you're generating a lot of messages. Let's say you're backing up data from your laptop with AES-256-GCM, same password, and a random nonce. You could do this every second for 100 years and most cryptographers would still consider it completely safe regarding the random nonce usage. $\endgroup$
    – oittaa
    Apr 2, 2022 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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