I'm planning to use the crypto_box() functions of Nacl to encrypt messages as part of a client/server protocol. The server has to deal with multiple clients and each message from a client to the server is encrypted using the public key of the server and signed with the private key of the client.
The cypto_box() functions also require me to provide a nonce. The current message number could be used as a nonce–to my understanding, the nonce is necessarily known to an attacker who is capable of keeping track of how many messages were exchanged. Both, the client and server would then maintain a message counter and simply use the newest counter value as a nonce.
However, I must deal with the case where messages are reordered or lost. Therefore I'd send the nonce in plaintext alongside the encrypted message. As long as the same nonce is not used twice, I don't see any problems with this approach. Did I miss out on something?
No, nonce's and IV's may be considered public knowledge. I've just checked the NaCl site and I don't see any explicit remarks that contradict this.
CBC mode of operation has some additional requirements for the IV (non-predictability) but that's of course not an issue in NaCl.
You should make sure that you don't accept any nonces <= the last received nonce though, otherwise an attacker could probably resend or reorder messages.