Defending against denial of service attacks

BACKGROUND

Software vendors may deploy services on servers connected to a network, such as, for example, the Internet, or other networks. When the services are provided on the Internet, the services may be called web services. Third parties may use the deployed services by accessing the servers. If a server, which provides a particular service, is not operational, then the particular service is not available and a software vendor who provides the particular service may appear to be unreliable.

Services, such as, for example, publicly-provided web services, may be attacked by hackers. One type of attack that hackers may employ includes the use of botnets (multiple processing devices working in tandem, typically, with a malicious purpose) to overload and effectively, disable a server. Such an attack is called a Denial of Service (DoS) attack.

SUMMARY

This Summary is provided to introduce a selection of concepts in a simplified form that is further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

In embodiments consistent with the subject matter of this disclosure, a server may send a challenge to a processing device in response to receiving a request, from the processing device, for access to a service. The challenge may include a partial key for a memory-intensive operation to be performed by the processing device, as well as a number of iterations of the memory-intensive operation to perform, and a result of performing the number of iterations of the memory-intensive operation. Upon receiving the challenge, the processing device may search for a complete key consistent with the partial key and may perform the memory-intensive operation for the number of iterations to produce a proposed result. If the proposed result matches the result included in the challenge, the processing device may send a challenge answer, including the complete key, to the server. If the server determines that the complete key included in the challenge answer is correct, then the server may access the requested service and may return a result of the access to the processing device.

In some embodiments, consistent with the subject matter of this disclosure, the server may calculate a blinding value, corresponding to a number of hidden bits of the partial key. The blinding value may be based, at least in part, on a level of busyness of the server. Further, in some embodiments, the server may include, with the challenge, a timestamp and a digital signature, signed with the server's private key. If the response to the challenge is not received by the server within a predetermined time window, or the response does not include a valid digital signature then the server may discard the response. Additionally, in some embodiments, the server may maintain a cache of recently received challenge answers and may discard a newly received answer if it is already in the cache.

In various embodiments, the memory-intensive operation may include a stream cipher operation. Other embodiments may include other memory-intensive operations.

DRAWINGS

In order to describe the manner in which the above-recited and other advantages and features can be obtained, a more particular description is described below and will be rendered by reference to specific embodiments thereof which are illustrated in the appended drawings. Understanding that these drawings depict only typical embodiments and are not therefore to be considered to be limiting of its scope, implementations will be described and explained with additional specificity and detail through the use of the accompanying drawings.

<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates an exemplary operating environment for embodiments consistent with the subject matter of this disclosure.

<figref idrefs="DRAWINGS">FIG. 2</figref> is a functional block diagram of a processing device, which may be used to implement a server or a processing device shown in <figref idrefs="DRAWINGS">FIG. 1</figref>.

<figref idrefs="DRAWINGS">FIGS. 3-6</figref> are flowcharts illustrating exemplary processes that may be performed by an embodiment of a server consistent with the subject matter of this disclosure.

<figref idrefs="DRAWINGS">FIG. 7</figref> is a flowchart illustrating an exemplary process that may be performed by an embodiment of a processing device acting as a client.

DETAILED DESCRIPTION

Embodiments are discussed in detail below. While specific implementations are discussed, it should be understood that this is done for illustration purposes only. A person skilled in the relevant art will recognize that other components and configurations may be used without parting from the spirit and scope of the subject matter of this disclosure.

Overview

In embodiments consistent with the subject matter of this disclosure, a network-connected processing device, such as, for example, a client device, may send a request to access a service provided via the network. A processing device, such as, for example, a server, which provides the service, may receive the request and may respond by creating and transmitting a challenge to the client device. In some embodiments, the challenge may include a partial key for a memory-intensive operation, a number of iterations to perform, and a result of performing the memory-intensive operation for the number of iterations using a complete key corresponding to the partial key. In some embodiments, a number of bits of the partial key not provided may be determined based on a level of busyness of the server. The level of busyness may be determined based on processor utilization of the server and/or a length of a queue, such as, for example, a queue of requests for accessing the service. In other embodiments, the level of busyness may be determined based on one or more other factors.

The client device may receive the challenge and may select a proposed complete key corresponding to the partial key. The client device may then perform the memory-intensive operation for the number of iterations using the proposed complete key to produce a proposed result. If the proposed result equals the result included with the challenge, the client device may transmit a challenge answer, including the proposed complete key, to the server. Otherwise, the client device may select a next proposed complete key corresponding to the partial key and may repeat performing of the memory-intensive operation for the number of iterations using the next proposed complete key to produce a next proposed result. The client device may repeat the process until use of a proposed complete key produces a proposed result that matches the result included with the challenge.

The server may receive the challenge answer and may determine whether the challenge answer is correct. A correct challenge answer may include a proposed complete key that matches a complete key used by the server to create the challenge. If the challenge answer is determined to be correct, the server may access the requested service and may return a result of accessing the requested service to the client device.

