USRE47296E1 - System and method for an adaptive TCP SYN cookie with time validation - Google Patents

Abstract

Provided is a method and system for TCP SYN cookie validation. The method includes receiving a session SYN packet by a TCP session setup module of a host server, generating a transition cookie including a time value representing the actual time, sending a session SYN/ACK packet, including the transition cookie, in response to the received session SYN packet, receiving a session ACK packet, and determining whether a candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a continuation reissue application of U.S. Pat. No. 7,675,854 and claims benefit under 35 U.S.C. 120 as a continuation of application Ser. No. 13/413,191 filed on Mar. 6, 2012, which is an application for reissue of U.S. Pat. No. 7,675,854, originally issued on Mar. 9, 2010.

BACKGROUND OF THE INVENTION

When a TCP (Transmission Control Protocol) connection starts, a destination host receives a SYN (synchronize/start) packet from a source host and sends back a SYN ACK (synchronize acknowledge). The destination host normally then waits to receiver an ACK (acknowledge) of the SYN ACK before the connection is established. This is referred to as the TCP “three-way handshake.”

While waiting for the ACK to the SYN ACK, a connection queue of finite size on the destination host keeps track of connections waiting to be completed. This queue typically empties quickly since the ACK is expected to arrive a few milliseconds after the SYN ACK is sent.

A TCP SYN flood attack is a well known denial of service attack that exploits the TCP three-way handshake design by having an attacking source host generate TCP SYN packets with random source addresses toward a victim host. The victim destination host sends a SYN ACK back to the random source address and adds an entry to the connection queue, or otherwise allocates server resources. Since the SYN ACK is destined for an incorrect or non-existent host, the last part of the “three-way handshake” is never completed and the entry remains in the connection queue until a timer expires, typically, for example, for about one minute. By generating phony TCP SYN packets from random IP addresses at a rapid rate, it is possible to fill up the connection queue and deny TCP services (such as e-mail, file transfer, or WWW) to legitimate users. In most instances, there is no easy way to trace the originator of the attack because the IP address of the source is forged. The external manifestations of the problem may include inability to get e-mail, inability to accept connections to WWW or FTP services, or a large number of TCP connections on your host in the state SYN_RCVD.

A malicious client sending high volume of TCP SYN packets without sending the subsequent ACK packets can deplete server resources and severely impact the server's ability to serve its legitimate clients.

Newer operating systems or platforms implement various solutions to minimize the impact of TCP SYN flood attacks. The solutions include better resource management, and the use of a “SYN cookie”.

In an exemplary solution, instead of allocating server resource at the time of receiving a TCP SYN packet, the server sends back a SYN/ACK packet with a specially constructed sequence number known as a SYN cookie. When the server then receives an ACK packet in response to the SYN/ACK packet, the server recovers a SYN cookie from the ACK packet, and validates the recovered SYN cookie before further allocating server resources.

The effectiveness of a solution using a SYN cookie depends on the method with which the SYN cookie is constructed. However, existing solutions using a SYN cookie typically employ a hash function to construct the SYN cookie, which can lead to a high percentage of false validations of the SYN cookie, resulting in less than satisfactory protection again TCP SYN flood attack.

Therefore, there is a need for a better system and method for constructing and validating SYN cookies.

SUMMARY OF THE INVENTION

An aspect of the present invention provides a system for TCP SYN cookie validation. The system includes a host server including a processor and memory. The processor is configured for receiving a session SYN packet, generating a transition cookie, the transition cookie comprising a time value representing the actual time, sending a session SYN/ACK packet, including the transition cookie, in response to the received session SYN packet, receiving a session ACK packet, and determining whether a candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

One aspect of the invention includes the system above in which the processor is further configured for regarding the received session ACK packet as valid if the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

In another aspect of the invention, the predetermined time interval is in the range of one to six seconds.

In one aspect of the invention, the predetermined time interval is three seconds.

In another aspect of the invention, the step of generating the transition cookie includes the use of data obtained from the session SYN packet.

In one aspect of the invention, the data obtained from the session SYN packet comprises the source IP address of an IP header associated with the session SYN packet.

In another aspect of the invention, the data obtained from the session SYN packet comprises the sequence number of a TCP header associated with the session SYN packet.

In another aspect of the invention, the data obtained from the session SYN packet comprises a source port associated with the session SYN packet.

In another aspect of the invention, the data obtained from the session SYN packet comprises a destination port associated with the session SYN packet.

Another aspect of the present invention provides a method for TCP SYN cookie validation. The method includes receiving a session SYN packet by a TCP session setup module, generating a transition cookie by the TCP session setup module, the transition cookie comprising a time value representing the actual time, sending a session SYN/ACK packet, including the transition cookie, in response to the received session SYN packet, receiving a session ACK packet, and determining whether a candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

In an aspect of the invention, the method further includes indicating the received session ACK packet comprises a valid candidate transition cookie if the time value of the candidate transition cookie is within a predetermined time interval of the time the session ACK packet is received.

In another aspect of the invention, the step of generating the transition cookie includes the use of data obtained from the session SYN packet.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a schematic diagram illustrating a host server including a TCP session setup module and a client server, in accordance with an embodiment of the present invention;

FIG. 2 is a schematic diagram of a TCP/IP handshake in accordance with an embodiment of the present invention;

FIG. 3a illustrates a method including steps for generating a transition cookie data element by atransition cookie generator245, in accordance with an embodiment of the present invention;

FIG. 3b illustrates a method including steps for generating a transition cookie secret key by atransition cookie generator245 based on data obtained from the received session SYN packet, in accordance with an embodiment of the present invention;

FIG. 3c illustrates a method including steps for generating a transition cookie based on a transition cookie data element, a transition cookie secret key, and data obtained from a received session SYN packet in accordance with an embodiment of the present invention;

