Why is random IV fine for AES-CBC but not for AES-GCM

Question

I have been using AES-CBC for encryption and I use a random IV each time I encrypt plain text. As far as I can tell, this is the recommended approach.

I have been looking into AES-GCM / AES-CTR, primarily for the AEAD. I have not yet implemented anything with this but from everything I have read, basically the nonce is just a shorted IV and there is an internal counter that is used for each encryption call. The developer / needs to make sure the nonce changes before the 32 bit counter cycles back, otherwise the same nonce (IV) is potentially used with the same key which could encrypt the same plain text and leak the encryption key.

What I don't really understand is why can AES-CBC be fine with a random IV but some of what I have read indicates a random nonce (IV) for AES-GCM is a bad idea. The only thing I can think of is the that IV for AES-CBC is longer than the nonce for AES-GCM so the likely hood of duplicate nonce is greater for AES-GCM.

I need to encrypt data that is anywhere from a few bytes to 10 - 20 GB. I know AES-GCM has a limit to the size of data (~60GB) that it can encrypt before the counter cycles. I can get around this limitation since my data is below this limit.

Can someone shed some light on why a random nonce is not suggested for AES-GCM?

Answer 1

GCM is based on CTR mode and inherits the many-time pad (or two-time pad) problem if a nonce is reused with the same key (very nice example). If the IV is reused in CBC mode, then the only thing that an observer can detect is the equality of message prefixes.

An observer can detect that a previously sent message is sent again with CBC mode, which might not give them much, but CTR provides them with the ability to deduce the contents of a message if the some information about the structure of the content is known.

A nonce for AES-GCM mode is expected to be 96 bit long. If you're generating nonces randomly, then you are expected to generate a duplicate nonce after 2^n/2=2⁴⁸ messages (see Birthday problem). That is, the probability of generating a duplicate nonce is 50% if you generated 2⁴⁸ encrypted messages with the same key. That is quite a lot of messages, but it can happen earlier.