Improved SYN Cookies: Looking for testers

We have a SYN cookie implementation for quite some time now but it
has some limitations with current realities for window scaling and
SACK encoding the in the few available bits.

This patch updates and improves SYN cookies mainly by:

  a) encoding of MSS, WSCALE (window scaling) and SACK into the ISN
     (initial sequence number) without the use of timestamp bits.

  b) switching to the very fast and cryptographically strong SipHash-2-4
     hash MAC algorithm to protect the SYN cookie against forgery.

The patch had been reviewed by dwmalone (cookies) and cperciva (siphash).

Please find it here for testing:

  http://people.freebsd.org/~andre/syncookie-20130708.diff

Please enable TCP logdebug to see connection status reporting by the
changes.

Detailed discussion:

The purpose of SYN cookies is to encode all necessary session state
in the 32 bits of our initial sequence number to avoid storing any
information locally in memory.  This is especially important when
under heavy spoofed SYN attacks where we would either run out of
memory or the syncache would fill with bogus connection attempts
swamping out legitimate connections.

The 32 bits of the ISN are a very limited space because we also have
to store a cryptographically strong enough hash MAC in it to prevent
spoofing of valid SYN cookies.  The result is that 24 bits have to
be dedicated to the MAC hash and only 8 bits remain available for
the session state.

The common parameters used on TCP sessions have changed quite a bit
since SYN cookies very invented some 17 years ago.  Today we a lot
more bandwidth making the use window scaling almost mandatory.  Also
SACK has become standard as it makes recovering from packet loss
much more efficient.

The original SYN cookies method only stored an indexed MSS values in
the cookie.  This obviously isn't sufficient anymore and breaks in
the presence of WSCALE.  WSCALE information is only exchanged during
SYN and SYN-ACK.  If we can't keep track of it then we severely under-
estimate the available send or receive window compounded with the fact
that with large window scaling the window size information on the TCP
segment header would be even lower numerically.

A number of years back I extended SYN cookies to store the additional
state in the TCP timestamp fields, if available on a connection.  It
has been adapted by Linux as well.  While timestamps are common among
the BSD, Linux and other *nix systems Windows never enabled them by
default and thus are not present for the vast majority of clients seen
on the Internet.

The new improvement in this patch moves all necessary information into
the ISN again removing the need for timestamps.  Both the MSS and send
WSCALE are stored in 3 bit indexed form together with a single bit for
SACK.  While we can't represent all possible MSS and WSCALE values, both
are 16 bit fields in the TCP header, in only 3 bits each this, it turns
out, isn't actually necessary.

The MSS depends on the MTU of the path and with the dominance of ethernet
the main value seen is around 1460 bytes.  Encapsulations for DSL lines
and some other overheads reduce it by a few more bytes for many connections
seen.  Based on large traffic surveys I've selected the most common values
that perfectly, or with only a small down rounding difference, represent
essentially 99.99% of all connections seen in real life.  Rounding down
to the next lower value isn't a problem as we only would send slightly
more packets for the same amount of data.

The send WSCALE is bit more tricky as rounding down would let us under-
estimate the available send space available towards the remote host.
Again it turns out that a small number of values dominates all connections
and is thus carefully selected again.  The receive WSCALE isn't encoded
at all but recalculated based on the local receive socket buffer size
when a valid SYN cookie returns.  The socket buffer size most likely
didn't change in the mean time on a listen socket.  If it did we'd have
a discrepancy for those SYN cookies in flight at the time of the change.

These improvements allow one to run with SYN cookies only on Internet
facing servers.  However while SYN cookies are calculated and sent all the
time, they're only used when the syn cache overflows due to attacks or
overload.  In that cause though you can rest assured that no significant
degradation in TCP connection setup happens anymore and that even Windows
clients can make use of window scaling and SACK.

In addition the hash MAC to protect the SYN cookies is changed from MD5
to SipHash-2-4, a much faster and cryptographically secure algorithm
recently developed by Jean-Philippe Aumasson and Daniel J. Bernstein.
Ministat makes the MAC hash calculation speed difference even more obvious:

x md5
+ siphash
+------------------------------------------------------------+
| +                                                          |
~ .                                          ..              ~
| +                                          xx              |
|++                                          xx              |
|++                                          xx              |
|++                                          xx              |
|++  +                                       xx              |
|++  +                                       xx              |
|++ ++                                       xx              |
|++ ++                                       xxx             |
|++ ++                                       xxx             |
|++ ++                                       xxx     xx     x|
|                                           |_A_|            |
| MA                                                         |
+------------------------------------------------------------+
     N           Min           Max        Median           Avg        Stddev
x  84         23467         28845         23955     23920.714     746.57003
+  84          8311          9777          8800     8840.6786     323.69754
Difference at 95.0% confidence
         -15080 +/- 174.018
         -63.0417% +/- 0.727477%
         (Student's t, pooled s = 575.39)

Happy testing.

-- 
Andre