G.E.N.E.S.I.S.
Gibson's ENcryption-Enhanced Spoofing Immunity System



Edited: Jan 12,2001 at 16:23 (-0700 UTC) . . . because sometimes it IS rocket science!

A Simple TCP/IP Implementation Enhancement to
Eliminate Denial of Service (DoS) Vulnerability


Part I - Understanding the Problem

by Steve Gibson


  Any and all original intellectual property which may have
been created by this Work is hereby formally and freely placed
into the PUBLIC DOMAIN by this author, the Work's originator
and/or inventor, Steven M. Gibson, Laguna Hills, CA, USA.

It is my belief and sincere hope that it will be of value to the
Internet community for the benefit of all Internet users.
 

Part I - Understanding the Problem
Part II - Exploring the Solution
Part III - Acknowledgement of Previous Work


Overview

Malicious hackers often exploit well-known characteristics of the Internet's TCP protocol to cause Internet web sites to "deny their services" to others. The most commonplace, simple, difficult to block, and effective of these exploits is the TCP "SYN Flood". A SYN Flood operates by falsifying high numbers of connections to an Internet Server. The initiation of connections from falsified Clients quickly exhausts the inbound connection resources available to a Server, resulting in its inability to accept valid connections from real Clients.

While developing our own custom IP protocol suite to host our forthcoming NanoProbe Technology, I faced the problem of dealing with attacks of this sort, to which our high-profile site will surely be subjected. Since I was implementing the TCP protocol on my own, from scratch, I could do anything I wanted. On this occasion I devised a unique and highly-effective solution which, while completely compliant with the TCP protocol specification, completely eliminates the problems associated with falsified inbound connections.

Using this technique, outlined below, falsified connections cease to present any sort of problem for a Server. Any implementation of the TCP protocol can be easily enhanced to render it absolutely immune to source address spoof flooding while allowing it to remain highly available to legitimate inbound connection requests.

To understand the technique, it's important to understand the problem . . .




How TCP connects:

The Internet can be described as an unreliable,
non-deterministic, packet-switched network.

By this we mean that data flows across the Internet encapsulated within individual data packages or packets and that individual packets might arrive out of sequence . . . or perhaps not at all. To manage this high degree of uncertainty, individual TCP packets are transmitted with "sequence numbers" to allow the receiving end to reassemble the original packet sequence and acknowledge the receipt of packets received.

Before packets of data can begin flowing from end-to-end over a TCP "connection" the endpoints must exchange their initial packet sequence numbers (so that the other end knows what sequence numbers to expect). Each end sends its initial sequence number and acknowledges the receipt of the other's in a "connection opening" process known as the 3-Way Connection Handshake:

3-Way Connection Handshake

Let's examine the three packet transactions:

To set the stage, the Server listens for inbound connections being initiated by Client machines . . .
 

To begin establishing a connection, the Client chooses an Initial Sequence Number (Client ISN = CISN) for the packets it will be sending in the future. It sends its CISN in a packet with the "SYN" flag bit set and therefore known simply as a "SYN" packet.

When the Server receives the "SYN" packet it knows that a new TCP connection is being requested. So it sets aside some of its RAM memory to hold the details of this new connection. The Client ISN (CISN) contained in the SYN packet is saved in this memory block along with the Client's "Source IP" address and "Source Port" number.

When future packets are received by the Server, the memory blocks describing the Server's current TCP connections can be searched for an IP and Port number "match" to locate the storage block managing that connection.
 

For the next step in TCP connection handshaking, our Server chooses its own Initial Sequence Number for the packets it will be sending. It sends this Server ISN (SISN) back to the Client machine and it also ACKnowledges the receipt of the Client's CISN. Since this one packet is being used to BOTH SYNchronize our ISN and ACKnowledge the receipt of the Client's CISN, both the SYN and ACK flag bits are set. We call this a SYN/ACK packet.

The Client's receipt of the Server's SYN/ACK packet marks an important event: It verifies the existence of the Server and also confirms that a round-trip "packet path" exists between the two machines across the sometimes wild and woolly Internet.

The Client will verify that the CSN returned in the ACK portion of the Server's SYN/ACK packet matches the CISN it sent to the Server, and it will save the Server's Initial Sequence Number (SISN) provided in the SYN portion of the SYN/ACK packet.
 

The third and final step in our 3-Way TCP connection handshake requires our Client to ACKnowledge the receipt of the Server's ISN. This informs the Server that its SYN/ACK packet was able to successfully negotiate the return trip to the Client. The Client returns the Server's ISN in a packet with only the "ACK" flag bit set, and we call this an "ACK" packet.

