Nonce for AES GCM to prevent replay attacks

Question

I am wanting to encrypt a message with a pre shared key that uses AES GCM from the OpenSSL library to do so.

I generate my key for the AES crypto via hashing my pre shared key with a salt using the PKCS5_PBKDF2_HMAC_SHA1 function which gives me a key of 32 bytes.

Once this is done I generate a crypto secure pseudo random byte sequence using RAND_bytes to generate 12 bytes to use as my IV.

Then I proceed with my crypto of the message, generation of the MAC, and packaging of my encrypted message in the form of [Length (Message + IV + MAC)][MAC][IV][Encrypted Message]

Now my question is, how can I implement protection against replay attacks. Or is there already protection built in?

From what I understand is that AES GCM only authenticates (preventing modification to the encrypted data) and encrypts data. It does not actually have a mechanism to recognize if a message has been received already, or at least in the OpenSSL implementation.

So for me to add replay protection to this message encryption, how should I add a nonce to the crypto scheme.

1. Should I simply keep track of each random IV for the given communication session and comparing any incoming message IV against the list of already received IVs?
2. Should I subtract 4 bytes from my 12 byte IV to use the free 4 bytes as a counter? ([Random Bytes X 8][00 00 00 01]) Incrementing it per message and when a message is received see if the message comes from the past until the session is over.
3. Prefix or Suffix a nonce counter to the message being encrypted, using a fully random IV and use the same detection mechanism as #2 except checking the decrypted message for the nonce rather than the IV?

A session usually only lasts for less than 50 messages, and there is no way to implement a stream cipher (SSL,TLS) encryption.

I feel that #1 may be resource consuming since I have to iterate an entire list of IVs in search for a duplicate and if the sessions ever grew in size this could be costly. #3 is alright besides the fact that the nonce is joined with the message, although since it is known in size (4 bytes) this can easily be extracted from the message. #2 seems like the best option, since all you need to keep track of is the previous messages counter and the message is left unmodified.

Is there a proper and safe way to implement a nonce to prevent replay attacks?

Thanks for your time.

Answer 1

Any of the ways you listed would work.

If you're collecting alternatives, yet another one (which I have seen in practice) is to include the message counter as the AAD (additional authenticated data), which is another input to GCM.

When we consider which one would be the best, we note that GCM has absolutely no requirement that the nonce be "random", or for that matter, unpredictable. So, there is no particular reason you couldn't use 4 of the bytes (or, for that matter, all 12 bytes) as a counter; given that all the options on the table are secure, this option (which is the cheapest) would appear to be the best.