Subject: [Tsvwg] port randomization

From: Mark Allman <[email-masked]>
Date: Wed, 28 Mar 2007 15:03:35 -0400

Folks-

I read the port randomization draft
(raft-larsen-tsvwg-port-randomization-01).  I think it is basically good
and we should publish guidance on the topic.

I did have a little bit of heartburn with the document in that I think
it puts Algorithm 2 in a worse light than is really required.  And, more
generally I thought it worried about collisions far more than is
warranted.  

Algorithm 2 is basically that you pick some point in the ephemeral port
space at random and use that port.  And, if that port is in use then you
try to next one (and, this repeats).  Two things ...

(1) Why is the chance of collision enough in this algorithm to worry
    about the two more complicated algorithms?  The ephemeral port space
    recommended in this document contains 64511 ports.  So, if N are in
    use and the random() function is nicely uniform over the space then
    the probability of picking a used port is N/64511.  To even get a 1%
    collision rate you'd need to have 645 active connections.  I would
    say that is a ton for most hosts.

(2) I don't understand why the algorithm increments the port number and
    tries again when there is a collision.  Why not just roll another
    random number?  That would then reduce the chance of collision to
    (N/64511)^x on the x-th attempt to get an unused port number.  For
    instance, if half the ports were in use the chance of generating six
    in-use ports in a row would be 1.5%.  

Algorithms 3 & 4 are harder for me to simply look at and calculate
probabilities, but my guess is that Algorithm 2' as suggested above
would be just fine and would not require tables and secrets and such.

It would be nice if the document at least tried to objectively justify
the lower collision rates of these more complicated algorithms instead
of just assuming there is a collision problem that we somehow need to
address and in fact these more complicated algorithms do address said
'problem'.  None of this is clear to me at all.

I have some nits that I'll not both the list with.

allman

---

From: Lars Eggert <[email-masked]>
Date: Thu, 29 Mar 2007 09:18:03 +0300

> generally I thought it worried about collisions far more than is

I haven't read the draft, but there are random number generators that  
create random number sequences without repetitions. Isn't that what  
one would want here?

Lars

---

From: Fernando Gont <[email-masked]>
Date: Thu, 29 Mar 2007 05:32:05 -0300

Mark,

Thanks so much for your feedback. You'll find my comments inline....

>try to next one (and, this repeats).  Two things ...

The collisions we are more concerned about are those that happen when 
the client chooses a port number for which there's a TCP in the 
TIME_WAIT state at the server (rather than "local collisions" because 
of a port number being currently in use at the client side).

