System and method for authenticating RFID tags

• US 8,766,778 B2
• Filed: 04/30/2010
• Issued: 07/01/2014
• Est. Priority Date: 04/30/2009
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Brown, Daniel Richard L.
• Primary Examiner(s): Zimmerman, Brian
• Assistant Examiner(s): NGUYEN, LAURA N
• Application Number:
  US12/771,335
• Publication Number:
  US 20100308978A1
• Time in Patent Office: 1,523 Days
• Field of Search: 340/5.2, 340/10.1, 340/10.42, 340/572.1, 340/531, 455/110, 380/255, 380/277, 380/28, 380/270, 380/282, 380/285, 382/119, 713/168, 713/176, 713/180, 726/9, 726/20
• US Class Current: 340/10.4
• CPC Class Codes: G06F 21/44 Program or device authentication
• CPC Class Codes: G06K 7/10366 the interrogation device being adapted for miscellaneous applications
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3213 using tickets or tokens, e.g. Kerberos network architectures or network communication protocols for entities authentication using tickets in a packet data network H04L63/0807
• CPC Class Codes: H04L 9/3252 using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A system and method of providing authenticity to a radio frequency identification (RFID) tag are provided. The method comprises generating a plurality of digital signatures, wherein each digital signature is generated using an index value unique to that digital signature and using information associated with the RFID tag; and storing the plurality of digital signatures on the RFID tag in association with respective index values to enable a desired digital signature to be selected according to a provided index value. Also provided are a system and method of enabling an RFID reader to authenticate an RFID tag, which utilize a challenge comprising an index value to request one of the stored signature and authenticating same. Also provided is an RFID tag that is configured to participate in the challenge-response protocol.

Claims

1. A method of enabling a radio frequency identification (RFID) tag to be authenticated, the method comprising:

generating a plurality i of digital signatures using a digital signature scheme providing message recovery,

wherein each digital signature comprises a recoverable first signature component generated from a hidden message portion H_i comprising a concatenation of respective index value i unique to that digital signature and a hidden message portion value H, and a second signature component generated from the hidden message portion H_i and a visible message portion V_i; and

,

storing the plurality of digital signatures with the corresponding visible message portions V_i on the RFID tag in association with the respective index values i to enable a desired digital signature and visible message portion V_i to be selected according to a provided index value;

wherein the hidden message portion H_i of the selected digital signature is recoverable from the first signature component.

2. The method according to claim 1, wherein the hidden message portion value H comprises a product identifier (ID), the product ID being associated with a product with which the RFID tag is to be used.

3. The method according to claim 1, wherein the digital signature scheme providing message recovery is the Elliptic Curve Pintsov-Vanstone Signature (EPVS) scheme, wherein the ECPVS scheme encrypts the respective hidden message portion H_i in generating the recoverable first signature component.

4. The method according to claim 1, wherein the respective visible message portions V_i comprise a single common visible message portion V for all of the plurality of digital signatures and corresponding to a single UID for that RFID tag.

5. The method according to claim 1, wherein the digital signature scheme providing message recovery is the Elliptic Curve Digital Signature with Recovery (ECDSR) scheme,

wherein each digital signature further comprises a recoverable third signature component generated from a second hidden message portion H_2i,

wherein the ECDSR scheme encrypts the respective index value i unique to that digital signature and the hidden message portion H_i using a public key of a particular RFID reader to generate the first recoverable signature component, such that only that RFID reader can recover the hidden message portion H_i from the recoverable first signature component, and the ECDSR scheme encrypts the second hidden message portion H_2i using a public key available to all RFID readers to generate the recoverable third signature component, such that all RFID readers can recover the second hidden message portion H_2i.

6. The method according to claim 5, wherein the hidden message portion value H comprises a product ID, the product ID being associated with a product with which the RFID tag is to be used.

7. A non-transitory computer readable storage medium comprising computer executable instructions for enabling an RFID tag to be authenticated, the non-transitory computer readable storage medium comprising instructions for performing the method according to claim 1.