In some embodiments consistent with the subject matter of this disclosure, the challenge may be transmitted by the server with a timestamp and a digital signature, which may be calculated over the challenge and the timestamp. The challenge answer provided by the client device may include the challenge, a copy of the timestamp included with the challenge, and the digital signature. If the challenge answer received by the server includes a correct challenge answer, a valid digital signature, and a copy of the timestamp indicating a time within a predetermined time window of a current time, then the server may access a requested service and may provide a result of accessing the requested service to the client device.

Exemplary Operating Environment

<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates an exemplary operating environment <b>100</b> for embodiments consistent with the subject matter of this disclosure. Operating environment <b>100</b> may include a network <b>102</b>, a processing device <b>104</b>, and one or more servers <b>106</b>.

Network <b>102</b> may be a single network or a combination of networks, such as, for example, the Internet. Network <b>102</b> may include a wireless network, a wired network, a packet-switching network, a public switched telecommunications network, a fiber-optic network, other types of networks, or any combination of the above.

Processing device <b>104</b> may be a user's processing device, such as, for example, a desktop personal computer (PC), a laptop PC, a handheld processing device, or other processing device. In embodiments consistent with the subject matter of this disclosure, processing device <b>104</b> may function as a client, which may request a service provided by a server via network <b>102</b>. In embodiments in which the service is provided via the Internet, the service may be called a web service.

Server <b>106</b> may be a processing device or a group of processing devices configured to work together to provide a service via network <b>102</b>. In embodiments in which server <b>106</b> include a group of processing devices, the processing devices may be configured as a server farm.

Exemplary Processing Device

<figref idrefs="DRAWINGS">FIG. 2</figref> is a functional block diagram that illustrates an exemplary processing device <b>200</b>, which may be used to implement embodiments of processing device <b>104</b> and/or server <b>106</b> consistent with the subject matter of this disclosure.

Processing device <b>200</b> may include a bus <b>210</b>, an input device <b>220</b>, a memory <b>230</b>, a read only memory (ROM) <b>240</b>, an output device <b>250</b>, a processor <b>260</b>, a storage device <b>270</b>, and a communication interface <b>280</b>. Bus <b>210</b> may permit communication among components of processing device <b>200</b>.

Processor <b>260</b> may include at least one conventional processor or microprocessor that interprets and executes instructions. Memory <b>230</b> may be a random access memory (RAM) or another type of dynamic storage device that stores information and instructions for execution by processor <b>260</b>. Memory <b>230</b> may also store temporary variables or other intermediate information used during execution of instructions by processor <b>260</b>. ROM <b>240</b> may include a conventional ROM device or another type of static storage device that stores static information and instructions for processor <b>260</b>. Storage device <b>270</b> may include any type of media for storing data and/or instructions.

Input device <b>220</b> may include a keyboard or other input device. Output device <b>250</b> may include one or more conventional mechanisms that output information to the user, including one or more display screens, or other output devices.

Communication interface <b>280</b> may include a transceiver for transmitting and receiving information to or from network <b>102</b>. Communication interface <b>280</b> may transmit and receive information via a wireless or wired connection.

Processing device <b>200</b> may perform such functions in response to processor <b>260</b> executing sequences of instructions contained in a tangible machine-readable medium, such as, for example, memory <b>230</b>, ROM <b>240</b>, or other medium. Such instructions may be read into memory <b>230</b> from another machine-readable medium, such as storage device <b>270</b>, or from a separate device via communication interface <b>280</b>.

Exemplary Server Processes

<figref idrefs="DRAWINGS">FIG. 3</figref> is a flowchart illustrating an exemplary process, which may be performed in embodiments of server <b>106</b> consistent with the subject matter of this disclosure. The process may begin with server <b>106</b> receiving a request for access to a service, such as, for example, a web service, or other service, from processing device <b>104</b>, which may function as a client device (act <b>302</b>). Next, server <b>106</b> may create a challenge in response to receiving the request for access to the service (act <b>304</b>).

<figref idrefs="DRAWINGS">FIG. 4</figref> is a flowchart illustrating an exemplary process for performing act <b>304</b> in embodiments consistent with the subject matter of this disclosure. The process may begin with server <b>106</b> selecting a key (act <b>402</b>). In some embodiments, the key may be a variable length key having a length between 40 and 256 bits, inclusively. In other embodiments, a different key length may be employed.

Next, server <b>106</b> may determine a level of busyness (act <b>404</b>). The level of busyness may be determined based on one or more factors. In some embodiments, server <b>106</b> may determine the level of busyness based on processor utilization and/or a length of a queue, such as, for example, a queue of requests for access to a service, or another queue. In other embodiments, the level of busyness may be based on one or more other factors. Server <b>106</b> may then determine a blinding value based on the determined level of busyness (act <b>406</b>). The blinding value corresponds to a number of bits of the key to be blinded, or hidden, from the client device. In some embodiments, the blinding value may be high when a determined level of busyness is high and may be low when a determined level of busyness is low.

