D. J. Bernstein
TCP/IP

SYN cookies

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 use cryptographic techniques to solve the problem. I pointed out how easy this was on 16 September 1996; Eric Schenk and I worked out the gory details over the next few weeks. Jeff Weisberg released a SunOS implementation in October 1996, and Eric Schenk released a Linux implementation in February 1997.

SYN cookies are now a standard part of Linux and FreeBSD. They are, unfortunately, not enabled by default under Linux. 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.

Who invented SYN cookies?

As far as I know, Phil Karn was the first to design an Internet protocol that used cookies to protect against blind denial-of-service attacks. But the idea is much older than this. Cookies can be found in sweepstakes mailings, for example.

I think I was the first to point out that TCP servers can use cookies without any changes to the TCP protocol. (Perry Metzger subsequently claimed that he had pointed this out earlier. However, Metzger didn't respond when I asked him for copies of the relevant messages. NANOG archives show that Metzger stated on 9 September 1996 that cookies would require a new ``TCP++'' protocol, and on 17 September 1996 that ISPs had to filter their outbound packets.)

My first proposal didn't comply with the TCP requirement to use increasing initial sequence numbers. Eric Schenk had the idea of adding something to the client's initial sequence number.

I proposed time-dependent SYN cookies. The time dependence prevents attackers from (1) collecting valid cookies at a public computer and subsequently (2) reusing the cookies in a blind attack from somewhere else.

SYN cookie monsters

A few people (notably Alexey Kuznetsov, Wichert Akkerman, and Perry Metzger) have been spreading misinformation about SYN cookies. Here are some of their bogus claims:

SYN cookies ``present serious violation of TCP protocol.'' Reality: SYN cookies are fully compliant with the TCP protocol. Every packet sent by a SYN-cookie server is something that could also have been sent by a non-SYN-cookie server.
SYN cookies ``do not allow to use TCP extensions'' such as large windows. Reality: SYN cookies don't hurt TCP extensions. A connection saved by SYN cookies can't use large windows; but the same is true without SYN cookies, because the connection would have been destroyed.
SYN cookies cause ``massive hanging connections.'' Reality: With or without SYN cookies, connections occasionally hang because a computer or network is overloaded. Applications deal with this by simply dropping idle connections.
SYN cookies cause ``serious degradation of service.'' Reality: SYN cookies improve service. They do take a small amount of CPU time to compute, but that CPU time has to be spent anyway for hard-to-predict sequence numbers; see RFC 1948.
SYN cookies cause ``magic resets.'' Reality: SYN cookies never cause resets.

These people also have the annoying habit of crediting their bogus claims to other people, such as me. I don't know whether to attribute this to malice or stupidity; either way, I would like the record to be set straight.

I invited Kuznetsov to either retract or defend his claims. He refused to do so. I'm sure he's aware by now that his claims are false, and that any attempted defense will be promptly ripped to shreds; but he's still not admitting his errors. It's unfortunate that he doesn't have more respect for the truth.

I also invited Akkerman to either retract or defend his claims. He did not respond.