Autonomous NAT Traversal
Abstract—Traditional NAT traversal methods require the help of a third party for signalling. This paper investigates a new autonomous method for establishing connections to peers behind NAT. The proposed method for autonomous NAT traversal uses fake ICMP messages to initially contact the NATed peer. This paper presents how the method is supposed to work in theory, discusses some possible variations, introduces various concrete implementations of the proposed approach and evaluates empirical results of a measurement study designed to evaluate the efficacy of the idea in practice.
A large fraction of the hosts in a typical peer-to-peer network are in home networks. Most home networks use network address translation (NAT)  to facilitate multiple computers sharing a single global public IP address, to enhance security or simply because the provider’s hardware often defaults to this configuration. Recent studies have reported that up to 70% of users access P2P networks from behind a NAT system . This creates a well-known problem for peer-to-peer networks since it is not trivial to initiate a connection to a peer behind NAT. For this paper, we will use the term server to refer to a peer behind NAT and the term client for any other peer trying to initiate a connection to the server.
Unless configured otherwise (protocols such as the Internet Gateway Device Protocol  are counted as configuration in this context), almost all NAT implementations refuse to forward inbound traffic that does not correspond to a recent matching outbound request. This is not primarily an implementation issue: if there are multiple hosts in the private network, the NAT is likely unable to tell which host is the intended recipient. Configuration of the NAT is not always an alternative; problems range from end-user convenience and capabilities of the specific NAT implementation to administrative policies that may prohibit changes to the NAT configuration (for example, due to security concerns).
Since NAT systems prohibit inbound requests that do not match a previous outbound request, all existing NAT traversal techniques (aside from those changing the configuration of the NAT system) that we are aware of require some amount of active facilitation by a third party , . The basic approach in most of these cases is that the server in the private network behind the NAT is notified by the third party that the client would like to establish a connection. The server then initiates the connection to the client. This requires that the server maintains a connection to a third party, that the client is able to locate the responsible third party and that the third party acts according to a specific protocol.
The goal of this paper is autonomous NAT traversal, meaning NAT traversal without a third party. Using third parties increases the complexity of the software and potentially introduces new vulnerabilities. For example, if anonymizing peer-to-peer networks (such as GNUnet  or Tor ) used third parties for NAT traversal, an attacker may be able to monitor connections or even traffic volumes of peers behind NATs which in turn might enable deanonymization attacks , . Another problem is that the decrease in available globally routable IPv4 addresses  will in the near future sharply reduce the fraction of hosts that would be able to facilitate NAT traversal.
II. TECHNICAL APPROACH
The proposed technique assumes that the client has somehow learned the current external (globally routable) IP address of the server’s NAT. This could be due to a previous connection between the two systems or a third party having provided the IP address in a previous exchange. Note that we specifically assume that no third party is available at the time when the client attempts to connect to the server behind the NAT.
The first goal of the presented NAT traversal method is to communicate the public IP address of a client that wants to connect to the server behind the NAT. After the server is aware of the IP address of the client, it connects to the client (similar to NAT traversal methods that involve a third party).
The key idea for enabling the server to learn the client’s IP address is for the server to periodically send a message to a fixed, known IP address. The simplest approach uses ICMP ECHO REQUEST messages to an unallocated IP address, such as 220.127.116.11. Since 18.104.22.168 is not allocated, the ICMP REQUEST will will not be routed by routers without a default route; ICMP DESTINATION UNREACHABLE messages that may be created by those routers can just be ignored by the server.
As a result of the messages sent to 22.214.171.124, the NAT will enable routing of replies in response to this request. The connecting client will then fake such a reply. Specifically, the client will transmit an ICMP message indicating TTL_EXPIRED (Figure 1). Such a message could legitimately be transmitted by any Internet router and the sender address would not be expected to match the server’s target IP.
The server listens for (fake) ICMP replies and upon receipt initiates a connection to the sender IP specified in the ICMP reply. If the client is using a globally routable IP address, this is entirely unproblematic and both TCP or UDP can be used to establish a bi-directional connection if the client listens on a pre-agreed port. In cases where there is no pre-agreed port, a port number can in most cases be communicated as part of the payload of the ICMP ECHO RESPONSE, which is typically not checked against the payload of the corresponding ICMP ECHO REQUEST by NAT implementations.
(Fig. 1. This figure diagrams the process of sending and receiving the fake ICMP messages for the server and client. In step 1, the server sends a fake ICMP request to 126.96.36.199 and in step 2 the client sends the matching reply. Note that this is a fake reply since the client never receives the ICMP request sent to 188.8.131.52 by the server. The important information contained in the actual packets is displayed for each step. The blue (solid) line shows the ICMP request path and the dashed (green) line shows the ICMP reply path.)
A. NAT-to-NAT Communication Further complications arise if both the client and the server are behind NAT. In this case, often the client will be unable to transmit a fake ICMP response to the server due to restrictions imposed by the NAT implementation of the client. One possible idea for circumventing this problem is for the client to send the same message that the server is sending except with TTL 1 to its NAT. If the NAT accepts the packet despite the forged sender IP address it might theoretically generate the desired ICMP response and forward it to the external network. However, in practice we did not find NATs where generating the necessary ICMP message using a TTL of 1 works.
Even if the client is able to transmit the fake ICMP response, the next step; in which both the client and server are aware of the others IP address and now intend to establish a TCP or UDP connection can still be complicated. The reason is that NAT systems can change the source port numbers of outbound messages. Without a third party, both client and server would have to guess matching source and destination port numbers as chosen (possibly at random) by their respective NAT implementations. Depending on the type of the NAT implementations (Full cone, restricted cone, port-restricted, symmetric), finding the correct port may take several messages. Client and server can reduce the total number of messages required by transmitting and listening on multiple ports in this phase.
B. Using UDP packets instead of ICMP ECHO REQUESTs A possible alternative to having the sender transmit ICMP ECHO REQUESTs to a fixed, known IP address is having the sender transmit UDP packets to a fixed, known IP address and port. In this case, the client would again forge an ICMP TTL EXPIRED message, only this time using the UDP format. The main disadvantage of this variation is that the sender has to guess the external UDP sender port number when faking the ICMP response. Since some NAT implementations randomly change those port numbers, the server might have to send UDP packets using multiple sender ports in order to give the client a sufficient chance at guessing correctly.
The main advantage of this technique is that the server no longer needs to send using RAW sockets, which may reduce the privileges required for the server. Note that the server still needs to be able to listen for the ICMP reply, which requires RAW sockets on Linux. In the case of a full-cone NAT, using UDP packets instead of ICMP ECHO REQUESTs also has the advantage of establishing a port mapping which can then be used as an alternative method for contacting the peer.
Another difference between the two approaches is the possible payload that can be embedded in the response. With ICMP ECHO REQUESTs, the payload can be as big as the packet size permits and is hence only limited by the MTU of the respective physical network. Well-formed ICMP UDP TTL exceeded replies on the other hand can only contain 32 bits of payload: the ICMP TTL EXCEEDED response contains the first 64 bits of the payload of the original IP packet. In those 64 bits, the 16-bit UDP checksum field and the 16-bit UDP packet length are unverifiable (for NAT’s that do not track extensive information about outgoing UDP packets) and can hence be used to transmit 32 bits of information to the server (in addition to the sender’s IP address). With our approach, either of these payload sizes is enough as we only transmit a port number in addition to the IP address.
This section summarizes the three implementations of the proposed method that we have done so far. All of the presented implementations are freely available from the web pages of the respective projects.
A. Implementation in NAT-Tester Framework Our implementation in the NAT-Tester framework was used to gather the data for this paper. It transmits the various packet types (with or without payload) using raw sockets and uses libpcap to determine which messages were forwarded by the NAT. The client is currently available for W32 and Linux and must be run with administrator rights. This implementation is useful for researchers interested in exploring the various variations of this and other NAT traversal methods.
B. Implementation in pwnat tool The pwnat tool1 is a GNU/Linux-only stand-alone implementation of autonomous NAT traversal. After contacting the server behind the NAT, it establishes a channel with TCPsemantics using UDP packets. It supports both client and server behind NAT (if one of the NATs allows the fake ICMP messages to be transmitted). This implementation targets endusers.
C. Implementation in the GNUnet Framework Finally, we have created a re-usable implementation of the presented ICMP-based NAT traversal method in GNUnet, GNU’s framework for secure peer-to-peer networking . Since the use of ICMP requires the use of non-portable and often privileged system calls, this implementation is split into three main components:
This component is a small program that provides the core ICMP-related functionality for the server. The code periodically generates the ICMP ECHO REQUEST message and also listens for incoming ICMP TTL EXCEEDED responses. If such a response is received, it simply prints the IP address of the sender to stdout. If the ICMP also contains a 16-byte payload, it is interpreted as a port number and also printed.
This component is a small binary which simply sends a single (fake) ICMP message to the IP address specified at the command line. An additional argument can be given which will be interpreted as a port number to be transmitted in the payload of the fake ICMP response message.
This component implements a GNUnet transport plugin  and is thus specific to the GNUnet peerto-peer framework. Depending on how the peer is configured, it controls ICMP servers or clients and ultimately establishes connections between peers.
Splitting the implementation into these three components has the advantage of minimizing the amount of code that must run with super-user privileges on POSIX systems (by installing the ICMP server and client with the SUID bit set). Furthermore, since the ICMP code is platform-specific, this makes it easier to manage this platform-specific part of the code. Finally, this split makes it easy to share the platformspecific but peer-to-peer network agnostic ICMP code so that it can be used with other peer-to-peer applications. This implementation is suitable as a starting point for developers of P2P networks.
IV. EXPERIMENTAL RESULTS
We have evaluated the proposed autonomous NAT traversal techniques on a large number of NAT implementations using our NAT-Tester framework , . The framework consists of a public client that volunteers download and execute. The client then performs various tests against the local NAT implementation and reports the results back to the NAT-Tester server. This enables us to evaluate NAT traversal strategies against a wide range of NAT implementations. Detailed results are made public on the NAT-Tester web page.2 In this section we will summarize the results based on the data available so far.
Table I summarizes which fractions of the NAT implementations evaluated so far support the proposed method for autonomous NAT traversal. We distinguish between behavior relevant for using autonomous NAT traversal from the point of view of both clients and servers behind NAT. We consider two cases: the case where the server uses ICMP ECHO REQUESTs and the case where the server transmits UDP packets. We also consider the extend of UDP port randomization which determines how efficient the second stage in the case of NATto-NAT communication would be. NAT implementations are categorized into the typical four types (full cone, restricted cone, port-restricted, symmetric) in cases where NAT-Tester is able to determine the type. NAT implementations that do not seem to fall into any of these categories are only included in the total.
The data shows that in virtually all cases NATs forward the faked ICMP messages for UDP (UDP-Server), but only in about half the cases for ICMP ECHO REQUESTs (EchoServer). Furthermore, a significant majority of all NATs also preserve the source port (when possible), so the additional requirement of guessing the port for faking the ICMP response for a UDP message does not change the overall cost of the approach. Finally, NATs virtually always prevent their clients from transmitting the fake ICMP messages used by our clients (Echo-Client, ICMP-UDP-Client). Based on what we have seen from inspecting NAT configurations directly, the reason seems to be that NAT rules typically only allow ICMP packets for the states “NEW” and “ESTABLISHED” in the state machine  — and the fake response falls into neither category.
The proposed method of autonomous NAT traversal works well in the case of an unrestricted client attempting to initiate a connection to a server behind NAT. Here, in virtually all cases a single ICMP message by the client would be followed by traditional connection reversal  which then reliably creates a UDP or TCP connection. In other words, there is no need for third parties to help initiate connections to NATed servers in this case.
On the other hand, if both systems are behind NAT, the proposed method rarely works and a third party is required. Assuming 70% of the peers in a network are behind NAT, this means that roughly 50% of all possible connections can be established using autonomous NAT traversal. However, even in the case where both systems are behind NAT a possible advantage of the proposed method remains; it is easy to create a simple, generic and fully stateless service that receives requests from NATed peers and generates fake ICMP replies to notify the server behind NAT. In this case, the payload of the ICMP reply would need to contain the original IP address (and likely source port number) of the client since the IP header of the faked ICMP response would now contain the IP address of the service.
EXPERIMENTAL EVALUATION OF AUTONOMOUS NAT TRAVERSAL. “ECHO-SERVER” LISTS THE NUMBER OF NAT IMPLEMENTATIONS THAT ALLOWS (FAKED) ICMP TTL EXPIRED REPLIES TO TRAVERSE THE NAT IN RESPONSE TO ICMP ECHO REQUEST MESSAGES. “ECHO-CLIENT” LISTS THE NUMBER OF NAT IMPLEMENTATIONS THAT ALLOW CLIENTS TO TRANSMIT (FAKED) ICMP TTL EXPIRED MESSAGES. “UDP-SERVER” AND “ICMP-UDP-CLIENT” GIVE THE SAME NUMBERS WHEN USING UDP PACKETS INSTEAD OF ICMP ECHO REQUESTS. “PRESERVES PORTS” INDICATES THE NUMBER OF IMPLEMENTATIONS THAT PRESERVE THE SENDER’S LOCAL PORT AS THE EXTERNAL PORT IF POSSIBLE. “ANY SERVER” LISTS THE NUMBER OF NATS WHERE EITHER THE ECHO-SERVER OR THE UDP-SERVER WORK. FINALLY, “TWO-MESSAGE SUCCESS” LISTS THE NUMBER OF NATS WHERE AUTONOMOUS NAT TRAVERSAL (AS A SERVER) SUCCEEDS EITHER WITH ECHO-SERVER OR WITH UDP WITH PORT PRESERVATION AND HENCE ONLY TWO MESSAGES ARE NECESSARY TO REACH THE SERVER.
Fake replies can enable autonomous NAT traversal in a number of cases. As with most NAT traversal techniques, this approach does not work for all installations. What is unusual about the presented method is that it works extremely well if only one peer is behind NAT and virtually never if both peers are behind NAT. Systems that require high NAT traversal success rates typically implement a number of traversal techniques and the presented approach extends the set of available methods by one that, if applicable, is cheaper and simpler than most of the existing techniques.
The authors thank the many volunteers that have downloaded and executed the NAT-Tester and helped us gather data to evaluate the method. This work was funded in part by the Deutsche Forschungsgemeinschaft (DFG) under ENP GR 3688/1-1.
#!/usr/bin/env python # -*- coding: utf-8 -*- # Created by i@BlahGeek.com at 2014-01-07 import socket import logging import time from ipaddr import IPAddress from threading import Thread from bitstring import Bits ICMP_PROTO = socket.getprotobyname('icmp') ICMP_ECHO_REQUEST_TYPE = 8 ICMP_TIME_EXCEED_TYPE = 11 SERVER_PORT = 2345 CLIENT_PORT = 2345 BUFSIZE = 4096 NO_RESPONSE_IP = '184.108.40.206' UDP_HELLO_MSG = 'Hello from pypwnat' def checksum(data, checksum_offset=1): ''' calcualte checksum using one's complement sum of all 16-bit words, put the result in the `checksum_offset`th 16-bit word data and returned data is bitstring.Bits''' chunks = list(data.cut(16)) s = sum(map(lambda x: x.uint, chunks)) s = (s & 0xffff) + (s >> 16) chunks[checksum_offset] = ~ Bits(length=16, uint=s) return Bits(0).join(chunks) def make_ip_packet(src, dst, protocol, body, id=42, ttl=64): ip_header = Bits(hex='4500') # IP version and type of service and etc total_length = Bits(length=16, uint=20+body.length/8) # Total length # The BSD suite of platforms (excluding OpenBSD) # present the IP offset and length in host byte order. # as they say... It's a feature, not a BUG! total_length = Bits(length=16, uint=socket.htons(total_length.uint)) ip_header += total_length ip_header += Bits(length=16, uint=id) # identification ip_header += Bits(hex='0000') # flags, fragment offset ip_header += Bits(length=8, uint=ttl) # TTL ip_header += Bits(length=8, uint=protocol) ip_header += Bits(hex='0000') # checksum ip_header += Bits(length=32, uint=int(IPAddress(src))) ip_header += Bits(length=32, uint=int(IPAddress(dst))) return checksum(ip_header, 5) + body def make_icmp_packet(typ, code=0, body=None, id=42, seq=42): icmp_header = Bits(length=8, uint=typ) # type icmp_header += Bits(length=8, uint=code) # code icmp_header += Bits(hex='0000') # checksum icmp_header += Bits(length=16, uint=id) + Bits(length=16, uint=seq) icmp_header = checksum(icmp_header) return icmp_header if body is None else (icmp_header+body) def send_echo_request(sock, ip, seq=42, id=42): ''' a simple ping ''' logging.debug('Sending echo request with id=%d, seq=%d.' % (id, seq)) icmp_packet = make_icmp_packet(ICMP_ECHO_REQUEST_TYPE) ip_packet = make_ip_packet(0, ip, ICMP_PROTO, icmp_packet) sock.sendto(ip_packet.bytes, (ip, 1)) return ip_packet def send_time_exceed(sock, server_ip, seq=42, id=42): logging.debug('Sending time exceed message.') inner_icmp = make_icmp_packet(ICMP_ECHO_REQUEST_TYPE) inner_ip = make_ip_packet(server_ip, NO_RESPONSE_IP, ICMP_PROTO, inner_icmp) icmp_packet = make_icmp_packet(ICMP_TIME_EXCEED_TYPE, body=inner_ip) ip_packet = make_ip_packet(0, server_ip, ICMP_PROTO, icmp_packet) sock.sendto(ip_packet.bytes, (server_ip, 1)) return ip_packet def handle_icmp_response(response): logging.debug('Handling response in new thread.') response = Bits(bytes=response) source_ip = response[12*8:][:4*8] source_ip = IPAddress(source_ip.uint) response = response[20*8:] # ignore IP header typ = response[:8] if typ.uint != 11: logging.debug('Not time exceed packet, ignore.') return logging.info('Got response from %s' % source_ip.compressed) udpsock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM) udpsock.bind(('0.0.0.0', SERVER_PORT)) udpsock.connect((source_ip.compressed, CLIENT_PORT)) udpsock.send(UDP_HELLO_MSG) def run_server(ping_interval=10.0): sock = socket.socket(socket.AF_INET, socket.SOCK_RAW, ICMP_PROTO) sock.setsockopt(socket.IPPROTO_IP, socket.IP_HDRINCL, 1) sock.settimeout(ping_interval) while True: send_echo_request(sock, NO_RESPONSE_IP) try: response = sock.recv(BUFSIZE) except socket.timeout: logging.debug('No ICMP response within %f seconds, continue.' % ping_interval) continue else: logging.debug('Got ICMP response!') th = Thread(target=handle_icmp_response, args=[response]) th.start() def run_client(server_ip): sock = socket.socket(socket.AF_INET, socket.SOCK_RAW, ICMP_PROTO) sock.setsockopt(socket.IPPROTO_IP, socket.IP_HDRINCL, 1) udpsock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM) udpsock.bind(('0.0.0.0', CLIENT_PORT)) udpsock.connect((server_ip, SERVER_PORT)) while True: logging.debug('Sending hello message via UDP.') udpsock.send(UDP_HELLO_MSG) send_time_exceed(sock, server_ip, NO_RESPONSE_IP) try: response = udpsock.recv(BUFSIZE) except socket.error: logging.debug('UDP message refused, continue') time.sleep(0.1) continue else: logging.info('Got UDP response!') print response break if __name__ == '__main__': logging.basicConfig(level=logging.DEBUG, format='[%(threadName)s] %(levelname)s : %(msg)s') import argparse parser = argparse.ArgumentParser() parser.add_argument('-s', '--server', action='store_true', help='Run as server') parser.add_argument('-c', '--client', type=str, help='Run as client, must provide IP of server') args = parser.parse_args() if args.server: run_server() else: run_client(args.client)
hatsune ~ > sudo python2 pypwnat.py -s
[MainThread] DEBUG : Sending echo request with id=42, seq=42.
[MainThread] DEBUG : Got ICMP response!
[Thread-1] DEBUG : Handling response in new thread.
[MainThread] DEBUG : Sending echo request with id=42, seq=42.
[Thread-1] INFO : Got response from 220.127.116.11
Blah-MacbookAir ~/D/p/pypwnat (master)> sudo python pypwnat.py -c 18.104.22.168
[MainThread] DEBUG : Sending hello message via UDP.
[MainThread] DEBUG : Sending time exceed message.
[MainThread] INFO : Got UDP response!
Hello from pypwnat