Method and system for distributed generation of unique random numbers for digital tokens

• US 6,948,074 B1
• Filed: 03/09/2000
• Issued: 09/20/2005
• Est. Priority Date: 03/09/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Grabelsky, David, Borella, Michael S.
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): TRAN, ELLEN C
• Application Number:
  US09/521,788
• Time in Patent Office: 2,021 Days
• Field of Search: 713/153, 713/201, 713/168, 709/223, 709/228
• US Class Current: 726/14
• CPC Class Codes: H04L 61/2525 Translation at a client
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/1458 Denial of Service
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

A method and system for distributed generation of unique random numbers. The unique random number can be used to create digital cookies or digital tokens. A first network device (e.g., a computer) on a computer network receives an x-bit bit mask template from a second network device on the computer network (e.g., a gateway). The first network device generates a first portion of an x-bit digital cookie. The first network device requests a second portion of the x-bit digital cookie from the second network device. The request includes the first portion of the x-bit digital cookie. The first network device generates a complete x-bit digital cookie using the first portion of the x-bit digital cookie generated by the first network device and the second portion of the x-bit digital cookie generated by the second network device. The generated complete x-bit digital cookie is not in use on the computer network because the second network device has selected the second portion of the bit mask so the complete x-bit digital cookie including the first portion generated on the first network device and the second portion generated on the second network device is not use on the computer network. The method and system can be used on a Distributed Network Address Translation (“DNAT”) or a Realm Specific Internet Protocol (“RSIP”) subnet to allow a network device (e.g., a computer) to create a complete x-bit digital cookie with help from a DNAT/RSIP gateway. The complete x-bit digital cookie can be used as a 64-bit anti-clogging cookie for security protocols such as Internet Key Exchange (“IKE”) protocol exchanges used with Internet Protocol security (“IPsec”).

Claims

1. In a computer network with a plurality of network devices, a method for distributed generation of unique random numbers for digital cookies, comprising the steps of:

generating a first portion of a x-bit digital cookie on a first network device on the computer network based on an x-bit bit mask template sent to the first network device from a second network device on the computer network;

sending a first message to request a second portion of the x-bit digital cookie from the second network device, wherein the first message includes the first portion of the x-bit digital cookie;

receiving a first response from the second network device wherein the first response includes a second portion of the x-bit digital cookie from the second network device, and wherein the second network device generates potential x-bit digital cookies using the first portion of the x-bit digital cookie from the first network device and a second portion of the x-bit digital cookie generated on the second network device until the second network device generates a potential x-bit digital cookie that is not in use on the computer network;

generating a complete x-bit digital cookie on the first network device using the first portion of the x-bit digital cookie and the second portion of the x-bit digital cookie, wherein the complete x-bit digital cookie is not in use on the computer network.

2. A computer readable medium having stored therein instructions for causing a central processing unit to execute the method of claim 1.

3. The method of claim 1 further comprising:

sending the complete x-bit digital cookie in a plurality of messages used to a establish a secure connection between the first network device on the computer network and third network device on a remote computer network.

4. The method of claim 3, wherein the plurality of messages include a plurality of Internet Key Exchange protocol messages.

5. The method of claim 1 wherein the step of generating a first portion of an

x-bit digital cookie includes generating a n-bit random number, wherein the number-n is determined by counting n-number of bits set to a value of one in the x-bit bit mask sent to the first network device by the second network device.

6. The method of claim 1 wherein the second portion of the bit mask is an (x-n) bit random number generated on the second network device, wherein n is less than or equal to x.

7. The method of claim 1 wherein the x-bit bit mask template is a 64-bit, bit mask template.

8. The method of claim 1 wherein the step of generating a complete x-bit digital cookie on the first network device includes generating a complete x-bit digital cookie on the first network device by placing values of bits from the first portion of the x-bit digital cookie in bit positions with a value of one using the x-bit bit mask template, and by placing values of bits from the second portion of the x-bit digital cookie in bit positions with a value of zero using the x-bit bit mask template.

9. The method of claim 1 wherein the second network device is any of a Distributed Network Address Translation gateway or a Realm Specific Internet Protocol gateway.

10. In a computer network with a plurality of network devices, a method for distributed generation of unique random numbers for digital cookies, comprising the steps of:

maintaining a list of complete digital cookies in use on the computer network on a second network device;

generating a x-bit bit mask template on a second network device, wherein the x-bit bit mask has n-bits randomly set to a value of one and remaining (x-n) bits randomly set to value of zero wherein n is less than or equal to x;

sending the x-bit bit mask template to a first network device on the computer network;

receiving a request from the first network device to request a second portion of a x-bit digital cookie from the second network device, wherein the first message includes an first portion of the x-bit digital cookie;

(a) generating a second portion of a x-bit digital cookie on the second network device;

(b) generating a potential x-bit digital cookie on the second network device using the first portion of the x-bit digital cookie generated on the first network device and the second portion of the x-bit digital cookie generated on the second network device;

(c) comparing the potential x-bit digital cookie with complete digital cookies from the list of complete digital cookies maintained on the second network device that are in use on the computer network;

