HK1134359B - Authentication with physical unclonable functions - Google Patents

Abstract

Physical Unclonable Functions (PUFs) for authentication can be implemented in a variety of electronic devices including FPGAs, RFIDs, and ASICs. In some implementations, challenge-response pairs corresponding to individual PUFs can be enrolled and used to determine authentication data, which may be managed in a database. Later when a target object with a PUF is intended to be authenticated a set (or subset) of challenges are applied to each PUF device to authenticate it and thus distinguish it from others. In some examples, authentication is achieved without requiring complex cryptography circuitry implemented on the device. Furthermore, an authentication station does not necessarily have to be in communication with an authority holding the authentication data when a particular device is to be authenticated.

Description

Identity verification using physical unclonable functions

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims priority from united states provisional application No. 60/973,505 entitled "authentication systems inventing physical operable Functions" filed on 19/9/2007 and united states provisional application No. 61/018,618 entitled "Secure RFID" filed on 2/1/2008, which are incorporated herein by reference.

The present application also relates to U.S. application No. 11/273,920 entitled "vollate Device Keys and applications theory," filed on 14/9/2005 and published on 21/2006 as US2006/0210082a1, which is incorporated herein by reference.

Background

The present invention relates to authentication using a physical unclonable function.

A Physical Unclonable Function (PUF) in an electronic circuit may be used to distinguish multiple integrated circuits (ICs, "chips") from each other. The ability to distinguish chips from each other using PUFs in hardware ("hard PUFs") or in programmable devices ("soft PUFs") is a potentially valuable way to authenticate an IC. Such authentication has a wide range of applications and includes anti-counterfeiting, inventory control, multi-factor authentication (to allow access to computer systems or online computer systems & networks), and secret key generation for encryption and other security applications (using appropriate control logic used in conjunction with the basic PUF circuit), among others. An efficient authentication mechanism can be performed in a number of ways, but typically involves the use of a digital challenge (a string of 1 s and 0 s) that, when applied to a typical PUF circuit, produces a corresponding digital response (another string of 1 s and 0 s), with the different digital responses of the integrated circuits differing. These challenges and their corresponding responses are challenge-response pairs (CRP) of the PUF.

Disclosure of Invention

PUFs for authentication can be implemented in a variety of electronic devices, including FPGAs, RFIDs, and ASICs. In some implementations, CRPs corresponding to individual PUFs can be created and managed in a database. Later, when attempting to authenticate a target object with a PUF, a challenge set (or subset) is applied to each PUF device to authenticate it and thereby distinguish them from each other. Since any two PUFs have different electronic characteristics (although otherwise the electronic circuit layout is identical), this can be an efficient and low-cost mechanism for authentication of electronic components. Authentication is accomplished without the need to implement complex encryption circuitry on the device. Using a simpler circuit with fewer logic gates also reduces the amount of power required by the device.

In general, in one aspect, a method for authenticating a device with an authentication station, wherein the device provides the following capabilities: accepts a challenge value from the authentication station and returns a response value to the challenge value to the authentication station, the response value being dependent on a manufacturing characteristic of the device (e.g., a semiconductor manufacturing characteristic). The method includes identifying the device, the identifying the device including accepting, at an authentication station, identification data from the device to be authenticated. Authentication data characterized by one or more challenge value and response value pairs associated with the identified device is retrieved, wherein the authentication data was previously obtained by a trusted authority in communication with the device. The data retrieval does not require communication between the authentication station and the trusted authority after the device is identified. The first challenge value is provided to the device from the authentication station, and the first response value from the device is accepted at the authentication station. It is then determined whether the first challenge value and the first response value pair sufficiently match the authentication data.

Aspects may also include one or more of the following.

The first challenge value and the first response value pair substantially match if there are represented challenge and response value pairs in the data such that the challenge in the data is equal to the first challenge value and the corresponding response in the data is different from the first response value, the corresponding response in the data being less than the first response value by a predetermined maximum number of bit positions.

The device includes a proximity device, such as a Radio Frequency Identification Device (RFID), and the steps of accepting the identification data, providing the first challenge, and accepting the first response each include communicating between the authentication station and the proximity device using a wireless communication protocol. For example, the wireless communication protocol may be compatible with the ISO 14443 standard and the identification data may represent an Electronic Product Code (EPC) associated with the apparatus.

The authentication station is one of a plurality of distributed authentication stations associated with a trusted authority, wherein the authentication station may be remotely located from the trusted authority.

Determining the authentication data includes: prior to accepting the identification from the device, data is accepted that associates each of the plurality of device identifications with a corresponding subset of challenge and response value pairs of the device corresponding to the device identification obtained by a trusted authority of the device. After identifying the device, a subset of challenge and response value pairs for the device is accessed according to the accepted identification data.

Determining the authentication data includes: a password for authentication data from the device is accepted at the authentication station. Before identifying the device, decryption information for decrypting the password of the data accepted from the device is accepted, for example, decryption information from a trusted authority.

The authentication data includes model parameters sufficient to predict a response value for each of the plurality of challenge values. For example, the model parameters include delay parameters corresponding to delay elements in the device from which the response values are determined at the device.

The method comprises the following steps: selecting a challenge value at the authentication station and determining a predetermined response value for the selected challenge from the model parameters, the determining whether the first challenge value and the first response value pair sufficiently match the authentication data comprising: it is determined whether the first response value sufficiently matches the predetermined response value.

