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?

Tweak

I have a follow on question to this. With AES-CBC I am using a long term key and generate the random IV and save the IV with the encrypted data and save the data to disk and everything works fine. In this implementation, I am not concerned about AEAD. With AES-GCM / CTR, I still want to use a long time key. My plan is to setup the encryption, encrypt the data with the nonce / key and save the nonce with the encrypted data. To decrypt, I will set the nonce and decrypt the data. Is saving the nonce in plain form safe with AES-GCM / CTR? – Tweak

With AES-CTR / GCM, I am expecting that for each setup of the cipher, the internal counter is set to 0, so if I am encrypting the data for long term storage, isn't there a perceived order of the use of the NONCE with the data? If I encrypt PlainText1, PlainText2, PlainText3 using the same NONCE in the same cipher session, don't I need to decrypt these in the same order? – Tweak

I'm voting to close this question as off-topic because it belongs on crypto.stackexchange.com – Baeza

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.

Balfour

I figured the 2^n/2 issue would be part of the issue. The example helps explain it. – Tweak

NIST specifies 2^32 messages as a hard limit for GCM with a random IV, not 2^48. Furthermore GCM will also leak the GHASH key if an IV is repeated, so it's not just the confidentiality that is lost - so is the authenticity of future messages. – Onieonion

Answer 2

GCM mode

Using a random IV / nonce for GCM has been specified as an official recommendation by - for instance - NIST. If anybody suggests differently then that's up to them.

---

The birthday problem greatly increases the chance of an IV collision when a random IV is used. With the default size of the nonce (12 bytes or 96 bits) the chance of a collision isn't high. It is still possible to encrypt over a billion files or messages before the mode becomes vulnerable.

If GCM becomes vulnerable then an adversary may find the (internal) key used to generate the authentication tag. Besides that, as GCM uses CTR mode internally, so the confidentiality of the data within the files / messages is likely lost. So if an IV is ever repeated GCM will fail spectacularly.

Careful protocol design and implementation of the random IV are required because of the above limitations and vulnerabilities. It is therefore advisable to use a well tested cryptographic random number generator to generate the values of the IV.

---

More information on the generation of the IV and the resulting limitations is available in sections 8.2 and 8.3 of the NIST specification SP 800-38D on GCM.

In the NIST specs it is required to use the full 96 bits for the random IV. So there aren't any spare bits to include other information within the IV, as using an IV other than the default size of 96 bits is not advisable.

NIST specifies a limit of of 2^32 (four billion) messages to be encrypted with the same key for the randomly generated IV.

---

If the number of messages is an issue it might be better to use a key based key derivation algorithm and derive a new AES-256 bit key for each ciphertext. Another option that might offer some security against collisions for the random nonce is using AES-GCM-SIV, as the IV doesn't just rely on the nonce if that's used. Still, you'd need a maximum number of messages even for SIV mode.

CBC mode

For CBC mode a fully unpredictable, i.e. randomized IV is a requirement. If this wasn't the case then the first block(s) of the cipher may get identical input in case the XOR of the IV and the first plaintext block was encrypted before. This would result in identical ciphertext blocks which means that an adversary would gain information about the plaintext.

Usually this requirement is met by simply creating a random IV and including it with a ciphertext. Other mechanisms are possible, e.g. encrypting a counter using a different key for both sender and receiver.

Onieonion

well GCM is counter with authentication extras, and while CBC gets hurt from predictability of the IV, for CTR the thing isnt called "nonce" without reason. here, a repetition will as far as I read completely destroy the crypto, especially if known/chosen plaintext is involved which would allow you to get the encrypted nonce+counter as result allowing you to just XOR it with cipher that had same key+IV to get the other plaintext you didnt know before. – Inarticulate

@MaartenBodewes The nonce is only passed through GHASH if its length != 96 bits, and the 2^32 limit only applies to deterministic nonces whose length is not 96 bits. With the recommended 32 bit fixed field and 64 bit invocation field the limit is 2^64. – Treasatreason

Answer 3

GCM is a variation on Counter Mode (CTR). As you say, with any variant of Counter Mode, it is essential that the Nonce is not repeated with the same key. Hence CTR mode Nonces often include either a counter or a timer element: something that is guaranteed not to repeat over the lifetime of the key.

If the Nonce is purely random then there is a small chance that it will repeat. That problem is easily avoidable, hence the advice not to use a random nonce.

In CBC mode the IV munges the contents of the first block. If the first block is not altered (or a fixed IV is used) then the encryption of the first block (only) is effectively in ECB mode, which is insecure. A random IV for CBC mode avoids this problem.

Hence the difference in treatments: CTR (and modes like GCM which are derived from it) need a guaranteed unique Nonce. Modes like CBC need a random IV.

Luigi