System and method for authenticating RFID tags

• US 9,734,322 B2
• Filed: 06/30/2014
• Issued: 08/15/2017
• 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): NGUYEN, LAURA N
• Application Number:
  US14/319,545
• Publication Number:
  US 20150002260A1
• Time in Patent Office: 1,142 Days
• 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 for authenticating a radio frequency identification (RFID) tag, the method comprising:

sending a challenge comprising an index value i to the RFID tag, the index value i in a set of index values, wherein each index value in the set of index values is associated with a single signature, and wherein an i^th signature corresponding to the index value i comprises an i^th set of signature components;

receiving, in response to the challenge, at least, the corresponding i^th set of signature components, wherein each of said i^th set of signature components having been generated from a message m_i comprising at least a hidden portion H_i and a corresponding visible portion V_i and stored on the RFID tag;

obtaining the corresponding visible portion V_i and a public key W corresponding to the i^th set of signature components; and

,

verifying the corresponding i^th set of signature components using the corresponding visible portion V_i and the public key W;

wherein the RFID tag is authenticated if the corresponding i^th set of signature components is verified, and

wherein the hidden portion H_i is recoverable from the corresponding i^th set of signature components,

wherein each of the i^th set of signature components stored on the RFID tag remain available for subsequent challenges.

2. The method of claim 1, wherein before authenticating the RFID tag the method further comprises:

recovering a representation H_i′

of the hidden portion H_i from a signature component c_i of the i^th set of signature components; and

,

verifying the i^th set of signature components if a specified characteristic is successfully recovered from the representation H_i′

.

3. The method of claim 2, wherein the specified characteristic comprises identifying an expected value in the representation H_i′

.

4. The method of claim 2, wherein the specified characteristic comprises confirming an expected redundancy in the representation H_i′

.

5. The method of claim 1, wherein the corresponding visible portion V_i is obtained from the RFID tag.

6. The method of claim 1, wherein the public key W is obtained by recovering the public key W from the RFID tag.

7. The method of claim 1, wherein the public key W is obtained from a signing station that generated the corresponding i^th set of signature components.

8. The method according to claim 1, wherein the hidden portion H_i comprises a product identifier for identifying a product associated with the RFID tag.

9. The method according to claim 1, wherein the visible portion V_i is the same for all i sets of signature components.

10. The method according to claim 1, wherein the i sets of signature components were generated using an Elliptic Curve Pintsov-Vanstone Signature (ECPVS) scheme.

11. The method according to claim 1, wherein the i sets of signature components each comprise a pair of signature components (c_i, s_i).

12. The method according to claim 1, wherein the i sets of signature components each comprise three signature components (c1_i, c2_i, s_i), and wherein the i sets of signature components were generated using an Elliptic Curve Digital Signature with Recovery (ECDSR) scheme and a public key for at least one of the three signature components, and wherein a first signature component c1_i was generated from a first separated hidden portion H1_i, and a second signature component c2_i was generated from a second separated hidden portion H2_i, the first separated hidden portion H1_i and the second separated hidden portion H2_i having been separated from the hidden portion H_i, the method further comprising:

recovering information from the at least one of the three signature components using the public key.

13. The method according to claim 12, wherein the first signature component c1_i is a single value for all i sets of signature components.

14. A non-transitory computer readable storage medium comprising computer executable instructions for execution by an RFID reader to authenticate a radio frequency identification (RFID) tag, the instructions comprising:

instructions to send a challenge comprising an index value i to the RFID tag, the index value i in a set of index values, wherein each index value in the set of index values is associated with a single signature, and wherein an i^th signature corresponding to the index value i comprises an i^th set of signature components;

instructions to receive, in response to the challenge, at least, the corresponding i^th set of signature components, wherein each of said i^th set of signature components having been generated from a message m_i comprising at least a hidden portion H_i and a corresponding visible portion V_i and stored on the RFID tag;

instructions to obtain the corresponding visible portion V_i and a public key W corresponding to the i^th set of signature components; and

,

instructions to verify the corresponding i^th set of signature components using the corresponding visible portion V_i and the public key W;

wherein the RFID tag is authenticated if the corresponding i^th set of signature components is verified, and wherein the hidden portion H_i is recoverable from the corresponding i^th set of signature components,

wherein each of the i^th set of signature components stored on the RFID tag remain available for subsequent challenges.

15. A computing device operative to authenticate an RFID tag, the computing device comprising a 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:

send a challenge comprising an index value i to the RFID tag, the index value i in a set of index values, wherein each index value in the set of index values is associated with a single signature, and wherein an i^th signature corresponding to the index value i comprises an i^th set of signature components;

receive, in response to the challenge, at least, the corresponding i^th set of signature components, wherein each of said i^th set of signature components having been generated from a message m_i comprising at least a hidden portion H_i and a corresponding visible portion V_i and stored on the RFID tag;

obtain the corresponding visible portion V_i and a public key W corresponding to the i^th set of signature components; and

,

verify the corresponding i^th set of signature components using the corresponding visible portion V_i and the public key W;

wherein the RFID tag is authenticated if the corresponding i^th set of signature components is verified, and wherein the hidden portion H_i is recoverable from the corresponding i^th set of signature components,

wherein each of the i^th set of signature components stored on the RFID tag remain available for subsequent challenges.

