WireGuard-native NAT traversal

Firezone is a modern alternative to corporate VPNs. But modern doesn't mean completely reinventing the wheel. When we first set out to build it, we reached for existing standards. WireGuard was an easy choice given its widespread adoption as a modern VPN protocol. It is simple by design and the cryptographic primitives allow for fast yet secure implementations. WireGuard itself is only a protocol format and state machine. It does not concern itself with transporting the encrypted packets from A to B. The official WireGuard paper recommends UDP as a transport protocol but even with that in place, you are missing a crucial bit: NAT traversal.

NAT traversal is what allows devices behind different routers or firewalls to directly talk with one another. Without it, one or both of the devices would need a publicly reachable IP or forwarded port. That is doable, but it is a comforting feeling to know that your firewalls remain configured to block all ingress by default and access is only granted on-demand.

NAT traversal is a pretty well understood and researched topic with its own RFC: RFC 8445. Instead of devising our own scheme right away, we thus started off with ICE (Interactive Connectivity Establishment). ICE is built on top of the STUN message format and supports a large set of use cases, all centered around the idea of establishing a connection between two end-user devices across the Internet. It is built into every web browser and powers many applications such as VoIP, browser games or peer-to-peer file transfer. It has been battle-tested for well over a decade and it was sensible to assume that it would be a good foundation to build upon.

Essentially, ICE defines an algorithm where both peers first explore their local network environment, creating a list of network addresses. They then exchange these lists via a reliable signaling channel and form possible paths through pair-wise combinations. Finally, these paths are then tested for connectivity and the "best" one gets nominated as the path to be used for further communication.

For the longest time, Firezone has been building on top of str0m's ICE implementation. str0m is an open-source, sans-IO WebRTC implementation in Rust and as such, it also contains an ICE agent. Even though str0m was originally built for the use case of an SFU (Selective Forwarding Unit) where NAT traversal isn't as critical, its implementation has served Firezone very well for our peer-to-peer use case.

Two state machines, one connection

To establish a new peer-to-peer connection, we first run ICE to learn the path between the two Firezone peers. As soon as ICE has nominated a path, we handshake a WireGuard session and user traffic starts flowing. Depending on the latency of your Internet connection, the entire process takes anywhere from 200-500 milliseconds.

One could argue that this sequence is a clean separation of responsibilities. ICE doesn't know that we are running WireGuard and WireGuard doesn't know that we are running ICE. Yet as we've gained experience with running this setup in production across thousands of customer networks, we noticed that occasionally, these two state machines would disagree as to whether the connection was still healthy. ICE may declare a connection unhealthy once a certain number of checks go unanswered and WireGuard may declare a session unhealthy if it doesn't receive a response packet for 15s and the resulting re-key handshakes stay unanswered.

The separation of responsibilities was clean on paper. Yet, with both of these protocols running in isolation, we suddenly had two opinions on the health of the session.

This is a problem. You really don't want to have two independent state machines trying to decide the same thing. One particular experiment we ran in our test lab made this especially apparent. We tested what happens when we overloaded a Firezone tunnel with traffic. And by overload I mean sending a fixed-rate stream of UDP traffic that is not flow-controlled and will thus sustain its load even if it experiences 50% or more packet loss. Under such extreme conditions, the kernel's receive buffers overflow and half the packets don't even make it to the application. The kernel has no policy as to which UDP packets it drops, it simply drops whatever comes in and doesn't fit into the receive buffer.

With ICE and WireGuard being two separate protocols, this had interesting consequences. In a scenario where 50% of inbound packets get dropped, the chance of the individual STUN connectivity checks to make it through to the application are minuscule and as a result, ICE will very quickly declare the connection broken because it is not receiving responses to its connectivity checks. In the grand scheme of things, this is pretty ironic because the connection is clearly working. It is working as hard as it can to keep up with all the inbound traffic.

The catch-22

In an ideal world, we'd like WireGuard to be authoritative here. Its state machine already knows whether application traffic is flowing or not and ultimately that is what the user experiences as a healthy connection.

The above failure case is fabricated. A non-adversarial protocol typically wants to have its data actually delivered and therefore embeds some form of flow or congestion controller that reduces the throughput as it experiences packet loss. However, this exact kind of testing revealed where our model was falling short. More generally, the learning from it is that any additional protocol running besides WireGuard may have its packets dropped while WireGuard itself is still healthy. Yet, without an additional protocol like ICE, we can't handshake the WireGuard session. It is a catch-22. We need ICE for NAT traversal but once it has done its job, we'd like to be able to turn it off or make it non-authoritative regarding the connection's health. Unfortunately, it is not quite that easy. NAT traversal isn't a one-off job. It is something you need to do continuously to refresh NAT bindings and react to topology changes in the network.

There is no relay fallback

NAT traversal is also not guaranteed to succeed. Regardless of the network topology we find ourselves in, we must have a way of connecting two nodes with each other, even if both of them are behind symmetric NAT. A symmetric NAT randomizes the source port of outgoing packets and therefore prevents direct connections from being established. Our solution to that is our global TURN relay fleet. TURN is another protocol from the WebRTC suite. Effectively, it allows you to bind a socket on a remote server. That server has a publicly reachable IP and can thus relay all traffic arriving at the bound port back to you. Every Firezone node already connects to its two geographically-nearest relay servers and eagerly binds a socket on them. As soon as we need to connect to a Gateway, those relay sockets become part of our address candidate set and get included in the ICE checks automatically.

