G.E.N.E.S.I.S. Gibson's ENcryption-Enhanced Spoofing Immunity System A Simple TCP/IP Implementation Enhancement to Eliminate Denial of Service (DoS) Vulnerability Part II - Exploring the Solution 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.   G.E.N.E.S.I.S. The elimination of Denial of Service (DoS) vulnerability requires that the Server defers any per-connection resource commitment until the Client's remote IP address has been "authenticated". Surprisingly, the existing TCP protocol can accommodate these changes at the Server, without requiring any alteration in the Client's operation. The application of this technique requires three key innovations and a few implementation details:

Connection Management Deferral: The first innovation applied to the TCP protocol is the deferral of all "connection management" until the end of the standard 3-way TCP handshake. In other words, rather than storing connection information upon the receipt of the Client's first SYN packet (as the traditional TCP protocol suggests) we instead refuse to take the connection "seriously" until we have received the Client's ACK packet. Let's refer to our 3-way TCP connection handshake diagram to see how this can be accomplished: 3-Way Connection Handshake As shown in the familiar diagram above, the third and final handshake packet is the ACK packet sent from the Client to the Server. The key to deferring all connection establishment work until the receipt of this packet is noticing that this ACK packet contains every piece of information required to define the connection. It contains both the Client's current Sequence Number (CSN) and the Server's Sequence Number (SSN), which this packet is acknowledging. And since each TCP/IP packet contains the packet's source and destination IP addresses and the source and destination TCP port numbers . . . . . . the ACK packet contains a COMPLETE specification for the current state of the connection. This means that we do not need to save ANY information about the pending connection after receiving the Client's initial SYN packet. When a SYN packet is received, we respond with a valid SYN/ACK packet, ACKnowledging the receipt of the Client's SYN and providing our own initial sequence number (ISN) . . . then we forget all about the pending connection! If the Source IP of the SYN packet was spoofed, our replying SYN/ACK will fly off into Internet oblivion, but we will not be in any way damaged by the connection that never follows because we will have already forgotten about it. Only if the Client replies to the receipt of our SYN/ACK with an ACK packet, do we finally need to get serious about the connection. At that time we would allocate the resources to manage it further, recording the complete connection information obtained from the ACK packet. This is an entirely workable solution as it is, and we are completely immune to SYN flooding. But we do have one big problem . . . Now we are vulnerable to ACK Flooding! Whoops. We quickly see that the only thing we've achieved so far is pushing the same problem we had before back further in the handshake process. Now, a malicious hacker can flood us with spoofed ACK packets to cause us to establish falsified connections and quickly overwhelm our Server's resources. But we HAVE achieved something important: The deferral of connection management, until we receive an ACK packet, provides us with powerful leverage because, unlike with the SYN packet, a valid ACK packet must be an acknowledgement of the receipt of the SYN/ACK packet we previously sent. This provides us with the key to discriminating between ACK packets which are valid replies to our SYN/ACK, and those that we can discard as spoofing attempts. Encrypted Tokens: If we include information — an Encrypted Token — in our outbound SYN/ACK packet which will be returned in the Client's ACK packet, and which, being securely encrypted, can not be predicted or calculated by the Client, an ACK packet can no longer be spoofed, because it must be an actual response to the receipt of our SYN/ACK packet and containing the proper Encrypted Token.

