SYSTEM AND METHOD FOR AUTHENTICATING RFID TAGS

• US 20100308978A1
• Filed: 04/30/2010
• Published: 12/09/2010
• 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.
• Granted Patent: US 8,766,778 B2
• Time in Patent Office: Days
• US Class Current: 340/10.42
• 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 of digital signatures, wherein each digital signature is generated using an index value unique to that digital signature and 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.

2. The method according to claim 1, wherein the information associated with the RFID tag comprises a unique identifier (UID) for that RFID tag.

3. The method according to claim 1, wherein the information associated with the RFID tag comprises a product identifier (ID), the product ID being associated with a product with which the RFID tag is to be used.

4. The method according to claim 1, wherein the plurality of digital signatures are generated using a digital signature scheme providing message recovery, the method further comprising incorporating at least a portion of the information associated with the RFID tag in a recoverable signature component of each digital signature.

5. The method according to claim 4, wherein the information associated with the RFID tag comprises a product ID, the product ID being associated with a product with which the RFID tag is to be used, and wherein the portion of the information associated with the RFID tag incorporated in the recoverable signature component comprises the product ID.

6. The method according to claim 4, further comprising incorporating a respective index value in the recoverable signature component of each digital signature.

7. The method according to claim 4, wherein the digital signature scheme providing message recovery is the Elliptic Curve Pintsov-Vanstone Signature (EPVS) scheme, wherein the ECPVS scheme encrypts a hidden message portion H in generating the recoverable signature component, the hidden message portion H being derived from the portion of the information associated with the RFID tag.

8. The method according to claim 7, wherein the ECPVS scheme includes a visible message portion V, the visible message portion V being common to all of the plurality of signatures and corresponding to a UID for that RFID tag.

9. The method according to claim 4, wherein the digital signature scheme providing message recovery is the Elliptic Curve Digital Signature with Recovery (ECDSR) scheme, wherein the ECDSR scheme encrypts one portion of the information associated with the RFID tag using a public key of a particular RFID reader such that only that RFID reader can recover the one portion to generate a first recoverable signature component, and wherein the ECDSR scheme encrypts another portion of the information associated with the RFID tag using a public key available to all RFID readers to generate a second recoverable signature component.

10. The method according to claim 9, wherein the one portion of information associated with the RFID tag comprises a product ID, the product ID being associated with a product with which the RFID tag is to be used.

11. The method according to claim 1, wherein the plurality of digital signatures are generated using the Elliptic Curve Digital Signature Algorithm (ECDSA) scheme, wherein the ECDSA scheme operates on a message m in generating a pair of signature components (r, s), and wherein the message m comprises the information associated with the RFID tag.

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

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

14. 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 has been generated using a respective index value unique to that digital signature and information associated with the RFID tag;

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

authenticating the RHD tag using the corresponding digital signature.

15. A computer readable storage medium comprising computer executable instructions for authenticating an RFID tag, the computer readable storage medium comprising instructions for performing the method according to claim 14.

16. 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 has been generated using a respective index value unique to that digital signature and information associated with the RFID tag;

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

authenticating the RFID tag using the corresponding digital signature.

17. The RFID reader according to claim 16, wherein the cryptographic processor is configured for performing one or more digital signature schemes providing message recovery to recover at least a portion of the information associated with the RFID tag from a recoverable signature component of the corresponding digital signature.

18. The RFID reader according to claim 17, wherein the cryptographic processor is configured for performing the Elliptic Curve Pintsov-Vanstone Signature (EPVS) scheme to recover a hidden message portion H from a recoverable signature component, the hidden message portion H being derived from the portion of the information associated with the RFID tag.

19. The RFID reader according to claim 17, wherein the cryptographic processor is configured for performing the Elliptic Curve Digital Signature with Recovery (ECDSR) scheme to recover one portion of the information associated with the RFID tag using a public key of the RFID reader.

20. The RFID reader according to claim 16, wherein the cryptographic processor is configured for performing the Elliptic Curve Digital Signature Algorithm (ECDSA) scheme, wherein the ECDSA scheme operates on a message m and a pair of signature components (r, s), and wherein the cryptographic processor is further configured for obtaining the information associated with the RFID tag from the message m.

21. 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 an 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 has been generated using a respective index value unique to that digital signature and information associated with the RFID tag; and

providing a response to the RFID reader to enable the RFID reader to authenticate the RFID tag, wherein the response comprises the requested digital signature.

22. A computer readable storage medium comprising computer executable instructions for enabling an RFID reader to authenticate an RFID tag, the computer readable storage medium comprising instructions for performing the method according to claim 21.

23. An RFID tag configured to perform the method according to claim 21.