WO2025034214A1 - Hashing circuitry based on hybrid ring generators - Google Patents

Abstract

A hashing circuit comprises: an n-bit hybrid ring generator configured to implement a primitive polynomial of degree n, a phase shifter coupled to outputs of the n-bit hybrid ring generator, and an m-bit nonlinear sequential device coupled to outputs of the phase shifter. The n-bit hybrid ring generator comprises n state elements coupled to each other to form an n-bit ringlike structure, k feedback-enable devices, and injection devices configured to inject bits of the binary value into the n-bit ringlike structure. The n-bit ringlike structure has a top row and a bottom row, of which each has at least one of the n state elements and at least one of the k feedback- enable devices. The m-bit nonlinear sequential device comprises m state elements coupled to each other to form an m-bit ringlike structure and one or more feedback paths comprising nonlinear devices implementing nonlinear functions.

Description

Patent 202308205 Hashing Circuitry Based On Hybrid Ring Generators FIELD OF THE DISCLOSED TECHNIQUES [01] The presently disclosed techniques relate to the field of hardware security and trust. Various implementations of the disclosed techniques may be particularly useful for hashing circuitry design and applications. BACKGROUND OF THE DISCLOSED TECHNIQUES [02] Hash functions play a host of roles in protecting digital ecosystems. Cryptographic hashing is essential for many cyber and information security applications, including data integrity, entity authentication, digital signatures, cryptographic key generation, password security, forensic investigation, transactions integrity in blockchains, and message validation in internet of things. For example, if one enters a password in a website, the server will likely store a hashed version of the password. Similarly, hashes secure website connections and transactions with cryptocurrencies. Non-crypto hash functions, on the other hand, can make handling files far more efficient in large data centers. [03] Cryptographic hash functions play a vital role in shaping high end hardware roots of trust – foundations on which secure operations of digital integrated circuits (IC) depend. Typically, they are integrated into circuits as customized security blocks that handle chip and device identities, manage cryptographic keys and functions, and secure boot processes, attestation, authentication, and firmware updates. Accordingly, the hardware root of trust should be capable of detecting an intrusion, disabling access pending further actions, and/or obfuscating logic operations of the IC. The foundation for a silicon-based fixed-function root of trust is its authentication protocol. It runs a specific set of functions such as true random number generation, data encryption, keys validation, logic locking, Patent 202308205 and data hashing. As an initial part of the actual challenge-response procedure, an IC creates a truly random token, commonly known as a challenge or a nonce (it may also contain some individual data from the IC such as its electronic identification number), and then sends it over to a secure server. The security processor computes a hash of the nonce. This hash (or digest) is subsequently returned to the IC to be compared with a hash value produced locally (internally) by the IC. The latter is usually done by virtue of a device implementing a lightweight cryptographic hash function. [04] Lightweight crypto hashing circuitry has become a key hardware security primitive. It should be able to produce virtually unique and fixed-length digests for arbitrarily long input sequences even in small devices with limited computing resources. Because of their not so lightweight hardware and complex implementations, however, many IC vendors may still not think the conventional solutions as acceptable. Hashing circuitry having properties of being lightweight, compact, programmable, scalable and being capable of turning into a keyed hashing scheme easily is thus highly desirable. BRIEF SUMMARY OF THE DISCLOSED TECHNIQUES [05] Various aspects of the disclosed technology relate to hashing circuitry constructed based on hybrid ring generators. In one aspect, there is a hashing circuit configured to convert a binary value into a hash value, comprising: an n-bit hybrid ring generator configured to implement a primitive polynomial of degree n, the n-bit hybrid ring generator comprising n state elements coupled to each other to form an n-bit ringlike structure in a schematic diagram, k feedback-enable devices, and injection devices configured to inject bits of the binary value into the n-bit ringlike structure, the n-bit ringlike structure having a top row and a bottom row, each of the top row and the bottom row having at least one of the n state elements and at least one of the k feedback-enable devices, each of the k feedback-enable devices coupled to a state element on a different row through one of k feedback lines; a phase shifter coupled to outputs of the n-bit hybrid ring generator; and Patent 202308205 an m-bit nonlinear sequential device coupled to outputs of the phase shifter, the m-bit nonlinear sequential device comprising m state elements coupled to each other to form an m-bit ringlike structure in a schematic diagram and one or more feedback paths comprising nonlinear devices, each of the nonlinear devices configured to implement a nonlinear function converting bits from outputs of some of the m state elements into a bit. [06] The circuit may further comprise: a plurality of 2-to-1 multiplexers inserted between the phase shifter and the m-bit nonlinear sequential device, select inputs for the plurality of 2-to-1 multiplexers being coupled to outputs of state elements in the m state elements. [07] The numbers of state elements in the n state elements placed on the top row and the bottom row may be equal or differ by one, the numbers of feedback-enable devices in the k feedback-enable devices placed on the top row and the bottom row may be equal or differ by one, k may be greater than 2, none of the k feedback lines may cross each other, and feedback lines coupled to feedback-enable devices on the top row and feedback lines coupled to feedback-enable devices on the bottom row may be placed alternatively with respective to each other. The k feedback lines may be distributed such that the numbers of two groups of state elements on the top row or on the bottom row between any three neighboring feedback lines or between two neighboring feedback lines and their neighboring end of the ringlike structure are equal or differ by no more than two. [08] The n-bit hybrid ring generator may further comprise: feedback path selection storage devices; and feedback path selection logic devices, wherein the feedback path selection storage devices and the feedback path selection logic devices are configured to enable the n-bit hybrid ring generator to implement one of a plurality of primitive polynomials of degree n based on feedback configuration bits stored in the storage devices. Patent 202308205 [09] The n-bit hybrid ring generator may be configured to receive an initial value before the circuit starts to convert the binary value into the hash value. [10] The nonlinear function may be a derivative of bent function, the derivative of bent function being a balanced Boolean function. [11] Each of the nonlinear devices may comprise: a bent function device configured to implement a bent function receiving bits at the outputs for the plurality of state elements; an AND gate, inputs of the AND gate being coupled to an output of a state element shared with the bent function device and one of the outputs for the plurality of state elements; and circuitry configured to combine output of the bent function device with output of the AND gate into a bit and to inject the bit into the m-bit ringlike structure. [12] The nonlinear function-based device may be configured to receive an initial value before the circuit starts to convert the binary value into the hash value. [13] The n state elements and the m state elements may be flip-flops, the k feedback-enable devices and the injection devices may be XOR gates, and the phase shifter may comprise XOR gates. [14] In another aspect, there are one or more non-transitory computer-readable media storing computer-executable instructions for causing one or more processors to perform a method, the method comprising: creating the above hashing circuit in a circuit design. [15] Certain inventive aspects are set out in the accompanying independent and dependent claims. Features from the dependent claims may be combined with features of the independent claims and with features of other dependent claims as appropriate and not merely as explicitly set out in the claims. [16] Certain objects and advantages of various inventive aspects have been described herein above. Of course, it is to be understood that not necessarily all such objects or advantages Patent 202308205 may be achieved in accordance with any particular embodiment of the disclosed techniques. Thus, for example, those skilled in the art will recognize that the disclosed techniques may be embodied or carried out in a manner that achieves or optimizes one advantage or group of advantages as taught herein without necessarily achieving other objects or advantages as may be taught or suggested herein. BRIEF DESCRIPTION OF THE DRAWINGS [17] Figure 1 illustrates an example hashing circuit that may be implemented according to various embodiments of the disclosed technology. [18] Figure 2 illustrates an example of an n-bit hybrid ring generator that may be implemented according to various embodiments of the disclosed technology. [19] Figure 3 illustrates a flowchart showing a process for generating a maximum-length hybrid ring generator-based system that may be implemented according to various examples of the disclosed technology. [20] Figure 4 illustrates a 4-bit ring generator and a lookup table which are used to show how the primitiveness test operates. [21] Figure 5A illustrates an example conventional 32-bit ring generator that implements a primitive polynomial. [22] Figure 5B illustrates an example 32-bit hybrid ring generator and its feedback function corresponding to the primitive polynomial of Fig.5A. [23] Figure 6 illustrates an example programmable hybrid ring generator that may be implemented according to various embodiments of the disclosed technology. Patent 202308205 [24] Figure 7A illustrates an example of another type of hybrid ring generators that may be implemented according to various examples of the disclosed technology, a 24-bit hybrid ring generator. [25] Figure 7B illustrates a 24-bit ring generator and a corresponding primitive polynomial which can be used to derive the 24-bit hybrid ring generator in Fig.7A. [26] Figure 8 illustrates an example of a 32-bit nonlinear sequential device that may be implemented according to various examples of the disclosed technology. [27] Figure 9 illustrates three simple nonlinear devices that may be used in an m-bit nonlinear sequential device according to various examples of the disclosed technology. [28] Figure 10 illustrates an example block diagram of a hashing circuit that may be implemented according to various embodiments of the disclosed technology. [29] Figure 11 illustrates an example of a programmable computer system with which various embodiments of the disclosed technology may be employed. DETAILED DESCRIPTION OF THE DISCLOSED TECHNIQUES [30] Various aspects of the disclosed technology relate to hashing circuitry constructed based on hybrid ring generators. In the following description, numerous details are set forth for the purpose of explanation. However, one of ordinary skill in the art will realize that the disclosed technology may be practiced without the use of these specific details. In other instances, well-known features have not been described in detail to avoid obscuring the disclosed technology. [31] Some of the techniques described herein can be implemented in software instructions stored on a computer-readable medium, software instructions executed on a computer, or some combination of both. Some of the disclosed techniques, for example, can be Patent 202308205 implemented as part of an electronic design automation (EDA) tool. Such methods can be executed on a single computer or on networked computers. [32] Although the operations of the disclosed methods are described in a particular sequential order for convenient presentation, it should be understood that this manner of description encompasses rearrangements, unless a particular ordering is required by specific language set forth below. For example, operations described sequentially may in some cases be rearranged or performed concurrently. Moreover, for the sake of simplicity, the disclosed flow charts and block diagrams typically do not show the various ways in which particular methods can be used in conjunction with other methods. [33] The detailed description of a method or a device sometimes uses terms like “configure” and “inject” to describe the disclosed method or the device function/structure. Such terms are high-level descriptions. The actual operations or functions/structures that correspond to these terms will vary depending on the particular implementation and are readily discernible by one of ordinary skill in the art. [34] As used in this disclosure, the singular forms “a,” “an,” and “the” include the plural forms unless the context clearly dictates otherwise. Additionally, the term “includes” means “comprises.” Moreover, unless the context dictates otherwise, the term “coupled” means electrically or electromagnetically connected or linked and includes both direct connections or direct links and indirect connections or indirect links through one or more intermediate elements not affecting the intended operation of the circuit. [35] Additionally, as used herein, the term “design” is intended to encompass data describing an entire integrated circuit device. This term also is intended to encompass a smaller group of data describing one or more components of an entire device such as a portion of an integrated circuit device nevertheless. Patent 202308205 [36] Fig.1 illustrates an example hashing circuit 100 that may be implemented according to various embodiments of the disclosed technology. The hashing circuit 100 comprises an n-bit hybrid ring generator 110, a phase shifter 120, and an m-bit nonlinear sequential device 130. The hashing circuit 100 is configured to convert a binary value 150 into a hash value 160. [37] The n-bit hybrid ring generator 110 is configured to implement a primitive polynomial of degree n. Here, n is an integer. In a typical application, n is greater than 4. The n-bit hybrid ring generator 110 comprises n state elements, k feedback-enable devices for k feedback lines, and some injection devices. The n state elements are coupled to each other to form an n-bit ringlike structure in a schematic diagram. The n-bit ringlike structure has a top row and a bottom row, of which each has at least one of the n state elements and at least one of the k feedback-enable devices. Each of the k feedback-enable devices is coupled to a state element on a different row through one of the k feedback lines. The injection devices are configured to inject bits of the binary value 150 into the n-bit ringlike structure in a parallel fashion. These bits can circulate in the n-bit ringlike structure until a bit sequence, a final digest, is outputted. The n-bit hybrid ring generator 110 may be initialized by an initial value 115. In some embodiments of the disclosed technology, the feedback function of the n-bit hybrid ring generator 110 can be reprogrammed by a secret selection mask, feedback configuration bits 170. An example reprogrammable n-bit hybrid ring generator will be described later. As also will be discussed below, the n-bit hybrid ring generator 110 can accelerate circulation of the binary value 150 injected into the register compared to conventional ring generators and employ the smaller number of feedback taps than the number of terms of the deployed primitive polynomial. [38] The phase shifter 120 is coupled to outputs of the n-bit hybrid ring generator 110. Like conventional linear feedback shift registers, hybrid ring generators may not be free from and linearly dependent positions in their output sequences. The phase shifter 120 can take Patent 202308205 advantage of the shift-and-add property and use a set of linear combinations of the outputs of the n-bit hybrid ring generator 110 to obtain sequences that are shifted with respect to every other sequence by at least a given number of bits. The phase shifter 120 can also act as an expander, allowing a relatively compact hybrid ring generator to drive a large number of receivers. This can result in substantial savings in the sequential logic footprint. The phase shifter 120 can be obtained by selecting XOR tap combinations randomly, and then by checking whether a sequence produced by a linear combination of newly selected XOR taps does not overlap with sequences generated on already existing outputs. [39] The m-bit nonlinear sequential device 130 is coupled to outputs of the phase shifter 120. The m-bit nonlinear sequential device 130 comprises m state elements and one or more feedback paths comprising nonlinear devices. The m state elements are coupled to each other to form an m-bit ringlike structure in a schematic diagram. Each of the nonlinear devices is configured to implement a nonlinear function converting bits from outputs of some of the m state elements into a bit. The bit itself or another bit derived from it is injected back into the m-bit ringlike structure. The m-bit nonlinear sequential device 130 may be initialized by an initial value 135. [40] The m-bit nonlinear sequential device 130 and the n-bit hybrid ring generator 110 can be configured to work synchronously to produce the hash value 160. Given initial (proprietary) states of the n-bit hybrid ring generator 110 and the m-bit nonlinear sequential device 130, the hashing circuit 100 can process the binary value 150 of arbitrary length, e.g., a one-time nonce, for a number of clock cycles (or iterations). This number can be equal to the sum of cycles needed to shift-in the binary value 150 and a predefined number of additional cycles required to complete a hash computation. The hash value 160 can have a fixed length of m, being obtained by reading out the entire content of the m state elements. The combination of the n-bit hybrid ring generator 110, Patent 202308205 the phase shifter 120, and the m-bit nonlinear sequential device 130 can make it computationally infeasible to find the binary value 150 based on the hash value 160. [41] In some embodiments of the disclosed technology, the hashing circuit 100 can further comprise multiplexers 140 between the phase shifter 120 and the m-bit nonlinear sequential device 130. The multiplexers 140 are configured to select randomly and per- cycle data produced by the n-bit hybrid ring generator 110 and the phase shifter 120. A signal placed on the selection input of each of the 2-to-1 multiplexers 140 can be provided by one or more dedicated state element of the m-bit nonlinear sequential device 130 (only one state element is needed if the multiplexer 140 is 2-to-1 multiplexer). In addition to improved randomness, the multiplexers 140 can enhance nonlinearity of the results. By using the multiplexers 140, linear expressions leaving the phase shifter are turned into nonlinear formulas even before they enter the m-bit nonlinear sequential device 130. What makes it possible is the equation y = a + bc + ac, i.e., the multiplexer algebraic normal form (ANF) with a, b, and c assuming the role of data and selection inputs, respectively. [42] Fig. 2 illustrates an example of an n-bit hybrid ring generator 200 that may be implemented according to various embodiments of the disclosed technology. The n-bit hybrid ring generator 200 comprises n state elements 210 and k feedback-enable devices 220. Here, k is greater than 2. The state elements 210 can be implemented using flip- flops. The feedback-enable devices 220 can be implemented using XOR gates. [43] The n state elements 210 are connected directly or indirectly to each other to form a ringlike structure in a schematic diagram as illustrated in Fig. 2. An example indirect connection is connecting through one of the k feedback-enable devices 220. Another example of indirect connection is connecting through an injection device (another XOR gate, for example) when the n-bit hybrid ring generator 200 serves as a multiple-input test response compactor, a decompressor, a true random number generator, or a part of Patent 202308205 the hashing circuit 100 in Fig. 1. The numbers of state elements placed on the top and bottom rows of the ringlike structure are equal or differ by one. [44] Each of the k feedback-enable devices 220 is placed between two neighboring state elements in the n state elements 210, receiving signals directly or indirectly from one of the two neighboring state elements and a state element on a different row via one of feedback lines 230, 240, respectively. Again, an example indirect connection with one of the two neighboring state elements may be through an injection device. An example indirect connection with a state element on a different row may be through logic gate(s) when the n-bit hybrid ring generator 200 is an n-bit programmable hybrid ring generator- based system which will be discussed later. [45] The numbers of feedback-enable devices placed on the top and bottom rows of the n-bit hybrid ring generator 200 are equal or differ by one. The feedback lines 230 are associated with the feedback-enable devices on the top row and thus are referred to as upward feedback lines. The feedback lines 240 are associated with the feedback-enable devices on the bottom row and thus are referred to as downward feedback lines. The total number of feedback lines are equal to the number of the feedback-enable devices, k. None of the feedback lines 230, 240 cross each other. The upward feedback lines 230 and the downward feedback lines 240 are placed alternatively. While the feedback lines 230, 240 are shown as conducting lines in Fig. 2, the feedback lines 230, 240 can pass through logic gates like those used in an n-bit programmable hybrid ring generator-based system which will be discussed later. [46] The mutual spatial separations between the feedback lines 230, 240 may be made roughly the same so that the feedback lines 230, 240 are (approximately) uniformly distributed. For example, the numbers of two groups state elements on the top row or on the bottom row between any three neighboring feedback lines or between two neighboring feedback lines and their neighboring end of the ringlike structure are equal or differ by no more Patent 202308205 than two. They are, therefore, amenable to implementing highly modular hybrid ring generators. [47] If the n-bit hybrid ring generator 200 implements a primitive polynomial of degree n over Galois field of order 2, i.e., GF(2), it will yield a sequence comprising 2ⁿ – 1 states, preserving the maximum length property of the corresponding linear feedback shift register (LFSR). This can be verified using a fast LFSR simulation technique. The computing time for this primitiveness test is proportional to n², i.e., O(n²). Due to the high computational efficacy, the test can be employed to obtain hybrid ring

