Key generation

TECHNICAL FIELD

0001This invention relates to authentication of integrated circuits.

BACKGROUND

0002Integrated circuits that are fabricated using the same lithography masks can be uniquely identified by embedding a unique identifier in the chip, such as a serial number embedded in the chip by the manufacturer. Another example of generating a unique identifier is to incorporate an array of transistors in the chip, measure the threshold voltages of the transistors in the array, and output the measurements as the identifier. For a given number of chips made from the same lithography masks, if the number of transistors in the array is large enough, the identifiers generated from the array will be unique. Due to process variations in the fabrication of the chip, no two chips will have arrays of transistors whose threshold voltages are exactly the same.

0003A unique identifier that is secretly embedded in a chip can be used to authenticate the chip. Authentication means proving to a user that the chip is not a counterfeit, or proving that certain processing results are processed by the chip and not some other chip. An example of a unique identifier is a secret key embedded in a smartcard. A card reader reads the secret key from the smartcard and compares it with a secret key previously stored in a database. If there is a match, the smartcard is authenticated, and the card reader can proceed to transact with the smartcard. The secret key needs to remain secret so that an adversary cannot duplicate the key and falsify identity.

0004An adversary may probe the chip to attempt to find the secret key using invasive methods, e.g., removal of the package and layers of the integrated circuit, or non-invasive methods, e.g., differential power analysis that attempts to determine the key by stimulating the integrated circuit chip and observing the power and ground rails. To prevent physical invasion of the chip, sensing circuitry may be included in the packaging of the chip to detect intrusion and erase sensitive information upon detection of intrusion.

0005<patcit id="pcit0001" dnum="FR2738971A1"><text>FR 2 738 971 A1</text></patcit> discloses a method and an apparatus for determining an encryption key associated with an integrated circuit having a memory plane that includes a matrix of electric contacts on it's surface and a layer of inhomogeneous electric resistivity material disposed on the matrix. An encryption key is determined by the integrated circuit on the basis of the random distribution of the electrical resistances connecting the various electric contacts of the matrix.

0006<patcit id="pcit0002" dnum="WO0049538A1"><text>WO 00/49538 A1</text></patcit> discloses an integrated circuit identification device (ICID) to be incorporated into an integrated circuit. The ICID includes an array of electronic cells in which the magnitude of an output signal of each cell is a function of randomly occurring parametric variations which vary from cell to cell. The ICID also includes a circuit for measuring the output of each cell and for producing output data having a value reflecting the particular combination of measured characteristics of all of the elements of the array. When number of elements in the array is made large enough, it is insured that to a high degree of probability, the pattern of measured array cell characteristics for an ICID embedded in any one IC will be unique and distinguishable from such patterns measured by ICIDs embedded in millions of other ICs. Thus, the value of the output data produced by the ICID circuit acts as a unique "fingerprint" for the IC in which it is installed, and can be used as a unique identification for that IC.

0007<nplcit id="ncit0001" npl-type="s"><text>Ravikanth P.S. in "Physical One-way Functions", thesis at the Massachusetts Institute of Technology, March 01, 2001, pages 1-154</text></nplcit> provides a theoretical treatise of physical one-way functions and physical one-way hash functions as primitives for physical cryptography. In this respect, he defines physical one-way functions with respect to a physical probe and physical systems in some unknown state. In this thesis, a function is called a physical one-way function if (a) there exists a deterministic physical interaction between the probe and the system which produces an output in constant time (b) inverting the function using either computational or physical means is difficult (c) simulating the physical interaction is computationally demanding and (d) the physical system is easy to make but difficult to clone.

0008Thus, according to an aspect, it is a problem to provide an easy and secure decryption of data. This problem is solved by a method and a chip having the features disclosed in claims 1 and 7, respectively. Preferred embodiments are defined in the dependent claims.

0009Patent document <patcit id="pcit0003" dnum="FR2738971A1"><text>FR 2 738 971 A1</text></patcit> discloses a method for determining an encryption key associated with an integrated circuit having a memory plane. The method comprises the steps of (a) forming a matrix of N electrical contacts Ci (i = 1, ..., N) on the surface of said memory plane, (b) depositing a layer of a material having random inhomogeneous electrical resistivity on said matrix, and (c) determining said encryption key or resistive key Kr on the basis of the random distribution of electrical resistances connecting the various electrical contacts Ci of the matrix. The method is useful for protecting smart cards used in coded television services.

SUMMARY

0010By designing an integrated circuit chip with a large set of measurable physical characteristics that are difficult to duplicate accurately, it is possible to authenticate the chip by selectively measuring a subset of the physical characteristics and comparing the measured results with pre-stored measurements. If they match, the chip is authenticated. The chip can be designed so that the number of measurable physical characteristics is sufficiently large such that it is impractical for an adversary to measure all of the physical characteristics exhaustively and store the measured results. The chip can also be configured so that it is difficult for the adversary to create a model of the chip by measuring a subset of the physical characteristics. Because the adversary cannot know in advance which subset of physical characteristics will be chosen and measured, the adversary cannot falsify the identity of the chip by producing correct measurements in response to challenges. The identity of the chip can be obtained only if the adversary is in possession of the chip. The secret key or keys to authenticating the chip is inseparable from the chip itself.

0011In general, in one aspect, the invention features a method that includes providing a first device from a group of devices fabricated based on a common design, each device having a corresponding plurality of measurable characteristics that is unique in the group to that device, each device having a measurement module for measuring the measurable characteristics. The method further includes enabling authentication of the first device by selective measurement of one or more of the plurality of measurable characteristics of the device.

0012Implementations of the invention may include one or more of the following features. Enabling authentication of the first device includes enrolling the first device by transmitting selection information to the first device, receiving from the first device response information generated by selective measurement of one of the plurality of characteristics based on the selection information, and storing the received response information in association with the first device and the selection information. Enabling authentication of the first device further includes authenticating the first device by repeating the steps of transmitting the selection information to the first device, receiving response information generated by the selective measurement of the one of the characteristics, and comparing the received response information with the stored response information.

0013Each of enrolling the first device and authenticating the first device includes selectively measuring the one of the plurality of characteristics based on the selection information and generating the measurement information. The method further includes enrolling each of the group of devices, including for each of the devices: transmitting selection information to the device that identifies a subset of the measurable characteristics, receiving from the device response information generated by selective measurement of each of the subset of measurable characteristics identified in the selection information, and storing the received response information in association with the first device and the selection information.

0014The method further includes determining a different subset of the measurable characteristics for each of the devices. Determining the different subset for each device includes randomly choosing the members of each of the subsets. The method further includes authenticating the first device, including: transmitting selection information to the first device that identifies one of the subset of measurable characteristics for the first device, receiving from the first device response information generated by selective measurement of the identified one of the subset of measurable characteristics, and comparing the received response information with the stored response information received during enrollment of the first device.

0015The method further includes fabricating the devices in the group of devices according to a common design. Fabricating the devices includes fabricating the group of devices according to a common set of lithography masks. The corresponding plurality of measurable characteristics of the devices include characteristics determined during fabrication of the devices. The characteristics determined during fabrication of the devices include uncontrolled characteristics of a fabrication process. Providing the first device from the group of devices includes providing a first integrated circuit.

0016The corresponding plurality of measurable characteristics include delay characteristics of a plurality of signal paths in the integrated circuit. The plurality of signal paths include multiple paths through each of a set of circuit components. The circuit components include passive transmission lines. The circuit components include active semiconductor elements. The active semiconductor elements include logic gates. The corresponding plurality of measurable characteristics comprise optical characteristics. The optical characteristics include reflection characteristics. The reflection characteristics include speckle patterns.

0017The number of measurable characteristics of each device may be greater than 2, 4, 16, 256, 2¹⁶, 2³² 2⁶⁴, or 2¹²⁸. Each device includes a functional component and a measurable component that have the plurality of measurable characteristics. The method further includes packaging the device in a package. The functional component and the measurable component are disposed in the package in a way such that the functional component cannot be physically accessed without altering the plurality of measurable characteristics.

0018The method further includes receiving a selection signal at the first device encoding selection information that includes an identifier, and selecting one of the plurality of measurable characteristics using the identifier. Selecting the one of the measurable characteristics includes applying a one-way function using the identifier as an argument. Applying the one-way function further uses a second identifier as an argument. The second identifier includes an identification of the device. The identification of the device includes a serial number stored in the device. The second identifier includes an identification of a personality.

0019The method further includes measuring the selected characteristic. The selected characteristic includes a delay characteristic of a selected signal path. Measuring the delay characteristic includes generating an oscillating signal using the selected delay path. Measuring the delay characteristic further includes determining a quantity related to an oscillation frequency of the oscillating signal. Determining the quantity related to the oscillation frequency includes counting a number of oscillations during a timed interval. Determining the quantity related to the oscillation frequency includes applying a phase-locked loop to the oscillating signal. Measuring the selected characteristic includes compensating for variations in the measurement of the selected characteristic due to changes in an environment of the device.

0020The method further includes measuring a reference characteristic, and computing a ratio of a measurement of the selected characteristic to a measurement of the reference characteristic. The method further includes correcting errors in a measurement of the selected characteristic. The method further includes determining response information using the measured characteristic, and transmitting a response signal from the first device encoding the response information. Determining the response information includes applying a one-way function using the measured characteristic as an argument. The method further includes providing a result signal encoding a result generated by the device, and wherein applying the one-way function further uses an argument determined from the result. The method further includes accepting code for executing an operation on a processor in the device, and wherein applying the one-way function further uses an argument determined from the code.

0021The method further includes accepting a command for execution in the device, and wherein applying the one-way function further uses an argument determined from the command. Providing the response signal includes providing an acknowledgement that the command was executed in the device. The method further includes accepting a second selection signal at the first device encoding a second identifier, measuring a second of the characteristics selected according to the second identifier, and providing a result signal encoding the measurement of the second of the characteristics. Applying the one-way function further uses an argument determined from the measurement of the second of the characteristics.

0022The method further includes receiving a selection signal at the first device encoding selection information that includes an identifier, selecting a first one of the plurality of measurable characteristics using the identifier, and selecting a second one of the plurality of measurable characteristics also using the identifier. The method further includes measuring the first selected characteristic to generate a first measurement, measuring the second selected characteristic to generate a second measurement, and comparing the first measurement to the second measurement. The method further includes generate a one-bit response according to the comparison of the first and second measurements. The method further includes generating an n-bit response by repeating n-1 times the steps of receiving a selection signal encoding selection information that includes an identifier, selecting a first one and a second one of the plurality of measurable characteristics using the identifier, measuring the first one and second one of the measurable characteristics to generate a first measurement and a second measurement, and comparing the first and second measurements to generate one bit of the n-bit response.

0023The method further includes in a first operating mode, accepting a first selection signal at the first device encoding a first identifier, applying a first one-way function using the first identifier as an argument, selecting one of the plurality of characteristic using the result of the first one-way function, measuring the selected characteristic, and providing a first response signal that encodes an identifier of the selected characteristic and the measured characteristic. In a second operating mode, accepting a second selection signal at the first device encoding a second identifier, selecting one of the plurality of characteristic using the second identifier, measuring the selected characteristic, applying a second one-way function using the measured characteristic as an argument, and providing a second response signal that encodes the result of applying the second one-way function. The second identifier is the same as the result of applying the first one-way function using the first identifier as an argument.

0024In general, in another aspect, the invention features a method that includes providing a first device from a group of devices fabricated based on a common design, each device having a corresponding plurality of measurable characteristics that is unique in the group to that device, the measurable characteristics having discrete values. The method further includes enabling authentication of the first device by selective measurement of one or more of the plurality of measurable characteristics of the device. The corresponding plurality of measurable characteristics include delay characteristics of a plurality of signal paths in the first device. The corresponding plurality of measurable characteristics include optical characteristics.

0025In general, in another aspect, the invention features a method that includes providing a first device from a group of devices fabricated based on a common design, each device having a corresponding plurality of measurable characteristics that is unique in the group to that device, each device having a processor. The method further includes selectively measuring one or more of the plurality of measurable characteristics of the first device, accepting code for executing an operation on a processor of the first device, and applying a one-way function using a first argument determined from the code.

0026Implementations of the invention may include one or more of the following features. Applying the one-way function further includes using a second argument determined from a measured characteristic. The code includes a public encryption key. The method further includes determining the second argument by using the public encryption key to encrypt a value derived from the measured characteristic. The code includes selection information that identifies a subset of the measurable characteristics. Selectively measuring one or more of the plurality of measurable characteristics includes selectively measuring each of the subset of measurable characteristics identified by the selection information. Applying the one-way function further includes using a second argument determined from the selection information. The corresponding plurality of measurable characteristics include delay characteristics of a plurality of signal paths in the first device.

