Low-complexity cryptographic techniques for use with radio frequency identification devices

• US 7,532,104 B2
• Filed: 02/19/2004
• Issued: 05/12/2009
• Est. Priority Date: 05/06/2003
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: RSA Security Incorporated (Symphony Technology Group LLC)
• Inventors: Juels, Ari
• Primary Examiner(s): Holloway, III; Edwin C
• Application Number:
  US10/782,309
• Publication Number:
  US 20040222878A1
• Time in Patent Office: 1,909 Days
• Field of Search: 340/5.61, 340/5.8, 340/5.1, 340/5.64, 340/5.26, 340/10.1, 340/426.36, 340/825.69, 340/572.1, 713/168, 713/150, 713/182, 380/258, 380/270, 341/174, 341/176, 361/171
• US Class Current: 340/5.61
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3273 for mutual authentication network architectures or network communication protocols for achieving mutual authentication in a packet data network H04L63/0869

Abstract

Cryptographic techniques are provided having a complexity level which permits their implementation in inexpensive radio frequency identification (RFID) tags or other RFID devices. In an RFID system comprising one or more RFID devices and at least one reader that communicates with the devices, a plurality of pseudonyms is associated with a given one of the RFID devices. The RFID device transmits different ones of the pseudonyms in response to different reader queries, and an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device.

Claims

1. A method for use in an RFID system comprising at least one RFID device and at least one reader which communicates with the RFID device, the method comprising the steps of:

associating a plurality of pseudonyms with the RFID device; and

transmitting from the RFID device different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier authenticates itself to the RFID device by releasing to the RFID device an authentication value β

_i unique to a given pseudonym α

_i transmitted by the RFID device;

wherein the RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ

_i unique to the given pseudonym α

_i transmitted by the RFID device; and

wherein at least one of the values α

_i, β

_i and γ

_i is selected from a corresponding set of such values that is stored in the RFID device and updated using one-time pads transmitted by the verifier to the RFID device over multiple authentication sessions carried out between the verifier and the RFID device.

2. The method of claim 1 wherein the transmitted pseudonyms are authenticated by the reader.

3. The method of claim 1 wherein the transmitted pseudonyms are authenticated by a verifier other than the reader.

4. The method of claim 1 wherein the RFID device is configured to authenticate itself to a verifier only after the verifier has authenticated itself to the RFID device.

5. The method of claim 1 wherein one or more of the pseudonyms each comprise an identifier of the RFID device.

6. The method of claim 1 wherein the pseudonyms are stored in the RFID device as an ordered list of pseudonyms, the method further including the steps of designating a particular one of the pseudonyms as a current pseudonym and, in response to a given reader query, transmitting the current pseudonym, wherein over a plurality of reader queries the pseudonym designated as the current pseudonym periodically cycles through the list of pseudonyms.

7. The method of claim 6 wherein after the current pseudonym is transmitted by the RFID device responsive to the given query, a different one of the plurality of stored pseudonyms is designated as the current pseudonym to be transmitted responsive to a subsequent query.

8. The method of claim 1 wherein one or more of the pseudonyms are generated on an as-needed basis within the RFID device.

9. The method of claim 1 wherein one or more of the pseudonyms are generated externally to the RFID device.

10. The method of claim 1 further including the step of limiting a rate at which the RFID device is permitted to transmit pseudonyms responsive to reader queries.

11. The method of claim 1 further including the step of periodically altering one or more of the plurality of pseudonyms.

12. The method of claim 11 wherein the altering step is implemented responsive to receipt of refresh information in the RFID device from a verifier.

13. The method of claim 12 wherein the refresh information comprises one or more refresh values transmitted from the verifier to the RFID device after mutual authentication of the RFID device and the verifier.

17. The method of claim 1 wherein a verifier of the system is configured to store for a given RFID device T_x a static identifier id_x corresponding to at least one pseudonym of T_x.

