TWI861966B - Processor, data processing system, method and design structure for performing secure hash algorithms - Google Patents

Abstract

A processor includes a register file and an execution unit. The execution unit includes a hash circuit including at least a state register, a state update circuit coupled to the state register, and a control circuit. Based on a hash instruction, the hash circuit receives from the register file and buffers within the state register a current state of a message being hashed. The state update circuit performs state update function on contents of the state register, where performing the state update function includes performing a plurality of iterative rounds of processing on contents of the state register and returning a result of each of the plurality of iterative rounds of processing to the state register. Following completion of all of the plurality of iterative rounds of processing, the execution unit stores contents of the state register to the register file as an updated state of the message.

Description

Processor, data processing system, method and design structure for executing secure hashing algorithm

The present invention relates generally to data processing, and more particularly to efficiently executing secure hashing algorithms in hardware.

An important aspect of data security is the protection of data at rest (e.g., when stored in a data storage device) or in transition (e.g., during transmission) through encryption. In general, encryption involves converting unencrypted data (called plaintext) into encrypted data (called ciphertext) by combining the plaintext with one or more encryption keys using an encryption function. To recover the plaintext from the ciphertext, the ciphertext is processed by a decryption function using one or more decryption keys. Thus, encryption provides data security by requiring that an additional secret (i.e., a decryption key) be known to a party before the party can access the protected plaintext.

In many implementations, data encryption is performed in software running on a general-purpose processor. While implementing encryption in software offers the advantage of being able to choose from different encryption algorithms and easily adapting the selected encryption algorithm to work with a variety of data lengths, performing encryption in software has the attendant disadvantage of relatively poor performance. As the size of data sets continues to increase dramatically in the "Big Data" era, the performance achieved by implementing encryption in software may be unacceptable when encrypting large messages and/or data sets. Concerns about encryption performance have also arisen due to the increasing need to run enterprise applications with encrypted data in order to mitigate the consequences of "hacktivism" and other cyberattacks and to ensure regulatory compliance. Therefore, it is often desirable to provide support for encryption in hardware to achieve improved performance.

The present invention recognizes that one class of cryptographic algorithms for which hardware support is desirable is hash functions, including but not limited to hash functions belonging to the Secure Hash Algorithm (SHA) family of standards. As is known in the art, the SHA family of standards defines hash algorithms approved by the National Institute of Standards (NIST) for generating compressed representations of messages (i.e., message digests). The SHA family of standards is specified in two Federal Information Processing Standards (FIPS): FIPS 180-4 "Secure Hash Standard" and FIPS 202 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions", which are incorporated herein by reference. FIPS 180-4 specifies seven hashing algorithms, namely Secure Hash Algorithm-1 (SHA-1) and the SHA-2 family of hashing algorithms, including SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, and SHA-512/256. FIPS 202 additionally specifies four SHA-3 hashing algorithms with fixed-length outputs (i.e., SHA3-224, SHA3-256, SHA3-384, and SHA3-512) and two closely related "extensible output" functions (XOFs) named SHAKE128 and SHAKE256 (where SHAKE is an abbreviation for Secure Hash Algorithm and Keccak). Additional uses of the SHA family of standards (e.g., as a stream cipher, an authenticated encryption system, or a tree hashing scheme) have not yet been adopted as NIST standards.

Given the wide variety of hash functions and the data sizes of hash functions (even within the SHA family of standards), widespread support in hardware for hash functions can result in a large area within the processor layout being consumed by circuitry implementing the hash functions. As a result, some hardware solutions choose to implement this circuitry separately from the processor core, for example in a bus-attached application specific integrated circuit (ASIC) or accelerator. While offering the potential for better performance than some software solutions, the use of such auxiliary circuitry is still subject to bus and memory access latency and message passing overhead, again limiting performance compared to what can be achieved within a high-performance processor core. This performance loss is particularly severe for relatively small messages (e.g., messages that fit within a single message block), which are the majority of SHA messages processed in enterprise servers. The present invention addresses these and other design considerations by efficiently implementing the hash function in the processor.

In one embodiment, a processor includes a register file and an execution unit. The execution unit includes: a hash circuit including at least one state register; a state update circuit coupled to the state register; and a control circuit. Based on a hash instruction, the hash circuit receives from the register file and buffers a current state of a message being hashed in the state register. The state update circuit executes a state update function on the content of the state register, wherein executing the state update function includes executing a plurality of iterative rounds of processing on the content of the state register, and returning a result of each of the plurality of iterative rounds of processing to the state register. After completing all the plurality of iterative rounds of processing, the execution unit stores the content of the state register to the register file as an updated state of the message.

The processor may be incorporated into a data processing system comprising a plurality of processors, a shared memory, and a system interconnect communicatively coupling the shared memory and the plurality of processors. The processor may also be tangibly embodied in a machine-readable storage device for use in a design structure for designing, manufacturing, or testing an integrated circuit.

In one embodiment, a method for performing data processing in a processor includes fetching instructions to be executed by the processor by an instruction fetch unit. The instructions include a hash instruction. Based on receiving the hash instruction, an execution unit of the processor executes the hash instruction. Executing the hash instruction includes receiving from a register file and buffering a current state of a message being hashed in a state register of the execution unit. Executing the hash instruction also includes executing a state update function on the content of the state register in a state update circuit, wherein executing the state update function includes executing a plurality of iterative rounds of processing on the content of the state register, and returning a result of each of the plurality of iterative rounds of processing to the state register. After completing all of the plurality of iterative rounds of processing, the content of the state register is stored in the register file as an updated state of the message.

In at least some embodiments, the state update function comprises a secure hash algorithm 3 (SHA3) state permutation function; and the state update circuit performs twenty-four rounds of processing, each round of processing utilizing a respective round index of the twenty-four round indices as an input.

In one embodiment, the execution unit executes the hash instruction in a squeeze phase of a secure hash algorithm and a Keccak (SHAKE) hash algorithm.

In at least some embodiments, the state update function comprises a secure hash algorithm 2 (SHA2) block hash function. In at least some embodiments, the hash circuit further comprises an adder configured to add the contents of the state register to the current state and return a resulting sum to the register file. In some embodiments, the execution unit further comprises a message block register for buffering a message block of the message and a message scheduling round circuit coupled to the message block register. The message scheduling circuit performs a plurality of iterative rounds of processing on the content of the message block register and returns a result of each of the plurality of iterative rounds of processing to the message block register. In some embodiments, the state update circuit includes a data path for data words having a first data width, and the execution unit is configured to expand the data words of a message block of the message to the first data width before processing the data words of the message in the state update circuit based on the hash instruction indicating a second data width narrower than the first data width.

100:Data processing system

102: Processor

104: Processor core

106: Cache memory

110: System interconnects

112:Memory controller

114: System memory

116: Input/output (I/O) adapter

118: Non-volatile storage system

120: Network adapter

200: Processor cores

202: Instruction fetch unit

204: Instruction decoding unit

206: Branch processing unit

210: Mapper circuit

216: Dispatching circuit

218: Release Queue

220: Fixed point unit

222: Floating point unit

224: Load-storage unit

226: Vector-scalar unit

230: Storage

300:Architecture register file

301: 256-bit registers r0 to rS

302: Functional unit/arithmetic logic unit/rotation unit

304: Functional unit/multiplication unit

306: Functional unit/division unit

308: Functional unit/encryption unit

310: Functional unit/replacement unit

312: Functional unit/Binary Code Decimal (BCD) unit

314: Accelerator unit

316: Wide vector register file

317: Registers R0 and R1

320: Transmission unit

400: SHA3/SHAKE hashing circuit

402: SHA2 hashing circuit

404: Single instruction multiple data (SIMD) exclusive OR (XOR) circuit

406: Data transmission circuit

500:Procedure

502: Message

504: SHA3 absorption phase

506: SHA3/SHAKE squeeze phase

508: Message summary

600: Block

602: 1600-bit extended message block

604: SHA3 state replacement function

606: 1600-bit bit-by-bit XOR function

610:1600 bits final absorption status

702: Round index 0 specified by the SHA-3 standard

704: SHA3 round function

800: Result block 1

802: Truncation function

804: Truncation function

900: SHA3 hashing instruction

902: Operation code field

904: Register field

906: Register field

1000: Bit-by-bit XOR instruction

1002: Operation code field

1004: Register field

1006: Register field

1008: Register field

1100a: 1024-bit dual-input multiplexer

1100b: 1024-bit dual-input multiplexer

1102a: 1024-bit status register

1102b: 1024-bit status register

1106: SHA3 round circuit

1108: Output multiplexer

1110: Control circuit/control logic

1200: Block

1202: Block

1204: Block

1206: Block

1208: Block

1210: Block

1214: Block

1216: Block

1300: SHA2 hash function

1302: Message

1304: Block

1306: 16× w- bit message block/message block 1

1308:8× w bits initial state

1310: SHA2 block hash function

1312: Truncation function

1314: Message summary

1400: message scheduling round function

1402: w- bit round key

1404: Round function/initial update round

1406: Block

1410:8× w bit carry propagation addition function

1420: Block/16× w bit initialization

1500: SHA2-224 or SHA2-256 input message

1502: 32-bit word

1504: Output message

1506:64-bit double word

1508: 32-bit zero word

1600: SHA2 hashing instruction

1602: Operation code field

1604: Operand register field

1606: Operand register field

1608: Mode field

1702a:512-bit dual input state multiplexer

1702b: 1024-bit dual-input message multiplexer

1704a:512-bit status register

1704b: 1024-bit message block register

1708: Update working status circuit

1710: Message scheduling return circuit

1712: Single Instruction Multiple Data (SIMD) adder

1720: Control circuit

1800: Block/input status

1802: SHA2 Sigma 0 circuit

1804: SHA2 MA circuit

1806: SHA2 Sigma 1 Circuit

1808: SHA2 CH circuit

1810:64-bit adder

1812: 64-bit adder/modular adder

1814:64-bit adder/modular adder

1816: Result status

1900:SHA2 Sigma Circuit

1902:64-bit input variable

1904a: 64-bit rotation circuit

1904b: 64-bit rotation circuit

1906a: 32-bit rotation circuit

1906b: 32-bit rotation circuit

1908a: 64-bit rotate/shift circuit

1908b: 32-bit rotate/shift circuit

1910a: Multiplexer

1910b: Multiplexer

1910c: Multiplexer

1912: Three-input 64-bit bit-by-bit XOR circuit/3-way bit-by-bit XOR circuit

1914:64-bit output

2000: Block

2002: Block

2004: Block

2006: Block

2010: Block

2012: Block

2014: Block

2016: Block

2100: Unfilled message

2300:Last message block

2300':Last message block

2300":Last message block

2302: EOM padding byte

2304:EOB padding byte

2306: Last message byte

2308: EOM/EOB padding bytes

2310: Message block

2312: Additional zero message block

2400:Last message block

2400':Last message block

2400":Last message block

2402: EOM fill byte

2404:EOB filler

2406:Last message byte

2408: Message block

2410: Complete message block

2412: Message block

2500: Filling instructions

2502: Operation code field

2504: Register 1 field

2506: Register 2 field

2508: Mode field

2510: Hash identifier (HID) subfield

2512: Block length (BL) subfield

2514: Expand (E) subfield

2600: Filling circuit

2602: Select EOM circuit

2604: Select EOB circuit

2606: Select BL size circuit

2608:EOB enabling circuit

2610: Comparator

2612:Decoder

2614: Bit-by-bit AND circuit

2620: EOM enabling circuit/selection circuit

2622: Comparator

2624:Decoder

2626: Bit-by-bit AND circuit

2630:Conditional "or" circuit

2700: "or" gate

2702: Double input "and" gate

2704: Double input "and" gate

2800: Block

2802: Block

2804: Block

2806: Block

2808: Block

2810: Block

2812: Block

2814: Block

2816: Block

2818: Block

2820: Block

2822: Block

2900: Design process

2910: Design Program

2920: Design structure

2930:Library component

2940: Design specifications

2950: Characterization data

2960: Verification data

2980: Wiring comparison table

2985:Test data file

2990: Design rules/second design structure

2995: Stage

