Understanding NAT Traversal in Detail
Intro
This post is a set of notes on my understanding of Tailscale’s How NAT traversal works, together with an overview of how several common NAT traversal techniques work.
NAT
NAT (Network Address Translation) was introduced primarily to address the shortage of IPv4 addresses.
In simple terms, most machines use a private IP address, such as 192.168.1.2. When a device A with such an address needs to reach a device B on the public Internet, such as 8.8.8.8, NAT replaces the private IP and port in the packet header with a public IP and port, using an address such as 212.5.102.68, before forwarding the packet to the Internet. When the response comes back, NAT uses the mapping it maintains to perform the reverse translation. This allows multiple devices to share a single public IP.
A (192.168.1.2) <--> (192.168.1.1) Router/NAT (212.5.102.68) <--> Internet <--> (8.8.8.8) B
The process is completely transparent to both sides. In this example, A does not know its own public IP on the Internet, and B does not know A’s private IP.
STUN and Basic Traversal
As we can see, A can access the outside world normally. But an external device clearly cannot access A directly, because it does not know A’s public IP after NAT. This is where STUN (Session Traversal Utilities for NAT) comes in. Its basic workflow is:
- A sends a request to a STUN server, asking what IP the server sees it coming from.
- The STUN server replies with something like, “As far as I can see, your packet came from this IP:port.”
A then needs some way to communicate this information to its peer, which can try connecting to that IP:port. In practice, however, things are not quite that simple.
Types of NAT
There are several types of NAT, some of which impose additional firewall restrictions:
- Full cone: the most open type. Once a mapping has been established, any external device can reach the internal device through the mapped public address.
- Restricted cone: unlike full cone, this additionally requires the internal device to have already sent a packet to that external device. In other words, the firewall treats it as an established connection.
- Port-restricted cone: adds another requirement to restricted cone—the internal device must have sent a packet to that particular port on the external device before the connection is considered established.
- Symmetric: the strictest type. NAT creates different mappings for connections from an internal device to different external devices, giving them different public IP:port pairs.
Tailscale’s article includes a particularly clear table:
| Endpoint-independent mapping | Mapping depends on endpoint IP:port | |
|---|---|---|
| Endpoint-independent firewall | Full cone | N/A |
| Firewall depends on endpoint IP | Restricted cone | N/A |
| Firewall depends on endpoint IP:port | Port-restricted cone | Symmetric |
In fact, as long as the mapping is endpoint-independent, we can traverse NAT by having the internal device send packets, even if the firewall strictly requires a matching IP:port. Symmetric NAT is the genuinely troublesome case: because every endpoint gets a different mapping, the STUN server and the target external device see different public IP:port pairs. This is when we generally have to rely on a relay.
A Relay Protocol: TURN
The classic relay protocol is TURN (Traversal Using Relays around NAT). Its operation is straightforward:
- Devices authenticate with a TURN server, which assigns an IP:port after successful authentication.
- A peer connects to that IP:port, and the TURN server relays the traffic.
But TURN has a number of problems, so mainstream traversal tools generally use something else for relaying. Tailscale, for example, uses its own protocol, DERP.
Port Scanning and the Birthday Paradox: Trying to Traverse Symmetric NAT
Relaying is not the only possible way through symmetric NAT; the alternatives are just rather hacky.
From the analysis above, we do not know which IP:port the peer should connect to, because the mapping it receives differs from the STUN server’s. If we query several STUN servers, however, we obtain several IP:port results. The number of IP addresses is bound to be small—usually just one—and the maximum port number is 65535, so the set of possible IP:port combinations is relatively limited. Sending 100 packets per second and trying every port on an IP would therefore complete traversal in about ten minutes in the worst case. Port scanning is a classic attack pattern, though, and risks triggering an IDS (Intrusion Detection System).
We can improve on this using the birthday paradox. For example, open 256 ports on the internal device and have the socket on each port send packets to random ports on the peer’s IP. This creates 256 NAT mapping entries. The peer likewise opens random ports and sends packets to the internal device. According to the birthday paradox, a port collision should occur quite quickly.
| Packets sent (ports opened by the peer) | Collision probability |
|---|---|
| 174 | 50% |
| 256 | 64% |
| 1024 | 98% |
| 2048 | 99.9% |
At the same rate of 100 packets per second, sending 2048 packets takes only 20 seconds, with a success probability of 99.9%.
This technique, however, only applies when just one side is behind symmetric NAT.
If the peer is also behind symmetric NAT, a collision requires not only that its request use the right port, but also that the port expected by its NAT match. We were previously searching a one-dimensional space—the peer’s port, which we can call the destination port. With symmetric NAT on both sides, we are searching a two-dimensional space of source-port/destination-port pairs. Unsurprisingly, this is much harder. A 50% success probability requires 54,000 packets, while 99.99% requires 170,000. At the earlier transmission rate, those take nine and 28 minutes respectively.
Ordinary routers also support only a limited number of active sessions. Trying to traverse symmetric NAT on both sides this way can easily overload their session tables.
UPnP and Other Port Mapping Protocols
There are also ways to make traversal simpler. These are known as port mapping protocols, the most familiar being UPnP-IGD (Universal Plug’n’Play — Internet Gateway Device Protocol).
UPnP-IGD works roughly as follows:
- Use UPnP to discover gateway devices on the network, typically by sending SSDP messages to which the gateway responds.
- Send a request to the gateway, explicitly asking it to forward a LAN IP:port to the WAN.
- The gateway replies with the assigned WAN IP:port.
You can roughly think of UPnP-IGD as a local version of STUN: it lets an internal device discover its externally mapped IP and port. Better still, it makes the gateway more permissive toward that mapping, since the internal device explicitly requested it.
UPnP is often disabled, however, because of security concerns.
NAT-PMP and PCP are similar protocols, with much the same situation.
Multiple Layers of NAT
On a real network, a device may pass through more than one NAT on its way to the Internet.
A typical example is a home network. The optical network terminal supplied by an ISP often doubles as a gateway, introducing one layer of NAT. Many people then connect their own home router behind it, adding another. This is why people so often want to put the ISP’s terminal into bridge mode.
Multiple NAT layers generally do not affect traversal using STUN and similar methods. NAT is transparent by design, and STUN only needs to discover the real public IP and port produced by the outermost mapping. As long as that endpoint is reachable, the inner NAT layers will forward the traffic accordingly. Port mapping protocols such as UPnP are a different matter: they can only discover the innermost NAT mapping.
CGNAT and Hairpinning
To conserve IP addresses, ISPs often perform NAT inside their own networks as well, which is why home broadband connections generally do not have a public IP. This is a particularly large-scale form of layered NAT called carrier-grade NAT, or CGNAT.
CGNAT introduces another scenario: both endpoints may be on the same side of the same CGNAT, inside its network. Their direct connection should not need to traverse the Internet at all. But STUN returns the IP:port on the outside of the CGNAT, which can make the STUN-based approach fail.
In this situation, port mapping protocols may become useful again. Since we are staying inside the CGNAT, usable information about the NAT mappings within that network is all we need.
If neither side has a usable mapping, another possibility is that the router supports NAT hairpinning:
- Use STUN to obtain the peer’s public IP information, then connect to that address.
- Under a normal NAT configuration, the packet would first be forwarded toward the public network and then dropped, because routing it back to the same public address is not allowed.
- With NAT hairpinning enabled, the router recognizes that the destination is actually part of its internal network, rewrites it to the internal address, and forwards the packet.
ICE
ICE (Interactive Connectivity Establishment) can be thought of as an algorithm for selecting among the methods above. Its basic workflow is:
- Both sides gather candidates: local IP:port pairs (host candidates), public IP:port pairs discovered through STUN (server-reflexive candidates), relay servers, and so on.
- They exchange their candidate information over a signaling channel using some protocol—for example, WebRTC uses SDP.
- Each side tries connecting to the other’s candidates to find which combinations work.
- The working combinations are ranked by priority, usually host candidates first, then server-reflexive candidates, then relay candidates.
- Establish the connection.
Some Popular Traversal Tools
Tailscale
Tailscale takes an approach similar to ICE, with some optimizations of its own:
- ICE hard-codes the ordering of connection methods, while Tailscale adjusts it dynamically based on RTT. Most of the time, the resulting order agrees with ICE’s.
- Rather than waiting for all probing to finish before connecting, as ICE does, Tailscale initially sends everything through a relay—the fastest way to establish connectivity, with a 100% success rate—and switches to a better path if it finds one.
- For relaying, it uses its own DERP protocol. As a company selling a service, Tailscale naturally also provides DERP servers.
FRP
As its name suggests, FRP (Fast Reverse Proxy) is a reverse proxy, so it traverses NAT by relaying. An FRP server with a public IP acts as the relay, exposing services opened by an FRP client without a public IP to the Internet.
FRP later added XTCP mode, which also attempts direct, non-relayed NAT traversal. A fallback can be configured so that an unfriendly NAT type causes it to fall back to the relayed mode, STCP.
Ngrok
Ngrok is also a reverse proxy and works along similar lines to FRP. Unlike FRP, which is simply open-source software, Ngrok is a company selling a complete service, including relay servers for its users.
Surge Ponte
Surge introduced Ponte in version 5.0 to provide NAT traversal. Once enabled, Ponte first detects the NAT type and attempts direct traversal only with full-cone NAT. In all other cases, it forwards UDP through a relay.
Surge is generally used as a proxy tool, so users already have a number of working proxy servers configured. Ponte uses those very servers as relays, which is a particularly interesting touch. Since they are proxy servers, their network performance should generally be good, making them good relays too. We know that restricted-cone and port-restricted-cone NAT are not especially difficult to traverse; Surge’s decision to relay in those cases may have something to do with this advantage, and perhaps with its independent development model as well.