0027In general, in another aspect, the invention features a method that includes providing a first device from a group of devices fabricated based on a common design, each device having a corresponding plurality of electrically measurable characteristics that is unique in the group to that device. The method further includes enabling authentication of the first device by selective measurement of one or more of the plurality of measurable characteristics of the device.

0028Implementations of the invention may include one or more of the following features. The corresponding plurality of measurable characteristics include delay characteristics of a plurality of signal paths in the first device.

0029In general, in another aspect, the invention features an apparatus that includes a device selected from a group of devices fabricated based on a common design, each device in the group having a corresponding plurality of measurable characteristics that is unique in the group to that device, the device including a measuring component that measures a selected characteristic.

0030Implementations of the invention may include one or more of the following features. The device includes an integrated circuit. The integrated circuit includes signal paths, and the plurality of measurable characteristics comprise the delay characteristics of the signal paths. The integrated circuit comprise a set of circuit components, and the signal paths include paths through each of a set of the circuit components. The device further includes a processor. The processor implements a one-way function. The device includes an array of light emitting components, an array of light detection components, and a light transmission medium that creates a speckle pattern that can be detected by the array of light detection components when one or more of the light emitting components are emitting light. The apparatus further includes a storage device to store identifiers and responses associated with the device, each identifier identifying one or more measurable characteristics, each response corresponding to one or more identifiers and is derived from one or more measurements of the measurable characteristics identified by the one or more identifiers.

0031Other features and advantages of the invention will be apparent from the description and drawings, and from the claims.

DESCRIPTION OF DRAWINGS

0032<ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">FIG. 1</figref> shows a chip that implements a physical random function (PUF).</li><li><figref idref="f0002">FIG. 2</figref> shows a process for using PUF circuits to authenticate chips.</li><li><figref idref="f0003">FIG. 3</figref> shows a PUF circuit.</li><li><figref idref="f0004">FIG. 4</figref> shows a delay circuit.</li><li><figref idref="f0004">FIGs. 5 and 6</figref> show switches used in the delay circuit of <figref idref="f0004">FIG. 4</figref>.</li><li><figref idref="f0005">FIG. 7</figref> is a timing diagram.</li><li><figref idref="f0006">FIGs. 8A</figref> and <figref idref="f0007">8B</figref> show delay circuits.</li><li><figref idref="f0008">FIG. 9</figref> shows a chip that includes a compensated PUF circuit.</li><li><figref idref="f0009">FIGs. 10 and 11</figref> show compensated PUF circuits.</li><li><figref idref="f0011">FIG. 13A</figref> shows a controlled PUF (CPUF) circuit.</li><li><figref idref="f0012">FIGs. 13B</figref> and <figref idref="f0013">14</figref> show CPUF chips.</li><li><figref idref="f0014">FIG. 30</figref> is a diagram illustrating a control algorithm.</li><li><figref idref="f0015">FIG. 31</figref> shows a program for anonymous introduction.</li><li><figref idref="f0016">FIG. 36</figref> shows a self-oscillating loop.</li><li><figref idref="f0017 f0018 f0019 f0020 f0021 f0022 f0023 f0024 f0025">FIGs. 37-45</figref> are graphs showing experimental data.</li><li><figref idref="f0026">FIGs. 46 and 47</figref> show delay circuits used in the experiment.</li><li><figref idref="f0027">FIGs. 48</figref> and <figref idref="f0028">49</figref> are graphs showing experimental data.</li><li><figref idref="f0029">FIGs. 50A</figref> and <figref idref="f0030">50B</figref> show obfuscated PUF chips.</li><li><figref idref="f0031 f0032">FIG. 51-53</figref> show PUF circuits.</li><li><figref idref="f0033">FIG. 54</figref> shows a PUF device.</li><li><figref idref="f0034">FIG 55</figref> shows a PUF circuit using a PLL to measure oscillation frequency.</li><li><figref idref="f0035">FIG. 56</figref> shows a PUF circuit.</li></ul>

0033Like reference symbols in the various drawings indicate like elements.

DETAILED DESCRIPTION

IC implemented PUF

0034Referring to <figref idref="f0001">FIG. 1</figref>, a semiconductor integrated circuit (referred to below as an "IC" or a "chip") 50 includes a functional module 52 and a physical random function (also called a physical unknown function, or "PUF") circuit 100. Chip 50 is a specific instance of a chip that has been fabricated according to a chip design, for example, according to a set of lithography masks, for the chip.

0035PUF circuit 100 is an implementation of a physical random function (PUF) that maps an input to an output in a way that is difficult to predict based on the design of the chip, such as based on a lithography mask for fabricating the chip, or based on a non-destructive physical inspection of the chip. The mapping of inputs to outputs by a PUF circuit does not necessarily have to be truly "random" such that the outputs of the PUF circuit are evenly distributed among the range of all possible outputs. For example, depending on the fabrication of a particular PUF circuit, it is possible that the outputs generated by that PUF circuit are more concentrated around particular values. Functional module 52 implements a desired operation of the chip, for example by receiving data on an input line 107, processing the data, and generating a message based on the processing of the data on a message line 109.

0036PUF circuit 100 receives an input on a signal line 106 and generates an output on line 108. Each (input, output) pair is specific to chip 50 and depends on characteristics of a portion of the physical structure associated with chip 50. Different chips fabricated using the same lithography masks will in general have somewhat different physical structure, for instance due to small variations in the fabrication process. Therefore, such different chips will, in general, map the same PUF input to different outputs. As is described more fully below, the (input, output) pairs can be used to authenticate and identify chip 50 or to prove that the message is generated by a particular chip, i.e., chip 50, and not by a counterfeit chip.

0037In the description below, the term "PUF" refers to the physical random function that maps inputs to outputs, and the term "PUF circuit" refers to the circuit that implements the function. The term "PUF <i>f</i> circuit" refers to a circuit that implements a particular physical random function <i>f</i>. The term "PUF chip" refers to a chip that includes a PUF circuit.

0038Chip 50 is fabricated using a set of lithography masks that define the circuit patterns of chip 50. When the same lithography masks are used to produce a set of chips, due to slight variations in the manufacturing process, in general, no two chips are exactly alike. There will be slight variations in various parameters (e.g., length and width of conducting wires, concentration of doping regions, thickness of dielectric layers) within each chip as well as across different chips. Functional module 52 is designed to be sufficiently robust so that despite of the variations in the parameters, the functions performed by the functional module 52 remain the same for all chips made from the same set of lithography masks. PUF circuit 100, on the other hand, is designed to take advantage of the variations in the various parameters across different chips. The "function" of PUF circuit 100 is, in general, different for different chips fabricated using the same set of lithography masks. Different PUF circuits 100 fabricated using the same set of lithography masks in general map the same input to different outputs.

0039PUF circuit 100 includes a measurable component 102 and a measurement circuit 104. The function implemented by PUF circuit 100 depends on a large number of separate physical characteristics in measurable component 102 that are combined according to the input to the PUF to determine the output of the PUF. Measurement circuit 104 is designed to measure the combinations of physical characteristics to determine the output. The output may represent a processed version of the actual measurements, where the processing is designed to reduce or correct measurement errors and effects of environmental conditions, as well as to mask actual physical parameters. The individual physical characteristics are difficult to predict or measure by physical inspection of the device, and even if known, would be difficult, if not impossible, to duplicate accurately in a copy of chip 50.

Authentication

0040One application of PUF circuit 100 of chip 50 is to authenticate the identity of the chip. In this application, a subset of the possible (input, output) pairs for the PUF are first determined by providing different inputs on signal line 106 to PUF circuit 100 and recording the corresponding outputs on signal line 108. The inputs are chosen so that the PUF circuit uses a variety of combinations of the separate physical characteristics. The outputs of the PUF circuit are kept secret, as is the set of inputs that have been used.

0041At the time the identity of chip 50 is to be authenticated, one of the inputs for which a corresponding output has been recorded and kept secret is provided as an input on signal line 106 to PUF circuit 100. The output on output line 108 of PUF circuit 100 is compared with the stored corresponding output. If they match, the chip is authenticated. Such an input is termed a "challenge" and the output is termed the "response" to the challenge. In general, the challenges and responses are discrete values represented as binary numbers.

0042Upon every successful authentication of a given chip, a set of challenge-response pairs is potentially revealed to an adversary. The same challenge-response pair is preferably not reused. A database of challenge-response pairs is maintained by the person who wishes to identify the chip. This database need only cover a small subset of all the possible challenge-response pairs. If the database runs out of challenge-response pairs, new challenge-response pair may be generated from the chip using methods described later.

0043<figref idref="f0002">FIG. 2</figref> shows a process 268 that illustrates a general approach for using PUF circuits to authenticate chips. Process 268 includes the following steps: <tables id="tabl0001" num="0001"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="19mm" /><colspec colnum="2" colname="col2" colwidth="147mm" /><tbody><row><entry>Step 270:</entry><entry>A manufacturer designs chip 50 that includes PUF circuit 100. A set of lithography masks containing patterns for fabricating the chip is generated based on the chip design.</entry></row><row><entry>Step 271:</entry><entry>The manufacturer uses the set of lithography masks to fabricate n chips. Each chip contains a PUF circuit that is made from the same patterns on the lithography masks, but due to random variations in the fabrication process, have different measurable physical characteristics.</entry></row><row><entry>Step 272:</entry><entry>A set of challenge-response pairs is generated for each chip.</entry></row><row><entry>Step 273:</entry><entry>The challenge-response pairs are stored in a secure location.</entry></row><row><entry>Step 274:</entry><entry>The chips are distributed to chip owners.</entry></row><row><entry>Step 275:</entry><entry>When a chip X (one of the <i>n</i> fabricated) needs to be authenticated, a challenge response pair associated with chip X is retrieved from the secure location. The challenge is sent to the chip.</entry></row><row><entry>Step 276:</entry><entry>A response is received from the chip.</entry></row></tbody></tgroup></table></tables> Step 277: The response received from the chip is compared with the response retrieved from the secure location. If the responses match, the chip is authenticated.

0044In one example, steps 270 and 271 are performed by a manufacturer of the chips, and steps 272 to 277 are performed by an entity (e.g., a bank) who wishes to distribute the chips to its customers and later authenticate the chips to determine whether to grant access to services.

0045In another example, after the chips are fabricated, the chips are distributed to chip owners. A chip owner may create a set of challenge response pairs, and distribute the set of challenge response pairs to an end user. The end users may use the challenge response pairs received from the chip owner to generate new challenge response pairs that are known only to the end user.

0046Chip 50 can be embedded into a smartcard to allow authentication of the identity of the smartcard, allowing a card holder to gain access to services provided by a smartcard company. Each smartcard has a serial number, and the smartcard company has a set of challenge response pairs associated with each serial number. When the smartcard is presented to a card reader, the card reader selects one or more challenges based on the smartcard serial number. The challenges are sent to chip 50, which generates one or more responses and sends them back to the card reader. The card reader compares the received responses with the stored responses. If the responses match, the smartcard is authenticated, meaning that the smartcard contains a chip that is the same chip originally used to generate the challenge response pairs.

0047Chip 50 can also be used in "certified executions." An owner of chip 50 allows end users to gain access to the chip to process data and generate a computation result. The owner distributes a set of challenge-response pairs (CRPs) to an end user to allow him to gain access to the processing powers of a chip. The end user sends challenges to the chip and receives responses from the chip to verify that the computation results are indeed produced by the chip and not by some other counterfeit chip.

0048In the above smartcard and certified execution applications, an adversary may intercept the challenges and responses transmitted to and received from chip 50 and launch various types of attacks. This can be prevented by using control algorithms that will be described in more detail later.

0049The output of PUF circuit 100 is based on a combination of physical characteristics that are selected by the input. PUF circuit 100 is designed so that the number of combinations (or the number of possible inputs) is sufficiently large such that it is impractical for an adversary who is in possession of chip 50 to measure and store all of the (input, output) pairs exhaustively. Therefore, it is not practical for an adversary to copy the functionality of chip 50, including the functionality of PUF circuit 100, for example, by storing all the possible (input, output) pairs in the copy. As long as the subset of possible inputs that were initially used to record valid (input, output) pairs has been kept secret from the adversary, and that subset cannot be predicted by the adversary, the adversary cannot practically measure all the (input, output) pairs that would be needed to later mimic the behavior of chip 50.