20. The method of claim 1 wherein a verifier of the system in conjunction with an authentication session with the RFID device specifies a value identifying a particular pseudonym to be transmitted by the RFID device.

21. The method of claim 1 wherein the RFID device determines which of the plurality of pseudonyms to transmit responsive to a given reader query based at least in part on timing information.

22. The method of claim 1 wherein the RFID device incorporates a pseudorandom number generator, where ƒ

<sub>κ

x</sub> (i) represents an output of the pseudorandom number generator for index i, where κ

_x is a seed associated with the RFID device.

23. The method of claim 22 wherein the RFID device generates the plurality of pseudonyms as pseudonyms α

₁=ƒ

(1), α

₂=ƒ

(2), . . . , α

_k=ƒ

(k).

31. The method of claim 1 wherein one or more of the pseudonyms each comprise a portion of an identifier of the RFID device.

14. A method for use in an RFID system comprising at least one RFID device and at least one reader which communicates with the RFID device, the method comprising the steps of:

associating a plurality of pseudonyms with the RFID device; and

transmitting from the RFID device different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device; and

wherein for a given value κ

utilized in the RFID device, a vector Δ

_κ

={δ

_κ

⁽¹⁾, δ

_κ

⁽²⁾, . . . , δ

_κ

^(m)} of one-time pads is maintained in the RFID device, wherein the one-time pad δ

_κ

⁽¹⁾ is designated as a live pad and is used by the RFID device to update the value κ

, where m denotes a number of authentication sessions over which one-time pads are constructed.

15. The method of claim 14 wherein the value κ

is updated by computing κ

←

κ

⊕

δ

_K ⁽¹⁾.

16. The method of claim 14 wherein in conjunction with updating the value κ

, the vector Δ

_κ

is updated utilizing a vector {tilde over (Δ

)}_κ

={{tilde over (δ

)}_κ

⁽¹⁾, {tilde over (δ

)}_κ

⁽²⁾, . . . , {tilde over (δ

)}_κ

^(m)} of one-time pads, the vector Δ

_κ

being updated by discarding the previous live pad {tilde over (δ

)}_κ

⁽¹⁾, setting δ

_κ

⁽ⁱ⁾=δ

_κ

⁽ⁱ⁺¹⁾ for 1≦

i≦

n−

1, setting δ

_κ

^(m)=0^l, and performing an element-wise exclusive-or of Δ

_κ

and {tilde over (Δ

)}_κ

by computing δ

_κ

⁽ⁱ⁾=δ

_κ

⁽ⁱ⁾⊕

{tilde over (δ

)}_κ

⁽ⁱ⁾, such that the updated vector Δ

_κ

comprises a set of m one-time pads with decreasing levels of backward secrecy.

18. A method for use in an RFID system comprising at least one RFID device and at least one reader which communicates with the RFID device, the method comprising the steps of:

associating a plurality of pseudonyms with the RFID device; and

transmitting from the RFID device different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier is configured to store for a given RFID device T_x a static identifier id_x corresponding to at least one pseudonym of T_x; and

wherein the pseudonyms for T_x are obtained by encrypting id_x ∥

Z_x under a symmetric key K_α

for the verifier, where Z_x, comprises a pseudonym counter.

19. The method of claim 18 wherein when the verifier receives a pseudonym from the RFID device, the verifier decrypts the pseudonym using K_α

to obtain the corresponding static identifier id_x.

24. A method for use in an RFID system comprising at least one RFID device and at least one reader which communicates with the RFID device, the method comprising the steps of:

associating a plurality of pseudonyms with the RFID device; and

transmitting from the RFID device different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the RFID device incorporates a pseudorandom number generator, where ƒ

<sub>κ

x</sub> (i) represents an output of the pseudorandom number generator for index i, where κ

_x is a seed associated with the RFID device;

wherein the RFID device and the verifier attempt to maintain a common counter d_x unique to the RFID device, and share the seed K_x; and

