Overview

Snowflake uses STUN (RFC 5780) to traverse NATs and allow clients to connect to proxies that can be run on volunteer home networks: in browser extensions, on mobile phones, or as a command line program on a home desktop.

Types of NATs

Not all NAT and firewall configurations are the same. Two specific peers are not necessarily guaranteed to be able to form a P2P connection using STUN. There are two different factors that determine whether the NATs of two peers are compatible: The NAT mapping behaviour and the NAT filtering behaviour.

NAT Mapping Behaviour

A NAT's mapping behaviour determines how an internal (ip, port) pair is mapped to an external (ip, port) pair. The internal pair is the address and port assigned to the application on the user's machine. The external pair is the address and port that are visible to the rest of the internet.

There are many different ways to perform this mapping, but for simplicity we will consider the following three general types:

• Address-independent (AI) mapping: internal addresses are mapped to the same external address regardless the remote (ip, port) pair they are connecting to, or there is no NAT in place
• Address-only-dependent (AO) mapping: internal addresses are mapped to a different external address depending on which remote ip address they are connecting to
• Address-and-port-dependent (AP) mapping: internal addresses are mapped to a different external address depending on which remote ip and port they are connecting to

NATs that are either address only dependent or address and port dependent are typically referred to as symmetric NATs.

NAT Filtering Behaviour

Filtering behaviour can also be generalized into the same three types:

• Address-independent (AI) filtering: incoming connections are not filtered
• Address-only-dependent (AO) filtering: incoming connections are filtered if there was not a corresponding outgoing connection to the remote IP address
• Address-and-port-dependent (AP) filtering: incoming connections are filtered if there was not a corresponding outgoing connection to the remote IP address and port pair

NAT Variations

The following NAT variations (that present a combination of NAT mapping and filtering behaviour) are typically seen in the wild:

• Full Cone: A full cone NAT is one where all requests from the same internal IP address and port are mapped to the same external IP address and port. Furthermore, any external host can send a packet to the internal host, by sending a packet to the mapped external address.

  Mapping: AI
  Filtering: AI
  

• Restricted Cone: A restricted cone NAT is one where all requests from the same internal IP address and port are mapped to the same external IP address and port. Unlike a full cone NAT, an external host (with IP address X) can send a packet to the internal host only if the internal host had previously sent a packet to IP address X.

  Mapping: AI
  Filtering: AO
  

• Port Restricted Cone: A port restricted cone NAT is like a restricted cone NAT, but the restriction includes port numbers. Specifically, an external host can send a packet, with source IP address X and source port P, to the internal host only if the internal host had previously sent a packet to IP address X and port P.

  Mapping: AI
  Filtering: AP
  

• Symmetric: A symmetric NAT is one where all requests from the same internal IP address and port, to a specific destination IP address and port, are mapped to the same external IP address and port. If the same host sends a packet with the same source address and port, but to a different destination, a different mapping is used. Furthermore, only the external host that receives a packet can send a UDP packet back to the internal host.

  Mapping: AO or AP
  Filtering: AO or AP
  

NAT Compatibility

The following chart shows which NATs are compatible with each other. Columns and rows show the NAT type in the form: (mapping, filtering). Pairwise compatible NATs are marked with a checkmark (✔️), and incompatible NATs are marked with an X.

TURN Servers

Most WebRTC applications require matching a specific peer to a specific client (as is the case for a video call), and are left with no choice but to proxy the traffic between two incompatible peers through a centralized server. TURN (RFC 5766,RFC 6062) is a common way to accomplish this.

However, using centralized TURN servers isn't ideal for our censorship-resistance use case of WebRTC. A single TURN server or even a small set of TURN servers can be easily targeted and blocked by a censor. Using existing public infrastructure or domain fronting to discourage blocking through collateral damage would be expensive, potentially damaging to other applications that rely on those servers, and generally doesn't scale the way we want Snowflake to be able to scale.

NAT Matching

Fortunately, we don't have to match specific clients to specific proxies. We can match a client with any available proxy, meaning we can choose from the set of polling proxies one that has a NAT compatible with the client.

Proxy assignment

The broker is responsible for sorting proxies into buckets, according to which types of NATs they are compatible with. When a client polls, the broker picks a proxy out of a compatible bucket to give to the client.

In practice, we don't need buckets for each possible combination of mapping and filtering behaviour. We simplify this to 2 buckets:

• unrestricted: proxies in this bucket will work with all clients, even those with the most restrictive symmetric NATs and filtering behaviour. This includes proxies with no NATs, full cone NATs, and restricted cone NATs.
• restricted: all other proxies are restricted. This includes port restricted cone NATs and symmetric NATs. Most¹ of the proxies in this bucket will work for clients without symmetric NATs.

Determining NAT behaviour

We determine the NAT behaviour of clients by using the tricks in RFC 5780. We worked with pion to implement the necessary functionality in their STUN library https://github.com/pion/stun.

However, this method does not work for web-based proxies such as those run with the badge or Snowflake webextension. The Mozilla and Chrome WebRTC APIs do not expose the ability to perform the STUN tests in RFC 5780, nor do these browser allow arbitrary UDP connections to be made by javascript (and for good reason). This presented a problem considering the vast majority of our proxies are web-based.

To solve this, we set up a probe service that allows proxies to test their NAT compatibility by attempting to connect to symmetrically NAT'd WebRTC peer. If it is able to successfully open a datachannel with this peer, we classify it as an unrestricted proxy. If the proxy times out without opening the datachannel, we sort it into the restricted bucket. For standalone proxies written in Go, we use the same method.

---

1. there is an edge case here where clients with port-dependent filtering behaviour (AI,PD) won't work with symmetrically mapped proxies, i.e. proxies with (AO,X) or (AP,X) behaviours. However, symmetric mapping is relatively rare. At the time of writing this post, (AI,PD) clients work with over 80% of restricted proxies. ↩︎