FIG. 4a illustrates steps for generating a candidate encrypted data element by atransition cookie validator275 based on data obtained from a received session ACK packet, in accordance with an embodiment of the present invention;

FIG. 4b illustrates a method including steps for generating a candidate transition cookie secret key by atransition cookie validator275 based on data obtained from a received session ACK packet and a candidate sequence number, in accordance with an embodiment of the present invention;

FIG. 4c illustrates a method including steps for generating a candidate transition cookie data element by atransition cookie validator275 based on a candidate encrypted data element and a candidate transition cookie secret key, in accordance with an embodiment of the present invention;

FIG. 4d illustrates a method including the steps for validating a candidate transition cookie data element, in accordance with an embodiment of the present invention; and

FIG. 5 illustrates a method including steps for generating information based on a validated candidate transition cookie data element, in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

In the following description, for purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one having ordinary skill in the art, that the invention may be practiced without these specific details. In some instances, well-known features may be omitted or simplified so as not to obscure the present invention. Furthermore, reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in an embodiment” in various places in the specification are not necessarily all referring to the same embodiment.

Transmission Control Protocol (“TCP”) is one of the main protocols in TCP/IP networks. Whereas the Internet Protocol (“IP”) deals only with packets, TCP enables two hosts to establish a connection and exchange streams of data. TCP guarantees delivery of data and also guarantees that packets will be delivered in the same order in which they were sent.

The terms “host server” and “client server” referred to in the descriptions of various embodiments of the invention herein described are intended to generally describe a typical system arrangement in which the embodiments operate. The “host server” generally refers to any computer system interconnected to a TCP/IP network, including but not limited to the Internet, the computer system comprising at a minimum a processor, computer memory, and computer software. The computer system is configured to allow the host server to participate in TCP protocol communications over its connected TCP/IP network. Although the “host server” may be a single personal computer having its own IP address and in communication with the TCP/IP network, it may also be a multi-processor server or server bank. The “client server” is similar to the “host server”, although it is understood that the “client server” may, in fact, be a single personal computer attached to the TCP/IP network. The only difference between the client and the host server for the purposes of the present invention is that the host server receives the SYN from the client server, sends a SYN ACK to the client server, and waits for the ACK from the client server.

FIG. 1 is a schematic diagram illustrating an embodiment of the present invention. Ahost server102 may include aTCP session module104. The TCPsession setup module104 can engage in aTCP handshake108, such as described above, with aclient server106. In an embodiment, the TCPsession setup module104 is a software component of thehost server102. In one embodiment, the TCPsession setup module104 is implemented in an Application Specific Integrated Circuit (“ASIC”) or a Field Programmable Gate Array (“FPGA”). It is the TCP session setup module that handles the “3-way handshake”108 between thehost server102 and theclient server106. The TCP session setup module may itself also incorporate modules for sending and receiving TCP session packets. These modules may include but are not limited to a session SYN packet receiver, a session SYN/ACK packet sender, and a session ACK packet receiver, which are all known to those of ordinary skill in the computer arts.

The TCPsessions setup module104 may itself be embedded in one or more other host server modules (not shown). The TCP session setup module may alternatively comprise a hardware or firmware component. For example, the software which handles theTCP handshake108 on behalf of thehost server102 may be programmed onto a externally programmable read-only memory (“EPROM”) (not shown), and the EPROM may then be integrated into the host server. In another example, the ASIC or FPGA is integrated into the host server.

FIG. 2 illustrates a TCPsession setup module104 processing TCP/IP segments (not shown), such assession SYN packet210, session SYN/ACK packet220, andsession ACK packet230.

A TCP/IP segment includes a TCP header and an IP header as described in IETF RFC 793 “Transmission Control Protocol” section 3.1 “Header Format”, incorporated herein by reference. A TCP header optionally includes a sack-permitted option as described in IETF RFC 2018 “TCP Selective Acknowledgement Options” section 2 “Sack-Permitted Option”, incorporated herein by reference. Asession SYN packet210 is a TCP/IP segment with the SYN control bit in the TCP Header set to “1”. A session SYN/ACK packet220 is a TCP/IP segment with the SYN control bit and the ACK control bit in the TCP header set to “1”. ASession ACK Packet230 is a TCP/IP segment with the ACK control bit in the TCP header set to “1”.

Referring toFIG. 2, in an embodiment, the TCPsession setup module104 receives asession SYN packet210, obtains data from asession SYN packet210, such as but not limited to the source IP address of the IP header, or the sequence number of the TCP header, and uses the data to generate atransition cookie250. Thetransition cookie250 is preferably a 32-bit data element. In response to thesession SYN packet210, the TCPsession setup module104 creates and sends out a session SYN/ACK packet220 in accordance with IETF RFC 793 “Transmission Control Protocol” section 3.4 “Establishing a connection”, incorporated herein by reference. The TCPsession setup module104 preferably includes thetransition cookie250 as the sequence number of the TCP header in the session SYN/ACK packet220.

After the TCPsession setup module104 has sent out the session SYN/ACK packet220, it waits for receipt of a respondingsession ACK packet230. In an embodiment, when a session SYN/ACK packet230 is received, the TCPsession setup module104 generates a 32-bitcandidate transition cookie270 such that the sum ofcandidate transition cookie270 and a value of “1” equal the acknowledgement number of the TCP header in thesession ACK packet230. For example, if the acknowledgement number is “41B4362A” in hexadecimal format thecandidate transition cookie270 is “41B43629” in hexadecimal format; the sum of “41B43629” and a value of “1” equals “41B4362A”. In another example, if the acknowledgement number is “00A30000” in hexadecimal format thecandidate transition cookie270 is “00A2FFFF” in hexadecimal format; the sum of “00A2FFFF” and a value of “1” equals “00A30000”. In another example, if the acknowledgement number is “00000000” in hexadecimal format theCandidate Transition Cookie270 is “FFFFFFFF” in hexadecimal format; the sum of “FFFFFFFF” and a value of “1” equals “00000000”, with the most significant bit carried beyond the 32-bit boundary. The TCPsession setup module104 may thus validate thecandidate transition cookie270 in this manner. If the TCPsession setup module104 determines that thecandidate transition cookie270 is thus valid, thesession ACK packet230 is also valid. In this case, the TCPsession setup module104 obtains data from the validatedsession ACK packet230 and sends the data and information generated during the validation ofcandidate transition cookie270 to a computing module (not shown) for further processing.

