Extraction of a private datum to authenticate an integrated circuit

ι

EXTRACTION OF ONE! GIVEN! PRIVATE! FOR AUTHENTICATION OF AN INTEGRATED CIRCUIT

The present invention relates to the authentication of an integrated circuit or of an electronic element or sub-assembly containing such a circuit by means of an authentication procedure using secret data contained in the integrated circuit. L¹ The invention relates more particularly to authentication procedures based on the use of a private data or key (also called secret) by means of an external device. An example of application of the present invention is the field of smart cards, whether they are prepaid units of account or not.

The various methods of authenticating a smart card or the like are intended to avoid pirating or falsifying a card either by using a discreet device reproducing the card, or by hacking a reading terminal. or by large-scale reproduction of falsified smart cards.

The most efficient authentication methods use private data present in the integrated circuit to be authenticated and a so-called public data or key, depending on

0 this private data and stored in an external device. The private datum is brought into play indirectly at each need for authentication of the integrated circuit, without there being any transfer of knowledge. In processes known as without knowledge transfer (or zero-knowledge), authentication takes place according to a protocol which, in a proven manner, and under assumptions recognized as perfectly reasonable by the scientific community, does not reveal anything of the secret key of the entity whose signature is to be authenticated. Examples of known authentication methods to which the present invention applies are described in French patent application No. 2,716,058 and in US patent No. 4,995,082.

The drawback of using private data which is otherwise essential to distinguish or differentiate electronic assemblies or subassemblies, for example smart cards, from one another is that this data constitutes data stored in the component to be identified. . Such data is therefore liable to be hacked by examining the element for storing this data in the smart card, or by hacking the registers in which the data is stored, etc. The private data is also generally immutable for a given smart card in order to allow repetitive authentication of the latter. This results in a fragility of the authentication function.

In an application to prepaid smart cards (eg, telephone unit cards), if the private data is the same for an entire smart card family, this makes large scale hacks possible.

In practice, the private datum itself is not sent, but a calculation result taking into account this private datum, a number depending on a random number chosen by the integrated circuit and communicated to the external device, and a random number chosen by the external device and communicated to the card. The result is then verified by the external device to authenticate the card.

The present invention aims to improve the integrated circuit authentication procedures and systems using private data emanating from the integrated circuit.

The invention aims, more particularly, to optimize the anti-fraud security of electronic devices having recourse to an integrated circuit provided with a private datum by preventing the extraction of this private datum by various attacks of the integrated circuit.

To achieve these objects, the present invention provides a method for extracting private data in an integrated circuit participating in an authentication procedure by means of an external device taking this private data into account, the private data being generated on request and made ephemeral.

According to one embodiment of the present invention, at each generation of the private datum, a lifetime of this private datum is initialized and this datum is erased from at least a first storage element containing it, at the end of this lifespan.

According to an embodiment of the present invention, the generation of the private data item and the initialization of its lifetime are triggered by the same signal.

According to one embodiment of the present invention, the lifetime of the private data item is reduced as it is generated.

According to one embodiment of the present invention, the service life is variable.

According to one embodiment of the present invention, the private data item is obtained at least partially from a network of physical parameters.

According to an embodiment of the present invention, the network of physical parameters is programmable.

According to one embodiment of the present invention, the network of physical parameters is programmed, at least partially, by a word supplied by a storage element.

According to an embodiment of the present invention, the network of physical parameters is programmed, at least partially, by noise.

According to one embodiment of the present invention, the network of physical parameters is also controlled outside the periods of generation of the private datum.

According to an embodiment of the present invention, the private datum is obtained at least from a first datum stored in the integrated circuit and from a second datum generated on demand by the physical parameter network.

According to one embodiment of the present invention, the second data item is made ephemeral.

According to an embodiment of the present invention, the numbers of bits of the first and second data are close to each other, preferably equal.

The present invention also provides an integrated circuit, comprising means for implementing the method.