The additional authentication data is determined at an authentication station adapted for further authentication of the device, e.g. by a further authentication station. This may include: the method includes generating one or more additional challenge values, providing the challenge values to the device, and accepting corresponding response values from the device. Additional authentication data may be provided to the trusted authority or a password for the additional authentication data may be provided to the device or communicated to another authentication station.

The method further comprises the following steps: the method further includes determining the first challenge value as a previous value to the second challenge value in a deterministic sequence associated with the apparatus, and determining the second response value from the accepted first response value. Determining whether the first challenge value and the first response value pair sufficiently match the authentication data comprises: it is determined whether the second challenge value and the second response value pair sufficiently match the authentication data.

In general, in another aspect, multiple challenges are used on arbitrary objects/devices to improve authentication error rates.

In general, in another aspect, an ID in conjunction with a CRP is used with a subject/device to improve performance, expand capabilities, and/or facilitate a more highly scalable CRP authentication system.

In general, in another aspect, multiple databases of CRPs are used to enhance the flexibility of the authentication process across multiple users, allow third party mediation, and/or recovery mechanisms in the event of security violations around information in any of the databases providing CRPs, where the multiple databases may be shared or may be independent of each other.

In general, in another aspect, a device security circuit includes circuitry for combining a set of outputs, each output determined by a corresponding control input for selecting a physical characteristic of a device, and utilizing a combination of the outputs to perform a security function associated with the device, where the outputs are dependent on the physical characteristic of the device. In some examples, the apparatus includes a set of separate circuits, each circuit for generating a different one of the set of outputs. In some instances, the same circuit is used to generate multiple outputs in the set of outputs. The circuitry for combining the set of outputs may comprise circuitry for exclusive or (xor) operations. The period may also include circuitry for generating a control input based on a challenge value provided to the device. For example, the circuit includes a Linear Feedback Shift Register (LFSR).

In general, in another aspect, a method for authenticating a device includes: registering each of a plurality of devices, wherein each device provides the capability to: the challenge value is accepted and a response value to the challenge value is returned, the response value being dependent on the manufacturing characteristics of the device. Registering each device includes: the plurality of challenge values are provided to the device, the corresponding plurality of response values from the device are received, and the model parameter is calculated based on the plurality of challenge values and the corresponding plurality of response values. The model parameters are sufficient to predict a response value corresponding to the challenge value provided to the device. The model parameters are stored for subsequent use in authenticating the device.

Aspects may also include one or more of the following.

Storing the model parameters includes storing the model parameters in association with an identification of the apparatus.

The storage model parameters include: the password for the model parameters is provided to the device for storage on the device.

The method comprises the following steps: the method includes authenticating one of the plurality of devices, retrieving model parameters for the one device, providing a first challenge value to the one device, accepting a first response value from the one device, and determining whether the first challenge value and the first response value pair sufficiently match based on the model parameters.

After accepting response values from the device for calculating model parameters, the device is inhibited from subsequently providing response values suitable for subsequent model parameter calculations by the device. For example, the prohibiting includes: physically making a change to the device (e.g., burning a short), or deleting the required data (e.g., encryption key).

Calculating the model parameters includes: a parameter corresponding to a circuit parameter of a circuit element of the device is calculated, the parameter being used to calculate a response value from the challenge value.

In general, in another aspect, a security device includes: a communication interface for accepting challenge values from the authentication station and providing corresponding response values to the authentication station; a sequencer for determining a sequence of configuration values based on the challenge values; and a response circuit whose functional characteristics depend on circuit manufacturing characteristics that are essentially unique to the apparatus, the circuit including a configuration input coupled to the output of the sequencer such that the response output is dependent on the configuration value and the manufacturing characteristics. The apparatus is configured to accept the challenge value and generate a corresponding response value from a sequence configuration of the response circuit configured in accordance with an output of the sequencer. The sequencer may include a linear feedback shift register. The response circuit may include a set of delay elements that may be configured according to the configuration inputs to form one or more delay paths through the response circuit.

The methods described herein may address one or more of the following. First, PUFs can be electrically "noisy". Unless error correction is applied to the output of the PUF, the PUF produces slightly different results even if the PUF is challenged each time with the same challenge. This phenomenon is similar to the way that human biometric (e.g., fingerprint) measurements can produce results that are slightly different from each other. In the case of human biometrics, these differences may be due to errors in the measurement system, stains on the contact points, etc. In the case of PUFs, the cause of noise may be temperature, voltage, radiation, or aging, which are well known to alter the electrical and functional characteristics of the circuit. In the case of PUFs, this may cause the response to the same challenge to vary slightly from measurement to measurement.

Second, as the number of devices to be authenticated grows in scale, the difficulty of managing the database (particularly indexing and accessing data after assembling the database on board) increases if only CRPs are stored. In addition, additional complexity is added if the user of the system simply wants to identify the device/component/product (such as for tracking & tracking repository control). If the user only wants to identify the component using CRPs, the user may be required to select a challenge to apply to the device, but not any navigation as to which CRP should correspond to that particular device. Of course, this can be done with the same pre-challenge applied to all devices, but doing so adds an extra processing step, slows down the process, and greatly enlarges the indexing barrier.

