Subject: [Ietf-behave] Port scan to and from symmetric NAT'd peers

From: David Barrett <[email-masked]>
Date: Fri, 24 Jun 2005 22:05:58 -0700 (PDT)

So I'm about to embark on implementing my symmetric NAT piercing tech, 
and I'm having trouble learning about how port scans and NATs combine 
both today, as well as under the IETF BEHAVE recommendations.  Can you 
help me to understand:

1) If a symmetric NAT assigns different external ports to each outgoing 
UDP request in round-robin fashion, what happens if there aren't enough 
ports to go around?  How does it pick which mappings to override?

For example, I am behind a symmetric NAT, and I contact 65537 external 
nodes, there simply aren't enough port mappings to accomodate all 
sessions.  If it uses a simple "least recently used" approach, would I 
in effect deny service to every other node behind my NAT (by remapping 
their ports to me)?  Or is there some kind of hard limit on the number 
of ports that will be assigned to a given endpoint?

2) Do symmetric (or any) NATs use the full range (0-65535) of extenal 
port mappings, or do they avoid certain "special" ranges (such as 
0-1023)?  Thus if I'm trying to scan a symmetric NAT to find any nodes 
behind it, need I (in the worst case) scan the entire range (0-65535) or 
can I target my scan better?

3) Given the fuzzy line between NATs and firewalls, do NATs typically 
perform any sort of "attack detection" and thus block activities such as 
port scanning, whether inbound or outbound?  Naturally, this would 
depend on the implementation, but I'm curious if you are aware of 
implementations that do this today, or if the BEHAVE draft makes any 
recommendations around this type of functionality.

4) Do you have any advice for me regarding how to effectively pierce 
symmetric NATs while remaining a "good citizen" of the Internet? 
Naturally, port-scanning is a horrible solution to the problem of 
piercing symmetric NATs, but it's the only one of which I'm aware.  Can 
you offer me any advice on how to target my scan most effectively, 
structure my scan to avoid setting off any alarms, or do away with the 
scan altogether?

Thanks for your help!

-david

---

From: Saikat Guha <[email-masked]>
Date: Sat, 25 Jun 2005 00:52:09 -0700 (PDT)

On Fri, 2005-06-24 at 22:05 -0700, David Barrett wrote:
> how port scans and NATs combine 
> both today

I have some numbers: http://www.guha.cc/saikat/stunt-results.php?sort=-9
but this is for TCP and some of it is from only 13 NATs in the lab. I do
not have data for UDP and do not know if there is a correlation between
TCP/UDP, but hopefully it'll provide some insights.

> ports to go around?  How does it pick which mappings to override?

In my tests, the new TCP connection being attempted after all ports had
been exhausted would timeout; that new SYN would be dropped by the NAT
without any ICMP.  

> sessions.  

While all symmetric NATs with one external IP would choke after 65535
unique external endpoints; I observed some (Netgear, Allied Telesyn)
that choke at ~1000 unique endpoints (see the 'Max Flows' column). This
is for TCP of course. I've heard reports of some old Linksys, D-Link and
Netgerar NATs choking at 255 sessions on various forums. 

Btw, on the STUNT result page above, I did not test more than 1020
sessions due to compiled in per-process kernel limits. So it is possible
some of those NATs run out of ports long before 65K.

> 0-1023)?

I see all possible behavior in this respect. Look under the "Preserves"
columns. LOW is defined as <=1023, HIGH as >=1024 and DYNAMIC as
>=49152. I saw NATs that only use DYNAMIC. I saw NATs that preserve the
port number and therefore use LOW as well. I saw NATs that don't
preserve the port number but still use LOW (freaky). Saying anything
conclusive about what a NAT _does not_ use is tricky since a 'no' in the
table could just be because the NAT wasn't desperate enough to use that
port. But I can say that there are NATs that use all port ranges.

> implementations that do this today

I am not aware of any active 'intrusion detection' type of counter
measures on home NATs, but I know of firewalls that will dynamically
block (or rate limit) suspected 'intrusions'. And I have heard of ISP's
that will lodge a complaint if they detect targeted scans -- but they
might have mellowed since, thanks to worms and viruses :-p

> or if the BEHAVE draft makes any 

The UDP draft doesn't say anything about scans or max-flows. It
recommends the use of HIGH ports I believe, and the use of LOW ports is
optional.

> piercing symmetric NATs, but it's the only one of which I'm aware.

There certainly are better solutions! Port prediction is a very
efficient one. Yutaka-san had a draft at some point where he found that
most subsequent ports are 1 or 2 higher than the previous one. 