In order to generate and validatetransition cookies250,270, the TCPsession setup module104 may include atransition cookie generator245 and atransition cookie validator275, respectively. Alternatively, the generation and validation may be performed directly by the TCPsession setup module104. In the descriptions herein, references to the TCP andtransition cookie validator275 are understood to include any of the alternative embodiments of these components.

Atransition cookie generator245 includes the functionality of generating a transition cookie based on the data obtained from asession SYN210 packet received by the TCPsession setup module104.

Atransition cookie validator275 includes the functionality of validating acandidate transition cookie270 generated based on data obtained from asession ACK packet230 received by the TCPsession setup module104.

In exemplary operation, atransition cookie generator245 is software or firmware that generates atransition cookie250 based on data obtained from asession SYN packet210 received by the TCPsession setup module104. An exemplary method for generating atransition cookie250 by atransition cookie generator245 includes multiple steps as illustrated inFIGS. 3a-3c.

FIG. 3a illustrates exemplary steps for generating a transitioncookie data element330 by atransition cookie generator245. Atransition cookie generator245 includes aclock305 indicating the current time of day in microseconds in a 32-bit format.

The transitioncookie data element330 is preferably a 32-bit data element, generated by thetransition cookie generator245 based on theselective ACK321, theMSS index324 and the 32-bit current time of day indicated byclock305.Selective ACK321 is a 1-bit data element which is set to a value of “1” bytransition cookie generator245 if a TCP header in a receivedsession SYN packet210 includes an optional sack-permitted option, or to “0” if a TCP header in a receivedsession SYN packet210 does not include an optional sack-permitted option.

Maximum Segment Size (“MSS”)322 is the maximum number of bytes that TCP will allow in an TCP/IP packet, such assession SYN packet210, session SYN/ACK packet220, andsession ACK packet230, and is normally represented by an integer value in a TCP packet header. If a TCP header in a receivedsession SYN packet210 includes a maximum segment size option, thetransition cookie generator245 sets theMSS322 to equal the maximum segment size option data of the maximum segment size option. Otherwise, if the TCP header in a receivedsession SYN packet210 does not include a maximum segment size option, thetransition cookie generator245 sets theMSS322 to a default value, for example, such as integer “536”. TheMSS index324 is a 4-bit data element set by thetransition cookie generator245 based on theMSS322. Thetransition cookie generator245 preferably includes an MSS table307, which maps anMSS322 to anMSS index324. Thetransition cookie generator245 maps aMSS322 with the MSS table307 to set the value ofMSS index324. For example,MSS322 has an integer value of “1460”. After the mapping,MSS index324 has a value of “4” as represented in hexadecimal format. In an alternative embodiment, means other than an MSS table307 may be employed to determine theMSS index324 value, such as the use of a mapping algorithm.

In generating a transitioncookie data element330, thetransition cookie generator245 sets a transitioncookie data element330 to equal the 32-bit current time of day indicated byclock305. For example, the 32-bit current time of day may be “A68079E8” as represented in hexadecimal format, so the transitioncookie data element330 has a value of “A68079E8”.

Next, thetransition cookie generator245 replaces the least significant 4 bits (bit0-3) of transitioncookie data element330 with theMSS index324, and replaces bit4 of a transitioncookie data element330 withselective ACK321. For example, if a transitioncookie data element330 has been set to a value of “A68079E8”,selective ACK321 has a value of “1”, andMSS index324 has a value of “4” as represented in hexadecimal format, after the replacements, transitioncookie data element330 has a value of “A68079F4” in hexadecimal format.

FIG. 3b illustrates exemplary steps for generating a transition cookiesecret key360, such as by atransition cookie generator245 based on data obtained from a receivedsession SYN packet210. The data used in generating the transition cookiesecret key360 may include at least thesource IP address312 of an IP header, adestination port314, asource port316 and asequence number318 of a TCP header in a receivedsession SYN packet210. In generating a transition cookiesecret key360, atransition cookie generator245 forms a 96-bit data element, afirst data item340, by concatenating asource IP address312, asequence number318, asource port316, and adestination port314. For example, if thesource IP address312 is 192.168.1.134, the hexadecimal representation being “C0A80186”, thesequence number318 is “9A275B84”, thesource port316 is 4761, the hexadecimal representation being “1299”, and thedestination port314 is 240, the hexadecimal representation being “00F0”, then, after the concatenation, thefirst data item340 has a hexadecimal value of “C0A801869A275B84129900F0”.

Next, since the transition cookiesecret key360 is a 128-bit data element, thetransition cookie generator245 may use a hash function to generate the transition cookie secret key360 from thefirst data item340. Further, thetransition cookie generator245 may use a secret key offset301, which may be a 6-bit integer value, to select a 6-bit non-negative integer fromfirst data item340 starting at the bit indicated by secret key offset301. For example, if the secret key offset301 has a value of “12” and thefirst data item340 has a hexadecimal value of “C0A801869A275B84129900F0”, thetransition cookie generator245 selects a 6-bit non-negative integer from thefirst data item340 starting at bit12 (bit12-17). The selected non-negative integer is of this example is thus “16”. Thetransition cookie generator245 then uses the selected non-negative integer to select 64 bits of data from thefirst data item340, starting at the bit indicated by the selected non-negative integer, to generate thesecond data item350, which has 64 bits.

