Calculating hash values

Determining hash values based on at least two types of hash functions, utilizing a memory that is arranged to store at least one state to be used to determine hash values pursuant to a SHA-3 function, wherein hash values pursuant to any of a SHA-2 function or a SHA-1 function are determined based on the state.

TECHNICAL FIELD

The present disclosure is related to devices for producing cryptographic hash values.

BACKGROUND

Currently, three types of cryptographic hash functions are standardized by NIST and commonly used, namely SHA-1, SHA-2 and SHA-3:SHA-1: A 160-bit hash function which resembles the earlier MD5 algorithm. This was designed by the National Security Agency (NSA) to be part of the Digital Signature Algorithm. Cryptographic weaknesses were discovered in SHA-1, and the standard was no longer approved for most cryptographic uses after 2010.SHA-2: A family of two similar hash functions, with different block sizes, known as SHA-256 and SHA-512. They differ in the word size; SHA-256 uses 32-byte words where SHA-512 uses 64-byte words. There are also truncated versions of each standard, known as SHA-224, SHA-384. SHA-512/224 and SHA-512/256. These were also designed by the NSA.SHA-3: A hash function formerly called Keccak, chosen in 2012 after a public competition among non-NSA designers. It supports the same hash lengths as SHA-2, and its internal structure differs significantly from the rest of the SHA family.

It is noted that each hash function SHA-1. SHA-2 or SHA-3 is herein also referred to as a type of hash function. Each type of hash function may have several different implementations and/or—in case of SHA-2—families of hash functions.

SHA-1 and SHA-2 use the Mergle-Damgard construction and are ARX (add, rotate, xor)-based designs. SHA-3 uses the Sponge construction and is an SPN (substitution permutation network)-based design.

Additionally, all hash functions have derivates with different message, hash, state, chaining value and word sizes, which results in different interfaces, memories, and data paths for each of the hash function.

For example, word sizes of 32-bit or 64-bit and different intermediate state sizes amounting to, e.g., 160-bit for SHA-1 or 1600 bits for SHA-3, are used.

SUMMARY

Due to variations in design, separate hardware realizations (also referred to as hardware accelerators) are implemented for each of the several types of hash function. This applies in particular for SHA-3, which utilizes a design that is substantially different from SHA-1 or SHA-2.

It is a disadvantage that any hardware that is capable of providing hash values according to different types of hash functions, e.g., SHA-1, SHA-2 or SHA-3, require a large amount of space in hardware, in particular on a chip.

Hence, based on the general objective for efficient area utilization, it is an objective to enable an optimized hardware structure that is capable of performing several hash functions, in particular at least two different types of hash functions.

This is solved according to the features of the independent claims. Further embodiments result from the dependent claims.

The examples suggested herein may be based on at least one of the following solutions.

Combinations of the following features could be utilized in order to reach a desired result. The features of the method could be combined with any feature(s) of the device, apparatus, or system, or vice versa.

A device is provided for determining hash values based on at least two types of hash functions, wherein the devicecomprises a memory that is arranged to store at least one state to be used to determine hash values pursuant to a SHA-3 function, andis arranged to determine hash values pursuant to any of a SHA-2 function or a SHA-1 function based on the state.

The SHA-2 function may be a SHA-256 function or a SHA-512 function.

According to an embodiment, each of the states comprises bits that are arranged in a virtual data cube, wherein the virtual data cube comprises:a number of z slices,a number of y planes, anda number of x sheets.

The state may be a data structure that is stored in the memory. The organization of the state allows for an efficient determination of hash values for different types of hash functions. The state may thus serve as a shared memory to be used differently for each type of hash function.

It is noted thateach plane comprises a number of z rows and a number of x lanes;each slice comprises a number of x columns and a number of y rows; andeach sheet comprises a number of y columns and a number of z lanes.

According to an embodiment, an input message of the SHA-2 function and chaining values of the SHA-2 function are stored in lanes of the state.

According to an embodiment, an addition of the SHA-2 function is computed in a slice-by-slice manner on the slices of the state.

According to an embodiment, bitwise Boolean functions majority and choice of the SHA-2 function are each computed in a slice-by-slice manner on the slices of the state.

According to an embodiment, sigma functions of SHA-2 function computed in a lane-by-lane manner on lanes of the state.

According to an embodiment, the state is part of a shared hardware, which further comprises a shared interface, shared data paths and/or a shared logic to determine the hash values.

According to an embodiment, the device is at least one of the following or it is at least part of one of the following or it comprises at least one of the following:an integrated circuit,a hardware security module,a trusted platform module.a crypto unit,a FPGA.a processing unit.a controller,a smartcard.

Also, a method is suggested for determining hash values based on at least two types of hash functions,wherein a shared memory comprises at least one state, wherein the structure of the state is capable of determining hash values pursuant to the SHA-3 function,wherein hash values pursuant to any of a SHA-2 function or a SHA-1 function are determined based on the structure of the state.

Further, a computer program product is provided, which is directly loadable into a memory of a digital processing device, comprising software code portions for performing the steps of the method as described herein.

DETAILED DESCRIPTION

Examples described herein in particular refer to a shared hardware that may be used for compiling different types of hash functions, in particular at least two out of SHA-1. SHA-2, and SHA-3. The hardware may be shared on several levels, e.g., a shared interface, a shared memory, shared data paths and/or a shared logic. The solutions presented allow significantly reducing the hardware overhead by a hardware solution that implements, e.g., the SHA-3 function in combination with the SHA-1 function and/or the SHA-2 function.

The shared interface of the shared hardware comprises a memory-based interface using, e.g., 32-bit words or 64-bit words.

