US 7,600,255 B1Granted

Preventing network denial of service attacks using an accumulated proof-of-work approach

AssigneeCisco Technology, Inc.

InventorMark Baugher

Life of this patent

Estimating the term…

Loading patent…

Abstract

Accumulated proof-of-work approaches for protecting network resources against denial-of-service attacks are disclosed. A client computer or other requester is required to perform work, such as repeatedly hashing a message until a specified number of bits is zero, as a condition for accessing a resource. Proof of the work performed by a legitimate requester is accumulated across multiple requests, so that established users of a resource are not penalized when proof-of-work is used to prevent a denial of service attack. Requesters who cannot show accumulated work greater than a specified threshold are required to perform additional work. In certain embodiments, work may be accumulated only within a specified time window, and the threshold may vary according to resource capacity or loading. Proof-of-work values may be communicated between the user and the resource in cookies.

Claims28

Dependent claims

A method of preventing an attack on a network, the method comprising the computer-implemented steps of:

receiving a request to access a resource from a user, wherein the request includes an accumulated work value;
wherein the accumulated work value represents a total amount of work previously performed by the user and accumulated across multiple prior requests by the user;
receiving a prior keyless user identity value H(i+1,x) in the request comprising a one-time password, wherein H(i+1,x) is computed by the user as a hash chain from a non-shared user secret (x), wherein H(n,x)=h(H(n−1,x)), wherein n>0 and H(0,x)=x, wherein function h is a one-way function that is difficult to invert;
receiving a current user identity value H(i,x);
verifying that the keyless user identity value properly identifies the user only upon determining that h(H(i,x))==H(i+,x);
wherein h comprises a SHA-1 hash algorithm;
wherein n is between 10^4 and 10^6;
determining whether the accumulated work value exceeds a required work threshold value, and if not, requiring the user to perform a quantity of work as a condition for accessing the resource;
providing the user with access to the resource;
determining an amount of accumulated work output value to provide to the user based on a volume of data communicated between the resource and the user;
and
wherein the accumulated work output value represents a second amount of work performed by the user;
providing the accumulated work output value to the user.

10 more elements

An apparatus, comprising

one or more processors;
means for receiving a request to access a resource from a user, wherein the request includes an accumulated work value;
wherein the accumulated work value represents a total amount of work previously performed by the user and accumulated across multiple prior requests by the user;
means for receiving a prior keyless user identity value H(i+1,x) in the request comprising a one-time password, wherein H(i+1,x) is computed by the user as a hash chain from a non-shared user secret (x), wherein H(n,x)=h(H(n−1,x)), wherein n>0 and H(0,x)=x, wherein function h is a one-way function that is difficult to invert;
means for receiving a current user identity value H(i,x);
means for verifying that the keyless user identity value properly identifies the user only upon determining that h(H(i,x))==H(i+1,x);
wherein h comprises a SHA-1 hash algorithm;
wherein n is between 10^4 and 10^6;
means for determining whether the accumulated work value exceeds a required work threshold value, and if not, requiring the user to perform a quantity of work as a condition for accessing the resource;
means for providing the user with access to the resource;
means for determining an amount of accumulated work output value to provide to the user based on a volume of data communicated between the resource and the user;
and
wherein the accumulated work output value represents a second amount of work performed by the user;
means for providing the accumulated work output value to the user.

11 more elements

An apparatus, comprising:

a processor;
a computer-readable volatile or non-volatile medium storing one or more stored sequences of instructions that are accessible to the processor, wherein execution of the one or more stored sequences of instructions by the processor causes the processor to perform:
receiving a request to access a resource from a user, wherein the request includes an accumulated work value;
wherein the accumulated work value represents a total amount of work previously performed by the user and accumulated across multiple prior requests by the user;
receiving a prior keyless user identity value H(i+1,x) in the request comprising a one-time password, wherein H(i+1,x) is computed by the user as a hash chain from a non-shared user secret (x), wherein H(n,x)=h(H(n−1,x)), wherein n>0 and H(0,x)=x, wherein function h is a one-way function that is difficult to invert;
receiving a current user identity value H(i,x);
verifying that the keyless user identity value properly identifies the user only upon determining that h(H(i,x))==H(i+1,x);
wherein h comprises a SHA-1 hash algorithm;
wherein n is between 10^4 and 10^6;
determining whether the accumulated work value exceeds a required work threshold value, and if not, requiring the user to perform a quantity of work as a condition for accessing the resource;
providing the user with access to the resource;
determining an amount of accumulated work output value to provide to the user based on a volume of data communicated between the resource and the user;
and
wherein the accumulated work output value represents a second amount of work performed by the user;
providing the accumulated work output value to the user.

12 more elements

A computer-readable volatile or non-volatile medium storing one or more sequences of instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform:

receiving a request to access a resource from a user, wherein the request includes an accumulated work value;
wherein the accumulated work value represents a total amount of work previously performed by the user and accumulated across multiple prior requests by the user;
receiving a prior keyless user identity value H(i+1,x) in the request comprising a one-time password, wherein H(i+1,x) is computed by the user as a hash chain from a non-shared user secret (x), wherein H(n,x)=h(H(n−1,x)), wherein n>0 and H(0,x)=x, wherein function h is a one-way function that is difficult to invert;
receiving a current user identity value H(i,x);
verifying that the keyless user identity value properly identifies the user only upon determining that h(H(i,x))==H(i+1,x);
wherein h comprises a SHA-1 hash algorithm;
wherein n is between 10^4 and 10^6;
determining whether the accumulated work value exceeds a required work threshold value, and if not, requiring the user to perform a quantity of work as a condition for accessing the resource;
providing the user with access to the resource;
determining an amount of accumulated work output value to provide to the user based on a volume of data communicated between the resource and the user;
and
wherein the accumulated work output value represents a second amount of work performed by the user;
providing the accumulated work output value to the user.

10 more elements

Dependencies are inferred from the claim text.