The problem here is that in BSD-derived systems, if there's a 
collision the connection attempt might timeout after 75 seconds or so 
(IIRC, SYN segments received for connections in the TIME-WAIT state 
with an ISN smaller that the last sequence number seen on the 
connection are ignored). OTOH, if the server strictly implements RFC 
793, the connection attempt would lead to the assassination of the 
TIME-WAIT state (unless there's some spec that I missed).

>     say that is a ton for most hosts.

The problem that a number of users encountered in FreeBSD and NetBSD 
was that when connections were being established (and closed) at a 
high rate (for some service), the client would reuse a port number 
which would be in the TIME-WAIT state at the server. As a result, the 
connection would timeout (after 75 seconds or so). Considering the 
length of the TIME-WAIT state, this can be an issue (and has been 
reported by some users of FreeBSD and OpenBSD).

I'm personally not much concerned about local collisions, though, 
because the client does get to know that they happened and thus can 
try some other port number immediately.

>     in-use ports in a row would be 1.5%.

This is what has been implemented by those implementations that do 
"simple" port randomization (eg, FreeBSD and OpenBSD). So in that 
sense it documents "what has been done". Do you suggest we should 
include this (randomize again if there's a collision) as another alternative?

(I'd probably not replace the current "Algorithm 2", as it documents 
what is currently being done, but woould rather add it as another approach).

>'problem'.  None of this is clear to me at all.

Good point.

As a side note: wrt "collision rate", Algorithm 3 has the same 
properties as the non-random Algorithm 1. Algorithm 4 is meant to be 
an improvement of the collision-rate properties of Algorithm 3. (But 
yes, this needs to be justified).

Thanks,

-- 
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: Thu, 29 Mar 2007 07:45:07 -0300

>create random number sequences without repetitions. Isn't that what

You mean each number in the possible range is returned once before 
any number is reused? If so, that sounds like I can cause the system 
to be attacked to issue a number of connection requests to a system I 
own, and therefore know the subset of port numbers that will be used 
for the next connections.

Also, let's say that the first sequence of random numbers ends with, 
say, port "1000". How do you prevent the random number generator from 
starting the next sequence with "1000" or any of the last few numbers 
of the previous sequence? (i.e., how do you prevent it from quick 
reuse of port numbers).

Or am I missing something?

---

From: Lars Eggert <[email-masked]>
Date: Thu, 29 Mar 2007 14:19:16 +0300

On 2007-3-29, at 13:45, ext Fernando Gont wrote:
> any number is reused?

Yes.

> If so, that sounds like I can cause the system to be attacked to  
> issue a number of connection requests to a system I own, and  
> therefore know the subset of port numbers that will be used for the  
> next connections.

I don't see how - the ports of the system to be attacked will appear  
to be random.

> Also, let's say that the first sequence of random numbers ends  
> with, say, port "1000". How do you prevent the random number  
> generator from starting the next sequence with "1000" or any of the  
> last few numbers of the previous sequence? (i.e., how do you  
> prevent it from quick reuse of port numbers).

Good point. There is something else need to protect against this.

(You could just use the same sequence over and over or at least  
multiple times, but that has obvious security issues. You could also  
divide your port number space in half and switch between the two  
halves when you run out in one, with a different random sequence in  
each each time. That way, you'd only need to check that you switch  
between spaces not more often than the MSL. But I haven't fully  
thought this through.)

I need to really read the draft though.

Lars

---

From: Fernando Gont <[email-masked]>
Date: Thu, 29 Mar 2007 09:03:49 -0300

>I don't see how - the ports of the system to be attacked will appear

Let's suppose the port number space are the numbers in the range 0 to 
7.  Let's say I cause the attacked system to establish 6 connections 
to a system I own, and that the attacked system first uses port 
number 5, then port number 1, then 7, then 0, then 4, and then 3. 
Right now, I know that the next two connection requests issued by the 
attacked system will use port number 2 or port number 6.

In practice it would be harder than this (as one sequence comes after 
another, and in principle the attacker does not know where each 
sequence starts or ends). But I think it should be pretty doable.

>I need to really read the draft though.

Great. Feedback will be more than welcome.

Thanks,

---

From: Lars Eggert <[email-masked]>
Date: Thu, 29 Mar 2007 15:09:35 +0300

On 2007-3-29, at 15:03, ext Fernando Gont wrote:
> Let's suppose the port number space are the numbers in the range 0  
> to 7.  Let's say I cause the attacked system to establish 6  
> connections to a system I own, and that the attacked system first  
> uses port number 5, then port number 1, then 7, then 0, then 4, and  
> then 3. Right now, I know that the next two connection requests  
> issued by the attacked system will use port number 2 or port number 6.
>
> In practice it would be harder than this (as one sequence comes  
> after another, and in principle the attacker does not know where  
> each sequence starts or ends). But I think it should be pretty doable.

Right. But I don't see how this is a realistic concern if you  
randomize of the ephemeral ports. If you can open thousands of  
concurrent connections to a destination, you have other means of  
attack anyway.

Lars

---

From: Fernando Gont <[email-masked]>
Date: Thu, 29 Mar 2007 10:44:43 -0300

>concurrent connections to a destination, you have other means of

Well, the goal of the i-d is port randomization (although it also 
argues about using a larger port range for the ephemeral ports, too). 
So, while there are certainly other threats... we have to make that one right.

---

From: Mark Allman <[email-masked]>
Date: Thu, 29 Mar 2007 09:21:04 -0400

> of a port number being currently in use at the client side).

I see.  So, that makes the collisions way more expensive.  OK.

(The more expensive the collisions the more we should try to avoid them,
for sure.)

> sense it documents "what has been done". 

OK.

> Do you suggest we should include this (randomize again if there's a
> collision) as another alternative?

It seems easy and obvious to me.

> yes, this needs to be justified).

This is my very high-order bit.  If this was all quantified then it
would be much easier to reason about these things and to figure out if
the more complicated schemes are worth it or not.

allman

---

From: Michael Vittrup Larsen <[email-masked]>
Date: Fri, 30 Mar 2007 11:30:58 +0200

A few comments:

* The intention is to 'randomise' ports _between_ hosts.  The port sequence 
really do not matter and any sequence can be used as long as the starting 
point/offset is different for each F(local_IP, remote_IP, remote_port).

* Using a sequential port search-range has the nice property that reuse is 
postponed as long as possible and hopefully the port is then no longer in use 
when the 'next_ephemeral_port' wrap-around (thus assuming port wrap-around 
time is less then the average connection lifetime).  Having a single 
global 'next_ephemeral_port' reduce the probability of this assumption and 
having e.g. peer dependent 'next_ephemeral_port's increase the probability of 
this assumption.

* In most cases using a peer dependent random sequence (with the property 
mentioned below) will reduce the vulnerability _between_ hosts while still 
retaining the property that reuse is postponed as long as possible.

Also, please remember that this is obfuscation and simplicity is an important 
requirement.  A possible solution should not be overdone.

/Michael

-- 
This communication is confidential and intended solely for the addressee(s). 
Any unauthorized review, use, disclosure or distribution is prohibited. If 
you believe this message has been sent to you in error, please notify the 
sender by replying to this transmission and delete the message without 
disclosing it. Thank you.

E-mail including attachments is susceptible to data corruption,interruption, 
unauthorized amendment, tampering and viruses, and we only send and receive 
e-mails on the basis that we are not liable for any such corruption, 
interception, amendment, tampering or viruses or any consequences thereof.

---

From: Michael Vittrup Larsen <[email-masked]>
Date: Fri, 30 Mar 2007 12:17:08 +0200

A few comments:

/Michael