Server <b>106</b> may then determine a number of iterations to perform of a memory-intensive process (act <b>408</b>). In some embodiments, the number of iterations may be based on the level of busyness. For example, the number of iterations may be high when the level of busyness is high and may be low when the level of busyness is low.

Server <b>106</b> may then create a challenge by providing the key with a number of hidden bits (partial key), corresponding to the blinding value (act <b>410</b>) and by providing a result of performing the memory-intensive operation for the number of iterations (act <b>412</b>).

In some embodiments consistent with the subject matter of this disclosure, the memory-intensive operation may include a stream cipher operation, or another memory-intensive operation. The stream cipher operation may include, for example, RC4® (RC4 is a registered trademark of RSA Security, Inc. of Bedford, Mass.), ARC4 or another stream cipher operation. In one embodiment, values may be written to a block of memory and a stream cipher operation may be performed over the block of memory to generate a challenge answer.

Returning to <figref idrefs="DRAWINGS">FIG. 3</figref>, server <b>106</b> may send the challenge to processing device <b>104</b> (act <b>306</b>).

<figref idrefs="DRAWINGS">FIG. 5</figref> is a flowchart illustrating an exemplary process for performing act <b>306</b>. The process may begin with server <b>106</b> forming a challenge message including the key having a number of hidden bits (partial key), the result of performing the memory-intensive operation for the number of iterations, and a value corresponding to the number of iterations (act <b>502</b>). The number of hidden bits may correspond to the blinding value.

Server <b>106</b> may then add a timestamp to the challenge message (act <b>504</b>), and may calculate and add a digital signature to the challenge message (act <b>508</b>). The digital signature may be calculated, using a secret key of server <b>106</b> (or a secret key of a respective one of server <b>106</b> when server <b>106</b> includes a server farm), over challenge message information, including the partial key, the result of performing the memory-intensive operation for the number of iterations, the value corresponding to the number of iterations, and the timestamp. In one embodiment, the digital signature may be a hashed message authentication code (HMAC). Other types of digital signatures may be used in other embodiments. Server <b>106</b> may then send the challenge message to the client device (act <b>510</b>).

Returning to <figref idrefs="DRAWINGS">FIG. 3</figref>, server <b>106</b> may receive a challenge answer from processing device <b>104</b> (act <b>308</b>). Server <b>106</b> may then determine whether the received challenge answer is valid (act <b>310</b>).

<figref idrefs="DRAWINGS">FIG. 6</figref> is a flowchart illustrating an exemplary process for performing act <b>310</b>. The process may begin with server <b>106</b> determining whether the received challenge answer includes a valid digital signature (act <b>602</b>). In some embodiments, the received challenge answer may include a copy of the challenge, including the partial key, the number of iterations, and a result of performing the memory-intensive operation for the number of iterations, as well as a timestamp and a digital signature calculated over the copy of the challenge and the timestamp. As mentioned previously, the digital signature may be calculated according to a hashed message authentication code (HMAC). In other embodiments, the digital signature may be calculated according to another method.

If server <b>106</b> determines that the received challenge answer includes a valid digital signature signed by server <b>106</b> (or by one of server <b>106</b> when server <b>106</b> includes a server farm), then server <b>106</b> may compare the received timestamp with a current time to determine whether the challenge answer was received within a predetermined time window (act <b>604</b>). In some embodiments, the predetermined time window may be a time period of <b>15</b> minutes measured from a time indicated by the received timestamp. In other embodiments, a different predetermined time window may be employed.

If server <b>106</b> determines that the received challenge answer is received within the predetermined time window, then server <b>106</b> may determine whether the received challenge answer includes a correct challenge answer (act <b>606</b>). In some embodiments, a correct challenge answer includes a complete copy of the key selected by server <b>106</b> during act <b>402</b>. Additionally, in some embodiments, if server <b>106</b> determines that the received challenge answer is correct, then server <b>106</b> may check if the challenge answer is already in a cache of recently received answers (act <b>607</b>). If server <b>106</b> determines that the correct challenge answer is not included in the cache of recently received answers, then an indication of a valid challenge answer may be provided (act <b>608</b>).

If, during act <b>602</b>, server <b>106</b> determines that the received digital signature is invalid, or during act <b>604</b>, server <b>106</b> determines that the received challenge answer was not received within the predetermined time window, or during act <b>606</b>, server <b>106</b> determines that the challenge answer is not correct, or during act <b>607</b>, server <b>106</b> determines that this is a repetition of a previously received challenge answer, then server <b>106</b> may provide an indication that the challenge answer is invalid (act <b>610</b>).