wherein for a given counter value d, the RFID device computes a given one of the pseudonyms as a function of both a base value b and the given counter value d, and the verifier provides a subseciuent instruction to the RFID device to increment the base value b.

25. The method of claim 24 wherein in order to determine which RFID device is associated with a given incoming value α

, the verifier performs a lookup in a list {ƒ

<sub>κ

x</sub> (d_x)} of current α

values for a plurality of RFID devices.

26. The method of claim 24 wherein for the given counter value d, the RFID device computes the given pseudonym as α

_d=ƒ

(bk+d), where ε

denotes a number of pseudonyms associated with the RFID device.

27. An apparatus for use in an RFID system, the apparatus comprising:

an RFID device having a plurality of pseudonyms associated therewith and being operative to communicate with one or more readers of the system;

the RFID device being further operative to transmit different ones of the pseudonyms in response to different reader queries of the RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier authenticates itself to the RFID device by releasing to the RFID device an authentication value β

_i unique to a given pseudonym α

_i transmitted by the RFID device;

wherein the RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ

_i unique to the given pseudonym α

_i transmitted by the RFID device; and

wherein at least one of the values α

_i, β

_i and γ

_i is selected from a corresponding set of such values that is stored in the RFID device and updated using one-time pads transmitted by the verifier to the RFID device over multiple authentication sessions carried out between the verifier and the RFID device.

28. An RFID system comprising:

a plurality of RFID devices; and

a plurality of readers which communicate with at least a subset of the RFID devices;

wherein a plurality of pseudonyms are associated with a given one of the RFID devices, the given RFID device being configurable to transmit different ones of the pseudonyms in response to different reader queries of the given RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier authenticates itself to the given RFID device by releasing to the given RFID device an authentication value β

_i unique to a given pseudonym α

_i transmitted by the given RFID device;

wherein the given RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ

_i unique to the given pseudonym α

_i transmitted by the given RFID device; and

wherein at least one of the values α

_i, β

_i and γ

_i is selected from a corresponding set of such values that is stored in the given RFID device and updated using one- time pads transmitted by the verifier to the given RFID device over multiple authentication sessions carried out between the verifier and the given RFID device.

29. An apparatus for use in an RFID system, the apparatus comprising:

a reader which communicates with one or more RFID devices;

wherein a plurality of pseudonyms are associated with a given one of the RFID devices, the given RFID device transmitting different ones of the pseudonyms in response to different reader queries of the given RFID device;

wherein an authorized verifier is able to determine that the different transmitted pseudonyms are associated with the same RFID device;

wherein the verifier authenticates itself to the given RFID device by releasing to the given RFID device an authentication value β

_i unique to a given pseudonym α

_i transmitted by the given RFID device;

wherein the given RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ

_i unique to the given pseudonym α

_i transmitted by the given RFID device; and

wherein at least one of the values α

_i, β

_i and γ

_i is selected from a corresponding set of such values that is stored in the given RFID device and updated using one-time pads transmitted by the verifier to the given RFID device over multiple authentication sessions carried out between the verifier and the given RFID device.

30. A method for use in a system comprising at least one device and at least one reader which communicates with the device, the method comprising the steps of:

associating a plurality of pseudonyms with the device; and

transmitting from the device different ones of the pseudonyms in response to different reader queries of the device;

wherein the pseudonyms are determined utilizing an updateable set of one or more one-time pads maintained in the device;

wherein the device comprises an RFID device;

wherein a verifier authenticates itself to the RFID device by releasing to the RFID device an authentication value β

_i unique to a given pseudonym α

_i transmitted by the RFID device;

wherein the RFID device authenticates itself to the verifier by releasing to the verifier an authentication value γ

_i unique to the given pseudonym α

_i transmitted by the RFID device; and

wherein at least one of the values α

_i, β

_i and γ

_i is selected from a corresponding set of such values that is stored in the RFID device and updated using one-time pads transmitted by the verifier to the RFID device over multiple authentication sessions carried out between the verifier and the RFID device.