Apparatus with anticounterfeiting measures

Patent metadata

Field	Value
Publication number	US-11074349-B2
Application number	US-201916240671-A
Country	US
Kind code	B2
Filing date	Jan 4, 2019
Priority date	Dec 4, 2009
Publication date	Jul 27, 2021
Grant date	Jul 27, 2021

Abstract

A method for device authentication comprises receiving, by processing hardware of a first device, a message from a second device to authenticate the first device. The processing hardware retrieves a secret value from secure storage hardware operatively coupled to the processing hardware. The processing hardware derives a validator from the secret value using a path through a key tree. The first device then sends the validator to the second device.

First claim

What is claimed is:

1. A method for device authentication comprising:
receiving, by processing hardware of a first device, a message from a second device as part of a challenge-response protocol;
retrieving, by the processing hardware, a secret value from secure storage hardware operatively coupled to the processing hardware;
determining a path through a key tree based at least in part on the message, wherein the key tree comprises a node and a plurality of branches connected to the node, wherein the node is associated with a key and each of the plurality of branches are associated with an entropy redistribution operation that when applied to the key generates an associated derived key;
deriving, by the processing hardware, a validator at least in part from the secret value using a sequence of entropy redistribution operations associated with the path through the key tree; and
exchanging the validator between the first device and the second device as part of the challenge-response protocol in order to authenticate the first device.

2. A method as in claim 1 , wherein the first device comprises a printer cartridge and the second device comprises a printer.

3. A method as in claim 1 , wherein the message comprises a message identifier, and wherein the path is determined based at least in part on the message identifier.

4. A method as in claim 3 , wherein the path comprises a plurality of portions, the method further comprising:
decomposing the message identifier into a plurality of parts; and
determining each portion of the plurality of portions of the path using one of the plurality of parts of the message identifier.

5. A method as in claim 4 , wherein each portion of the plurality of portions of the path is associated with a distinct entropy redistribution operation.

6. A method as in claim 4 , further comprising:
performing the following for a first portion of the path;
determining a first value of a first part of the plurality of parts;
determining a first entropy redistribution operation based at least in part on the first value;
applying the first entropy redistribution operation on the secret value to compute an intermediate key;

for one or more additional portion of the path, performing the following comprising:
determining a value of an additional part of the plurality of parts;
determining an additional entropy redistribution operation based at least in part on the value of the additional part; and
applying the additional entropy redistribution operation on a previously computed intermediate key to compute a next intermediate key; and

for a final portion of the path, performing the following comprising:
determining a value of another additional part of the plurality of parts;
determining another additional entropy redistribution operation based at least in part on the value of the other additional part; and
applying the other additional entropy redistribution operation on a previously computed intermediate key to compute the validator.

7. A method as in claim 1 , further comprising
generating an expected response by the second device;
comparing, at the second device, the validator to the expected response;
determining, by the second device, whether the validator matches the expected response; and
verifying at the second device that the first device is authentic responsive to the validator matching the expected response.

8. A method as in claim 7 , wherein the expected response comprises an expected validator, the method further comprising:
deriving the expected validator from an additional secret value at the second device using the path through the key tree.

9. A method as in claim 7 , the method further comprising:
deriving, at the second device, a second validator using the path through the key tree;
sending the second validator to the first device; and
determining whether the second validator matches an expected value; and
verifying at the first device that the second device is authentic responsive to determining that the second validator matches the expected value.

10. A device, comprising:
secure storage hardware to store a secret value; and
processing hardware operatively coupled to the secure storage hardware, wherein the processing hardware is to:
receive a message from a second device as part of a challenge-response protocol;
retrieve the secret value from the secure storage hardware;
determine a path through a key tree based at least in part on the message, wherein the key tree comprises a node and a plurality of branches connected to the node, wherein the node is associated with a key and each of the plurality of branches are associated with an entropy redistribution operation that when applied to the key generates an associated derived key;
derive a validator at least in part from the secret value using a sequence of entropy redistribution operations associated with the path through the key tree; and
provide the validator to the second device as part of the challenge-response protocol in order to authenticate the device to the second device.

11. The device of claim 10 , wherein the device comprises a printer cartridge and the second device comprises a printer.

12. The device of claim 10 , wherein the message comprises a message identifier, and wherein the path is determined based at least in part on the message identifier.

13. The device of claim 12 , wherein the path comprises a plurality of portions, and where the processing hardware is further to:
decompose the message identifier into a plurality of parts; and
determine each portion of the plurality of portions of the path using one of the plurality of parts of the message identifier.

14. The device of claim 13 , wherein each portion of the plurality of portions of the path is associated with a distinct entropy redistribution operation.

15. The device of claim 13 , wherein the processing hardware is further to:
perform the following for a first portion of the path;
determine a first value of a first part of the plurality of parts;
determine a first entropy redistribution operation based at least in part on the first value;
apply the first entropy redistribution operation on the secret value to compute an intermediate key;

for one or more additional portion of the path, perform the following comprising:
determine a value of an additional part of the plurality of parts;
determine an additional entropy redistribution operation based at least in part on the value of the additional part; and
apply the additional entropy redistribution operation on a previously computed intermediate key to compute a next intermediate key; and

for a final portion of the path, perform the following comprising:
determine a value of another additional part of the plurality of parts;
determine another additional entropy redistribution operation based at least in part on the value of the other additional part; and
apply the other additional entropy redistribution operation on a previously computed intermediate key to compute the validator.

16. A system comprising:
a first device comprising secure storage hardware and processing hardware operatively coupled to the secure storage hardware, wherein the secure storage hardware is to store a secret value and the processing hardware is to:
receive a message from a second device as part of a challenge-response protocol;
retrieve the secret value from the secure storage hardware;
determine a path through a key tree based at least in part on the message, wherein the key tree comprises a node and a plurality of branches con

Assignees

• Cryptography Res Inc

Inventors

• Kocher Paul C
• Rohatgi Pankaj
• Jaffe Joshua M

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• G06F2221/2125

  Just-in-time application of countermeasures, e.g., on-the-fly decryption, just-in-time obfuscation or de-obfuscation · CPC title

• H04L2463/061

  applying further key derivation, e.g. deriving traffic keys from a pair-wise master key · CPC title

• H04L9/003

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title

• H04L9/3236

  using cryptographic hash functions · CPC title