Methods and systems for authenticating messages

• US 20040193875A1
• Filed: 03/27/2003
• Published: 09/30/2004
• Est. Priority Date: 03/27/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Aura, Anssi Tuomas
• Granted Patent: US 7,409,544 B2
• Time in Patent Office: Days
• 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:

concatenating a public key and a modifier;

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

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

determining a value for the modifier for use by the first hash function by executing a second hash function on the public key and an initial value for the modifier; and

repeating the execution of the second hash function while changing the value of the modifier until the second hash function yields a target result.

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 the target result of the second hash function is determined in part by a security parameter value.

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

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

7. A computer-readable medium containing instructions for performing a method for generating a cryptographic address, the method comprising:

concatenating a public key and a modifier;

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

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

determining a value for the modifier for use by the first hash function by executing a second hash function on the public key and an initial value for the modifier; and

repeating the execution of the second hash function while changing the value of the modifier until the second hash function yields a target result.

8. 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.

9. The method of claim 8, 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.

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

11. The method of claim 8, wherein the target result of the second hash function is determined in part by a security parameter value.

12. The method of claim 11, wherein the security parameter value is contained in selected bits of the network address.

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

14. A computer-readable 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.

15. 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;

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

16. The method of claim 15, 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.

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

“

u”

bit, “

g”

bit, and a routing prefix.

18. The method of claim 15, wherein the target result of the second hash value is determined in part by a security parameter value.

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

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

21. A computer-readable medium containing instructions for performing 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;

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

22. A computer-readable medium having stored thereon a data structure, the data structure comprising:

a first data field containing data representing a public key of a computing device;

a second data field containing data representing a modifier value; and

a third data field containing data representing a portion of a network of the computing device that is not node-selectable.

23. A computer-readable medium having stored thereon a data structure for a network address for a computing device, the data structure comprising:

a first data field representing a portion of the network address of the computing device that is not node-selectable;

a second data field representing a security parameter that defines the level of security provided by a cryptographic process employed to generate at least a part of the network address; and

a third data field representing a node-selectable portion of the network address.

24. The computer-readable medium of claim 23, the data structure further comprising:

a fourth data field representing a universal bit of the network address; and

a fifth data field representing a group bit of the network address.

25. A method for securing at least a portion of a message, the portion of the message comprising more and less rapidly changing data, the method comprising:

computing a first hash value using a first hash function, the input to the first hash function including the more rapidly changing data 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 the less rapidly changing data and the modifier; and

comparing at least a portion, of the second hash value with a target value and, if they do not match, then repeating the producing of the second hash value with a different value of the modifier.

26. The method of claim 25, wherein the less rapidly changing data are also input to the first hash function.

27. The method of claim 25 wherein the less rapidly changing data comprises an element selected from the group consisting of:

a portion of an address, a security parameter, and a public key.

28. The method of claim 25 wherein the more rapidly changing data are selected from the group consisting of:

a portion of an address and a timestamp.

29. The method of claim 25 wherein the target value is selected from the group consisting of:

an all-zero digital value, an all-one digital value, an address, a publicly known value, a value computed from the publicly known value, a value computed from the publicly known value and a previously sent message, and a value computed from the publicly known value and more than one previously sent message.

30. The method of claim 25 wherein the different value of the modifier is produced by incrementing a previous value of the modifier.

31. A computer-readable medium containing instructions for performing a method for securing at least a portion of a message, the portion of the message comprising more and less rapidly changing data, the method comprising:

computing a first hash value using a first hash function, the input to the first hash function including the more rapidly changing data 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 the less rapidly changing data and the modifier; and

comparing at least a portion of the second hash value with a target value and, if they do not match, then repeating the producing of the second hash value with a different value of the modifier.

32. A method for authenticating at least a portion of a message, the portion of the message comprising more and less rapidly changing data, the method comprising:

retrieving a modifier and a first hash value;

producing a second hash value by hashing the less rapidly changing data and the modifier;

producing a third hash value by hashing the more rapidly changing data and the modifier; and

if at least a portion of the second hash value matches a target value, and if at least a portion of the third hash value matches the first hash value, then accepting the portion of the message as authentic.

33. The method of claim 32, wherein producing the third hash value also includes hashing the less rapidly changing data.

34. A computer-readable medium containing instructions for performing a method for authenticating at least a portion of a message, the portion of the message comprising more and less rapidly changing data, the method comprising:

producing a second hash value by hashing the less rapidly changing data and the modifier;