0050Each combination of physical characteristics can be seen as one of a large number of "signatures" of the chip that can be used to authenticate the identity of the chip. By using variations in the chip due to fabrication process variations, it is possible to store a large number of signatures on the chip without the need to store any signature information in storage devices, such as registers or memory cells. The signatures are associated with the wiring and components of the PUF chip, which cannot be duplicated accurately, and are not stored so that it can be read out by an adversary.

0051PUF circuit 100 is designed so that it is difficult for the adversary to create a model of the PUF circuit by physical inspection or measurement of chip 50 and to later mimic the behavior of chip 50 based on such a model. The measurement of the combination of physical characteristics, in general, is a non-linear and non-monotonic function of the measurement of individual physical characteristics due to interaction among wires and devices in the chip. Even if the adversary is given complete mask information of the chip and unrestricted physical access to the chip, it is difficult for the adversary to invert the function implemented by PUF circuit 100 to obtain the parameters of the model.

0052Chip 50 is "secured" in the sense that even if the adversary has possession of the device for a certain amount of time, the probability that the adversary is able to produce a response to a rightful owner's challenge is low. Once the chip is returned to its rightful owner, the owner knows that only he has the correct responses to the selected subset of challenges stored in the secure location. The probability that someone else can generate the correct responses to falsify the identity of device is very low.

0053If the adversary uses the same lithography masks to fabricate a counterfeit chip, due to the statistical variation inherent in the manufacturing process, the probability that the counterfeit chip will produce exactly the same responses to the rightful owner's challenges as the original chip is very low. Conceptually, the adversary could fabricate a huge number of chips and make comprehensive measurements on each one in order to create and discover a counterfeit with challenge-response pairs that match the original chip, but such an approach may not be practical.

0054Related to the difficulty in predicting which inputs will be used to authenticate chip 50, it would be difficult for an adversary to predict which combinations of physical characteristics will determine the needed outputs. Also, PUF circuit 100 preferably forms combinations of the individual physical characteristic in a manner such that knowledge of the individual characteristics cannot be used to form a model of the combinations.

0055Even if the adversary probed chip 50 to obtained a number of outputs while he has possession of the chip, it would be difficult to obtain the physical characteristics of PUF circuit 100 from those outputs. Once the adversary is not in possession of the chip, it would be difficult to generate additional outputs from the outputs that the adversary obtained earlier.

0056PUF circuit 100 is also preferably designed such that an attempt to measure the physical characteristics that determine the PUF function cannot be easily performed without destroying the functionality of the PUF circuit itself and consequently destroying the characteristics to be measured.

Delay-based PUF

0057In one example of a PUF circuit 100, the physical characteristics of measurable component 102 include path delays along paths of conducting wires or traces and semiconductor components forming at least part of the circuitry of PUF circuit 100. When chips are fabricated using the same set of lithography masks, there are "random" variations in the fabrication due, for example, to process temperature and pressure variations during the manufacturing steps. The random variations in the fabrication results in random variations in the PUF circuit 100. One aspect of this random variation is that path delays for corresponding wires and devices across different chips are different. Experiments have shown that delay variations can be 5% or more. Furthermore, for the same operating conditions, these delay variations remain relatively constant for a particular chip.

0058Other factors that are related to the operating conditions of the chip, such as operating temperature or supply voltage, may also cause variations in the path delays. Such variations are addressed using compensation techniques implemented in PUF circuit 100, as is described further below.

0059There may also be variations or errors in the measurement of path delays. The measurement circuitry is designed so that it is possible to measure path delays with a sufficiently high accuracy so that the variations in path delay values are mainly attributable to variations in the fabrication process and influenced much less by measurement variations. This ensures that measurement errors and variations do not affect the ability to identify and authenticate individual chips.

0060Referring to <figref idref="f0003">FIG. 3</figref>, an example of the PUF circuit 100 is a PUF circuit 101 that uses a delay circuit 111. An input to delay circuit 111 identifies an overall delay path, which is composed of a number of separate delay paths chained together, each separate delay path made up of conducting wires or traces and semiconductor components. Because of interactions between the elements in the chain, the overall delay is not necessarily a simple function of individual delays of the elements, such as a simple sum of the delays.

0061The path delays of delay circuit 111 are measured by using delay circuit 111 to form an oscillator block 122 and measuring the oscillating frequency of the oscillator block using a counter block 123. Oscillator block 122 self-oscillates at a frequency that depends on the signal path selected by an input signal on a signal line 106, and counter block 123 counts the number of oscillations within a predetermined period of time.

0062Oscillator block 122 includes an inverter 124 that inverts the signal at one end 126 of delay circuit 111. The output of inverter 124 is connected to an input 128 of an AND gate 130. Another input 132 of AND gate 130 is connected to receive a COUNT signal. When the COUNT signal is high, the inverter 124, AND gate 130, and the selected signal path in delay circuit 111 form a negative feedback loop and self-oscillates to generate an oscillating signal on a signal line 134. The oscillation frequency varies depending on the path delay of the selected signal path.

0063Counter block 123 includes a buffer circuit 138 that is connected to signal line 134 and is used to synchronize the oscillating signal with a clock signal. An output 140 of buffer circuit 138 is connected to an input of an AND gate 142. Another input of AND gate 142 is connected to receive the COUNT signal. When the COUNT signal is high, the oscillating signal on line 134 passes through buffer circuit 138 and AND gate 142 to an output 144 of the AND gate. The rising edge of the oscillating signal is counted by counter 136 during the period that the COUNT signal remains high. The count value at the output 146 represents a measurement of the path delay of the selected signal path in delay circuit 111. A higher count value represents a lower delay, and vice versa. When the input signal represents a challenge, the count value (or a processed version of the count value) represents a response of PUF circuit 101 to the challenge.

0064Referring to <figref idref="f0004">FIG. 4</figref>, delay circuit 111 includes 128 switches 112. Delay circuit 111 receives an input signal that includes 128 bits (<i>b</i>₁ to <i>b</i>₁₂₈), each input bit controlling one of the switches 112. If <i>b</i>_i = 1, the switch is crossed (see <figref idref="f0004">FIG. 5</figref>). If <i>b</i>_i = 0, the switch is uncrossed (see <figref idref="f0004">FIG. 6</figref>). Initially, a rising edge at a point <i>x</i> on signal line 114 is forwarded to signal lines 116 and 118. The rising edges passes through switches 112, following complementary paths that depend on the input signal, until they arrive at points <i>y</i> and <i>z</i> that connect to inputs of an AND gate 120. There is a characteristic delay between a rising transition at point <i>x</i> to a rising transition at point <i>y</i> or <i>z</i>, and typically another characteristic delay for a falling transition at input <i>x</i> to a falling transition at point <i>y</i> or <i>z</i>.

0065<figref idref="f0005">FIG. 7</figref> is a timing diagram that shows the delay characteristic of delay circuit 111. Delay Δ₁ is the longer of the characteristic delay between a rising transition at point <i>x</i> and a rising transition at point <i>y</i> or <i>z</i> (here, the rising transition at point z occurs later). Delay Δ₂ is the shorter of the characteristic delay between a falling transition at point <i>x</i> to a falling transition at point <i>y</i> or <i>z</i> (here, the falling transition at point <i>y</i> occurs earlier). If the sum of delays of inverter 124 and AND gate 130 is Δ₃, the period <i>T</i> of the oscillating block 122 is Δ₁+Δ₂+2·Δ₃. In one example, the delays of inverter 124 and AND gate 130 may be different for a rising edge and a falling edge.

0066In delay circuit 111, the measurable characteristics are the path delays of the signal paths. Different input signals select different signal paths within delay circuit 111, and different path delays are measured by measurement circuit 104. Different delay circuits 111 that are fabricated using the same set of lithography masks will exhibit slightly different path delays when the same input signals are presented. Different delay circuits 111 will output different responses for the same challenge. The number of different delay circuits 111 that can be uniquely identified increases exponentially as the number of switches 112 increases.

0067Referring to <figref idref="f0006">FIG. 8A</figref>, delay circuit 160 is an alternative design for delay circuit 111 (<figref idref="f0003">FIG. 3</figref>). As in delay circuit 111, delay circuit 160 includes <i>n</i>-1 stages 162 followed by a multiplexer 184, where n is the number of bits in the challenge. Each stage 162 includes a switch block 164 and a variable-delay buffer 166. Switch block 164 includes two multiplexers 166 and 168, and four buffers 170, 172, 174, and 176. Each stage 162 has an upper path 178 and a lower path 180. At an input 182 of the delay circuit 160, a rising (or falling) edge is sent into both the upper and lower paths 178 and 180. At each stage 162, depending on the value of the challenge bit for that stage, the path of the rising (or falling) edges may or may not cross, i.e., the edge from the lower path goes to the higher path and vice versa. One of the two edges is then selected by an output multiplexer 184 to be looped back to the input 182 to induce self-oscillation.

0068There is a possibility that two delay circuits may generate the same response to a particular challenge. Two or more challenges are used each time an attempt is made to identify a chip having PUF circuit 101 so that the probability of two or more delay circuits having identical responses to all the challenges is lowered. The number of challenge-response pairs available can be increased by increasing the number of stages 162 in delay circuit 160. This is because the number of signal paths in delay circuit 160 that can be measured is exponential in the number of stages 162.

0069The delays of the overall signal paths are not independent because there is much sharing between the signal paths. By using variable-delay buffers 166, it is more difficult for an adversary to exploit such dependency. Variable-delay buffer 166 has two pairs of buffers. The first pair includes buffers 170 and 172; the second pair includes buffers 174 and 176. In each pair of buffers, one buffer is always on, while the other buffer is only activated when the path connecting to the other pair of buffers is low. The dependence between paths is more difficult to exploit because the buffer pairs add a complicated non-monotonic interaction between two edges racing through the circuit (e.g., if the path delay of one circuit element becomes longer, it is possible that the total path delay will become shorter). This prevents the adversary from solving linear equations to obtain the delays of individual delay circuit elements.

0070Delay circuit 160 in <figref idref="f0006">FIG. 8A</figref> can be improved by adding an arbiter that decides, part way through the delay paths, which of the signals in upper path 178 or lower path 180 is faster, and set a switch further down the delay paths based on that decision.

0071Referring to <figref idref="f0007">FIG. 8B</figref>, a delay circuit 1030 includes 129 stages 162 that receives a 128-bit challenge. Each stage includes a switch block 164 and a variable delay buffer 166. An upper path 178 and a lower path 180 run through the stages. An arbiter 1032 is connected to the upper and lower paths that connect two successive stages, e.g., the stages that receive the 100^th and 101^st challenge bits. Arbiter 1032 determines which of the signals on upper path 178 and lower path 180 (after the stage that receives the 100^th challenge bit) is faster, and generates an output on signal line 1036 that is sent to another stage (e.g., stage 1034 between the stages that receive the 127^th and 128^th challenge bits) down stream. The signal on line 1036 determines whether the switch block 164 in stage 1034 is crossed or uncrossed. This effectively produces a "secret challenge bit" that is unknown to an adversary.

Compensated PUFs

0072The measurable characteristics in measurable component 102 (such as path delays of the signal paths in delay circuit 160) may vary due to variations in environmental conditions, such as varying ambient temperature and power supply voltages. Optional circuitry is added to chip 50 to compensate for such variations. A PUF circuit with circuitry that compensates environmental variations will be referred to as a compensated PUF circuit.

0073Referring to <figref idref="f0008">FIG. 9</figref>, chip 50 includes a compensated PUF circuit 149 that takes the ratio of the outputs of a PUF circuit 101 and a reference circuit 148 to generate an output of the compensated PUF circuit 149. In this example, reference circuit 148 is a simple self-oscillating loop that changes oscillation frequency in proportion to the changes in the oscillation frequency of PUF circuit 101. The outputs of PUF circuit 101 and reference circuit 148 are sent to a divider 152. The ratio becomes the response of the compensated PUF circuit 149. Because PUF circuit 101 and reference circuit 148 are influenced by the environmental conditions more or less equally, the ratio generated by the divider 152 will be less affected by the environmental conditions.

0074During operation, the temperature of circuits in chip 50 increases due to resistive heating. Compensated PUF 149 is designed so that the circuits are heated uniformly during operation to ensure the stability of the ratio of the outputs of PUF circuit 101 and reference circuit 148.

