US5623545A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic data generation for self-test of cryptographic hash algorithms in personal security devices
Assignee: National Semiconductor Corp
•
Filing: 1995-08-31
•
Granted: 1997-04-22
•
Expires: 2015-08-31
Abstract
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).
Inventors
- 👤 Matthew H. Childs
- 👤 Thomas M. Norcross
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 08:42
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/06; H04L9/0643; H04L2209/00; H04L2209/12; H04L2209/125; H04L2209/26
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
182 words
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.
Claim 2
Independent Claim
182 words
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.
Claim 3
Dependent Claim
16 words
A method of testing a hash circuit as in claim 1, wherein M=512, E=2056, and H=160.
Claim 4
Dependent Claim
34 words
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.
Claim 5
Dependent Claim
34 words
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.
Claim 6
Dependent Claim
85 words
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.
Claim 7
Dependent Claim
36 words
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}.
Claim 8
Dependent Claim
107 words
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}.
Claim 9
Dependent Claim
36 words
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}.
Claim 10
Dependent Claim
33 words
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.
Claim 11
Dependent Claim
20 words
A method of testing a hash circuit as in claim 9, wherein the hash circuit implements a Secure Hash Algorithm.
Claim 12
Dependent Claim
43 words
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.
Claim 13
Dependent Claim
111 words
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.
Claim 14
Dependent Claim
45 words
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.
Claim 15
Dependent Claim
43 words
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.
Claim 16
Dependent Claim
124 words
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.
Claim 17
Dependent Claim
32 words
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.
Claim 18
Dependent Claim
42 words
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.
Claim 19
Dependent Claim
40 words
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.
Claim 20
Dependent Claim
25 words
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.
Claim 21
Dependent Claim
31 words
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.
Claim 22
Dependent Claim
73 words
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.
References Cited (Backward Citations)
US4680539A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-04-21 | 2000-10-21 | 2001-04-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-04-21 | 2004-10-21 | 2005-04-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-04-21 | 2008-10-21 | 2009-04-22 | $7700.00 | Window Closed / Lapsed |