producing a third hash value by hashing the more rapidly changing data and the modifier; and

if at least a portion of the second hash value matches a target value, and if at least a portion of the third hash value matches the first hash value, then accepting the portion of the message as authentic.

35. A method for creating a cryptographic hash value, the method comprising:

computing a first cryptographic hash value from a first message using a first cryptographic hash function, where the first cryptographic hash value is for authenticating the message; and

computing a second cryptographic hash value from a second message using a second cryptographic hash function, the second hash value belonging to a target subset of all possible hash values obtainable from the second cryptographic hash function, wherein the first message is at least in part derived from some portions of the second message.

36. The method of claim 35, wherein a size of the target subset of all possible hash values is expressed as some bits of the first hash value.

37. The method of claim 35, wherein the target subset of all possible hash values is determined by comparing a number of bits in the second hash value against a known value and a size of the target subset of all possible hash values is expressed as the number of bits to compare.

38. The method of claim 35, wherein the first and second hash functions are instantiations of the same cryptographic hash function.

39. A computer-readable medium containing instructions for performing a method for creating a cryptographic hash value, the method comprising:

computing a first cryptographic hash value from a first message using a first cryptographic hash function, where the first cryptographic hash value is for authenticating the message; and

computing a second cryptographic hash value from a second message using a second cryptographic,hash function, the second hash value belonging to a target subset of all possible hash values obtainable from the second cryptographic hash function, wherein the first message is at least in part derived from some portions of the second message.

40. A method for creating a cryptographic hash value, the method comprising:

computing a first hash value from a message using a first cryptogrpahic hash function;

modifying the message and re-computing the first hash value until the first hash value belongs to a target subset of all possible hash values, the modification made to the message being such that the original message can be recovered by undoing the modification;

computing a second hash value from the message using a second cryptographic hash function; and

making the message and the second hash value available for subsequent verification.

41. The method of claim 40, wherein the target subset of all possible hash values is determined by comparing a number of bits in the second hash value against a known value and a size of the target subset of all possible hash values is expressed as the number of bits to compare.

42. The method of claim 40, wherein the first and second hash functions are instantiations of the same cryptographic hash function with differing input.

43. The method of claim 40, wherein the modification made to the message is implemented by incrementing a numeric value in the message.

44. The method of claim 40, wherein the party creating the cryptographic hash value selects a size of the target subset of all possible hash values and encodes the size in the first hash value.

45. The method of claim 44, wherein the encoding is achieved by trial and error by selecting a suitable message when computing the first and second hash values.

46. The method of claim 44, wherein the encoding is achieved by changing the first hash value after computation.

47. A computer-readable medium containing instructions for performing a method for creating a cryptographic hash value, the method comprising:

computing a first hash value from a message using a first cryptogrpahic hash function;

modifying the message and re-computing the first hash value until the first hash value belongs to a target subset of all possible hash values, the modification made to the message being such that the original message can be recovered by undoing the modification;

computing a second hash value from the message using a second cryptographic hash function; and

making the message and the second hash value available for subsequent verification.

48. A method for verifying a cryptographic hash value, the method comprising:

obtaining a modified message and a first hash value;

computing a second hash value from the modified message using a first cryptographic hash function;

computing a third hash value from the modified message using a second cryptographic hash function;

verifying that the second hash value belongs to a target subset of all possible hash values;

verifying that the first hash value and at least a portion of the third hash value match; and

recovering an original message by undoing a modification done to the original message by a party that created the original message.

49. The method of claim 48, wherein the party verifying the cryptographic hash value decodes a size of the target subset of all possible hash values from bits of the first hash value.

50. The method of claim 48, wherein the target subset of all possible hash values is determined by comparing a number of bits in the second hash value against a known value and a size of the target subset of all possible hash values is expressed as the number of bits to compare.

51. The method of claim 48, wherein the first and second hash functions are instantiations of the same cryptographic hash function with differing input.

52. The method of claim 48, wherein the modification made to the message is undone by resetting a numeric value in the message to a known value.

53. A computer-readable medium containing instructions for performing a method for verifying a cryptographic hash value, the method comprising:

obtaining a modified message and a first hash value;

computing a second hash value from the modified message using a first cryptographic hash function;

computing a third hash value from the modified message using a second cryptographic hash function;

verifying that the second hash value belongs to a target subset of all possible hash values;

verifying that the first hash value and at least a portion of the third hash value match; and

recovering an original message by undoing a modification done to the original message by a party that created the original message.