0075When there are two oscillating loops that oscillate at almost the same frequency, the oscillating signals may interfere with one another so that the two signals lock onto a single oscillating frequency. Therefore, the challenge to PUF circuit 101 is selected so that the oscillation frequencies of PUF circuit 101 and reference circuit 148 are sufficiently different to prevent interference of the oscillating signals.

0076Referring to <figref idref="f0009">FIG. 10</figref>, another example of a compensated PUF circuit 149 includes two PUF circuits, 148 and 150, that receive the same input signal. The ratio of the outputs of PUF circuits 148 and 150 are used to generate an output of the compensated PUF circuit 149.

0077Referring to <figref idref="f0009">FIG. 11</figref>, yet another example of a compensated PUF 153 includes a PUF circuit 101, a register 156, and a divider 152. A first input value is sent to PUF circuit 101 to generate a first output value that is stored in register 156. A second input value is sent to PUF circuit 101 to generate a second output value. Both the first and second output values are sent to divider 152 to calculate a ratio of the two output values. The ratio becomes the output of compensated PUF 153.

0078When the changes in environmental conditions are large (e.g., variations of greater than 30 degrees in ambient temperature), using ratios of outputs may not be sufficient to suppress the influence of the environmental changes. Sets of CRPs are generated for different temperature ranges. For example, a set of CRPs are used when the temperature is between 20° C to 50° C, another set of CRPs are used when the temperature is between 45° C and 75° C, and so forth. The PUF circuit can be seen as implementing 2 or 3 different PUFs, only one of which is expressed at a time depending on the temperature.

0079Circuit aging can also change delays, but its effects are smaller than the temperature effects.

0080Changes in power supplies may also affect the outputs of PUF circuits. However, experiments have shown that as long as power supply voltages do not vary too much (the exact number depends on the particular PUF circuit used), taking ratios of outputs from different oscillating loops is sufficient to compensate for the effects from power supply variations.

Controlled PUFs

0081In an alternative version of chip 50, one or more control modules are added to limit access to the PUF circuit (e.g., 100). The PUF circuit and control modules are physically linked in a way that is difficult to separate, and the PUF circuit can only be accessed through control algorithms implemented by the control modules. The term "controlled PUF (CPUF) circuit" will be used to refer to a combination of the PUF circuit and the one or more control modules.

0082A CPUF chip can be designed so that the control modules implementing the control algorithms are protected by the physical system on which the PUF circuit is based. An attempt to circumvent the algorithms will likely lead to the alteration of the PUF circuit.

0083One type of control algorithm can be used to restrict the inputs (or challenges) that are presented to the PUF circuit, to limit the information about outputs (or responses) that is provided outside of the controlled PUF circuit, and/or to implement functionality that is to be authenticated by the PUF.

0084As shown below, in one example, by using control, a weak PUF circuit can be improved into a stronger PUF circuit that is more difficult for the adversary to tamper with. In another example, control can be used to establish a secret that is shared between the CPUF chip and a user trying to use the functionalities of the CPUF chip.

Improved PUFs

0085An adversary may try to build a model of a PUF circuit by measuring the outputs of the PUF circuit to a number of adaptively-chosen inputs. The inputs are chosen so that the input-output pairs can be used to establish a set of equations that can be solved to obtain parameters for building a model of the PUF circuit. The model can then be used to simulate and clone the PUF circuit. This can be prevented by adding control around the PUF circuit so that it is difficult for the adversary to choose a particular input that can lead to equations that are easy to solve.

0086Referring to <figref idref="f0011">FIG. 13A</figref>, a functional block diagram of an improved PUF g circuit 186 includes a PUF <i>f</i> circuit 188, an ECC module 190, a random hash module 192, and a random hash module 194. Modules 190, 192, and 194 can be implemented by stand-alone circuits or by a microprocessor running software code. A challenge of improved PUF g circuit 186 is sent to hash module 192 through a signal line 198. At the same time, redundancy information is sent to ECC module 190 to correct minor errors in the outputs of PUF <i>f</i> circuit 188. Random hash module 192 implements a one-way random hash function <i>h</i>₃, which, when applied to the challenge, generates a hash value that becomes an input that is sent to PUF <i>f</i> circuit 188 through a signal line 200. The hash value is also sent to random hash module 194 through line 205.

0087The random hash modules 192 and 194 may be implemented by hardware circuitry or software running on a microprocessor (not shown).

0088PUF <i>f</i> circuit 188 includes one or more self-oscillating loop circuits (such as the one shown in <figref idref="f0003">FIG. 3</figref>) that have oscillation frequencies dependent on the input to the PUF <i>f</i> circuit 188. PUF <i>f</i> circuit 188 outputs a particular count value on a signal line 202 when a particular input is received on signal line 198. The count value passes through ECC module 190, which, using the redundancy information, removes small variations in the count value due to statistical variations and inaccuracies in the measurements. ECC module 190 generates an output, which is sent to random hash module 194 through line 203. The output of ECC module 190 is passed through random hash module 194 that implements a one-way random hash function <i>h</i>₄. The output of random hash module 194 is produced on signal line 204 and represents the response of CPUF g circuit 186.

0089Small differences in the signal on line 203 will result in large differences in the output of the random hash module 194 on line 204. By using random hash module 194, it is difficult to obtain information on the underlying physical characteristics of PUF circuit 188 from the response on line 204.

0090By using ECC module 190, the same output is produced on line 203 when a particular input is sent to PUF <i>f</i> circuit 188 on line 200. This allows the same response to be produced on line 204 when the same challenge is provided on line 198 despite small variations in the measurement of the physical characteristics of PUF circuit 188. The ECC module 190 may be implemented by hardware circuitry or by software running on a microprocessor (not shown).

0091In improved PUF g circuit 186, if <i>x</i> represents the challenge, then the output of PUF <i>f</i> circuit 188 on signal line 202 can be represented as <i>f</i> (<i>h</i>₃(<i>x</i>)). Because <i>h</i>₃(<i>x</i>) is a one-way random hash function, it is difficult for the adversary to determine <i>x</i> given <i>h</i>₃(<i>x</i>). Thus, even if the adversary finds a set of inputs for the PUF <i>f</i> circuit 188 that can be used to establish a model of PUF <i>f</i> circuit 188, the improved PUF g 186 is not compromised because the adversary is unable to present those inputs to the PUF <i>f</i> 188, i.e., the adversary has no way of presenting the correct challenge <i>x</i> to generate the required input <i>h</i>₃(<i>x</i>).

0092For the CPUF g circuit 186 to be robust to physical attacks, the modules that control access to PUF <i>f</i> circuit 188 are intertwined with circuit 188 so that it is difficult for an adversary to bypass the control modules through physical probing. In particular, the adversary is prevented from reading the response of PUF <i>f</i> circuit 188 directly before it goes through the output random hash module <i>h</i>₂ 194, and from bypassing the input random module <i>h</i>₁ 192 by sending a challenge to the PUF circuit directly.

0093In the case where path delays of signal paths are the measurable physical characteristics of PUF <i>f</i> module 188, the metal wiring and devices forming the signal paths can be constructed on top of (or surrounding) random hash modules 192 and 194 and the signal lines 200 and 202 within an integrated circuit so that an adversary cannot physically access random hash modules 192 and 194 or signals lines 200 and 202 without altering the path delays of the signal paths, thereby altering the function <i>f</i>.

0094<figref idref="f0012">FIG. 13B</figref> shows an example of a chip 50 that includes a substrate 1040, a control logic layer 1042, logic and power wires layers 1044, and delay wires layer 1046. Control logic 1042 includes random hash modules 192 and 194. Control logic may also include a microprocessor (e.g., 51 in <figref idref="f0013">FIG. 14</figref>) that is used to provide other control functions. Logic and power wires layers 1044 contain power wires and other logic circuits that need to be protected. Delay wires layer 1046 includes the metal wiring and devices forming the signal paths of a PUF module.

0095The response of improved PUF g circuit 186 generated on signal line 204 can be written as <i>g</i>(<i>x</i>) = <i>h</i>₄(ECC(<i>f</i>(<i>h</i>₃(<i>x</i>))), <i>h</i>₃(<i>x</i>)). By using the random hash module 194, the output of PUF g circuit 186 will exhibit more randomness. Similar outputs generated by PUF <i>f</i> circuit 188 and ECC module 190 will be hashed to very different hash values (which becomes the output of CPUF g circuit 186). This prevents an adversary from guessing the response to one challenge by using the responses to similar challenges. Post-composing the output of PUF <i>f</i> circuit 188 with a random hash function <i>h</i>₄ and passing the output of module 192 to module 194 through line 205 make the system provably resistant to non-physical attacks, as long as enough information is extracted from the PUF circuit before running the outputs through the output random hash function. In the case of a delay circuit, a number of path delays are measured until a few hundreds of bits of information have been extracted from the system. The measurements are then passed through the random hash function <i>h</i>₂.

0096In one implementation of measuring multiple path delays, random hash function <i>h</i>₃ can be chosen so that it provides a very wide output (i.e., a large number of output bits). This output is split into many different challenges that are sent to PUF circuit 188 one at a time. The responses are concatenated and error corrected by ECC module 190 into a single response that is sent to random hash module <i>h</i>₄ 194.

Multiple personalities

0097Some users may feel uncomfortable using chips that have unique identifiers because they feel that they can be tracked. For example, in certified executions, an owner of a PUF chip who allows the PUF chip to provide computation services to one entity may not wish to be known that the same chip is providing computation services to another entity. To alleviate concerns about privacy, improved PUF g circuit 186 is designed to receive a personality number on line 197 that can be selected by the owner of the circuit. A challenge is hashed with the personality number to produce a hash value, and the hash value is used as an input to the rest of the improved PUF <i>g</i> circuit 186. This can be expressed as <maths id="math0001"><math display="block"><mi>I</mi><mi>n</mi><mi>p</mi><mi>u</mi><mi>t</mi><mo>=</mo><msub><mi>h</mi><mn>3</mn></msub><mfenced><mrow><mi>C</mi><mi>h</mi><mi>a</mi><mi>l</mi><mi>l</mi><mi>e</mi><mi>n</mi><mi>g</mi><mi>e</mi><mo>,</mo><mi mathvariant="normal"></mi><mi>P</mi><mi>e</mi><mi>r</mi><mi>s</mi><mi>o</mi><mi>n</mi><mi>a</mi><mi>l</mi><mi>i</mi><mi>t</mi><mi>y</mi></mrow></mfenced><mo>.</mo></math><img file="EP2320344B1_D0001.tif" /></maths> Different personality numbers correspond to different sets of challenge-response pairs. By using different personality numbers, the owner effectively has many different PUF circuits.

0098In certified executions, the owner may select a first personality number when improved PUF g circuit 186 is providing computation service to a first application, and select a second personality number when the improved PUF g circuit 186 is providing computation service to a second application. The first and second applications will not know that they interacted with the same improved PUF g circuit 186.

Unique ID

0099To ensure that any two PUFs are different, the actual challenge can be combined with an unique identifier, which is separate from the PUF circuit and is unique to the chip, to generate a hash value that is passed through the rest of the PUF. In improved PUF g chip 186, the identifier is generated by an identifier module 196, which can be a hard-wired circuit that generates a unique binary number. The unique identifier that is used need not be secret and can be, for example, the chip's serial number. Since no two serial numbers are the same, no two PUFs will be identical. Even if two CPUFs share the same underlying PUF <i>f</i>, there is no way for an adversary to know this since he cannot probe PUF <i>f</i> circuit 188 directly.

Feedback

0100To add more complexity to the adversary's problem, the CPUF g circuit 186 may be used multiple times to produce one response. The corrected response from one round may be fed back into the PUF circuit. After a few rounds have been completed, all their outputs may be merged together along with the challenge, the personality, and the identifier generated by identifier module 196 and passed through a random hash function to produce the overall response.

CPUF chip

0101Referring to <figref idref="f0013">FIG. 14</figref>, a semiconductor chip 48 is an implementation of a CPUF chip. Chip 48 includes a PUF circuit 100 and a microprocessor 51. PUF circuit 100 includes a measurable component 102 and a measurement circuit 104. Microprocessor 51 implements control algorithms such that the PUF circuit 100 can only be accessed by using software code that follows certain secure protocols. The software code may include code that causes microprocessor 51 to implement a functional module 52 to perform computations to generate a computation result. The software code may include code that causes microprocessor 51 to implement a control module 54 for adding control (e.g., applying random hash functions or adding encryption) to the computation results or the output of PUF circuit 100. The secure protocols requires microprocessor 54 be intertwined with the physical characteristics of measurable component 102 in such a way that any tampering with microprocessor 54 will change the output of PUF circuit 100.