repeating steps (a), (b) and (c) until a potential x-bit digital cookie is generated that is not in use on the computer network; and

sending the second portion of the x-bit digital cookie for the potential x-bit digital cookie that is not in use on the computer network to the first network device, wherein the first network device uses the first portion of the x-bit digital cookie and the second portion of the x-bit digital cookie to create a complete x-bit digital cookie that is not in use on the computer network.

11. A computer readable medium having stored therein instructions for causing a central processing unit to execute the method of claim 10.

12. The method of claim 10 wherein the first portion of the x-bit digital cookie includes an n-bit random number, wherein the n-bits were determined by counting a number of bits set to the value of one in the x-bit bit-mask sent to the first network device and generating an n-bit random number on the first network device.

13. The method of claim 10 wherein step (a) includes generating a (x-n) bit random number on the second network device, wherein the first portion of the x-bit digital cookie from the first network device includes n-bits.

14. The method of claim 10 wherein step (b) includes placing values of bits from a n-bit first portion of the x-bit digital cookie generated on the first network device in bit positions with a value of one in the x-bit bit mask, and placing values of bits from a (x-n) bit second portion of the x-bit digital cookie generating on the second network device in bit positions with a value of zero in the x-bit bit mask.

15. The method of claim 10 wherein the x-bit bit mask template is a 64-bit, bit mask template.

16. The method of claim 10 wherein the second network device is any of a Distributed Network Address Translation gateway or a Realm Specific Internet Protocol gateway.

17. In a computer network with a plurality of network devices, a method for distributed generation of unique random numbers for digital cookies, comprising the steps of:

sending a first request from a first network device to a second network device for an x-bit bit mask template;

receiving a first response on the first network device from the second network device including a x-bit bit mask template, wherein the x-bit bit mask template has n-bits randomly set to a value of one and remaining (x-n) bits randomly set to a value of zero, wherein n is less than or equal to x;

counting n-number of ones in the x-bit bit mask template on the first network device;

generating an n-bit random number on the first network device based on the n-number of ones counted in the x-bit bit mask;

sending a second request to the second network device including the n-bit random number for a (x-n) bit random number;

receiving a second response from the second network device including a (x-n) bit random number; and

creating a complete digital cookie using the (x-n) bit random number, the x-bit random number and the x-bit bit mask, wherein the complete digital cookie is not in use on the computer network.

18. A computer readable medium having stored therein instructions for causing a central processing unit to execute the method of claim 17.

19. The method of claim 17 wherein the x-bit bit mask template is a 64-bit bit mask template.

20. The method of claim 17 wherein the second network device is any of a Distributed Network Address Translation gateway or a Realm Specific Internet Protocol gateway.

21. The method of claim 17 further comprising:

sending the complete x-bit digital cookie in a plurality of messages used to a establish a secure connection between the first network device on the computer network and third network device on a remote computer network.

22. The method of claim 21 wherein the plurality of messages include a plurality of Internet Key Exchange protocol messages.

23. In a computer network with a plurality of network devices, a method for distributed generation of unique random numbers for digital cookies, comprising the steps of:

maintaining a list of complete digital cookies in use on the computer network on a second network device;

generating a x-bit bit mask template on a second network device, wherein the x-bit bit mask has n-bits randomly set to a value of one and remaining (x-n) bits randomly set to value of zero, wherein n is less than or equal to x;

sending the x-bit bit mask template to a first network device on the computer network;

receiving a request from the first network device to request an (x-n) bit random number for an x-bit digital cookie from the second network device, wherein the first message includes an n-bit random number;

(a) generating a (x-n) bit random number on the second network device;

(b) generating a potential x-bit digital cookie on the second network device using the n-bit random number generated on the first network device and the (x-n) bit random generated on the second network device, wherein the potential x-bit digital cookie is generated by placing values of bits from the n-bit random number generated on the first network device in bit positions with a value of one in the x-bit bit mask, and placing values of bits from a (x-n) bit random number generating on the second network device in bit positions with a value of zero in the x-bit bit mask;

(c) comparing the potential x-bit digital cookie with complete digital cookies from the list of complete digital cookies maintained on the first network device that are in use on the computer network;

repeating steps (a), (b) and (c) until a potential x-bit digital cookie is generated that is not in use on the computer network;

sending the (x-n) bit random number used to generate the potential x-bit digital cookie that is not in use on the computer network to the first network device, wherein the first network device uses the n-bit random number and the (x-n) bit random number to create a complete x-bit digital cookie that is not in use on the computer network.

24. A computer readable medium having stored therein instructions for causing a central processing unit to execute the method of claim 23.

25. The method of claim 23 wherein the x-bit bit mask template is a 64-bit, bit mask template.

26. The method of claim 23 wherein the second network device is any of a Distributed Network Address Translation gateway or a Realm Specific Internet Protocol gateway.

27. The method of claim 23 further comprising generating a complete x-bit digital cookie on the first network device using the n-bit random number, the (x-n) bit random number and the x-bit bit mask template.