For example, if the selected non-negative integer is “8” and thefirst data item340 has a hexadecimal value of “C0A801869A275B84129900F0”, thetransition cookie generator245 selects 64 bits (bit8-71) of thefirst data item340 to generate asecond data item350, having a hexadecimal value of “869A275B84129900”. In another example, if the selected non-negative integer is “52”, and thetransition cookie generator245 selects 64 bits (bit52-95 and bit0-19) of thefirst data item340 in a wrap-around fashion, bits52-95 have a hexadecimal value of “C0A801869A2”, and bit0-19 have a hexadecimal value of “900F0”, so the generatedsecond data item350 has a hexadecimal value of “900F0C0A801869A2”. Thetransition cookie generator245 then generates a transition cookiesecret key360 by storing thesecond data item350 in the least significant 64 bits (bit0-63) of the transition cookiesecret key360 and setting the most significant 64 bits (bit64-127) to “0”. For example, if thesecond data item350 has a hexadecimal value of “869A275B84129900”, the transition cookiesecret key360 has a hexadecimal value of “0000000000000000869A275B84129900”.

FIG. 3c illustrates exemplary steps for generating atransition cookie250 based on a transitioncookie data element330, a transition cookiesecret key360, and data obtained from a receivedsession SYN packet210, including asequence number318 of a TCP header in a receivedsession SYN packet210. To generate atransition cookie250, atransition cookie generator245 applies acryptographic method308 on the transition cookiesecret key360 and the transitioncookie data element330, such as an RC5 algorithm described in IETF RFC 2040 “The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms” section 1 “Overview”, and sections 2-8 with detailed explanations, incorporated herein by reference. The RC5 algorithm takes a 32-bit plaintext input and a 128-bit encryption key to generate a 32-bit ciphertext output. Thetransition cookie generator245 uses the transitioncookie data element330 as the plaintext input to the RC5 algorithm, and the transition cookiesecret key360 as the encryption key input to the RC5 algorithm. Thetransition cookie generator245 stores the resulting 32-bit ciphertext output of the RC5 algorithm in theencrypted data element370.

Next, thetransition cookie generator245 performs an unsigned binary addition on anencrypted data element370 and thesequence number318, and stores the result in thetransition cookie250. For example, if theencrypted data element370 has a value of “0025BC83” in hexadecimal format, and thesequence number318 has a value of “0743BD55” in hexadecimal format, the result of the addition is hexadecimal “076979D8”. After the addition, thetransition cookie250 has a value of “076979D8” in hexadecimal. In another example, if theencrypted data element370 has a value of “BE43D096” in hexadecimal format, and thesequence number318 has a value of “9A275B84” in hexadecimal format, the result of the addition, and the value oftransition cookie250 is hexadecimal “1586B2C1A”, with the most significant bit carried beyond the 32-bit boundary.

In another embodiment, atransition cookie generator245 may use different steps to generate a transition cookiesecret key360. For example, a secret key offset301 may be an integer of a different bit length, such as a 4-bit integer value, a 3-bit integer value, or a 5-bit integer value. Also, atransition cookie generator245 may use a secret key offset301 to select a non-negative integer value of a different bit length from afirst data item340. For example, atransition cookie generator245 may select a 4-bit non-negative integer value, a 7-bit non-negative integer value, or a 5-bit non-negative value from afirst data item340.

In other embodiments, atransition cookie generator245 may store asecond data item350 in the least significant 64 bits (bit0-63) of a transition cookiesecret key360 or storesecond data item350 in the most significant 64 bits (bit64-127) of a transition cookiesecret key360.

Atransition cookie generator245 may also perform an exclusive-or operation on the most significant 48 bits (bit0-47) of afirst data item340 and the least significant 48 bits (bit48-95) of afirst data element340 to form a 48-bit temporary data element (not shown). Similarly, in another embodiment, atransition cookie generator245 may perform an exclusive-or operation on the 48 even bits (bit0,2,4, . . .90,92,94) and the 48 odd bits (bit1,3,5, . . .93,95,97) to form a 48 bit temporary data element. In yet another embodiment, atransition cookie generator245 may store a 48-bit temporary data element in the least significant 48 bits (bit0-47) and the most significant 48 bits (bit80-127) of a transition cookiesecret key360, and set bit48-79 to “0”, or store a 48-bit temporary data element in the least significant 48 bits (bit0-47) of a transition cookiesecret key360, and set the most significant 80 bits (bit48-127) of a transition cookiesecret key360 to “0”.

In other embodiments of the invention, atransition cookie generator245 may use an encryption algorithm to generate a transition cookie secret key360 from thefirst data item340.

In another embodiment, atransition cookie generator245 includes a secret key and an encryption algorithm, and uses afirst data element340 as a plaintext input, and a secret key as an encryption key input to the encryption algorithm to generate a 128-bit ciphertext output. Next, atransition cookie generator245 generates a transition cookiesecret key360 as a 128-bit ciphertext output. Alternatively, the ciphertext output may be a 96-bit data element, and atransition cookie generator245 stores a 96-bit ciphertext output in the least significant 96 bits (bit0-95) of a transition cookiesecret key360, and sets the most significant 32 bits (bit96-127) to “0”. In another alternative, atransition cookie generator245 stores the least significant 32 bits (bit0-31) of a 96-bit ciphertext output in the most significant 32 bits (bit96-127) of a transition cookiesecret key360.

As seen inFIG. 2, atransition cookie validator275 validates acandidate transition cookie270 generated from asession ACK packet230 received by the TCPsession setup module104. An exemplary method for validating acandidate transition cookie270 by atransition cookie validator275 may include multiple steps as illustrated inFIGS. 4a-4d.