An example may be as follows: The SHA-1 part of the shared interface comprises sixteen (16) 32-bit message words and five (5) 32-bit hash or chaining value words. The SHA-256 part of the shared interface comprises sixteen (16) 32-bit message words and eight (8) 32-bit hash or chaining value words, whereas the SHA-512 part of the shared interfaces comprises sixteen (16) 64-bit message words and eight (8) 64-bit hash or chaining value words. The SHA-3 part of the shared interface comprises twenty-five (25) 64-bit words containing the whole SHA-3 state consisting of nine (9) to twenty-one (21) 64-bit message words depending on respective hash function.

The shared interface is mapped to enable an efficient data transfer between a central processing unit (CPU) and the shared hardware. The shared memory of the shared hardware may contain software for at least a portion of each type of hash function. In addition, each data word can be accessed in a random or pseudo-random order, which can be useful for security applications.

Although each type of hash function utilizes a different state size and memory structure (different state, message, hash, chaining value, word sizes), the approach provided herein suggests using a shared memory for all types of hash functions to reduce the overall area required on the hardware (i.e., on at least one chip).

To further optimize the shared hardware, a shared datapath and shared logic may be used. The shared datapath may be used for all three types of hash functions. The various types of hash functions use word-wise functions, which may be different for each type of hash function. The functions may contain rotations, shifts, 32-bit and 64-bit word operations and rotate-with-XOR functions (sigma functions of SHA-2). Also, modular additions are required for SHA-1 and SHA-2 and Rho, Iota, Theta, Pi and Chi (Sbox) functions for SHA-3. Within the shared datapath, shared logic is used which breaks these different functions into common pieces, which are then combined by the hardware again to compute all necessary functions for SHA-1. SHA-2, and SHA-3.

FIG.1shows an exemplary structure of a state100that may be used for each type of hash function. The state100is visualized as a three-dimensional data structure comprising three axes x, y, and z. The single element of the state is a bit, and the z-dimension indicates the length of the word, which may be, e.g., a 32-bit word or a 64-bit word.

In the example ofFIG.1, an exemplary number of eight (8) bits are shown in z-direction, whereas an actual implementation may utilize words with thirty-two (32) bits or sixty-four (64) bits.

The state100is an exemplary data structure that may be stored to a memory in various ways. For example, the three-dimensional state100can be stored in a linear memory. For example, a memory management system or any software accessing the linear memory may ensure that a virtual three-dimensional data structure can be accessed. e.g., via coordinates or indices.

The state100may be used for each type of hash function as follows:

Data can be stored in various portions of the state100, which is a data structure with a predefined number of bits in z-direction. Hence, when reference is made to a “word” that is stored in a lane this refers to a lane of the state100. The state100has as many bits in z-direction as there are bits in the word. An exemplary word may have thirty-two (32) bits or sixty-four (64) bits, but other implementations are feasible as well.

The state100corresponds to a memory that is utilized for SHA-3. The solution presented herein allows using this state100also for SHA-2 or SHA-1.

According to an exemplary embodiment, a variant of SHA-3 may use fifty (50) 32-bit lanes with bit index j=0, 1, . . . , 31.

SHA-3 further comprises the functions Theta, Pi, Rho, Chi, Iota (see. e.g., https://en.wikipedia.org/wiki/SHA-3). The functions Theta, Pi, Chi, Iota are usually computed slice-by-slice in hardware. The function Rho is usually computed lane-by-lane in hardware.

In an exemplary implementation, SHA-512 may further useAn input message: w[0] . . . w[15], which corresponds to 16 words that are stored in 16 lanes of the state100.Chaining values: a, b, c, d, e, f, g, h, which are 8 words that are stored in 8 lanes of the state100.

The input message (16 words) and the chaining values (8 words) are stored as twenty-four (24) words in twenty-four (24) lanes out of the twenty-five (25) lanes of the state100.

Further, SHA-2 consists of additions, bitwise Boolean functions (maj, ch) and sigma functions (s0, s1, S0, S1):The addition is computed slice-by-slice (starting from bit0because of the carry bit or since addition is a T-function).The bitwise Boolean functions majority (maj) and choice (ch) are computed slice-by-slice.The sigma functions s0, s1, S0, S1 are computed lane-by-lane.

Hereinafter, “temp1” and “temp2” are temporary values. “and”, “xor”, “not” are Boolean functions. “rightrotate k” is a rotate instruction to the right by k bits and “rightshift k” is a shift instruction to the right by k bits.

The sigma functions to be computed on lanes (words) are as follows:

Additions and Boolean functions are computed slice-by-slice (instead of word-by-word for round [i]) as follows:

Each bit-wise addition may be conducted using a standard full adder. However, other types of bit-wise adders may be used accordingly.

with c[0]=0 and j=0, 1, . . . 63 (in case of SHA-512) or j=0, 1, . . . 31 (in case of SHA-256) the carry bits of all ten (10) adders may be stored temporarily and can be used by the operation directed to the next slice.

FIG.2shows a block diagram comprising a processing unit201capable of computing hash values203based on different types of hash functions. The processing unit201has access to a shared memory202, which comprises several states203. Each state is a virtual data structure as shown inFIG.1. The data structure is virtual, because the actual implementation of the virtual cube structure can be achieved in many ways via. e.g., file management systems.

FIG.3shows a schematic flow chart comprising steps of a method to compile hash values for different types of hash functions by utilizing the common virtual data structure “state.” In a step301, a hash value is to be determined for one of various types of hash functions. The types of hash functions comprise SHA-1, SHA-2, and SHA-3. In a step302, a shared memory is used to utilize a state100(seeFIG.1) as the virtual data structure to compile the hash value based on the respective type of hash function.