% todo:
%   * include math about network rates and CPU rates, relate to DDOS
%   * DDOS is more trouble for the network 
%   * tests: reducing backlog from 128 to 5 doesn't make pauses more
%            consistent 
%   * tests: turning on SYN cookies doesn't affect the pause
% 

\definefilesynonym
  [font-lbr] [font-pos]
\usemodule
  [pre-01]
\setupwhitespace
  [medium]

\setupexternalfigures
  [directory=figs]
\useexternalfigure
  [synkill2] [DOS-synkill-2]
\useexternalfigure
  [synkill6] [DOS-synkill-6]
\useexternalfigure
  [results] [results.1]

\definecolor [BackgroundColor]  [r=.8, g=.8, b=.8]
\definecolor [InteractionColor] [r=.1, g=.5, b=.8]
\definecolor [ContrastColor]    [r=.8, g=.1, b=.2]

\starttext
\startstandardmakeup
\midaligned{{\tfd SYN Cookies}}
\blank[2*big]
\midaligned{{\tfc Ed L.~Cashin}}
\blank[6*big]
\midaligned{{\tfb (B)RATS}}
\midaligned{{\tfc November 2001}}
\stopstandardmakeup

\Topics{Topics}

\Topic{The Solution and the Problem}

\Subject{Solution: SYN Cookies}

Let's start with the denouement: you don't need a queue of tcpcb's.

\startitemize [4]
\item	use cryptographic hashing to make a sequence number
\item	don't allocate tcpcb
\stopitemize

\Subject{Problem: tcpcb Limit}

In the first part of the {\sc tcp} handshake, a {\sc tcp} control
block of about 140 bytes is traditionally allocated to store
information about the new connection.

Here is the {\sc tcp} handshake that we saw in the synkill paper.

\placefigure
  {{\sc tcp} handshake}
  {\clip[width=10cm,
         height=5cm,
         hoffset=10.5cm,
         voffset=2.5cm]{\externalfigure[synkill2]}}

\startitemize [4]
\item If O.S. must allocate a tcpcb for each incoming {\sc syn} packet and \dots
\item if there's a limit to the number that may be allocated
\stopitemize
\dots\ then a {\sc syn} flood may prevent new {\sc tcp} connections.

\Topic{Implications}

The implications of SYN Cookies as a solution to the vulnerability of
having a finite half-open connection queue.

\Subject{Scales Well}

Different from increasing the limit.

Since the queue is eliminated entirely, this specific solution to this
specific problem should scale well, even under currently|-|popular
{\sc ddos} attacks through fat pipes.

\Subject{Firewall}

A firewall with {\sc syn} cookies turned on could play one of the
roles described in the synkill paper.

\placefigure
  {invulnerable firewall}
  {\clip[width=9.5cm,
         height=4.25cm,
         hoffset=10.25cm,
         voffset=2.5cm]{\externalfigure[synkill6]}}

\Subject{Hosts}

``If it's possible to make a firewall immune to {\sc dos} via {\sc
syn} flooding, why not make the hosts invulnerable?''

\Subject{Caveats}

Even without the tcpcb limit, other resources are limited.

Examples: Network bandwidth; {\sc cpu}.

\Topic{The Method}

\Subject{People}

\startitemize [3]
\item Dan Bernstein
\item Eric Schenk
\item Andi Kleen
\stopitemize

\Subject{Disadvantages}

\startitemize [4]
\item no fancy {\sc tcp} options during {\sc syn} flood.
\item limited choice of {\sc mss} values.
\item lost {\sc ack} may hang clients.
\item brute-force sequence number guessing

      inject 1 per $2^{27}$ packets
\stopitemize

Also, unlike the synkill solution, only one host is protected.

\Subject{The Algorithm: ISN}

2 constant secret keys: ``sec1'' and ``sec2''.

A constant sorted table of 8 common {\sc mss} values, ``msstab''.

Keep track of a ``last overflow time.''

Maintain a counter that increases slowly over time and never repeats,
such as ``number of seconds since 1970, shifted right 6 bits.''

When a {\sc syn} comes in from $(saddr,sport)$ to $(daddr,dport)$ with
{\sc isn} $x$, find the largest $i$ for which $msstab[i] \leq$ the
incoming {\sc mss}. Compute \dots

$$
\eqalign{z =\, &{\tf MD5}(sec1,saddr,sport,daddr,dport,sec1)\cr
             &+ x\cr
	     &+ (counter \ll 24)\cr
             &+ ({\tf MD5}(sec2,counter,saddr,sport,daddr,dport,sec2)\>
                \%\> (1 \ll 24))\cr}
$$

\dots\ and then \dots

$$
   y = (i \ll 29) + (z \>\%\> (1 \ll 29)).
$$

\dots\ where $y$ is the {\sc isn}.
   
\Subject{The Algorithm: Handshake Step 2}

If not out of memory for tcpcb's, create a tcpcb as usual, with $y$ as
our {\sc isn}. Send back a {\sc synack} packet.

Else the queue is full, so set the ``last overflow time'' to the
current time and send the {\sc synack} anyway, with all fancy options
turned off.  Do not allocate tcpcb.

\Subject{The Algorithm: Handshake Step 3}

\startitemize [n]
\item Look for a $(saddr,sport,daddr,dport)$ tcpcb. If it's there,
      done. 
\item If the ``last overflow time'' is earlier than a few minutes
      ago, give up.
\item Figure out whether {\sc isn} makes sense.  This means
          recomputing $y$ as above, for each of the counters that
          could have been used in the last few minutes (say, the last
          four counters), and seeing whether any of the $y$'s match
          the {\sc isn} in the bottom 29 bits. If none of them do,
          give up.
