US-12621124-B2 - Non-cryptographic hashing using carry-less multiplication

Abstract

Non-cryptographic hashing using carry-less multiplication and associated methods, software, and apparatus. Under one aspect, the disclosed hash solution expands on CRC technology that updates a polynomial expansion and final reduction, to use initialization (init), update and finalize stages with extended seed values. The hash solutions operate on input data partitioned into multiple blocks comprising sequences of byte data, such as ASCII characters. During multiple rounds of an update stage, operations are performed on sub-blocks of a given block in parallel including carry-less multiplication and shuffle operations. During a finalize stage, multiple SHA or carry-less multiplication operations are performed on data output following a final round of the update stage.

Inventors

• Gregory B. Tucker
• Vinodh Gopal

Assignees

• INTEL CORPORATION

Dates

Publication Date

20260505

Application Date

20220902

Claims (18)

1. 1 . A method for performing a non-cryptographic hash over input data, comprising: performing a first stage to generate an initialization (init) value; performing multiple rounds of an update stage on sequential blocks of the input data, wherein a round of the update stage employs an output from a previous round as an input to that round, wherein rounds of the update stage operate on multiple sub-blocks of input data in parallel using multiple sets of accumulators; and performing a finalize stage operating on an output from a last round of the update stage, partial data following a last block of input data and the init value as an input, wherein the finalize stage employs SHA (Secure Hash Algorithm) instructions or clmul (carry-less multiplication) instructions, in part, to generate a hash digest.
2. 2 . The method of claim 1 , wherein each block comprises 256 bytes and each set of accumulators comprise 16 one-byte accumulators.
3. 3 . The method of claim 1 , multiple operations are performed on each sub-block of data during an update stage round, including one or more carry-less multiplication operations and at least one shuffle operation.
4. 4 . The method of claim 1 , wherein one or more 512-bit Single Instruction Multiple Data (SIMD) clmul instructions are employed during a round of an update stage.
5. 5 . The method of claim 1 , wherein the hash digest comprises a 128-bit hash digest.
6. 6 . The method of claim 1 , wherein the SHA instructions comprise SHA1 instructions.
7. 7 . The method of claim 1 , wherein generation of the init value employs a random seed and comprises multiple operations including a shuffle operation.
8. 8 . The method of claim 1 , further comprising employing multiple bitwise XOR operations during a round of an update stage and the finalize stage.
9. 9 . The method of claim 1 , wherein rounds of the update stage operating on multiple sub-blocks of data employs random constants for each sub-block.
10. 10 . A non-transitory machine-readable storage medium having instructions stored thereon configured to be executed on one or more processors to generate a non-cryptographic hash digest over input data, wherein generation of the non-cryptographic hash digest comprises: performing a first stage to generate an initialization (init) value; performing multiple rounds of an update stage on sequential blocks of the input data, wherein a round of the update stage employs an output from a previous round as an input to that round and employs carry-less multiplication operations on m-bit values, wherein rounds of the update stage operate on multiple sub-blocks of input data in parallel using multiple sets of accumulators; and performing a finalize stage operating on an output from a last round of the update stage partial data following a last block of input data and the init value as an input, wherein the finalize stage generates and n-bit hash digest, where n>m.
11. 11 . The non-transitory machine-readable storage medium of claim 10 , wherein each block comprises 256 bytes and each set of accumulators comprise 16 one-byte accumulators.
12. 12 . The non-transitory machine-readable storage medium of claim 10 , multiple operations are performed on each sub-block of data during an update stage round, including one or more carry-less multiplication operations and at least one shuffle operation.
13. 13 . The non-transitory machine-readable storage medium of claim 10 , wherein the hash digest comprises a 128-bit hash digest and wherein instructions include one or more 512-bit Single Instruction Multiple Data (SIMD) clmul instructions that are executed during a round of an update stage.
14. 14 . The non-transitory machine-readable storage medium of claim 10 , wherein rounds of the update stage operating on multiple sub-blocks of data employs random constants for each sub-block.
15. 15 . A computing system, comprising: one or more processors; memory, operatively coupled to the one or more processors; and instructions, to be executed on the one or more processors to enable the computing system to generate an n-bit non-cryptographic hash digest over input data by: performing a first stage to generate an initialization (init) value; performing multiple rounds of an update stage on sequential blocks of the input data, wherein a first round of the update stage uses first values as an input and a subsequent round of the update stage employs an output from a previous round as an input to that round, wherein an update stage round employs carry-less multiplication instructions operating on m-bit data values, wherein m<n, wherein rounds of the update stage operate on multiple sub-blocks of data in parallel using multiple sets of accumulators; and performing a finalize stage operating on the init value, on an output from a last round of the update stage and partial data following a last block of input data to generate the n-bit non-cryptographic hash digest.
16. 16 . The computing system of claim 15 , wherein multiple operations are performed on each sub-block of data during an update stage round, including at least one shuffle operation.
17. 17 . The computing system of claim 15 , wherein the finalize stage employs SHA (Secure Hash Algorithm) instructions executed on a processor.
18. 18 . The computing system of claim 15 , wherein rounds of the update stage operating on multiple sub-blocks of data employs random constants for each sub-block.

