Subject: [tcpm] Improved SYN cookies

From: Andre Oppermann <[email-masked]>
Date: Tue, 16 Jul 2013 19:42:10 +0200

This is a FYI on a recent enhancement I did to FreeBSDs SYN cookie
implementation to encode all necessary information in the ISN bits
instead of relying on the mostly absent TCP timestamp.

With it pretty much all previous shortcomings of SYN cookies are solved.

  http://svnweb.freebsd.org/base?view=revision&revision=253210
  http://svnweb.freebsd.org/base/head/sys/netinet/tcp_syncache.c?r1=253210&r2=253209&pathrev=253210

Additional comments always welcome of course.  The comments in the code
provide additional insight.

Abstract:

Improve SYN cookies by encoding the MSS, WSCALE (window scaling) and SACK
information into the ISN (initial sequence number) without the additional
use of timestamp bits and switching to the very fast and cryptographically
strong SipHash-2-4 MAC hash algorithm to protect the SYN cookie against
forgeries.

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 original SYN cookies method only stored an indexed MSS values in the
cookie.  This isn't sufficient anymore and breaks down in the presence of
WSCALE information which is only exchanged during SYN and SYN-ACK.  If we
can't keep track of it then we may severely underestimate the available
send or receive window. This is compounded with large windows whose size
information on the TCP segment header is even lower numerically.  A number
of years back SYN cookies were extended to store the additional state in
the TCP timestamp fields, if available on a connection.  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 common parameters used on TCP sessions have changed quite a bit since
SYN cookies very invented some 17 years ago.  Today we have a lot more
bandwidth available making the use window scaling almost mandatory.  Also
SACK has become standard making recovering from packet loss much more
efficient.

This change moves all necessary information into the ISS removing the need
for timestamps.  Both the MSS (16 bits) and send WSCALE (4 bits) are stored
in 3 bit indexed form together with a single bit for SACK.  While this is
significantly less than the original range, it is sufficient to encode all
common values with minimal rounding.

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.  Rounding down to the next lower value in some cases isn't a problem
as we send only slightly more packets for the same amount of data.

The send WSCALE index is bit more tricky as rounding down under-estimates
the available send space available towards the remote host, however a small
number values dominate and are 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.  A listen socket
buffer size is unlikely to change while active.

The index values for MSS and WSCALE are selected for minimal rounding errors
based on large traffic surveys.  These values have to be periodically
validated against newer traffic surveys adjusting the arrays tcp_sc_msstab[]
and tcp_sc_wstab[] if necessary.

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.

-- 
Andre

---

From: Barath Raghavan <[email-masked]>
Date: Tue, 16 Jul 2013 16:08:38 -0700

This seems like a very nice enhancement of SYN cookies.  I was reading
through the patch and had a couple of questions and comments.

In tcp_syncache.c, you say: "The MAC is computed over
(faddr||laddr||fport||lport||irs||flags||secmod)".  What is secmod?
Is it used for salting / key selection?  I found it in the code but
wasn't entirely clear on what it was supposed to represent.  Also, how
long are secmod, irs, and flags?

My comment is that you might avoid using an unvetted hash algorithm
(e.g., SipHash) even if it has a good pedigree, and when using a hash
function to build a MAC, you might prefer using a known-good
construction like HMAC.

One good alternative to using a custom hash-based MAC here is to use
AES.  Since AES is standard and the data you are computing the MAC
over is small (can be squeezed into 128 bits from what I can tell), a
nice approach to creating a fast and secure MAC is to use AES as a
secure pseudorandom function (PRF); all secure PRFs are secure MACs.
That is, given the 128-bit secret key k (that's given to SipHash in
the current design) and the message m (data to compute the MAC over),
you can compute AES_k(m) and truncate the output.  You can rotate the
secret key k periodically as in the current design.

I like your analysis that's under the headings "Vector 1" and "Vector
2", and think it's sound.

Thanks!

-Barath

> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: Andre Oppermann <[email-masked]>
Date: Wed, 17 Jul 2013 17:58:55 +0200

> long are secmod, irs, and flags?

Secmod is the memory address of the hash bucket of the SYN cache.  We
typically have 512 hash bucket heads to which the entry chains attach.
The size of secmod depends on the pointer size of the architecture and
is either 32 or 64 bits.  IRS is 32 bits and flags 8 bits.

> function to build a MAC, you might prefer using a known-good

The primary motivation for SipHash is its speed.  We do not gain anything
by using a HMAC-SHA256 which is about a thousand times slower.  We have
to make sure that we do not replace the SYN cache memory exhaustion with
a high computational overhead CPU exhaustion attack.  For example SipHash-
2-4 is three times faster than the (non-HMAC) MD5 hash we previously used.

SipHash is adequate for the purpose here as the key cracking window is
only 30 seconds.  The cryptographers I asked have expressed their confidence
in using SipHash for this purpose.  SipHash itself combines a number of
cryptographic approaches used by a couple of SHA3 finalists.  See the SipHash
paper for more details.

Using a HMAC construction is mostly necessary to prevent length extension
attacks with hash algorithms that are susceptible to it (Merkle–Damgård
construction based ones like MD5 and SHA1+2).  In our case of SYN cookies
the message length is fixed and can't be extended.  A MAC thus should be
sufficient.  SipHash already is a keyed hash MAC that doesn't need a HMAC
construction for this application.

> secret key k periodically as in the current design.

I wary of self-invented crypto approaches as they violate rule #1.  I'm
not enough of a crypto-math guy to comment on the strength or weakness
of your proposed approach.  I just want to point out that AES is quite
a complex function with a large state.  It most likely is way slower
than even the previous simple MD5 we had.  Also AES, especially in hash
constructions, is very susceptible to side channel timing attacks.  Using
a constant-time AES implementation yet makes it slower again.  Hardware
supported AES is not available on all platforms and even then it typically
is optimized for bulk throughput and not for one-off single block encryption
with comparatively high setup times.

For SYN cookies we have to optimize for speed with reasonable hash strength.
The 30 second cookie lifetime is a big constraint for any attacker.

I believe, given all current knowledge and design goals, SipHash-2-4 is the
optimal choice for SYN cookies.

> 2", and think it's sound.

Thanks for the review and feedback. :)

-- 
Andre

---

From: Joe Touch <[email-masked]>
Date: Wed, 17 Jul 2013 09:36:55 -0700

Have you addressed the impact on:
	- ISN reuse and overlap
	- other protocols that use ISN (TCP-AO comes to mind)

Joe