One approach for providing test solutions at different stages of an IC life cycle consists in including built-in self-test (BIST) resources into the DUT. Classically, storage elements are organized into scan chains and additional hardware is used for feeding the scan chains with pseudorandom test data, and sinking the test responses before analysis of the compressed signature [3]. Therefore, BIST does not provide controllability and observability of the internal storage elements from the circuit interface. However, BIST must be implemented at low cost and its efficiency must be demonstrated in terms of fault coverage and test duration.

In the next subsections, we propose dedicated built-in self-test solutions for cryptographic cores, as well as partial-BIST solutions, where the test generation is performed by the external tester while the response analysis is performed on-chip.

BISTed Cryptographic Cores

Random pattern testability of crypto-cores has been discussed in [4]. Authors show how random data and possible errors can be easily propagated through typical operations involved in encryption algorithms.

Security provided by block cipher algorithms such as DES and AES relies on two main properties named diffusion and confusion [5, 6]. Confusion refers to making the relationship between the key and the ciphertext as complex and involved as possible. Diffusion refers to the property that redundancy in the statistics of the plaintext is dissipated in the statistics of the ciphertext. For diffusion to occur, a change in a single bit of the plaintext should result in changing the value of many ciphertext bits. These properties are supported by the Feistel network [7] for the DES and by the substitution—permutation network for the AES. AES and DES also have two common characteristics. First, they are iterative algorithms. DES is composed of 16 rounds while AES is made of 10 rounds. All rounds are (quasi) identical, i.e., the result of a round is used as the input of the next round. Second, since encryption/decryption are bijective operations for a given key, each round is a bijective operation too (on a set of 2^{64} elements for DES on a set of 2^{128} elements for AES).

The diffusion property is a very interesting feature with regard to the test of their hardware implementation. It implies that every input bit of the round module influences many output bits, i.e., every input line of a round is in the logic cone of many output bits. In other words, an error caused by a fault in the body of the round is very likely to propagate to the output. Thus, the circuit is very observable. Moreover, since rounds are bijective, the input logic cone of every output contains many inputs. In other words, each fault is highly controllable. Therefore, these circuits are highly testable by nature whatever the implementations.

Example of BIST implementations are provided in [8, 9]. Figure7.2 (except for yellow area) presents a generic implementation of either AES [10] or DES [11] symmetric cryptographic algorithms. The hardware implementation is mainly composed of a key-generation module and a Round module. In mission mode, after an initial operation (XOR between Key and Plaintext for AES, and permutation of the plaintext for DES), the plaintext block is looped around the Round module several times (10 for AES, 16 for DES) before the final cipher is loaded into the output register, possibly after a final operation like the final permutation in DES. The yellow area in Fig. 7.2 depicts the required modifications to support the built-in self-test of the module itself.

Fig. 7.2 Implementation of the symmetric cryptographic algorithm

During the BIST mode, an initial message M_{1} is encrypted into M_{2} = Round(M_{1}) and the process is repeated n times (M_{i+1} = Round(M_{i}), i e{1...n}). Finally, the output data M_{n}+_{1} is stored into the output register for comparison with the expected golden value. Concerning round key generation, either the keys are precomputed and stored in the circuit or the key generation module calculates the sequence of keys. For the latter case, AES is modified in such a way that the tenth round key is used as the primary key for the next round key generation. In this way, during self-test, the key-generation module receives as many different stimuli as rounds. For DES, this is not necessary because the key-generation module does not contain any logic. The round keys are simply formed of subsets of bits of the initial key.

It has been shown that for DES, with several keys and initial input messages, after 25 encryptions (i.e., 400 clock cycles), the whole circuit (round module and control module) has always been fully tested [8]. In the same way, for AES the experiments have been repeated with different plaintexts and secret keys as starting points, obtaining test sequences ranging from 2100 to 2500 patterns [9].

Following the same principle, in [12] the authors propose a solution for the BIST of public-key cryptocores. As the modular multiplication is at the heart of many public-key algorithms, they considered the Elliptic Curve Cryptography (ECC) as the appropriate choice for the public-key cryptosystem. The key idea is to configure the multiplier such that it concurrently acts as both a test pattern generator and signature analyzer. As in the previous solution, the outputs are fed back to the inputs providing the test patterns. Concurrently, the multiplier compacts its outputs to the final signature. Experimental results showed that very high fault coverage can be obtained with a very limited number of clock cycles.