Collision-free hashing for accessing cryptographic computing metadata and for cache expansion

Patent metadata

Field	Value
Publication number	US-11429580-B2
Application number	US-202016912378-A
Country	US
Kind code	B2
Filing date	Jun 25, 2020
Priority date	Jun 25, 2020
Publication date	Aug 30, 2022
Grant date	Aug 30, 2022

Abstract

Embodiments are directed to collision-free hashing for accessing cryptographic computing metadata and for cache expansion. An embodiment of an apparatus includes one or more processors to compute a plurality of hash functions that combine additions, bit-level reordering, bit-linear mixing, and wide substitutions, wherein each of the plurality of hash functions differs in one of the additions, the bit-level reordering, the wide substitutions, or the bit-linear mixing; and access a hash table utilizing results of the plurality of hash functions.

First claim

What is claimed is:

1. An apparatus comprising:
a memory hierarchy storing a hash table, wherein each entry of the hash table comprises a plurality of key-value pairs; and
a core coupled to the memory hierarchy, the core comprising hardware circuitry to:
generate a plurality of hash functions that combine additions, bit-level reordering, bit-linear mixing, and wide substitutions, wherein each hash function of the plurality of hash functions differs from other hash functions in the plurality of hash functions in the bit-linear mixing and is common among the plurality of hash functions in the additions, the bit-level reordering, the wide substitutions; and
iterate through the plurality of hash functions to compute hashed versions of a single key until an access to the hash table is enabled via one of the hashed versions the single key.

2. The apparatus of claim 1 , wherein results of the plurality of hash functions are utilized as a key for a key-value pair of the plurality of key-value pairs of the hash table.

3. The apparatus of claim 1 , wherein the plurality of hash functions are keyed hash functions that share operations comprising the additions, the bit-level reordering, and the wide substitutions, but utilize different keys.

4. The apparatus of claim 1 , wherein the hardware circuitry is further to access the memory hierarchy, wherein at least one level in the memory hierarchy comprises a plurality of cache units, wherein each cache unit of the plurality of cache units is accessed by computing outputs of different cryptographic hash functions from the plurality of hash functions.

5. The apparatus of claim 4 , wherein the outputs of the different cryptographic hash functions are computed in parallel, and wherein the plurality of cache units are accessed in parallel using the outputs as indexes to the plurality of cache units.

6. The apparatus of claim 1 , wherein the plurality of hash functions further combine sequences of one of additions with carries or subtractions with borrows.

7. The apparatus of claim 1 , wherein the wide substitutions comprise implementing S-boxes based on Galois Field (GF) inversion.

8. The apparatus of claim 1 , wherein the hash table is to store metadata corresponding to cryptographic computing.

9. A method comprising:
generating, by a processor, a plurality of hash functions that combine additions, bit-level reordering, bit-linear mixing, and wide substitutions, wherein each hash function of the plurality of hash functions differs from other hash functions in the plurality of hash functions in the bit- linear mixing and is common among the plurality of hash functions in the additions, the bit-level reordering, the wide substitutions; and
iterating, by the processor, through the plurality of hash functions to compute hashed versions of a single key until an access to a hash table is enabled via one of the hashed versions the single key.

10. The method of claim 9 , wherein results of the plurality of hash functions are utilized as a key for a key-value pair of the plurality of key-value pairs of the hash table.

11. The method of claim 9 , wherein the plurality of hash functions are keyed hash functions that share operations comprising the additions, the bit-level reordering, and the wide substitutions, but utilize different keys.

12. The method of claim 9 , further comprising accessing a memory hierarchy where at least one level in the memory hierarchy comprises a plurality of cache units, wherein each cache unit of the plurality of cache units is accessed by computing outputs of different cryptographic hash functions from the plurality of hash functions.

13. The method of claim 12 , wherein the outputs of the different cryptographic hash functions are computed in parallel, and wherein the plurality of cache units are accessed in parallel using the outputs as indexes to the plurality of cache units.

14. The method of claim 9 , wherein the wide substitutions comprise implementing S-boxes based on Galois Field (GF) inversion.

15. The method of claim 9 , wherein the hash table is to store metadata corresponding to cryptographic computing.

16. A non-transitory computer-readable storage medium having stored thereon executable computer program instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
generating, by the one or more processors, a plurality of hash functions that combine additions, bit-level reordering, bit-linear mixing, and wide substitutions, wherein each hash function of the plurality of hash functions differs from other hash functions in the plurality of hash functions in the bit-linear mixing and is common among the plurality of hash functions in the additions, the bit-level reordering, the wide substitutions; and
iterating, by the one or more processors, through the plurality of hash functions to compute hashed versions of a single key until an access to a hash table is enabled via one of the hashed versions the single key.

17. The non-transitory computer-readable storage medium of claim 16 , wherein the plurality of hash functions are keyed hash functions that share operations comprising the additions, the bit-level reordering, and the wide substitutions, but utilize different keys.

18. The non-transitory computer-readable storage medium of claim 16 , wherein the one or more processors to perform further operations comprising accessing a memory hierarchy where at least one level in the memory hierarchy comprises a plurality of cache units, wherein each cache unit of the plurality of cache units is accessed by computing outputs of different cryptographic hash functions from the plurality of hash functions.

19. The non-transitory computer-readable storage medium of claim 18 , wherein the outputs of the different cryptographic hash functions are computed in parallel, and wherein the plurality of cache units are accessed in parallel using the outputs as indexes to the plurality of cache units.

20. The non-transitory computer-readable storage medium of claim 16 , wherein the wide substitutions comprise implementing S-boxes based on Galois Field (GF) inversion.

Assignees

• Intel Corp

Inventors

• Kounavis Michael E
• Ghosh Santosh
• Deutsch Sergej
• Lemay Michael
• Durham David M

Classifications

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F21/45 Primary

  Structures or tools for the administration of authentication · CPC title

• G06F16/24573

  using data annotations, e.g. user-defined metadata · CPC title

• G06F16/24552

  Database cache management · CPC title

• G06F21/602

  Providing cryptographic facilities or services · CPC title