Implementing multiple personalities to preserve anonymity

0102In the CPUF g circuit 186 of <figref idref="f0008">FIG. 9</figref>, a user can select different personalities for the CPUF g circuit 186 by using different numbers for the <i>PersonalitySelect</i> signal on line 197. The following describes a control algorithm for implementing selection of personalities. An owner of CPUF chip 48 (<figref idref="f0013">FIG. 14</figref>) who is trying to hide his identity is referred to as an "anonymous owner" of the CPUF chip. It is assumed that all sources of information concerning the identity of the CPUF chip's anonymous owner have been eliminated by other protocol layers. The control algorithm is designed to prevent CPUF chip 48 from leaking the anonymous owner's identity. It is assumed that there are enough people using anonymized introduction that traffic analysis (correlating the arrival of a message at a node with the departure of a message a little while later simply from timing considerations) is unusable.

0103The control algorithm is designed so that programs that are sent to CPUF chip 48 cannot freely set <i>PersonalitySelect.</i> Otherwise, those programs can put CPUF chip 48 into a known personality and defeat the purpose of having a personality selector. To implement selection of personality, the following primitive procedures are implemented by CPUF chip 48: <ul id="ul0002" list-style="bullet" compact="compact"><li><i>ChangePersonality</i>(<i>Seed</i>): This procedure changes the personality to <i>h</i>(<i>PersonalitySelect, Seed</i>), where h is a random hash function.</li><li><i>RunProg</i>(<i>Program</i>): This procedure runs the program that is given as an argument without changing <i>PersonalitySelect.</i> When a program is loaded into the CPUF chip from the outside world and run without going through <i>RunProg, PersonalitySelect</i> is set to zero, the default personality.</li><li><i>Decrypt</i>(<i>message, key</i>): This procedure is used to decrypt the message, <i>message,</i> that was encrypted with an encryption key, <i>key.</i></li><li><i>HashWithProg</i>(<i>x</i>): This procedure is used to compute <i>h</i>(<i>h</i>(<i>program</i>), <i>x</i>).</li><li><i>Hash</i>(<i>...</i>): This function is a random hash function.</li><li><i>Blind</i>(<i>message, factor</i>): This procedure is used to apply the blinding factor, <i>factor,</i> to a message, <i>message.</i> The blinding factor will be described below.</li></ul>

Choosing the Current Personality

0104When the anonymous owner of CPUF chip 48 wants to show a personality other than the CPUF chip's default personality, he intercepts all programs being sent to the CPUF chip and encapsulates them in a piece of code of his own: <pre listing-type="program-listing"> /* Select Personality Program */ ESeed = /* the personality seed encrypted with Secret */ EProgram = /* the encapsulated program encrypted with Secret */ begin program Secret = GetSecret(Challenge); Seed = Decrypt(Eseed, Secret); Program = Decrypt(EProgram, Secret); ChangePersonality(Seed); RunProg(Program); end program</pre>

0105In <i>Select Personality Program,</i> the line that appears before "begin program" is a piece of data that accompanies the program but that does not participate in the hash of the program. If <i>EProgram</i> were included in the hash, then it would not be possible to encrypt it because the encryption key would depend on the encrypted program. <i>Seed</i> is derived from <i>Eseed,</i> which is an arbitrarily selected seed value encrypted with <i>Secret. Challenge</i> is the challenge of one of the anonymous owner's CRPs.

0106By encapsulating the program in this way, the anonymous owner is able to change the personality that the CPUF is exhibiting when it runs the user's program. There is no primitive procedure to allow the user's program to determine the personality that it is using. The seed that is used with <i>ChangePersonality</i> is encrypted so the user has no way of knowing which personality he is using. The user's program is encrypted, so even by monitoring the owner's communication, the user cannot determine if the program that is being sent to the CPUF is his own program.

0107An advantage of preserving anonymity of the owner is that multiple mutually mistrusting parties can securely use the same computing device.

Anonymous introduction

0108The following describes a process for "anonymous introduction." In anonymous introduction, an owner of a CPUF chip gives a user a CRP certified by a certifier so that the user can use the CRP to perform certified executions on the CPUF chip. The owner does not want to reveal to the user which CPUF the CRP corresponds to. After anonymous introduction, the user obtains a certified CRP and can use the CRP to generate other CRPs and perform certified executions on the CPUF chip. However, the user will not be able to determine which CPUF he is using, and whether he is communicating with the same CPUF as other users or certifiers.

0109<figref idref="f0014">FIG. 30</figref> illustrates a model for anonymous introduction. A user 222 does not have CRPs for a CPUF chip 224 and would like to establish his own private list of CRPs. A certifier 232 and an owner 234 communicate with each other, owner 234 and user 222 communicate with each other, and owner 234 communicates with CPUF chip 224. The communication channels between certifier 232, owner 234, and user 222 are secure (private and authentic). The communication channel 226 between owner 234 and CPUF chip 224 is insecure. Certifier 232 and user 222 can potentially collude to determine if their CRPs are for the same CPUF chip.

0110An example of a protocol for anonymous introduction uses a procedure called "blinding," which can be explained using the following example: Alice wants Bob to sign a message for her, but she does not want Bob to know what he has signed. To do this, Alice hides the message by applying a "blinding factor." Bob receives the blinded message, signs it, and returns the signed blinded message to Alice. Alice can then remove the blinding factor without damaging Bob's signature. The resulting message is signed by Bob, but if Bob signs many messages, he cannot tell which unblinded message he signed on which occasion.

0111The protocol for anonymous introduction includes the following steps: <tables id="tabl0002" num="0002"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="18mm" /><colspec colnum="2" colname="col2" colwidth="148mm" /><tbody><row><entry>Step 300:</entry><entry>The owner of the CPUF chip collects a challenge from the certifier and the user's public key. The owner sends the program shown in <figref idref="f0015">FIG. 31</figref> to the CPUF chip.</entry></row><row><entry>Step 302:</entry><entry>The owner decrypts the output from the CPUF chip, checks the MAC, and passes <i>Mesg5</i> on to the certifier, along with a copy of the program (only the part that participates in the MAC) encrypted with the certifier's public key.</entry></row><row><entry>Step 304:</entry><entry>The certifier decrypts the program, checks that it is the official anonymous introduction program, then hashes it to calculate <i>CertSecret.</i> He can then verify that <i>Mesg4</i> is authentic with the MAC. He signs <i>Mesg4</i> and sends the result to the owner.</entry></row><row><entry>Step 306:</entry><entry>The owner unblinds the message and ends up with a signed version of <i>Mesg3.</i> He can check the signature and the MAC in <i>Mesg3</i> to make sure that the certifier is not communicating his identity to the user. He sends the unblinded message to the user. This message is in fact a version of <i>Mesg3</i> signed by the certifier.</entry></row><row><entry>Step 308:</entry><entry>The user checks the signature and decrypts <i>Mesg2</i> with his secret key to get a CRP.</entry></row></tbody></tgroup></table></tables>

0112In the above protocol, <i>UserPubKey</i> and <i>CertChallenge</i> are encrypted so that it is difficult to correlate the message that the user sends to the CPUF chip with the certifier's challenge or with the user's public key. <i>Seed</i> is encrypted to prevent the certifier or the user from knowing how to voluntarily get into the personality that the user is being shown. <i>PreChallengeSeed</i> is encrypted to prevent the certifier from finding out the newly created challenge when he inspects the program in step 304. The encryption between <i>Mesg5</i> and <i>Mesg6</i> prevents correlation of the message from the CPUF to the owner and the message from the owner to the certifier.

0113More than one layer of encapsulation may be used. An entity who has gained access to a personality of a CPUF through anonymous introduction can introduce other parties to this PUF. In particular, he can send the signed CRP that he received back to the certifier and get the certifier to act as a certifier for his personality when he anonymously introduces the CPUF to other parties.

0114CPUF chips and control algorithms can be used in, for example, smartcard applications and certified executions.

Experiment data

0115Experiments have been conducted using Xilinx XC2S200 field programmable gate arrays (FPGAs) to determine the feasibility of building PUFs that can be uniquely identified. FPGAs are fabricated in large volume, and the fabrication process is tuned to produce ICs that are as identical as possible in order to maximize yield and performance. The experiments indicate that even a highly-optimized fabrication process designed for predictability has enough variability to enable reliable identification.

0116Referring to <figref idref="f0016">FIG. 36</figref>, a self oscillating loop 236 includes a delay circuit 238 and a switching circuit 240 (enclosed in dashed lines) that is implemented by a lookup table in the FPGA. The behavior of the lookup table can be modeled by an XOR gate 241 and a multiplexer 242. A signal on line 245 is duplicated into two signals that enter delay circuit 238 and switch between an upper path 247 and a lower path 249. The signals on path 247 and 249 enter switching circuit 240 through signal lines 239 and 237, respectively. An output 251 of switching circuit 240 switches when the slower transition, either a rising edge or a falling edge, reaches its inputs through lines 237 and 239. Circuit 240 is similar to a flip-flop that changes state when both outputs from the delay circuit are at the same level.

0117A number of profiles were generated for different FPGAs in different conditions. A profile represents measurements of 128 challenge response pairs. All profiles were established using the same challenges. By comparing the differences in the responses in two profiles, a distribution of differences was obtained. If most of the differences are near zero, then the profiles are close. If the differences are far from zero, then the profiles are distant. The experiment results show that the distribution of differences was typically Gaussian. Therefore, the difference between two profiles can be characterized by a standard deviation.

0118Referring to <figref idref="f0017">FIG. 37</figref>, each line represents the differences between a first profile and a second profile. The horizontal axis represents tolerance, and the vertical axis indicates the probability that for a given challenge, the difference in response will be lower than the difference in response that is indicated on the horizontal axis. The first profile remained the same for different lines, and was obtained by measuring the responses generated by an FPGA chip called "Abe" that ran on a first test board at room temperature. For line 242, the second profile was obtained by measuring the responses generated by Abe on the first test board at room temperature for a second time. The standard deviation <i>σ</i> of the differences between the two profiles is about 1×10^-5. Since the measurements were made on the same chip on the same board under the same temperature, the results represent power supply variations of the test board over time.

0119For line 244, the second profile was obtained by measuring the responses generated by the Abe chip on a second test board at room temperature. In this case, <i>σ</i>≈2.5×10^-5. Because the measurements were performed in different test boards, the result reflects power supply variations across different test boards. For lines 246, 248, and 250, the second profile was obtained by measuring the responses from the Abe chip on the first test board at 10, 20, and 30 degrees Celsius above room temperature, respectively. In this case, <i>σ</i>≈5×10^-5 to 1.5×10^-4). For lines 252 and 254, the second profiles were obtained by measuring the responses from FPGA chips called "Hal" and "Walt", respectively, on the first test board. In these cases, <i>σ</i>≈4×10^~4. These experiments show that the difference between the profiles of two different chips on the same test board is larger than the difference between the profiles of the same chip on the same test board measured at different times, or the same chip on different test boards, or the same chip on the same test board measured at different temperatures (varying as much as 30 degrees Celsius). This demonstrates that it is possible to distinguish between different FPGAs based on measuring the delay characteristics of the chips. The data shows that each challenge is capable of providing 0.7 bits of information about the identity of the FPGA when 30-degree Celsius variations are allowed, and 1.5 bits if 10-degree Celsius variations are allowed.

0120To distinguish between 1 billion different components, a sufficient number of bits are required to identify 10¹⁸ = 2⁶⁰ components. A total of 40 to 90 challenges are required to obtain those 60 bits of information, depending on the temperature variations that are allowed. The numbers that are given here are dependent on the PUF circuit that is considered. By properly designing the layout of the circuit, it may be possible to build PUFs for which more bits can be extracted from each challenge.

0121Other experiments were conducted using FPGAs to implement PUF circuits 101 of <figref idref="f0003">FIG. 3</figref>. In the experiments, the delays across two or more FPGAs are compared. Each FPGA has exactly the same logic circuit, and the PUF circuit was implemented in the FPGAs in the exact same locations. The FPGAs can be viewed as integrated circuit chips made from the same lithography masks.

0122In one experiment, each FPGA was equipped with 8 self-oscillating loops, such as the circuit 101 in <figref idref="f0003">FIG. 3</figref>. Each loop includes 32 buffers (a logic gate that copies its input to its output with a short delay) and an inverter. The frequencies of the loops were determined by measuring the number of oscillations that occurred during a certain period of time (typically 2²⁰ cycles of an external 50 MHz oscillator). The period of the loops was on the order of 60 <i>ns.</i>

