Using cookies to defeat syn-flooding

[Ron Rivest <[e-mail]>]

Here is a thought on a scheme for defeating swamping (syn-flooding)
attacks, together with an improvement suggested by Butler Lampson.
Since I'm not an expert on network protocols, it needs review by those
who are...

Flooding attack (paragraph to define problem and establish terminology):

Assume that the scenario is that machine A receives a SYN packet
allegedly from machine B.  Currently A returns its own SYN packet, after
logging the connection request in a queue.  If the original SYN packet
was bogus, and had a spoofied source ip address, then A is left waiting
for B to complete the handshake until timeout, tying up A's resources.
With many bogus SYN packets received, A is clogged up and A's legitimate
users are denied service.

Analysis:

The problem is that A is allocating resources (i.e. making queue entries)
with every SYN packet received.  

The idea:

Defer A's allocation of resources until A has some confirmation that 
B is "real". (I.e. until the third message of the three-message protocol
is received from B).

How:

When A receives the first SYN packet, it does NOT generate a queue
entry.  Rather, it sends B, as part of its return SYN packet, 
a "cookie" that contains the information that the queue entry would have:
	-- source id of the SYN packet received
	-- when to time the connection request out
	-- port number
	-- other stuff (?)
The cookie would contain this material in the clear, together with
a cryptographic checksum (MAC) on this data, computing from the data
of the cookie and a secret key known only to machine A. 

When B replies, he returns the cookie, which A checks.  A cookie with
an invalid MAC is discarded.  A cookie with a good MAC that has not
timed out and which has not already been honored will generate a new
connection.  (Note that to prevent replays A must keep track of which
connections have been opened within the last cookie-time-out period,
but A does not need to keep track of cookies that have never been
returned.)

In this way, syn-flooding is defeated.


Improvement:

Butler Lampson suggested that the cookie might actually be squeezed
into the current protocol.  I don't know enough of the details to
tell.  He thought that A's return SYN includes a 32-bit number which
is returned (slightly modified) in B's final ACK.  This might be used
to store just the MAC for the cookie, if the rest of the cookie could
be reconstructed from the material already in the second message.
More likely, the 32-bit quantity would have to code both the time-out
and the MAC.  (Allocate say 12 bits for time out to the minute mark
and 20 bits for checksum; change to a new crypto key whenever every
2^{12} minutes.)  

It would be neat if this improvement could fit within the current
implementation of IPv4.  

Perhaps something like this would be valuable for IPv6 in any case...

Comments appreciated ...

	Ron Rivest