Cryptographic countermeasures against connection depletion attacks

• US 7,197,639 B1
• Filed: 02/02/2000
• Issued: 03/27/2007
• Est. Priority Date: 02/05/1999
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: RSA Security Incorporated (Symphony Technology Group LLC)
• Inventors: Juels, Ari, Brainard, John
• Primary Examiner(s): ZIA, SYED
• Application Number:
  US09/496,824
• Time in Patent Office: 2,610 Days
• Field of Search: 713/201
• US Class Current: 713/168
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/1458 Denial of Service
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3271 using challenge-response
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps

Abstract

This invention relates to cryptographic communications methods and systems that protect a server from a connection depletion attack. Specifically, the invention presents a method for allocating a resource comprising the steps of receiving a resource allocation request from a client, imposing a computational task and a time limit for correct completion of the task upon the client, verifying that the task was performed correctly within the time limit, and allocating the resource if the task was correctly performed within the time limit.

Claims

1. A method for allocating a resource, comprising the steps of:

(a) receiving a resource allocation request from a client;

(b) imposing on said client a computational task and a time limit for correct completion of said computational task;

(c) receiving verification that said client has correctly performed said computational task within said time limit; and

(d) allocating said resource for said client if the verification is received;

wherein said step (b) comprises communicating a puzzle as at least a portion of said communication task.

2. The method of claim 1 wherein said resource allocation request comprises a network connection request.

3. The method of claim 1 wherein said step (b) comprises communicating the output of a one-way function to said client.

4. The method of claim 1 wherein said step (b) comprises communicating the output of a block cipher to said client.

5. The method of claim 1 wherein said step (b) comprises communicating the output of a function, wherein the input of said function is generated, based at least in part on a server secret unknown to said client, and not revealed through correct performance of said computational task.

6. The method of claim 1 wherein said step (b) comprises communicating the output of a function, wherein the input of said function comprises a timestamp and information authenticating the timestamp.

7. The method of claim 1 wherein said step (b) comprises communicating a puzzle constructed in a self authenticating fashion.

8. The method of claim 1 wherein said step (b) comprises communicating a hash image and a partially revealed pre-image to said client.

9. The method of claim 8 wherein said step (c) comprises receiving the remaining pre-image.

10. The method of claim 1 wherein said step (b) comprises communicating a plurality of sub-puzzles to a client.

11. The method of claim 10 wherein said step (b) comprises communicating a plurality of independently constructed sub-puzzles.

12. The method of claim 10 wherein said step (b) comprises communicating a plurality of sub-puzzles wherein each sub-puzzle is constructed with an overlap of at least a portion of information that is common to two or more of the plurality of sub-puzzles.

13. The method of claim 1 wherein said step (a) comprises receiving a TCP SYN request.

14. The method of claim 1 wherein said step (a) comprises receiving a request to open an SSL connection.

15. The method of claim 1 wherein said step (b) comprises the steps of:

(ba) determining if a computational task is to be imposed upon said client based upon the operating circumstances at the time of receiving said resource allocation request from said client; and

(bb) if a computational task is determined to be imposed upon said client then selecting a computational task responsive to at least one characteristic of said operating circumstances at the time of receiving said resource allocation request; and

(bc) if a computational task is determined to be imposed upon said client then imposing the selected computational task on said client.

16. The method of claim 1, wherein said step (a) comprises receiving a resource allocation request comprising a query, or accompanied or preceded by a query concerning whether a server is currently imposing computational tasks.

17. A method for procuring a resource comprising the steps of:

(a) communicating a resource allocation request to a server;

(b) receiving a computational task from said server;

(c) performing or delegating the performance of said computational task correctly within a known time limit; and

(d) communicating to said server a verification that said computational task has been performed correctly within the known time limit;

wherein said step (b) comprises receiving said computational task and a time limit for performance of said computational task from said server.

18. The method of claim 17 wherein said resource allocation request comprises a network connection request.

19. The method of claim 17 wherein said step (c) comprises solving a puzzle.

20. The method of claim 19 wherein said step (c) comprises a linear search of the solution space associated with said computational task.

21. The method of claim 17 wherein said step (c) comprises solving a plurality of sub-puzzles.

22. The method of claim 17 wherein said step (a) comprises transmitting a TCP SYN request.

