I was looking for a way to send UDP that is encrypted and authenticated, with private contents and no replay attacks.

I use crypto_box/unbox as is, although we do do the crypto_beforenm()/crypto_afternm() as (a) our clients are known, and (b) it's ridiculously faster. The docs on NaCl mention it, sort of, but it's much, much, faster. If you can do it, you always should do it.

As for replay attacks, we use what I'll call "hash chaining" (if someone knows the real name, I'd like to know). We have two kinds of messages, ordered and unordered. Unordered messages can be replayed at any time, as they are read-only, or some other kind of status messages, such as a heartbeat.

For ordered messages, we hash the previous message and use it as input for the next message when it is hashed. Both hashes are sent with each message (we use Sip-Hash 2-4, highly recommended BTW). (One analogy would be how git works, where the previous commit's hash is hashed as part of the new commit's hash.)

The chain of messages from the device to the server is called the "device stream", and we have a second chain going back to the device, the "update stream". The system supports multiple device streams for a single users (e.g. an iPhone and an iPad), but there's only one update stream for all devices, so they stay in sync.

Both ends of the connection test the hashes before applying, which trivially prevents replay attacks, since every ordered message can only be "played" once. We store the current device stream hash when the database is updated, in the same transaction, on both the client and the server. This provides resiliency in the face of crashes.

We also use the hash chain to detect out-of-order messages. In our application, they're pretty rare, so I simply drop out-of-order messages and request the correct one from the client.

This could be bad, because playing back old messages would illicit a response. For that reason, and also because I don't want to store update streams in the database permanently, the messages include their offset in the stream. The in-memory, wire format, and on-disk format of each messages is identical, so we can lay them end-to-end on disk. When a messages comes in, we can trivially determine if it is old, and drop it that way, too. If we need to write an update stream to disk, because the client hasn't connected in a while and we want to free up space, it's a single sendfile() + known offset call, conceptually, to send the update stream since they last signed back on. That way, we don't need a separate index for streams on disk.

Hope that helps!