0123In the following description of the experiment results, the standard deviations are given in parts per million (ppm). A deviation of n ppm around a frequency <i>f</i>₀ corresponds to a deviation of <maths id="math0002"><math display="inline"><mfrac><mrow><mi>n</mi><mo>⋅</mo><msub><mi>f</mi><mn>0</mn></msub></mrow><msup><mn>10</mn><mn>6</mn></msup></mfrac><mo>.</mo></math><img file="EP2320344B1_D0002.tif" /></maths>

0124Referring to <figref idref="f0018">FIG. 38</figref>, a graph 472 shows histograms of measurements of four PUF circuits on different FPGAs. The horizontal axis represents delay, using an arbitrary unit. The vertical axis represents probability density. The histograms show the relationship between measurement error and inter-FPGA variation for the four different FPGAs. Each peak represents a different FPGA. The width of a peak represents measurement error. The measurements were made without compensation.

0125Referring to <figref idref="f0019">FIG. 39</figref>, a graph 474 shows histograms of measurements of four compensated PUFs on different FPGAs. The horizontal axis represents compensated measurement, each data point representing a ratio of two measurements. The vertical axis represents probability density. The histograms show the relationship between measurement error and inter-FPGA variation for the four different FPGAs. The standard deviation in inter-FPGA delays with compensated measurements ranges from 5000ppm to 30000ppm, depending on the pair of loops that was used for the measurement. The four peaks in histograms 472 and 474 shows that the inter-FPGA variation is larger than the measurement errors. This shows that is it possible to differentiate between different FPGAs despite some measurement errors.

0126Referring to <figref idref="f0020">FIG. 40</figref>, a graph 476 shows two histograms representing measurements of an oscillating loop with the other loops on the FPGA turned on or off. The horizontal axis represents time measurement, using an arbitrary unit. The vertical axis represents probability density. The influence of the other loops (as indicated by the distance between the two peaks, which is about 10 ppm) is smaller than the measurement error (as indicated by the width of the peak). Thus, interference from one loop to another should not hinder identification of a chip, as long as the two loops are not oscillating at nearby frequencies.

0127Referring to <figref idref="f0021">FIG. 41</figref>, a graph 478 shows two histograms, each representing measurements of the oscillating frequency for different power supply voltages. The horizontal axis represents power supply in volts. The vertical axis represents compensated delay. Around the FPGA's 2.5V operating point, the variation of the compensated measurement with voltage is about 3000 ppm/V. In practice, external power supply variations can be kept to within 1%, which corresponds to 1% × 2.5V × 3000ppm/V = 75ppm. Therefore, commonly available voltage regulators will suffice to keep the supply voltage within tolerable bounds. In this experiment, the compensated measurement has an extremum around 2.7V. By running the FPGAs at 2.7V instead of the rated 2.5V, the robustness of the measurements can be further improved.

0128Referring to <figref idref="f0022">Fig. 42</figref>, a graph 480 shows frequency measurement values versus time (in half-second sampling intervals) as the ambient temperature varied from 25°C to 50°C. The two FPGAs did not undergo the same temperature changes at the same time. The horizontal axis represents time (with 100 ms as unit). The vertical axis represents delay. The variation in frequency is about 50000ppm for uncompensated measurements.

0129Referring to <figref idref="f0023">FIG. 43</figref>, a graph 482 shows that with compensated measurement, the variation in frequency is reduced to 100ppm. The horizontal axis represents time (with 100 ms as unit). The vertical axis represents compensated measurement.

0130Referring to <figref idref="f0024">FIG. 44</figref>, a graph 484 shows histograms of the measurements in <figref idref="f0022">FIG. 42</figref>. The horizontal axis represents delay. The vertical axis represents probability density.

0131Referring to <figref idref="f0025">FIG. 45</figref>, a graph 486 shows histograms of the measurements in <figref idref="f0023">FIG. 43</figref>. The horizontal axis represents compensated measurement. The vertical axis represents probability density. Graphs 482 and 486 show that two FPGAs can be differentiated with compensated measurement despite a 25°C temperature variation.

0132Referring to <figref idref="f0026">FIGs. 46 and 47</figref>, an experiment was made on two PUF circuits that included a demultiplexer circuit 484 with 12 stages of demultiplexer 486. Each demultiplexer 486 switches a signal on an input 488 to one of the two outputs 490.

0133Referring to <figref idref="f0027">FIGs. 48</figref> and <figref idref="f0028">49</figref>, graphs 492 and 494 show compensated path delays measurements versus challenges for the demultiplexer circuit 484 on two different FPGAs. In each graph, the horizontal axis represents the challenge number, and the vertical axis represents compensated measurement. The graphs show that there is a dependency of the response on the challenge. The graphs show certain patterns in the relationship between challenges and responses. This pattern is common to the two FPGAs and is due to large differences between paths in given stages of the delay circuit. To see a difference between the two FPGAs, one has to look at the small scale differences between the two plots (i.e., looking for 1% variations on a plot that covers 50% variations). These differences appear in the difference in texture between the plots for the two chips.

Physically Obfuscated Keys

0134Referring to <figref idref="f0029">FIG. 50A</figref>, an example of a CPUF chip 256 uses constant values stored on the chip to generate secrets (or keys) that allows authentication of the chip or computation results of the chip. Chip 256 includes a functional module 52, a PUF circuit 100, and a control module 54. Chip 256 receives a program sent by a user through I/O port 257 that instructs functional circuit to compute a result. Chip 256 additionally includes an EEPROM 444 that stores two constant numbers, constant A and constant B, that are written into the memory after chip 256 is fabricated. Control module 54 controls a multiplexer 442 to select one of the two numbers, and uses the selected number as a prechallenge to generate a challenge that is sent to PUF circuit 100 to generate a first secret. Control module 54 uses the first secret to encrypt and sign the computation result from functional module 52 to generate a "semi-encrypted and signed" message. Signing a message means generating a MAC for the message. Control module 54 then controls multiplexer 442 to select the other of the two numbers, uses the selected number to cause PUF circuit 100 to generate a second secret. Control module 54 uses the second secret to encrypt and sign the semi-encrypted and signed message to generate a fully-encrypted and signed message, which is then output to a user of chip 256.

0135Chip 256 is designed so that the wiring of delay lines in PUF circuit 100 covers control module 54 and the output of PUF circuit 100 An adversary cannot measure the output of PUF circuit 100 unless he goes through the overlaid wiring, which will cause the physical characteristics of PUF circuit 100 to change. Even if an adversary can measure the first secret, he will not be able to obtain the second secret since the PUF circuit has been modified when he measures the first secret. The adversary will not be able to obtain both secrets to decrypt or compromise the final message.

0136Referring to <figref idref="f0030">FIG. 50B</figref>, a CPUF chip 700 contains a PUF circuit 100 that generates a response used to decrypt content that is stored in a ROM 704. PUF The content in ROM 704 is encrypted using a k-bit key K. PUF circuit 100 is hard-wired to receive a challenge 702 stored on chip 700, and output a k-bit response on line 706. The response on line 706 is combined with the contents of fuses 708 through an exclusive-or operation to produce key K on line 714. The fuses represent '0' or '1' depending on whether it is burned out or not. A decrypter 712 receives the key K and decrypts the contents of ROM 704. The contents of ROM 704 can be, e.g., a program. A microcontroller 716 performs computations according to the decrypted content.

0137A number of chips 700 are fabricated based on a common design. To reduce the cost of fabricating these chips, the same ROM 704 is used for each chip 700, so the key K is the same for all chips. The response from the PUF circuit 100 is different for each chip, but by setting the fuse bits appropriately for each chip, the key that is sent to decrypter 712 through line 714 can be set to be the same key that is needed to decrypt the content of ROM 704.

0138In one example of fabricating the chips, the fuse bits are set while the chip is in testing by the manufacturer. An initialization circuit 718 receives the key K from the manufacturer through line 720, and receives the response from PUF circuit 100 through line 722. Initialization circuit 718 calculates the fuse bits that is needed to generate the correct key K, and burns the fuses 708 accordingly. In this way, the response from PUF circuit 100 never leaves chip 700.

0139Chip 700 cannot be cloned. Even if an adversary is able to determine the state of the fuses, he cannot determine the response of PUF circuit 100. Thus, the value of K can remain secret.

PUFs using synchronous logic circuit

0140A PUF circuit may be implemented using a clocked circuit so that the output of the circuit in response to an input is different when the period of the clock cycle is different. When a set of integrated circuit chips having clocked circuits are fabricated using a set of lithography masks, each chip is unique in its delay characteristics due to variations in manufacturing across different dies, wafers, and processes. The clocked circuit is designed on assumption that certain timing constraints are met. The delays of components and wires are characterized for worst-case behavior, and the clock period is selected to be larger than the worst-case delay over all register-to-register paths, taking into account the hold time and setup time constraints of the registers. When the clock period is sufficiently large, despite the variations in the delay characteristics, different chips will have the same combinational logic functionality. By purposely decreasing the period of the clock signal driving the clocked circuit so that the timing constraints are not met, different chips with the exact same functionality will have different behaviors because their delay characteristics are different.

0141To identify a given chip, a sequence of input stimuli is sent to the chip. A clock period is selected so that the input stimuli stimulates particular wires and gates. The output response of the chip is sampled at a particular time. By ensuring that the input stimuli exercises a large number of paths in the chip and choosing the sampling time appropriately, the output response will depend on the delays of a large number of gates and wires in the chip. The input stimuli and associated response of the chip become the secret signature of the chip.

0142The number of paths in the chip grows exponentially with the number of inputs or gates in the chip. Given an input stimulus, the delay of some subset of gates will determine the output response of the chip. Because there is an exponential number of input stimuli, it is very difficult to guess which stimuli were used to create the signature.

0143Referring to <figref idref="f0031">FIG. 51</figref>, a PUF circuit 450 can be represented by a combinational logic circuit 452 with feedback loops broken by registers 453. Circuit 452 maps an input bit-vector on a line 454 to an output bit-vector on a line 456. The mapping depends on the period of a clock signal on a line 458. By varying the period of the clock signal, the same input bit-vector will stimulate different wires and components in circuit 452 to produce a different output bit-vector in an unpredictable way. The unpredictability comes from the variations in the circuit due to variations in the fabrication process. Also, the delay of each gate, wire, or path is a complex function of transitions on nearby wires, the values of capacitances being discharged and charged by the input stimulus.

0144To use PUF circuit 450, the input stimuli on line 454 and the period of clock signal on line 458 are chosen so that variations in the clock signal will produce different outputs on line 456. Assume that the input on line 454 is an <i>n</i>-bit wide bit-vector, and the output on line 456 is an <i>m</i>-bit wise bit-vector. The input signal on line 454 is a sequence of input transitions (i.e., from low to high or high to low). For example, if line 454 is 3-bit wide, then an example of a sequence of 3 transitions is 〈1,0,1〉→〈0,0,0〉→〈1,1,0〉. The number of sequences of input transitions is exponential in the number of transitions, and each sequence of input transitions can correspond to different clock periods. The different input stimuli and responses are used as the secret signature of PUF circuit 450.

Secret signature