According to an embodiment of the present invention, the circuit comprises a circuit for reinitializing at least one storage element.

According to one embodiment of the present invention, the reset circuit consists of one or more delay elements initialized by a command for generating the private datum.

According to an embodiment of the present invention, the delay provided by at least one delay element of the reset circuit is variable.

These objects, characteristics and advantages, as well as others of the present invention will be explained in detail in the following description of particular embodiments given without limitation in relation to the appended figures, among which:

FIG. 1 illustrates, in the form of a flowchart, an authentication method for an integrated circuit implementing private data to which the present invention applies, FIG. 2 represents, in the form of block diagrams and in a manner very schematic, a circuit for extracting private data according to one embodiment of the present invention;

FIG. 3 represents an embodiment of a network of physical parameters of an extraction circuit according to the present invention;

FIGS. 4A and 4B illustrate, in the form of timing diagrams, the operation of the network of FIG. 3; and FIGS. 5, 6 and 7 represent three embodiments of a reset circuit of an extraction circuit according to the present invention.

The same elements have been designated by the same references in the various figures. For reasons of clarity, only the process steps and the elements of the extraction circuit which are necessary for understanding the invention have been shown in the figures and will be described below. In particular, the authentication methods and the algorithms having recourse to private data are perfectly known and will not be detailed, except as regards the supply of the private data object of the invention.

A characteristic of the present invention is not to store, permanently, the private or secret data in binary form in the integrated circuit but to generate this private data on request, that is to say during a procedure of 'authentication. The invention further provides that this private data item is ephemeral, that is to say that it is no longer detectable in the integrated circuit at the end of a predetermined time which follows its generation.

FIG. 1 represents, in the form of a simplified flowchart, an embodiment of an authentication procedure of the type to which the present invention applies. This example concerns the authentication of a smart card by an external device. In FIG. 1, we have highlighted the steps of the authentication procedure taking place on the card side C or on the reader side R.

An authentication phase naturally follows the introduction of a card in the reader, the sending of an identifier by the card to the reader or to a central, its verification by the central, then extraction by the central. a data or public key v from the identifier communicated by the card. This public key most often comes from a key table.

For the actual authentication phase, we start by drawing randomly, on the card side, a number r (block 10). This number r is stored (block 11, MEM (r)) in the integrated circuit of the card. Then, a first algorithm ALGO1 providing a result X is applied (block 12) to this number r. The result X is transmitted to the reader R which stores it (block 13, MEM (X)). On the reader side, a random number e is drawn (block 14) which is stored (block 15, MEM (e)). This number e is sent to the card C which itself stores it (block 16, MEM (e)).

The card then extracts its private data s (block 17) according to the method of the present invention. This private data item is taken into account in a second algorithm ALGO2 (block 18) with the data r and e to provide a result Y. Preferably, the number r is erased after having been used for the calculation of the number Y and before l sending the latter. The result Y is sent to the reader R which checks (block 19) by means of a third algorithm ALGO3 that the quantity X is indeed equal to the application of this algorithm to the quantities Y, e and v. The public key v is of course a function of the data or private key s of the card. Depending on the result of the consistency test, the reader provides an authentication (T) or no authentication (F) indicator to the card (block 20). The authentication procedure is then completed.

An authentication method as described in FIG. 1 is known. The invention intervenes only to provide the private data item s in a characteristic way.

The sizes of the different data are usually important to improve the security against hacking.

According to a particular embodiment, the different quantities are linked together by the following algorithms and relationships:

the public v and private keys s are linked to each other by the relation v = g ~^s modulo n, where g represents a cyclic group generator and n an integer, the first algorithm ALGO1 is X = g^r modulo n; the second ALGO2 algorithm is Y = r + es; and the third algorithm ALGO3 is X = g^Y.V^e modulo n.

Still according to this example, the different data taken into account can have the following sizes:

n, g and X each represent about 1000 bits, · r, s and Y each represent about 220 bits; and e represents about 30 bits.

