I am considering a system where a small device accepts messages/commands from another device over a wireless channel. I am worried about replay attacks. The messages will be encrypted. What are well-vetted schemes for protection against these attacks? I am not too keen on timestamps (as described in this Q&A) as I don't really want to have to keep clocks synchronised. I am currently thinking of using HMAC but want to be sure that I'm doing the right thing.
An old but excellent paper on this topic is Tuomas Aura's Strategies against Replay Attacks.
The simplest version of the "Hashed Full Information" method would be to include the MAC of the previous message in the next message (you may also be able to use this as the nonce). Then store the most recent MAC along with the session key and check new messages against that. This would force serialization of messages within each session. (Assuming that is what you were thinking of when writing "use HMAC".)