Authentication engine architecture and method
View Patent ↗Provided is an architecture (hardware implementation) for an authentication engine to increase the speed at which multi-loop and/or multi-round authentication algorithms may be performed on data packets transmitted over a computer network. Authentication engines in accordance with the present invention apply a variety of techniques that may include, in various applications, collapsing two multi-round authentication algorithm (e.g., SHA1 or MD5 or variants) processing rounds into one; reducing operational overhead by scheduling the additions required by a multi-round authentication algorithm in such a matter as to reduce the overall critical timing path (“hiding the ads”); and, for a multi-loop (e.g., HMAC) variant of a multi-round authentication algorithm, pipelining the inner and outer loops. In one particular example of applying the invention in an authentication engine using the HMAC-SHA1 algorithm of the IPSec protocol, collapsing of the conventional 80 SHA1 rounds into 40 rounds, hiding the ads, and pipelining the inner and outer loops allows HMAC-SHA1 to be conducted in approximately the same time as conventional SHA1.
1. An authentication engine comprising:
an inner hash engine configured to perform a multi-round authentication algorithm, wherein the multi-round authentication algorithm includes a plurality of sequential operations, the inner hash engine including:
a first N to 1 hardware adder module, and
a second N to 1 hardware adder module coupled to receive an output from the first N to 1 hardware adder module,
wherein the first N to 1 hardware adder module and the second N to 1 hardware adder module are arranged to collapse two consecutive operations in the plurality of sequential operations into a single operation;
an outer hash engine configured to perform, in hardware, an authentication algorithm on an output from the inner hash engine; and
memory configured to perform lookups for both the inner and outer hash engines.
2. The authentication engine of claim 1 , wherein the multi-round authentication algorithm is a hash algorithm.
3. The authentication engine of claim 2 , wherein the multi-round authentication algorithm is MD5.
4. The authentication engine of claim 2 , wherein the multi-round authentication algorithm is the Secure Hash Algorithm (SHA).
5. The authentication engine of claim 1 , wherein the authentication algorithm performed by the outer hash engine is the Secure Hash Algorithm (SHA).
6. The authentication engine of claim 1 , wherein the first N to 1 hardware adder module includes:
a plurality of hardware carry save adders; and
a hardware carry look-ahead adder coupled to a hardware carry save adder in the plurality of hardware carry save adders.
7. The authentication engine of claim 6 , wherein the second N to 1 hardware adder module includes:
a plurality of hardware carry save adders; and
a hardware carry look-ahead adder coupled to a hardware carry save adder in the plurality of hardware carry save adders.
8. The authentication engine of claim 7 , wherein a hardware carry save adder in the first N to 1 hardware adder receives a first non-liner function as input.
9. The authentication engine of claim 7 , wherein a hardware carry save adder in the second N to 1 hardware adder receives a second non-liner function as input.
10. The authentication engine of claim 1 , wherein the first N to 1 hardware adder receives a first non-liner function as input and the second N to 1 hardware adder receives a second non-liner function as input.
11. The authentication engine of claim 1 , wherein the inner hash engine further comprises:
a first hardware circular shifter coupled to the input of the first N to 1 adder; and
a second hardware circular shifter coupled to the output of the first N to 1 adder.
12. An authentication engine, comprising:
an inner hash engine configured to perform a modified Secure Hash Algorithm having a plurality of sequential operations, the inner hash engine including:
a first hardware adder module including a first cascade of carry save adders and a first carry look-ahead adder coupled to a last carry save adder in the first cascade of carry save adders, and
a second hardware adder module including a second cascade of carry save adders and a second carry look-ahead adder coupled to a last carry save adder in the second cascade of carry save adders,
wherein the first hardware adder module and the second hardware adder module are arranged to collapse two consecutive operations of an unmodified Secure Hash Algorithm into a single operation in the modified Secure Hash Algorithm, and
wherein the first carry look-ahead adder, the last carry save adder in the first cascade of carry save adders, the second carry look-ahead adder, and the last carry save adder in the second cascade of carry save adders are in a timing critical path; and
an outer hash engine configured to perform an authentication algorithm on an output from the inner hash engine.
13. The authentication engine of claim 12 , wherein the last carry save adder in the first cascade of carry save adders is configured to receive a first non-linear function as input.
14. The authentication engine of claim 13 , wherein the first non-liner function receives a first value for a first variable, a first value for a second variable and a first value for a third variable as input.
15. The authentication engine of claim 14 , wherein the second non-liner function receives a second value for the first variable, a second value for the second variable and a second value for the third variable as input.
16. The authentication engine of claim 12 , wherein the last carry save adder in the second cascade of carry save adders is configured to receive a second non-linear function as input.
17. The authentication engine of claim 12 , wherein the first hardware adder module receives a first value for a fourth variable and a first value for a first constant as inputs.
18. The authentication engine of claim 17 , wherein the second hardware adder module receives a second value for the fourth variable and a second value for the first constant as inputs.
19. The authentication engine of claim 18 , wherein the value of the first constant is dependent upon the position of the operation in the plurality of sequential operations being performed by the inner hash engine.