FIG. 4a illustrates exemplary steps for generating a candidateencrypted data element470 by atransition cookie validator275 based on data obtained from a receivedsession ACK packet230. The candidateencrypted data element470 may be a 32-bit data element generated based on thesequence number418 of the TCP header in the receivedsession ACK packet230, and thecandidate transition cookie270 generated from the receivedsession ACK packet230 as illustrated inFIG. 2.

Thecandidate sequence number428 may be a 32-bit data element generated by atransition cookie validator275 such that the sum ofcandidate sequence number428 and a value of “1” equals thesequence number418.

The candidateencrypted data element470 is generated by thetransition cookie validator275 such that the result of performing an unsigned binary addition of the candidateencrypted data element470 and thecandidate sequence number428 equals thecandidate transition cookie270.

FIG. 4b illustrates exemplary steps for generating a candidate transition cookiesecret key460 by thetransition cookie validator275 based on data obtained from the receivedsession ACK packet230 and acandidate sequence number428. The data used for generating the candidate transition cookiesecret key460 may include at least asource IP address412 of the IP header in a receivedsession ACK packet230, adestination port414 and asource port416 of the TCP header in a receivedsession ACK packet230. In the process, a 96-bitfirst data item440 is formed by atransition cookie validator275 by concatenating asource IP address412, acandidate sequence number428, asource port416, and adestination port414. For example, if thesource IP address412 is 192.168.1.134, having a hexadecimal representation of “C0A80186”, thecandidate sequence number428 is hexadecimal “9A275B84”, thesource port416 is 4761, having a hexadecimal representation of “1299”, and thedestination port414 is 240, having a hexadecimal representation of “00F0”, after the concatenation, thefirst data item440 has a hexadecimal value of “C0A801869A275B84129900F0”.

Next, the 128-bit candidate transition cookiesecret key460 is generated from afirst data item440 by atransition cookie validator275 using a hash function. In an embodiment, atransition cookie validator275 uses a 6-bit secret key offset401 to select a 6-bit non-negative integer from afirst data item440 starting at a bit indicated by secret key offset401. For example, if the secret key offset401 has a value of “12” and thefirst data item440 is “C0A801869A275B84129900F0”, thetransition cookie validator275 selects a 6-bit non-negative integer from thefirst data item440 starting at bit12 (bits12-17), selecting the non-negative integer “16”. Thetransition cookie validator275 then generates a 64-bitsecond data item350 by using the selected non-negative integer to select 64 bits of data from thefirst data item440, starting at the bit indicated by the selected non-negative integer.

For example, if the selected non-negative integer is “8” and thefirst data item440 has a hexadecimal value of “C0A801869A275B84129900F0”, thetransition cookie validator275 selects 64 bits (bit8-71) of thefirst data item440 to generate asecond data item450 having a hexadecimal value of “869A275B84129900”. In another example, if thefirst data item440 has a hexadecimal value of “C0A801869A275B84129900F0”, and the selected non-negative integer is “52”, thetransition cookie validator275 selects 64 bits (bit52-95 and bit0-19) in a wrap-around fashion. Bits52-95 have a hexadecimal value of “C0A801869A2”, and bits0-19 have a hexadecimal value of “900F0”, so the generatedsecond data item450 has a hexadecimal value of “900F0C0A801869A2”.

Next, thetransition cookie validator275 generates a candidate transition cookiesecret key460 by storing thesecond data item450 in the least significant 64 bits (bit0-63) of the candidate transition cookiesecret key460 and setting the most significant 64 bits (bit64-127) to “0”. For example, if thesecond data item450 has a hexadecinmal value of “869A275B84129900”, the candidate transition cookiesecret key460 has a hexadecimal value of “0000000000000000869A275B84129900”.

FIG. 4C illustrates exemplary steps for generating a candidate transitioncookie data element430 by atransition cookie validator275 based on a candidateencrypted data element470 and a candidate transition cookiesecret key460.

In an embodiment, atransition cookie validator275 applies acryptographic method408 on a candidate transition cookiesecret key460 and a candidateencrypted data element470. Anexemplary cryptographic method408 is an RC5 algorithm described in IETF RFC 2040 “The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms” section 1 “Overview”, and sections 2-8 with detailed explanations, incorporated herein by reference. The RC5 algorithm takes a 32-bit ciphertext input and a 128-bit decryption key to generate a 32-bit plaintext output. Atransition cookie validator275 uses a candidateencrypted data element470 as a ciphertext input to the RC5 algorithm, and a candidate transition cookiesecret key460 as a decryption key input to the RC5 algorithm, to generate a 32-bit candidate transitioncookie data element430 as the plaintext output of the RC5 decryption algorithm.

FIG. 4d illustrates exemplary steps by atransition cookie validator275 of validating a candidate transitioncookie data element430. In an embodiment, atransition cookie validator275 includes aclock305. Theclock305 indicates the current time of day, preferably in microseconds in a 32-bit format. The modifiedcurrent time409 is a 32-bit data element set by atransition cookie validator275 sets to the current time indicated byclock305. Atransition cookie validator275 then sets the least significant 5 bits (bit0-4) of the modifiedcurrent time409 to “0”. For example, if the modifiedcurrent time409 has a value of “89AE03F6” in hexadecimal format, after setting the least significant 5 bits to “0”, the modifiedcurrent time409 has a hexadecimal value of “89AE03E0”.

Next, atransition cookie validator275 sets a 32-bit adjusted candidate transitioncookie data element431 to equal the candidate transitioncookie data element430, and then sets the least significant 5 bits (bit0-4) of the adjusted candidate transitioncookie data element431 to “0”. For example, if the adjusted candidate transitioncookie data element431 has a hexadecimal value of “89DB468F”, after setting the least significant 5 bits to “0”, the adjusted candidate transitioncookie data element431 has a hexadecimal value of “89DB4680”.

