Using time to determine a hash extension

• US 7,624,264 B2
• Filed: 06/22/2005
• Issued: 11/24/2009
• Est. Priority Date: 03/27/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aura, Tuomas, Roe, Michael
• Primary Examiner(s): Chai; Longbit
• Application Number:
  US11/165,412
• Publication Number:
  US 20060005014A1
• Time in Patent Office: 1,616 Days
• Field of Search: 713/162
• US Class Current: 713/162
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 9/006 involving public key infrastructure [PKI] trust models network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

An extensible cryptographically generated network address may be generated by forming at least a portion of the network address as a portion of a first hash value. The first hash value may be formed by generating a plurality of hash values by hashing a concatenation of a public key and a modifier using a second hash function until a stop condition. The stop condition may include computing the plurality of hash values for a period of time specified by a time parameter. A second hash value may be selected from the plurality of hash values, and the modifier used to compute that hash value may be stored. A hash indicator may be generated which indicates the selected second hash value. The first hash value may be generated as a hash of a concatenation of at least the public key and the modifier. At least a portion of the node-selectable portion of the network address may include at least a portion of the first hash value.

Claims

1. A method for generating a network address, the method comprising:

a) generating by a computing device an interim hash value based on a combination of at least one cryptographically generated address parameter and a public key, wherein a modifier is included in the at least one cryptographically generated address parameter;

b) modifying the modifier;

c) repeating the operations of generating and modifying until a stop condition, the stop condition including a time limit specified by a time parameter to generate a plurality of interim hash values;

d) terminating the computing when the stop condition is met, the stop condition further comprising a probability below a threshold probability that a more secure hash value will be generated within a remaining time of the time limit;

e) selecting by the computing device a second hash value from the plurality of interim hash values;

f) generating by the computing device a first hash value based on the second hash value; and

g) concatenating a portion of the network address that is not node-selectable and at least a portion of the first hash value to form the network address of the computing device.

2. The method of claim 1, wherein concatenating includes concatenating a hash indicator with the portion of the address that is not node selectable and the at least a portion of the first hash value.

3. The method of claim 2, wherein the hash indicator includes a count of zero bits in a selected portion of the second hash value.

4. The method of claim 2, wherein the hash indicator replaces a portion of the at least a portion of the first hash value.

5. The method of claim 1, wherein generating the first hash value includes generating the first hash value based on a combination of the at least one cryptographically generated address parameter, the portion of the network address that is not node-selectable, and the public key.

6. The method of claim 5, further comprising detecting a collision between the network address and an existing network address, and incrementing a collision count parameter of at least one cryptographically generated address parameter.

7. The method of claim 5, wherein generating the first hash value includes generating the first hash value based on a combination of the at least one cryptographically generated address parameter, the portion of the network address that is not node-selectable, the collision count parameter, and the public key.

8. The method of claim 1, wherein the stop condition includes comparing with a specified threshold a probability of generating another interim hash value that would be selected instead of one of the already generated ones within a specified period of time.

9. The method of claim 8, further comprising computing the stop condition on a logarithmic scale of probability, on a logarithmic scale of computation time, or in units of hash bits.

10. A method for a computing device to derive a node-selectable portion of a network address from a public key of the computing device, the method comprising:

a) computing by a computing device a plurality of hash values using a second hash function until a stop condition, the stop condition including computing the plurality of hash values for a time limit specified by a time parameter, an input for each hash value in the plurality of hash values including a concatenation of a public key and a modifier, wherein the modifier is included in at least one cryptographically generated address parameter and is modified during repeating of computing operations;

b) terminating the computing operation when the stop condition is met, the stop condition further comprising a probability below a threshold probability that a more secure hash value will be generated within a remaining time of the time limit;

c) selecting by the computing device a second hash value from the plurality of hash values;

d) generating by the computing device a hash indicator indicating the selected second hash value;

e) computing by the computing device a first hash value using a first hash function, the input to the first hash function including a concatenation of the public key and the modifier;

f) setting at least a portion of a node-selectable portion of a network address of the computing device to a portion of the first hash value.

11. The method of claim 10, wherein generating the hash indicator includes an indication of a number of zero bits in a portion of the second hash value.

12. The method of claim 11, further comprising encoding the hash indicator into at least a portion of the node-selectable portion of the network address.

13. The method of claim 10, wherein selecting the second hash value includes selecting a hash value in the plurality of hash values having the greatest number of zero bits in a predetermined portion of the hash value.

14. The method of claim 13, wherein selecting the second hash value includes comparing a second computed hash value of the plurality of hash values with a first computed hash value of the plurality of hash values, selecting a hash value from the first and the second computed hash values based on a number of zero bits in a predetermined portion of the hash value.

15. The method of claim 14, further comprising storing the modifier used to compute the selected hash value associated with a hash indicator indicating the number of zero bits.

16. The method of claim 14, wherein the stop condition includes comparing with a specified threshold a probability of generating another one of the plurality of hash values that would be selected instead of one of the already generated plurality of has values within a specified period of time.

17. The method of claim 16, further comprising computing the stop condition on a logarithmic scale of probability, on a logarithmic scale of computation time, or in units of hash bits.

18. One or more computer readable storage media having computer executable components being executed by a processor to generate a network address of a computing device, comprising:

a) means for generating a plurality of interim hash values using a second hash function until a stop condition, the stop condition including computing the plurality of interim hash values for a time limit specified by a time parameter, each interim hash value having an input including a concatenation of a public key and a modifier, wherein the modifier is included in at least one cryptographically generated address parameter and is modified during repeating of computing operations;

b) means for terminating the means for generating the plurality of interim hash values when the stop condition is met, the stop condition further comprising a probability below a threshold probability that a more secure hash value will be generated within a remaining time of the time limit;

c) means for selecting a second hash value from the plurality of interim hash values;

d) means for generating a hash indicator indicating the selected second hash value;

e) means for computing a first hash value, the input to the first hash function including a concatenation of the public key and the modifier; and

f) means for generating a network address of the computing device based on at least a portion of the first hash value.

19. The one or more computer readable media of claim 18, further comprising, means for resolving a collision between the generated network address and an existing network address.