FIG. 1 is a high-level block diagram of a data processing system including a processor according to one embodiment; FIG. 2 is a high-level block diagram of a processor core according to one embodiment; FIG. 3 is a high-level block diagram of an exemplary execution unit of a processor core according to one embodiment; FIG. 4 is a more detailed block diagram of an accelerator unit within a processor core according to one embodiment; FIG. 5 is a time-space diagram of message hashing according to the SHA-3 standard; FIG. 6 is a block diagram of FIG. FIG. 7A is a time-space diagram of the SHA3 permutation function depicted in FIG. 6 ; FIG. 7B is a time-space diagram of the SHA3 round function depicted in FIG. 7A ; FIG. 8 is a time-space diagram of the SHA3/SHAKE squeeze phase depicted in FIG. 5 ; and FIGS. 9 to 10 respectively illustrate a time-space diagram for a SHA3 hash instruction and a bitwise exclusive or (exclusive FIG. 11 is a high-level block diagram of an exemplary SHA3/SHAKE hashing circuit according to one embodiment; FIG. 12 is a high-level logic flow chart of an exemplary procedure by which a processor executes a SHA3 hashing instruction according to one embodiment; FIG. 13 depicts a time-space diagram of message hashing according to the SHA-2 standard; FIG. 14 is a time-space diagram of the SHA2 block hashing function shown in FIG. 13; FIG. 15 depicts a time-space diagram of the SHA2 block hashing function shown in FIG . FIG. 16 depicts an exemplary format for a SHA2 hash instruction according to one embodiment; FIG. 17 is a high-level block diagram of an exemplary SHA2 hash circuit according to one embodiment; FIG. 18 is a high-level block diagram of an exemplary update working state circuit from FIG. 17 according to one embodiment; FIG. 19 is a SHA2 sigma circuit as shown in FIG. FIG. 20 is a high-level logic flow diagram of an exemplary process by which a processor executes a SHA2 hash instruction according to one embodiment; FIG. 21A depicts an exemplary unfilled message; FIG. 21B depicts an exemplary filled message; FIGS . 22A - 22B depict assembling blocks of message blocks in a narrower first register file and transferring the message blocks to a wider second register file; and FIGS. 23A - 23D depict various filling scenarios for SHA3/SHAKE messages. 24A to 24D depict various padding scenarios for SHA2 messages; FIG. 25 depicts an exemplary padding instruction according to an embodiment; FIG. 26 depicts an exemplary padding circuit according to an embodiment; FIG. 27 depicts an exemplary circuit for combining end of block (EOB) and end of message (EOM) bytes and messages according to an embodiment; FIG. 28 is a high-level logic flow chart of an exemplary procedure for padding message blocks according to an embodiment; and FIG. 29 depicts an exemplary design procedure according to an embodiment.

Referring now to the figures and in particular to FIG1 , a high-level block diagram of a data processing system 100 is shown according to one embodiment. In some implementations, the data processing system 100 may be, for example, a server computer system (e.g., one of the POWER series servers available from Business Machines Corporation), a mainframe computer system, a mobile computing device (e.g., a smartphone or tablet), a laptop or desktop personal computer system, or an embedded processor system.

As shown, data processing system 100 includes one or more processors 102 that process instructions and data. As is known in the art, each processor 102 may be implemented as a respective integrated circuit having a semiconductor substrate in which the integrated circuit system is formed. In at least some embodiments, processor 102 may generally implement any of a number of commercially available processor architectures, such as POWER, ARM, Intel x86, NVidia, Apple silicon, etc. In the depicted example, each processor 102 includes one or more processor cores 104 and a cache memory 106 that provides low latency access to instructions and operands that are likely to be read and/or written by processor core 104 . Processors 102 are coupled for communication via a system interconnect 110 , which in various implementations may include one or more buses, switches, bridges, and/or hybrid interconnects.

The data processing system 100 may additionally include a number of other components coupled to the system interconnect 110. For example, such components may include a memory controller 112 that controls access to a system memory 114 by the processor 102 and other components of the data processing system 100. In addition, the data processing system 100 may include an input/output (I/O) adapter 116 for coupling one or more I/O devices to the system interconnect 110 , a non-volatile storage system 118 , and a network adapter 120 for coupling the data processing system 100 to a communication network (e.g., a wired or wireless local area network and/or the Internet).

Those skilled in the art will also appreciate that the data processing system 100 shown in FIG. 1 may include many additional components that are not shown. Because such additional components are not necessary for understanding the described embodiments, they are not shown in FIG. 1 or further discussed herein. However, it should also be understood that the enhancements described herein are applicable to data processing systems and processors of different architectures and are in no way limited to the generalized data processing system architecture shown in FIG. 1 .

2 , a high-level block diagram of an exemplary processor core 200 is depicted according to one embodiment. The processor core 200 may be used to implement any of the processor cores 104 of FIG. 1 .

In the depicted example, the processor core 200 includes an instruction fetch unit 202 for fetching instructions in one or more instruction streams from memory 230 (which may include, for example, cache 106 and/or system memory 114 of FIG. 1 ). In a typical implementation, each instruction has a format defined by the instruction set architecture of the processor core 200 and includes at least an operation code (opcode) field that specifies an operation to be performed by the processor core 200 (e.g., fixed-point or floating-point arithmetic operations, vector operations, matrix operations, logical operations, branch operations, memory access operations, cryptographic operations, etc.). Some instructions may additionally include one or more operand fields that directly specify operands or implicitly or explicitly reference one or more registers storing source operands to be used in the execution of the instruction and one or more registers for storing destination operands generated by the execution of the instruction. Instruction decode unit 204 , which may be combined with instruction fetch unit 202 in some embodiments, decodes instructions fetched from register 230 by instruction fetch unit 202 and transfers branch instructions that control the flow of execution to branch processing unit 206. In some embodiments, the processing of branch instructions performed by branch processing unit 206 may include speculating the outcome of a conditional branch instruction. The results of branch processing (both speculative and non-speculative) performed by branch processing unit 206 may then be used to redirect one or more streams of instruction fetches performed by instruction fetch unit 202 .

Instruction decode unit 204 forwards instructions that are not branch instructions (often referred to as "sequential instructions") to mapper circuit 210. Mapper circuit 210 is responsible for assigning physical registers within the register file of processor core 200 to instructions as needed to support instruction execution. Mapper circuit 210 preferably implements register renaming. Thus, for at least some classes of instructions, mapper circuit 210 establishes a temporary mapping between a set of logical (or architectural) registers referenced by the instruction and a larger set of physical registers within the register file of processor core 200 . As a result, processor core 200 may avoid unnecessary serialization of non-data-dependent instructions that may otherwise occur due to nearby instructions in program order reusing a limited set of architected registers.

Still referring to FIG. 2 , the processor core 200 further includes a dispatch circuit 216 that is configured to ensure that any data dependencies between instructions are observed and to dispatch sequential instructions when the sequential instructions become ready to execute. Instructions dispatched by the dispatch circuit 216 are temporarily buffered in an issue queue 218 until the execution unit of the processor core 200 has resources available to execute the dispatched instructions. When appropriate execution resources become available, the issue queue 218 opportunistically and possibly out of order relative to the original program order of the instructions issues instructions from the issue queue 218 to the execution unit of the processor core 200 .

In the depicted example, processor core 200 includes several different types of execution units for executing respective different classes of instructions. In this example, the execution units include: one or more fixed-point units 220 for executing instructions that access fixed-point operands; one or more floating-point units 222 for executing instructions that access floating-point operands; one or more load-store units 224 for loading data from and storing data to memory 230 ; and one or more vector-scalar units 226 for executing instructions that access vector and/or scalar operands. In a typical embodiment, each execution unit is implemented as a multi-stage pipeline, in which multiple instructions can be processed simultaneously at different execution stages. Each execution unit preferably includes at least one register file or is coupled to access at least one register file, the at least one register file including a plurality of physical registers for temporarily buffering operands accessed during or generated by instruction execution.

Those skilled in the art will appreciate that processor core 200 may include additional components not shown, such as logic configured to manage the completion and retirement of instructions targeted by the completion of execution of execution units 220 through 226. Because these additional components are not necessary for understanding the described embodiments, they are not shown in FIG. 2 or discussed further herein.

Referring now to FIG. 3 , a high-level block diagram of an exemplary execution unit of the processor 102 according to one embodiment is shown. In this example, the vector-scalar unit 226 of the processor core 200 is shown in greater detail. In the embodiment of FIG. 3 , the vector-scalar unit 226 is configured to perform operations on different types of operators and generate multiple different classes of instructions for different types of operators. For example, the vector-scalar unit 226 is configured to perform operations on vector and scalar source operators and generate a first class of instructions for vector and scalar destination operators. The vector-scalar unit 226 executes instructions of this first class of instructions in functional units 302-312 , which in the depicted embodiment include: an arithmetic logic unit/rotate unit 302 for performing addition, subtraction, and rotate operations, a multiplication unit 304 for performing binary multiplication, a division unit 306 for performing binary division, an encryption unit 308 for performing encryption functions, a permutation unit 310 for performing operand permutations, and a binary coded decimal (BCD) unit 312 for performing decimal math operations. The vector and scalar source operators on which these operations are performed, and the vector and scalar destination operators generated by these operations, are buffered in physical registers of the architectural register file 300 .

In this example, the vector-scalar unit 226 is additionally configured to execute instructions of a second class that cause hash functions to be executed. The vector-scalar unit 226 executes instructions of this second class in the accelerator unit 314. Operands on which these hash functions are executed and operands generated by these hash functions are buffered and accumulated in a wide vector register file 316 , which may include, for example, 1024-bit wide physical registers.

In operation, the vector-scalar unit 226 receives an instruction from the issue queue 218. If the instruction is in the first category of instructions (e.g., vector-scalar instructions), the associated source operands for the instruction are accessed in the architectural register file 300 using the mapping between logical registers and physical registers established by the mapper circuit 210 , and then transferred with the instruction to the associated one of the functional units 302 to 312 for execution. The destination operands generated by the execution are then stored back into the physical registers of the architectural register file 300 determined by the mapping established by the mapper circuit 210 . On the other hand, if the instruction is in the second category of instructions (eg, shuffle instructions), the instruction is forwarded to the accelerator unit 314 for execution with respect to the operands buffered in the specified registers of the wide vector register file 316 .

Referring now to FIG. 4 , a more detailed block diagram of the accelerator unit 314 of FIG. 3 is depicted according to one embodiment. The accelerator unit 314 includes circuitry for executing a variety of hash functions in hardware, including, for example, one or more hash functions defined by the SHA family of standards. In the depicted example, the hash circuitry of the accelerator unit 314 includes at least a SHA3/SHAKE hash circuit 400 as described in more detail below with reference to FIG. 11 and a SHA2 hash circuit 402 as described in more detail below with reference to FIG. 17 . The accelerator unit 314 further includes a single instruction multiple data (SIMD) exclusive OR (XOR) circuit 404 for use in performing SHA3/SHAKE hashing of messages, as discussed further below. Finally, the accelerator unit 314 includes a data transfer circuit 406 for transferring data (e.g., messages to be hashed and message digests) between a memory system (e.g., cache 106 and system memory 114 ) and a wide vector register file 316 .

Referring now to FIG. 5 , there is a time-space diagram of a process 500 for message hashing according to the SHA-3 standard. As is known in the art, the SHA-3 standard (i.e., FIPS 202) employs a sponge construction based on a wide random function or random permutation. According to this sponge construction, a message 502 of any arbitrary length (possibly many megabytes) is first processed in an input phase (referred to in sponge terminology as a SHA3 absorption phase 504 ). The SHA3 absorption phase 504 , described in more detail below with reference to FIG. 6 , is identical for both the SHA3 hash function and the SHAKE hash function. The SHA3 absorption phase 504 produces a 1600-bit final absorption state 610 , which is then processed in the output phase (referred to in sponge terminology as the SHA3/SHAKE squeeze phase 506 ) to generate a message digest 508. The SHA3/SHAKE squeeze phase 506 , described in detail below with reference to FIG. 8, operates differently for the SHA3 hash function and the SHAKE hash function. Specifically, the SHA3/SHAKE squeeze phase 506 generates a fixed-length message digest 508 for various SHA3 hash functions, but generates a variable-length message digest 508 for the SHAKE hash function.

Table I below summarizes the properties of the four SHA3 hash functions and two SHAKE hash functions defined by the SHA-3 standard and listed in the first row. In Table I, the second row summarizes the size in bits ( r ) of the message blocks into which the variable-length message 502 is subdivided by the SHA3 absorption phase 504. The message block size r is an integer multiple of the byte length, and the first message block of each message is byte-aligned. The third row of Table I summarizes the size in bits ( d ) of the message digest 508 output by the SHA3/SHAKE squeeze phase 506. Again, it should be noted that, unlike the SHA3 hash functions, SHAKE-128 and SHAKE-256 generate variable-length digests of length d' . As mentioned in the fourth row of Table I, for each hash function specified by the SHA-3 standard, the length of the final absorbed state 610 is 1600 bits. The fifth row of Table I specifies different values of c , i.e., the number of lower-order bits passed between iterations of the SHA3 state permutation function during the SHA3/SHAKE squeeze phase 506 (see, e.g., FIG. 8 ). Finally, the sixth row of Table I specifies that each iteration of the SHA3 state permutation function employs 24 rounds of permutations per message block (see, e.g., FIG. 7A ). In updates to the SHA-3 standard or in non-standard implementations, the number of permutation rounds may be varied, e.g., by reducing the number of permutations required (e.g., to 12).

Referring now to FIG. 6 , a time-space diagram of the SHA3 absorption phase 504 depicted in FIG. 5 is depicted. As shown, the SHA3 absorption phase 504 receives as input a message 502 of any arbitrary length. As shown at block 600 , the message 502 is padded to obtain a length that is an integer multiple of r bits. In many prior art implementations, this padding is accomplished via a potentially high-latency, computationally expensive memory-to-memory move of the entire message 502. In some other prior art implementations, the SHA hashing software routine pads the message block after loading the message block into a SIMD register using a learned SIMD instruction sequence. Although these prior art techniques may be used herein to perform padding, as described in detail below with reference to FIGS. 21A-27 , such padding may alternatively be efficiently performed by hardware in processor registers (e.g., wide vector register file 316 ) according to the disclosed invention by executing padding instructions. Padding message 502 by executing padding instructions also allows padding to be applied to the end of message 502 in a manner that overlaps in time with the processing of message blocks in SHA3 absorption phase 504 .

In the SHA3 absorption phase 504 , each of the n ( n is a positive integer) message blocks of length r that make up the padded message is extracted and then zero-extended in the trailing low-order bits to form n 1600-bit extended message blocks 602. The first message block, message block 1 602 , forms the input to the SHA3 state permutation function 604 defined by the SHA-3 standard. As described below with reference to FIGS. 9 and 11 , according to one aspect of the disclosed invention, the SHA3 state permutation function 604 is executed in hardware by executing a SHA3 hash instruction. The 1600-bit state output of the SHA3 state permutation function 604 forms the first input of the 1600-bit bit-by-bit XOR function 606 , which treats the next 1600-bit extended message block 602 of the padded message as the second input. The result of the bit-by-bit XOR function 606 forms the input of the next iteration of the SHA3 state permutation function 604. As shown, this process continues repeatedly for each of the message blocks 602 until the final iteration of the SHA3 state permutation function 604 generates and outputs the 1600-bit final absorbed state 610 , as previously mentioned in the description of FIG. 5 .

Referring now to FIG. 7A , a time-space diagram of the SHA3 permutation function 604 shown in FIG. 6 is shown. The SHA3 permutation function 604 accepts a 1600-bit input and then processes the 1600-bit input in conjunction with a SHA-3 standard specified round index 0 702 in the first of 24 rounds of the SHA3 round function 704. This process continues repeatedly, with each subsequent round of processing in the SHA3 round function 704 receiving as input the 1600-bit output of the previous SHA3 round function 704 and the associated SHA3 standard specified round index 702 (which is a constant). After the 24 rounds of processing within the SHA3 state permutation function 604 are completed, the SHA3 state permutation function 604 outputs a 1600-bit state, which serves as input to the bit-wise XOR function 606 , or in the case of the final iteration of the SHA3 state permutation function 604 within the SA3 absorption phase 504, constitutes the final absorption state 610 that serves as input to the SHA3/SHAKE squeeze phase 506 .

Referring now to FIG. 7B , a time-space diagram of the SHA3 round function 704 depicted in FIG. 7A is depicted. As shown, the SHA3 round function 704 includes a sequence of functions specified by the SHA-3 standard, including, in order, the five functions referred to in the SHA-3 standard by the Greek letters θ (theta), ρ (rho), π (pi), χ (chi), and ϊ (iota). The θ function receives and processes a 1600-bit input to the round function 704 , and the output of each of the other functions except the ϊ function is fed to the next sequential function. Finally, the ϊ function processes the output of the χ function and the associated round index 702 to produce a 1600-bit output for a given iteration of the SHA3 round function 704 . In the prior art, executing round function 704 using two single instruction multiple data (SIMD) vector pipelines may take up to 80 cycles. According to one aspect of the invention disclosed herein, round function 704 may be completed in a single cycle of processor core 104 using SHA3/SHAKE hash circuit 400 of FIG. 11 described below.

Referring now to FIG. 8 , a time-space diagram of the SHA3/SHAKE squeeze phase 506 shown in FIG. 5 is shown. As previously described, the SHA3/SHAKE squeeze phase 506 receives as input the 1600-bit final absorption state 610 generated by the SHA3 absorption phase 504. To generate a message digest 508 for use with any of the SHA3 functions defined by the SHA-3 standard, the SHA3/SHAKE squeeze phase 506 first extracts the r high-order bits before the final absorption state 610 to form a result block 1 800. The truncation function 802 then truncates r bits of the result block 1 800 to retain the high-order d bits that form the message digest 508 .

To generate a message digest for one of the SHAKE functions defined by the SHA-3 standard, the r bits of result block 1 800 form the r high-order bits of the input to a truncation function 804. These r high-order bits are concatenated with n -1 additional r- bit result blocks 800 , each of which is formed by the r high-order bits of the output of a repetition of the SHA3 state permutation function 604 as previously described with respect to FIG. 7A . Each SHA3 state permutation function 604 of the SHA3/SHAKE squeeze phase 506 receives a 1600-bit input (i.e., r + c = 1600) and generates a 1600-bit output that feeds subsequent iterations of the SHA3 state permutation function 604 except for the last iteration of the SHA3 state permutation function 604. The truncation function 804 truncates the r × n input bits to obtain a message digest 508 having a user-specified length d' bits.

9-10 , exemplary formats for a SHA3 hash instruction 900 and a bitwise exclusive OR (XOR) instruction 1000, respectively, are shown according to one embodiment. In one exemplary embodiment, the accelerator unit 314 is configured to utilize the SHA3/SHAKE hash circuit 400 to perform a SHA3/SHAKE state permutation function in hardware in response to receiving the SHA3 hash instruction 900 , and utilize the SIMD XOR circuit 404 to perform a 1024-bit bitwise XOR of a specified operand in response to receiving the bitwise XOR instruction 1000 .

In the illustrated embodiment, the SHA3 hash instruction 900 includes an opcode field 902 that specifies a specific architecture-specific opcode for the SHA3/SHAKE permutation function. The SHA3 hash instruction 900 further includes one or more register fields 904 , 906 that specify registers within the wide vector register file 316 for the source and destination operands of the SHA3/SHAKE state permutation function. For example, in one implementation, the SHA3 hash instruction 900 includes a single register field 904 that specifies the first of a pair of adjacent 1024-bit registers that buffer a 1600-bit source operand and, after the SHA3/SHAKE permutation function is completed, buffer a 1600-bit destination operand (which overwrites the source operand). In an alternative implementation, the SHA3 hash instruction 900 includes two register fields 904 , 906 that specify a separate pair of 1024-bit source and destination registers (in which case the destination operand does not overwrite the source operand).

As mentioned above, in future updates to the SHA-3 standard or in non-standard implementations, it may be desirable to control the number of permutations applied by the SHA3 state permutation function 604. In such embodiments, the SHA3 hash instruction 900 for the number of permutations may include directly setting the number of permutations or referencing a field of a register that specifies the number of permutations.

10 depicts an exemplary embodiment in which the bitwise XOR instruction includes an opcode field 1002 that specifies a specific architecture-specific opcode for a 1024-bit bitwise XOR function. The bitwise XOR instruction 1000 also includes three register fields 1004 , 1006 , and 1008 that are used to separately specify 1024-bit registers within the wide vector register file 316 for buffering two 1024-bit source operands and one 1024-bit destination operand.

Now that the SHA3 and SHAKE hash functions have been explained, as well as exemplary instructions for implementing portions of these hash functions, pseudocode for executing an exemplary SHA3 hash function in hardware is presented. In the following pseudocode, reference is made to the following registers:

Rr←block length in bytes

Rr且第一塊未被填充 RL←Message length in bytes //Assume RL

Rr and the first block is not filled

Ra←Starting address of the message

Rb←address of the message digest generated by the hash function

Rd←Message summary length in bytes

Xs←SHA3 state //Wide vector register pair

Xm←Message block //Wide vector register pair

Given these registers, the pseudonym for any of the SHA3 (not SHAKE) hash functions can be expressed as follows:

Xs=loadlength(Ra,Rr) //Load the first message block and initialize the status

Xs=sha3hash(Xs) //Execute SHA3 hashing command to perform substitution on the first message block

RL-=Rr //The length of the unprocessed part of the reciprocating message

Ra+=Rr //Increase to the pointer of the next message block in the message

While(RL>=Rr) //Enter the loop for processing each remaining message block, except the last message block of the message

{Xm=loadlength(Ra,Rr) //Load the next message block

Xs=wide_xor(Xs,Xm) //Execute bit-by-bit XOR instruction to combine the status and current message block

Xs=sha3hash(Xs) //Execute SHA3 hashing command to perform substitution on the current message block

RL-=Rr //The length of the unprocessed part of the reciprocating message

Ra+=Rr //Increase to the pointer of the next message block

}

Xm=loadlength(Ra,RL) //Load the last message block (if it exists) (RL can be zero)

Xm=sha3_padding(Xm,RL,sha3-type) //Execute padding instructions based on the remaining message length and SHA3 function to fill the message

Xs=wide_xor(Xs,Xm) //Execute bit-by-bit XOR instruction to combine the status and the last message block

Xs=sha3hash(Xs) //Execute SHA3 hashing instruction to perform substitution on the last message block and generate the final absorption state

Store_length(Xs,Rb,Rd) //In the SHA3 squeeze phase, truncate the last absorbed state to form a message digest by storing the leading Rd bytes of Xs to memory at address Rb

Referring now to FIG. 11 , a high-level block diagram of an exemplary SHA3/SHAKE hash circuit 400 suitable for executing a SHA3 hash instruction 900 is shown according to one embodiment. As shown, the SHA3/SHAKE hash circuit 400 includes two 1024-bit two-input multiplexers 1100 a , 1100 b , two 1024-bit state registers 1102 a, 1102 b , a SHA3 round circuit 1106 , and a control circuit 1110 that controls the operation of the SHA3/SHAKE hash circuit 400 in response to the SHA3 hash instruction 900 .

The input multiplexer 1100a has: a first input, which is coupled to receive the high-order 1024 bits of the 1600-bit input state from the first register of the register pair in the wide vector register file 316 identified by the SHA3 hash instruction 900 ; and a second input, which is coupled to receive the high-order 1024 bits of the 1600-bit round feedback from the SHA3 round circuit 1106 . Input multiplexer 1100b is similarly structured having a first input coupled to receive a 1024-bit value comprising the low-order 576 bits of a 1600-bit input state from a second register in a register pair specified by an instruction in wide vector register file 316 , and a second input coupled to SHA3 round circuit 1106 to receive a 1024-bit value comprising the low-order 576 bits of a 1600-bit round feedback. Control logic 1110 within the SHA3/SHAKE hash circuit 400 provides select signals, not shown, to the input multiplexers 1100a , 1100b to cause the input multiplexers 1100a , 1100b to select the value present at their first input prior to SHA3 round 0 and to select the value present at their second input after each of SHA3 rounds 0 through SHA3 rounds 23. The values output by the input multiplexers 1100a , 1100b, buffered in the state registers 1102a , 1102b, respectively, together form the 1600-bit round input value for the SHA3 round circuit 1106 , which is configured to perform the SHA3 round function 704 on the round input value, as previously described with reference to FIGS. 7A-7B .

The control circuit 1110 is further configured to sequence the SHA3 round circuit 1106 through each of the 24 rounds required by the SHA-3 standard using the correct round index specified by the SHA-3 standard. After the 23rd round is completed, the state registers 1102a , 1102b will respectively hold the high-order 1024 bits and low-order 576 bits of the 1600-bit output state. The control circuit 1110 is further configured to assert a select signal (not shown) once the output state is obtained, so that the output multiplexer 1108 writes the high-order bits and low-order bits of the 1600-bit output state from the state registers 1102a , 1102b to the instruction-specified register pair in the wide vector register file 316 in two consecutive cycles (assuming that the wide vector register file 316 has a single write port).

Referring now to FIG. 12 , a high-level logic flow chart of an exemplary process for executing the SHA3 hash instruction 900 according to one embodiment is depicted. For ease of understanding, the process of FIG. 12 is described with reference to the exemplary SHA3/SHAKE hash circuit 400 of FIG. 11 .

12 begins at block 1200 and then proceeds to block 1202 , which shows the SHA3/SHAKE hash circuit 400 receiving the SHA3 hash instruction 900 that specifies the operand register pair in the wide vector register file 316. In response to receiving the SHA3 hash instruction 900 , the control circuit 1110 causes the contents of the operand register pair to be read from the wide vector register file 316 and loaded into the state registers 1102a , 1102b via the input multiplexers 1100a , 1100b (block 1204 ). The control circuit 1110 also initializes the internal round counter to 0 (block 1206 ).

The process then continues from block 1206 to block 1208 , which shows that control circuit 1110 directs SHA3 round circuit 1106 to perform iterations of SHA3 round function 704 using round inputs buffered in state registers 1102a , 1102b and the appropriate round index specified by the SHA- 3 standard. Control circuit 1110 also increments the round counter (block 1208 ). The results of the processing by SHA3 round circuit 1106 are returned to state registers 1102a , 1102b by input multiplexers 1100a , 1100b . As indicated at block 1210 , control logic 1110 causes SHA3 round circuit 1106 to perform the 24 rounds of processing specified by the SHA-3 standard using the appropriate round index. When the 24 rounds of processing are completed, control circuit 1110 asserts the appropriate select signal to cause output multiplexer 1108 to store the 1600-bit state buffered in state registers 1102a , 1102b (zero-extended in the low-order bits to form two 1024-bit values) into the operand register pair within the wide vector register file 316 specified by the SHA3 hash instruction 900 (block 1214 ). Thereafter, the program of FIG. 12 ends at block 1216 .

Referring now to FIG. 13 , a time-space diagram of message hashing according to the SHA-2 standard (FIPS 180-4) is shown, which is performed by the SHA2 hashing circuit 402 in the embodiment of FIG. 4 . The following Table II summarizes the properties of the six SHA2 hashing functions defined by the SHA-2 standard and listed in the first row. In Table II, the second row summarizes the message block size ( r ) in bits. The message block size r is an integer multiple of the byte length, and the first message block of the message is byte aligned. The third row of Table II summarizes the fixed size ( d ) in bits of the message digest generated by each SHA2 hashing function. The fourth row of Table II specifies the size in bits of the state of each SHA2 hash function, and the fifth row of Table II indicates the number of rounds of processing employed in each SHA2 hash function (i.e., 64 or 80) (see, e.g., FIG. 14 ). Finally, the sixth row of Table II specifies the word size in bits used for each SHA2 hash function. It should be noted that for all variants, the state size is 8 times the word size (i.e., contains 8 words), and the size of the message block is 16 times the word size (i.e., contains 16 words). As described below, according to one aspect of the disclosed invention, a SHA2 hash function using a 32-bit word size and a SHA2 hash function using a 64-bit word size are processed along the same data stream by message extension of words applied to SHA2-224 and SHA2-256 hash functions, as described below with reference to FIG. 15 .

Table II

As shown in FIG13 , the SHA2 hash function 1300 receives as one input a message 1302 of any arbitrary length (e.g., the length may be millions of bytes). As shown at block 1304 , the message 1302 is padded to obtain a length that is an integer multiple of r bits. As discussed above with reference to FIG6 , this padding can be efficiently performed by hardware in processor registers (e.g., wide vector register file 316 ) rather than by executing a pad instruction to perform a memory move. Message 1302 is padded by executing a padding instruction, and in particular the last message block of message 1302 , which also allows padding to be applied to the end of message 1302 in a manner that overlaps in time with the processing of the message blocks by SHA2 hash function 1300. Each of the n ( n is a positive integer) message blocks of length r (where r = 16× w ) that make up the padded message generated by block 1304 is extracted to form one of the n 16× w bit message blocks 1306 .

In addition to the message 1302 , the SHA2 hash function 1300 also receives as input an 8× w bit SHA-2 specified constant value. As is known in the art, this constant value, which can be accessed from the architectural register file 300 , varies between SHA2 hash functions and forms an 8× w bit initial state 1308. The initial state 1308 and the first message block (i.e., message block 1 1306 ) form two inputs to the SHA2 block hash function 1 1310 defined by the SHA-2 standard. As described below with reference to FIGS. 16 and 17 , according to one aspect of the disclosed invention, the SHA2 block hash function 1310 is executed in hardware by executing a SHA2 hash instruction. The 8× w bit state output by SHA2 block hash function 1 1310 forms the first input of SHA2 block hash function 2 1310 , which treats the next 16× w bit message block 2 1306 as the second input. The result of SHA2 block hash function 2 1310 forms the next repeated input of SHA2 block hash function 1310 . As shown, this process continues repeatedly for each of the message blocks 602 until the final n- th iteration of the SHA2 block hash function 1310 generates and outputs an 8× w - bit final state, which is truncated by the truncation function 1312 to produce a message digest 1314 having d bits.

Referring now to FIG. 14 , a time-space diagram of the SHA2 block hash function 1310 shown in FIG. 13 is depicted. The SHA2 block hash function 1310 accepts a 16× w bit message block 1306 and, as shown at block 1420 , initializes a 16× w bit message schedule for the message block 1306. The SHA2 block hash function 1310 then processes the 16× w bit message schedule through n rounds of processing in a message schedule round function 1400 , where the 16× w bit output of each of rounds 1 to n-2 serves as input to the next round of message schedule processing.

As shown, the SHA2 block hash function 1310 also receives as input an 8× w bit current hash state (i.e., the initial state 1308 or the output of the previous SHA2 block hash function 1310 ). The SHA2 block hash function 1310 splits this 8× w bit current hash state into 8w bit variables a to h as indicated at block 1406. The SHA2 block hash function 1310 then processes the current hash state by updating the round function 1404 through n rounds of processing. Initial update round 0 1404 takes as additional inputs the w- bit SHA-2 specified round key 0 1402 and the w high-order bits of the 16× w-bit message scheduling initialization 1420. Each successive iteration of update round function 1404 takes as input the state generated by the previous iteration of update round function 1404, the w high - order bits of the 16× w -bit output of the corresponding iteration of message scheduling round function 1400 , and the w- bit SHA-2 specified round key 1402. The hash state output by update round function n -1 1404 is added to the input hash state by the 8× w -bit carry propagation addition function 1410 to generate the next hash state.

Referring now to FIG. 15 , a message expansion for a SHA2 hash function according to an exemplary embodiment is illustrated. As mentioned above with reference to Table II and FIG. 13 , embodiments of the present invention preferably support processing of SHA2 hash functions of different word sizes w along a common data path by expanding the message words and initial hash states of those SHA2 hash functions that employ smaller word sizes. This expansion may be performed, for example, at blocks 1304 and 1308 of FIG. 13 . 15 illustrates a specific example in which each of the sixteen 32-bit words 1502 of a SHA2-224 or SHA2-256 input message 1500 is expanded to form a corresponding one of the sixteen 64-bit double words 1506 of an output message 1504. In this example, each 64-bit double word 1506 is formed by concatenating the 32-bit word of the input message 1500 in the high-order half of the 64-bit double word 1506 with the 32-bit zero word 1508 in the low-order half of the double word 1506. The resulting output message 1504 can then be processed by the SHA2 hash circuit in the same manner as a message using 64-bit words.

16 , an exemplary format for a SHA2 hash instruction 1600 according to one embodiment is depicted. In one exemplary embodiment, the accelerator unit 314 is configured to execute the SHA2 block hash function 1310 in hardware using the SHA2 hash circuit 402 in response to receiving the SHA2 hash instruction 1600 .

In the illustrated embodiment, the SHA2 hash instruction 1600 includes an opcode field 1602 that specifies a specific architecture-specific opcode for the SHA2 block hash function. The SHA2 hash instruction 1600 further includes one or more operand register fields 1604 , 1606 that specify operand registers within the wide vector register file 316 for source and destination operands of the SHA2 block hash function. For example, in one implementation, the SHA2 hash instruction 1600 includes a register field 1604 that specifies a 1024-bit register that buffers the current hash state of the input and buffers the current hash state of the output after the SHA2 block hash function is completed (which overwrites the input current hash state). In addition, the SHA2 hash instruction 1600 includes a register field 1606 that buffers the current message block to be processed. The SHA2 hash instruction 1600 further includes a mode field 1608 that indicates whether the SHA2 hash function to be performed uses 32-bit words or 64-bit words.

Now that the SHA2 hash function and exemplary instructions for implementing portions of the SHA2 hash function have been explained, a pseudocode for executing an exemplary SHA2 hash function (i.e., SHA2-512) in hardware is presented. In the SHA2-512 hash function, each message block is 1024 bits long, and the hash state and message digest are each 512 bits long. In the following pseudocode, the following registers are referenced:

Rl←Message length in bits

128個位元組，因此第一訊息塊未被填充 RL←Message length in bytes; assuming

128 bytes, so the first message block is not filled

Ra←Starting address of the message

Ri←address of initial state

Rb←address of the message digest generated by the hash function

Rd←Message summary length in bytes

Xs←SHA2 status //Wide vector register

Xm←Current message block //Wide vector register

Given these registers, the pseudo code for executing the SHA2-512 hash function can be expressed as follows:

Xs=load(Ri,64) //Load the initial state of 64 bytes

Xm=load(Ra,128) //Load the first (complete) message block

Xs=sha2hash(Xs,Xm,64-bit) //Execute SHA2 hashing instruction to execute block hashing function

RL-=128 //Decrease the length of the message to be processed

Ra+=128 //Advance pointer to the next message block

While(RL>=128) //Through the remaining message block loop, except for the last message block

{Xm=load(Ra,128) //Load the next message block (full size)

Xs=sha2hash(Xs,Xm,64-bit) //Execute SHA2 hashing instruction to execute block hashing function

RL-=128 //Decrease the length of the message to be processed

Ra+=128 //Advance pointer to the next message block

}

Xm=1oadlength(Ra,RL) //Load the last message block (if it exists) (RL can be zero)

Xm=sha2_EOM_pad(Xm,RL) //Append the SHA2 EOM byte to the end of the message block

If(RL>111)then //If the filling spans two message blocks, then

{Xs=sha2hash(Xs,Xm,64-bit) //Execute SHA2 hashing instruction to execute the block

Xm=force-to-zero //Hash function and set the last message block to zero

}

Xm=sha2_EOB_pad(Xm,RI) //Insert EOB into the last block of the padded message

Xs=sha2hash(Xs,Xm,64-bit) //Execute SHA2 hashing instruction to perform block hashing function on the last message block

Store(Xs,Rb,64) //Truncate the state to the leading 64 bytes of Xs to obtain the message digest and store it to memory at address Rb

Referring now to FIG. 17 , a high-level block diagram of an exemplary embodiment of the SHA2 hash circuit 402 of FIG. 4 suitable for executing the SHA2 hash instruction 1600 is shown. As shown, the SHA2 hash circuit 402 includes a 512-bit dual-input state multiplexer 1702 a , a 1024-bit dual-input message multiplexer 1702 b , a 512-bit state register 1704 a , a 1024-bit message block register 1704 b , an update work status circuit 1708 , a message scheduling round circuit 1710 , and a control circuit 1720 that controls the operation of the SHA2 hash circuit 402 in response to the SHA2 hash instruction 1600 .

In this example, a first input of state multiplexer 1702a is coupled to receive the current hash state held in the 512 high-order bits of the register specified by register field 1604 of SHA2 hash instruction 1600 in width vector register file 316. A second input of state multiplexer 1702a is coupled to the output of update working state circuit 1708 . Message multiplexer 1702b is similarly configured, having: a first input coupled to receive a message block from a register specified by register field 1606 of SHA2 hash instruction 1600 in width vector register file 316 ; and a second input coupled to receive a 1024-bit round feedback from message scheduling round circuit 1710 . The control logic 1720 within the SHA2 hash circuit 400 provides a select signal (not shown) to the multiplexers 1702a , 1702b to cause the multiplexers 1702a , 1702b to select the value present at the first input before the update round 0 function 1404 , and to select the value present at the second input after each of the update round 0 function to the SHA2 block hash n function. The values output by the multiplexers 1702a , 1702b are temporarily buffered in the state register 1704a and the message block register 1704b, respectively. The message blocks buffered in the message block register 1704b form the inputs of the message scheduling round circuit 1710 , which implements the message scheduling round function 1400 of FIG. 14. The 64 high-order bits from the message block register 1704b and the 512-bit state in the state register 1704a form the two inputs of the update work state circuit 1708 , which is configured to execute the update round function 1404 as previously described with reference to FIG. 14 .

The control circuit 1720 is further configured to sequence the update of the working state circuit 1708 through each of the n rounds using the correct round index specified by the SHA-2 standard. After the last round n -1 is completed, the state register 1704a will hold a 512-bit hash state. The control circuit 1720 is further configured to cause the single instruction multiple data (SIMD) adder 1712 to add the hash state from the state register 1704a to the input hash state read from the wide vector register field 316 once the output hash state is obtained, and store the result back to the wide vector register file 316 as the next hash state, as described above with respect to the addition function 1410 of Figure 14. Those skilled in the art will appreciate that in different implementations, the SIMD adder 1712 may be implemented as a dedicated component of the SHA2 hash circuit 402 or as a separate pipeline that may be shared by multiple hash circuits, for example.

Referring now to FIG. 18 , a more detailed block diagram of the exemplary update operating state circuit 1708 from FIG. 17 is depicted according to one embodiment. In this embodiment, the 512-bit state received as one input to the update operating state circuit 1708 , buffered in the state register 1704 a , is split into eight 64-bit variables, referred to as variables a through h in the SHA-2 standard, as shown at block 1800 . The update working state circuit 1708 includes: two sigma function circuits, namely SHA2 sigma 0 circuit 1802 and SHA2 sigma 1 circuit 1806 , and SHA2 MA circuit 1804 and SHA2 CH circuit 1808 , each of which performs a respective function defined by the SHA-2 standard. The update working state circuit 1708 also includes three 64-bit adders 1810 , 1812 and 1814. SHA2 sigma 0 circuit 1802 applies a sigma function with n (n1, n2, n3) = (28, 34, 39) and m (m1, m2, m3) = (2, 13, 22) to variable a to generate a first input of adder 1812 . Variables a , b, and c are processed by SHA2 MA circuit 1804 to generate the second input of adder 1812. SHA2 Sigma 1 circuit 1806 applies a sigma function with n (n1, n2, n3) = (14, 18, 41) and m (m1, m2, m3) = (6, 13, 22) to variable e to generate the first input of the five inputs of adder 1810. Variables e , f, and g are processed by SHA2 CH circuit 1808 to generate the second input of adder 1810. Adder 1810 adds the associated round key, round message block, and variable d to these two inputs to generate a sum that forms the first input of adder 1814 and the third input of adder 1812 .

Update working state circuit 1708 generates a 512-bit result state 1816 consisting of eight 64-bit variables a' to h' . Variable a' of result state 1816 is formed by the output of adder 1812 , variables b' , c' and d' are formed by variables a , b and c of input state 1800 , and variables f' , g' and h' are formed by variables e , f and g of input state 1800. Residual variable e' is formed by the sum of the output of adder 1810 and variable d of input state 1800 .

It should be noted that the 32-bit to 64-bit expansion of the SHA-2 message word described above with reference to FIG15 does not affect (is transparent to) the design of the SHA2 MA circuit 1804 , the SHA2 CH circuit 1808 , and the modular adders 1812 , 1814. The trailing zero expansion of the SHA2 message using 32-bit words only affects the SHA2 sigma circuits 1802 , 1806 , as described in more detail below with reference to FIG19 .

19 is a more detailed block diagram of an exemplary embodiment of a SHA2 Sigma circuit 1900 , which may be used to implement the SHA2 Sigma 0 circuit 1802 and the SHA2 Sigma 1 circuit 1806 of FIG 18. The SHA2 Sigma circuit 1900 receives a 64-bit input variable 1902 including 32 high-order bits (bits 0 to 31) and 32 low-order bits (bits 32 to 63).

SHA2 Sigma circuit 1900 includes a 64-bit rotate circuit 1904a that rotates the 64-bit input variable 1902 by n1 bits (i.e., 28 bits for SHA2 Sigma 0 circuit 1802 and 14 bits for SHA2 Sigma 1 circuit 1806 ) to obtain a first 64-bit input to multiplexer 1910a . SHA2 sigma circuit 1900 further includes a 32-bit rotate circuit 1906a that rotates the 32 high-order bits of input variable 1902 by m1 bits (i.e., 2 bits for SHA2 sigma 0 circuit 1802 and 6 bits for SHA2 sigma 1 circuit 1806 ) to obtain a second 64-bit input to multiplexer 1910a when concatenated with the 32 low-order bits of input variable 1902. Multiplexer 1910a selects between its first and second inputs based on a mode signal determined by mode field 1608 of the associated SHA2 hash instruction 1600 . That is, if the mode signal indicates that the mode field 1608 is set to indicate the SHA2 hash function using 64-bit words, the multiplexer 1910a selects the first input, and if the mode signal indicates that the mode field 1608 is set to indicate the SHA2 hash function using 32-bit words, the multiplexer 1910a selects the second input.

SHA2 Sigma circuit 1900 further includes a 64-bit rotate circuit 1904b that rotates the 64-bit input variable 1902 by n2 bits (i.e., 34 bits for SHA2 Sigma 0 circuit 1802 and 18 bits for SHA2 Sigma 1 circuit 1806 ) to obtain a first 64-bit input to multiplexer 1910b . SHA2 Sigma circuit 1900 also includes a 32-bit rotate circuit 1906b that rotates the 32 high-order bits of input variable 1902 by m2 bits (i.e., 13 bits for both SHA2 Sigma 0 circuit 1802 and SHA2 Sigma 1 circuit 1806 ) to obtain a second 64-bit input to multiplexer 1910b when connected in series with the 32 low-order bits of input variable 1902. Multiplexer 1910b selects between its first and second inputs based on the mode signal. Specifically, if the mode signal indicates that the mode field 1608 is set to indicate the SHA2 hash function using 64-bit words, the multiplexer 1910b selects the first input, and if the mode signal indicates that the mode field 1608 is set to indicate the SHA2 hash function using 32-bit words, the multiplexer 1910b selects the second input.

SHA2 Sigma circuit 1900 also includes a 64-bit rotate/shift circuit 1908a that rotates and shifts the 64-bit input variable by n3 bits (i.e., 39 bits for SHA2 Sigma 0 circuit 1802 and 41 bits for SHA2 Sigma 1 circuit 1806 ) to obtain a first 64-bit input to multiplexer 1910c . SHA2 Sigma circuit 1900 additionally includes a 32-bit rotate/shift circuit 1908b that rotates and shifts the 32 high-order bits of input variable 1902 by m3 bits (i.e., 22 bits for both SHA2 Sigma 0 circuit 1802 and SHA2 Sigma 1 circuit 1806 ) to obtain a second 64-bit input to multiplexer 1910c when concatenated with the 32 low-order bits of input variable 1902. Multiplexer 1910c selects between its first and second inputs based on the mode signal. As with multiplexers 1910a , 1910b , multiplexer 1910c selects the first input if the mode signal indicates that mode field 1608 is set to indicate a SHA2 hash function using 64-bit words, and multiplexer 1910c selects the second input if the mode signal indicates that mode field 1608 is set to indicate a SHA2 hash function using 32-bit words.

The 64-bit outputs of multiplexers 1910a , 1910b , and 1910c form the inputs of a three-input 64-bit bit-by-bit XOR circuit 1912 , which performs a bit-by-bit XOR on its three inputs to generate a 64-bit output 1914 . Those skilled in the art will appreciate that in some embodiments of the SHA2 sigma circuit 1900 , the functionality of the rotation circuits 1904a to 1904b and 1906a to 1906b and the rotation/shift circuits 1908a to 1908b may be implemented by appropriate routing, thereby allowing the SHA2 sigma circuit 1900 to be implemented by three multiplexers 1910a to 1910c and a 3-way bitwise XOR circuit 1912 without the need for explicit rotation and shift circuitry.

Referring now to FIG. 20 , a high-level logic flow chart of an exemplary process for executing the SHA2 hash instruction 1600 according to one embodiment is depicted. For ease of understanding, the process of FIG. 20 is described with reference to the exemplary embodiment of the SHA2 hash circuit 402 depicted in FIGS. 17 to 19 .

The process of Figure 20 begins at block 2000 and then continues to block 2002 , which shows the SHA2 hash circuit 402 receiving the SHA2 hash instruction 1600 specifying a particular SHA2 mode (i.e., 32-bit or 64- bit word size) and the state registers and message block registers in the wide vector register file 316 . In response to receiving the SHA2 hash instruction 1600 , the control circuit 1720 causes the 512-bit state and 1024-bit message blocks to be read from the width vector register file 316 and load them into the state register 1704a and the message block register 1704b via multiplexers 1702a and 1702b , respectively (block 2002 ). The control circuit 1720 also initializes the internal round counter to 0 (block 2004 ).

The program then continues from block 2004 to block 2006 , which shows that control circuit 1720 directs message scheduling round circuit 1710 to execute iterations of message scheduling round function 1400 using the message blocks buffered in message block register 1704b . In addition, control circuit 1720 directs update work status circuit 1708 to execute iterations of update round function 1404 based on the appropriate round index, the 64 high-order bits of message block register 1704b , and the input hash state from status register 1704a . The processing results of the update working state circuit 1708 and the message scheduling round circuit 1710 are returned to the registers 1704a and 1704b by the multiplexers 1702a and 1702b respectively. The control circuit 1110 also advances the round counter. At block 2010 , the control logic 1720 determines whether the SHA2 hash circuit 402 has executed the last round of processing specified by the SHA-2 standard by referring to the round counter. As mentioned in Table II, the SHA2 hash circuit 402 executes 64 rounds of processing for the SHA2 hash function using 32-bit words, and executes 80 rounds of processing for the SHA2 hash function using 64-bit words. If the control circuit 1720 determines at block 2010 that there is still at least one additional round of processing to be performed, the program returns to block 2006 , which has been described. However, in response to determining at block 2010 that all rounds of processing are complete, the control circuit 1720 causes the previous state to be read again from the wide vector register file 316 and added to the final state buffered in the state register 1704a by the SIMD adder 1712 (block 2012 ). The control circuit 1720 then directs the storage of the resulting next state back to the wide vector register file 316 (block 2014 ). Thereafter, the program of Figure 20 ends at block 2016 .

As discussed above with reference to block 600 of FIG. 6 and block 1304 of FIG. 13 , messages processed by SHA2 and SHA3 hash functions are padded to produce messages whose length is an even multiple of the block length r bits. FIG. 21A depicts an exemplary unpadded message 2100 having a total length of L bits and including n message blocks. Among them, the first n -1 message blocks include r bits, but the final message block n includes k bits, where k < r . As shown in FIG. 21B , in general, message 2100 is padded by appending rk padding bits to the end of message block n , thereby producing n message blocks each having a length of r bits.

The content of the padding bits appended to obtain a padded message may vary depending on the hash function under consideration. For example, in the SHA2 and SHA3/SHAKE hashing algorithms discussed herein, the padding bits will include bytes marking both the end of the unpadded portion of the message (i.e., the end-of-message (EOM) marker) and the end of the last block of padded messages (i.e., the end-of-block (EOB) marker). As further explained below, in some cases, the padding bits including the EOM and EOB markers may all be included in the message block containing the final message bytes; in other cases, the addition of padding bits may require appending an additional message block to the message. In either case, the disclosed invention preferably performs message filling in a processor register by executing one or more instructions rather than by a high latency memory move operation that transfers a message between two locations in memory.

In at least some architectures, the load storage unit 224 , the memory controller 112 , and/or the system interconnect 110 are not configured to support data transfer of lengthy data objects (e.g., complete r- bit SHA3/SHAKE and SHA2 message blocks) between the system memory 114 and the wide vector register file 116. In such architectures, the message blocks are transferred in multiple smaller chunks to a narrower register file, and then transferred from the narrower register file to one or more wide vector registers in the wide vector register file 316 . 22A shows an example of assembling SHA3/SHAKE message block n into an architected register file 300 including 256-bit registers r0 to r7 301. In this example, a load length instruction is executed, for example, by the load storage unit 224 of FIG. 2 to load five 256-byte blocks of the 1152-bit SHA3-224 message block n into registers r0 to r7 and any register bytes that do not contain message data are set to zero. Given a message block length of 1152 bits in SHA3-224, the message bytes in message block n will at most completely fill registers r0 to r3 plus the leading 128 bits of register r4 (of course, the final message block without padding may contain fewer than r bits). At least the remaining 128 bits of register r4 and all of registers r5 to r7 are zeroed, either automatically or by executing a load length instruction. (Registers r6 and r7 need only be zeroed for the generic SHA3 function for any of the supported message block lengths). Additional data transfer instructions may then be executed by data transfer circuit 406 or transfer unit 320 to transfer the contents of registers r0 to r7 to registers R0 and R1 317 of wide vector register file 316 , which includes registers R0 to RT each having an exemplary width of 1024 bits as discussed above. In an alternative implementation, the same result may be achieved by loading four registers 301 within architected register file 300 to buffer blocks n1 to n4 and then reusing the same registers 301 on a subsequent cycle to buffer blocks n5 to n8.

22B depicts a similar example showing the 1024-bit SHA2 message block n being transferred to wide vector register 317 in wide vector register file 316 after the message blocks are assembled in register 301 of architectural register file 300. In this example, a load length instruction is executed, for example by load storage unit 224 of FIG. 2 , to load four 256-byte blocks of SHA2 message block n into registers r2 through r5 of architectural register file 300 and any register bytes that do not contain message data are set to zero. Additional data transfer instructions may then be executed by data transfer circuit 406 to transfer the contents of registers r2-r5 to register R0 317 of wide vector register file 316. In an alternative implementation, the same result may be achieved by loading two registers 301 within architected register file 300 to buffer blocks n1 and n2 and then reusing the same registers 301 on a subsequent loop to buffer blocks n3-n4.

In at least some preferred embodiments, a procedure for loading message blocks into the wide vector register file 316 shown in Figures 22A to 22B is performed for all message blocks of the SHA3/SHAKE or SHA2 message, including message block n , which is the last message block that is not filled with messages. As explained below, the end of the message can then be filled at least partially in the wide vector register file 316 by executing one or more instructions.

Figures 23A to 23D depict various padding conditions for SHA3/SHAKE messages of various lengths. According to the SHA-3 standard, each message must include EOM padding that marks EOM. Under the SHA3 standard, EOM padding has a fixed value of x06 for the SHA3 hash function and a fixed value of x1F for the SHAKE hash function. The location of the EOM padding within the padded message varies depending on the message length, which is often unknown at compile time. The SHA-3 standard further mandates that the last byte of each padded message be a fixed value EOB padding byte.

As shown in FIG. 23A , if the last message block 2300 of the SHA3/SHAKE message includes more than two bytes that do not contain message data, the EOM pad byte 2302 is inserted into the zero byte of the associated wide vector register 317 immediately following the last message byte 2306 , and the EOB pad byte 2304 is inserted into the set byte of the wide vector register 317 as the last byte of the padded message block.

23B shows a similar second situation, where the last message block 2300' of the SHA3/SHAKE message includes exactly two zero bytes that do not contain message data. In this situation, the last two zero bytes of the last message block 2300' are replaced with EOM padding bytes 2302 , followed by EOB padding bytes 2304 .

23C depicts a third situation in which the last message block 2300" of the SHA3/SHAKE message includes only a single zeroed message byte following the last message byte 2306. In this situation, execution of the padding instruction as described below causes the EOM and EOB padding values to be OR'ed together and inserted into the last byte of the padded message block 2300" as the EOM/EOB padding byte 2308 .

23D shows the final situation, where the last message byte 2306 of the SHA3/SHAKE message is the last byte of the message block 2310. Because the message block 2310 does not include the capacity for the required EOM and EOB padding in this situation, an additional zeroed message block 2312 is appended to the message (e.g., by executing a load length instruction). The EOM padding byte 2302 is inserted as the first byte into this zeroed message block 2312 , and the EOB padding byte 2304 is inserted as the last byte into this zeroed message block 2312 . It should be noted that in each of the four cases depicted in Figures 23A to 23D , both EOM padding and EOB padding can be advantageously applied by a single padding instruction since both EOM padding and EOB padding always belong to the same message block. It should also be understood that although Figures 23A to 23D depict padding being applied to messages that include an integer number of message bytes, padding can be similarly applied to byte messages that do not include an integer number of bytes.

In one embodiment, three instructions may be used to implement padding of SHA3/SHAKE messages of arbitrary length as shown in Figures 23A to 23D . These instructions include: (1) a load length instruction that stages the final message block of the padded message into a specified register 301 in the architectural register file 300 ; (2) a transfer instruction that transfers the message block from register 301 in the architectural register file 300 to one or more wide vector registers 317 in the wide vector register file 316 as shown in Figure 22A ; and (3) a fill instruction that inserts EOM and EOB padding at the appropriate byte positions in the final message block of the padded SHA3/SHAKE message held in the wide vector register 317 . Of course, in an alternative implementation, it is possible to insert EOM padding and EOB padding into the final message block using two different instructions. However, for single-block messages such as those commonly used in post-quantum encryption schemes, adding additional padding instructions increases latency and undesirably reduces hashing performance.

Figures 24A to 24D depict various padding conditions for SHA2 messages of various lengths. According to the SHA-2 standard, each message must include an EOM padding byte having a value of x80 in the byte immediately following the last message byte. The position of the EOM padding byte within the padded message therefore varies depending on the message length. The SHA-2 standard further mandates that the last two words (i.e., two 32-bit words or two 64-bit words, depending on the SHA2 hash function in question (see Table II)) contain EOB padding specifying the length of the unpadded message in bits.

In the first case shown in Figure 24A , the last message block 2400 of the SHA2 message includes more than two words plus one byte that do not contain message data. In this case, the last message block 2400 is filled by inserting an EOM fill byte 2402 into the zero byte of the associated width vector register 317 immediately after the last message byte 2406 and by inserting two EOB fill words 2404 as the last two words of the last message block 2400 .

24B illustrates a similar second situation, where the last message block 2400′ of the SHA2 message includes exactly two words plus one byte that do not contain message data. In this situation, the last message block 2400′ is filled by inserting an EOM fill byte 2402 into the zero byte of the associated width vector register 317 immediately after the last message byte 2406 and inserting two EOB fill words 2404 as the last two words of the last message block 2400 .

Figure 24C depicts a third case, in which the last message block 2400" of the unfilled SHA2 message includes too few bytes containing no message data to accommodate the EOM fill byte 2402 and the two EOB fill words 2404. In this case, the SHA2 message is filled by inserting the EOM fill byte 2402 into the zero bytes of the associated wide vector register 317 immediately after the last message byte 2406. Because the EOB fill word 2404 does not fit within the message block 2400" , an additional zero message block 2408 is appended to the message (e.g., by executing a load length instruction). The EOB fill word 2404 is then inserted as the last two words of the message block 2408 .

24D shows a fourth case, where the last message byte 2406 of the SHA2 message forms the last byte of a complete message block 2410. Because the message block 2410 does not include space for EOM or EOB padding, an additional zeroed message block 2412 is appended to the SHA2 message. The additional message block 2412 includes the EOM padding byte 2402 as the first byte of the message block 2412 , followed by a number of zeroed bytes, and finally two EOB padding words 2404 at the end of the message block 2412 .

In one embodiment, padding of SHA2 messages of arbitrary length can be accomplished using as few as four instructions. These instructions include: (1) a load length instruction that places the final message block of the SHA2 message in a specified register 301 in the architectural register file 300 and sets any register bytes that do not contain message bytes to zero; (2) an insert word instruction that places two EOB fill words 2404 in the appropriate bytes of register 301 in the architectural register file 300 to mark the end of the filled message; (3) a transfer instruction that transfers the contents of register 301 of the buffered message block from the architectural register file 300 to wide vector register 317 in the wide vector register file 316 . and (4) a fill instruction that inserts EOM fill bytes 2402 into the appropriate location in wide vector register 317. In this embodiment, execution of the fill instruction inserts EOM fill bytes 2402 instead of EOB fill words 2404 because (1) EOM fill bytes 2402 and EOB fill words 2404 may be located in different message blocks, and (2) EOB fill words 2404 may be efficiently located in the appropriate register 301 in architected register file 300 using existing insert word instructions. Of course, in an alternative embodiment, both EOM fill bytes 2402 and EOB fill words 2404 may be applied to the SHA2 message block in register 301 of architected register file 300 .

Referring now to FIG. 25 , an exemplary fill instruction 2500 is illustrated according to one embodiment. In at least one embodiment, the exemplary fill instruction 2500 may be executed by the accelerator unit 314 within the data transfer circuit 406 to perform fill for both SHA3/SHAKE message blocks and SHA2 message blocks.

In the illustrated example, the fill instruction 2500 includes an operation code field 2502 that specifies an architecture specific operation code for the message fill instruction. The fill instruction further includes two register fields 2504 , 2506 that specify the storage locations of the source and destination operands of the fill operation. For example, the register 1 field 2504 may identify the destination wide vector register 317 in the wide vector register file 316 that buffers the message block to be filled, and the register 2 field 2506 may specify the register 301 in the architecture register file 300 that holds the remaining message length in bytes.

The fill instruction 2500 further includes a mode field 2508 that provides information for filling the message. In an exemplary embodiment, the mode field 2508 includes at least three subfields, including a hash identifier (HID) subfield 2510 , a block length (BL) subfield 2512 , and an extension (E) subfield 2514. The HID subfield 2510 indicates the type of hash function applied to the message block. For example, in one implementation, the HID subfield 2510 may include two bits that specify one of the following hash types: SHA3, SHAKE, SHA2 (64-bit word), and SHA2 (32-bit word). BL subfield 2512 indicates (possibly when interpreted together with HID subfield 2510 ) the length of the message block in bytes. E subfield 2514 indicates whether the width vector register 317 specified by register 1 field 2504 holds the leading segment S0 or the trailing segment S1 of the message block. For example, in one embodiment where the wide vector register 317 is 1024 bits wide, if the wide vector register 317 specified by the register 1 field 2504 does not hold a trailing segment of a message block, then the E subfield 2514 may have a value of b0, and if the wide vector register 317 is specified to hold a trailing segment of a message block, then the E subfield 2514 may have a value of b1. Of course, in other embodiments where the wide vector register 317 has a different width (e.g., 512 bits), the E subfield 2514 may include additional bits to specify additional register segments.

Referring now to FIG. 26 , an exemplary fill circuit 2600 is shown according to one embodiment. The fill circuit 2600 , which may be implemented as part of the data transfer circuit 406 of the accelerator unit 314 , for example, fills the message segment S1 held in the target wide vector register in response to the execution of the fill instruction 2500 as shown in FIG. 25 . The illustrated example assumes that the wide vector register file 316 has 1024-bit wide vector registers 317 .

In this exemplary embodiment, fill circuit 2600 includes select EOM circuit 2602 , which selects the value of EOM fill byte 2302 or 2402 (i.e., eom_byte) based on the hash function specified by HID subfield 2510 of fill instruction 2500. Fill circuit 2600 also includes select EOB circuit 2604 , which selects the value of the EOB fill byte (i.e., eob_byte) to be inserted by fill instruction 2500 based on HID subfield 2510 in a similar manner. In the described embodiment, for the SHA3/SHAKE hash function, the select EOB circuit 2604 selects a fixed eob_byte value specified by the SHA-3 standard, which is contained in the register indicated by register 2 field 2506. For the SHA2 hash function, the select EOB circuit 2604 selects a zero eob_byte because the EOB fill word 2404 is inserted by a separate instruction in this embodiment. The fill circuit 2600 further includes a select BL size circuit 2606 that selects and outputs an 8-bit block length value based on the HID field 2510 and the BL field 2512 of the fill instruction 2500 .

The 8-bit block length value output by the select BL size circuit 2606 is received by the EOB enable circuit 2608 , which includes a comparator 2610 , a decoder 2612 , and a bitwise AND circuit 2614. The high-order bit of the 8-bit block length value indicates whether the length of the message block exceeds the width of the 1024-bit wide vector register 317 (as would be the case, for example, for SHA3-224, SHAKE-128, and SHAKE 256). The low-order 7 bits of the block length form the block length size (bl_size), which indicates the number of bytes contained in the segment of the message block buffered in the target width vector register 317 identified by register 1 field 2504. The decoder 2612 decodes the 7-bit bl_size value to obtain a 128-bit representation of the position of the end of the message block within the target width vector register 317 . Comparator 2610 compares the high-order bits of the 8-bit block length with the E subfield 2514 of the fill instruction 2500 to form a 1-bit indication of whether EOB padding is added to the segment of the message block buffered in the target width vector register (i.e., whether the target width vector register 317 buffers the trailing segment S1 of the message block). This 1-bit indication is then logically combined by a bit-wise AND circuit 2614 to generate a 128-bit EOB enable signal (eob_en(0:127)) which identifies the byte of the message segment buffered in the target width vector register 317 into which the EOB padding is to be inserted (if any).

Still referring to FIG26 , the padding circuit 2600 further includes an EOM enabling circuit 2620 , which includes a selection circuit 2620 , a comparator 2622 , a decoder 2624 , and a bitwise AND circuit 2626. In the depicted example, the selection circuit 2620 is implemented by a dual-input multiplexer having a first input coupled to receive an 8-bit indication of a message length, and a second input coupled to receive an extended message length for a SHA-2 hash function using 32-bit words. The extended message length value at the second input doubles the original length of the message according to the equation EX_LEN = 4*(LEN/4) + LEN by inserting b0 between bits 5 and 6 of the original length. This technique preserves the bit positions of the original bits 6:7, which indicate the byte positions within the 32 high-order bits of the extended message block of the final message bytes, if any. If HID subfield 2510 indicates that the hash function is a SHA3/SHAKE hash function or a SHA2 hash function that uses 64-bit words, then selection circuit 2620 selects the first of its two 8-bit inputs, and if HID subfield 2510 indicates that the hash function is a SHA2 hash function that uses 32-bit words, then selection circuit 2620 alternatively selects the second of its two inputs.

The 8-bit length value output by the select circuit 2620 includes a high-order bit indicating whether the block length exceeds the width of the 1024-bit wide vector register file 316 , and seven low-order bits indicating the number of bytes contained in the segment of the message block buffered in the target wide vector register 317 identified by register 1 field 2504. The decoder 2624 decodes the seven low-order bits to obtain a 128-bit representation of the byte position (if any) at which the end of the message byte is to be inserted in the target wide vector register 317 . Comparator 2622 compares the high-order bits of the length value output by select circuit 2620 with E subfield 2514 of fill instruction 2500 to form a 1-bit indication of whether EOM padding is to be added to the segment of the message block buffered in target width vector register 317. This 1-bit indication is then logically combined by bitwise AND circuit 2626 to generate a 128-bit EOM enable signal (eom_en(0:127)) that identifies the bytes of the message segment buffered in target width vector register 317 into which EOM padding is to be inserted (if any).

The EOB enable signal eob_en (o: 127), the EOM enable signal eom_en (0: 127), eom_byte, eob_byte and the message segment from the target width vector register 317 are all passed to the conditional "OR" circuit 2630 , which conditionally inserts EOM and/or EOB padding into the message segment to obtain the filled message segment Sp. The filled message segment Sp is then stored back to the target width vector register 317 specified in register 1 field 2504 .

Referring now to FIG. 27 , an exemplary embodiment of the conditional OR circuit 2630 of FIG. 26 is shown. In this example, each of the 128 bytes of the message segment has a respective associated OR gate 2700 having three 8-bit inputs. The first input of the OR gate 2700 is coupled to receive the respective bytes of the message segment S. The second input of the OR gate 2700 is coupled to the output of a dual-input AND gate 2702 , which qualifies the eom_byte for a given bit packet of the message segment S with eom_en(). The third input of the OR gate 2700 is coupled to the output of the dual-input AND gate 2704 , which qualifies eob_byte with eob_en() for a given bit packet of the message segment S. The OR gate 2700 performs a logical OR operation on these three inputs and writes the resulting bytes of the padded message segment Sp to the target wide vector register 317 in the wide vector register file 316. Therefore, if neither eom_en() nor eob_en() is asserted for a given bit packet of the message segment S, the associated OR gate 2700 simply writes the bytes of the input message segment S to the corresponding bytes of the padded message segment Sp. However, if either or both of eom_en() or eob_en() are asserted for a given bit packet of message segment S, then the associated OR gate 2700 writes eom_byte, eob_byte, or a logical combination thereof, into the corresponding bytes of the padded message segment Sp, as indicated by the enable signals eom_en() and eob_en().

Referring now to FIG. 28 , a high-level logic flow chart of an exemplary process for filling a message block according to one embodiment is depicted. The depicted process may be executed by the accelerator unit 314 in response to receiving a fill instruction 2500. For ease of understanding, the process is described below with reference to the exemplary fill circuit depicted in FIGS. 26-27 .

28 begins at block 2800 and then proceeds to block 2802 , which shows the accelerator unit 314 receiving the fill instruction 2500 for execution. In response to receiving the fill instruction 2500 , the accelerator unit 314 first accesses the source operand specified by the register fields 2504 , 2506 of the fill instruction 2500 (block 2804 ). Specifically, the accelerator unit 314 reads the message segment S from the target width vector register 317 specified by the register 1 field 2504 in the width vector register file 316 , reads the unfilled message length from the register 301 specified by the register 2 field 2506 in the architectural register file 300 , and transmits these operands to the fill circuit 2600 of FIG. 26 , which, as mentioned above, can be implemented in the data transfer circuit 406. At block 2806 , the fill circuit 2600 uses the mode field 2508 of the fill instruction 2500 to select the parameters of the fill operation. Specifically, the select EOM circuit 2602 selects the value of the EOM fill byte (eom_byte) 2302 or 2402 based on the hash function specified by the mode field 2508 , the select EOB circuit 2604 selects the value of the EOB fill byte (eob_byte) to be inserted by the fill instruction 2500 (i.e., a fixed value for SHA3/SHAKE and a zero byte for SHA2, since the EOB fill word 2404 is applied by a separate instruction for SHA2), and the select BL size circuit 2606 selects the block length based on the HID subfield 2510 and the BL subfield 2512 . The eom_byte selected by the selected EOM circuit 2602 and the eob_byte selected by the selected EOB circuit 2604 form the input to the conditional "OR" circuit 2630 .

At block 2808 , selection circuit 2620 determines whether the hash function applied to the message is one of the SHA2-224 or SHA2-256 hash functions using 32-bit words based on the HID subfield of mode field 2508. If not, selection circuit 2620 selects and outputs the message length read from register 301 identified by free register 2 field 2506 as the length of the message, and the process of Figure 28 continues to block 2812 , which is described below. However, if the selection circuit 2620 determines at block 2808 that the HID subfield 2510 of the fill instruction 2500 indicates that a 32-bit word SHA2 hash function is used, the selection circuit 2620 selects and outputs a double length for the SHA2 message to account for the message expansion described above with reference to FIG. 15. In one implementation, the expanded SHA2 message length can be conveniently calculated as: 4*(LEN/4)+LEN. The program then continues from block 2810 to block 2812 .

Block 2812 shows the determination by the EOM enable circuit 2620 whether EOM padding is to be placed in the current message segment. If not, the EOM enable vector eom_en (0:127) generated by the EOM enable circuit 2620 is all zeros, and no EOM padding is inserted into the message segment S. Therefore, the process transfers to block 2816 , which is described below. However, if the EOM enable circuit 2620 determines at block 2812 that EOM padding is to be inserted into the message segment S, the EOM enable circuit 2620 generates an EOM enable vector eom_en (0:127) that identifies the byte of the message segment S where the EOM padding byte is to be inserted, and the EOM padding byte is inserted into the specified byte of the padded message segment Sp by the conditional "OR" circuit 2630 (block 2814 ). The program continues from block 2814 to block 2816 .

At block 2816 , the BL size selection circuit 2606 and the EOB enable circuit 2608 determine whether the hash function specified by the mode field 2508 of the hash instruction 2500 is a SHA3 or SHAKE hash function and EOB padding bytes are to be inserted into the message segment S. If not, the EOB enable vector eob_en (0:127) generated by the EOB enable circuit 2608 is all zeros, and no EOB padding is inserted into the message segment S. Therefore, the program jumps from block 2816 to block 2820 , which is described below. However, if the BL size circuit 2606 and the EOB enable circuit 2620 determine at block 2816 that the hash function specified by the mode field 2508 is a SHA3 or SHAKE hash function and EOB padding is to be inserted into the message segment S, then the EOB enable circuit 2608 generates an EOB enable vector eob_en (0:127) that identifies the byte of the message segment S into which the EOB padding byte is to be inserted, and the EOB padding byte is inserted into the specified byte of the padded message segment Sp by the conditional "or" circuit 2630 (block 2818 ). The program then jumps to block 2820 .

Block 2820 shows the data transfer circuit 406 writing the resulting padded message segment Sp into the target width vector register 317 specified by register 1 field 2504. Thereafter, the process of FIG. 28 ends at block 2822 .

Referring now to FIG. 29 , a block diagram of an exemplary design flow 2900 for use in, for example, semiconductor IC logic design, simulation, testing, layout, and manufacturing is shown. The design flow 2900 includes a program, machine, and/or mechanism for processing a design structure or device to generate a logically or otherwise functionally equivalent representation of the design structure and/or device described above and shown herein. The design structure processed and/or generated by the design flow 2900 may be encoded on a machine-readable transmission or storage medium to include data and/or instructions that, when executed or otherwise processed on a data processing system, generate a logically, structurally, mechanically, or otherwise functionally equivalent representation of a hardware component, circuit, device, or system. A machine includes, but is not limited to, any machine used in an IC design process, such as designing, manufacturing, or simulating a circuit, component, device, or system. For example, a machine may include: a lithography machine, a machine and/or equipment for generating masks (e.g., an electron beam writer), a computer or equipment for simulating a design structure, any equipment for a manufacturing or testing process, or any machine for programming a functionally equivalent representation of a design structure into any medium (e.g., a machine for programming a programmable gate array).

The design flow 2900 may vary depending on the type of representation being designed. For example, a design flow 2900 for building an application specific IC (ASIC) may be different from a design flow 2900 for designing a standard component or from a design flow 2900 for materializing a design into a programmable array, such as a programmable gate array (PGA) or a field programmable gate array (FPGA) provided by Altera® or Xilinx®.

FIG. 29 illustrates a plurality of such design structures including an input design structure 2920 preferably processed by a design program 2910. The design structure 2920 may be a logical analog design structure generated by the design program 2910 and processed to produce a logically equivalent functional representation of a hardware device. The design structure 2920 may also or alternatively include data and/or program instructions that, when processed by the design program 2910, generate a functional representation of the physical structure of the hardware device. Whether representing functional and/or structural design features, the design structure 2920 may be generated using electronic computer-aided design (ECAD) such as implemented by a core developer/designer. When encoded on a machine-readable data transmission, gate array, or storage medium, the design structure 2920 can be accessed and processed by one or more hardware and/or software modules within the design process 2910 to simulate or otherwise functionally represent an electronic component, circuit, electronic or logical module, apparatus, device, or system, such as those shown herein. Thus, design structure 2920 may include files or other data structures including human and/or machine readable source code, compiled structures, and computer executable program code structures that functionally simulate or otherwise represent circuits or other levels of a hardware logic design when processed by a design or simulation data processing system. Such data structures may include hardware description language (HDL) design entities or other data structures that conform to lower level HDL design languages (such as Verilog and VHDL) and/or higher level design languages (such as C or C++) and/or are compatible with lower level HDL design languages and/or higher level design languages.

Design program 2910 preferably employs and incorporates hardware and/or software modules for synthesizing, translating, or otherwise processing design/simulation functional equivalents of components, circuits, devices, or logic structures shown herein to generate a wiring lookup table 2980 that may contain design structures such as design structure 2920. Wiring lookup table 2980 may include, for example, a compiled or otherwise processed data structure representing a list of wires, discrete components, logic gates, control circuits, I/O devices, models, etc. that describe connections to other components and circuits in an integrated circuit design. The wiring lookup table 2980 can be synthesized using an iterative process, where the wiring lookup table 2980 is resynthesized one or more times depending on the design specifications and parameters for the device. As with other design structure types described herein, the wiring lookup table 2980 can be recorded on a machine readable storage medium or programmed into a programmable gate array. The medium can be a non-volatile storage medium such as a disk drive or optical disk drive, a programmable gate array, a CF card (compact flash) or other flash memory. Additionally or in the alternative, the medium can be system or cache memory or buffer space.

The design process 2910 may include hardware and software modules for processing a variety of input data structure types including a wiring lookup table 2980. Such data structure types may reside, for example, in a library component 2930 and include a collection of commonly used components, circuits, and devices for a given manufacturing technology (e.g., different technology nodes: 32nm, 45nm, 290nm, etc.), including models, layouts, and symbolic representations. The data structure types may further include design specifications 2940 , characterization data 2950 , verification data 2960 , design rules 2990 , and test data files 2985 , which may include input test patterns, output test results, and other test information. The design process 2910 may further include, for example, standard mechanical design processes such as stress analysis, thermal analysis, mechanical event simulation, process simulation for operations such as casting, molding, and die-stamping. A person skilled in the art of mechanical design will understand the range of possible mechanical design tools and applications for use in the design process 2910 without departing from the scope and spirit of the present invention. The design process 2910 may also include modules for performing standard circuit design processes such as timing analysis, verification, design rule checking, placement and routing operations.

The design program 2910 employs and incorporates logical and physical design tools such as HDL compilers and simulation model building tools to process the design structure 2920 along with some or all of the depicted supporting data structures and any additional mechanical design or data, if applicable, to generate a second design structure 2990. The design structure 2990 resides on a storage medium or programmable gate array in a data format for exchanging data of mechanical devices and structures (e.g., information stored in IGES, DXF, Parasolid XT, JT, DRG, or any other suitable format for storing or presenting such mechanical design structures). Similar to design structure 2920 , design structure 2990 preferably includes one or more files, data structures, or other computer-encoded data or instructions that reside on a transmission or data storage medium and that, when processed by an ECAD system, generate a logically or otherwise functionally equivalent form of one or more of the embodiments of the invention presented herein. In one embodiment, design structure 2990 may include a compiled, executable HDL simulation model that functionally simulates a device presented herein.

Design structure 2990 may also employ a data format for exchanging layout data of integrated circuits and/or a symbol data format (e.g., information stored in GDSII (GDS2), GL1, OASIS, a map file, or any other suitable format for storing such design data structures). Design structure 2990 may include information such as, for example, symbol data, map files, test data files, design content files, manufacturing data, layout parameters, wires, metal levels, vias, shapes, data for routing through fabricated lines, and any other data required by a manufacturer or other designer/developer to produce devices or structures as described above and shown herein. The design structure 2990 may then proceed to stage 2995 , where, for example, the design structure 2990 : proceeds to tape-out, is released to manufacturing, is released to a mask room, is sent to another design house, is sent back to a customer, etc.

As described, in at least one embodiment, a processor includes a register file and an execution unit. The execution unit includes: a hash circuit including at least one state register; a state update circuit coupled to the state register; and a control circuit. Based on a hash instruction, the hash circuit receives from the register file and buffers a current state of a message being hashed in the state register. The state update circuit executes a state update function on the content of the state register, wherein executing the state update function includes executing a plurality of repeated rounds of processing on the content of the state register, and returning a result of each of the plurality of repeated rounds of processing to the state register. After completing all the plurality of repeated rounds of processing, the execution unit stores the content of the state register to the register file as an updated state of the message.

In at least some embodiments, the state update function comprises a secure hash algorithm 3 (SHA3) state permutation function; and the state update circuit performs twenty-four rounds of processing, each round of processing utilizing a respective round index of the twenty-four round indices as an input.

In one embodiment, the execution unit executes the hash instruction in a squeeze phase of a secure hash algorithm and a Keccak (SHAKE) hash algorithm.

In at least some embodiments, the state update function comprises a secure hash algorithm 2 (SHA2) block hash function. In at least some embodiments, the hash circuit further comprises an adder configured to add the contents of the state register to the current state and return a resulting sum to the register file. In some embodiments, the execution unit further comprises a message block register for buffering a message block of the message and a message scheduling round circuit coupled to the message block register. The message scheduling circuit performs a plurality of iterative rounds of processing on the content of the message block register and returns a result of each of the plurality of iterative rounds of processing to the message block register. In some embodiments, the state update circuit includes a data path for data words having a first data width, and the execution unit is configured to expand the data words of a message block of the message to the first data width before processing the data words of the message in the state update circuit based on the hash instruction indicating a second data width narrower than the first data width.

Although various embodiments have been particularly shown and described, those skilled in the art will appreciate that various changes in form and detail may be made therein without departing from the spirit and scope of the appended claims, and such alternative implementations are intended to be within the scope of the appended claims. For example, although the present invention has been described with specific reference to the SHA family of standards, those skilled in the art will appreciate that the disclosed invention is also applicable to other hashing algorithms (e.g., generalized Keccak functions, among others). Additionally, although illustrative numbers of bits and bytes have been discussed herein for ease of understanding, it should be understood that the specific numbers of bits and bytes used in hashing algorithms can and do change over time, and that the principles of the disclosed invention apply to encryption algorithms regardless of the specific numbers of bits and bytes in a given implementation.

The flowcharts and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagram may represent a module, segment, or portion of an instruction that includes one or more executable instructions for implementing a specified logic function. In some alternative implementations, the functions mentioned in the blocks may not occur in the order mentioned in the figures. For example, depending on the functionality involved, two blocks shown in succession may actually be executed substantially simultaneously, or the blocks may sometimes be executed in reverse order. It should also be noted that each block of the block diagram and/or flowchart illustration and the combination of blocks in the block diagram and/or flowchart illustration can be implemented by a special purpose hardware-based system that performs the specified function or action or performs a combination of special purpose hardware and computer instructions.

Additionally, although the embodiments have been described with respect to a computer system executing program code that directs the functions of the present invention, it should be understood that the present invention may alternatively be implemented as a program product including a computer-readable storage device storing program code that can be processed by a data processing system. The computer-readable storage device may include volatile or non-volatile memory, optical or magnetic disks, or the like. However, as used herein, "storage device" is specifically defined to include only legal products and excludes the signal medium itself, the transient propagation signal itself, and the energy itself.

Program products may include data and/or instructions that, when executed or otherwise processed on a data processing system, generate a logically, structurally or otherwise functionally equivalent representation (including simulation models) of a hardware component, circuit, device or system disclosed herein. Such data and/or instructions may include hardware description language (HDL) design entities or other data structures that conform to lower-level HDL design languages (such as Verilog and VHDL) and/or higher-level design languages (such as C or C++) and/or are compatible with lower-level HDL design languages and/or higher-level design languages. Additionally, the data and/or instructions may also be in a data format and/or symbolic data format used to exchange layout data of an integrated circuit (e.g., information stored in GDSII (GDS2), GL1, OASIS, a map file, or any other suitable format for storing such design data structures).

2800: Block

2802: Block

2804: Block

2806: Block

2808: Block

2810: Block

2812: Block

2814: Block

2816: Block

2818: Block

2820: Block

2822: Block

Claims (10)

A processor comprises: an instruction fetch unit, which fetches instructions to be executed; a register file, which includes a plurality of registers for storing source and destination operands; and an execution unit, which is used to execute a hash instruction, wherein the execution unit includes: a hash circuit, which includes at least one state register; a state update circuit, which is coupled to the state register; and a control circuit, wherein the execution unit is configured to perform the following operations based on the hash instruction: receiving a current state of a message being hashed from the register file and buffering it in the state register; performing a state update on the content of the state register in the state update circuit; A new function, wherein executing the state update function includes performing a plurality of iterative rounds of processing on the content of the state register, and returning a result of each of the plurality of iterative rounds of processing to the state register; and after completing all of the plurality of iterative rounds of processing, storing the content of the state register to the register file as an updated state of the message, wherein: the state update function includes a secure hash algorithm 2 (SHA2) block hash function; and the hash circuit further includes an adder, which is configured to add the content of the state register to the current state and return a resulting sum to the register file. A processor as claimed in claim 1, wherein: the execution unit further includes a message block register for buffering a message block of the message and a message scheduling circuit coupled to the message block register; and executing a state update function includes executing a plurality of repeated rounds of processing on the content of the message block register by the message scheduling circuit, and returning a result of each of the plurality of repeated rounds of processing to the message block register. A processor as claimed in claim 1, wherein: the state update circuit includes a data path for data words having a first data width; and the execution unit is configured to expand the data words of a message block of the message to the first data width before processing the data words of the message in the state update circuit based on the hash instruction indicating a second data width narrower than the first data width. A data processing system comprising: a plurality of processors, including the processor of claim 1; a shared memory; and a system interconnect coupling the shared memory and the plurality of processors in a communication manner. A method for performing data processing in a processor, the method comprising: extracting instructions to be executed by the processor by an instruction extraction unit, wherein the instructions include a hash instruction; and based on receiving the hash instruction, an execution unit of the processor executes the hash instruction, wherein the execution unit includes: a hash circuit, which includes at least one state register; a state update circuit, which is coupled to the state register; and a control circuit, wherein the execution includes: receiving a current state of a message being hashed from a register file and buffering it in the state register; performing a state update on the content of the state register in the state update circuit. A new function, wherein executing the state update function includes performing a plurality of iterative rounds of processing on the content of the state register, and returning a result of each of the plurality of iterative rounds of processing to the state register; and after completing all of the plurality of iterative rounds of processing, storing the content of the state register to the register file as an updated state of the message, wherein: the state update function includes a secure hash algorithm 2 (SHA2) block hash function; and the hash circuit further includes an adder, which is configured to add the content of the state register to the current state and return a resulting sum to the register file. The method of claim 5, wherein: the execution unit further includes a message block register for buffering a message block of the message and a message scheduling circuit coupled to the message block register; and executing a state update function includes executing a plurality of repeated rounds of processing on the content of the message block register in the message scheduling circuit, and returning a result of each of the plurality of repeated rounds of processing to the message block register. The method of claim 5, wherein: The state update circuit includes a data path for data words having a first data width; and the method further includes: based on the hash instruction indicating a second data width narrower than the first data width, before processing the data words of the message in the state update circuit, expanding the data words of a message block of the message to the first data width. A design structure, tangibly embodied in a machine-readable storage device, for designing, manufacturing or testing an integrated circuit, the design structure comprising: a processor, comprising: an instruction fetch unit, which fetches instructions to be executed; a register file, which comprises a plurality of registers for storing source and destination operands; and an execution unit, which is used to execute a complex A hash instruction, wherein the execution unit includes: a hash circuit including at least one state register; a state update circuit coupled to the state register; and a control circuit, wherein the execution unit is configured to perform the following operations based on the hash instruction: receiving from the register file and buffering in the state register a current state of a message being hashed; The state update circuit executes a state update function on the content of the state register, wherein the execution of the state update function includes executing a plurality of repeated rounds of processing on the content of the state register, and returning a result of each of the plurality of repeated rounds of processing to the state register; and after completing all the plurality of repeated rounds of processing, the state register is The contents of the register are stored in the register file as an updated state of the message, wherein: the state update function comprises a secure hash algorithm 2 (SHA2) block hash function; and the hash circuit further comprises an adder configured to add the contents of the state register to the current state and return a resulting sum to the register file. The design structure of claim 8, wherein: the execution unit further includes a message block register for buffering a message block of the message and a message scheduling circuit coupled to the message block register; and executing a state update function includes executing a plurality of repeated rounds of processing on the content of the message block register by the message scheduling circuit, and returning a result of each of the plurality of repeated rounds of processing to the message block register. The design structure of claim 8, wherein: the state update circuit includes a data path for data words having a first data width; and the execution unit is configured to expand the data words of a message block of the message to the first data width before processing the data words of the message in the state update circuit based on the hash instruction indicating a second data width narrower than the first data width.