8. A system for enabling an RFID tag to be authenticated, the system comprising a cryptographic processor, a memory, and an interface for establishing a communicable connection to the RFID tag, the memory comprising computer executable instructions for causing the processor to perform the method according to claim 1.

9. A method of authenticating an RFID tag, the method comprising:

randomly selecting an index value from a predefined range of index values;

generating a challenge comprising the selected index value;

providing the challenge to the RFID tag to enable the RFID tag to determine a corresponding digital signature stored thereon in association with the selected index value, wherein each digital signature comprises a recoverable first signature component generated from the hidden message portion H_i comprising a concatenation of a respective index value i unique to that digital signature and a hidden message portion value H, and a second signature component generated from the hidden message portion H_i and a visible message portion V_i;

obtaining a response from the RFID tag, the response comprising the corresponding digital signature; and

authenticating the RFID tag using the corresponding digital signature by verifying the second signature component, and recovering the hidden message portion H_i from the recoverable first signature component and verifying that the hidden message portion H_i has a pre-determined amount of redundancy.

10. A non-transitory computer readable storage medium comprising computer executable instructions for authenticating an RFID tag, the non-transitory computer readable storage medium comprising instructions for performing the method according to claim 9.

11. An RFID reader configured for authenticating a RFID tag, the RFID reader comprising a cryptographic processor, a memory, and an interface for establishing a communicable connection to the RFID tag, the memory comprising computer executable instructions for causing the processor to authenticate the RFID tag by:

randomly selecting an index value from a predefined range of index values;

generating a challenge comprising the selected index value;

providing the challenge to the RFID tag to enable the RFID tag to determine a corresponding digital signature stored thereon in association with the selected index value, wherein each digital signature comprises a recoverable first signature component generated from a hidden message portion H_i comprising a concatenation of a respective index value i unique to that digital signature and a hidden message portion value H, and a second signature component generated from the hidden message portion H_i and a visible message portion V_i;

obtaining a response from the RFID tag, the response comprising the corresponding digital signature; and

authenticating the RFID tag using the corresponding digital signature by verifying the second signature component, and recovering the hidden message portion H_i from the first signature component and verifying that the hidden message portion H_i has a pre-determined amount of redundancy.

12. The RFID reader according to claim 11, wherein the cryptographic processor is configured for performing the Elliptic Curve Pintsov-Vanstone Signature (EPVS) scheme to recover the hidden message portion H_i.

13. The RFID reader according to claim 11, wherein the cryptographic processor is configured for performing the Elliptic Curve Digital Signature with Recovery (ECDSR) scheme to recover the hidden message portion H_i using a public key of the RFID reader.

14. A method of enabling an RFID reader to authenticate an RFID tag, the method comprising:

receiving a challenge from the RFID reader, the challenge comprising challenge index value randomly selected by the RFID reader from a predefined range of index values;

obtaining a requested digital signature from a plurality of digital signatures each being stored on the RFID tag in association with a respective index value, the requested digital signature corresponding to the index value provided by the RFID reader, wherein each digital signature comprises a recoverable first signature component generated from a hidden message portion H_i comprising a concatenation of a respective index value i unique to that digital signature and a hidden message portion value H, and a second signature component generated from the hidden message portion H_i and a visible message portion V_i; and

providing a response to the RFID reader comprising the digital signature corresponding to the received challenge index value to enable the RFID reader to authenticate the RFID tag signature by verifying the second signature component, and recovering the hidden message portion H_i from the recoverable first signature component and verifying that the hidden message portion H_i has a pre-determined amount of redundancy.

15. A non-transitory computer readable storage medium comprising computer executable instructions for enabling an RFID reader to authenticate an RFID tag, the non-transitory computer readable storage medium comprising instructions for performing the method according to claim 14.

16. An RFID tag configured to perform the method according to claim 14.