Subject: Re: [Tsvwg] Follow-up : Effects of port randomization with TCP TIME-WAIT state

From: "Patrick Tate (ptate)" <[email-masked]>
Date: Fri, 5 Sep 2008 15:11:54 -0400

Hi Fernando,

Please see <ptate> below.

At 02:52 p.m. 03/09/2008, Anantha Ramaiah (ananth) wrote:

    #1 explain why port randomization is useful and leave the algorithms
up
    to the implementations. Don't even mention it.

    #2 explain a handful of algorithms to illustarte PR.

    #3 also talk about the TIME-WAIT issue since it is important as far
as
    TCP is concerned. SCTP and other protocols don't have the TIME-WAIT,
    FWIW.

    #4 elaborate TIME-WAIT issue w.r.t PM (since it is important same
    rationale as #3) and mention a few algorithms for the same.

    Fernando's draft does #1 to #3 above, but our draft focusses on #4
    above.

I'm not sure why you think so. Our port randomization draft does #1
through #4. Now I have put the discussion of collision of
connection-id's in a separate section. But most (if not all) of the text
was already there.

    Anyways, we feel that this would be a good value addition to the PM
    draft, but would like to hear the consensus of the WG group, more
    importantly does the WG feel that it is an important issue that is
worth
    documenting?

The issue is very simple: when there are collisions of the connection-id
in the remote peer, what happens is what RFC 1337 says. The only new
thing with port randomization is that collisions of connection-id's may
happen more frequently than before, and therefore you may face the
problems described in RFC 1337 in scenarios in which you didn't use to
face them.

However, if algorithm #3 is in place, the situation is exactly the same
as with the traditional BSD ephemeral port selection algorithm. And with
algorithm #4 in place, the situation is even *better* (and you don't
need special magic to handle the issue of collision-id's).

<ptate>  The problem as I see it with algorithm 3 and 4 from the draft
is that for a single given attempt to produce a unique port, these
algorithms can fail to attempt all possible ports.  Eg., for algorithm
3, if F() yields a result such that (((max_ephemeral - mix_ephemeral) %
F()) == 0), the algorithm will loop through,  trying the same set of
port values repeatedly for count attempts without truly attempting all
of the possible ports.  F() has to be chosen carefully to ensure the
modulus with respect to the given port range is a good result.  There
are other modulus values other than 0 (like any even modulus results
when (max_ephemeral - min_ephemeral) is even) that will cause similar
poor behavior for the algorithm.  Maybe I have not read the latest
version of the draft and this is discussed (mine is dated Feb 25, 2008)?

<ptate> And even with a table as algorithm 4 suggests, one cannot be
truly guaranteed to try all possible ports or even close to all possible
ports in a given range to see if there are any ports available.  I am
assuming here for both of these points I make that local IP address,
remote IP address, and remote port are all the same, because that is the
case we are trying to address and discuss with our document.

-Patrick

Thanks!

Kind regards,

--
Fernando Gont
e-mail: fernando at gont.com.ar || fgont at acm.org PGP Fingerprint:
7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1

---

From: Fernando Gont <[email-masked]>
Date: Fri, 05 Sep 2008 16:28:17 -0300

>version of the draft and this is discussed (mine is dated Feb 25, 2008)?

All the versions of the draft have always included the same 
algorithm. But the algorithm does not work like that. It starts at 
some offset given by F(), and then tries all the possible ports in 
the ephemeral port range until it selects one that does not result in 
a collision of conenction-id's.

>case we are trying to address and discuss with our document.

This is the code for algorithm #3:

      /* Initialization at system boot time */
      for(i = 0; i < TABLE_LENGTH; i++)
          table[i] = random() % 65536;

      /* Ephemeral port selection function */
      num_ephemeral = max_ephemeral - min_ephemeral + 1;
      offset = F(local_IP, remote_IP, remote_port, secret_key);
      index = G(offset);
      count = num_ephemeral;

      do {
          port = min_ephemeral + (offset + table[index]) % num_ephemeral;
          table[index]++;

            if(five-tuple is unique)
          return port;

         count--;

      } while (count > 0);

      return ERROR;

It does try all the ports in the ephemeral port range.

Thanks!

Kind regards,

--
Fernando Gont
e-mail: [email-masked] || [email-masked]
PGP Fingerprint: 7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1

---

From: "Patrick Tate (ptate)" <[email-masked]>
Date: Fri, 5 Sep 2008 16:27:11 -0400

> -----Original Message-----
> From: Fernando Gont [mailto:[email-masked]] 
> Sent: Friday, September 05, 2008 3:28 PM
> To: Patrick Tate (ptate); [email-masked]
> Subject: Re: [Tsvwg] Follow-up : Effects of port 
> randomization with TCP TIME-WAIT state
> 
> algorithm. But the algorithm does not work like that. It 
> starts at some offset given by F(), and then tries all the 
> possible ports in the ephemeral port range until it selects 
> one that does not result in a collision of conenction-id's.

<ptate> OK, I see the next_ephemeral++ now in algorithm 3 in your draft,
so I agree it does try all ports, my apologies.

<ptate> However, doesn't this simply resolves basically to the
traditional incremental port selection algorithm given a single local
ip, remote ip, remote port combination and does not provide much port
obfuscation for that case (other than for the initial selected port
value)?