23. The method of claim 17 wherein said step (a) comprises transmitting a request to open an SSL connection.

24. The method of claim 17 wherein said step (a) comprises transmitting a resource allocation request comprising a query, or accompanied or preceded by a query concerning whether a server is currently imposing computational tasks.

25. An apparatus for allocating a resource comprising:

a first receiver receiving a resource allocation request from a client;

a computational task generator for imposing a computational task upon said client for correct performance within a time limit; and

a transmitter communicating said computational task to said client;

a second receiver receiving a verification from said client that said computational task was correctly performed with said time limit; and

an allocator allocating said resource for said client;

wherein said computational task comprises a puzzle.

26. The apparatus of claim 25 wherein said first receiver and said second receiver comprise the same receiver.

27. The apparatus of claim 25 wherein said first receiver receives a resource allocation request comprising a network connection request.

28. The apparatus of claim 25 wherein said transmitter communicates said computational task and a time limit for performance of said computational task to said client.

29. The apparatus of claim 25 wherein said puzzle comprises the output of a one-way function.

30. The apparatus of claim 25 wherein said puzzle comprises the output of a block cipher.

31. The apparatus of claim 25 wherein said puzzle comprises the output of a function, wherein the input of said function is based at least in part on a server secret unknown to said client and not revealed through correct performance of said computational task.

32. The apparatus of claim 25 wherein said puzzle comprises the output of a function, wherein the input of said function comprises a timestamp and information authenticating the timestamp.

33. The apparatus of claim 25 wherein said puzzle is constructed in a self authenticating fashion.

34. The apparatus of claim 25 wherein said puzzle comprises a hash image, and a partially revealed pre-image.

35. The apparatus of claim 34 wherein said verification comprises verifying the remaining unrevealed pre-image.

36. The apparatus of claim 25 wherein said puzzle comprises a plurality of sub-puzzles.

37. The apparatus of claim 36 wherein said plurality of sub-puzzles are constructed independently.

38. The apparatus of claim 36 wherein said plurality of sub-puzzles are constructed with an overlap of at least a portion of information that is common to two or more of the plurality of sub-puzzles.

39. The apparatus of claim 25 wherein said resource allocation request comprises a TCP SYN request.

40. The apparatus of claim 25 wherein said resource allocation request comprises a request to open an SSL connection.

41. The apparatus of claim 25 wherein said computational task is selected responsive to at least one characteristic of the operating circumstances at the time of receiving said resource allocation request.

42. The apparatus of claim 25 wherein said resource allocation request comprises a query, or is accompanied or preceded by a query concerning whether a server is currently imposing computational tasks.

43. The apparatus of claim 25 comprising a time limit generator generating a time limit within which said client must correctly perform said computational task.

44. An apparatus for procuring a resource comprising:

a first transmitter communicating a resource allocation request to a server;

a first receiver receiving a computational task from said server;

a computational task solver correctly performing said computational task within a known time limit; and

a second transmitter communicating to said server a verification that said computational task has been performed;

further comprising a second receiver receiving a time limit for performing said computational task.

45. The apparatus of claim 44 wherein said first transmitter and said second transmitter comprise the same transmitter.

46. The method of claim 44 wherein said first transmitter sends a resource allocation request comprising a network connection request.

47. The apparatus of claim 44 wherein said first receiver and said second receiver comprise the same receiver.

48. The apparatus of claim 44 wherein said computational task comprises a puzzle.

49. The apparatus of claim 44 wherein said computational task performs a linear search of potentially the entire solution space associated with said computational task.

50. The apparatus of claim 44 wherein said computational task comprises a plurality of sub-puzzles.

51. The apparatus of claim 50 wherein said sub-puzzles are constructed independently.

52. The apparatus of claim 50 wherein said sub-puzzles are constructed with an overlap of at least a portion of information that is common to two or more of the plurality of sub-puzzles.

53. The apparatus of claim 44 wherein said resource allocation request comprises a TCP SYN request.

54. The apparatus of claim 44 wherein said resource allocation request comprises a request to open an SSL connection.

55. The apparatus of claim 44 wherein said resource allocation request comprises a query, or is accompanied or preceded by a query concerning whether said server is currently imposing computational tasks.