Third, there are situations where associating a single "gold" repository of CRPs for all authentication events with a device equipped with a PUF can complicate the authentication process. A single database is far from ideal in situations where all parties must access the single database, excessive network latency, the occurrence of access to the network altogether, or concern about catastrophic failure of the database (such as may occur if security around the single database may be breached by an attacker). Furthermore, in some cases, different parties may want their own CRP database for the subject to be authenticated, and they may not want to share or store their own CRP in the central database.

In general, in another aspect, a secure rfid device uses a combination of outputs from multiple (e.g., 2, 3, or more) "PUF" circuits, for example, with an XOR operator. The outputs of the PUF circuits may each correspond to the output of a different PUF circuit, or may correspond to sequentially estimated outputs of the same PUF circuit, e.g. with different control inputs that make the outputs dependent on different physical characteristics.

In some examples, each PUF circuit is controlled according to the output of a Linear Feedback Shift Register (LFSR), e.g., where each LFSR implements a different polynomial output and utilizes samples or different inputs (i.e., challenges).

Advantages of one or more aspects may include increased difficulty in simulating PUF circuits. For example, the difficulty of simulating physical characteristics (e.g., delay) in a PUF can be greatly increased by using an XOR of two different PUFs. As another example, with an LFSR that determines the control input to a PUF, it is difficult to simulate by making it difficult for an adversary to select particular characteristics of the PUF to contribute to the output of the PUF.

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

Drawings

Fig. 1 is a diagram showing a PUF-based RFID authentication system.

Fig. 2 is a diagram illustrating a PUF-based RFID authentication system.

Fig. 3 is a diagram showing a PUF-based RFID.

Figure 4 is a flow diagram illustrating a PUF generating a response from a challenge.

Fig. 5 is a diagram showing response bits summed into one response.

Fig. 6 is a diagram showing redundant response bits summed to one long response with an embedded reply response.

Figure 7 is a diagram showing a PUF with additional output circuitry for simulation.

Detailed Description

Referring to fig. 1, one example of an authentication system performs authentication of a proximity device such as an RFID (radio frequency identification device) using a Physical Unclonable Function (PUF) circuit. In particular, the authentication system extends the identification function of a conventional RFID to provide an authentication function, which prevents "cloning" of the RFID or makes such cloning very complicated. It should be understood that the techniques described below are not limited to use with RFID or nearby devices. Other examples of authentication systems propose different types of devices that use an integrated PUF as the basis for authentication.

In one exemplary scenario, RFID 110 is provided to manufacturer 102 in an unprogrammed state, such as a manufacturer of luxury consumer products. The manufacturer affixes the REID to the manufactured product to serve as the basis for identification and authentication as the product moves through the supply chain to the end consumer. For example, a manufacturer may store an identification number (ID)104, such as an EPC (electronic product code), on an RFID. In other instances, each RFID is configured with a permanent unique ID, which can then be associated with the EPC or lot number as needed.

The PUF 114 on the RFID is utilized by the authority 120, which is the originator of establishing the authenticity of the product to which the RFID 110 is attached, to determine information that will be subsequently used for RFID authentication. Note that the regulatory agency 120 may be the same party as the original manufacturer 102. Generally speaking, this authentication method relies on an enrollment phase in which an authority provides a set of challenges 126 to the RFID, which are used by the PUF 114 on the device to generate the challengeCorresponding responses 128, and these responses are passed back to the authority 120. Each challenge and its associated response form a challenge-response pair (CRP). The set of challenges forms a very small subset of all possible challenges that may be sent and may therefore be considered a random selection. For example, using a 64 bit challenge, there is 2⁶⁴The number of possible challenges, and the number of challenges used during enrollment will typically be a very small fraction of this number, e.g., hundreds of 64-bit challenges. The regulatory agency securely stores this small subset of CRPs that can be used for authentication.

At some future time, the RFID is typically authenticated after it has left the supervision of an authority or other trusted party. The identity authentication comprises: a challenge (or possibly a small subset) is provided to the device from an authentication station (such as a portable RFID reader), a corresponding response is received, and a determination is made as to whether the response is suitably consistent with the response provided during initial enrollment. For example, a randomly selected challenge from the subset used during enrollment is provided to the RFID and the response is compared to the enrolled response based on a plurality of bit level differences. For example, in some instances, if there is a difference of less than 12 bits in the 128 bits, then an authentication time response and an enrollment time response are concluded.

Examples of authentication systems using the above general approach utilize one or more of specific technologies, families of technologies described below that are generally used to improve performance and extend the capabilities of CRP authentication systems, and CRP authentication systems constructed in particular with PUFs embedded in electronic circuits.

In some embodiments, to reduce type 1 (false positive, i.e. asserting a cloned device as authentic) and type 2 (false negative, i.e. asserting a genuine device as untrusted) errors caused by "noise" (e.g. bit errors) in PUF circuitry, multiple challenges may be applied to one integrated circuit/device equipped with a PUF. Statistical theory holds that applying multiple challenges to the same subject reduces authentication error rates. This can be done in a number of ways (with similar effect) including: (a) more than two challenges are applied in the same read/challenge/response cycle and the resulting responses are linked (effectively increasing the bit length of the challenge without requiring a separate authentication step for each challenge), and (b) if the product appears to be untrusted after the first authentication attempt, the second, third, or nth challenge is applied in sequence order. A first of these techniques may be implemented in hardware or firmware without burdening the authentication system. The second of these techniques has the advantage that it can be selectively applied only to those PUF objects that were previously found to be suspect/untrusted. By using multiple challenges and responses for a given object, type 1 and type 2 errors can be reduced, assuming that the challenge and underlying response for any given PUF are statistically independent of each other. Furthermore, even if the underlying challenge & response is not statistically completely independent, it may still show that type 1 and type 2 errors are reduced if there are some measures of randomness in the underlying CRP results from one device to another.

