Source and importance of nonce / IV for protocol using AES-GCM

Question

I am making a protocol that uses packets (i.e., not a stream) encrypted with AES. I've decided on using GCM (based off CTR) because it provides integrated authentication and is part of the NSA's Suite B. The AES keys are negotiated using ECDH, where the public keys are signed by trusted contacts as a part of a web-of-trust using something like ECDSA. I believe that I need a 128-bit nonce / initialization vector for GCM because even though I'm using a 256 bit key for AES, it's always a 128 bit block cipher (right?) I'll be using a 96 bit IV after reading the BC code.

I'm definitely not implementing my own algorithms (just the protocol -- my crypto provider is BouncyCastle), but I still need to know how to use this nonce without shooting myself in the foot. The AES key used in between two people with the same DH keys will remain constant, so I know that the same nonce should not be used for more than one packet.

Could I simply prepend a 96-bit pseudo random number to the packet and have the recipient use this as a nonce? This is peer-to-peer software and packets can be sent by either at any time (e.g., an instant message, file transfer request, etc.) and speed is a big issue so it would be good not to have to use a secure random number source. The nonce doesn't have to be secret at all, right? Or necessarily as random as a "cryptographically secure" PNRG? Wikipedia says that it should be random, or else it is susceptible to a chosen plaintext attack -- but there's a "citation needed" next to both claims and I'm not sure if that's true for block ciphers. Could I actually use a counter that counts the number of packets sent (separate from the counter of the number of 128 bit blocks) with a given AES key, starting at 1? Obviously this would make the nonce predictable. Considering that GCM authenticates as well as encrypts, would this compromise its authentication functionality?

Selangor

Just a note - security.stackexchange.com/questions might be a better place for this kind of question. – Pop

@Eugene Mayevski 'EldoS Corp He just got a better answer from a larger community. – Unperforated

@Eugene Mayevski 'EldoS Corp See, there is nothing to worry about. SO answered his question. – Unperforated

@Rook you are right, yet the point was totally different. security.stackexchange.com has been created for security-related questions and you surely know that StackOverflow and sister sites were created in order to organize wiki-like knowledgebase of questions and answers. And having all questions about certain topic in one place is much better than having them spread across several sites. So while short-term for the OP is to get the widest exposure, community interest could be to separate programming- and theoretical security questions. – Pop

@ugene Mayevski 'EldoS Corp So then you are recommending that people keep cross posting between the two sites? Secuirty.se will be useful but as it stands there are nearly one Dozen users that regularly answer questions, its just not very interesting. – Unperforated

Are you using a packet-based protocol, or a stream-based protocol? CTR mode could potentially work for both, but your requirements will be different depending on which you are using. – Beaut

Answer 1

GCM is a block cipher counter mode with authentication. A Counter mode effectively turns a block cipher into a stream cipher, and therefore many of the rules for stream ciphers still apply. Its important to note that the same Key+IV will always produce the same PRNG stream, and reusing this PRNG stream can lead to an attacker obtaining plaintext with a simple XOR. In a protocol the same Key+IV can be used for the life of the session, so long as the mode's counter doesn't wrap (int overflow). For example, a protocol could have two parties and they have a pre-shared secret key, then they could negotiate a new cryptographic Nonce that is used as the IV for each session (Remember nonce means use ONLY ONCE).

If you want to use AES as a block cipher you should look into CMAC Mode or perhaps the OMAC1 variant. With CMAC mode all of the rules for still CBC apply. In this case you would have to make sure that each packet used a unique IV that is also random. However its important to note that reusing an IV doesn't have nearly as dire consequences as reusing PRNG stream.

Unperforated

Thanks for the answer - so I will use a different, random nonce for each packet. Is it fine to simply prepend the nonce to the cipher text? – Selangor

@bowenl2 no, you use a key+nonce for each SESSION, the internal counter increments to account for how many bytes you have encrypted so that you don't reuse PRNG. This is like having an IV for each packet. The next time you establish a connection you can't use that same Nonce+Key. However you run into the danger of loosing synchronization if you loose a packet. – Unperforated

thanks again -- that was a typo. I'm using a 96 bit nonce for each session now which is sent by party who initiates the connection. – Selangor

CTR doesn't result in just a stream cipher - it's randomly seekable, which is not a property of stream ciphers. – Beaut

@Nick Johnson that is really important for a protocol that needs to account for packet loss. However my point on reusing prng is still valid. – Unperforated

Answer 2

I'd suggest against making your own security protocol. There are several things you need to consider that even a qualified cryptographer can get it wrong. I'd refer you to the TLS protocol (RFC5246), and the datagram TLS protocol (RFC 4347). Pick a library and use them.

Concerning your question with IV in GCM mode. I'll tell you how DTLS and TLS do it. They use an explicit nonce, i.e. the message sequence number (64-bits) that is included in every packet, with a secret part that is not transmitted (the upper 32 bits) and is derived from the initial key exchange (check RFC 5288 for more information).

Disconnect

I'm definitely leaning towards just using TLS at this point directly over TCP to minimize the impact of me (inevitably) screwing up but I'm still interested in the theory behind it. Also I believe the stuff in the second paragraph is only intended to protect against CBC attacks but I could be wrong. – Selangor

Please see my question here regarding your suggestion: #5722107 – Selangor