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

The Genesis of GENESIS

Page Updated: Jan 07, 2008 at 15:16 (3,542.93 days ago)Viewed 6 times per day

During early August of 2000, I was faced with a significant problem: I wanted to create a second-generation port probing facility by creating my own packets from scratch, i.e. "by hand", and accept inbound connections from a companion second-generation remote IP authenticating client.

Since then, both of those systems have been developed, at least partially deployed, and in continuous use. I named the build-my-own-packet system NanoProbe (see that link for the whole story) and the remote client IP authentication system RSVP (see that link for that whole story).

The problem I faced was of receiving unsolicited connections from TCP clients. Any TCP server that accepts client connections can be vulnerable to deliberately fraudulent spoofed SYN packets. Such packets lead a TCP server to believe that valid connections are being requested, and usually cause it to allocate local "connection resources" such as buffer space and connection management tables. If a significant number of spoofed SYN packets arrive within a short time, the TCP server's ability to accept new connections — even legitimate connections — will be exhausted and the server's services will be denied. This was the classic, non-bandwidth flooding, denial of service attack.

I was designing and implementing my own IP protocol suite from scratch (in assembly language of course). It would support ICMP, UDP, and TCP packet generation and connection acceptance. I used Google to search the web for any solutions to this problem and I came up dry. After several days I hit upon an incredibly cool idea that, at the time, I believed to be completely unique and original. The concept beautifully and perfectly solved the problem of client IP spoofing  . . . which I believed no one else had solved before.

As usual, my first step was to share the idea with the people in our newsgroups. So I created a pair of web pages to carefully and thoroughly explain how TCP connects, how TCP's inherent trust can be abused by an Internet client that deliberately lies about its IP, and how the system I had invented would solve the problem.

Since I knew how valuable this solution could be to the entire industry, I also formally placed any and all intellectual property contained within the concept into the public domain — giving the idea away to the world. I posted a note to that effect at the top of those pages.

Something similar had been done before

Shortly after the second page was published, accompanied by excited online discussion, someone named "Torinak" spoke up to say that my solution resembled something called "SYN Cookies" that had been developed several years before and was part of the LINUX kernel (though it was disabled by default since it could "break" some things about TCP).

Needless to say, I was somewhat disappointed to learn that this was a case of parallel invention and that my idea was not unique. But I was glad to know about what had been done before. Knowing, then, the name "SYN Cookies", Google immediately produced pages of search hits, including those written by the concept's principal originator, Daniel Bernstein (here's Dan's page). As you would expect in a case of separate invention, many (in fact most) of the specific details of our respective solutions were very different. However, we both had the same basic concept about how a client's IP could be authenticated while remaining largely compatible with the existing (non-authenticating) TCP protocol.

I exchanged some eMail with Dan to discuss his implementation and ask him why the basic concept embodied in both of our approaches had remained such a well-kept secret within the industry. I was puzzled about why it had not been more widely implemented by the Internet community. It seemed that it was mostly a case of confusion, some controversy surrounding the aspects of TCP protocol which SYN Cookies (or any deferred-connection system) might break, coupled with general apathy and inertia.

SYN Cookies had some useful features I hadn't considered

My own invention (as described on the following pages) was less than a day old and, of course, had never been implemented. By comparison, the details of SYN Cookies were years old and had the benefit of extensive open-source community experimentation and tweaking. So SYN Cookies had evolved some useful improvements that I had never considered, as well as some unnecessary (TCP Option) complications that were not required by my security scanning NanoProbe / RSVP application.

When I set about implementing my own, similar, token-based deferred TCP connection establishment solution, I incorporated my own brand of "token expiration" for the prevention of "replay attacks" (see FAQ section below). I also switched from using the encrypt/decrypt approach described on my pages to a one-way hashing function.

The GENESIS pages were never updated

The GENESIS pages were created to be a quick communication of a new idea to the folks inhabiting our newsgroups. The actual GENESIS code, as written, implemented a number of additional features, but since the pages were only intended to communicate the fundamental idea of TCP connection deferment, they did not track the concept's implementation.

If my solution to the problem of SYN spoofing had been completely new and unique, as I originally believed, I imagine that I would have produced and maintained a more formal and accurate specification of my implementation. But since I was only using the GENESIS system for my own purposes, and since the equivalent open-source LINUX implementation of the concept was readily available, I saw no reason to invest any more of my severely limited time in that direction.