It will be noted that various algorithms are known in the art and could be implemented using the method of the invention. For example, the public key v can be calculated by the reader or the central office from the identifier of the card and from data sent by the latter.

FIG. 2 represents an embodiment of a cell 1 for extracting private data in an integrated circuit according to the present invention. Cell 1 comprises a network of physical parameters (PPN) linked to the manufacture of the integrated circuit chip. This network of physical parameters 2 supplies a large number of signals and participates in the generation of the private datum s according to the invention.

A preferred embodiment of a network of physical parameters will be illustrated below in relation to FIG. 3. However, it is also possible to use a conventional network of physical parameters consisting, for example, in measuring electrical parameters. It may be, for example, a measurement of a threshold voltage of a transistor, a measurement of a resistance or a measurement of parasitic capacitance, a measurement of the current produced by a source of current, a time constant measurement (for example, an RC circuit), a measurement of an oscillation frequency, etc. As these characteristics are sensitive to technological and manufacturing process variations, it can be considered that the electrical parameter (s) taken into account are specific to manufacturing and constitute a signature of the integrated circuits resulting from this manufacturing.

In the example of a measurement of electrical parameters, these signals are converted into digital signals by means of an analog digital converter 24 (ADC) and if necessary multiplexed by a multiplexer 4 (MUX) to constitute a binary word SP2, stored in a register 25. The word SP2 is therefore sensitive to technological and manufacturing process dispersions. The converter 24 and the multiplexer 4 have been shown in dotted lines because they are optional elements. In particular, the converter 24 may be omitted in the preferred embodiment of the network of physical parameters described later in relation to FIG. 3.

Preferably, the electrical parameters measured by means of the network 2 are not always the same. Network 2 is then programmable. It is parameterized or configured for each measurement from a binary word MP, stored in a register 26. The word MP is specific to the integrated circuit chip and can be individualized from one card to another. The measurement of the physical parameters is triggered by an MES signal from a control unit 7 of cell 1.

Cell 1 preferably receives a single control signal St, triggering an extraction of the parameter s delivered on a single output terminal of cell 1.

The word SP2 is supplied to a combiner 8 also receiving a binary word SPI stored in a register 9. The role of circuit 8 is to combine the words SPI and SP2 to provide the private data item s stored in a register 10.

As a specific example of an embodiment, the combination operated by the combiner 8 can be of the type:

S = ((SP1 - SP2)² + (SP1 + SP2)²)² modulo P, where P is a k-bit prime number. The number s is then a word of k bits obtained from the words SP1 and SP2 respectively on k1 and k2 bits. Preferably, the numbers k1 and k2 of bits of words SP1 and SP2 are equal. This makes it possible to keep the equality of difficulty for a possible pirate in the event that a part (SP1 or SP2) of the word s should come to be discovered.

Like the MP number, the SP1 number is different from card to card. The combiner 8 guarantees the size of the data item s and a non-zero value. The use of data SP1 specific to the card guarantees that the private key s is unique whatever the data MP supplied to the physical parameter network to configure it. According to a simplified embodiment, for example for a circuit of reduced size, it will be possible to seek, for a given private key size, to limit the size of the physical parameter network by increasing the size of the data item SP1.

According to the invention, cell 1 also comprises a circuit 22 for resetting (resetting to zero or to one) some of its registers. The role of circuit 22 in particular is to make the presence of private data s in register 21 temporary. To guarantee optimum security, circuit 22 (Res) controls the reinitialization not only of register 21 but also of register 25 containing the data. SP2 taken from network 2. In other words, the lifespan of the private data and / or of its constituents is fixed from its generation.

An advantage of the present invention is that by combining the use of a network of physical parameters to condition at least part of the private data and a timed reset of the storage elements (for example, of the registers) storing this private data, a possible pirate is prevented from discovering the private data of the card by a visual examination, for example.

