SYN Cookies

When a syncache bucket does overflow, a fallback mechanism exists which permits sending back a SYN cookie instead of performing oldest FIFO drop of an entry on the hash list. This section explains the syncookie approach, and outlines how the cookie is constructed.

The cookie is sent to the remote system as the system's Initial Sequence Number (ISN), and then returned in the final phase of TCP's three way handshake. As connection establishment is performed by the returning ACK, a secret should be used to validate the connection, which is concealed from the remote system by use of a non-invertible hash. To prevent an intermediate system from collecting cookies and replaying them at a later date, the cookie should also contain a time component. The solution chosen here was to keep a table of secrets which have a bounded lifetime, which has an added benefit of regularly changing the secret which is sent back to the remote system. Figure 5 shows the internal structure of the cookie.

Figure 5: Layers of data in the syncookie.

The basis of the implementation is a table of 128 32-bit values obtained from arc4random(). Each entry is used for a duration of 31.25 milliseconds, and has a total lifetime of 4 seconds, which was chosen as a reasonable upper bound for the RTT to the remote system, as SYN,ACK containing the cookie must reach the system and be returned before the secret expires.

In order to generate a cookie, the system tick timer is scaled into units of 31.25 milliseconds by use of divide and shift operations, with the result used to choose the correct window index. If the secret in the current window has expired, a new 32-bit secret is obtained from arc4random(), and the timeout is reset.

The local address, foreign address, local port, foreign port and secret are passed through MD5 to create the initial basis of the cryptographic hash, with 25 bits being used in the cookie, and 7 bits containing the window index. The peer MSS from the TCP options section of the initial SYN is fit into one of 4 predefined MSS values, and the resulting 2 bit index is xor'ed into the mix, as shown by $(A)$ in Figure 5. Finally, the peer's 32-bit ISS is xor'ed in to generate the final cookie, which is sent back to the connecting system as the ISN.

Since no state is kept on the server machine, any returning ACK which contains the correct TCP sequence numbers may serve to establish a connection. Validating the ACK is the reverse of the above process. First the peer's sequence number is removed, and then the 7 bit index is used to select the correct window. If the secret has expired, then the ACK is immediately discarded without further processing. This insures that the system does not have to check every incoming ACK unless a syncookie was recently sent. If the timeout indicates that the secret is valid, it is used in the MD5 hash computation. The ACK is considered valid if the remaining 23 bits evaluate to 0.

In practice, this means that a remote system has 4 seconds to try and brute force a space of $2^{23}$ entries.

Figure 6: Time required to connect() to remote system and read() one byte in response. No errors at the system call level were observed during the test.