TCP SYNCOOKIES - SYN FLOOD

Mail service for Panix, an ISP in New York, was shut down by a SYN flood starting on 6 September 1996. A week later the story was covered by the RISKS Digest, the Wall Street Journal, the Washington Post, and many other newspapers.

SYN flooding had been considered by security experts before. It was generally considered insoluble. See, for example, ``Practical UNIX and Internet Security,'' by Garfinkel and Spafford, page 778:

The recipient will be left with multiple half-open connections that are occupying limited resources. Usually, these connection requests have forged source addresses that specify nonexistent or unreachable hosts that cannot be contacted. Thus, there is also no way to trace the connections back. ... There is little you can do in these situations. ... any finite limit can be exceeded.

Large SYN queues and random early drops make SYN flooding more expensive but don't actually solve the problem.
SYN cookies are now a standard part of Linux and FreeBSD. To enable them, add

echo 1 > /proc/sys/net/ipv4/tcp_syncookies

to your boot scripts.

What are SYN cookies?
SYN cookies are particular choices of initial TCP sequence numbers by TCP servers. The difference between the server's initial sequence number and the client's initial sequence number is

* top 5 bits: t mod 32, where t is a 32-bit time counter that increases every 64 seconds;
* next 3 bits: an encoding of an MSS selected by the server in response to the client's MSS;
* bottom 24 bits: a server-selected secret function of the client IP address and port number, the server IP address and port number, and t.

This choice of sequence number complies with the basic TCP requirement that sequence numbers increase slowly; the server's initial sequence number increases slightly faster than the client's initial sequence number.

A server that uses SYN cookies doesn't have to drop connections when its SYN queue fills up. Instead it sends back a SYN+ACK, exactly as if the SYN queue had been larger. (Exceptions: the server must reject TCP options such as large windows, and it must use one of the eight MSS values that it can encode.) When the server receives an ACK, it checks that the secret function works for a recent value of t, and then rebuilds the SYN queue entry from the encoded MSS.

A SYN flood is simply a series of SYN packets from forged IP addresses. The IP addresses are chosen randomly and don't provide any hint of where the attacker is. The SYN flood keeps the server's SYN queue full. Normally this would force the server to drop connections. A server that uses SYN cookies, however, will continue operating normally. The biggest effect of the SYN flood is to disable large windows.

Blind connection forgery
If an attacker guesses a valid sequence number sent to someone else's host then he can forge a connection from that host.

Attackers can try to cryptanalyze the server-selected secret function: inspect a series of valid cookies and then intelligently guess a new cookie. For a secure function, the attacker's chance of success is not noticeably better than the chance of success for a uniform random guess. Secret-key message authenticators are designed to provide exactly this type of security. The following function is extremely fast and appears to be secure: encode the input in 16 bytes; feed the result through Rijndael with a secret key; extract the first 24 bits of the result.

No matter what function is used, the attacker will succeed in a connection forgery after millions of random ACK packets. Servers can make this attack more expensive in two ways:

* Keep track of the most recent SYN queue overflow time (for each SYN queue, not in a global variable). Don't rebuild missing SYN entries if there hasn't been a recent overflow. This stops ACK forgeries from passing through SYN-blocking firewalls.
* Add another number to the cookie: a 32-bit server-selected secret function of the client address and server address (but not the current time). This forces the attacker to guess 32 bits instead of 24.

A new protocol with 128-bit sequence numbers would make blind connection forgeries practically impossible.