implementing GCM with dev/urandom for a nonce

Question

I'm currently trying to integrate GCM into my code, and I have just enough knowledge to know I'm probably doing this wrong. I know for GCM and other CTR like ciphers, using the same key with the same nonce multiple times is a terrible, horrible, very bad idea. the question is, using the same key for a decently long period (several hundred or thousand messages), what is the likely hood that a nonce is repeated, if the nonce is randomized each message with /dev/urandom. or should I simply stick to a counter beginning at a random number?

clarification: the keys are unique per session, being derived from diffie hellman group 14. my only concern is the likely hood of generating two matching nonces, given a pool of say 20000 nonces from dev urandom

Answer 1

If you are following NIST recommendations and you use a 96 bit NONCE (12 bytes), then you should be fine using a random NONCE generated by /dev/urandom. It should provide sufficient entropy for your needs.

But you'll be better off using the deterministic construction for the NONCE. It requires the NONCE to be composed of a 32 bit "fixed field" and a 64 bit counter. You can use a sequence number for your fixed field or a randomly generated string as recommended by the standard specification. As such you'll be able to do at most 2⁶⁴ opertions with the same key/NONCE. But then you have a hard limit on the number of operations you can process from the underlying CTR mode of operation to 2³² - 2.

Another data point in your decision might be the recommendations in Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS:

We conclude that an attack on an implementation using random nonces is unlikely, but it cannot be definetly excluded. For safety reasons random nonces should be avoided and a counter should be used.

I have summarized some more considerations on how to use AES-GCM correctly in a blog post.

Answer 2

For GCM, the requirement about the IV/nonce is that it is unique per message. It does not need to be random; that's a good way to do it, but not the only way. There are other mods where the nonce does need to be random.

For CTR, the requirement about the nonce/IV/counter is that it is unique per block. Incrementing a counter from 0 is fine, but you have to increment it per block, not just per message. That is, the counter value needs to be unique, not just the initial counter value. The block size is determined by the underlying block cipher; it's 16 for AES (regardless of the key size). For example, if you send a 48-byte message then a 64-byte message with the same key, it's fine to start the first message with 0 (so it will consume the values 0–2), and the second message with 3 (so it will consume 3–6). It wouldn't be fine to start the second message with 1: that would leak information about blocks encrypted with the same counter value.

GCM uses CTR internally, but GCM takes a 96-bit nonce and uses that plus a 32-bit block counter as the CTR counter value. So with GCM you don't have to worry about the message length, you can use a simple incrementing nonce per message.

If you have a library that provides AES-GCM and incorporates the nonce generation (so you pass it the key and the message, and it produces cihertext that starts with the IV that it chose at random), then by all means use this. The only case in which this would be unsafe is if you don't trust the underlying random generator.

For example, if you're on an embedded platform with no RNG, but a pre-shared key and storage for a counter value, you could keep a running counter across all messages. But in this scenario you could also implement a PRNG and use that for the counter. A running counter is a bit easier to implement if you're doing everything from scratch. But if you're on a platform without stringent limitations and with readily available libraries, the simple option is to use a random initial counter value. This will require less custom plumbing between messages, and reduces the risk that you later change the padding mode to one that needs random IVs and forget to adapt the IV selection.

Note that counter values can be reused freely with different keys. It's only using the same counter value with the same key twice that's bad.