In some embodiments, each RFID does not have a unique ID. Instead, an identifier pre-challenge is sent to the device and the response is used as the ID. If multiple devices are known to return the same response to the pre-query, an additional query may be required to uniquely identify the device. In some embodiments, to increase the efficiency of the authentication process and reduce the complexity of database processing problems, the use of non-PUF "identifiers" such as unique product numbers (which may be assigned in any order-random, serialized, etc.) or other single unique identifier ("ID") in conjunction with CRPs for objects equipped with PUFs adds significant advantages to the system. Such a number may be stored in a non-volatile random access memory (the most common form of memory for such numbers) or otherwise generated from the circuit. By associating what may essentially be a "common" ID (e.g., an electronic product global code, EPC) with a set of underlying CRPs for the apparatus, the authentication process is greatly simplified.

Referring to fig. 1, the authentication step in this case reads/scans ID 104 and associates a particular CRP that is stored, for example, in database 122 for that object ID. With this ID, the database 122 can be quickly ordered to find CRPs that should correspond to the product when subsequent tests are performed during the authentication process. With the ID, no pre-query is required to look up the object in the database. Furthermore, not only can the database itself be organized and accessed more efficiently with the ID, but information about the product is not central to authentication, but other transactions such as base inventory control can be made more accessible to the user. In some exemplary usage models, including usage in inventory control or tracking & tracing systems, such IDs may be common.

In some embodiments, to provide greater flexibility in the data processing process and to allow multiple parties to use the same authentication system, and also to provide a recovery mechanism that compromises the security of any database of authenticated CRPs, multiple CRP databases may be created, and further separate or even completely different CRP databases may be associated across multiple users. Under one such model, any party with a trusted PUF-equipped device may create their own database of CRPs associated with the object. Statistically, if the physical entropy of the PUF is large enough (mainly defined by the number of independent bits that can be generated by the PUF), the probability that any two parties can have the same CRP database for the same object by design is arbitrarily small. Each database is created by obtaining a completely different CRP set through a challenge sequence sent to the device performing the authentication. Each party can at least manage its own information independently if all parties agree to share the same database. Either with its own CRP for such objects/devices or a third party (such as a central repository or service provider) that utilizes agreements between the parties themselves may make an official between the parties and prove (for example) that an object held by party a is the same as another object held by party B at another time/place (which may also be different). In this example, if the parties a and B never need to share their respective CRPs for the subject in question, they no longer need to share their respective CRPs for the subject in question. A chain of trust between multiple parties can now be implemented. Furthermore, multiple CRP databases may be created in order to provide a recovery mechanism that compromises the security of any database of the identity verification CRP.

Referring to fig. 1, in some implementations, the initial CRP set obtained by the regulatory agency 120 in the initial enrollment is stored in the primary database 122. All or some of the known challenge response pairs are then securely distributed to the remote device, not necessarily remaining in communication with the master database after the remote device receives the data. For example, the remote device may be a handheld RFID reader 140 that stores the CRP in a local database 142. The apparatus 140 may perform authentication if the local database 142 has at least one CRP for a product to be authenticated. From time to time, or upon command from the remote device, other CRPs may be distributed from the primary database 122 to the remote device 140 to supplement the CRPs used which, if there were any possibility that the response was intercepted, would no longer be used for security reasons. The reader 140 may also refresh its own local database 142 directly from the authenticating device 110 by sending additional challenges and recording each response 150, forming a new CRP. However, if this step is implemented in a situation where the communication may be intercepted, the counterfeiter may replay the most recently acquired CRP.

In some implementations, when the device 110 has been authenticated, the reader 140 can refresh its own local database 142 directly from the authenticated device. The reader 140 issues a random challenge and the product itself provides a new response 150. In some implementations, these new challenges are provided by the remote device. For example, by the remote device using the CRP to authenticate one product at a time, even if the product is in an untrusted environment during the time of interception, the product still provides other CRPs, which may later be used to authenticate the product again. This newly generated CRP may be uploaded to the central database 122 and then distributed to still other remote devices for later authentication. In some implementations, the agreement between the reader and the product may cause the product to provide a new CRP (or a response to a second challenge provided by the reader) for each authentication that may be used later, thereby eliminating the need to separately initiate the interaction to obtain the new CRP.

Referring again to fig. 1, in some implementations, the RFID device 110 has a PUF circuit 114 and an Identifier (ID)104 associated with, for example, an Electronic Product Code (EPC). In some implementations, the ID 104 is stored by the manufacturer 102 in a non-volatile memory (ID register) 112. The enrollment authority 120 retrieves the ID 104 from the device and provides a plurality of challenges (e.g., challenge) to the PUF circuit 114_i126). The authority records the response (e.g., response) for each challenge_i128) To create a data set D representing the found challenge/response pairs (CRP). In some instances, data set D explicitly represents challenge-response pairs, e.g., as a list or in a database. The number of CRPs in D for any particular RFID is not comprehensive and may represent only a small fraction of the possible CRPs for the circuit. The authority stores the data set D associated with the ID of the device, for example in a database 122 indexed by the device identifier.