Thetransition cookie validator275 may then determine if the candidate transitioncookie data element430 is valid by determining if the adjusted candidate transitioncookie data element431 is within a time margin of 3 seconds of the modifiedcurrent time409. In an embodiment, in order to determine if the adjusted candidate transitioncookie data element431 is within a time margin of 3 seconds of the modifiedcurrent time409, the transition cookie stores the modifiedcurrent time409 in the least significant 32 bits (bit0-31) of a first 33-bit time data element, sets the most significant bit (bit32) to “0”, and adds 6 seconds to the first 33-bit time data element. Adding 6 seconds is to add 6,000,000 micro seconds as represented by “5B8D80” in hexadecimal format. For example, if before the addition, the first 33-bit time data element has a hexadecimal value of “0FFFFFAE2”, After the addition of “5B8D80”, the first 33-bit time data element has a hexadecimal value of “1005B8862”. Thetransition cookie validator275 stores the adjusted candidate transitioncookie data element431 in the least significant 32 bits (bit0-31) of a second 33-bit time data element, sets the most significant bit (bit32) to “0”, and adds 3 seconds to the second 33-bit time data element. Adding 3 seconds is to add 3,000,000 micro seconds as represented by hexadecimal “2DC6C0”. Thetransition cookie validator275 stores the modifiedcurrent time409 in the least significant 32 bits (bit0-31) of a third 33-bit time data element, and sets the most significant bit (bit32) to “0”. If the second 33-bit time data element is smaller than the first 33-bit time data element and the second 33-bit time data element is larger than the third 33-bit time data element, thetransition cookie validator275 determines that the adjusted candidate transitioncookie data element431 is within 3 seconds of the modifiedcurrent time409, and thus that the candidate transitioncookie data element430 is valid.

FIG. 5 illustrates exemplary steps of generating information based on a validated candidate transitioncookie data element430. In an embodiment,candidate MSS522 is an integer. Atransition cookie validator275 includes a reversed MSS table507, which includes information that maps a 4-bit data element to acandidate MSS522. Atransition cookie validator275 extracts the least significant 4-bit (bit0-3) data from candidate transitioncookie data element430, maps the extracted 4-bit data to a reversed MSS table507, and stores the result in acandidate MSS522. Atransition cookie validator275 may then generate a maximum segment size option as described in IETF RFC 793 “Transmission Control Protocol” section 3.1 “Header Format”, incorporated herein by reference, and sets a maximum segment size option data of the maximum segment size option to equal acandidate MSS522. Atransition cookie validator275 may further examine bit4 of a candidate transitioncookie data element430. If bit4 of candidate transitioncookie data element430 has a value of “1”, atransition cookie validator275 may generate a sack-permitted option as described in IETF RFC 2018 “TCP Selective Acknowledgement Options” section 2, incorporated herein by reference. A TCPsession setup module104 may then send a sack-permitted option, a maximum segment size option, and data obtained from a receivedsession ACK packet230 to a computing module (not shown) for further processing.

There are many different encryption algorithms that use encryption keys of different bit lengths, such as, for example, 56-bit, 64-bit, 96-bit, 128-bit. These may generate ciphertext outputs of different bit lengths, for example, 96-bit, 64-bit, 128-bit, or 32-bit. Persons of ordinary skill in the cipher arts will be able to apply different methods, for example a hash function, to generate the transition cookie secret key360 from the ciphertext output.

Atransition cookie validator275 may also use different steps to generate a candidate transition cookiesecret key460. The steps used by atransition cookie validator275 to generate a candidate transition cookiesecret key460 are similar to the steps used by atransition cookie generator245 to generate a transition cookiesecret key360.

Alternative embodiments of the invention may employ a different algorithm for thecryptographic methods308,408. In one example, the different algorithm is an RC2 algorithm described in IETF RFC 2268 “A Description of the RC2(r) Encryption Algorithm” section 1 “Introduction” and section 2-4 with detailed explanation, incorporated herein by reference. In another example, the different algorithm is a Blowfish algorithm. In one other example, the different algorithm is a Data Encryption Standards (“DES”) algorithm based on Federal Information Processing Standards Publication “Data Encryption Standard (DES) FIPS PUB 46-3”, which is incorporated herein by reference in its entirety. Other algorithms are also usable.

Also, atransition cookie validator275 may use different time margins of modifiedcurrent time409 to determine if the candidate transition cookie data element is valid. Different time margins include but are not limited to 1 second, 4 seconds, 6 seconds, 2 seconds, or 11 seconds.

In an embodiment, the method of generating a transition cookie includes MD5 signature option information in the TCP options field. When this method is used, the method of validating acandidate transition cookie270 correspondingly includes the MD5 signature option information in the TCP options field.

In another embodiment,transition cookie generator245 may include a plurality of transition cookie generation methods forgenerating transition cookie250. For example, the secret key offset301 may have a different value, such as an integer value of different bit length, such as 4-bit, or 8-bit. In other examples, the selected non-negative integer fromfirst data item340 may be of different bit length, such as 8-bit, or 10-bit, thecryptographic method308 may be a different algorithm than RC5, or the generating of transitioncookie data element330 may include MD5 signature option information in the TCP options field ofsession SYN packet210. A transition cookie generation method may include steps different from the steps in the exemplary method illustrated inFIGS. 3a-3c.

In an embodiment, thetransition cookie generator245 may selects method to generatetransition cookie250 based on random data.

The random data may include time. In one embodiment,transition cookie generator245 selects a method based on the time of day. Alternatively, thetransition cookie generator245 may select a method after a time period, such as 10 seconds, 30 seconds, 2 minutes or 3 hours.

In another embodiment, the random data may include a source IP address insession SYN packet210, or a destination IP address insession SYN packet210.

