System and method for secure authentication

1. A method for device authentication comprising:

receiving, by processing hardware of a first device, a message from a second device to authenticate the first device;

retrieving, by the processing hardware, a secret value from secure storage hardware operatively coupled to the processing hardware;

deriving, by the processing hardware, a validator from the secret value using a path through a key tree, wherein the path identifies a plurality of entropy distribution operations and is based on dividing the message into a plurality of parts, wherein the key tree avoids leakage of the secret value at least in part by computing a plurality of successive intermediate keys starting with a value based on the secret value and leading to the validator, wherein each successive intermediate key is derived based on a different part of the plurality of parts of the message and a prior key; and

exchanging the validator between the first device and the second device as part of a 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 a first part of the plurality of parts determines a first leg of the path through the key tree and a second part of the plurality of parts determines a second leg of the path through the key tree, and wherein the first leg of the path is associated with a first entropy distribution operation and the second leg of the path is associated with a second entropy distribution operation.

4. A method as in claim 1 , further comprising

comparing, at the second device, the validator to an expected response generated by the second device; and

verifying at the second device that the first device is authentic when the validator matches the expected response.

5. A method as in claim 4 , 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, wherein the path is based on the message.

6. A method as in claim 4 , 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

verifying at the first device that the second device is authentic when the second validator matches an expected value.

7. 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 to authenticate the first device;

retrieve the secret value from the secure storage hardware;

derive a validator from the secret value using a path through a key tree, wherein the path identifies a plurality of entropy distribution operations and is based on dividing the message into a plurality of parts, wherein the key tree avoids leakage of the secret value at least in part by, computing a plurality of successive intermediate keys starting with a value based on the secret value and leading to the validator, wherein each successive intermediate key is derived based on a different part of the plurality of parts of the message and a prior key; and

exchange the validator between the first device and the second device as part of a challenge-response protocol in order to authenticate the first device.

8. The system of claim 7 , further comprising the second device, wherein the second device is to:

generate an expected response;

compare the validator to the expected response;

determine whether the validator matches the expected response; and

verify that the first device is authentic responsive to determining that the validator matches the expected response.

9. The system of claim 8 , wherein the expected response comprises an expected validator, and wherein the second device is to:

derive the expected validator from an additional secret value at the second device using the path through the key tree.

10. The system of claim 7 , wherein the first device comprises a printer cartridge and the second device comprises a printer.

11. The system of claim 7 , wherein a first part of the plurality of parts determines a first leg of the path through the key tree and a second part of the plurality of parts determines a second leg of the path through the key tree, and wherein the first leg of the path is associated with a first entropy distribution operation and the second leg of the path is associated with a second entropy distribution operation.

12. A system comprising:

a first device comprising processing hardware, wherein the processing hardware is to:

send a message to a second device as part of a challenge-response protocol in order to authenticate the first device;

receive a response from the second device as part of the challenge-response protocol, the response comprising a first validator;

derive a second validator from a secret value using a path through a key tree, wherein the path identifies a plurality of entropy distribution operations and is based on dividing the message into a plurality of parts, wherein the key tree avoids leakage of the secret value at least in part by, computing a plurality of successive intermediate keys starting with a value based on the secret value and leading to the validator, wherein each successive intermediate key is derived based on a different part of the plurality of parts of the message and a prior key;

compare the first validator to the second validator;

determine whether the first validator matches the second validator; and

verify that the second device is authentic responsive to determining that the first validator matches the second validator.

13. The system of claim 12 , wherein a first part of the plurality of parts determines a first leg of the path through the key tree and a second part of the plurality of parts determines a second leg of the path through the key tree, and wherein the first leg of the path is associated with a first entropy distribution operation and the second leg of the path is associated with a second entropy distribution operation.

14. The system of claim 12 , wherein the first device comprises a printer and the second device comprises a printer cartridge.