generator 200. [48] Fig. 3 illustrates a flowchart 300 showing a process for generating a maximum-length hybrid ring generator-based system that may be implemented according to various examples of the disclosed technology. A maximum-length hybrid ring generator is a hybrid ring generator implementing a primitive polynomial, and vice versa. In operation 310, a candidate hybrid ring generator is selected. Its size (the number of state elements, n), the desired number of feedback taps (the number of feedback-enable devices, k), and other constraints such as feedback lines being approximately uniformly distributed can be set based on the application. The numbers of state elements in the state elements placed on the top row and the bottom row are equal or differ by one. The feedback lines of the candidate hybrid ring generator do not cross each other and the upward feedback lines and the downward feedback lines are placed alternatively. [49] In operation 320, a primitiveness test is performed on the candidate hybrid ring generator. The primitiveness test is based on a lemma: Suppose that 2ⁿ – 1 = p1^a p2^b … pm^g, where p₁, p₂, … , p_m are distinct primes. Then an irreducible polynomial h(x) over GF(2) is primitive if and only if x^c ^ 1 mod h(x), where c = (2ⁿ – 1)/pi for i = 1, 2, … , m, wherein the ring structure implements a primitive polynomial of degree n over GF(2). The primitiveness test can analyze the corresponding n-bit LFSR implementing h(x). When Patent 202308205 initialized to a non-zero seed s, this LFSR generates a periodic sequence of span 2ⁿ – 1, i.e., a k-sequence, provided that: after 2ⁿ – 1 steps the seed s occurs again, and after (2ⁿ – 1)/p_i steps the seed s does not occur again, for i = 1, 2, … , m. [50] Specifically, let an n-bit LFSR be initialized with a seed having a single one on the jth position (stage) and then run for c clock cycles reaching state S[j, c]. This requires a single simulation step to determine states S[j, 1], j = 0, … , n – 1. Subsequently, values of S[j, 2ⁱ] can be derived using exclusively the principle of superposition since S[j, 2ⁱ] is equal to a bit-wise XOR of S[m, 2^i-1], where S[m, 2^i-1] is only taken into account if the mth bit of S[m, 2^i-1] is set to 1. Consequently, in n² steps one can obtain states S[j, 2ⁱ], i = 0, … , n – 1, j = 0, … , n – 1. By virtue of these values, any other state the LFSR reaches after a given number of cycles (like those specified above) can be computed in a similar fashion, i.e., by applying the principle of superposition in at most n steps. [51] Fig.4 illustrates a 4-bit ring generator 410 and a lookup table 420 which are used to show how the primitiveness test operates. The 4-bit ring generator 410 implements a primitive polynomial h(x) = x⁴ + x + 1. The entry located in the ith row and jth column of the lookup table 420 represents a state that the 4-bit ring generator 410 enters after 2ⁱ steps, assuming that the initial state features a single 1 on the jth position in its binary representation. Single simulation steps suffice to determine the contents of the first row of the lookup table 420. The first row entry in column j stores the state that immediately follows a state comprised of all zeros but a single 1 on position j. For instance, the 4-bit ring generator 410 initialized with state 0010 moves to state 0011 in one step, which is represented by the entry in row one, column three of the lookup table 420. The entries in the remaining rows can be determined using the principle of superposition. There is no need to use any form of logic simulation. [52] Assuming that its initial state was 0010, determining the state that the 4-bit ring generator 410 reaches after two clock cycles can be reduced to finding a state that the same circuit Patent 202308205 reaches after one clock cycle, provided that its current state is 0011. Superposition allows further decomposition of the problem into two simpler tasks – finding immediate successors of states 0010 and 0001 – as the superposition of these states yields state 0011. As the first row of the lookup table 420 shows, the 4-bit ring generator 410 moves in one step from states 0010 and 0001 to states 0011 and 1000, respectively. Their bit-wise sum results in state 1011. This is exactly the state that should be placed in row two, column three, of the lookup table 420. [53] Using the lookup table 420, a state reachable after an arbitrary number of cycles can be found in at most n basic steps, each comprising as many as n lookups. The computational complexity of this process is thus O(n²). Let the 4-bit ring generator 410 start in state 1010. The task is to determine a state that this circuit reaches after the next 11 clock cycles. Because 11 = 2⁰ + 2¹ + 2³, three steps are needed. An immediate (after 2⁰ = 1 step) successor of state 1010 can be found by determining immediate successors of states 1000 and 0010, which are, according to the lookup table 420, states 0100 and 0011, respectively. Their sum yields state 0111. Next, this state can be decomposed into three components, look up states that can be reached from them in 2¹ = 2 steps, and find their sum, that is, 1100. Eventually, the same approach can be applied to state 1100, this time by retrieving states reachable in 2³ = 8 clock cycles from states 1000 and 0100. These states are 0101 and 1010, respectively. Hence, the final state is 1111. [54] Referring back to Fig.3, in operation 330, the result of the primitiveness test is checked to determine whether the candidate hybrid ring generator can generate a maximum length sequence. Specifically, whether the seed S occurs again the after 2ⁿ – 1 steps and whether the seed S does not occur again, for i = 1, 2, … , k, after (2ⁿ – 1)/p_i steps are checked. If the answers for both questions are yes, in operation 340, a primitive polynomial is retrieved for the candidate hybrid ring generator. The Berlekamp-Massey algorithm may be employed for this operation. If the answer for either of the questions is no, in operation 350, some of the constraints may be relaxed, primarily locations of one or more feedback Patent 202308205 taps (feedback-enable devices). In some cases, another candidate hybrid ring generator with a different degree n, a different number of feedback taps, or both needs to be selected. Then the operations 320 and 330 are repeated. [55] Following the structural approach illustrated by the flow chart 300, maximum-length hybrid ring generators can be obtained. The hybrid ring generators generated in such a way are optimal in the sense of having feedback connections (feedback lines) distributed as much uniformly as possible. They are, therefore, amenable to implementing highly modular hybrid ring generators. More importantly, these hybrid ring generators feature feedback lines alternately going up and down, which can significantly accelerate circulation of data injected into the register. The circulation speed can be measured as the number of clock cycles needed for an injected signal bit to reach every flip-flop of the ring generator at least once. Furthermore, these hybrid ring generators are lightweight compared with conventional ring generators because they are capable of using the smaller number of feedback taps than the number of terms of the deployed characteristic polynomial. Experimental data show that the XOR (feedback-enable devices) count reduction for hybrid ring generators over conventional ring generators can be as high as 7.57x, for n ≤ 256. [56] Fig.5A illustrates an example conventional 32-bit ring generator 510 that implements a primitive polynomial 520. For a ring generator, a given feedback loop, corresponding to tap x^k, is created by encompassing k adjacent flip-flops, beginning with the leftmost ones. For in Fig.5A, the first feedback loop, corresponding to the feedback tap x⁴, is created by encompassing four adjacent flip-flops 14-17; the second feedback loop, corresponding to the feedback tap x⁵, is created by encompassing five adjacent flip-flops 14-18; and the third feedback loop, corresponding to the feedback tap x⁶, is created by encompassing six adjacent flip-flops 13-18. In the figure, each of the symbols 515 for the 32-bit ring generator 510 represents a pair of two-input XOR gates (feedback-enable devices) while each of the other same symbols represents a single two-input XOR gates Patent 202308205 (feedback-enable devices). In total, the 32-bit ring generator 510 has nineteen XOR gates (feedback-enable devices), corresponding to the number of the corresponding feedback function terms in primitive polynomial 520 except terms 32 and 0. [57] Fig.5B illustrates an example 32-bit hybrid ring generator 530 and its feedback function 540 corresponding to the primitive polynomial 520 of Fig. 5A. Here, the symbols “–” and “+” are used to indicate respective tap connection directions. The 32-bit

