AUTHENTICATION WITH PHYSICAL UNCLONABLE FUNCTIONS

• US 20090083833A1
• Filed: 09/19/2008
• Published: 03/26/2009
• Est. Priority Date: 09/19/2007
• Status: Active Grant

• Current Assignee: Verayo, Inc.
• Original Assignee: Verayo, Inc.
• Inventors: Ziola, Thomas, Suh, Gookwon Edward, Paral, Zdenek, Khandelwal, Vivek, Devadas, Srinivas
• Granted Patent: US 8,782,396 B2
• Time in Patent Office: Days
• US Class Current: 726/2
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 2221/2129 Authenticate client device independently of the user
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3271 using challenge-response
• CPC Class Codes: H04L 9/3278 using physically unclonable functions [PUF]
• CPC Class Codes: H04W 12/062 Pre-authentication
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication

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.

Claims

1. A method for authenticating a device using an authentication station, said device providing a capability to accept a challenge value from the authentication station and return a response value to the challenge value to the authentication station that depends on fabrication characteristics of the device, the method comprising:

identifying the device, including accepting identification data at the authentication station from the device to be authenticated;

determining authentication data characterizing one or more pairs of challenge and response values associated with the identified device that were previously obtained by a trusted authority in communication with the device, wherein said retrieving of the data does not require communication between the authentication station and the trusted authority after identifying the device;

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

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

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

2. The method of claim 1 wherein the device comprises a radio frequency proximity device and the steps of accepting the identification data, providing the first challenge, and accepting the first response each comprise communicating between the authentication station and the radio frequency proximity device using a radio communication protocol.

3. The method of claim 2 wherein the radio communication protocol is compatible with an ISO 14443 standard.

4. The method of claim 1 wherein the identification data represents and Electronic Product Code (EPC) associated with the device.

5. The method of claim 1 wherein the authentication station comprises one of a plurality of distributed authentication stations associated with the trusted authority.

6. The method of claim 1 wherein determining the authentication data comprises:

prior to accepting the identification from the device, accepting data associating each of a plurality of device identifications with a corresponding subset of pairs of challenge and response values obtained by the trusted authority for the device corresponding to the device identification; and

after identifying the device, accessing the subset of values for the device according to the accepted identification data.

7. The method of claim 1 wherein determining the authentication data comprises:

accepting an encryption of the authentication data at the authentication station from the device.

8. The method of claim 7 further comprising, prior to identifying the device, receiving decryption information for decrypting the encryption of the data accepted from the device.

9. The method of claim 1 wherein the authentication data comprises model parameters sufficient to predict a response value for each of a plurality of challenge values.

10. The method of claim 9 wherein the model parameters comprise delay parameters corresponding to delay elements in the device according to which response values are determined at the device.

11. The method of claim 9 further comprising selecting a challenge value at the authentication station and determining a predicted response value for the selected challenge according to the model parameters, and wherein determining whether the pair of the first challenge value and the first response value sufficiently match according to the authentication data includes determining whether the first response value sufficiently matches the predicted response value.

12. The method of claim 1 further comprising determining additional authentication data at the authentication station suitable for further authentication of the device, including generating one or more additional challenge values, providing the challenge values to the device, and accepting corresponding response values from the device.

13. The method of claim 12 further comprising providing the additional authentication data to the trusted authority.

14. The method of claim 12 further comprising providing an encryption of the additional authentication data to the device.

15. The method of claim 1 further comprising:

determining the first challenge value as a preceding value to a second challenge value in a deterministic sequence associated with the device; and

determining a second response value from the accepted first response value;

wherein determining whether the pair of the first challenge value and the first response value sufficiently match according to the authentication data comprises determining whether the pair of the second challenge value and the second response value sufficiently match according to the authentication data.

16. A method for improving authentication error rates comprising:

providing multiple challenges to an entity;

performing authentication of the entity based on corresponding responses to the multiple challenges.

17. A method for authenticating a device comprising:

providing a challenge to the device;

combining the challenge with an identifier of the device stored at the device; and

providing a response to the combination of the challenge and the identifier.

18. A method comprising:

maintaining multiple databases holding challenge-response pairs for devices;

enabling authentication of devices using any one of the multiple databases; and

substantially preventing disclosure information in any one of the databases based on disclosure of information in another of the databases.

19. A device security circuit comprising:

circuitry for combining a plurality of outputs, each output being determined by a corresponding control input for selecting physical characteristics of the device upon which the output depends; and

using the combination of the plurality of outputs for a security function associated with the device.

20. The device of claim 19 further comprising:

a plurality of separate circuits, each for generating a different one of the plurality of outputs.

21. The device of claim 19 further comprising:

a circuit for generating multiple of the plurality of outputs.

22. The device of claim 19 further comprising:

circuitry for generating the control inputs from challenges values provided to the device.

23. The device of claim 22 wherein the circuitry for generating the control inputs includes a linear feedback shift register.

24. The device of claim 19 wherein the circuitry for combining the plurality of outputs comprises circuitry implementing an exclusive OR (XOR) operation.

25. A method for authenticating devices, each device providing a capability to accept a challenge value and return a response value to the challenge value that depends on fabrication characteristics of the device, the method comprising, enrolling 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;

computing model parameters from the plurality of challenge values and corresponding plurality of response values, the model parameters being sufficient to predict response values corresponding to challenge values provided to the device; and

storing the model parameters for subsequent use for authenticating the device.

26. The method of claim 25 wherein storing the model parameters comprises storing the model parameters in association with an identification of the device.

27. The method of claim 25 wherein storing the model parameters comprises providing an encryption of the model parameters to the device for storage on the device.

28. The method of claim 25 further comprising authenticating one of the devices, including:

retrieving the model parameters for the device;

providing a first challenge value to the device;

accepting a first response value from the device;

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

29. The method of claim 25 wherein after accepting the response values for computing the model parameters from the device, inhibiting the device from subsequently providing response values suitable for subsequent computing of model parameters for the device.

30. The method of claim 25 wherein computing the model parameters includes computing parameters corresponding to circuit parameters of circuit elements of the device used to compute a response value from a challenge value.

31. A security device comprising:

a communication interface for accepting a challenge value from an authentication station and providing a corresponding response value to the authentication station;

a sequencer for determining a sequence of configuration values based on the challenge value; and

a response circuit whose functional characteristics depend on fabrication characteristics of the circuit that are substantially unique to the device, said circuit including configuration inputs coupled to the output of the sequencer such that an output of the response depends on a the configuration value and the fabrication characteristics;

wherein the device is configured to accept the challenge value and generate the corresponding response value according to sequential configurations of the response circuit configured according to outputs of the sequencer.

32. The security device of claim 31 wherein the sequencer comprises a linear feedback shift register.

33. The security device of claim 31 wherein the response circuit comprises a plurality of delay elements configurable according to the configuration input to form one or more delay paths through the response circuit.