Safety of random nonce with AES-GCM? 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.
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.