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 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:

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: 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.