The Server's receipt of the Client's ACK packet completes the opening of the TCP connection. Both machines have received, recorded, and acknowledged the other's Initial Sequence Number and in the process they have verified that they are both able to send packets to the other across the Internet.

Now that we understand how TCP connections are established between two machines, let's see how this process can be deliberately subverted by malicious hackers . . .




Source address spoofing:

Every IP packet traversing the Internet carries the IP address of both its source and its destination. So, for example, when an IP "Ping" packet arrives at a machine with its implicit request to be "echoed" back to the sender, the receiving machine simply swaps the source and destination IP addresses, changes the packet "type" from "Echo Request" to "Echo Reply", and sends it back out. It will automatically return to the originating Source IP address, which has now become the destination.

But the "Source IP" address is just a data field like any other in the IP packet and nothing about the design of the Internet prevents this information from being deliberately falsified. A packet's Source IP is the only identification of the packet's originating machine, and packets travel across the Internet by hopping from one router to the next. Therefore, the true source of a packet with a "spoofed" source IP address is immediately obscured and backtracking a packet to its source is flatly impossible. As you can see . . .

If the intent of a malicious hacker does not require returned
packets, the Internet provides virtually perfect anonymity.



How can spoofed packets deny service?

To understand the operation of a SYN Flood style Denial of Service (DoS) attack, consider the consequence of opening a TCP connection to a Server using a spoofed Source IP address:

Spoofed Source IP Non-Connection

A Malicious Client's SYN packet, containing a deliberately "spoofed" and falsified Source IP address, appears to be just as valid to the receiving Server as any other. So, upon receipt of the SYN packet, the Server prepares for this new TCP connection exactly as we saw above: It sets aside some of its RAM memory (to hold the details of this new connection) into which it dutifully records the Client's initial sequence number (CISN) and the Client's apparent source IP and TCP port numbers. It chooses an initial sequence number for its own packets, and sends its replying SYN/ACK packet off to the Client containing its SISN and ACKnowledging the Client's CISN . . .

Except that the Client deliberately
lied about its IP address!

Since the Source IP contained in the Client's original SYN packet was spoofed, the Server sends its replying SYN/ACK packet to the spoofed IP address, which is probably to no machine at all. The well-meaning SYN/ACK packet heads off across the Internet, never to be heard from again.

As we know, once the Server has sent the SYN/ACK packet to the Client, it expects and waits for the Client's final "ACK" acknowledging the receipt of the SYN/ACK, and finalizing the establishment of the TCP connection.

But in this case, that final "ACK" will never arrive.

After some amount of waiting, a "timer" located in the block of memory set aside to manage this connection expires. The Server determines that the SYN/ACK must have been lost in transit to the Client, so it resends the SYN/ACK to the same spoofed IP address. Since the Internet really does lose, drop, and discard packets with some frequency, this "retrying" process must be repeated several more times. Since the Server has no way of knowing how "far away" the Client is, it also waits longer and longer after each retry in a well-meaning attempt to "adapt" to a particularly distant Client. All attempts must fail before the Server can reliably decide that a TCP connection with the Client can not be completed.

Only after the Server has finally given up retrying and
waiting, can it release the resources it set aside
for managing the anticipated connection.

. . . And this, of course, is the key to the destructive potential of flooding a Server with an endless stream of SYN packets containing spoofed Source IP addresses.

There is no way for the Server to know which inbound SYN packets are valid and which are spoofed, so it must treat each one as valid. But every received SYN forces the Server to set aside some RAM memory to manage that connection, and to keep this memory tied-up during lengthy waits and retries. If spoofed SYN packets arrive in a constant flood, all of the Server's available connection management memory will be quickly exhausted in managing connections that will never succeed . . . and legitimate Clients will be denied the service due to its inability to accept additional connections.

Since packets with spoofed Source IPs cannot be backtracked to their source there's no way to catch the perpetrators, and since the spoofed packets are otherwise completely valid, they cannot be "filtered" and prevented from being handled.

It has been a serious problem without
a good solution . . . until now.
 

For a detailed specification of the DoS Solution,
please proceed to the next page . . .

Part II - Exploring the Solution

Click for the DoS Solution Page


Purchase Info      GRC Mail System     
GRC's Homepage
     Tech Support     
Purchasing Info      GRC Mail System      To GRC's Home      Tech Support      Discussions

The contents of this page are Copyright (c) 2000 by Gibson Research Corporation.
SpinRite, ChromaZone, ShieldsUP, NanoProbe, the character 'Moe' (shown above),
and the slogan "It's MY Computer" are registered trademarks of Gibson Research
Corporation (GRC), Laguna Hills, CA, USA. GRC's web and customer privacy policy.
~ ~ ~