The random data may include the network interface at which a TCPsession setup module104 receives asession SYN packet210, or a Virtual Local Area Network (VLAN) information associated with asession SYN packet210.

In one embodiment,transition cookie validator275 includes a plurality of transition cookie validation methods for validatingcandidate transition cookie270. A transition cookie validation method may include steps different from the steps in the exemplary method illustrated inFIGS. 4a-4d. Atransition cookie validator275 may select a method to validatecandidate transition cookie270 based on random data.

In these embodiments it is understood to be preferred that thetransition cookie validator275 selects a complementary method to the method selected bytransition cookie generator245.

Although the invention herein has been described with reference to particular embodiments, it is to be understood that these embodiments are merely illustrative of the principles and applications of the present invention. It is therefore to be understood that numerous modifications may be made to the illustrative embodiments and that other arrangements may be devised without departing from the spirit and scope of the present invention as defined by the appended claims.

Claims (28)

The invention claimed is:

1. A system for TCP SYN cookie validation at a host server comprising:

a session SYN packet receiver for receiving a session SYN packet;

a transition cookie generator operating to generate a transition cookie with the use of a transition cookie secret key, the transition cookie comprising a time value representing the actual time, wherein the transition cookie generator generates the transition cookie secret key based on data obtained from the received session SYN packet, the data obtained from the SYN packet including at least one of a source IP address of an IP header, a destination port, a source port, and a sequence number of a TCP header in the received session SYN packet, wherein the transition cookie generator concatenates the obtained data from the session SYN packet to generate a first data item of the generator and the transition cookie generator uses a first hash function to generate the transition cookie secret key from the first data item of the generator;

a session SYN/ACK packet sender for sending the transition cookie in response to the received session SYN packet;

a session ACK packet receiver for receiving a session ACK packet, the session ACK packet including a candidate transition cookie; and

a transition cookie validator, for determining whether the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received, wherein the transition cookie validator generates a candidate transition cookie secret key based on data obtained from the received session ACK packet, the data obtained from the ACK packet including at least one of a source IP address of the IP header, a destination port, and a source port, wherein the transition cookie validator concatenates the obtained data from the session ACK packet to generate a first data item of the validator and the transition cookie validator uses the first or another hash function to generate the candidate transition cookie secret key from the first data item of the validator,

wherein at least one of:

the transition cookie generator uses a secret key offset to select one or more bits of data from the first data item of the generator in order to generate a second data item of the generator, and

the transition cookie validator uses a candidate secret key offset to select one or more bits of data from the first data item of the validator in order to generate a second data item of the validator.

2. The system according toclaim 1, in which the transition cookie validator determines that the received session ACK packet is valid if the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

3. The system according toclaim 1, in which the predetermined time interval is in the range of one to six seconds.

4. The system according toclaim 1, in which the predetermined time interval is three seconds.

5. The system according toclaim 1, in which the generating of the transition cookie includes the use of random data.

6. The system according toclaim 1, in which the generating of the transition cookie includes the use of data obtained from the session SYN packet.

7. A system for TCP SYN cookie validation at a host server comprising:

a session SYN packet receiver for receiving a session SYN packet;

a transition cookie generator operating to generate a transition cookie with the use of a transition cookie secret key, the transition cookie comprising a time value representing the actual time, wherein the transition cookie generator generates the transition cookie by (i) generating an encrypted data element of the generator by applying a cryptographic method on the transition cookie secret key and a transition cookie data element, (ii) performing an unsigned binary addition on the encrypted data element of the generator and a sequence number of a TCP header in the received session SYN packet, and (iii) storing the result in the transition cookie;

a session SYN/ACK packet sender for sending the transition cookie in response to the received session SYN packet;

a session ACK packet receiver for receiving a session ACK packet, the session ACK packet including a candidate transition cookie; and

a transition cookie validator, for determining whether the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

8. The system according toclaim 7, wherein the transition cookie data element comprises data based on at least one of: a selective ACK, an MSS index, and a 32-bit current time of day indicated by a clock.

9. A system for TCP SYN cookie validation at a host server comprising:

a session SYN packet receiver for receiving a session SYN packet;

a transition cookie generator operating to generate a transition cookie with the use of a transition cookie secret key, the transition cookie comprising a time value representing the actual time;

a session SYN/ACK packet sender for sending the transition cookie in response to the received session SYN packet;

a session ACK packet receiver for receiving a session ACK packet, the session ACK packet including a candidate transition cookie; and

a transition cookie validator, for determining whether the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received, wherein the transition cookie validator generates:

a candidate sequence number such that a sequence number of a TCP header in the received session ACK packet equals the sum of the candidate sequence number and a value of 1,

a candidate encrypted data element such that the result of performing an unsigned binary addition of the candidate encrypted data element and a candidate sequence number equals the candidate transition cookie, and

a candidate transition cookie data element by applying a cryptographic method on a candidate transition cookie secret key and the candidate encrypted data element.

10. The system according toclaim 9, wherein the transition cookie validator validates the candidate transition cookie data element by adjusting the candidate transition cookie data element to generate, and determining if the adjusted candidate transition cookie data element is within a predetermined time margin of a modified current time.

11. A system for TCP SYN cookie validation at a host server, the system comprising:

at least one processor and a memory storing:

a session SYN packet receiver, wherein when the session SYN packet receiver is executed by the at least one processor, the session SYN packet receiver causing the at least one processor to receive a session SYN packet;

a transition cookie generator, the transition cookie generator being executed by the at least one processor to generate a transition cookie with the use of a transition cookie secret key, the transition cookie comprising a time value representing the actual time;

a session SYN/ACK packet sender, the session SYN/ACK packet sender being executed by the at least one processor to send the transition cookie in response to the received session SYN packet;