\item Create a new tcpcb. The top three bits of our {\sc isn} give a usable
          {\sc mss}. Turn off all fancy options.
\stopitemize

% \Topic{Does it Work?}
% 
% \Subject{Network Speeds}
% 
% \Subject{DOS Example}
% 
% \Subject{DOS Prevented}

\Topic{Current Status}

\Subject{Kleen's Advice}

Andi Kleen, who implemented the syncookie feature in the Linux kernel,
says this:

\starttyping
From: Andi Kleen <ak@suse.de>
Subject: Re: testing syncookie functionality
To: Ed L Cashin <ecashin@terry.uga.edu>
Date: Tue, 6 Nov 2001 01:17:05 +0100

Hi,

First I would suggest not putting much time anymore
into syncookies.  They're basically obsolete because
the cost of not using time stamps and SACK is too high,
and linux has the infrastructure now to keep a big
enough real queue that makes them not really needed
anymore.

Also they don't have enough bits to be secure from
brute force.
\stoptyping

\Subject{Bernstein's Perspective}

\starttyping
From: "D. J. Bernstein" <djb@cr.yp.to>
Subject: Re: SYN cookies testing and use
To: Ed L Cashin <ecashin@terry.uga.edu>
Date: 9 Nov 2001 19:58:17 -0000

Kleen is an idiot. Here's what Google's Jim Reese said
about SYN cookies in a talk a year ago:

   Security. Obviously a big issue, as we get more and
   more of these SYN flood attacks. ... The script
   kiddies are out there and they're out there to get
   us. We've seen a _tremendous_ increase in the amount
   of attacks on us as we grow more popular. It's
   inevitable. Every site sees it.

   SYN flood attacks are actually extremely well
   handled now by the Linux kernel with SYN
   cookies. They work extremely well. If you're not
   using them, you should be.

\stoptyping

\Subject{Valuable TCP Options}

Today some {\sc tcp} options are more critical than in 1996.

\startitemize [4]
\item {\sc sack} and {\sc d-sack}

  Selective acknowledgement and duplicate {\sc sack}.

\item timestamping

  For {\sc rtt} calculation and also protection against wrapped
  sequence numbers.

\item window scaling
\stopitemize

These options are especially important for ``long fat pipes.''

\Subject{Random Drop}

The ``intelligent dropping algorithms'' Kleen refers to are likely
variants on random drop.

Bernstein: random drop adversely affects legitimate clients'
new connections.

\Subject{Tests}

\startitemize [4]
\item lower the queue size 

  similar to queue full of legitimate users
\item three hosts
  \startitemize [2]
  \item attacker
  \item victim
  \item monitor
  \stopitemize
\item the tools
  \startitemize [2]
  \item synbo
  \item connect.rb
  \item icmpecho.rb
  \stopitemize
\page
\item the results
\stopitemize
\placefigure
  {without {\sc syn} cookies}
  {\externalfigure[results]}

\Subject{Conclusion}

SYN cookies solve the full|-|queue problem but \dots

\startitemize [4]
\item the cost of missing fancy {\sc tcp} options is greater today
\item {\sc syn} floods cause other problems, like network congestion
\stopitemize

\Topic{Appendices}

\Subject{Resources}

\startitemize
  [n][left={[},right={]}]
\item Dan~J.~Bernstein.  {\sl SYN Cookies.\/}
	http://\-cr.yp.to/\-syncookies.html
\item Dan~J.~Bernstein.  personal email correspondence, Nov.~2001.
\item Brendan Conoboy and Erik Fichtner.  {\sl ipfilter HOWTO.\/}
	http://\-www.\-ob\-fuscation.org/\-ipf/\-ipf-howto.txt 
\item Andi~Kleen.  personal email correspondence, Nov.~2001.
\item Christoph~L.~Schuba, et al.  {\sl Analysis of a Denial of
	Service Attack on TCP.\/}  (The ``synkill paper''.)
\item W.~Richard~Stevens.  {\sl
	TCP/IP Illustrated, V.1, The Protocols.\/}
	Addison|-|Wesley, 1994. 
\item W.~Richard~Stevens and Gary~R.~Wright.  {\sl
	TCP/IP Illustrated, V.2, The Implementation.\/}
	Addison|-|Wesley, 1995.
\item W.~Richard~Stevens. {\sl UNIX Network
	Programming, V.1, second ed.\/}  Prentice Hall PTR, 1998.
\stopitemize

\Subject{Packet Rates}

% figure out nice-looking width for columns based on text width
% 
\newdimen\colwidth
\colwidth=.55\textwidth
\colwidth=.3\colwidth

\placetable
  [here] [tab:pktrates]
  {packet rates of popular networks}
\starttable 
  [|w(\colwidth) l|w(\colwidth) r|w(\colwidth) r|]
\HL
\NC \bf Net Type \NC \bf Mbps \NC \bf SYN's/sec \NC\SR
\HL
\NC T1 \NC 1.5 \NC 4,825 \NC\MR
\NC 10 Base-T \NC 10.0 \NC 31,025 \NC\MR
\NC T3 \NC 45.0 \NC 140,621 \NC\MR
\NC 100 Base-T \NC 100.0 \NC 310,025 \NC\MR
\NC OC-3 \NC 155.0 \NC 484,375 \NC\MR
\NC GigE \NC 1,000.0 \NC 3,100,250 \NC\MR
\HL
\stoptable

\page

\null
\vfill
\midaligned{fin}
\vfill

\stoptext