The combinations of the parameters MP and SP1 conditioning the obtaining of the private data increase the difficulty of ίο hacking. Note however that the use of a combination of the words SP1 and SP2 is optional. In a first version, it will be possible to be satisfied with directly generating the private datum from the physical parameter network and making it ephemeral thanks to the circuit 22. According to another simplified embodiment, the data MP and SP1 are combined. In this case, only one register 9 or 26 is used. It will also be possible to detect the consistency of the response of the network of physical parameters insofar as the data SP1 and SP2 are then correlated. This can make it possible, for example, to detect a copy made after pirating of the data item SP1 and reproduction of the network 2, if the technological or manufacturing process dispersions are different for the original circuit and the pirate circuit.

The circuit 22 is for example controlled by a clock CLK triggered by the control unit 7 on the arrival of a signal St for triggering the extraction of the parameter s.

According to one embodiment of the invention applied to the case where a code is entered by the user of the card, this code can be stored directly or modified in the register 9 to constitute the code SP1. In this case, circuit 22 can also reset register 9 to zero to prevent the permanent presence of code SP1 on the card. This function is illustrated by a dotted line in figure 2.

According to another variant, it is possible to add to the control of the physical parameter network a noise source (dotted lines 23). This involves providing the physical parameter network with random commands outside of authentication periods. This then makes it more difficult to hack by observing the consumption of the circuit. By keeping Network 2 running all the time, it will be more difficult for a hacker to spot when it is being used to generate a key. In addition, a hacker could consider network 2 as a simple source of analog noise used to scramble consumption, which is known per se, and therefore eliminate the contribution to consumption in his attack, including when the network is used to generate a key. The measurement signal then controls a multiplexer responsible for selecting or combining the configuration signals represented by the word MP and the bits M23 arriving on link 23. The MES signal is, for example, a trigger bit of a multiplexer 2 ′ of signals MP and M23. The noise source 23 can replace all or part of the word MP in the configuration or programming of network 2.

According to another variant, the word MP is continuously supplied to the network 2 which then spends its time generating the data item SP2. The private key s remains however generated in an ephemeral way during the combination with the data SP1. There is then even more chance that the hacker will filter the consumption response of network 2 during an attack consisting in examining the consumption of the circuit.

The realization of a network of physical parameters consisting in measuring electrical parameters present in the network in the form of resistances, parasitic capacitances or the like is not the subject of the present invention. Such an achievement is perfectly classic. It could be, for example, a network of resistors and / or switchable capacitors associated in parallel and / or in series, the switches being controlled according to the configuration signals MP and possibly M23 arriving on the network 2.

By way of networks of physical parameters, it is also possible to resort to circuits making use of a time measurement. For example, the read / write time of an EEPROM type memory is measured. An example of such a physical parameter network is described in U.S. Patent No. 5,818,738.

FIG. 3 represents the electric diagram of a preferred embodiment of a physical parameter network according to the present invention.

In this example, circuit 2 comprises a single input terminal 42 intended to receive a digital signal E for triggering a generation. For the implementation of the invention, the signal E must comprise, as will be seen below in relation to FIGS. 4A and 4B, at least one edge per identification. This could be directly the St.

Circuit 2 directly delivers a binary code B] _, B2, Bi_i, B £, ..., Bn_i, Bn over a predetermined number of bits, this code being sensitive to technological and manufacturing process variations of the circuit. Each bit B- [is output on terminal 3] _, 32, ..., 3i, ..., 3_not-i, 3_not of circuit 2 which is specific to it. Circuit 2 therefore delivers the identification code in parallel form.

Each bit B-j_ of the identification code is associated with an electrical path P ^, P2, ..., Pi ..... Pn connecting the common input terminal 42 to a terminal 3i of the same rank. Preferably, the delays provided by the different electrical paths Pi are chosen to be slightly different from one another so as to guarantee sensitivity to technological dispersions in the manufacturing process.

It can therefore already be seen that, by the various delays provided by the electrical paths, the triggering edge of the input signal E is reproduced on the various outputs at different times.