Authenticating the Client The second innovation applied to the TCP protocol is the explicit, non-spoofable, cryptographic authentication of the remote Client's IP address. Authentication of the Client's IP, prior to the committment of any connection resources, provides all of the benefits of Connection Management Deferral with none of the liabilities. The following explanation of Client IP authentication deliberately overlooks an important TCP connection requirement. That is the subject of the third innovation. If you are a TCP guru, please withhold your objection until you have encountered the third innovation. The cryptographic community understands, more than any other group, that very little security is achieved through obscurity. Applying that to our context: Relying upon the hope that a malicious hacker will not have discovered something about the operation of a system, and depending upon this obscurity for the system's "security", is a really bad idea. Consequently, a paramount requirement for this new hacker-proof TCP technology is that it can withstand the full disclosure of every aspect of its operation without sacrificing any of its security. This has been achieved. Another concept from the security community is that the simplest solutions, lacking convoluted exceptions and complex bells and whistles, are the most provably secure. The solution I developed and present here is surprisingly simple and straightforward: Upon receipt of a SYN packet, we encrypt the Client's Source IP address and return it with our SYN/ACK response as our Initial Sequence Number. Upon receipt of an ACK packet, we decrypt the returned acknowledging sequence number and compare it with the Client's Source IP. BINGO!!   It is just that simple! The use of strong encryption creates an unknowable and non-discoverable relationship between the more than FOUR BILLION (32-bits) possible Internet addresses and the corresponding more than FOUR BILLION (32-bits) matching Encrypted Tokens. The only way for a remote Client to receive an encrypted token that correctly matches any address on the Internet is for it to send a SYN packet to the Server providing that address. Since it must also receive the Server's SYN/ACK reply containing the matching token, the Source IP address provided by the Client must be authentic (or the Server's reply won't return to the Client). When a properly matching encrypted token is returned with the Client's ACK packet, we know that the Client could have only received the encrypted token from us and that the token must have made a successful round trip to the Client and back. Thus, the Client's IP address, and its desire for a TCP connection with the Server, is perfectly authenticated and the Server may confidently establish a TCP connection. Repeating and Summarizing We are immune to SYN flooding because all connection management overhead is deferred until the end of the 3-way handshake and no record that a SYN was received is retained. We are immune to ACK flooding because the relationship between the ACK packet's apparent Source IP and the encrypted token it delivers is unknowable by any external agency. Therefore ACK packet senders are unable to spoof their source addresses because they have no way of producing properly matching tokens. Upon receipt of a SYN packet, our modified "connection deferring" TCP protocol generates and sends an answering SYN/ACK packet in ACKnowledgement of the Client's ISN, and provides our ISN (the Encrypted Token matching the Client's IP). We retain no record that a SYN has been received. The ISN we provide for our outbound SYN/ACK packet is just an encrypted version of the Client's apparent Source IP. If the received SYN carried a spoofed Source IP, our SYN/ACK response will disappear into the Internet and that will be the end of it. But since we no longer allocate any connection resources upon the receipt of SYN packets we don't care at all if the SYN's are spoofed. A valid Client replies to our SYN/ACK by sending an ACK packet back to us. It provides its current sequence number and also acknowledges the ISN we provided . . . which is actually its encrypted IP address. When we receive an ACK packet for a connection that does not currently exist, we simply decrypt the ACKnowledged sequence number (the returned encrypted token) and compare it with the packet's apparent Source IP address. If they match we know that the ACK and Client are authentic. Cool, huh??

What About This Encryption? Ronald Rivest, working in conjunction with RSA Laboratories, has invented a number of highly regarded cryptographic ciphers, systems and technologies. For our purposes, we require a cipher which is very fast since every received SYN packet requires an encryption of the apparent Source IP to generate the matching encrypted token, and every received ACK packet (describing a non-established connection) requires a decryption of the returned encrypted token to verify its IP match. Note that this is not strictly true: As web browsers request the contents of a web page connections tend to occur in "bunches" with multiple simultaneous overlapping connections to the same IP address, thus generating the same Encrypted Token. Therefore, a small "recent token cache" could be used to retain recent IP/Token pairs. This cache could be checked before a new encryption/decryption was performed. However, my experience with hand-optimized strong symmetric ciphers indicates that a properly selected and implemented cipher can be much faster than a cache search and lookup. My first implementation of this technology employs the well known and extremely strong RSA RC5 cipher. RC5 is a high-performance, parameterized, symmetric cipher. One of the most interesting characteristics of RC5 is that its "cipher strength" can be directly controlled through its parameters. The most important of these is the number of "rounds", or iterations, the algorithm uses. This essentially feeds the results of one "pass" back into the cipher for another. RSA recommends at least 12 rounds for good security but it's so fast I'm using many more. How secure is RC5? Recent studies of RC5 have attempted to "attack" this cipher using advanced statistical techniques. They have predicted that there would be a 45% probability of cracking RC5 when it is running with (only) 10 rounds and after analyzing 2^62 individual plaintext/encrypted pairs — IP/Token pairs in our case. However, since there are only 2^32 possible IP addresses in the entire version 4 Internet, even if a malicious hacker were able to get all FOUR BILLION IP/Token pairs from the Server (which is impossible, as we'll see below), this would still be 1/(2^30), or less than one billionth of the amount of data required to have a 45% chance of cracking the Server's token encryption. (In other words, forget about it!) To all that, add the following: My hand-written assembly language implementation of RC5 is SO FAST that I am running MANY more than 10 rounds, each one making the encryption even stronger and harder to crack. Every time the system is booted, and the TCP protocol is initialized, a new completely random, 256-bit cipher key is chosen. Since Encrypted Tokens are created simply based upon the Client's IP address, there is no way for any malicious hacker to ever collect even a small fraction of the total four billion possible IP/Token pairs . . . which will all change, anyway, the next time the Server is restarted! Encrypting the Client's IP address with a fast symmetric cipher, like RC5, provides an uncrackable and completely "opaque" token for use in authenticating the token's round-trip and therefore the IP address of the remote Client. Since the token is directly generated from the Client's IP address, the SYN-triggered generation and ACK-triggered verification are able to operate independently, tied together only by the Client's IP address. RSA's next-generation cipher, RC6, is even stronger than RC5 (not that we need any more strength) and, if adopted as the next international encryption standard to replace the rapidly weakening DES, RSA has promised to make the use of RC6 completely free. (I already own a licence to use RC5.) Further Reading About RC5 and RC6 I have assembled some relevant documents and PDF files: The RC5 Encryption Algorithm, by Ronald L. Rivest. (182k PDF file) Internet RFC 2040, by Robert W. Baldwin, Ron Rivest, and RSA (56k text file) What are RC5 and RC6?, RSA Security FAQ #3.6.4 (online web page) Linear Cryptanalysis of RC5 and RC6, by Johan Borst, et al (217k PDF file) On the Security of the RC5 Encryption Algorithm, RSA Labs (452k PDF file) The RC6 Block Cipher, Rivest, Robshaw, Sidney, Yin (423k PDF file) The Security of the RC6 Block Cipher, Scott Contini, RSA Labs (647k PDF file)

Initial Sequence Number Details The third and final innovation satisfies a "safety requirement" of the TCP protocol which our use of an initial sequence number that's simply based upon the Client's IP address was failing to meet. To understand the safety requirement, and our solution, we first need to learn . . . The whole truth about sequence numbers As we have seen, during the initial 3-way TCP connection handshake, each end of the connection sends the other end its "Initial Sequence Number". This tells the receiving end the "starting point" for the sender's packet sequence numbering. Once established, these sequence numbers are used to "re-sequence" packets that arrive in the wrong order, to identify duplicate packets, and to acknowledge the highest "sequence number" we have successfully received. Unacknowledged packets are automatically resent after an appropriate delay. Now, you might wonder why TCP bothers with all of this "Initial Sequence Number" stuff at all? For example, why not simply start numbering a connection's data stream at ZERO or ONE, and just count up from there? The reason involves the need for the "reusability" of any given connection: TCP allows connections to be closed and immediately re-opened and reused. But, if an existing connection was quickly closed and immediately re-opened, and if the new connection's initial sequence number was the same as the first, then data packets arriving late from the previous connection could be confused with packets from the new connection because their sequence numbers would be so similar. But, if the new connection was to use an initial sequence number much larger than the previous connection's, then any late arrivals from the previous connection would have sequence numbers lower than the initial sequence number of the new connection, and could be immediately discarded. The TCP protocol specifies that each machine should maintain a 32-bit counter which is increased by one approximately every 4 microseconds. This current count is then used to supply the Initial Sequence Number anytime TCP is establishing a new connection. In this way we are assured that quickly reused connections will have very distinct sequence numbers so that old packets can be easily identified as such. But now we see the problem with my scheme for basing our own Initial Sequence Numbers upon the Client's encrypted IP address. Since a quickly reused connection would have the same IP address as the last connection, we would use the same ISN for the new connection and create exactly the problem that Initial Sequence Numbers were designed to prevent! Whoops. But fear not . . . I've solved that problem too!      Can you guess? We use the Client's Initial Sequence Number as a BIAS to the ISN we generate from the Client's IP address! Here's how it works: Upon receipt of a SYN packet, we first ENCRYPT the Client's Source IP address, then ADD the Client's Initial Sequence Number (CISN) to the encrypted IP. This is what we return with our SYN/ACK response as our (Server) Initial Sequence Number (SISN). Upon receipt of an ACK packet, we first SUBTRACT the Client's ISN from our returned acknowledging Server sequence number, then we DECRYPT the result and compare it with the Client's Source IP. It's beautiful and perfect. What we are doing, conceptually, is using the Client's 32-bit Initial Sequence Number counter as our own. We can't use our own, since we need to hold the Client's encrypted IP there. So we add the Client's ISN to our encryption result in order to create the required "per-connection" changing ISN used to uniquely number our future packets. Since both packets from the Client (its initial SYN and its ACK) contain its ISN, we are able to use that as a "fixed bias" to our encryption — adding it before we send the SYN/ACK and subtracting it when we receive the ACK. Since the Client's ISN, complying with the TCP protocol, will be changed and much larger for a second connection, the ISN we supply to the Client will too, since we're simply adding it's own ISN to our fixed encryption result to form our ISN! Is that cool or what?!! Does this have any impact on our authentication security? No.  Clients are unable to gain any additional information from the ISN's we return since they are simply a sum of the Client's outgoing ISN and a fixed and unknowable encryption of the Client's IP. Thus, we are every bit as secure as we were, while also being fully compliant with the "increasing Initial Sequence Number" requirement of the TCP protocol!

Deploying GENESIS So, what does this all mean?  It means that . . . Any connection-accepting entity on the Internet, which would otherwise be inherently vulnerable to connection-initiation IP address spoofing, may employ this simple TCP enhancement to easily and efficiently authenticate the IP address of any connection-initiator prior to investing any local connection resources. This system may be transparently incorporated into any and all TCP protocol implementations. Doing so would render the GENESIS-using devices and machines completely immune to the consequences of SYN and ACK address spoofing Denial of Service attacks. Mainstream operating systems Since the GENESIS system is fully compatible with TCP protocol and can be seamlessly incorporated into existing host TCP/IP stacks, operating system vendors who incorporate this system into there offerings can effortlessly supply their customers with the industry's most robust Denial of Service protection. Personal firewalls and routers Higher-end personal computer (PC) software firewalls, which need to minimize their total resource usage, could make very good use of this system. In addition, the new breed of low-cost personal NAT router/packet filters, which have extremely limited local resources, could easily employ this system to hugely strengthen the protection they offer to their NAT client networks. Though some personal NAT routers claim "firewall status," this is typically unwarranted. The use of the GENESIS system delivers true firewall capability and benefits at no cost. Previous DoS solutions Commercial and personal firewalls have attempted to protect their client machines from half-open connection flooding by maintaining size-limited lists of half-open (possibly spoofed) connections. The oldest non-established connection is discarded when the list becomes full to make room for newly arriving SYN packets. This solution suffers from requiring resources to limit and manage the number of allowed half-open connections, and from the significant possibility that valid half-open connections will be pushed from the list, replaced by more recently spoofed SYN packets. This would cause valid connections to be rejected thus denying service to valid Clients. As a result, while existing techniques can mitigate the damaging effects of Denial of Service, they fail to completely solve the problem. By comparison, the GENESIS system requires NO local resources and suffers from none of these limitations. GENESIS offers the complete solution to TCP Denial of Service attacks.

Acknowledgements

To return to the previous page, press your browser's BACK button.

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