Volatile device keys and applications thereof

• US 7,839,278 B2
• Filed: 06/16/2009
• Issued: 11/23/2010
• Est. Priority Date: 11/12/2004
• Status: Expired due to Fees

• Current Assignee: Verayo, Inc.
• Original Assignee: Verayo, Inc.
• Inventors: Ziola, Thomas, Devadas, Srinivas
• Primary Examiner(s): Hunnings; Travis R
• Application Number:
  US12/485,479
• Publication Number:
  US 20090254981A1
• Time in Patent Office: 525 Days
• Field of Search: 340/572, 340/10, 340/505, 713/200, 713/181, 713/189
• US Class Current: 340/539.1
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/445 by mutual authentication, e.g. between devices or programs
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/76 in application-specific integrated circuits [ASIC] or field-programmable devices, e.g. field-programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 2221/2129 Authenticate client device independently of the user
• CPC Class Codes: G11C 16/20 Initialising; Data preset; Chip identification
• CPC Class Codes: G11C 16/22 Safety or protection circuits preventing unauthorised or accidental access to memory cells
• CPC Class Codes: G11C 2029/4402 Internal storage of test result, quality data, chip identification, repair information
• CPC Class Codes: G11C 2029/5002 Characteristic
• CPC Class Codes: G11C 7/24 Memory cell safety or protection circuits, e.g. arrangements for preventing inadvertent reading or writing; Status cells; Test cells
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/0838 Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these network architectures or network communication protocols for key exchange in a packet data network H04L63/061
• CPC Class Codes: H04L 9/0877 using additional device, e.g. trusted platform module [TPM], smartcard, USB or hardware security module [HSM]
• CPC Class Codes: H04L 9/304 based on error correction codes, e.g. McEliece
• CPC Class Codes: H04L 9/3278 using physically unclonable functions [PUF]

Abstract

A key is determined from a volatile response using circuitry on the device. The volatile response depend on process variation in fabrication of the device. Error control data that depends on the first volatile response can be computed, stored externally to the device, and then used to generate the key using a volatile response using the circuit. Applications of volatile keys include authentication and rights management for content and software.

Claims

1. A method comprising:

receiving identification information from a device;

sending a first challenge to a device, the first challenge selected from a database associated with the received identification information, the database including data characterizing a plurality of first challenges and a plurality of corresponding responses, each response associated with a corresponding first challenge;

receiving a volatile response from the device, the volatile response determined in the device according to a sequence of challenge values generated in the device on the basis of the first challenge; and

authenticating the device using the received volatile response and the response corresponding to the sent first challenge.

2. The method of claim 1, wherein the device comprises a proximity device.

3. The method of claim 2, wherein the device comprises a radio frequency identification device (RFID).

4. The method of claim 1, wherein the sequence of challenges is generated by operating on the first challenge with a linear-feedback shift register.

5. The method of claim 1, wherein each challenge included in the generated sequence of challenges includes at least 64 bits.

6. The method of claim 1, wherein each challenge in the sequence of challenges is applied to a circuit in the device to generate a corresponding part of the volatile response.

7. The method of claim 6, wherein each challenge in the sequence of challenges is applied to a corresponding one of a plurality of circuits in the device, each circuit generating a partial response, the volatile response formed from the plurality of partial responses.

8. The method of claim 6, wherein each challenge in the sequence of challenges is applied to the circuit to generate a corresponding one of a plurality of partial responses, the volatile response formed from the plurality of partial responses.

9. The method of claim 6, wherein the circuit is configurable to form any of a plurality of signal paths and application of a challenge to the circuit includes configuration of one of the signal paths.

10. The method of claim 1, wherein the volatile response is dependent on process variation during fabrication of the device.

11. The method of claim 1, wherein the device is one of a group of devices fabricated according to a same design, the volatile response unique in the group to that device.

12. An integrated circuit comprising:

a communication module configured to communication with an authentication device; and

circuitry configured to generate a volatile response, the volatile response determined according to a sequence of challenge values generated in the integrated circuit on the basis of a first challenge received from the authentication device, wherein the circuitry is configured to accept each challenge in the sequence of challenges and, for each challenge, to generate a corresponding partial response, the volatile response being formed from the plurality of partial responses;

wherein the communication module is configured to send the volatile response to the authentication device for authentication of the integrated circuit.

13. The integrated circuit of claim 12, wherein the integrated circuit forms a component of a proximity device.

14. The integrated circuit of claim 13, wherein the integrated circuit forms a component of a radio frequency identification device (RFID).

15. The integrated circuit of claim 12, wherein the communication module is configured to send identification information to the authentication device and to receive the first challenge from the authentication device, wherein the first challenge is selected by the authentication device on the basis of the identification information.

16. The integrated circuit of claim 12, wherein the circuitry to generate the volatile response includes a linear-feedback shift register configured to generate the sequence of challenges based on the first challenge.

17. The integrated circuit of claim 12, wherein each challenge included in the sequence of challenges includes at least 64 bits.

18. The integrated circuit of claim 12, wherein the circuitry to generate the volatile response includes a plurality of subcircuits, each subcircuit configured to accept at least one of the challenges in sequence of challenges and to generate a corresponding partial response based on the accepted challenge, the volatile response being formed from the plurality of partial responses.

