Methods and systems for authenticating messages

• US 7,409,544 B2
• Filed: 03/27/2003
• Issued: 08/05/2008
• Est. Priority Date: 03/27/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aura, Anssi Tuomas
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): Sandoval; Kristin D
• Application Number:
  US10/401,241
• Publication Number:
  US 20040193875A1
• Time in Patent Office: 1,958 Days
• Field of Search: 713/162
• US Class Current: 713/162
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• 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 9/3236 using cryptographic hash functions

Abstract

Disclosed is an authentication mechanism that provides much of the security of heavyweight authentication mechanisms, but with lower administrative and communicative overhead while at the same time not being limited to a 64-bit limit on the length of a cryptographic hash value. Removal of this limitation is achieved by increasing the cost of both address generation and brute-force attacks by the same parameterized factor while keeping the cost of address use and verification constant. The address owner computes two hash values using its public key and other parameters. The first hash value is used by the owner to derive its network address. The purpose of the second hash is to artificially increase that computational complexity of generating new addresses and, consequently, the cost of brute-force attacks. As another measure against brute-force attacks, the routing prefix (i.e., the non-node selectable portion) of the address is included in the first hash input.

Claims

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

setting an initial value for a modifier;

determining the value of the modifier for use by a first hash function by executing a second hash function on a public key and the modifier, repeating the execution of the second hash function while changing the value of the modifier until the second hash function yields a target result, wherein the target result of the second hash function is determined in part by a security parameter value;

concatenating a public key and the modifier;

executing the first hash function on the concatenated public key and the modifier to yield a first hash function value; and

concatenating a portion of an address that is not node-selectable and at least a portion of the first hash function value to create a network address.

2. The method of claim 1, wherein the portion of the network address that is not node-selectable is also concatenated with the public key and modifier as input to the first hash function.

3. The method of claim 1, wherein the public key and the modifier values are formatted as parts of a self-signed certificate.

4. The method of claim 1, wherein a portion of the network address comprises the security parameter value.

5. The method of claim 1, wherein the security parameter value is selected by a first computing device.

6. A computer storage medium containing instructions for performing a method for generating a cryptographic address, the method comprising:

setting an initial value for a modifier;

determining the value of the modifier for use by a first hash function by executing a second hash function on a public key and the modifier, repeating the execution of the second hash function while changing the value of the modifier until the second hash function yields a target result, wherein the target result of the second hash function is determined in part by a security parameter value;

concatenating a public key and the modifier;

executing the first hash function on the concatenated public key and the modifier to yield a first hash function value; and

concatenating a portion of an address that is not node-selectable and at least a portion of the first hash function value to create a network address.

7. A method for a second computing device to authenticate content data made available by a first computing device, the method comprising:

accessing authentication information made available by the first computing device, the authentication information including content data, a network address of the first computing device, a public key of the first computing device, and a modifier;

computing 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;

computing a second hash value using a second hash function, the input to the second hash function including a concatenation of the public key and the modifier; and

accepting the content data if the second hash value matches a target result, and the first hash value matches a second corresponding portion of the network address, wherein the target result of the second hash function is determined in part by a security parameter value.

8. The method of claim 7, wherein the portion of the network address that is not node-selectable is also concatenated with the public key and modifier as input to the first hash function.

9. The method of claim 7, wherein the public key and the modifier values are formatted as parts of a self-signed certificate.

10. The method of claim 7, wherein the security parameter value is selected by the first computing device.

11. The method of claim 7, wherein a portion of the network address comprises the security parameter value.

12. A computer storage medium containing instructions for performing a method for a second computing device to authenticate content data made available by a first computing device, the method comprising:

accessing authentication information made available by the first computing device, the authentication information including content data, a network address of the first computing device, a public key of the first computing device and a modifier;

computing 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;

computing a second hash value using a second hash function, the input to the second hash function including a concatenation of the public key and the modifier; and

accepting the content data if the second hash value matches a target result, and the first hash value matches a second corresponding portion of the network address, wherein the target result of the second hash function is determined in part by a security parameter value.

13. 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:

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

computing a second hash value using the second hash function, the input to the second hash function including a concatenation of the public key and the modifier;

comparing a portion of the second hash value with a target result, wherein the target result of the second hash value is determined in part by a security parameter value;

if the portion does not match the target result, modifying the value of the modifier, concatenating the modifier with the public key, and repeating the computing of a second hash function and the comparing;

setting the node-selectable portion of the network address to a portion of the first hash value; and

checking to see if the network address as set is already in use and if the network address as set is already in use, repeating the computing of the first hash value, the setting of the node-selectable portion of the network address, and the checking to see if the network address is already in use.

14. The method of claim 13, wherein a portion of the network address that is not node-selectable is also concatenated with the public key and modifier as input to the first hash function.

15. The method of claim 14, wherein a portion of the network address other than the node-selectable portion comprises an element selected from the group consisting of:

a Universal bit, a Group bit, and a routing prefix.

16. The method of claim 13, wherein a portion of the network address comprises the security parameter value.

17. The method of claim 13, wherein the security parameter value is selected by the computing device.

18. A computer storage medium containing instructions for performing a method for a computing device to derive a node-selectable portion of a network address from la public key of the computing device, the method comprising:

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

computing a second hash value using the second hash function, the input to the second hash function including a concatenation of the public key and the modifier;

comparing a portion of the second hash value with a target result, wherein the target result of the second hash value is determined in part by a security parameter value;

if the portion does not match the target result, modifying the value of the modifier, concatenating the modifier with the public key, and repeating the computing of a second hash function and the comparing;

setting the node-selectable portion of the network address to a portion of the first hash value; and

checking to see if the network address as set is already in use and if the network address as set is already in use, repeating the computing of the first hash value, the setting of the node-selectable portion of the network address, and the checking to see if the network address is already in use.