Re: [tcpm] poll for adopting draft-gont-tcp-security

[" Ilpo Järvinen " <[e-mail]>]

On Mon, 29 Jun 2009, Fernando Gont wrote:

> Matt Mathis wrote:
> 
> > > > I read all of 2 pages before I found something that, if significantly
> > > > deployed, would haunt some Internet users for a very very long time (p
> > > > 43, SACK resource exhaustion).
> > >
> > > I guess you are arguing against the proposed limit of 16 for the maximum
> > > number of sack holes? I understand you could argue that this value
> > > could/should be raised. However, IIRC I based my proposal on existing data
> > > on the number of holes.
> [....]
> > > I guess/hope you are not arguing against enforcing limits, but about the
> > > specific value proposed in the I-D. And the reason for submiting this I-D
> > > as a IETF I-D is exactly to discuss these issues and get consensus on
> > > e.g., what the proper/safe value should be for this limit.
> > The current limits are workaround for using inappropriate algorithms for
> > maintaining the  SACK scoreboard.
> 
> It's more than that. If you don't enforce any limits, you could get a system
> to commit lots of memory for the scoreboard. Not enforcing limits is a highway
> to buffer overflows and other type of attacks. You must impose *some* limit.

To me most sensible limit seems to be number of outstanding segments (not 
bytes) divided by two. There should be really very little reason to go 
beyond that. But of course not all implementations can directly 
determinate the number of outstanding segments (and would have to use some 
divided by MSS heurestics).

> > The easy way to implement the scoreboard has cost O(N^2).  However there is
> > at least one OS that uses an O(N*ln(N)) scoreboard, and O(N) might be
> > possible.  (These are the total cost of the worst case recovery at window
> > size N, so O(N) total cost is constant cost per ACK.)
> 
> Could you provide details of the algorithms you mention, references, etc.?

Any linked-list based implementation is basically O(n^2) under 
worst case attack, but they can also end up being that even in 
non-malicious cases too depending on the direction of lookups
and/or loss pattern.

O(n) for normal patterns seems well possible due to rather well 
predictable order of processing, obviously O(n*log n) is necessary
for malicious.

Also similar issues easily exist in the out-of-order segment handling at 
the receiver side.

-- 
 i.