[noise] Still working on DoS to no avail

[Jason A. Donenfeld]

Hi JP, Trevor, Noisey folks,

I've got a big problem with WireGuard and denial of service. I worked on
the problem some, came up with a mediocre solution, and then figured I'd
stop thinking about it during some recent trips, and then review the code
again to see if I could come up with fresh ideas with a clear head space.
Unfortunately, taking time away from thinking about the problem just made
me forget a lot. I have no new solutions or ideas. I'm at an impasse. It's
upsetting. I was hoping maybe you could give some fresh insight. Allow me
to describe the issue to you.

As you know, WireGuard is based on an elegant one round trip handshake
(Noise_IK). Initiator sends message to responder. Responder sends message
to initiator. Then they can exchange data securely. A priori, they each
know each others' static public keys. They also might optionally have a
pre-shared symmetric key, which seamlessly mixes this into the handshake
information to add an additional layer of symmetric crypto. When WireGuard
receives a handshake message, it puts it in a queue, and lets it be
asynchronously processed by worker threads.

Here's the problem: validating handshake messages requires a ECDH
computation. An optimized multicore implementation of Curve25519 running on
brand new Xeon hardware can be DoSd with around 300mbps of bandwidth. The
queue very quickly fills up and has to start dropping messages.

Let's go through a few ideas that don't work.

*- Why not just HMAC the handshake message with the pre-shared key? This
way, you only have to do an extremely fast HMAC computation to accept or
drop the message.*
Problem: The PSK is optional; this needs to be DoS-resistant even when
running in the non-PSK mode. Also, multiple parties know the PSK for
communicating with a single server. Also, trivial replay attack.

*- Why not HMAC the handshake message with the public key of the responder?*
Problem: Because public keys are public, not private. Also, trivial replay
attack.

*- Apply IP rate limiting.*
Problem: trivially spoofable since WireGuard is UDP-based, not TCP-based.

*- Well how does TCP do it?*
Message sequence numbers / cookie values. So...

*- Then why not use a cookie situation, like DTLS or IKEv2? Here, when the
responder is overloaded, it can optionally send a response saying "here's a
cookie value. Retransmit your message using this cookie value." The cookie
value is actually an HMAC of the initiator's source IP and port with some
responder secret that rotates every few seconds/minutes/whatever. The
responder keeps a ledger of the last eight or so secrets so it can try them
all, hoping one matches that isn't too old. Then, ordinary IP ratelimiting
can be applied to messages with the correct cookies, since spoofing will no
longer be possible.*
The problem here is that WireGuard relies on symmetric roles and protocols
of the initiator and responder -- they can change roles at any moment, and
they each might be communicating with multiple peers. In the IKEv2/DTLS
cookie scheme, the cookie the responder sends back to the initiator is
unauthenticated. An attacker can flood an initiator with bogus cookie
responses to cause a DoS. Also, this cookie value can be learned via MitM.
This also ruins the nice "one round trip" property of WireGuard. Though in
most cases -- when not overloaded -- the cookie round trip wouldn't be
required, sometimes it would, and this does add complexity.

*- Proof of work?*
Same issue as authentication DTLS/IKEv2, except here it's even worse: an
attacker can make an initiator waste lots of CPU cycles.


So, the best solution I've come up with sort of combines all of these
partial dysfunctional ones into a lopsided Frankenstein creation:

- Each handshake message (initiator->responder, responder->initiator) gets
added onto it a hash field.
- This hash field is an HMAC of the preceding bytes of the messages. It
uses as its HMAC key the following:
  1) The public key of the recipient of the message; concatenated with
  2) If PSK is being used, the PSK known to the recipient of the message
and the recipients various senders; concatenated with
  3) If the sender has a valid (unexpired) cookie from the recipient, the
cookie value.
- (1) is only useful if the public keys are kept secret.
- (2) is only useful if in PSK mode and other knowers of the PSK aren't
going to launch a DoS attack.
- (3) is required to be present when the server is under attack. Otherwise
it allows HMACs that use as its key only (1) and (2).

- If the receiver gets a handshake that is HMACd with a key that utilizes
(1) and (2), but not (3), and the receiver is under load, it responds with
a "cookie required" message.
- This message needs be authenticated and encrypted. Otherwise the
initiator could be sent phony cookies, or cookies could be intercepted.
- The message contains a random salt value.
- The message then contains the cookie value (which is an HMAC of the
sender's IP/port with a rotating secret as a key) authenticated-encrypted
using as a key:
  1) The public key of the responder; concatenated with
  2) If PSK is being use, the PSK; concatenated with
  3) The message's salt value.
- Both (1) and (2) have the same problems as mentioned above.

- If the receiver gets a handshake that is HMACd with a key that utilizes
(1), (2), and (3), and the server is under load, token bucket rate limiting
is done on the IP/port.


So, that's the scheme. It sort of works, but it's far from perfect, and I'm
not satisfied. Here's some untested code I wrote on the plane over a month
ago when I was dreaming this up:
http://0bin.net/paste/4iyjCG-ee310nS6C#p4nUhPnb4BEqxPcuFG+v7U1xrZHzJidboqQicHC92wu

I'm not so sure the best way forward. I'm all ears to any ideas you might
have.

Thanks,
Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/noise/attachments/20151222/8654f937/attachment.html>