Symmetric NAT Traversal using STUN:
http://cnscenter.future.co.kr/resource/ietf/ind-draft/draft-takeda-
symmetric-nat-traversal-00.txt

His draft pertains directly to your question since he tested UDP. From
my TCP testing, all but 1 or 2 of the symmetric NATs I encountered were
traversable with port prediction. Results are on the STUNT result page
under the 'Delta' and 'Predicted' columns.

Another solution, proposed by Biggadike et al., is to use the birthday
paradox to cut down the port-scan from 65K to a smaller number. It is
less efficient than port prediction since it still is a scan of sorts
but it is more efficient than a full port-scan, and it can handle
symmetric NATs that allocate ports randomly and are thus immune to port
prediction. See
http://sparrow.ece.cmu.edu/~adrian/projects/natblaster.pdf for details.

Hope this helps.

Cheers,
-- 
Saikat
Attachment:
signature.asc

---

From: David Barrett <[email-masked]>
Date: Sat, 25 Jun 2005 12:54:46 -0700 (PDT)

Saikat Guha wrote:
In my tests, the new TCP connection being attempted after all ports had
been exhausted would timeout; that new SYN would be dropped by the NAT
without any ICMP.  
Ah, I hadn't considered that possibility.  But, I guess it's better than 
allowing any node to DoS everyone else behind the NAT.  What does BEHAVE 
recommend in this scenario?

Wow, I had no idea they were that limited.  Does BEHAVE recommend a 
minimum 'Max Flows'?

Incidentally, are there NATs with multiple external IPs?  I'd never even 
considered this possibility, nor its ramifications.

Naturally, port-scanning is a horrible solution to the problem of 
piercing symmetric NATs, but it's the only one of which I'm aware.
There certainly are better solutions! Port prediction is a very
efficient one.
Ah, I'm sorry, I wasn't being clear -- I was categorizing "port 
prediction" as a high-precision subtype of "port scanning".  The Takeda 
draft (which is an excellent resource -- thank you for the link!) 
suggests "Multiple port prediction" (effectively a very narrow scan) as 
one of several strategies for improving port prediction success.

In my case the time elapsed between the STUN and NAT-traversal 
operations can grow to be quite large, and thus I might need to rely 
more heavily on this type of scanning that might otherwise be necessary. 
 (Or I need to rearchitect to have a smaller window, which is probably 
more likely, but I'm investigating all options.)

Another solution, proposed by Biggadike et al., is to use the birthday
paradox to cut down the port-scan from 65K to a smaller number. It is
less efficient than port prediction since it still is a scan of sorts
but it is more efficient than a full port-scan, and it can handle
symmetric NATs that allocate ports randomly and are thus immune to port
prediction. See
http://sparrow.ece.cmu.edu/~adrian/projects/natblaster.pdf for details.
So I've read through what I believe are the relevant portions of this 
paper, and I still don't "get" it.  Can you try to summarize this for me?

Hope this helps.
It does enormously.  Thanks!

-david

---

From: Saikat Guha <[email-masked]>
Date: Sun, 26 Jun 2005 01:49:07 -0700 (PDT)

On Sat, 2005-06-25 at 12:54 -0700, David Barrett wrote:
> Saikat Guha wrote:
> > the new TCP connection being attempted after all ports had
> > been exhausted would timeout
>
> What does BEHAVE recommend in this scenario?
> 
> Does BEHAVE recommend a minimum 'Max Flows'?

I don't think the UDP draft has any recommendations that address these
issues. FranÃois?

> Incidentally, are there NATs with multiple external IPs?  

Mainly corporate NATs, as far as  I know.

> > paradox to cut down the port-scan from 65K to a smaller number. 
>
> Can you try to summarize this for me?

The birthday paradox is that if there are 23 people in a room then there
is a slightly more than 50:50 chance that at least two of them will have
the same birthday (from Wikipedia). For 60 or more people, the
probability is greater than 99%. The argument can be generalized to say
that if two hosts randomly pick ~450 ports, then there is a 95% chance
that they'll pick the same port -- result from the Biggadike paper.

Intuitively, A sends out 450 packets to B's IP address but to different
ports so that 450 random holes are punched in A's symmetric NAT. B sends
450 packets addressed to A's IP address but to a random port. With 95%
probability, one of B's packets (sent to a random port) will coincide
with one of the (random) mappings allocated to A. So with ~900 packets,
you can find a working port mapping 95% of the time. 

-- 
Saikat 
Attachment:
signature.asc