# Replay attack prevention in connectionless UDP encrypted communication

What are the options for replay attack prevention when two parties exchange UDP messages. No connection or session is estabilished. Communicating parties have pre shared key that is used for encryption (aes-256) and authentication (hmac-sha-256).

Communicating devices:

• don't have real time clock. Real time can be obtained from NTP, (but what about NTP security?)
• have permanent memory
• UDP communication is the only option
• Options include an incrementing counter in the authenticated frames, with receiving party refusing out-of-order frames based on that. It requires permanent memory surviving power loss, and that's hard to get reliable. The question seems more fit for security.stackexchange.com. It also needs a better description of what the parties can do; no "reliable real time clock" does not imply impossibility to have absolute time using a third party, nor estimate elapsed time locally. Multiple UDP transactions can be linked.. – fgrieu Oct 23 '16 at 19:35
• @fgrieu If going with the incremented counter I would add a sliding window so that legitimate out-of-order UDP packets don't get needlessly discarded; this should only require a few more bytes of volatile memory. And isn't the counter optimal, since you need some form of non-volatile memory in any case, if all the nodes lose power simultaneously? (assuming that's a realistic threat model). – Thomas Oct 24 '16 at 2:12
• @Thomas: without building a full protocol on top of UDP (which is certainly possible), if it is wanted to tolerate out-of-order UDP packets, yes sliding windows is a good solution. And yes, if there is no trusted third party involved we need NVM in the receiver at least. And yes incrementing counter in the authenticated frames is a common way to deal with the issue, in some sense optimal; like, the simplest that works. – fgrieu Oct 24 '16 at 5:34
• What should happen if a packet is lost? Should subsequent packets be rejected until a resynch, or should the lost packet become uneligible when the next packet is received, or …? What overhead is acceptable (extra messages that wouldn't be needed if the communication was lossless and secure)? – Gilles 'SO- stop being evil' Oct 25 '16 at 20:07

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:

1. 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.
2. 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.
3. 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).
4. 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.

• Could you explain how does sliding expiration work? – PanJanek Oct 25 '16 at 7:20
• @PanJanek You just keep a bitfield that stores whether a packet with a given counter was received. Suppose you have an 8-bit bitfield, and you start at counter N. Then, if you receive a counter < N - 7, you discard it. If you receive a counter between N - 7 and N, you check/update your bitfield. If you receive a counter larger than N, you increment your N, shift your bitfield as needed, and repeat (obviously you can improve this to make it faster, but this is the basic idea). – Thomas Oct 25 '16 at 8:08
• The reason the bitfield is from N - 7 to N and not N to N + 7 is you aren't vulnerable to replays if you lose power, since your non-volatile counter is always ahead of the sliding window; the worse that can happen is you drop some packets depending on the size of your window (bitfield) which is safe and can be made self-correcting in your protocol. – Thomas Oct 25 '16 at 8:09
• In my experience, replay attacks are considered to be active attacks. Furthermore, the OP suggests the an attacker may manipulate the time of one of the parties involved in the protocol, which means that we silently assume that the attacker is active. Perhaps the "no active attacker" assumption in this answer should be weakened to "no tampering with data in UDP packets" (although that is a very strange assumption, since the attacker is known to be able to modify the headers). – Aleph Oct 25 '16 at 17:58
• @Aleph: Your remark makes a lot of sense. I have edited the first and butlast paragraph accordingly, to better define the protection given by using a counter. – fgrieu Oct 25 '16 at 19:28