0145In general, the secret signature can be viewed as a set of signatures {<i>S</i>}, where each signature <i>s</i>_j∈<i>S</i> includes <maths id="math0003"><math display="inline"><mrow><mo>〈</mo><mrow><msub><mi>V</mi><mi>i</mi></msub><msup><mrow /><mi>j</mi></msup><mo>,</mo><mi>c</mi><mi>l</mi><mi>o</mi><mi>c</mi><mi>k</mi><mo>_</mo><mi>p</mi><mi>e</mi><mi>r</mi><mi>i</mi><mi>o</mi><msubsup><mi>d</mi><mi>i</mi><mi>j</mi></msubsup><mo>,</mo><msubsup><mi>O</mi><mi>i</mi><mi>j</mi></msubsup></mrow><mo>〉</mo></mrow><mo>,</mo></math><img file="EP2320344B1_D0003.tif" /></maths><maths id="math0004"><math display="inline"><mn>1</mn><mo>≤</mo><mi>i</mi><mo>≤</mo><msub><mi>K</mi><mi>j</mi></msub><mo>.</mo><mi mathvariant="normal"></mi><msubsup><mi>V</mi><mi>i</mi><mi>j</mi></msubsup><mo>=</mo><mfenced><mrow><msubsup><mi>v</mi><mrow><mi>i</mi><mn>1</mn></mrow><mi>j</mi></msubsup><mo>,</mo><mi mathvariant="normal"></mi><mo>…</mo><mo>,</mo><msubsup><mi>v</mi><mrow><mi>i</mi><msub><mi>K</mi><mi>j</mi></msub></mrow><mi>j</mi></msubsup></mrow></mfenced></math><img file="EP2320344B1_D0004.tif" /></maths> is a sequence of inputs to the circuit, where each <maths id="math0005"><math display="inline"><msubsup><mi>v</mi><mrow><mi>i</mi><mi>k</mi></mrow><mi>j</mi></msubsup></math><img file="EP2320344B1_D0005.tif" /></maths> is an <i>n</i>-bit vector applied to the n inputs of circuit 452. {O_i^j} is the sequence of output responses of the circuit, and is a vector of K_j bit-vectors generated at the m-bit outputs. <i>Clock_period</i>_i^j is the clock period that the circuit is to be clocked at. {<i>V_i^j</i>, <maths id="math0006"><math display="inline"><mi>c</mi><mi>l</mi><mi>o</mi><mi>c</mi><mi>k</mi><mo>_</mo><mi>p</mi><mi>e</mi><mi>r</mi><mi>i</mi><mi>o</mi><msubsup><mi>d</mi><mi>i</mi><mi>j</mi></msubsup></math><img file="EP2320344B1_D0006.tif" /></maths>} will be referred to as an input stimulus, and {O_i^j} will be referred to as the circuit response. To determine {O_i^j}, {V_i^j} is applied to the circuit using {<i>clock_period</i>_i^j} as clock period, and the output of circuit 452 on line 456 is measured. The input stimulus and circuit responses are stored in a secure location and indexed by a serial number of chip 450.

0146When a chip that claims to be "foo" needs to be authenticated by an authenticating authority (AA), the AA selects a signature <i>s</i>_j from the set of signatures {<i>S</i>} that is indexed to the serial number of the chip "foo". The AA uses the input stimulus {<i>V_i^j,</i><maths id="math0007"><math display="inline"><mi>c</mi><mi>l</mi><mi>o</mi><mi>c</mi><mi>k</mi><mo>_</mo><mi>p</mi><mi>e</mi><mi>r</mi><mi>i</mi><mi>o</mi><msubsup><mi>d</mi><mi>i</mi><mi>j</mi></msubsup></math><img file="EP2320344B1_D0007.tif" /></maths>} to stimulate the chip and measures a response from the chip. If the measured response is different from {O_i^j}, then the chip is not "foo". If the responses match, then AA repeats the process with a different signature <i>s</i>_j.

0147The probability that {O_i^j} is the same for two distinct chips depend on the number of delay relationships that need to be satisfied in order for the two chips to have the same responses. For example, a path delay may have to be less than the clock period or more than the clock period by a certain amount so as to prevent the output from producing a glitch, i.e., go from 0 to 1 and back to 0, or vice versa. As another example, for two sub-paths of a circuit to maintain their relative relationship across different chips, their delays may have to differ by an amount greater than 5%.

0148As an illustration, let <i>K</i>_j=2 and assume that a 〈<i>v</i>_<i>i</i>1,<i>v</i>_<i>i</i>2〉 input pair causes a single transition to propagate through a single path in the chip to the output. If the delay of the path is <i>D,</i> then depending on whether <i>D</i> ≤ <i>clock_period</i>₂ or <i>D</i> > <i>clock_period</i>₂, different responses will result. Assume that the AA uses a pair of signatures from S, the secret signature of the chip "foo", and that the pair of signatures are { {{w_a, w_b}, D-ε, {o_c, o_d}}, {{w_a, w_b}, D+ε, {o_c', o_d'}}}. For the input stimulus in the first signature, the transition along the path in the chip will not make it in time to be clocked. For the input stimulus in the second signature, the transition will make it in time. In this case, the output response will be different for the two stimuli when they are applied to the chip "foo".

0149If the adversary wishes to produce a counterfeit chip "bar", the delay of its path has to be in the interval (D-ε, D+ε] to produce the same output response as "foo" for both stimuli. The smaller ε is, the lower the probability that this can be achieved. Let the probability of the two chips producing the same output response for the pair of signatures as <i>p</i>_i<i>.</i> It is clear that <i>p</i>_i &lt; 1. If there are <i>T</i> pairs of signatures like these for <i>T</i> different paths, then the probability that the counterfeit will have the same signatures will be <i>p</i>_i<i>^T</i>→0, as <i>T</i> grows large, assuming that the delays of the paths are independent - which will be true if the paths do not share any devices or wires.

0150By using input stimuli in the secret signature that sensitize multiple paths, the computational barrier presented to the adversary is increased. While there will still be a single transition at the output, there will be more devices and wires, whose delays affect the time that the transition occurs. This can decrease the probability that two chips have the same response to a signature.

0151Consider that the delay of each gate and wire in a set of chips fabricated with the same set of lithography masks follows a normal distribution with a mean of 1 ns, and a standard deviation of 0.05 ns. If a path is a sequence of 100 gates and wires, then the path delay follows a normal distribution with mean of 100 ns and a standard deviation of 0.5 ns. Assume that the path in the given chip has a delay equal to the mean of 100 ns. Then, the probability of another IC has a path delay within 0.5 ns of 100 is 0.68. Assuming a measurement accuracy of 0.5 ns, the probability that these two chips will produce the same output for a single stimulus is 0.68. If 64 input stimuli are applied to sensitize 64 different sets of paths, then the probability that outputs for 64 stimuli are all the same is less than 10^-10. Therefore, given the original chip with the mean path delay, the probability that one or more of a million chips fabricated using the same lithography masks have the same signature is approximately 106×10^-10=10^-4.

0152To compensate for temperature changes, when signatures are generated for chip 450 in FIG. 20, different signatures are generated for different temperatures. During authentication, the signature of a particular chip at a particular temperature is used.

0153To make the adversary's task more difficult, conducting particles can be scattered in the chips packaging so that the delays of gates and wires has a small dependence (e.g., +/- 5%) on the packaging used.

0154Referring to <figref idref="f0031">FIG. 52</figref>, a "glitch generator" 460 may be added to make a path (e.g., from a line 462 to a line 464) non-single event sensitizable. A path P is "single event sensitizable" if there exists an input vector pair such that under arbitrary delays in the circuit, the event propagates along the path P. Doing so prevents the adversary from obtaining an affine system of equations by applying input stimuli and measuring output path delays, and solving the equations to create a model of the gate and wire delays.

Example circuit

0155Referring to <figref idref="f0032">FIG. 53</figref>, a circuit 466 implements the function <i>f</i>(<i>a,b</i>) = <i>a</i>⊕<i>b.</i> Assume that circuit 466 is part of a clocked circuit, and that the output of circuit 466 is used by another circuit one clock cycle after input signals <i>a</i> and <i>b</i> appear on lines 469 and 471, respectively. Depending on the length of the clock cycle, the output of circuit 466 would be different. Assume that the delays in the gates, including the inverters, are all 1, and the delays of the wires are 0. If the circuit is clocked at <i>clock_period≥</i>3, then circuit 466 will respond like <i>f</i>(<i>X</i>) for all <i>X</i>. Assume that <i>Y</i>=〈<i>a</i>=0,<i>b</i>=0〉. If X=〈<i>a</i>=0,<i>b</i>=1〉 is applied after <i>Y and</i> the clock period is <i>clock_period</i> ≥ 2, the output of circuit 466 will be 1, the same as <i>f</i>(<i>X</i>). However, if circuit 466 is clocked with a period such that 1 ≤ <i>clock_period</i> &lt; 2, the output will be 0. If the clock period is chosen to be 1.95, then it is possible that a different circuit fabricated using the same lithography masks will still produce 1 as output for the sequence of (Y, X) pair above, if the delay of either the top AND gate 468 or the OR gate 470 is less than 0.95.

0156If <i>Y</i>=〈<i>a</i>=1,<i>b</i>=0〉 is applied, followed by <i>X</i>=〈<i>a</i>=0,<i>b</i>=1〉, then <i>f</i>(<i>X</i>)=1. The output of circuit 466 is 1 if <i>clock_period</i> ≥ 3, the output is 0 if 2 ≤ <i>clock_period</i> &lt; 3, and output is 1 if <i>clock_period</i> &lt; 2.

Choosing input stimulus and clock period

0157To determine which stimuli and clock period to use for a given PUF circuit, a model of the PUF circuit having approximate delays of the wires and gates in the chip can be used. Let the timing-approximate model be called <i>A</i>_f. An analysis can be performed on the model <i>A</i>_f and find what the waveform at the output would look like for any input stimulus, i.e., vector pair. This analysis takes linear time in the size of the chip. A particular transition in the output waveform can be chosen. Two clock periods is chosen, one ε before the transition and ε after the transition. A transition is selected such that the output is steady for a time larger than ε on either side of the transition. The PUF circuit is then verified to ensure that the PUF circuit produces the same response as <i>A</i>_f for the chosen input stimulus and clock periods. If the responses are the same, ε can be made smaller and the verification is repeated. If the responses are different, the clock periods or input stimulus is changed and the verification is repeated.

0158The set of signatures needs to be large enough such that the probability of two chips producing the same response to the input stimuli in the signature is very small. For a probability of 10^-10, 64 stimuli is required. The storage requirements of the signature is largely dictated by the size of the input stimulus in each signature, which is ∑<i>_jN</i>×<i>K_j</i> bits, where <i>N</i> is the number of inputs to the chip, and <i>K</i>_j is the length of the input stimulus of the <i>j</i>^th signature. The number of inputs <i>N</i> is limited by the package. Usually, <i>N</i> ≤ 500 and <i>K</i>_j ≥ 2.

0159The PUF chip may have a global reset that places it in a known state. Otherwise, a transfer sequence that places the chip in a known state can be applied before the first signature is applied. Assume <i>K</i>_j = 2, one authentication requires about 100 kilobytes to store the set of signatures.

Other implementations

0160A number of examples of the invention have been described. Nevertheless, it will be understood that various modifications may be made. For example, in <figref idref="f0011">FIG. 13A</figref>, the random hash module <i>h</i>₃ 192 may be replaced by a "distance d encoder." Such an encoder implements a mapping such that images of different elements always differ on at least d bits, which means that at least d bits of the input to the PUF circuit 188 cannot be directly chosen by the attacker.

0161In <figref idref="f0013">FIG. 14</figref>, the functional module 52 and the control module 54 may be implemented using a single microprocessor. The microprocessor performs computations and processing of data based on the software codes it receives. In <figref idref="f0029 f0030">FIG. 50</figref>, a simpler CPUF chip can be constructed by using one constant (e.g., the chip serial number) that is passed through a hash function to become the prechallenge used by control module 54 to generate the challenge to PUF circuit 100. Integrated circuit 102 may include more than one self oscillating loop circuits 114 to allow measurement of many signal delays simultaneously. Delay circuit 116 may be replaced by other types of circuits in which the delay is a complicated function of the challenge. In some CPUF implementations where it is not necessary to execute arbitrary algorithms, the program's actions may be implemented in hardware. The functional circuitry and the PUF does not have to be on the same chip; they can reside on different semiconductor chips in a multi-chip module. The input and output of the PUF circuit may be analog values rather than digitized values.

0162The measurable physical characteristics may be characteristics other than path delays. For example, referring to <figref idref="f0033">FIG. 54</figref>, PUF device 500 includes an integrated circuit 501, a light emitting diode (LED) array 502 and a charged coupled device (CCD) array 504, all of which are fabricated on a substrate 510. An epoxy 506 encloses the LED array 502 and CCD array 504. Epoxy 506 is coated with a reflective layer 508 so that light emitted by the LEDs of array 502 will be reflected by reflective layer 508 and detected by CCD array 504. As the light passes through epoxy 506, a speckle pattern that is unique to epoxy 506 will be detected by CCD array 504. When different combinations of LEDs in LED array 502 is illuminated, CCD array 504 will detect different speckle patterns. Only a few LEDs are turned on at the same time to maintain the contrast of the speckle pattern.

0163When several PUF devices are fabricated, the epoxy layer will have a slightly different optical transmission property for each device. Thus, the same combination of LEDs will produce different speckle patterns at the CCD array for different devices. A control signal that determines the combination of LEDs can be seen as a "challenge", and the pattern detected by CCD array 504 can be seen as a "response." Such challenge-response pairs can be used to authenticate the identity of PUF device 500. An advantage of using epoxy is that epoxy is stable through a substantial range of temperature. Thus, circuit for compensating effects of environmental variations can be made simpler.

