The simplest way to deal with replay attack prevention (in some narrow sense of that, where the goal is to avoid that the receiver allows the same command to be played to it several times) is to have an incremental counter in an authenticated section of the packet, incremented by the sender before forming a packet to be sent. The receiver checks the authenticity of packets, and discards packets with counter field lower or equal than its own counter, then sets its own counter to the counter just received; initially, the counter is zero on both sides; it must be large enough that it can't overflow, 4 bytes are often enough.
Problems are:
- This prevents replay of passively eavesdropped material, but not delayed play of actively eavesdropped and suppressed material. In many adversarial models, that is a devastating issue. Think of a garage door opener: the adversary intercepts "open door" command, count on the user re-issuing another, intercepts that too, plays the first command to garage door, door opens, user is happy; adversary plays the second command later when the user is away. On radio links with a CRC at the end of the packet, the attack can be carried by jamming the end of the CRC so that the receiver ignores the packet, but the eavesdropper has the data, perhaps with a fair amount of error-detection capability.
- This requires a reliable atomic counter in sender and receiver, and this is hard, especially in a context where attacker can cut power of the sender or receiver at an instant precisely timed w.r.t. update of the counter. Even static RAM with battery/supercap backup out of reach of an attacker does not provide atomic update beyond wordsize (and then, not all do that, much less give a clear insurance that they do); and things are worse with EEPROM and Flash, which often can only be erased a smaller number of times than the range of the counter, and can enter metastable states where the value read becomes unreliable. That can be solved, but is notoriously difficult to get right.
- There must be a distinct counter in the receiver for each sender (it is possible to live with a single counter on the sender side).
- Out-of-order delivery of packets, which can occur with UDP, no longer works. This can be fixed with a sliding window, typically in RAM, at the expense of adding complexity (thus risk of error; some briefly crept in earlier versions of the following).
Addition per comment: the receiver maintains a bitmap of $b$ bit(s), for of up to $b$ past counter values less than the current counter that it is willing to accept nevertheless; that bitmap in RAM is initialized to all-zero at reset; and if $0\le j<b$, and bit $j$ in the bitmap is a one, and the receiver's counter is $c$, and $c>j$, then a packet having counter field $c-j-1$ will be accepted (when it would be rejected per the rule in the first paragraph of this answer), and bit $j$ in the bitmap will become zero. The receiver's job on receiving a packet becomes
- check size and integrity of packet
- extract counter field $x$ of the packet
- if $x>c$
- if $x-c>b$, set bitmap to all-ones; else shift the bitmap introducing a zero bit at index 0, then $x-c-1$ times (possibly zero) shift the bitmap introducing a one bit at index 0. In C or C++, with $b=32$ and
m the bitmap as an uint32_t, this whole step could be: m = (x-c>32) ? 0xFFFFFFFF : ((m+m+1)<<(x-c-1))-1;
- $c\gets x$ atomically
- accept the packet as received in order (with no earlier packet possibly accepted later when the bitmap is all-zero), done;
- else, if $0<c-x\le b$ and if the (now well-defined) bit $c-x-1$ of the bitmap is a one
- change said bit to zero
- accept the packet as received out of order (which can require special care), done;
- else, reject the packet.
As stated in (1), all the above is insecure against an active attacker capable of delaying packets and gaining advantage of that. Alternatives that are secure in this scenario, and do not require the difficult atomic counter, include building a challenge/response protocol on top of UDP, with the challenge good for a certain delay measured by the receiver (which requires the ability to evaluate elapsed time, but not absolute time); main problem is, that requires two-way communication.
It is also possible to use an authenticated source of absolute time; the hard thing is to find a reliable free one, see this.