Provision is made to read the information present at the outputs of circuit 2 in a synchronized manner and at an instant corresponding, approximately, to the theoretical average delay between the various electrical paths. More precisely, according to the preferred embodiment of the invention illustrated by FIG. 3, an average electrical path 44 (CO) is provided for fixing the reading instant from the appearance of the triggering edge of the input signal. E.

For example, path 44 connects input 42 of circuit 2 to terminals Ck of flip-flops 5] _, 52, ..., 5_{i (} ..., 5_not forming part of the respective electrical paths P] _, P2, Pi, ···,

Pn and whose respective outputs Q constitute terminals 3] _, 32 / ··., 3j_, 3_not output of circuit 2. According to this embodiment, each electrical path Pi comprises a delay element (Cl), 62 (C2) ..., 6j_ (Ci) ..., 6_not (Cn) connecting the input 42 of the circuit to the input D of the corresponding latch of the path. The delay elements 6 ^ are the elements which have, according to the present invention, different delays with respect to each other. Indeed, the rockers 5j_ preferably have the same constitution. However, they participate in the delay given to the input signal up to the respective output terminals of circuit 2 with respect to the average delay CO provided by element 44.

When an edge is applied to the input signal E, this edge arrives at the respective D inputs of the flip-flops at different times. The reading of the input state of the various flip-flops is synchronized by the front of the delayed signal E, this time by element 44. It is in particular for this reason that a delay CO corresponding approximately to the delay is preferably chosen. average delay of the different elements 6i.

In the example of FIG. 3, the various outputs 3j_ of circuit 2 are individually connected to the input of a register for storing the binary code obtained, each bit corresponding to one of the outputs of the circuit. In practice, this register is register 25 of FIG. 2.

FIGS. 4A and 4B illustrate, in the form of timing diagrams and without respecting the scale, the operation of the network 2 of FIG. 3. FIGS. 4A and 4B represent examples of the shapes of the signal E, and of the signals at the output of the various delay elements. In the example of FIGS. 4A and 4B, for simplicity, the case of a binary code on four bits is considered. The chronograms have been designated by the references CO, Cl, C2, C3 and C4.

The difference between FIGS. 4A and 4B represents the difference between two circuits 1 integrated on chips from different manufactures.

In FIG. 4A, it is assumed that at an instant t5, a rising edge is triggered on the signal E. This edge appears on the various inputs of the D flip-flops (corresponding to the outputs of the delay elements C1, C2, C3 and C4) at respective different times t1, t2, t3 and t4. Furthermore, the element 44 (CO) provides a delay triggering the reading of the data at the input of the flip-flops at an instant t0. All the paths which generate a delay greater than the delay CO provide a bit at state 0 insofar as the edge of signal E has not yet reached them. All the paths which generate a delay less than the CO delay produce a bit at state 1 insofar as the edge of the signal E arrives at the input of the corresponding latch before the expiration of the CO delay. In the example of FIG. 4A, at the instant t0, the code 1010 is supplied as an identification code.

FIG. 4B illustrates the same circuit resulting from a different manufacturing process therefore giving a different chip. The code obtained is different there. For example, this is the code 0010. In FIG. 4B, an instant t5 identical to the case of FIG. 4A has been arbitrarily shown. On the other hand, the instants t'0, t'1, t'2, t'3 and t'4 at which the front of signal E has finished traversing the respective paths C0, Cl, C2, C3 and C4 are different from the case of Figure 4A.

It will be noted that the delay element C0 is itself sensitive to technological and manufacturing process dispersions. However, this has no impact on the implementation of the invention insofar as this delay represents an average delay and where the code sought is arbitrary. Indeed, for the generation of a private key, what is important is that integrated circuits resulting from the same manufacturing process provide the same code. As the delay elements are sensitive to manufacturing process dispersions, this will be the case with the implementation of the preferred embodiment of the network 2 of physical parameters.