This is worth understanding thoroughly: When talking about NAT traversal, people often talk about a "relay fallback" that comes into play when NAT traversal "fails". But that is not how the algorithm actually works. Strictly speaking, a fallback only takes effect when another approach fails. It is the "else" part of an "if". In ICE, candidate pair nomination actually works the opposite way. All pairs with successful checks get ranked based on their priority with direct pairs having a higher priority than relay pairs. From this perspective, there is no such thing as a "relay fallback". Relays are always reachable by design and thus at least one relay pair will always get nominated. Where possible, it might then get replaced with a direct one if that succeeds too.

Nothing on the wire but WireGuard

It was clear that this "split-brain" situation needed to be resolved. We got to work and set ourselves an ambitious goal. We didn't just want to replace ICE with a home-grown wire protocol. As we've established above, any additional protocol on the wire is susceptible to triggering false-positive disconnects. We wanted to completely remove ICE and be left with nothing on the wire but WireGuard. Project ICE-less was born.

With ICE gone, the WireGuard state machine is the sole authority over the health of the session. On top of it sits our newly conceived path agent which fulfills a similar but not quite the same role as the ICE agent.

But how can we establish a connection without ICE or something ICE-like nominating a working path for us first? Well, we know that a connection via our relays always succeeds, by design. We don't need to run an algorithm to select one of those relay paths. We can simply use all of them in parallel by fanning out the handshake and deduplicating it on the receiving end, thereby bootstrapping our WireGuard session.

Once the WireGuard session exists, the hardest part is actually done. We can now send encrypted messages between the nodes and at this point, application traffic can also already start flowing.

NAT traversal as an optimization

Even though our TURN relays are eBPF-accelerated and can sustain multiple GBit/s with ease, we don't want to run all of our users' traffic over them. This is where NAT traversal comes in. Conceptually, we treat NAT traversal as an optimization that may upgrade a relayed connection to a direct one. When you distill it down, NAT traversal, especially for UDP, is actually a fairly simple algorithm: You create an NxM matrix of addresses, simultaneously fire probes at each other and take note of which ones get answered. Every probe that gets answered is a valid path to the remote.

What is a probe? A probe is a UDP packet that gets sent on the same 4-tuple that you later want to send your application traffic on. NAT traversal takes advantage of the fact that NAT devices allow inbound packets for 4-tuples that they have seen outbound traffic for.

In practice, most WireGuard implementations expect that the bytes you are passing to it form a valid IP packet. The origin of those packets however is irrelevant. We are free to inject arbitrary IP packets into the WireGuard state machine. All we need to make sure of is to also intercept them again on the other side instead of forwarding them to the operating system. This capability is what allows us to perform NAT traversal with just WireGuard.

As soon as the session is bootstrapped via a relay path, we form the NxM matrix of our and the remote peer's addresses and start probing them. Each probe is a specifically crafted ICMPv6 echo request. Firezone peers recognize these ICMPv6 packets and intercept and answer them. These packets get encrypted and interleaved with the already flowing application traffic with one difference: Application traffic always rides the current "best" pair whereas probes have an assigned path.

Each address pair gets evaluated based on a deterministic scoring function, similar to ICE's priorities. Whenever a probe succeeds, we compare its score against the currently best pair and update it if necessary. From that moment onwards, application traffic follows the newly selected best pair.

WireGuard doesn't care about how we deliver the encrypted packets from A to B, meaning the paths chosen by either peer do not actually have to be the same. Each Firezone node picks its path based on address type (direct > relayed) but also based on RTT to the remote. This asymmetry allows us to pick whichever path is best from each node's point of view. This is especially handy when it comes to relayed connections. In network topologies where only relayed connections are possible, each Firezone node sends its traffic via the relay it was assigned to.

This allows us to better load-balance traffic and makes managing connections easier: one side of the connection can migrate to another relay without the other one needing to change any state. Here is where we distinctly differ from ICE by taking advantage of coupling ourselves to WireGuard. Being its own and self-contained standard, ICE cannot assume that the protocols higher up the stack can deal with asymmetric paths. Instead, ICE has the concept of a nominated pair, and pre-assigned roles per connection define which side is allowed to nominate. For relayed connections, ICE's priority model then works out in a way where the active (controlling) side prefers the local endpoint and the passive (controlled) side talks to its relay. If that relay goes away or the connection needs to be migrated for other reasons, the connection breaks in both directions at the same time.

WireGuard, however, doesn't need symmetric paths and using asymmetric paths for relayed connections means we always have a backup ready right away. If one side's relay disappears, we immediately re-run the probing and scoring algorithm and use the next-best path: the remote's relay. As soon as our own relay is restored, the same scoring function prefers the local relay and switches back.

Removing ICE from our stack also comes with security and privacy benefits: An on-path observer only sees WireGuard packets, all of them fully encrypted and authenticated, because our NAT traversal probes simply ride the already established tunnel.

Conclusion

On paper, treating NAT traversal and the WireGuard tunnel as separate protocols looks like a good separation of concerns. In reality, the two are very intertwined and managing two state machines causes all kinds of headaches. Additionally, certain optimizations only become possible by creating more coupling between components. Coupling is often seen as something to avoid or something that needs to be reduced. This is only true for things that should not be coupled. The opposite might actually be worse: De-coupling two concerns via an abstraction when they are conceptually intertwined tends to create more problems than it solves.

NAT traversal is one of the pillars that Firezone's data plane is built upon. What started as an investigation into some connectivity issues turned into completely removing a protocol and state machine from our stack while improving stability, time-to-first-byte, security and privacy at the same time, leaving us with nothing on the wire but WireGuard.