Later, the device is typically authenticated with a reader 140 (such as a portable RFID reader) after the RFID has left the supervision of a trusted party. In some instances, the reader has trusted communicative access to the regulatory agency or a database 122 created by the regulatory agency. In other examples, the reader may be disconnected from the regulatory agency while the reader is authenticating the RFID.

In some examples, the reader retrieves the ID 104 from the device 110, determines the challenge-response data D associated with the ID, and issues a challenge 146 to the circuit selected from the set of challenge/response pairs represented in D. For example, by querying the database with the ID, data D for the CRP set associated with the ID is determined. The database may be remote (e.g., database 122 controlled or trusted by a registration authority) or local (e.g., database 142 contained within the reader itself). For example, in instances where the reader will be disconnected from the regulatory agency during authentication, a portion of the master database 122 may be transferred to the reader 140 and stored in the local database 142. For example, a portion of the database may be selected based on a previous request for data for a product that is authenticated based on anticipated needs, such as data corresponding to a number of products in transit in a supply chain. For example, data is securely maintained in the reader with tamper-proof entropy to prevent the data from being exposed.

Generally, the challenge 146 is selected at the reader for a single use. The selection may be deterministic (e.g., by unordered list order selection) or random (i.e., randomly selected from the CRPs represented in D). Since each challenge is selected from 2^N(N is the number of bits in the challenge) pool of possible challenges, so even if chosen randomly, each challenge choice can be expected to be unique.

The circuit response R' 148 (the circuit response generated in the device with the PUF and sent back to the reader) is compared by the reader with the expected response from D. If the response R' is sufficiently similar to the expected response R, the circuit has been authenticated. Although an exact match is ideal, some bit error (up to a threshold) is allocated. If the response R' matches R (where the bit error is less than the threshold), then it is considered similar enough for authentication. In some embodiments, there is a significant difference between illegal responses (e.g., approximately 64 error bits in a 128-bit response) and legitimate responses (e.g., approximately 12-16 error bits in a 128-bit response). False positives (identifying imposters as authentic) and false negatives (rejecting legitimate devices) can be balanced and traded off against each other by setting appropriate authentication code distance thresholds. Other methods of determining sufficient similarity are also possible, for example, weighting different bit errors differently. If R' is not sufficiently similar, the device may be rejected, additional challenges may be issued, or other verification steps may be invoked.

In some embodiments, the reader is paired with a local database D_LAnd (5) performing maintenance. The local database may be initially obtained from a registration authority or obtained periodically, may be attached in encrypted form to a collection of RFID devices (e.g., on a DVD packaged with a plurality of products, each tagged with an RFID device), or may be embedded in encrypted form on the RFID devices themselves. Once the circuit has been authenticated, D can be augmented by the reader by issuing additional challenges and recording responses_L. Additionally or alternatively, these additional enrolled CRP can be sent back to the regulatory agency 120 to be added to the central database 120 or to other readers for further authentication along the supply chain. The additional registration allows the number of known CRPs to be refreshed to minimize the number of known CRPs at any given location or time.

Referring to fig. 2, in some embodiments as described above, during the enrollment phase, the authority 220 determines CRP data D based on a challenge 226 provided to the device 210 and a corresponding response 228 received from the device. The authority then encrypts data D (or more typically a subset of data corresponding to a subset of the enrolled challenge-response pairs) to form e (D). For example, e (d) may include a separate password for each challenge-response pair used during enrollment. The authority then passes the encrypted CRP data to the device (262), where it is stored in the memory 216 in encrypted form e (d) with the device itself 210. E (d) may be encrypted using a public/private key pair scheme, using a shared key scheme, or using any other scheme. Note that no data decryption functionality is required in the device 210. Multiple devices 210 may all use the same decryption key, grouped together, for example, by company, by recipient, by batch, or by any other collection of circuits. The reader then only needs the decryption key associated with the intended device. In some instances, the encryption key is specific to each device, e.g., determined from a key common to a group of devices and the ID 204 of the device.

Upon authentication, the RFID device 210 provides the reader with the ID and e (d) for the device, e.g., based on a request from the reader 240. In some implementations, powering the RFID causes the RFID to transmit its ID and e (d). Note that in the described scenario, the reader does not necessarily need to be connected to a central authority at the time of authentication or even after the device is registered by the central authority, as long as the reader has a key for decrypting data from the device. The reader decrypts D and selects a challenge, which is then sent to the circuit. The selection challenge may be deterministic (e.g., sequential) or random (i.e., randomly selected from the CRPs in D). In some examples, the reader makes a selection of a challenge (or challenge index) and requests only selected encrypted data from the reader, thereby avoiding the need to send the entire database on the device. In some embodiments, the reader performs further registration by sending a new challenge and receiving a corresponding response, then creates a local D_LFor subsequent authentication or for re-storage on the circuit.

When D is stored on the device, there is in principle a loss of connection between verifying that the PUF circuit is legitimate and verifying that the ID is legitimate. This can be corrected by linking the ID to the authentication process. In some embodiments, the device ID is used as part of the challenge within the PUF circuit. For example, a challenge from the reader is combined with an internal device ID before generating a response. In some embodiments, the device ID is used as part of an encryption scheme for encrypting e (d). For example, the key used to decrypt E (D) is a function of the ID and a private key known to the reader. In some embodiments, the device ID may be included in the database D prior to encryption so that the reader can use the device ID to verify the device ID; this serves as a traditional message authentication code for the device ID, ensuring that the encrypted database is made dependent on the device with a particular ID.

