another thread on montonic counter alternatives

["Jason A. Donenfeld" <Jason@zx2c4.com>]

Hi folks,

We've had this discussion a few times in various forms, but it's come
up again recently, with Karolin Varner (CC'd) emailing me with some
fresh enthusiasm about the problem space, so I thought this might be
something worth discussing again, perhaps this time with some input
from the Noise mailing list.

NoiseIK is 1-RTT, so WireGuard sticks a timestamp in the first message
to prevent replay attacks. Responders reject packets with timestamps
that are larger than the last one received. If a responder reboots,
there's subsequently no session to disrupt with a replay anyway, so
it's not an issue. Generally this works well, provided initiators have
a reliable monotonic counter. Generally timestamps are considered
reliable-enough monotonic counters. Issues with this begin from two
angles:

Angle 1) Embedded devices without a battery powered RTC that want to
use WireGuard to bootstrap have a chicken & egg problem.
Angle 2) Initiators that are using the old, crusty, and insecure NTP
protocol can have their time hijacked.

Angle 2 presents some interesting possibilities. An adversary who sets
somebody's time backwards can prevent them from connecting until their
time is set right again. Adversaries who set somebody's time forward,
say, to the maximum TAI64N value, and then subsequently have an
initiator send an initiation message, can then render that initiator's
static private key forever useless, since that future timestamp can
always be replayed, and will always set the responder's greatest-yet
value to that maximum. So, if your NTP is hijacked, your key is
forever DoS'd.

We've talked about a few solutions before to this. They all have
various pitfalls.

Idea 0) Insist people don't use NTP but rather some authenticated
alternative. Insist people have battery-powered RTCs.

Idea 1) Store a monotonic counter on disk, and just increment it by 1,
or even some random value bounded far below the limit, on each
handshake. The downside is this relies on storage that doesn't wear
out and is always available.

Idea 2) For a given system boot, store in memory the time of the first
handshake, and then increment that timestamp by 1 on each handshake.
The problem is figuring out when to sample that initial golden
timestamp. And it doesn't actually solve Angle 2, because that initial
golden timestamp still might wind up NTP sync'd at some point.

Idea 3) Insist people who must use NTP disable large jumps. This has
the same issue as Idea 2, in that the bootstrapping timestamp is still
an issue.

Idea 4) Require the responder to also have a synchronized clock and
reject handshakes that are too far into the future. This might
alleviate Angle 2 to a large degree but it causes big issues for Angle
1, potentially.

Other clever ideas?

Jason