RFID tags with dynamic key replacement

• US 10,084,597 B1
• Filed: 01/12/2018
• Issued: 09/25/2018
• Est. Priority Date: 07/02/2013
• Status: Active Grant

• Current Assignee: Impinj, Inc.
• Original Assignee: Impinj, Inc.
• Inventors: Robshaw, Matthew, Pesavento, Alberto, Diorio, Christopher
• Primary Examiner(s): Pham, Luu
• Assistant Examiner(s): Wilcox, James J
• Application Number:
  US15/870,698
• Time in Patent Office: 256 Days
• CPC Class Codes: G06K 19/073 Special arrangements for circuits, e.g. for protecting identification code in memory protection against unauthorised use of computer memory G06F12/14
• CPC Class Codes: G06K 7/10257 arrangements for protecting the interrogation against piracy attacks computer security in general G06F21/00; jamming of communication, countermeasures H04K3/00; secret communication H04K1/00
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0877 using additional device, e.g. trusted platform module [TPM], smartcard, USB or hardware security module [HSM]
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3271 using challenge-response
• CPC Class Codes: H04W 12/041 Key generation or derivation
• CPC Class Codes: H04W 12/0471 Key exchange
• CPC Class Codes: H04W 12/069 using certificates or pre-shared keys

Abstract

A cryptographically-enabled RFID tag stores a primary secret key and derives secondary keys from the primary key. A secondary key may be derived by combining the primary key with one or more other parameters using one or more algorithms. The tag uses a derived secondary key to encrypt or electronically sign a tag response sent to a verifying entity. The verifying entity does not know the derived secondary key, but knows the tag primary key and the parameters and algorithms used to derive the secondary key and can derive all of the potential secondary keys. The verifying entity can then attempt to authenticate the tag or tag response by trying potential secondary keys.

Claims

1. A method to wirelessly authenticate an item, the method comprising:

transmitting a message to a Radio Frequency Identification (RFID) integrated circuit (IC) associated with the item;

receiving, from the RFID IC, an identifier and a cryptographic response to the message;

determining, based on the identifier, a plurality of potential keys including a used key and at least one unused key;

generating a plurality of processed cryptographic responses, each processed cryptographic response based on the received cryptographic response and a respective potential key in the plurality of potential keys;

extracting verification values from the plurality of processed cryptographic responses;

in response to extracting at least one verification value, determining whether the at least one verification value one of corresponds to and is sufficiently close to a known value; and

in response to determining that the at least one verification value one of corresponds to and is sufficiently close to the known value, considering the item authentic, otherwise considering the item suspect.

2. The method of claim 1, further comprising:

in response to failing to extract at least one verification value, considering the item suspect.

3. The method of claim 1, further comprising determining the known value from a counter stored by a verifying entity.

4. The method of claim 1, further comprising determining the plurality of potential keys based on at least one of a seed value, a counter value, a random value, a generation algorithm, a parameter length, a parameter range, and at least two parameters.

5. The method of claim 1, wherein:

determining the plurality of potential keys comprises;

determining a primary key associated with the RFID IC based on the received identifier;

determining a plurality of potential parameter values associated with the received cryptographic response; and

determining each potential key in the plurality of potential keys based on the primary key and a respective potential parameter value;

the plurality of potential parameter values includes an actual parameter value and at least one other potential parameter value, and

the actual parameter value is at least one of;

used to generate the used key, and

included in the cryptographic response.

6. The method of claim 1, wherein considering the item suspect includes at least one of:

considering the item not authentic; and

considering the RFID IC as having been previously attacked.

7. A cryptographic device configured to wirelessly authenticate an item, the cryptographic device comprising:

a key-generation device configured to determine, based on an identifier received from a Radio Frequency Identification (RFID) integrated circuit (IC) associated with the item, a plurality of potential keys including a used key and at least one unused key; and

a processor configured to;

transmit a message to the RFID IC;

receive, from the RFID IC, the identifier and a cryptographic response to the message;

generate a plurality of processed cryptographic responses, each processed cryptographic response based on the received cryptographic response and a respective potential key in the plurality of potential keys;

extract verification values from the plurality of processed cryptographic responses;

in response to extracting at least one verification value, determine whether the at least one verification value one of corresponds to and is sufficiently close to a known value; and

in response to determining that the at least one verification value one of corresponds to and is sufficiently close to the known value, consider the item authentic, otherwise consider the item suspect.

8. The cryptographic device of claim 7, wherein the processor is further configured to, in response to failing to extract verification values, consider the item suspect.

9. The cryptographic device of claim 7, wherein the processor is further configured to determine the known value from a counter stored by a verifying entity.

10. The cryptographic device of claim 7, wherein the key-generation device is further configured to determine the plurality of potential keys based on at least one of a seed value, a counter value, a random value, a generation algorithm, a parameter length, and a parameter space.

11. The cryptographic device of claim 7, wherein:

the key-generation device is further configured to;

determine a primary key associated with the RFID IC based on the received identifier;

determine a plurality of potential parameter values associated with the received cryptographic response; and

determine each potential key in the plurality of potential keys based on the primary key and a respective potential parameter value, wherein

the plurality of potential parameter values includes an actual parameter value and at least one other parameter value, and

the actual parameter value is at least one of

used to generate the used key, and

included in the cryptographic response.

12. The cryptographic device of claim 7, wherein the cryptographic device is disposed within at least one of an RFID reader, a computer coupled to the RFID reader, a server coupled to the RFID reader, and an RFID IC.

13. The cryptographic device of claim 7, wherein the processing device is configured to consider the item suspect by at least one of:

considering the item not authentic; and

considering the RFID IC as having been previously attacked.

14. A Radio Frequency Identification (RFID) system configured to wirelessly authenticate an item, the system comprising:

an RFID reader configured to communicate with an RFID integrated circuit (IC) associated with the item;

a key-generation device configured to determine, based on an identifier received from the RFID IC, a plurality of potential keys including a used key and at least one unused key; and

a processor configured to;

cause the RFID reader to transmit a message to the RFID IC;

receive, from the RFID IC and via the RFID reader, the identifier and a cryptographic response;

generate a plurality of processed cryptographic responses, each processed cryptographic response based on the received cryptographic response and a respective potential key in the plurality of potential keys;

extract at least one verification value from the plurality of processed cryptographic responses;

in response to extracting the at least one verification value, determine whether the at least one verification value one of corresponds to and is sufficiently close to a known value; and

in response to determining that the at least one verification value one of corresponds to and is sufficiently close to the known value, consider the item authentic, otherwise consider the item suspect.

15. The RFID system of claim 14, wherein the plurality of processed cryptographic responses are determined from at least one of a seed value, a counter value, and an IC-generated random value.

16. The RFID system of claim 15, wherein

the processor is configured to determine the known value from a counter stored by a verifying entity.

17. The RFID system of claim 14, wherein the processor is further configured to:

determine a primary key based on the received identifier;

determine a plurality of potential IC parameter values; and

determine each potential key in the plurality of potential keys based on the primary key and a respective potential IC parameter value.

18. The RFID system of claim 14, wherein the processor is configured to consider the item suspect by at least one of:

considering the item not authentic; and

considering the RFID IC as having been previously attacked.

19. The RFID system of claim 14, wherein at least one of the key-generation device and the processor is integrated with the RFID reader.