Returning to <figref idrefs="DRAWINGS">FIG. 3</figref>, if server <b>106</b> determines that the challenge answer is invalid (an invalid challenge answer was indicated during act <b>610</b>), then server <b>106</b> may discard the challenge answer (act <b>312</b>).

If server <b>106</b> determines that the challenge answer is valid (a valid challenge answer was indicated during act <b>608</b>), then server <b>106</b> may add this challenge answer to a cache of recently received answers (act <b>313</b>). Server <b>106</b> may also determine whether a level of busyness is beyond a threshold (act <b>314</b>). For example, server <b>106</b> may determine that the level of busyness is beyond the threshold when a processor utilization of server <b>106</b> is beyond a given amount, such as, for example, 85%, or another suitable value, or when a length of a queue, such as, for example, a queue of received service requests, is beyond a queue length threshold, such as, for example, <b>100</b>, or another suitable value.

If server <b>106</b> determines that the level of busyness of server <b>106</b> is beyond the threshold, then server <b>106</b> may discard the received challenge answer (act <b>316</b>) and server <b>106</b> may repeat acts <b>304</b>-<b>314</b> to create and send a new challenge. Otherwise, server <b>106</b> may access the requested service (act <b>318</b>) and may return a result of accessing the requested service to the requesting processing device <b>104</b> (act <b>320</b>).

Exemplary Client Process

<figref idrefs="DRAWINGS">FIG. 7</figref> is a flowchart illustrating an exemplary process, which may be performed by processing device <b>104</b> acting as a client device. The process may begin with processing device <b>104</b> sending to server <b>106</b> a request to access a service (act <b>702</b>). As a result of sending the request to access a service, processing device <b>104</b> may receive from server <b>106</b> a challenge, which may include a partial key for a memory-intensive operation, such as, for example, a stream cipher operation or another operation, a value for a number of iterations, and a provided result of performing the memory-intensive operation using a complete key, corresponding to the partial key, for the number of iterations (act <b>704</b>).

Processing device <b>104</b> may then choose a complete key based on the received partial key (act <b>706</b>). In some embodiments, the key may have a key length of between 5 and 16 bytes, corresponding to 40-128 bits. In other embodiments, the key may have a different length.

Processing device <b>104</b> may perform the memory-intensive operation using the chosen complete key for the number of iterations to produce a proposed result (act <b>708</b>). In some embodiments, processing device <b>104</b> may perform a stream cipher operation using the chosen key. Processing device <b>104</b> may then determine whether the proposed result of the memory-intensive operation matches the provided result included in the received challenge (act <b>710</b>). If the proposed result does not match the provided result, then processing device <b>104</b> may choose a next complete key based on the partial key (act <b>712</b>). As an example, suppose the partial key is 1XX7AF in a hexadecimal representation, where “X” represents hidden bits. Corresponding complete keys may include, for example, 1007AF, 1017AF, 1027AF, 1037AF, . . . , 1FD7AF, 1FE7AF, and 1FF7AF. Processing device <b>104</b> may then repeat acts <b>708</b>-<b>712</b>.

If, during act <b>710</b>, processing device <b>104</b> determines that the proposed result equals the result provided in the challenge, then processing device <b>104</b> may send a challenge answer, including the proposed result, to server <b>106</b> (act <b>714</b>). In various embodiments, the challenge answer may further include a copy of information from the challenge, such as, for example, the partial key, the number of iterations, the result of performing the memory-intensive operation for the number of iterations, the timestamp, and the digital signature.

As a result of sending the challenge answer to server <b>106</b>, processing device <b>104</b> may receive a response from server <b>106</b> (act <b>716</b>). Processing device <b>104</b> may determine whether the response includes a result of accessing the requested service (act <b>718</b>). If the response includes the result of accessing the requested service, then processing device <b>104</b> may provide the result of accessing the requested service to a requester, such as, for example, a requesting application (act <b>720</b>).

If, during act <b>718</b>, processing device <b>104</b> determines that the response does not include the result of accessing the requested service, then processing device <b>104</b> may determine whether the response includes a new challenge (act <b>722</b>). If the response includes a new challenge, then processing device <b>104</b> may repeat acts <b>706</b>-<b>722</b>. If the response does not include a new challenge, then processing device <b>104</b> may provide an error indication (act <b>724</b>).

CONCLUSION

Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms for implementing the claims.

Although the above descriptions may contain specific details, they should not be construed as limiting the claims in any way. Other configurations of the described embodiments are part of the scope of this disclosure. Further, implementations consistent with the subject matter of this disclosure may have more or fewer acts than as described, or may implement acts in a different order than as shown. Accordingly, the appended claims and their legal equivalents should only define the invention, rather than any specific examples given.