Referring to fig. 3, a block diagram of an exemplary RFID 300 includes a radio circuit 302 and a data element 310 (e.g., memory for ID 312 and memory for e (d) 316). In some embodiments, a PUF 320 used in an RFID 300 includes two delay-based elements 330, each of which generates a single bit from a set of delay stages 332, which terminate in an arbiter 338 that compares the delays along two selected paths based on an N-bit challenge 322. Each delay stage 332 is configured by a challenge value 326. For example, in some embodiments, each delay stage 332 is a pair of multiplexers 334. Challenge values 326 configure each multiplexer 334 to pass a particular input. Other configurations of delay stage 332 may also be used.

The two bits generated by the two delay-based elements 330 may be combined at 340, preferably in a non-linear manner (e.g., using XOR logic gates), to generate one bit of the M-bit response 350. This process is repeated M times over and over to generate a complete M-bit response. In some embodiments, each iteration uses a subsequent challenge configuration generated by a sequencer 324 (e.g., a Linear Feedback Shift Register (LFSR)). In some embodiments, more than two delay-based elements may be used, the outputs of which are either XOR'd (summed modulo 2) collectively or combined in a non-linear fashion (e.g., according to hash elements). In some embodiments, only one delay-based element is used. The plurality of channels are generated by using the sequencers either extensively or using a plurality of sequencers. For example, a first path through the delay-based element is controlled by a first challenge from a first sequencer. The second channel is then controlled by a second challenge from the second sequencer. The two channels are combined, for example, using XOR logic gates. Any combination of one or more sequencers and one or more delay-based elements may be used to generate challenge response pairs.

With reference to figure 4 of the drawings,in some embodiments, the initial challenge 410 is used to launch (seed) a deterministic sequencer 414 (e.g., an LFSR). Each response bit R_i440 are all through the challenge_i418 configured PUF circuit 420. Each subsequent challenge_i418 are each generated by a deterministic sequencer 414. Each subsequent challenge_i418 may each be based on the type of sequencer and each challenge_i418 is generated by one or more iterations of sequencer 414. This process may be repeated M times in order to generate an M-bit response 450. This process is illustrated in fig. 5, where M challenges (510, 512, 514.., 518) are used to generate M response bits (540, 542, 544.., 548), which are combined to form an M-bit response 550.

In some embodiments, as shown in fig. 3, the PUF circuit incorporates a sequencer, e.g., an LFSR. The sequencer accepts an N-bit challenge 322 (i.e., a challenge sent from the reader or a challenge sent from the regulatory agency to the device) and generates a deterministic sequence of subsequent N-bit challenges. Each response bit is generated by the PUF circuit in response to an initial challenge and each subsequent challenge in the sequence. For example, each challenge bit is used as a configuration control 326 for each delay stage 332 of delay-based element 330.

Referring to fig. 2, in some embodiments, a small number of CRPs may be stored 262 in the memory 216 in encrypted form e (d) using means 210. As before, e (d) may be encrypted using a public/private key pair scheme, using a shared key scheme, or using any other scheme. In some embodiments, the encryption key is a function of the device ID 204 and a private key within the reader.

The reader 240 retrieves the device ID 204 and the encrypted data e (d) from the device 210. The data D is encrypted and the challenge C is selected. The reader randomly selects the offset delta and then calculates the challenge precursor C according to a sequencer implemented in the device_PSo that C is_POccurs in the deterministic sequence Δ iteration before C. The reader will then challenge C_PIs sent to the suitThe challenge C is thus sent in communication between the reader and the device from not the wrong way round. The PUF circuit generates a response of a minimum of Δ + mbits, where M is the number of bits in the response. For example, the device may be configured to generate a 2M-bit response, while a Δ unknown to the device may be selected by the reader in the range of 0 to M-1. The expected response R' to the challenge C is expected at a number Δ bits in the device response.

For example, referring to fig. 6, e (d) includes CRP for challenge 614 and response 654. The reader encrypts E (D) and determines a precursor challenge C_PAnd will ask C_PTo the device. The device is based on C_P→challenge₁610 generate response bits R for configuration₁640. The device then generates response bits for subsequent challenge in a deterministic order, e.g. challenge_Δ612 results in bit R_Δ642. Receiving by the reader the initial response bit R₁640 to R_Δ642, but not as a seek response. After receiving the delta initial response bits, the input bits constitute the response 654 in response to the desired challenge. Namely, challenge_Δ+1614 to challenge_Δ+M616 result in a response bit R_Δ+1644 to R_Δ+M646, which constitute a corresponding response 654. The device is unaware of Δ and will therefore continue to generate subsequent challenge 618 and response bits 648 for tracking response 656, which the reader will ignore. The apparatus may generate any number of response bits as long as there are at least Δ + M bits.

The reader compares R 'with the expected R from the decoded CRP and determines whether R' is close enough to R for authentication. In this way, the sought response is buried in the response stream at a location unknown to the reader.