generator 530 has only five XOR gates 533, 535 as feedback-enable devices. Compared with the conventional 32-bit ring generator 510, the reduction of feedback-enable device count is 19/5 = 3.8. The three XOR gates 533 and the two XOR gates 535 are placed alternatively on the top row and the bottom row of the 32-bit hybrid ring generator 530, respectively. As such, the upward feedback lines and the downward feedback lines not only do not cross each other but also are placed alternatively with respective to each other. Moreover, all of these upward/downward feedback lines are distributed in the ringlike structure approximately uniformly. The numbers of flip-flops between neighboring feedback lines or between a neighboring feedback line and a neighboring end of the 32-bit hybrid ring generator 530 are: 2, 2, 3, 3, 3, 3 for the top row (from left to right) and 2, 2, 3, 3, 4, 2 for the bottom row (from left to right). Thus, the numbers of two groups of flip flops on the top row or on the bottom row between any three neighboring feedback lines or between two neighboring feedback lines and their neighboring end of the 32-bit hybrid ring generator 530 are equal or differ by no more than two. Such a structure allows designers to minimize area and routing complexity, optimize wire sizing, and make the overall layout compact. [58] In some instances, instead of the original pseudorandom sequence produced by a ring generator or a linear feedback shift register, one may need to employ a sequence which is exactly the reverse of the original vector. Typically, this can be achieved by using a linear feedback shift register or a ring generator implementing a reciprocal polynomial h^*(x) of a given polynomial h(x), where h^*(x) = xⁿ h(1/x). As could be expected, given an

