System and method for secure authentication

• US 9,940,463 B2
• Filed: 08/30/2017
• Issued: 04/10/2018
• Est. Priority Date: 12/04/2009
• Status: Active Grant

• Current Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Inventors: Kocher, Paul, Rohatgi, Pankaj, Jaffe, Joshua M.
• Primary Examiner(s): LYNCH, SHARON S
• Application Number:
  US15/691,601
• Publication Number:
  US 20180004957A1
• Time in Patent Office: 223 Days
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 21/556 involving covert channels, i.e. data leakage between processes inhibiting the analysis of circuitry or operation with measures against power attack G06F21/755
• CPC Class Codes: G06F 21/575 Secure boot
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/755 with measures against power attack
• CPC Class Codes: G06F 21/76 in application-specific integrated circuits [ASIC] or field-programmable devices, e.g. field-programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 2212/402 Encrypted data
• CPC Class Codes: G06F 2221/034 Test or assess a computer or a system
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G06F 2221/2125 Just-in-time application of countermeasures, e.g., on-the-fly decryption, just-in-time obfuscation or de-obfuscation
• CPC Class Codes: G06F 2221/2145 Inheriting rights or properties, e.g., propagation of permissions or restrictions within a hierarchy
• CPC Class Codes: G06F 8/71 Version control security arrangements therefor G06F21/57; Configuration management
• CPC Class Codes: G06F 9/44505 Configuring for program initiating, e.g. using registry, configuration files
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2463/061 applying further key derivation, e.g. deriving traffic keys from a pair-wise master key
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0869 for achieving mutual authentication cryptographic mechanisms or cryptographic arrangements for mutual authentication H04L9/3273
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• CPC Class Codes: H04L 9/085 : Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0861 : Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/088 : Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068
• CPC Class Codes: H04L 9/0894 : Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/16 : the keys or algorithms being changed during operation
• CPC Class Codes: H04L 9/3236 : using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 : involving digital signatures
• CPC Class Codes: H04L 9/3271 : using challenge-response
• CPC Class Codes: H04L 9/50 : using hash chains, e.g. blockchains or hash trees

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, wherein the path is based on the message, wherein deriving the validator using the path through the key tree comprises 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 at least a portion of the message and a prior key. The first device then sends the validator to the second device.

Claims

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.