Is it possible to brute force search/guess symmetric NAT port prediction for hole punching?

Question

Say we have two clients A and B that wish to connect to each other, both behind symmetric NAT's NA and NB respectively. Also there is a rendezvous server S that exists to assist clients A and B with the hole punching process. The literatures says that because NA and NB randomly assign external ports anytime their respective clients initiate a new connection (even if the destination address is the same) the external port information that rendezvous server S swaps between its connecting clients is effectively useless. What i'm wondering is why is it not possible for clients A and B to try the external port information provided by S first and then, if that fails try repeatedly guessing/brute-forcing the external ports.

My guess is that trying all 2^16 ports would take too long or something is going completely over my head and the brute force search would require (2^16)^2 guesses which is completely unfeasible.

Answer 1

why is it not possible for clients A and B to try the external port information provided by S

Because the ports used for talking to S will never be the ports used to talk to either endpoint. A->S will be one port; A->B will be a different port. If NAT is being done correctly, neither port is guessable. The NAT entry maps Src(ip:port)/Dst(ip:port)[inside] to Src(ip:port)/Dst(ip:port)[outside] -- that's 8 numbers that NAT can change. When A changes from S to B, that's a completely new connection with completely new, unknown, external values. STUN/ICE/etc. are counting on the inside-outside src port association remaining the same for multiple destinations.

A and B have no way to know what port was selected by NAT, even if it is "sticky" (as long as the same inside src port is used, NAT uses the same outside src port), unless the same port(s) are used for multiple dst IPs. S only knows what was used to talk to it; if NAT uses a different outside src port, then neither S nor A will know what that port is.

Answer 2

"The literatures says that because NA and NB randomly assign external ports anytime their respective clients initiate a new connection (even if the destination address is the same) the external port information that rendezvous server S swaps between its connecting clients is effectively useless."

• Wrong. Most of the cheaper (more commen) symmetric NAT's, like the ones in university networks, are predictable in their port mapping scheme. My university's symmetric NAT always bumps up the port number by 1 for every new connection. See http://tools.ietf.org/id/draft-takeda-symmetric-nat-traversal-00.txt for predictive symmetric NAT traversal techniques.

"What i'm wondering is why is it not possible for clients A and B to try the external port information provided by S first and then, if that fails try repeatedly guessing/brute-forcing the external ports."

• It is possible if you like playing the lottery. My JVM can handle over 1000 threads. Each thread can be assigned a UDP socket. If the port mapping it truely random (it appears this way on cell phone towers, but there would likely be a bias toward certain numbers), then in theory you could send 1000 packets from 1000 threads concurrently and then wait on all 1000 of those sockets, listening for a reply. If there are 65535 possible ports, then you have a 1000/65535 chance, or 1.52% chance. Note that some symmetric NAT will change your public IP address if they run out of ports (PAT with Multiple IP Addresses), see http://www.cisco.com/c/en/us/support/docs/ip/network-address-translation-nat/26704-nat-faq-00.html. All in all, given that the symmetric NAT can take up more than 65535 ports (up to 65535 ports per public IP address, but your cell phone tower might have more than 1 ip address), you would have to go through 65535*n ports, where n is the number of IP addresses. And if you do take up that many ports, "If no ports are available, the packet is dropped, unless another IP address is available in the pool." which would most likely result in a denial of service of everyone using that NAT/router. If you repeatedly tried 1000 ports at a time, you would have to make a mean of 1 / .0152, or 66 attempts on average. If you wait maybe .5 seconds between each attemp, you're looking at 33 seconds to make a connection, on average.

"Is it possible"

• Yes, but it is not practical.

Answer 3

It's not enough to guess the source port. You also need to know S's port When A connects to S, NA is expecting traffic to return with a source IP of S. So B would also have to spoof the port and IP of S. If NA were a "real" firewall, you'd also have to guess TCP sequence numbers, otherwise the firewall would reject you.

Answer 4

The definition of a symmetric NAT is one where mappings depend entirely on the combination of [src ip, src port, dest ip, dest port, and probably IP version and / or transport protocol].

NOW: that is not to say that it isn't still possible to bypass symmetric NATs though. You have a number of possibilities here:

1. The NAT allocates random ports = you're screwed. There are like 68k valid ports. Both sides need to guess the others mapping. The chances of that occurring are (1 / 68000) * (1 / 68000) = infinitesimal. It's just not gonna happen.
2. The NATs use a predictable distance of N between mappings irrespective of [src ip, src port...]. N may be positive or negative modulo MAX_PORT.
3. The NAT preserves the distance between local ports + or - the distance between remote ports. So if local (1000) = remote (553); local (2000) == remote(1553).
4. The NAT does the same as above but ONLY if the local port increases by 1. The other scenario is if it increases by 2 (some routers do this so it's good to test for it.)
5. Some researchers have found routers that allocate mappings going up and down based on some function. Others have found routers that 'skip alternative ports' (not too sure what this means as it's too vague.)
6. I've saved the best for last: many routers simply preserve the source port. E.g. local (N) = remote (N).

Every single one of these options save for (1) means you can bypass symmetric NATs and hence is worth writing code for. You cannot brute force the connections between two random symmetric NATs. The exception is if you rooted both routers and wrote your own iptable routes to make ports predictable. But lets face it: its not practical to do such a thing.

I am still researching port mapping behaviours myself, but this answer should indicate how the vast majority of NATs behave in the real world. In addition to their mapping characteristics, you ought to be aware of the types of NATs because they dictate restrictions on how the mappings can be used. Like port restricted NATs = huge pain in the ass.