16. An RFID reader configured to authenticate a RFID tag, the RFID reader operative to:

send a challenge comprising an index value i to the RFID tag, the index value i in a set of index values, wherein each index value in the set of index values is associated with a single signature, and wherein an i^th signature corresponding to the index value i comprises an i^th set of signature components;

receive, in response to the challenge, at least, the corresponding i^th set of signature components, wherein each of said i^th set of signature components having been generated from a message m_i comprising at least a hidden portion H_i and a corresponding visible portion V_i and stored on the RFID tag;

obtain the corresponding visible portion V_i and a public key W corresponding to the i^th set of signature components; and

,

verify the corresponding i^th set of signature components using the corresponding visible portion V_i and the public key W;

wherein the RFID reader is operative to authenticate the RFID tag if the corresponding i^th set of signature components is verified,

wherein each of the i^th set of signature components stored on the RFID tag remain available for subsequent challenges.

17. The RFID reader of claim 16, wherein before authenticating the RFID tag the RFID reader is further operative to:

recover a representation H_i′

of the hidden portion H_i from a signature component c_i of the i^th set of signature components; and

,

verify the i^th set of signature components if a specified characteristic is successfully recovered from the representation H_i′

.

18. The RFID reader according to claim 16, wherein the i sets of signature components were generated using an Elliptic Curve Pintsov-Vanstone Signature (ECPVS) scheme.

19. The RFID reader according to claim 16, wherein the i sets of signature components each comprise a pair of signature components (c_i, s_i).

20. The RFID reader according to claim 16, wherein the i sets of signature components each comprise three signature components (c1_i, c2_i, s_i), and wherein the i sets of signature components were generated using an Elliptic Curve Digital Signature with Recovery (ECDSR) scheme and a public key for at least one of the three signature components, and wherein a first signature component c1_i was generated from a first separated hidden portion H1_i, and a second signature component c2_i was generated from a second separated hidden portion H2_i, the first separated hidden portion H1_i and the second separated hidden portion H2_i having been separated from the hidden portion H_i, the RFID reader further operative to:

recover information from the at least one of the three signature components using the public key.

21. A method of enabling an RFID tag to be authenticated, the method comprising:

receiving a challenge comprising an index value i, the index value i in a set of index values, wherein each index value in the set of index values is associated with a single signature, and wherein an i^th signature corresponding to the index value i comprises an i^th set of signature components;

obtaining the corresponding i^th set of signature components from i sets of signature components stored on the RFID tag, wherein each of said i^th set of signature components having been generated from a message m_i comprising at least a hidden portion H_i that includes the index value i unique to the corresponding i^th set of signature components, and a corresponding visible portion V_i′

; and

,

providing the corresponding i^th set of signature components in response to the challenge;

wherein a challenger may authenticate the RFID tag by obtaining the corresponding visible portion V_i and a public key W corresponding to the i^th set of signature components, and authenticating the RFID tag when the corresponding i^th set of signature components has been verified using the corresponding visible portion V_i and the public key W,

wherein each of the i sets of signature components stored on the RFID tag remain available for subsequent challenges.

22. The method according to claim 21, wherein the i sets of signature components each comprise three signature components (c1_i, c2_i, s_i), and wherein the i sets of signature components were generated using an Elliptic Curve Digital Signature with Recovery (ECDSR) scheme and a public key for at least one of the three signature components, and wherein a first signature component c1_i was generated from a first separated hidden portion H1_i, and a second signature component c2_i was generated from a second separated hidden portion H2_i, the first separated hidden portion H1_i and the second separated hidden portion H2_i having been separated from the hidden portion H_i, wherein the challenger may further recover private information from the at least one of the three signature components using the public key.

23. An RFID tag configured to:

receive a challenge comprising an index value i, the index value i in a set of index values, wherein each index value in the set of index values is associated with a single signature, and wherein an i^th signature corresponding to the index value i comprises an i^th set of signature components;

obtain the corresponding i^th set of signature components from i sets of signature components stored on the RFID tag, wherein each of said i^th set of signature components having been generated from a message m_i comprising at least a hidden portion H_i that includes the index value i unique to the corresponding i^th set of signature components, and a corresponding visible portion V_i′

; and

,

provide the corresponding i^th set of signature components in response to the challenge;

wherein a challenger may authenticate the RFID tag by obtaining the corresponding visible portion V_i and a public key W corresponding to the i^th set of signature components, and authenticating the RFID tag when the corresponding i^th set of signature components has been verified using the corresponding visible portion V_i and the public key W,

wherein each of the i sets of signature components stored on the RFID tag remain available for subsequent challenges.

24. A method of manufacturing an RFID tag that may be authenticated, the method comprising:

generating a plurality of i sets of signature components, each of the i sets of signature components generated from a message m_i comprising at least a hidden portion H_i and a corresponding visible portion V_i, wherein at least the hidden portion H_i is recoverable from at least one of the signature components; and

,

storing each of the plurality of i sets of signature components on the RFID tag in association with a respective index value i, the index value i in a set of index values, wherein each index value i in the set of index values is associated with a single signature, and wherein an i^th signature corresponding to the index value i comprises an i^th set of signature components, and wherein each of the i sets signature components stored on the RFID tag remain available to be chosen by each of a plurality of challenges.