System and method for authenticating RFID tags
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.
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.