When cryptologists Daniel J. Bernstein and Jeff Weisberg made SYN cookies mainstream as a way of mitigating SYN floods, the problem was considered insoluble. It was September 1996, following the SYN flood, which had shut down the mail service for Panix, the Internet Service Provider in New York. In a blog post on his own website, Bernstein describes the other proposed solutions at the time (large SYN queues and random early drops) as “more expensive but [they] don’t actually solve the problem”; by contrast, “SYN cookies use cryptographic techniques to solve the problem”.
This makes them much cheaper than other mitigation techniques because SYN cookies are stateless. They do not set up a session and route lookups, and maintain no connection request queues. Therefore, CPU and memory usage are dramatically reduced, leading to lower processing costs.
Bernstein defines SYN cookies as “particular choices of initial TCP sequence numbers by TCP servers” i.e. it only encodes whatever it needs to remember in the TCP sequence number that it sends in the SYN-ACK. When the ACK is received, the server checks that the secret function works for a recent value of t, and proceeds to rebuild the SYN queue entry from the encoded MSS. Essentially, until it receives the final ACP packet, it doesn’t hold onto the rest of the communication and only picks it back up from the value of the SYN cookie in the packet.
A TCP sequence number comprises of 32 bits, so the server needs to fit the “state” within 32 bits. SYN cookies use 5 bits for a timestamp, 3 bits for MSS, and 24 bits of “output of a cryptographic function”. Therefore, when the server receives an ACK which appears to be a response to a SYN-AC (the one with a cookie), then the server has to view it as the third part of the TCP handshake, and allocate the resources for a fully open connection. This happens only if the cookie value is correct (i.e. it matches the value sent in the ACK). The attacker knows the current time and can guess/observe the three-bit encoding for the MSS value, but there are now 24 unknown bits. If the cookie value is computed with a cryptographic hash or something equivalent, then an attacker has only the probability of one in 16 million to find a correct cookie value. This severely limits the attacker’s scope.
A server using SYN cookies doesn’t need to drop connections as its SYN queue increases. Instead, it returns a SYN-ACK, as if its SYN queue were larger. The most significant effect of a SYN flood then is merely to disable large windows.
Bernstein credits Phil Karn as the first to design an Internet protocol, which employed cookies to protect against DDoS attacks; however, cookies were found in earlier iterations. Bernstein suggested time-dependent SYN cookies, which prevent attackers at public computers from collecting valid cookies and stops them reusing the cookies in a blind attack from elsewhere.
Attackers are increasingly finding ways to outsmart SYN cookies, which security firm Radware dubbed a “tsunami SYN flood”. These types of SYN floods engineer SYN packets to grow from their usual length of 40-60 bytes up to 1,000 bytes. Packets of this size confound many defensive algorithms, including SYN cookies.