Microsoft, IBM, and others

Throughout the months which followed, these pages served their purpose: Many people enjoyed taking the intellectual walk through my description of an alternate and in some ways superior means for establishing a TCP connection. But even more significantly, perhaps because my pages were more visible than descriptions of SYN Cookies, I have had numerous conversations with engineers at Microsoft, IBM, Cisco, and other leading vendors. They have asked about my implementation, and I have gladly explained my enhancements and the limitations built into my approaches.

Today, Windows 2000 and XP incorporate a form of adaptive encrypted token SYN spoofing immunity that automatically "kicks in" when a Windows 2000 or XP machine is under a SYN spoofing attack. At that time, as with my system, a number of TCP optimization features are unavailable to the connections  . . . but that's far better than being able to offer no connections at all.

IBM has developed their own similar approach for dealing with, and creating an immunity against, SYN spoofing. Unfortunately, unlike my work and that of Dan Bernstein et al, IBM is attempting to patent their solution. You may find details of the pending IBM patent here: "Methods and systems for defeating TCP SYN flooding attacks".

If you are curious (as I was) you may download
this 17-page, 678kb, zipped PDF containing the
complete patent application for IBM's SYN
spoofing immunity system.

To download:

IBM's complete patent application (above) is puzzling. You will see that it solves the SYN spoofing problem in very much the same way as I and Bernstein et al already have, though with another typical round of "divergent invention" differences. Yet the patent makes no reference to either of our prior work. I hope that the patent examiners know enough to search for the phrase "SYN Cookies" before awarding all of the claims made by this application since many of them are now quite old news.




F.A.Q. — Frequently Asked Questions

Please note that these questions and answers presume a good familiarity with the GENESIS system and TCP connection establishment. If you have not yet read through the GENESIS pages, you may wish to do so before returning here.

 Do these systems prevent all SYN flooding attacks?

No. There is a world of difference between a SYN Spoofing DoS attack and a SYN Flooding DoS attack. Unfortunately, the two terms are often used interchangeably and incorrectly. (Even IBM's own patent application uses the term "SYN flooding attacks" when they really mean "SYN spoofing attacks.")

 If, after returning the SYN/ACK packet, the server retains no memory of a pending connection, what happens if the server's SYN/ACK packet is lost on its way back to the client? How can it be resent?

That's a VERY good point. In a traditional TCP connection establishment, the server can, and does, resend its SYN/ACK reply packet up to several times if it does not receive the client's expected answering ACK response. But with any "stateless" SYN-SYN/ACK exchange, there is no way for the server to resend a lost SYN/ACK since it retains no memory of the pending connection.

The good news is that everything continues to function correctly, thanks to the client's built-in lost packet retrying: If the client does not receive the answering SYN/ACK packet, it doesn't know whether its SYN packet was lost on the way to the server, or the server's SYN/ACK packet was lost its way back to the client. In EITHER case, the client will resend its initial SYN packet several times as necessary to receive the server's answering SYN/ACK.

In this fashion, the server's inability to resend its own lost SYN/ACK packet(s) is compensated for by a valid client's sincere desire to establish a connection with the server.

 What about "Replay Attacks?" With the GENESIS approach, couldn't a valid client generate a large number of valid SYN packets to receive their matching SYN/ACK packets. From these, an inventory of "valid" ACK packets could be assembled and later used to spoof valid connections.

Yes, that's a very good point which is not covered on the GENESIS pages. My implementation of the actual system mixed a randomly changing value into the computations. This has the effect of "expiring" any returned SYN/ACK tokens after a short time, thus managing the possibility of replay attacks. If a client's ACK fails the GENESIS validation, it is tested again using the previous random-mix value to see whether the packet was generated under the influence of that immediately preceding random value.




A conceptual description of the GENESIS System

The following three pages have remained in their original form with the single addition of a link back to this newer "preface" page. I hope you enjoy the journey . . .

Part I - Understanding the Problem


Jump to top of page
Gibson Research Corporation is owned and operated by Steve Gibson.  The contents
of this page are Copyright (c) 2016 Gibson Research Corporation. SpinRite, ShieldsUP,
NanoProbe, and any other indicated trademarks are registered trademarks of Gibson
Research Corporation, Laguna Hills, CA, USA. GRC's web and customer privacy policy.
Jump to top of page

Last Edit: Jan 07, 2008 at 15:16 (3,542.93 days ago)Viewed 6 times per day