Patent 202308205 n-bit hybrid ring generator, one can easily obtain its reciprocal version by converting the feedback function of the hybrid ring generator the same way it is done for the conventional ring generators. Note that all feedback connections will maintain their original directions. [59] As mentioned previously, the n-bit hybrid ring generator 110 in Fig. 1 may be reprogrammed by the feedback configuration bits 170, which can also be referred to as a secret selection mask. Fig.6 illustrates an example programmable hybrid ring generator 600 that may be implemented according to various embodiments of the disclosed technology. A conventional ring generator can be configured so that it allows one to pick any primitive polynomial. However, this solution, in addition to n AND gates, requires two XOR gates interspersed between every two successive flip-flops of a lower section of the ring generator, thus slowing down the entire device. Two 2-input XOR gates in a row could be replaced with a faster 3-input XOR gate, but this would be done at a price of a 30% higher transistor count. Therefore, the solution outlined in Fig.6 offers a good trade-off between the area overhead, speed, and the number of available polynomials. [60] As can be seen in the figure, XOR logic introduces a single-gate delay (the actual speed of the circuit is also determined by the AND gates, as in other solutions of this kind). An n-bit selection mask register 610 allows one to shift-in a selection mask 620 that determines the current feedback polynomial when this unit is in operation. Successive triplets of flip-flops become destinations for signals produced by stems selected as shown in the figure. Note that a given stem may form a feedback net with a fan-out of up to three branches depending on the content of the n-bit selection mask register 610. [61] Although the n-bit selection mask register 610 may enable any of 2ⁿ – 1 feedback configurations, only a fraction of them corresponds to primitive polynomials. The number of primitive polynomials that can be used in conjunction with hybrid ring generators similar to the programmable hybrid ring generator 600 can be obtained by Patent 202308205 systematically setting all 2ⁿ – 1 feedback nets and running the primitiveness test. Clearly, programmable hybrid ring generators of sizes common to many applications can offer a multimillion-polynomial programming capability. [62] Fig. 7A illustrates an example of another type of hybrid ring generators that may be implemented according to various examples of the disclosed technology: a 24-bit hybrid ring generator 710 and its feedback function 720. Fig. 7B illustrates a 24-bit ring generator 730 and a corresponding primitive polynomial 740 which can be used to derive the 24-bit hybrid ring generator 710. The primitive polynomial 740 has nine terms, h(x) = x²⁴ + x²² + x¹⁹ + x¹⁴ + x¹² + x¹⁰ + x⁷ + x² + 1, which causes the 24-bit ring generator 730 to go through all possible 2²⁴ – 1 nonzero values before entering the seed state. If a characteristic polynomial for a ring generator could be rewritten as h(x) = x^k b(x) + b(x) + 1, where x^kb(x) and b(x) have no terms in common but b(x), then a hybrid ring generator could be set up using the feedback: f(x) = x^k b(x) – x^k + 1. Here, the symbols “–” and “+” are used to indicate respective

