Automatic data generation for self-test of cryptographic hash algorithms in personal security devices

• US 5,623,545 A
• Filed: 08/31/1995
• Issued: 04/22/1997
• Est. Priority Date: 08/31/1995
• Status: Expired due to Term

• Current Assignee: National Semiconductor Corporation (Texas Instruments, Inc.)
• Original Assignee: National Semiconductor Corporation (Texas Instruments, Inc.)
• Inventors: Norcross, Thomas M., Childs, Matthew H.
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/521,794
• Time in Patent Office: 600 Days
• Field of Search: 380/2, 380/9, 380/28, 380/46, 380/49, 380/59, 364/717, 331/78, 324/73.1
• US Class Current: 380/2
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/26 Testing cryptographic entity, e.g. testing integrity of encryption key or encryption algorithm
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC

Abstract

According to the present invention, the solution includes the hardware hash algorithm block to automatically generate data to hash from its initialization values and to run unassisted instead of needing a continuous supply of additional input data. This approach according to the present invention solves the above shortcomings of related solutions by eliminating the need to continuously feed input data to be hashed to obtain a high fault coverage. This reduces the sizes of the firmware and test vectors necessary to test the hardware. Also, since the hardware autonomously generates new data to hash, other hardware modules can be tested in parallel. This reduces the overall test time and cost. To remove the requirement of inputting multiple fixed length sub-blocks, additional sub-blocks are created from the initial sub-block using a hardware expansion function, and the hardware continues to run unattended for some predetermined number of sub-blocks. The hash hardware can use the expansion function, W[i]=W[i-3] xor W[i-8] xor W[i-14] xor W[i-16], to expand existing data into new data, where W[i-x] originates from the initial sub-block. By utilizing the non-linear xor function, W[i] will be random data if any of W[i-3], W[i-8], W[i-14], or W[i-16] are random. This expansion function is good for achieving high fault coverage because the new W values will likely be different from the other W values that have been hashed. This expansion function is convenient to use because it is utilized by the Secure Hash Algorithm as specified by the Secure Hash Standard FIPS PUB 180 and FIPS PUB 180-1 (includes a left rotate by one bit position).

Claims

1. A method of testing a hash circuit taking T M-bit message blocks serially as input and producing an H-bit message digest as output, the hash circuit including a data expansion circuit taking the M-bit message block as input and producing an E-bit expanded message block as output, the method comprising the steps of:

(a) loading a predetermined input M-bit test message block MB(1) into the hash circuit;

for each i between 1 and T, inclusive;

(b) performing an expansion by using the data expansion circuit taking an ith M-bit test message block MB (i) as input and producing an ith E-bit expanded test message block as output;

(c) performing a hash by using the hash circuit taking the ith E-bit expanded test message block EMB (i) as input and producing an ith H-bit message digest MD(i) as output; and

(d) using the data expansion circuit taking a portion of the ith E-bit expanded test message block as input to generate;

an i+1th M-bit test message block MB (i+1) as output; and

(e) outputting, by the hash circuit, the Tth H-bit message digest.

2. A method of testing a hash circuit as in claim 1, wherein M=512, E=2056, and H=160.

3. A method of testing a hash circuit as in claim 2, wherein the hash includes a plurality of hash operations, and wherein the data expansion circuit produces a W-bit sub block per hash operation.

4. A method of testing a hash circuit as in claim 3, wherein the data expansion circuit includes bitwise exclusive ORing of two or more W-bit sub blocks to produce a future W-bit sub block.

5. A method of testing a hash circuit as in claim 4,

wherein W=32 and the hash circuit operates on 32-bit sub-blocks;

wherein each subsequent test message block MB(i+1) includes sixteen sub-blocks MB(i+1){0;

15};

wherein the expanded message block EMB(i) includes eighty 32-bit expanded sub-blocks EMB(i){0;

79};

wherein the data expansion circuit performs step (d) by performing the following,

for t=64 through 79,

performing a bitwise logical expansion operation to produce the subsequent message block t-64th sub block MB(i+1){t-64} by bitwise exclusive ORing four previously computed sub blocks.

6. A method of testing a hash circuit as in claim 5,

wherein the four previously computed sub blocks are

EMB(i){t},

EMB(i){t+2}, for t<

78, otherwise MB(i+1){t-78},