An advantage of this embodiment is that the network 2 is particularly sensitive. In practice, the detectable difference in the delays brought about by the different paths is of the order of a picosecond. However, the dispersions of the manufacturing or technological processes most often bring about differences of the order of at least ten picoseconds.

Another advantage is that in the event of time drift of one of the delays brought by the elements, this does not affect the results of the circuit. Indeed, all the delay elements preferably being of similar constitution, the dispersion will be in the same direction for all the elements (paths).

To produce the delay elements of the electrical paths of the network of FIG. 3, any integrated elements sensitive to technological dispersions or influenced by the manufacturing process can be used. It could be, for example, a series of resistors and / or capacitors. For the resistors, we can use resistors in the thickness of the integrated circuit, but we prefer to use polycrystalline silicon resistors whose value is related to the geometry and which have 1¹ advantage of being less dependent on temperature. Of course, the retarding elements can take other forms, provided they are sensitive to technological and / or manufacturing process dispersions. In addition, the choice of the range of variation of the delays provided by the various elements depends on the application and the desired sensitivity.

An advantage of the network of physical parameters illustrated by FIG. 3 is that it avoids having to resort to an analog / digital converter 24 insofar as the binary word is directly delivered by the respective outputs of the flip-flops.

FIGS. 5 to 7 represent, schematically and partially, various embodiments of the reset circuit 22.

According to a first embodiment illustrated by FIG. 5, circuit 22 consists of several delay elements 71 (τ), 72 (τ '), 73 (τ) to differentiate the instants of reinitialization of registers 25, 9 and 21. In the example of FIG. 5, element 71 provides the delay τ for reinitializing register 25. Element 72 and element 71 with which it is in series provide the delay τ + τ 'for reinitializing register 9 . Element 73 and element 71 with which it is in series provide the delay τ + τ for resetting register 21. It can be seen that, in a simplified manner, the signal applied to delay element 71 constituting the first element of the circuit 22 may directly be the bit of the signal St which may also constitute the MES bit for controlling the physical parameter network. In this case, it suffices that the reset inputs of the various registers can be activated by the appropriate state of the St.

According to the second embodiment of FIG. 6, the MES signal is used to trigger a delay element 74 providing a minimum delay -cm. Then we add to this minimum delay, a variable delay τν supplied by an element 75 which can be configured as a function of the signal MP and, if it exists, of the noise 23. FIG. 6 also illustrates an example of control of the network of more detailed physical parameters. than in figure 2. There is included a multiplexer 76 for combining the signals MP and the noise 23 or for selecting the signal MP or the noise 23. The reading of this multiplexer is controlled by the signal MES. The output of the multiplexer delivers a configuration word in a register 77 (REG). This configuration word is used for the physical parameter network 2 proper and, according to this embodiment, for configuring the variable delay τν.

According to a third embodiment illustrated by FIG. 7, a fixed delay τ is used, supplied by an element 71. However, instead of being triggered by the appearance of the signal St, the delay τ is triggered by the setting. operation of the network of physical parameters, that is to say by the multiplexer 76 or by the register 77 (not shown in FIG. 7), or by a signal produced by the network itself. In the example of FIG. 7, the delay element 71 can of course be associated with the elements 72 and 73 of FIG. 5. More generally, the various exemplary embodiments as well as others can be provided individually or in combination.

Of course, the present invention is susceptible of various variants and modifications which will appear to those skilled in the art. In particular, although the invention has been described in relation to a particular authentication method, the latter applies whatever the authentication procedure envisaged, provided that it uses private data on the part. of the circuit to be identified.

In addition, reference has been made to storage registers which may be replaced by any suitable storage element, for example memories or parts of memory which may or may not be volatile depending on the type of data stored. In addition, the writing and reading of data in these storage elements may be serial or parallel.

Finally, provision can be made to reduce the time of presence of the private key as it is generated during a single authentication, for example during successive generations required by unsuccessful authentications. This further improves reliability by reducing the presence of the private key in the event that there is an attack aimed at detecting this key.