In the example shown in Fig. 7B, the primitive polynomial 740 can be rewritten as h(x) = x¹²b(x) + b(x) + 1, where b(x) = x¹² + x¹⁰ + x⁷ + x². Thus the 24-bit ring generator 730 can be converted into the 24-bit hybrid ring generator 710 having a characteristic polynomial, f(x) = x¹²b(x) – x¹² + 1, which is the feedback function 720, f(x) = x²⁴ + x²² + x¹⁹ +

[63] The 24-bit hybrid ring generator 710 has four XOR gates whereas the 24-bit ring generator 730 has seven XOR gates. Thus, the reduction of the XOR gate count is 1.75 times. Moreover, the 24-bit hybrid ring generator 710 corresponds to the primitive polynomial 740 and thus can also go through all possible 2²⁴ – 1 nonzero values before entering the seed state like the 24-bit ring generator 730. Accordingly, this type of hybrid ring generators is also maximal-length hybrid ring generators. [64] No matter how many terms the corresponding primitive polynomial has, the hybrid ring generator derived following the method illustrated in Figs. 7A-7B always has a single Patent 202308205 feedback connection going in the opposite direction than all the remaining feedback lines, dictated by the single term having a negative sign in the hybrid characteristic polynomial. While the XOR gate count is reduced as well, the performance of this type of hybrid ring generators may not be as good as the n-bit hybrid ring generator-based system 200 shown in Fig. 2 in terms of circulation speed of injected errors and programmability. Further, area savings achieved by the former may not be as much as the latter. [65] Fig. 8 illustrates an example of a 32-bit nonlinear sequential device 800 that may be implemented according to various examples of the disclosed technology. The 32-bit nonlinear sequential device 800 comprises 32 state elements (five of them labeled as r₀, r₁, r₂, r₃ and r₄) and 4 feedback paths comprising nonlinear devices 820-850. The 32 state elements are coupled to each other to form a 32-bit ringlike structure in a schematic diagram. Each of the nonlinear devices 820-850 is configured to implement a 5-input nonlinear function derived based on a bent function (b₁, b₂, b₃ or b₄). Every bent function (b1, b2, b3 or b4) is driven by a continuous subset of state elements on the 32-bit ringlike structure. In the nonlinear device 830, for example, the bent function b2 is driven by state elements r₁, r₂, r₃ and r₄. The fifth input of the nonlinear device 830 is the state elements r₀. The 32-bit nonlinear sequential device 800 is configured to convert an input data stream 810 into a hash value 880. The input data stream 810 may be produced by a phase shifter like the phase shifter 120 in Fig.1. The hash value 880 may be obtained by shifting out the entire content of the 32 state elements while completing a hash computation. [66] The 5-input nonlinear function belong to a type of nonlinear functions defined as follows: g(r_n, …, r₁, r₀) = b(r_n, …, r₁) + r_k r₀, k ^ [1, n], (1) where ri is an input variable provided by one of the NSL FFs, and b(rn, …, r1) is an n- input bent function, n = 4, 6, or 8. See O.S. Rothaus, “On bent functions,” Journal of Combinatorial Theory, Ser. A, vol.20, no.3, pp.300-305, May 1976. J. Seberry and X.- Patent 202308205 M. Zhang in “Highly nonlinear 0-1 balanced Boolean functions satisfying strict avalanche criterion,” Advances in Cryptography, vol.718, LNCS, Springer, pp.145-155, 1993 have shown that if a bent function b(r_n, …, r₁) assumes the value of zero 2^n-1 + 2^n/2-1 times, and a bent function b(rn, …, r1) + rk, k ^ [1, n], assumes the value of zero 2^n-1 + 2^n/2-1 times, then g(r_n, …, r₁, r₀) has the following three properties: First, g(r) is balanced, 0s as 1s over its input set; in other words, g(r) outputs both 0s and

