Authentication with physical unclonable functions

• US 8,782,396 B2
• Filed: 09/19/2008
• Issued: 07/15/2014
• Est. Priority Date: 09/19/2007
• Status: Expired due to Fees

• Current Assignee: Verayo, Inc.
• Original Assignee: Verayo, Inc.
• Inventors: Ziola, Thomas, Paral, Zdenek, Devadas, Srinivas, Suh, Gookwon Edward, Khandelwal, Vivek
• Primary Examiner(s): Lipman, Jacob
• Application Number:
  US12/234,095
• Publication Number:
  US 20090083833A1
• Time in Patent Office: 2,125 Days
• Field of Search: 713/155
• US Class Current: 713/155
• 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 determining of the data includes securely receiving the data characterizing the one or more pairs of challenge and response values directly from the device at the authentication station and 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 identification data represents and Electronic Product Code (EPC) associated with the device.

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

4. 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.

5. 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.

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

7. The method of claim 1 wherein securely receiving the data from the device 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 any challenge value.

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. 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 the authentication data comprises model parameters sufficient to predict a response value for each of a plurality of challenge values for which response values have not been provided from 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.

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

17. The method of claim 16 wherein determining the predicted response includes predicting a plurality of delay values corresponding to the delay elements according to the model parameters and the first challenge, and determining the response by combining the plurality of delay values.

18. The method of claim 15 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.

19. The method of claim 18 wherein a response to the selected challenge has not previously been received from the device, and determining the predicted response value includes numerically simulating operation of the device according to the model parameters to determine the predicted response.