Hashing using multiple sub-hashes

• US 7,248,691 B1
• Filed: 10/31/2000
• Issued: 07/24/2007
• Est. Priority Date: 10/31/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Reichel, Robert P., Pandit, Bhalchandra S., Dubhashi, Kedarnath A., Hamblin, Jeffrey B.
• Primary Examiner(s): Vu; Kim
• Assistant Examiner(s): Dada; Beemnet W
• Application Number:
  US09/704,186
• Time in Patent Office: 2,457 Days
• Field of Search: 713/200, 713/201, 713/164, 713/165, 713/167, 713/168, 713/180, 380/28, 380/277, 380/278, 380/44, 380/273, 380/47, 380/286, 707 3- 6, 707/103.Y, 707/103.X, 707/103.Z
• US Class Current: 380/28
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3234 involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A hashing structure including multiple sub-hashes is used to determine whether an input value matches one or more of multiple target values. These values can be of any form, such as security identifiers in an access control system. To make the determination, a hash key is obtained from the input value and multiple sub-hash indexes (one for each of the multiple sub-hashes) are generated based on the key. Values are identified from the multiple sub-hashes by indexing into the sub-hashes using respective ones of the sub-hash indexes. These values are then combined to generate a resultant hash value. Each of the multiple target values corresponds to one of multiple portions of the resultant hash value. If the portion corresponding to one of the target values has a particular value, then that target value is a likely match and is compared to the input value to determine if indeed the two match. This comparison can then be repeated for each target value with a corresponding portion in the resultant hash value that has the particular value.

Claims

1. One or more computer readable storage media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform a method including:

generating a hash key based on an input value;

separating the hash key into a plurality of portions;

indexing into each of a plurality of sub-hashes using one of the plurality of portions, each location in each of the plurality of sub-hashes containing a multiple-bit value, each bit corresponding to one of a plurality of target values;

identifying a plurality of values from the plurality of sub-hashes based on the indexing;

combining the plurality of values to generate a hash result, wherein each bit in the hash result corresponds to one of the plurality of target values;

for each bit in the hash result that is set, comparing the input value to the corresponding target value; and

allowing access based on whether the values match.

2. One or more computer readable media as recited in claim 1, wherein the number of target values in the plurality of target values is equal to the number of bits in the hash result.

3. One or more computer readable media as recited in claim 1, wherein a maximum number of target values in the plurality of target values is equal to the number of bits in the result value.

4. One or more computer readable media as recited in claim 1, wherein a maximum number of target values in the plurality of target values is equal to the number of bits in each of a plurality of locations of the plurality of sub-hashes that can be indexed.

5. One or more computer readable media as recited in claim 1, wherein the separating comprises separating the hash key into two portions.

6. One or more computer readable media as recited in claim 1, wherein the separating comprises separating the hash key into a plurality of contiguous and equal portions.

7. One or more computer readable media as recited in claim 1, wherein the combining comprises performing a bitwise logical ANDing of the plurality of values.

8. A hashing architecture implemented in hardware for determining whether to allow access to an access controlled object, comprising:

a plurality of sub-hashes;

a plurality of sub-hash indexes, each index being generated from a hash key and used to index into one of the plurality of sub-hashes, each location in each of the plurality of sub-hashes containing a multiple-bit value, each bit corresponding to one of a plurality of target values; and

a combiner coupled to receive values from the plurality of sub-hashes based on the plurality of sub-hash indexes, and to generate a hash result by combining the received values; and

a comparator coupled to receive the hash result and to

determine which of the plurality of target values to compare to an input value;

compare the input value to at least one of the plurality of target values; and

allowing access based on the comparison.

9. A hashing architecture as recited in claim 8, wherein the combiner comprises a combinatorial logic component to perform a bitwise logical ANDing of the values received from the plurality of sub-hashes.

10. A hashing architecture as recited in claim 8, wherein the hashing architecture is implemented in a computing device.

11. A hashing architecture as recited in claim 8, wherein the plurality of sub-hash indexes are generated by separating the hash key into a plurality of equal portions.

12. A method, comprising:

generating a plurality of sub-hash keys based on a hash key, the hash key being based on an input value;

identifying a plurality of values from a plurality of sub-hashes by indexing into each of the plurality of sub-hashes using one of the plurality of sub-hash keys, each location in each of the plurality of sub-hashes containing a multiple-bit value, each bit corresponding to one of an plurality of target values;

generating a hash result based on the plurality of values;

determining based on the hash result which of the plurality of target values to compare to the input value;

comparing the input value to at least one of the plurality of target values; and

allowing access based on the comparison.

13. A method as recited in claim 12, further comprising generating the hash key prior to generating the plurality of sub-hash keys.

14. A method as recited in claim 12, wherein the generating the plurality of sub-hash keys comprises separating the hash key into a plurality of equal portions.

15. A method as recited in claim 12, wherein the generating the hash result comprises performing a bit-by-bit logical ANDing of the plurality of values.

16. One or more computer readable media storing a computer program that is executable by a processor to perform the method recited in claim 12.

17. One or more computer readable storage media having stored thereon a plurality of instructions that, when executed by one or more processors, cause the one or more processors to perform a method including:

