implementing GCM with dev/urandom for a nonce 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
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 264 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 232 - 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.