19. The integrated circuit of claim 12, wherein the circuitry is configurable to form any of a plurality of signal paths and wherein, in response to an application of a challenge in the sequence of challenges to the circuitry, one of the signal paths is configured.

20. The integrated circuit of claim 12, wherein the volatile response is dependent on process variation during fabrication of the integrated circuit.

21. The integrated circuit of claim 12, wherein the integrated circuit is one of a group of integrated circuits fabricated according to a same design, the volatile response unique in the group to that integrated circuit.

22. A system for authenticating a device on the basis of identification information received from the device, comprising:

a database storing data characterizing a plurality of first challenges and a plurality of corresponding responses, each response associated with a corresponding first challenge;

a selection module configured to select from the database a first challenge associated with the received identification information;

a communication module configured to

send the selected first challenge to the device, and

receive a volatile response from the device, the volatile response determined in the device according to a sequence of challenge values generated in the device on the basis of the first challenge; and

an authentication module configured to use the received volatile response and the response corresponding to the selected first challenge.

23. The system of claim 22, wherein the device comprises a proximity device.

24. The system of claim 23, wherein the device comprises a radio frequency identification device (RFID).

25. The system of claim 22, wherein the device is one of a group of devices fabricated according to a same design, the volatile response determined in the device unique in the group to that device.

26. The system of claim 22, wherein the volatile response is dependent on process variation during fabrication of the device.

27. A method comprising:

determining first challenge at a device, the first challenge selected from a database associated with the device, the database including a plurality of first challenges and corresponding codes, each first challenge corresponding to a code;

determining a volatile response in the device according to a sequence of challenge values generated in the device on the basis of the determined first challenge;

forming a cryptographic key in the device from the determined volatile response and the code corresponding to the first challenge; and

performing a cryptographic function in the device using the formed cryptographic key.

28. The method of claim 27 wherein the database is stored in a non-volatile storage in the device.

29. The method of claim 27 wherein the determined volatile response and the formed cryptographic keys are not stored in any non-volatile storage in the device.

30. The method of claim 29 wherein the code corresponding to the determined first challenge satisfies a constrained relationship between the cryptographic key, the volatile response, and the code.

31. The method of claim 29 wherein the code is determinable from the cryptographic key using the volatile response.

32. The method of claim 29 wherein the cryptographic key is determinable from the code using the volatile response.

33. The method of claim 30 wherein the constrained relationship comprises an exclusive OR relationship.

34. The method of claim 27 wherein the code corresponding to the determined first challenge comprises an encoding of the cryptographic key according to the volatile response.

35. The method of claim 34 wherein forming the cryptographic key comprises performing an exclusive OR operation using the determined volatile response and the code corresponding to the determined first challenge.

36. The method of claim 27 wherein performing the cryptographic function comprises performing a signing operation.

37. The method of claim 27 wherein performing the cryptographic function comprises performing a decryption operation.

38. The method of claim 27 wherein forming a cryptographic key in the device from the determined volatile response comprises forming a private key of a public key and private key pair.

39. The method of claim 38 wherein the formed private key was previously generated in the device using a volatile response to the determined first challenge.

40. The method of claim 38 wherein the formed private key is maintained private to the device without disclosure outside the device.

41. The method of claim 27 wherein the database further comprises error correction data corresponding to each of the first challenges.

42. A method comprising:

determining first challenge at a device;

determining a volatile response in the device according to a sequence of challenge values generated in the device on the basis of the determined first challenge;

determining a cryptographic key in the device, and forming a code from the cryptographic key, wherein at least one of determining the cryptographic key and forming the code from the cryptographic key is based on the determined volatile response; and

repeating determining the volatile response in the device according to a sequence of challenge values generated in the device on the basis of the determined first challenge, and determining the cryptographic key in the device from the repeated determined volatile response and the code.

43. The method of claim 42 further comprising storing data associating the code and the first challenge in a non-volatile storage in the device.

44. The method of claim 42 wherein determining the cryptographic key comprises determining a private key of a public key and private key pair.

45. The method of claim 44 wherein determining the private key comprises using the volatile response to determine the private key.

46. The method of claim 45 further comprising determining the public key corresponding to the private key based on the determined volatile response.

47. The method of claim 42 wherein determining the first challenge comprises receiving the first challenge at the device, and the method further comprises providing the code from the device.

48. An integrated circuit comprising:

a database configured to store a plurality of first challenges and corresponding codes, each first challenge corresponding to a code;

circuitry configured to generate a volatile response, the volatile response determined according to a sequence of challenge values generated in the integrated circuit on the basis of a first challenge received from the database;

a cryptographic key generator configured to accepted the volatile response and a code corresponding to the first challenge; and

a cryptographic module configurable according to a cryptographic key generated in the key generator.

49. A method comprising:

determining first challenge at a device;

determining a volatile response in the device according to a sequence of challenge values generated in the device on the basis of the determined first challenge;

determining a cryptographic key in the device, including determining a private key of a public key and private key pair; and

forming a code from the cryptographic key;

wherein at least one of determining the cryptographic key and forming the code from the cryptographic key is based on the determined volatile response.

50. The method of claim 49 wherein determining the private key comprises using the volatile response to determine the private key.

51. The method of claim 50 further comprising determining the public key corresponding to the private key based on the determined volatile response.