same of 0.5 provided picking any of its input vectors is equally likely; second, g(r) is highly nonlinear as its nonlinearity Ng ^ 2ⁿ – 2^n/2; the nonlinearity of a function g is the minimum number of its truth table entries that have to change to convert g to an affine function, i.e., a linear function or its complement; and third, g(r) satisfies the strict avalanche criterion, i.e., any single input change causes the output change with the probability of 0.5. These properties are considered desirable for several cryptographic primitives, including hash functions, as they can make them less vulnerable to certain algebraic attacks. [67] The input data stream 810 for the 32-bit nonlinear sequential device 800 is injected in the middle of a segment of state elements assigned to one of the bent functions b₁, b₂, b₃, b₄. For the bent function b2, the injection location is between the state elements r2 and r3. A single injector may be allocated to a dedicated segment unless the number of injectors is greater than the number of segments. If so, some segments can be used more than once. [68] Selection of nonlinear functions g(r) may be carried out in such a way that the associated bent functions are pairwise different and they are not complements of each other. The same process can be further guided by algebraic normal forms of g(r). Consider, for example, all 3,584 functions compliant with Eq. (1) and having 5-inputs. Putting one of them into algebraic normal form yields the following expression: g(a, b, c, d, e) = d + ae + bc + de (2) Patent 202308205 It is comprised of 3 additions and 3 multiplications. The same group contains also a function whose algebraic normal form is as follows: g(a, b, c, d, e) = a + d + ac + bc + bd + be + cd + ce + de (3) It features 7 multiplications and 8 additions. Given the same number of inputs, we preferably choose functions that offer the smallest number of AND operations to enable synthesis of area-efficient hash functions. Indeed, results of logic synthesis confirm a noticeable correlation between the number of multiplications and, in a lesser extent, additions in algebraic normal form, and the resultant silicon area occupied by a given function. Moreover, simulation experiments show that both the degree and the complexity of Boolean formulas in input variables (bits of a message) representing bits of a digest, i.e., state elements of the nonlinear sequential device, depend on the number of iterations rather than the actual number of monomials a given function g(r) consists of. [69] Besides bent functions, an m-bit nonlinear sequential device can be constructed based on various other nonlinear functions. Fig.9 illustrates three simple nonlinear devices 910, 920, 930 that may be used in an m-bit nonlinear sequential device according to various examples of the disclosed technology. Each of nonlinear devices 910, 920, 930 has only three logic gates and thus can make the m-bit nonlinear sequential device compact. However, bent functions are maximally nonlinear, and an m-bit nonlinear sequential device built based on them can have better preimage resistance, secondary preimage resistance, and collision resistance. [70] Fig. 10 illustrates an example block diagram of a hashing circuit 1000 that may be implemented according to various embodiments of the disclosed technology. The hashing circuit 1000 comprises a 24-bit hybrid ring generator 1010, a phase shifter 1020, multiplexers 1030, and a 32-bit nonlinear sequential device 1040. The 24-bit hybrid ring Patent 202308205 generator 1010 belongs to the family of the n-bit hybrid ring generator 200 in Fig. 2 which can be derived following the flowchart 300 in Fig.3. Its feedback function is f(x) = x²⁴ – x²² + x²⁰ – x¹⁸ + x¹⁶ – x¹⁴ + x¹⁰ – x⁶ + x³ + 1. The 24-bit hybrid ring generator 1010 can convert a binary value 1050 into a data stream, which can then be processed by the phase shifter 1020 to remove structural dependencies. The multiplexers 1030 can select randomly and per-cycle data from the outputs of the phase shifter 1020, introducing nonlinearity. The 32-bit nonlinear sequential device 1040 can further enhance nonlinearity and output a fixed-length hash value 1060. [71] Various examples of the disclosed technology may be implemented through the execution of software instructions by a computing device, such as a programmable computer. Accordingly, Fig. 11 shows an illustrative example of a computing device 1101. As seen in this figure, the computing device 1101 includes a computing unit 1103 with a processing unit 1105 and a system memory 1107. The processing unit 1105 may be any type of programmable electronic device for executing software instructions, but it will conventionally be a microprocessor. The system memory 1107 may include both a read-only memory (ROM) 1109 and a random access memory (RAM) 1111. As will be appreciated by those of ordinary skill in the art, both the read-only memory (ROM) 1109 and the random access memory (RAM) 1111 may store software instructions for execution by the processing unit 1105. [72] The processing unit 1105 and the system memory 1107 are connected, either directly or indirectly, through a bus 1113 or alternate communication structure, to one or more peripheral devices. For example, the processing unit 1105 or the system memory 1107 may be directly or indirectly connected to one or more additional memory storage devices, such as a “hard” magnetic disk drive 1115, a removable magnetic disk drive 1117, an optical disk drive 1119, or a flash memory card 1121. The processing unit 1105 and the system memory 1107 also may be directly or indirectly connected to one or more input devices 1123 and one or more output devices 1125. The input devices 1123 may Patent 202308205 include, for example, a keyboard, a pointing device (such as a mouse, touchpad, stylus, trackball, or joystick), a scanner, a camera, and a microphone. The output devices 1125 may include, for example, a monitor display, a printer and speakers. With various examples of the computing device 1101, one or more of the peripheral devices 1115- 1125 may be internally housed with the computing unit 1103. Alternately, one or more of the peripheral devices 1115-1125 may be external to the housing for the computing unit 1103 and connected to the bus 1113 through, for example, a Universal Serial Bus (USB) connection. [73] With some implementations, the computing unit 1103 may be directly or indirectly connected to one or more network interfaces 1127 for communicating with other devices making up a network. The network interface 1127 translates data and control signals from the computing unit 1103 into network messages according to one or more communication protocols, such as the transmission control protocol (TCP) and the Internet protocol (IP). Also, the network interface 1127 may employ any suitable connection agent (or combination of agents) for connecting to a network, including, for example, a wireless transceiver, a modem, or an Ethernet connection. Such network interfaces and protocols are well known in the art, and thus will not be discussed here in more detail. [74] It should be appreciated that the computing device 1101 is illustrated as an example only, and it is not intended to be limiting. Various embodiments of the disclosed technology may be implemented using one or more computing devices that include the components of the computing device 1101 illustrated in Fig. 11, which include only a subset of the components illustrated in Fig. 11, or which include an alternate combination of components, including components that are not shown in Fig.11. For example, various embodiments of the disclosed technology may be implemented using a multi-processor computer, a plurality of single and/or multiprocessor computers arranged into a network, or some combination of both. Patent 202308205 Conclusion [75] Having illustrated and described the principles of the disclosed technology, it will be apparent to those skilled in the art that the disclosed embodiments can be modified in arrangement and detail without departing from such principles. In view of the many possible embodiments to which the principles of the disclosed technologies can be applied, it should be recognized that the illustrated embodiments are only preferred examples of the technologies and should not be taken as limiting the scope of the disclosed technology. Rather, the scope of the disclosed technology is defined by the following claims and their equivalents. We therefore claim as our disclosed technology all that comes within the scope and spirit of these claims.

