AEAD constructions encrypt messages and append an authentication tag. That authentication tag is computed using the following data:
- The secret key
- The nonce
- The message, before or after encryption
- Optionally, some additional data
During the decryption process, the authentication tag is computed using the same data, and compared with the one that was attached to the ciphertext.
In order to prevent replay attacks, one of these parameters has to be implicitly known by the recipient.
A simple way to ensure that is to set the initial nonce to a given value, and increment it after every message.
The originator only sends the initialization vector. Individual messages do not contain a copy of the nonce used to encrypt them. They don't have to, since the recipient can perform the same operation as the sender, namely increment the nonce after every received encrypted message, in order to decrypt the stream.
If the stream being decrypted doesn't match the original stream, because messages have been altered, removed, added, duplicated or reordered, the authentication tag will not match the one computed by the recipient using the expected nonce. This issue will be immediately detected by verifying the tag.
When using a transport protocol such as UDP, encrypted messages are not guaranteed to be received in order. Some datagrams may also be missing or duplicated. Applications must reorder them and handle retransmission.
In that situation, a copy of the nonce, or value representing the difference with the initial nonce, can be added to every encrypted message. Since a message is encrypted and authenticated using a unique nonce in addition to the key, the decryption process will immediately detect a an encrypted message whose attached nonce has been tampered with.
Now, if the server is "stateless", there are no ways to ensure that a message hasn't been received before. However, it is still possible to check that a received message is not too old (with the definition of "too old" being application-specific).
Attach a timestamp to the message or to the ciphertext. If it is attached to the ciphertext, include it is the additional data, so that it will be part of the computation of the tag.
The recipient can then check that the timestamp has not been tampered with, and that it is not older than expected.
This requires synchronized clocks, and once again, only provides partial protection against replay attacks.