In many of the above techniques, the data D representing the enrolled challenge-response pairs is explicitly (e.g.) as a binary list of challenges and received responses. In some embodiments, rather than explicitly storing such binary pairs, data that allows prediction of a response to an additional challenge is determined by the authority and included in the data (or determined by the authority and included in the data in addition to explicitly storing such binary pairs). For example, a PUF digital model on an RFID may be used to determine the expected response. It is noted, however, that the PUF is designed to prevent unauthorized parties from building such a model (or is designed such that it is difficult for unauthorized parties to build such a model).

In some embodiments, the PUF is designed to have additional output connections. These connections expose enough of the circuit internal work to produce a PUF circuit model. After the model is generated, the extra output connections are broken or rendered unusable. Examples include the use of separate encryption keys or fuses that are overloaded and would break the connection.

Referring to fig. 7, as an example of an additional connection, the PUF circuit has three output bits R_iA 754、R_iB756. And R_i752. Output R_i752 for forming a response and is formed as R_iA754 and R_iB756 (e.g., using XOR logic gates). Thus R_iA754 and R_iB756 are used only as additional outputs for generating the model. That is, the authority provides the challenge to the device, which in turn provides a sequence of bits according to each of the delay-based elements prior to the XOR. These raw responses (e.g., R) are then used by the regulatory agency_iA754 and R_iB756) To build a model and predict the bit output of each delay-based element in response to any challenge. After enrollment, the PUF is changed to prevent direct output of the raw output without XOR. For example, a fuse 744 is placed leading to each additional output (R)_iA754 and R_iB756) On the line of (2). Once the model is built, each fuse 744 is overloaded and destroyed to break the output connection. The XOR step, or other form of nonlinear combination of the outputs of the PUF elements, prohibits subsequent unauthorized parties from modeling.

In some examples, the circuit model is encrypted as E (D)_M) And stored on the device. The reader then receives the ID and E (D) from the device_M). Equipped with means for E (D)_M) Reader determination circuit model D of the encryption key of_M. The reader generates an arbitrary random challenge, sends the challenge to the PUF circuit, receives a circuit response R', and utilizes the circuit model D_MThe expected response, R, is determined and R' and R are compared. If R is close enough to R', the circuit is validated. In some embodiments, the circuitry incorporates the ID into the challenge. In some embodiments, for E (D)_M) Incorporates the ID.

As shown in fig. 3, an implementation of a PUF circuit uses a pair of nearly identical signal traces driven from a common source, routed through a chain-switched multiplexer pair. The challenge word controls the multiplexer and the output is determined at a race condition arbiter at the end of the multiplexer chain. Natural variations in the manufacturing process create unpredictable signal path propagation delays in the multiplexer. Thus, the identical device generates a unique timing signature in another way, causing the arbiter to output a unique bit for each unique challenge. In some embodiments, multiple chains are used and the results are combined to form a PUF output. A multi-bit response is generated by concatenating arbiter output bits that originate from a deterministic sequence of challenges. This type of circuit can be simulated in hardware or software in a deterministic manner. For a given challenge, the complete model produces an output that is practically indistinguishable from a true PUF circuit. For use as an embedded cryptographic model, this helps to have a model that is easy to build, requires minimal components or relatively simple code, and requires only a small amount of information about the device being modeled (e.g., a true challenge/response pair).

An N-bit long multiplexer PUF circuit may be abstracted as a chain of N polarity switches and N +1 differential delay blocks. Each delay block holds a signed digital value delta_n(N ═ 0.. N), digital value δ_nDescribing the relative contribution of the multiplexer stage to the PUF output, where δ₀Element representation and challengeThe off-set. Challenge bit c_nFor each stage polarity switch p_nAnd (3) controlling:

p_n＝(1＝＝c_n)？(+1):(-1)

calculating the equivalent of the PUF output deviation for a given challenge by applying the given challenge to the switches and accumulating the delays, wherein the polarity switch of each stage conditionally negates the sum of the previous stages:

bias＝(...((δ_N*p_N+δ_N-1)*p_N-1+δ_N-2)...+δ₂)*p₂+δ₁)*p₁+δ₀

the PUF arbiter operation may be approximated as a sign of the verification output deviation; therefore, the output bit r ═ 0 (deviation ═ 0).

In one method of modeling a particular PUF circuit, the N +1 δ unique to that circuit are determined by iterative approximation_nThe value is obtained. Initially, all δ will be_nThe value is set to 0. For each challenge C_k(c of length N)_n，kArray), the model all outputs the bias b_kAnd corresponding model result r_k. For a corresponding challenge, the device actually returns a bit value a_k. The back propagation of the training bias then passes through δ_nArray increment of value t_kAt each stage by polarity p_nConditionally negated. In case the model is identical to the PUF device (a)_k＝＝r_k) The training bias increment is set such that it increases the number of current total biases:

t_k+＝[(1＝＝a_k)？(+1):(-1)]

in case the model does not conform to the PUF device (a)_k≠r_k) Setting the training offset delta such that it is equal for all deltas_nThe values are corrected to produce the desired result:

then increment the training deviation (t)_k) Applied to each delta_n：

δ₀＝δ₀+t_k

δ₁＝δ₁+t_k*p₁

δ₂＝δ₂+t_k*p₁*p₂

δ_N＝δ_N+t_k*p₁*p₂*...*p_N-1*p_N