Claims

Patent 202308205 What is claimed is: 1. A hashing circuit configured to convert a binary value into a hash value, comprising: an n-bit hybrid ring generator configured to implement a primitive polynomial of degree n, the n-bit hybrid ring generator comprising n state elements coupled to each other to form an n- bit ringlike structure in a schematic diagram, k feedback-enable devices, and injection devices configured to inject bits of the binary value into the n-bit ringlike structure, the n-bit ringlike structure having a top row and a bottom row, each of the top row and the bottom row having at least one of the n state elements and at least one of the k feedback-enable devices, each of the k feedback-enable devices coupled to a state element on a different row through one of k feedback lines; a phase shifter coupled to outputs of the n-bit hybrid ring generator; and an m-bit nonlinear sequential device coupled to outputs of the phase shifter, the m-bit nonlinear sequential device comprising m state elements coupled to each other to form an m-bit ringlike structure in a schematic diagram and one or more feedback paths comprising nonlinear devices, each of the nonlinear devices configured to implement a nonlinear function converting bits from outputs of some of the m state elements into a bit. 2. The hashing circuit recited in claim 1, further comprising: a plurality of 2-to-1 multiplexers inserted between the phase shifter and the m-bit nonlinear sequential device, select inputs for the plurality of 2-to-1 multiplexers being coupled to outputs of state elements in the m state elements. Patent 202308205 3. The hashing circuit recited in claim 1, wherein numbers of state elements in the n state elements placed on the top row and the bottom row are equal or differ by one, numbers of feedback-enable devices in the k feedback-enable devices placed on the top row and the bottom row are equal or differ by one, k is greater than 2, none of the k feedback lines cross each other, and feedback lines coupled to feedback-enable devices on the top row and feedback lines coupled to feedback-enable devices on the bottom row are placed alternatively with respective to each other. 4. The hashing circuit recited in claim 3, wherein the k feedback lines are distributed such that numbers of two groups of state elements on the top row or on the bottom row between any three neighboring feedback lines or between two neighboring feedback lines and their neighboring end of the ringlike structure are equal or differ by no more than two. 5. The hashing circuit recited in claim 1, wherein the n-bit hybrid ring generator further comprises: feedback path selection storage devices; and feedback path selection logic devices, wherein the feedback path selection storage devices and the feedback path selection logic devices are configured to enable the n-bit hybrid ring generator to implement one of a plurality Patent 202308205 of primitive polynomials of degree n based on feedback configuration bits stored in the storage devices. 6. The hashing circuit recited in claim 1, wherein the n-bit hybrid ring generator is configured to receive an initial value before the circuit starts to convert the binary value into the hash value. 7. The hashing circuit recited in claim 1, wherein the nonlinear function is a derivative of bent function, the derivative of bent function being a balanced Boolean function. 8. The hashing circuit recited in claim 1, wherein each of the nonlinear devices comprises: a bent function device configured to implement a bent function receiving bits at the outputs for the plurality of state elements; an AND gate, inputs of the AND gate being coupled to an output of the bent function device and one of the outputs for the plurality of state elements; and circuitry configured to combine output of the bent function device with output of the AND gate into a bit and to inject the bit into the m-bit ringlike structure.