Description

BACKGROUND INFORMATION High quality hashing is important in many storage and communication systems. Previous solutions to high-quality hashing usually involve cryptographic hashes or fast hashes based on the avalanche properties of combining ordinary integer arithmetic (multiply, add, shift, etc.). Cryptographic hashes are often based on NIST or other published standards such as SHA, MD5 or SM3. While these cryptographic algorithms produce high-quality hashes, they are often computationally too complex to meet throughput or latency goals. Non-cryptographic hashes in use include Murmur, cityhash, xxhash and others, which are based on integer arithmetic alone. Many non-cryptographic hashes are of limited size, 32 to 64-bits, and/or of limited quality. BRIEF DESCRIPTION OF THE DRAWINGS The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same becomes better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein like reference numerals refer to like parts throughout the various views unless otherwise specified: FIG. 1 is a flowchart illustrating a three-stage process for generating a hash digest, according to one embodiment; FIG. 2 is a process flow diagram illustrating input and operations for generating an init value, according to one embodiment; FIG. 3a is a process flow diagram illustrating input and operations performed in parallel during a first round of the update stage of FIG. 1 employing the init value as an input, according to one embodiment; FIG. 3b is a process flow diagram illustrating input and operations performed by subsequent rounds of the update stage, according to one embodiment; FIG. 4a is a diagram showing data from a first portion of input data being loaded into sets of accumulators to be processed during a first round of the update stage; FIG. 4b is a diagram showing data from a second portion of input data following the first portion being loaded into sets of accumulators to be processed during a second round of the update stage; FIG. 5a is shows the input data being partitioned into multiple fixed-size blocks followed by a partial h having a size less than the block size; FIG. 5b is a process flow diagram illustrating data output during the last round of the update stage being bitwise XOR'ed to generate an acc value; FIG. 6 is a process flow diagram illustrating inputs and operations performed during the finalize stage, according to one embodiment; FIG. 6a is a process flow diagram illustrating an alternative embodiment of the finalize stage under which SHA1 operations are replaced with carry-less multiplication operations; and FIG. 7 is a diagram illustrating an example computing system that may be used to practice one or more embodiments disclosed herein. DETAILED DESCRIPTION Embodiments of non-cryptographic hashing using carry-less multiplication and associated methods and apparatus are described herein. In the following description, numerous specific details are set forth to provide a thorough understanding of embodiments of the invention. One skilled in the relevant art will recognize, however, that the invention can be practiced without one or more of the specific details, or with other methods, components, materials, etc. In other instances, well-known structures, materials, or operations are not shown or described in detail to avoid obscuring aspects of the invention. Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, the appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments. For clarity, individual components in the Figures herein may also be referred to by their labels in the Figures, rather than by a particular reference number. Additionally, reference numbers referring to a particular type of component (as opposed to a particular component) may be shown with a reference number followed by “(typ)” meaning “typical.” It will be understood that the configuration of these components will be typical of similar components that may exist but are not shown in the drawing Figures for simplicity and clarity or otherwise similar components that are not labeled with separate reference numbers. Conversely, “(typ)” is not to be construed as meaning the component, element, etc. is typically used for its disclosed function, implement, purpose, etc. In accordance with aspects of the embodiments described and illustrated herein, a novel high-speed hashing technology is provided that employs technology