SHA-2 Acceleration Meeting the Needs of Emerging Applications: A Comparative Survey <s> 6) QUASI-PIPELINING <s> Hash functions are an important cryptographic primitive. They are used to obtain a fixed-size fingerprint, or hash value, of an arbitrary long message. We focus particularly on the class of dedicated hash functions, whose general construction is presented; the peculiar arrangement of sequential and combinational units makes the application of pipelining techniques to these constructions not trivial. We formalize an optimization technique called quasi-pipelining, whose goal is to optimize the critical path and thus to increase the clock frequency in dedicated hardware implementations. The SHA-2 algorithm has been previously examined by Dadda et al, with specific versions of quasi-pipelining; a full generalization of the technique is presented, along with application to the SHA-1 algorithm. Quasi-pipelining could be as well applied to future hashing algorithms, provided they are designed along the same lines as those of the SHA family. <s> BIB001 </s> SHA-2 Acceleration Meeting the Needs of Emerging Applications: A Comparative Survey <s> 6) QUASI-PIPELINING <s> In this paper, we present new techniques for collision search in the hash function SHA-0. Using the new techniques, we can find collisions of the full 80-step SHA-0 with complexity less than 239 hash operations. <s> BIB002
Quasi-pipelining is a technique aimed to introduce pipelining within the transformation round core, taking advantage of Equation (II.12) to perform data forwarding. The model has been formalised in BIB001 and can be potentially applied to any circuit which can be modeled as: • a shift register chain of n positions R i , i ∈ [1, n]; • a number of combinatorial logic functions φ i , including the identity, each of which taking as input one or more register values; • a chain of combining operations, each of which being a commutative and associative binary operator to combine the results of the φ i functions, feeding the shift register chain with the result. Two additional registers are placed at the end of the chain for the K constant and the W expanded word, with index n + 1 and n + 2 respectively. The latency of the combining operators, which for SHA-2 always coincide with the modulo addition, is assumed greater than the latency of the φ i functions, therefore the critical path runs from the R n+2 register through the combining operators chain, ending to the input of R 1 . In order to break this critical path, it may be first necessary to reorder the chain of combining operators, which is possible thanks to their commutativity and associativity properties. To this end, define the φ i block as the couple of each φ i operation and its associated combining operator.  Each φ i block is associated with an index I i constituted by the list of indices of the registers R j which feed the φ i function. The chain of combining operators can therefore be reordered by sorting the φ i blocks according to the lexicographic order of their indices. BIB002 For SHA-2, the chain is already well-ordered. The critical path can now be broken into so-called quasipipeline sections Q j , again according to the index I i of the φ i  The φ n+2 block does not include a combining operator. BIB002 I i ≺ I j if and only if I i is a prefix of I j or, possibly after a common prefix, the first differing number of I i is less than the corresponding number of I j blocks. Namely, a quasi-pipeline section includes all the φ i blocks sharing the same first number in their index I i . Quasipipelined sections are finally separated by registers. For SHA-2, the application of the quasi-pipelining technique requires the circuit to be split in two halves due to the feedback in the middle of the chain required to compute E t . The quasi-pipelining technique is then applied as graphically shown in Figure 6 and described below: The quasi-pipeline sections can be optimised by employing the delay balancing technique, letting paths shorter than the critical one be stretched without incurring any performance penalty. For example, there is no need to separate Q 3 and Q 4 , since both of them contain one modular addition, while Q 1 and Q 2 contain two modular additions. Similarly, there is no point in having Q 5 as a separate quasi-pipeline section, since it does not include any modular addition. The resulting quasi-pipeline sections are hence: Taking into account that the quasi-pipeline sections are filled in descending order, at each iteration t the quasi-pipeline section Q j computes its part of round t − q + j, where q is the total number of quasi-pipeline sections. If t < q − j, quasi-pipeline section Q j is not active, and its registers R i are not clocked in order to fill the pipeline. However, unlike usual pipelining, all the quasi-pipeline sections operate on the same input registers R i . This creates the need for data forwarding, which is allowed by the shift register configuration and the fact that the chain is lexicographically ordered. An array of selecting functions σ i , i.e. multiplexers, is therefore added to perform data forwarding and completing the circuit.