Patent 202308205 9. The hashing circuit recited in claim 1, wherein the nonlinear function-based device is configured to receive an initial value before the circuit starts to convert the binary value into the hash value. 10. The hashing circuit recited in claim 1, wherein the n state elements and the m state elements are flip-flops, the k feedback-enable devices and the injection devices are XOR gates, and the phase shifter comprises XOR gates. 11. One or more computer-readable media storing computer-executable instructions for causing a computer to perform a method, the method comprising: creating a hashing circuit in a circuit design, the hashing circuit comprising: an n-bit hybrid ring generator configured to implement a primitive polynomial of degree n, the n-bit hybrid ring generator comprising n state elements coupled to each other to form an n- bit ringlike structure in a schematic diagram, k feedback-enable devices, and injection devices configured to inject bits of the binary value into the n-bit ringlike structure, the n-bit ringlike structure having a top row and a bottom row, each of the top row and the bottom row having at least one of the n state elements and at least one of the k feedback-enable devices, each of the k feedback-enable devices coupled to a state element on a different row through one of k feedback lines; a phase shifter coupled to outputs of the n-bit hybrid ring generator; and Patent 202308205 an m-bit nonlinear sequential device coupled to outputs of the phase shifter, the m-bit nonlinear sequential device comprising m state elements coupled to each other to form an m-bit ringlike structure in a schematic diagram and one or more feedback paths comprising nonlinear devices, each of the nonlinear devices configured to implement a nonlinear function converting bits from outputs of some of the m state elements into a bit. 12. The one or more computer-readable media recited in claim 11, wherein the hashing circuit further comprises: a plurality of 2-to-1 multiplexers inserted between the phase shifter and the m-bit nonlinear sequential device, select inputs for the plurality of 2-to-1 multiplexers being coupled to outputs of state elements in the m state elements. 13. The one or more computer-readable media recited in claim 11, wherein numbers of state elements in the n state elements placed on the top row and the bottom row are equal or differ by one, numbers of feedback-enable devices in the k feedback-enable devices placed on the top row and the bottom row are equal or differ by one, k is greater than 2, none of the k feedback lines cross each other, and feedback lines coupled to feedback-enable devices on the top row and feedback lines coupled to feedback-enable devices on the bottom row are placed alternatively with respective to each other. Patent 202308205 14. The one or more computer-readable media recited in claim 13, wherein the k feedback lines are distributed such that numbers of two groups of state elements on the top row or on the bottom row between any three neighboring feedback lines or between two neighboring feedback lines and their neighboring end of the ringlike structure are equal or differ by no more than two. 15. The one or more computer-readable media recited in claim 11, wherein the n-bit hybrid ring generator further comprises: feedback path selection storage devices; and feedback path selection logic devices, wherein the feedback path selection storage devices and the feedback path selection logic devices are configured to enable the n-bit hybrid ring generator to implement one of a plurality of primitive polynomials of degree n based on feedback configuration bits stored in the storage devices. 16. The one or more computer-readable media recited in claim 11, wherein the n-bit hybrid ring generator is configured to receive an initial value before the circuit starts to convert the binary value into the hash value.

Patent 202308205 17. The one or more computer-readable media recited in claim 11, wherein the nonlinear function is a derivative of bent function, the derivative of bent function being a balanced Boolean function. 18. The one or more computer-readable media recited in claim 11, wherein each of the nonlinear devices comprises: a bent function device configured to implement a bent function receiving bits at the outputs for the plurality of state elements; an AND gate, inputs of the AND gate being coupled to an output of the bent function device and one of the outputs for the plurality of state elements; and circuitry configured to combine output of the bent function device with output of the AND gate into a bit and to inject the bit into the m-bit ringlike structure. 19. The one or more computer-readable media recited in claim 11, wherein the nonlinear function-based device is configured to receive an initial value before the circuit starts to convert the binary value into the hash value. 20. The one or more computer-readable media recited in claim 11, wherein the n state elements and the m state elements are flip-flops, the k feedback-enable devices and the injection devices are XOR gates, and the phase shifter comprises XOR gates.