This step is repeated for all available PUF data (CRP). The model is qualified when the error rate cannot be distinguished from the natural error rate of the PUF device. In some embodiments, thirty-two 64-bit challenges each producing a 64-bit response are sufficient to produce a model of a single 64-multiplexer PUF chain. By combining two such chains, e.g., using XOR, the same model may need to be far more than 2⁶⁴And (6) checking. Thus, the manufacturer can model the two chains separately and then cut off the direct chain output to limit future use to the XOR output. This makes it computationally difficult to reproduce the model.

In some examples, the RFID-based techniques described above are implemented in an RFID device that conforms to the ISO 14443-A, HF 13.56 operating frequency. The lengths of the challenge and response are configured in lengths of 64, 128, or 256 bits. The device has 512-bit user memory. In some instances, challenge-response interactions are performed by receiving a challenge using a memory-mapped address using a standard over-the-air command, where the PUF output is written to another memory-mapped register. Thus, using a written sequence that provides a challenge, a read is then made to retrieve a response. In some instances, new challenge-response commands are used such that only a single interaction is used to both provide the challenge and retrieve the response.

The techniques described above may be used in conjunction with the system described in co-pending application 11/273,920. For example, these techniques may also be used to authenticate devices other than proximity devices. Although these techniques are described in terms of RFID and RFID readers, it is useful to note that other devices (including proximity devices and readers) may also utilize these techniques. Examples include: a bluetooth enabled device that utilizes a PUF circuit to verify a connection; a portable media device that authenticates the device with the PUF circuit, e.g., when media is downloaded to the device; a handset authenticates the handset using a PUF circuit when connected to a network. Furthermore, RFID is seen in a variety of contexts, including use in security goods (e.g., pharmaceuticals, electronic devices, or tagged handbags) and to carry personal information (e.g., security badge cards, mass transit passes, or passports). As REIDs become more popular, RFID readers also become more popular. For example, a cell phone may be constructed to include an RFID reader so that the cell phone can be used to authenticate the RFID by communicating with a central authority. Different technologies are suitable for different environments.

Examples of the above methods may be implemented in hardware, in software, or in a combination of hardware and software. The hardware may include custom integrated circuits, or configurable circuits such as Field Programmable Gate Arrays (FPGAs). Hardware implementations may be specified in terms of circuit specification instructions stored on a computer-readable medium, for example, in the form of configuration data for an FPGA or in the form of a Hardware Description Language (HDL), such as Verilog. Software implementations may include instructions stored on a computer-readable medium for controlling the execution of a general-purpose or special-purpose controller or processor. For example, the authentication station may include a general purpose processor controlled by a stored program, while the proximity device may include a dedicated control processor controlled by instructions stored on the device.

It is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the invention, which is defined by the scope of the appended claims. Other embodiments are within the scope of the following claims.

Claims (9)

1. A method of authenticating a device using an authentication station, the device having the capability of: accepting a challenge value from the authentication station and returning a response value to the challenge value to the authentication station, the response value being dependent on a manufacturing characteristic of the device, the method comprising:

identifying the device, comprising: receiving, at the authentication station, identification data from the device to be authenticated;

determining authentication data characterized by one or more challenge value and response value pairs associated with the device being identified, the one or more challenge value and response value pairs previously obtained by a trusted authority in communication with the device, wherein the determination of the authentication data does not require communication between the authentication station and the trusted authority after the device is identified; and wherein the authentication data comprises model parameters sufficient to predict a response value for each of a plurality of challenge values, wherein the plurality of challenge values from which the response value is predicted are not represented in one or more of the pairs of challenge values and response values;

providing a first challenge value from the authentication station to the device;

accepting at the authentication station a first response value from the device;

determining whether the first challenge value and first response value pair substantially match the authentication data.

2. The method of claim 1, wherein the model parameters include delay parameters corresponding to delay elements in the apparatus from which response values are determined at the apparatus.

3. The method of claim 1, further comprising: selecting a challenge value at the authentication station and determining an expected response value for the selected challenge value in dependence on the model parameters, and wherein determining whether the first challenge value and first response value pair sufficiently match in dependence on the authentication data comprises determining whether the first response value sufficiently matches the expected response value.

4. A method for authenticating devices, each device having the capability to: accepting a challenge value and returning a response value to the challenge value, the response value being dependent on a manufacturing characteristic of the device, the method comprising registering each of a plurality of the devices, including:

providing a plurality of challenge values to the device;

accepting a corresponding plurality of response values from the device;

calculating a model parameter from the plurality of challenge values and the corresponding plurality of response values, the model parameter being sufficient to be used to predict a plurality of response values corresponding to a plurality of challenge values provided to the device but not represented in the plurality of challenge values; and

storing the model parameters for subsequent authentication of the device.

5. The method of claim 4, wherein storing the model parameters comprises: storing the model parameters in association with an identification of the apparatus.

6. The method of claim 4, wherein storing the model parameters comprises: providing the password for the model parameters to the device for storage on the device.

7. The method of claim 4, further comprising authenticating one of a plurality of the devices, comprising:

retrieving the model parameters of the device;

providing a first challenge value to the device;

accepting a first response value from the device;

determining whether the first challenge value and the first response value pair sufficiently match according to the model parameters.

8. The method of claim 4, wherein after accepting the response value from the device for calculating the model parameter, inhibiting the device from subsequently providing a response value suitable for subsequently calculating a model parameter for the device.

9. The method of claim 4, wherein calculating the model parameters comprises: a parameter corresponding to a circuit parameter of a circuit element of the device is calculated, the parameter being used to calculate a response value from the challenge value.