EMB(i){t+8}, for t<

72, otherwise MB(i+1){t-72}, and

EMB(i){t+13}, for t<

67, otherwise

MB(i+1){t-67}.

7. A method of testing a hash circuit as in claim 4,

wherein W=32 and the hash operation operates on 32-bit sub-blocks;

wherein each subsequent test message block MB(i+1) includes sixteen sub blocks MB(i+1){0;

15};

wherein the expanded message block EMB (i) includes eighty 32-bit expansion sub blocks EMB(i){0;

79};

wherein the data expansion circuit performs step (d) by performing the following;

for t=64 through 78,

performing a bitwise logical expansion operation to produce the subsequent message block t-64th sub block MB(i+i){t-64} by bitwise exclusive ORing four previously computed sub blocks;

for t=79,

assigning the subsequent message block t-64th sub block with the last message block sub block EMB (i){t}.

8. A method of testing a hash circuit as in claim 7,

wherein the four previously computed sub blocks are

EMB(i){t},

EMB(i){t+2}, for t<

78, otherwise MB(i+1){t-78},

EMB(i){t+8}, for t<

72, otherwise MB(i+1){t-78}, and

EMB(i){t+13}, for t<

67, otherwise

MB(i+1){t-67}.

9. A method of testing a hash circuit as in claim 8, wherein the next message block sub block MB(i+1){t-64} is left rotated by one bit position when a mode control bit is deasserted.

10. A method of testing a hash circuit as in claim 9, wherein the hash circuit implements a Secure Hash Algorithm.

11. A method of testing a hash circuit as in claim 10,

wherein the least significant bit of a test message block counter is written into the mode control bit, and

wherein the test message block counter is decremented each test message block i.

12. A method of testing a hash circuit as in claim 8, wherein the data expansion circuit comprises:

a K-deep W-bit wide first in first out register file having a load W_-- data input, a selected register output, and a register select input;

an W-bit wide bitwise XOR gate having first and second XOR inputs and producing an XOR output; and

a W-bit wide flip-flop for storing intermediate expansion data having a flip-flop input and a flip-flop output;

wherein the XOR output is connected to the flip-flop input, and the flip-flop output is connected to the first XOR input, and the second XOR input is connected to the selected register output.

13. A method of testing a hash circuit as in claim 12, wherein the data expansion circuit further comprises:

a left-shift multiplexor for selectively shifting the XOR output one bit position having a straight-through input and a left-shifted input, and producing an expansion sub block output.

14. A method of testing a hash circuit as in claim 13, wherein the data expansion, circuit further comprises:

an input multiplexor for selecting an externally supplied input or the expansion sub block output as inputs and producing the load W_-- data input.

15. A method of testing a hash circuit as in claim 12, wherein steps (b) and (d) are comprised of the steps of:

clearing the flip flop;

selecting a first register through the register select input of the K-deep register file and loading the XOR output into the flip flop;

selecting a second register through the register select input of the K-deep register file and loading the XOR output into the flip flop;

selecting a third register through the register select input of the K-deep register file and loading the XOR output into the flip flop; and

selecting a fourth register through the register select input of the K-deep register file and loading the XOR output into the last location of the K-deep register file.

16. A method of testing a hash circuit as in claim 1, further comprising the step of:

comparing the Tth H-bit message digest to a known correct answer to determine a test result.

17. A method of testing a hash circuit as in claim 1, further comprising, prior to step (a), the steps of:

setting an auto-test control bit;

loading T-1 into a test message block counter; and

loading five initialization constants into an H register.

18. A method of testing a hash circuit as in claim 17, wherein step (a) includes the step of:

for j=0 to 15;

loading a jth 32-bit test message block sub-block M_j (1) into a hash circuit data storage unit.

19. A method of testing a hash circuit as in claim 18, wherein the hash circuit data storage unit is a sixteen-deep 32-bit wide first-in-first-out buffer.

20. A method of testing a hash circuit as in claim 19, wherein the hash circuit data storage unit is used to store a current W value and 15 future W values.

21. A method of testing a hash circuit as in claim 20, wherein step (c) includes the steps of:

reading the current W value and one or more future W values from the hash circuit data storage unit;

performing a bitwise logical XOR on the current W value and the one or more future W values to produce an expansion W value;

writing the expansion W value into the hash circuit data storage unit.