generating a hash key based on an access control element security identifier;

separating the hash key into a first portion and a second portion;

indexing into a first sub-hash using the first portion to identify a first sub-hash value;

indexing into a second sub-hash using the second portion to identify a second sub-hash value;

combining the first sub-hash value and the second sub-hash value to generate a result value, wherein each bit in the result value corresponds to one of a plurality of security token security identifiers; and

for each bit in the result value that is set,

comparing the access control element security identifier to the corresponding security token security identifier; and

allowing access based on whether the access control security identifier matches the corresponding security token identifier.

18. One or more computer readable media as recited in claim 17, wherein the generating comprises generating the hash key by selecting a portion of the access control element security identifier.

19. One or more computer readable media as recited in claim 17, wherein the separating comprises separating the hash key into two portions that include an equal number of bits and that are contiguous.

20. One or more computer readable media as recited in claim 17, wherein the combining comprises bitwise ANDing together the first sub-hash value and the second sub-hash value.

21. A method, comprising:

generating a plurality of sub-hash indexes based on a hash key, the hash key being based on an input security identifier;

indexing into each of a plurality of sub-hashes using a respective one of a plurality of sub-hash indexes, each location in each of the plurality of sub-hashes containing a multiple-bit value, each bit corresponding to one of a plurality of target security identifiers;

generating a result hash value by combining a plurality of values resulting from indexing into the plurality of sub-hashes, wherein each of the plurality of target security identifiers corresponds to a portion of the result hash value;

comparing the input security identifier to at least one of the plurality of target security identifiers that corresponds to a portion of the result hash value having a particular value; and

allowing access based on whether the input security identifier matches one or more of the plurality of target security identifiers.

22. A method as recited in claim 21, wherein the particular value comprises a value of one.

23. A method as recited in claim 21, wherein each portion is a bit of the result hash value.

24. A method as recited in claim 21, wherein the generating a plurality of sub-hash indexes comprises:

selecting a portion of the input security identifier;

separating the portion into two equal and contiguous sub-portions; and

using each of the sub-portions as one of the plurality of sub-hash indexes.

25. A method as recited in claim 21, wherein the generating the result hash value comprises generating the result hash value by performing a bitwise logical ANDing of the plurality of values.

26. A method as recited in claim 21, wherein the input security identifier comprises an access control security identifier and each of the plurality of target security identifiers comprises a security token security identifier.

27. A method as recited in claim 21, wherein the input security identifier comprises a security token security identifier and each of the plurality of target security identifiers comprises an access control security identifier.

28. One or more computer readable media storing a computer program that is executable by a processor to perform the method recited in claim 21.

29. A computer-based system comprising:

a plurality of security token security identifiers corresponding to a user;

a plurality of access control security identifiers corresponding to an object;

a plurality of sub-hashes, each location in each of the plurality of sub-hashes containing a multiple-bit value, each bit corresponding to one of a plurality of target security identifiers; and

an access controller to determine whether any of the plurality of security token security identifiers match any of the plurality of access control security identifiers by, for each of the plurality of access control security identifiers,

generating a plurality of sub-hash indexes based on a hash key,

indexing into each of the plurality of sub-hashes using a respective one of the plurality of sub-hash indexes,

identifying a plurality of values from the plurality of sub-hashes based on the indexing,

combining the plurality of values to generate a hash result value, wherein each bit in the hash result value corresponds to one of the plurality of security token security identifiers, and

for each bit in the result value that is set,

comparing the access control security identifier to the corresponding security token security identifier to determine whether the values match; and

allowing the user access to the object based on whether the values match.

30. A system as recited in claim 29, wherein the plurality of sub-hashes comprise two sub-hashes.

31. A system as recited in claim 29, wherein each bit in the result value that is set has a value of one.

32. A system as recited in claim 29, wherein the combining comprises bitwise logically ANDing together the plurality of values.

33. A system as recited in claim 29, wherein each of the plurality of values and the hash result value each includes a number of bits equal to a maximum number of security token security identifiers that can be included in the plurality of security token security identifiers.

34. A system as recited in claim 29, wherein the system comprises an operating system.

35. A system as recited in claim 29, wherein the system comprises a resource manager that is not a part of an operating system.

36. A method, comprising:

for each sub-hash in a plurality of sub-hashes that can be used together to generate a hash result for determining whether an input value matches a target value, wherein each location in each of the plurality of sub-hashes contains a multiple-bit value, each bit corresponding to one of a plurality of target values,

(a) identifying a bit in a location of the sub-hash,

(b) identifying, in a source value, a plurality of bits corresponding to the sub-hash,

(c) comparing an identifier of the location to the plurality of bits,

(d) setting the bit if the identifier of the location matches the plurality of bits, and otherwise clearing the bit, and

(e) repeating acts (a), (b), (c), and (d) for each of a plurality of bits in the location of the sub-hash; and

allowing access based on whether the input value matches the target value.

37. A method as recited in claim 36, wherein the plurality of bits correspond to part of a portion of the source value that will be used to generate a hash value.

38. One or more computer readable media storing a computer program that is executable by a processor to perform the method recited in claim 36.