1. Field of the Invention
The present invention relates to the field of testing cryptographic hardware. Specifically, the present invention relates to achieving high fault coverage of a hardware hash function using an expansion function to automatically generate new hash test data from existing machine state.
2. Discussion of the Related Art
The Secure Hash Algorithm takes as input a variable number of 512-bit message blocks MB(i). If the message is not an exact multiple of 512-bits in length, the message is padded so that it is a multiple of 512 bits long. Padding is performed by appending a 1 and then as many zeros as are necessary to become 64 bits short of a multiple of 12. Finally, a 64-bit representation of prepadding length of the message is appended to the end. Thus, the padded message is one or more 512-bit message blocks, the first being MB(0), MB(1), . . . MB(i), etc. The Secure Hash Algorithm starts with five 32-bit variables, which are initialized as follows.
A=H0=0x67452301 PA1 B=H1=0xEFCDAB89 PA1 C=H2=0x98BADCFE PA1 D=H3=0x10325476 PA1 E=H4=0xC3D2E1F0 PA1 Wt=Mt for t=0 to 15 PA1 Wt=Wt-3XOR Wt-8 XOR Wt-14 XOR Wt-16 for t=16 to 79 PA1 Accumulator=(A&lt;&lt;&lt;5)+f(t,B,C,D)+E+Wt+Kt PA1 E=D PA1 D=C PA1 C=(B&lt;&lt;&lt;30) PA1 B=A PA1 A=Accumulator
The 512-bit message block is then expanded from sixteen 32-bit words (M0 to M15) to eighty 32-bit words (W0 through W79) using the following expansion function, in which t is the operation number from 0 to 79, and Mi represents the ith word:
The main loop of the Secure Hash Algorithm process then begins and is executed as follows, for t=0 through 79.
In the above equations the constant Kt has four different constant values, and f(t,B,C,D) implements three logic functions during the four rounds of twenty operations as shown below.
______________________________________ hash operation t Kt = f(t,B,C,D) = ______________________________________ t = 0-19 5A827999h (B&C).vertline.(.about.B&D) t = 20-39 6ED9EBA1h B XOR C XOR D t = 40-59 8F1BBCDCh (B&C).vertline.(B&D).vertline.(C&D) t = 60-79 CA62C1D6h B XOR C XOR D ______________________________________
After the eighty rounds, A, B, D, and E are added to H0, H1, H2, H3, and H4, respectively, and the respective sums replace the previous H0, H1, H2, H3, and H4, respectively. The final output message digest is 160-bit concatenation of H0, H1, H2, H3, and H4. The Secure Hash Algorithm continues with the next message block MB(i+1) until all message blocks have been processed.
A secure hash function is a critical function in data security, electronic commerce, and privacy enhanced mail systems. To optimize security these functions are implemented with hardware on a portable security token. This environment creates implementation challenges in the efficient and thorough testing in a secure manner. The objectives are to minimize the test time required to validate cryptographic hash algorithms used in personal portable security devices and to reduce the overall die size. The problem is secure devices typically need a large set of test vectors to provide the necessary fault coverage because normal test procedures such as scan or taking internal signals to pins can not be used because of a lack of security inherent in these procedures.
The related solutions were to increase chip size to facilitate the extra firmware and data storage necessary to test the hash algorithm. In manufacturing tests, the hash block was tested in a serial fashion with other hardware modules. The shortcomings are larger die size and longer test time which results in higher development costs.
Referring to FIG. 1, the field of one aspect of the present invention involves a production tester 100 performing testing on a cryptographic system (product) 102. The cryptographic system 102 is either a single integrated circuit or a system including several integrated circuits. The product 102 under test includes at least a hash function implementation 103. The hash function implementation 103 is either hardware-based, software-based, or some combination of software with special hardware support. The production tester 100 includes a pattern generating portion that produces input test vectors 105 to input to the product 102. The production tester 100 also includes a logic analyzer section for receiving output test vectors 106 from the product 102. The production tester 100 will typically run a test program 101 which includes selected values for the input test vectors 105 and the expected correct output test vectors 106 for any specific product 102. The input test vectors 105 are typically chosen so as to fully exercise the product 102. If any part of the product 102 is flawed, the output test vectors 106 will not match the precomputed expected (correct) results stored in the test program 101, and the product 102 under test will fail production testing.
FIG. 2 illustrates a typical testing procedure for production testing a hash implementation with T 512-bit test message blocks which are stored in the hash test data 104 as shown in FIG. 1. The production tester 100 at step 201 begins testing the hash implementation 103. At step 202, the tester 100 sends the first 512-bit test message block MB(1) as 16 serial 32-bit input vectors 105. At step 203, the product hashes the first message block using its hash implementation 103 to produce a message digest MD(1). Test 204 test whether the last test message block MB(T) has already been entered. If this is not the last test block T, test 204 in the test program 101 begins inputting the next test message block at step 202, through step 205. Step 205 illustrates proceeding to the next hash block, thereby repeating steps 202, 203, and 204 until the last test message block T has been processed, at which time test 204 in the test program 101 branches to the product outputting the final message digest MD(T) at step 206. During the hashing of each intermediate test message block MB(i), step 203 illustrates that each intermediate message digest MD(i) is a function of the current message block MB(i) and the previous message digest MD(i-1). Then the test program, at step 207, compares the output message digest MD(T) to the precomputed correct result PCR stored in the test program 101. If the two are equal, the product 102 passes the production hash implementation testing 208. If the two are different, the product 102 fails production testing.
There are a very large number of input permutations possible in the hash implementation. Because it is desirable to fully test the hardware hash circuitry, T is usually made to be very large. Assuming that the portion of circuitry tested during a particular hash cycle i is a random P fraction of the total hardware, then the total test coverage F fraction of the total hardware is 1-(1-P).sup.T. This means that in order to achieve a high fault coverage, the number of test message blocks T is increased. Unfortunately, however, the T test message blocks MB(1) through MB(T) are stored in the test program 101 as hash test data 104. If since P is a low number, T must be large to achieve high fault coverage, and all this test data 104 is stored in the test program 101. It is undesirable to maintain a large amount of test data 104 in the test program 101. Even if a program were written which would generate test data without requiring large data storage, it would be undesirable to occupy the input vector lines for a lengthy hash test, since this would forestall further tests which must be performed on the other parts of the product 102. Thus the total test time increases since the hash function test must occur serially with the other tests.