<ptate> I can see where obfuscation is achieved if connections are made
where any of the local ip, remote ip, or remote port are varied, but not
for the problematic case our draft is addressing. 

<ptate> It seems algorithm 4 also has similar behavior given a single
local IP, remote IP, and remote port combination as well if I am
following it correctly.  Again, I see where good obfuscation with
incrementally increasing port values are well achieved by this algorithm
for the case where any of local ip, remote ip, or remote port are
varied, but not if all these values stay the same, in which case this
resolves to the traditional incremental port selection algorithm with
just the initial port randomized.

<ptate> Or am I misunderstanding these algorithms altogether?

> >truly guaranteed to try all possible ports or even close to all 
> >possible ports in a given range to see if there are any ports 
> >available.  I am assuming here for both of these points I make that 
> >local IP address, remote IP address, and remote port are all 
> the same, 
> >because that is the case we are trying to address and 
> discuss with our document.
> 

<ptate> FYI, looks like this is the code for algorithm 4 :-).

Thanks!
-Patrick

> 
> Thanks!
> 
> Kind regards,
> 
> --
> Fernando Gont
> e-mail: [email-masked] || [email-masked] PGP 
> Fingerprint: 7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1
> 
> 
> 
> 
>

---

From: Fernando Gont <[email-masked]>
Date: Sat, 06 Sep 2008 05:46:18 -0300

At 05:27 p.m. 05/09/2008, Patrick Tate (ptate) wrote:

>ip, remote ip, remote port combination

Yes. And that's precisely it's goal.

>and does not provide much port

It does provide obfuscation, because an off-path attacker cannot 
predict the value of F().

>for the problematic case our draft is addressing.

Your draft is algorithm #1 of our draft, plus (an 
implementation-compromise) TIME_WAIT state on the side of the client. 
The only scenario in which that TIME_WAIT implementation approach 
will help is when connections are issued to a single service at a 
single system, and connections can have very varying life-spans. 
However, it is way too restrictive when you issue connections to 
different services and different hosts, as you put a *port* in the 
TIME_WAIT state, rather than the four-tuple.

>just the initial port randomized.

What's the problem if an attacker can predict the port numbers to be 
used for connection requests sent to *him*? :-)

The goal of port randomization is that you cannot predict which port 
numbers will be used for future connection requests sent to some 
other host other than yours.

Thanks!

Kind regards,

---

From: "Anantha Ramaiah (ananth)" <[email-masked]>
Date: Sat, 6 Sep 2008 22:30:32 -0700

Fernando, 

> TIME_WAIT state, rather than the four-tuple.

This is one of the suggestions which I received when we posted the draft
initially. Our version 2 would incorporate this along with other
suggestions.

I also need to get back to your other email, which I'll do when I get
more leisure time.

-Anantha

---

From: Fernando Gont <[email-masked]>
Date: Sun, 07 Sep 2008 05:20:09 -0300

>initially. Our version 2 would incorporate this along with other

The problem with the TIME-WAIT approach is that:

* If connections are issued to a single host/service at a high rate, 
you could implement TIME-WAIT as in your approach. But it imposes 
connection-rate limit of ephemeral_range/2*MSL... and I doubt you 
want to impose such a limit.

* If conenctions are issued to different hosts/services at a high 
rate, you'd have to implement a real TIME-WAIT state (i.e., put the 
*four*-tuple in the TIME-WAIT state). But this is very expensive: at 
least 12 bytes four each connection (you could put a "hash" in the 
TIME-WAIT state, but....)

However, IMO your draft doesn't have to do with port randomization, 
but with implementation strategies for the TIME-WAIT state on the client side.

Thanks!

Kind regards,

---

From: Mark Allman <[email-masked]>
Date: Mon, 08 Sep 2008 13:59:34 -0400

I took a spin through this draft and I don't really see the point, I
guess.  I find it maddening.  A few comments ...

  + Basically, this draft says "ports can collide if you use the port
    randomization stuff from the other draft".  OK, but that draft says
    as much.  And, then this draft essentially goes on to say that it
    has been observed in the field.  The insinuation is that this is a
    Really Big Deal.  However, the maddening part is that even though
    there is apparently this "experience" the draft does not quantify it
    in any way.  Does this mean you're seeing 3 collisions a week where
    before you saw none?  30?  300?  3000?  What is the magnitude of
    this "problem"?  Should I care?

  + And, method 2... This is mis-labeled.  If you have to keep a
    timestamp per tuple then it isn't a bit-array.

  + When describing method 3 you note that the cost of method 2 is
    pretty low in terms of memory (~8KB, as you note).  But, this is
    just wrong because (a) you fail to include the overhead of keeping
    timestamps around and (b) it's 8KB **for each (IP,IP,service)
    tuple**.

  + You miss a method that might work well for most machines: just
    keeping a list of the tuples and the time at which they were last
    used.  In the same memory as for a bit array of the whole port space
    you could track 400+ connections (using gross math).  That seems
    like plenty for a large class of machines.

  + In comparison to methods 1 & 2, method 3 seems like the obvious
    approach to recommend.  I wonder why you even bother sketching 1 &
    2?  Seems like in practical terms it would need to be 3 or what I
    sketched in the last bullet.

The last two bullets above are really me being academic.  I think before
we go down the path of recommending that hosts track this sort of stuff
we should understand the problem.  You have not demonstrated there is a
problem that needs to be solved.

allman