[noise] Stateless Protocols with Replay Attack Prevention

[Jason A. Donenfeld]

Hey folks,

I'm going through a few drafts of a very basic protocol, and I'm
hitting some snags. I fear I'm coming up with some kind of theoretical
limitation, for which no engineering solution exists, but I wanted to
run it past you first.

Simple site-to-site VPN protocol, using a shared key, with a symmetric
cipher in an AE mode. Messages are encrypted, MAC'd, put on the wire,
and are decrypted on the receiving end, where they bubble up into a
tun device. The beauty of this type of simplicity is that there is no
state on either end. Packets can just be sent inside the VPN with zero
requirements for setup, round-trips, initialization, book keeping,
etc.

But replay attacks. Oh, replay attacks. Obviously this scheme fails
miserable in the face of replay attacks.

The most naive solution would be to store every packet (or a hash of
every packet), and just check for inclusion. This obviously
incorporates state, as well as ridiculous storage requirements. An
improvement might be a packet counter. Or having synchronized clocks.
Both of these solutions, though, introduce state, and a handshake to
initialize counters and whatnot. Not to mention, the messiness of
out-of-order packets and having to use a window. These are ugly.

So I come to you to ask -- have folks come up with a really nice way
to eliminate replay attacks while still maintaining statelessness? Or
have I come across a fundamental contradiction?

Thanks,
Jason