a session ACK packet receiver, the session ACK packet receiver being executed by the at least one processor to receive a session ACK packet, the session ACK packet including a candidate transition cookie; and

a transition cookie validator, the transition cookie validator being executed by the at least one processor to determine whether the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received; and

wherein:

the transition cookie generator is executed by the at least one processor to generate the transition cookie secret key based on data obtained from the received session SYN packet;

the transition cookie validator is executed by the at least one processor to generate a candidate transition cookie secret key based on data obtained from the received session ACK packet;

the transition cookie generator is executed by the at least one processor to concatenate the obtained data from the session SYN packet to generate a first data item of the generator;

the transition cookie validator is executed by the at least one processor to concatenate the obtained data from the session ACK packet to generate a first data item of the validator;

the transition cookie generator is executed by the at least one processor to use a secret key offset to select one or more bits of data from the first data item of the generator in order to generate a second data item of the generator, and

the transition cookie validator is executed by the at least one processor to use a candidate secret key offset to select one or more bits of data from the first data item of the validator in order to generate a second data item of the validator.

12. The system according to claim 11, wherein:

when the transition cookie secret key is generated based on data obtained from the received session SYN packet, the obtained data includes at least one of: a source IP address of an IP header, a destination port, a source port, and a sequence number of a TCP header in the received session SYN packet, and

when the candidate transition cookie secret key is generated based on data obtained from the received session ACK packet, the obtained data includes at least one of:

a source IP address of the IP header, a destination port, and a source port.

13. The system according to claim 11, wherein at least one of:

the transition cookie generator is executed by the at least one processor to use a first hash function to generate the transition cookie secret key from the first data item of the generator, and

when the transition cookie validator is executed by the at least one processor to use the first or another hash function to generate the candidate transition cookie secret key from the first data item of the validator.

14. The system according to claim 11, in which the transition cookie validator is executed by the at least one processor to determine that the received session ACK packet is valid if the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

15. The system according to claim 11, in which the predetermined time interval is in the range of one to six seconds.

16. The system according to claim 11, in which the predetermined time interval is three seconds.

17. The system according to claim 11, in which the generating of the transition cookie includes the use of random data.

18. The system according to claim 11, in which the generating of the transition cookie includes the use of data obtained from the session SYN packet.

19. A system for TCP SYN cookie validation at a host server, the system comprising:

at least one processor and a memory storing:

a session SYN packet receiver, wherein the session SYN packet receiver is executed by the at least one processor to receive a session SYN packet;

a transition cookie generator, wherein the transition cookie generator is executed by the at least one processor to generate a transition cookie with the use of a transition cookie secret key, the transition cookie comprising a time value representing the actual time;

a session SYN/ACK packet sender, wherein the session SYN/ACK packet sender is executed by the at least one processor to send the transition cookie in response to the received session SYN packet;

a session ACK packet receiver, wherein when the session ACK packet receiver is executed by the at least one processor to receive a session ACK packet, the session ACK packet including a candidate transition cookie; and

a transition cookie validator, wherein the transition cookie validator is executed by the at least one processor to determine whether the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received; and wherein:

the transition cookie generator is executed by the at least one processor to generate the transition cookie by (i) generating an encrypted data element of the generator by applying a cryptographic method on the transition cookie secret key and a transition cookie data element, (ii) performing an unsigned binary addition on the encrypted data element of the generator and a sequence number of a TCP header in the received session SYN packet, and (iii) storing the result in the transition cookie.

20. The system according to claim 19, wherein the transition cookie data element comprises data based on at least one of: a selective ACK, an MSS index, and a 32-bit current time of day indicated by a clock.

21. The system according to claim 19, in which the transition cookie validator is executed by the at least one processor to determine that the received session ACK packet is valid if the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

22. The system according to claim 19, in which the predetermined time interval is in the range of one to six seconds.

23. The system according to claim 19, in which the predetermined time interval is three seconds.

24. The system according to claim 19, in which the generating of the transition cookie includes the use of random data.

25. The system according to claim 19, in which the generating of the transition cookie includes the use of data obtained from the session SYN packet.

26. A system for TCP SYN cookie validation at a host server, the system comprising:

at least one processor and a memory storing:

a session SYN packet receiver, wherein the session SYN packet receiver is executed by the at least one processor to receive a session SYN packet;

a transition cookie generator, wherein the transition cookie generator is executed by the at least one processor to generate a transition cookie with the use of a transition cookie secret key, the transition cookie comprising a time value representing the actual time;

a session SYN/ACK packet sender, wherein the session SYN/ACK packet sender is executed by the at least one processor to send the transition cookie in response to the received session SYN packet;

a session ACK packet receiver, wherein the session ACK packet receiver is executed by the at least one processor to receive a session ACK packet, the session ACK packet including a candidate transition cookie; and

a transition cookie validator, wherein the transition cookie validator is executed by the at least one processor to determine whether the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received; and to generate:

a candidate sequence number such that a sequence number of a TCP header in the received session ACK packet equals the sum of the candidate sequence number and a value of 1,

a candidate encrypted data element such that the result of performing an unsigned binary addition of the candidate encrypted data element and a candidate sequence number equals the candidate transition cookie, and

a candidate transition cookie data element by (i) applying a cryptographic method on a candidate transition cookie secret key and the candidate encrypted data element.

27. The system according to claim 26, wherein the transition cookie validator is executed by the at least one processor to validate the candidate transition cookie data element by adjusting the candidate transition cookie data element to generate, and determining if the adjusted candidate transition cookie data element is within a predetermined time margin of a modified current time.

28. The system according to claim 26, in which when the transition cookie validator is executed by the at least one processor to determine that the received session ACK packet is valid if the candidate transition cookie in the received session ACK packet comprises a time value representing a time within a predetermined time interval from the time the session ACK packet is received.

Images