0164An alternative method of measuring the oscillation frequency of the oscillating loop 122 in PUF circuit 101 of <figref idref="f0003">FIG. 3</figref> is to use a phase lock loop (PLL) circuit. Referring to <figref idref="f0034">FIG. 55</figref>, a PUF circuit 1000 includes an oscillator loop 122 and a PLL circuit 1002 used to measure the oscillation frequency of the oscillator loop. Oscillator loop 122 includes a delay circuit 111 that receives an input (or challenge). PLL circuit 1002 includes a phase detector 1004, a charge pump 1006, a loop filter 1008, a voltage controlled oscillator (VCO) 1010, a frequency divider 1012, and a counter 1014. Frequency divider 1012 generates an output on signal line 1016, which is sent to phase detector 1014. By comparing the signal on line 1016 with the signal on line 134 (which comes from oscillating loop 122), PLL circuit 1002 settles to a state in which the signals on lines 1016 and 134 have the same frequency. Counter 1014 determines the frequency, and generates an output on line 1018 which becomes the output (or response) of PUF circuit 1000.

0165Referring to <figref idref="f0035">FIG. 56</figref>, a PUF circuit 1010 includes a delay circuit 1012 and a delay circuit 1014. Each of delay circuits 1012 and 1014 receives an 128-bit challenge that selects one of 2¹²⁸ signal paths in the delay circuit. A transition (rising or falling edge) of a "Count" signal is sent to both delay circuits 1012 and 1014. The rising edge passes through the signal paths in delay circuits 1012 and 1014, and exits the delay circuits at lines 1016 and 1018, respectively. The signals on lines 1016 and 1018 are sent to an arbiter 1020, which produces a "1" if a transition on line 1016 arrives faster than a transition on line 1018, and produces a "0" if the transition on line 1018 arrives faster.

0166A one-bit digital response can be obtained without measuring oscillation frequency. This circuit produces a compensated value directly since temperature variations will have the same effect on delay circuits 1012 and 1014. Transitions in delay circuits 1012 and 1014 are both sped up (or slowed down) and will not change the output value. An arbiter is a simple circuit that can be realized using a flip-flop with the two inputs being the data input and the clock input. If the data arrives before the clock, the flip-flop produces a 1, else 0. Here, the signal on line 1016 is used as the data input, and the signal on line 1018 is used as the clock input. To produce a 64-bit response, sixty-four 128-bit challenges are sent through the PUF circuit 1010.

0167In <figref idref="f0013">FIG. 14</figref>, functional module 52 and control module 54 were implemented as software subroutines that are run on microprocessor 51. In an alternative example, the functional module 52 and control module 54 can be implemented using dedicated hardware circuits.

0168In FIGs. 16, 17, 19-22, 25, and 27-29, the PUF circuit 100 can be replaced by an improved PUF circuit 186 (<figref idref="f0011">FIG. 13A</figref>).

0169In <figref idref="f0029 f0030">FIG. 50</figref>, the control circuit 54 and functional circuit 52 may be replaced by a microcontroller that receives program codes and perform control and computational functions.

0170Accordingly, other embodiments are within the scope of the following claims.

0171In specific aspects, the invention provides one or more of the following items: <ol id="ol0001" compact="compact"><li>1. A method comprising: <ul id="ul0003" list-style="none" compact="compact"><li>providing a first device (50) from a group of devices fabricated based on a common design, each device (50) having a corresponding plurality of measurable characteristics that is unique in the group to that device, each device having a measurement module (104) for measuring the measurable characteristics; and</li><li>enabling authentication of the first device by selective measurement of one or more of the plurality of measurable characteristics of the device (50), wherein providing the first device from the group of devices includes providing a first integrated circuit (100), and wherein the plurality of measurable characteristics include delay characteristics of a plurality of signal paths in the integrated circuit (100).</li></ul></li><li>2. The method of item 1 wherein the plurality of signal paths includes multiple paths through each of a set of circuit components, wherein the circuit components include preferably one of passive transmission lines (178, 180), or active semiconductor elements, said active semiconductor elements including preferably logic gates (166, 168, 184).</li><li>3. The method of item 1 or 2, wherein each of the plurality of measurable characteristics depends on a set of separate physical characteristics, and wherein measurement of the selection of one or more of the measureable characteristics includes forming a non-linear combination of a plurality of the separate physical characteristics according to selection information.</li><li>4. The method of item 3 wherein the separate physical characteristics include characteristics of circuit components, and combining the plurality of separate physical characteristics includes forming a signal path through the circuit components se35 lected according to the selection information.</li><li>5. The method of any of items 1 through 4,wherein enabling authentication includes enrolling the first device, including transmitting selection information to the first device (50), receiving from the first device (50) response information generated by selective measurement of one of the plurality of characteristics based on the selection information, and storing the received response information in association with the first device (50) and the selection information.</li><li>6. The method of item 5, wherein storing the received response includes keeping the selection and response information secret.</li><li>7. The method of item 5, further comprising authenticating the first device, including transmitting the selection information to the first device (50), and receiving response information generated by the selective measurement of the one of the characteristics, and comparing the received response information with the stored response information.</li><li>8. The method of item 7 wherein each of enrolling the first device (50) and authenticating the first device (50) includes selectively measuring the one of the plurality of characteristics based on the selection information and generating the measurement information.</li><li>9. The method of any of items 1 through 4, further comprising enrolling each of the group of devices, including for each of the devices: <ul id="ul0004" list-style="none" compact="compact"><li>transmitting selection information to the device (50) that identifies a subset of the measurable characteristics;</li><li>receiving from the device (50) response information generated by selective measurement of each of the subset of measurable characteristics identified in the selection information; and</li><li>storing the received response information in association with the first device (50) and the selection information.</li></ul></li><li>10. The method of item 9 further comprising determining a different subset of the measurable characteristics for each of the devices, said determining the different subset for each device preferably including randomly choosing the members of each of the subsets.</li><li>11. The method of item 10 wherein determining a different subset for each of the devices includes determining a substantially small subset of the measurable characteristics for each device (50).</li><li>12. The method of item 10, wherein storing the received response information includes keeping the selection and response information secret.</li><li>13. The method of item 9 further comprising authenticating the first device, including: transmitting selection information to the first device (50) that identifies one of the subset of measurable characteristics for the first device (50); receiving from the first device (50) response information generated by selective measurement of the identified one of the subset of measurable characteristics; and comparing the received response information with the stored response information received during enrollment of the first device (100).</li><li>14. The method of any of items 1 through 4, further comprising fabricating the devices (100) in the group of devices according to a common design, said fabricating the devices (100) preferably comprising fabricating the group of devices according to a common set of lithography masks.</li><li>15. The method of any of items 1 through 4, wherein the corresponding plurality of measurable characteristics of the devices (50) include characteristics determined during fabrication of the devices (50), said characteristics determined during fabrication of the devices preferably including uncontrolled characteristics of a fabrication process.</li><li>16. The method of any of items 1 through 4, in which the corresponding plurality of measurable characteristics comprise optical characteristics, wherein the optical characteristics preferably include reflection characteristics, said reflection characteristics preferably including speckle patterns.</li><li>17. The method of any of items 1 through 4, in which the number of measurable characteristics of each device is greater than 2, preferably greater than 4, more preferably greater than 16, most preferably greater than 256.</li><li>18. The method of any of items 1 through 4, in which the number of measurable characteristics of each device is greater 2¹⁶, preferably greater than 2³², more preferably greater than 2⁶⁴, most preferably greater than 2¹²⁸.</li><li>19. The method of any of items 1 through 4, in which each device comprises a functional component and a measurable component that have the plurality of measurable characteristics.</li><li>20. The method of item 19, further comprising packaging the device in a package, wherein preferably the functional component and the measurable component are disposed in the package in a way such that the functional component cannot be physically accessed without altering the plurality of measurable characteristics.</li><li>21. The method of any of items 1 through 4, further comprising: <ul id="ul0005" list-style="none" compact="compact"><li>receiving a selection signal at the first device encoding selection information that includes an identifier; and</li><li>selecting one of the plurality of measurable characteristics using the identifier.</li></ul></li><li>22. The method of item 21 further comprising measuring the selected characteristic.</li><li>23. The method of item 22 wherein the selected characteristic includes a delay characteristic of a selected signal path.</li><li>24. The method of item 23 wherein measuring the delay characteristic includes generating an oscillating signal using the selected delay path.</li><li>25. The method of item 24 wherein measuring the delay characteristic further includes determining a quantity related to an oscillation frequency of the oscillating signal, said determining the quantity related to the oscillation frequency preferably including one of counting a number of oscillations during a timed interval or applying a phase-locked loop to the oscillating signal.</li><li>26. The method of item 23, wherein measuring the delay characteristic includes comparing delays of a plurality of selected signal paths.</li><li>27. The method of item 22 wherein measuring the selected characteristic includes compensating for variations in the measurement of the selected characteristic due to changes in an environment of the device (50).</li><li>28. The method of item 22 further comprising measuring a reference characteristic, and computing a ratio of a measurement of the selected characteristic to a measurement of the reference characteristic.</li><li>29. The method of item 22 further comprising correcting errors in a measurement of the selected characteristic.</li><li>30. The method of item 22 further comprising: <ul id="ul0006" list-style="none" compact="compact"><li>determining response information using the measured characteristic; and</li><li>transmitting a response signal from the first device (50) encoding the response information.</li></ul></li><li>31. The method of any of items 1 through 4, further comprising: <ul id="ul0007" list-style="none" compact="compact"><li>receiving a selection signal at the first device (50) encoding selection information that includes an identifier;</li><li>selecting a first one of the plurality of measurable characteristics using the identifier; and</li><li>selecting a second one of the plurality of measurable characteristics also using the identifier.</li></ul></li><li>32. The method of item 31, further comprising: <ul id="ul0008" list-style="none" compact="compact"><li>measuring the first selected characteristic to generate a first measurement;</li><li>measuring the second selected characteristic to generate a second measurement; and</li><li>comparing the first measurement to the second measurement.</li></ul></li><li>33. The method of item 32, further comprising generating a one-bit response according to the comparison of the first and second measurements.</li><li>34. The method of item 33, further comprising: generating an n-bit response by repeating n-1 times the steps of receiving a selection signal encoding selection information that includes an identifier, selecting a first one and a second one of the plurality of measurable characteristics using the identifier, measuring the first one and second one of the measurable characteristics to generate a first measurement and a second measurement, and comparing the first and second measurements to generate one bit of the n-bit response.</li><li>35. An apparatus comprising: <ul id="ul0009" list-style="none" compact="compact"><li>a device (50) selected from a group of devices fabricated based on a common design, each device (50) in the group having a corresponding plurality of measurable characteristics that is unique in the group to that device (50), the device (50) including a measuring component that measures a selected characteristic, wherein</li><li>the device (50) comprises an integrated circuit (100), and wherein</li><li>the integrated circuit (100) comprises signal paths, and the plurality of measurable characteristics comprise the delay characteristics of the signal paths.</li></ul></li><li>36. The apparatus of item 35, wherein the integrated circuit (100) comprises a set of circuit components, and the signal paths include paths through each of a set of the circuit components.</li><li>37. The apparatus of item 36, wherein the circuit components include preferably one of passive transmission lines (178, 180), or active semiconductor elements, said active semiconductor elements including preferably logic gates (166, 168, 184).</li><li>38. The apparatus of item 35 wherein the measurement component includes an oscillator circuit (122) whose oscillation characteristics depends on a delay characteristics of one or more of the signal paths.</li><li>39. The apparatus of item 35 wherein the measurement component includes an arbiter circuit (1032) configured to compare delay characteristics of a plurality of the signal paths.</li><li>40. The apparatus of any of items 35 through 39 wherein each of the plurality of measurable characteristics depends on a set of separate physical characteristics, and wherein selective measurement of one or more of the measureable characteristics includes forming a non-linear combination of a plurality of the separate physical characteristics according to selection information.</li><li>41. The apparatus of item 40 wherein the separate physical characteristics include characteristics of circuit components, and combining the plurality of separate physical characteristics includes forming a delay path through the circuit components selected according to the selection information.</li><li>42. The apparatus of item 40 wherein a result of combining of a plurality of separate characteristics is substantially unpredictable based on selective measurements of other combinations of the separate characteristics.</li></ol>