Cryptographic device with resistance to differential power analysis and other external monitoring attacks

• US 8,707,052 B2
• Filed: 02/08/2013
• Issued: 04/22/2014
• 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 C., Rohatgi, Pankaj, Jaffe, Joshua M.
• Primary Examiner(s): Song, Hosuk
• Application Number:
  US13/762,703
• Publication Number:
  US 20130173928A1
• Time in Patent Office: 438 Days
• Field of Search: 380/277, 380/44, 713/181, 713/189, 713192-194, 726 26- 27
• US Class Current: 713/189
• 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

Techniques usable by devices to encrypt and decrypt sensitive data to in a manner that provides security from external monitoring attacks. The encrypting device has access to a base secret cryptographic value (key) that is also known to the decrypting device. The sensitive data are decomposed into segments, and each segment is encrypted with a separate encryption key derived from the base key and a message identifier to create a set of encrypted segments. The encrypting device uses the base secret cryptographic value to create validators that prove that the encrypted segments for this message identifier were created by a device with access to the base key. The decrypting device, upon receiving an encrypted segments and validator(s), uses the validator to verify the message identifier and that the encrypted segment are unmodified, then uses a cryptographic key derived from the base key and message identifier to decrypt the segments.

Claims

1. A device comprising:

storage hardware to store a secret value; and

processing hardware, coupled to the storage hardware, to;

derive a message key for a message based at least in part on the secret value and a message identifier of the message, wherein the message key is derived using a plurality of entropy distribution operations;

encrypt a data segment of the message using an encryption key derived from the message key to produce an encrypted data segment;

compute a validator based on the secret value and the encrypted data segment; and

output the encrypted data segment and the validator.

2. The device of claim 1, wherein the processing hardware is further to:

derive the message key using a path through a key tree, wherein the path through the key tree is based on the message identifier and identifies the plurality of entropy distribution operations.

3. The device of claim 2, wherein the processing hardware is further to:

divide the message identifier into a plurality of parts, wherein each of the plurality of parts determines a leg of the path, and wherein each leg of the path is associated with a particular entropy distribution operation of the plurality of entropy distribution operations.

4. The device of claim 3, wherein the processing hardware is further to:

compute a plurality of intermediate keys in succession, wherein each of the plurality of intermediate keys is computed based on applying one of the plurality of entropy distribution operations to at least one of the secret value or a previous intermediate key in the succession.

5. The device of claim 1, wherein the processing hardware is further to encrypt a plurality of data segments of the message using hash chaining operations comprising:

encrypting a first data segment of the plurality of data segments with a first encryption key derived from the message key to create a first encrypted data segment;

hashing the first encrypted data segment to create a first hash segment;

combining the first hash segment with a second data segment of the plurality of data segments to create a first combined data segment; and

encrypting the first combined data segment with a second encryption key derived from the message key.

6. The device of claim 1, where the processing hardware is further to encrypt a plurality of data segments of the message using hash chaining operations comprising:

constructing a first plaintext segment comprising at least a first data segment of the plurality of data segments;

hashing the first plaintext segment to create a first plaintext hash segment;

constructing a second plaintext segment comprising the first plaintext hash segment and a second data segment of the plurality of data segments;

encrypting the first plaintext segment with a first encryption key derived from the message key; and

encrypting the second plaintext segment with a second encryption key derived from the message key.

7. The device of claim 1, where the processing hardware is further to:

divide the message into a plurality of data segments;

derive a plurality of encryption keys in succession using a plurality of cryptographic operations, each encryption key corresponding to at least one of the plurality of data segments and being derived by applying a cryptographic operation of the plurality of cryptographic operations to a previous encryption key in the succession; and

encrypting the plurality of data segments using corresponding ones of the plurality of encryption keys.

8. The device of claim 1, the processing hardware further to:

divide the message into a plurality of data segments;

encrypt each of the plurality of data segments with a different encryption key of a plurality of encryption keys to create a plurality of encrypted data segments; and

compute a plurality of validators, each of the plurality of validators corresponding to one of the encrypted data segments.

9. The device of claim 1, the processing hardware further to:

generate a nonce for the message; and

derive the message identifier based on the nonce.

10. The device of claim 1, wherein to compute the validator the processing hardware:

computes a hash of the encrypted data segment; and

performs an additional plurality of entropy distribution operations on the message key using a key tree, wherein the hash indicates a path through the key tree, the path identifying the additional plurality of entropy distribution operations.

11. The device of claim 1, wherein the processing hardware is further to:

provide the data segment and the validator to a remote device to perform mutual authentication between the device and the remote device.

12. The device of claim 1, where the processing hardware is further to encrypt the data segment using an intra-segment key change that comprises:

dividing the data segment into a plurality of data sub-segments;

transforming a first encryption key into a plurality of encryption sub-keys using a plurality of cryptographic operations, each encryption sub-key corresponding to at least one of the data sub-segments;

encrypting a first data sub-segment with a first corresponding encryption sub-key; and

encrypting a second data sub-segment with a second corresponding encryption sub-key.

13. A device comprising:

storage hardware to store a secret value; and

processing hardware, coupled to the storage hardware, to;

receive an encrypted data segment and a validator;

obtain a message identifier corresponding to the encrypted data segment;

derive a message key using the secret value and the message identifier, where the message key is derived using a plurality of entropy distribution operations;

verify, using the received validator, that the encrypted data segment has not been modified; and

decrypt the encrypted data segment using a decryption key derived from the message key to produce a decrypted data segment responsive to verifying that the encrypted data segment has not been modified.

14. The device of claim 13, where the processing hardware is further to:

derive the message key using a path through a key tree, wherein the path through the key tree is based on the message identifier and identifies the plurality of entropy distribution operations.

15. The device of claim 14, wherein the processing hardware is further to:

divide the message identifier into a plurality of parts, where each of the plurality of parts determines a leg of the path, and where each leg of the path is associated with a particular entropy distribution operation of the plurality of entropy distribution operations.

16. The device of claim 15, wherein the processing hardware is further to:

compute a plurality of intermediate keys in succession, wherein each of the plurality of intermediate keys is computed based on applying one of a plurality of entropy distribution operations to at least one of the secret value or a previous intermediate key in the succession.

17. The device of claim 13, wherein the processing hardware is further to receive and decrypt a plurality of encrypted data segments using hash chaining operations comprising:

cryptographically transforming a first encrypted data segment of the plurality of encrypted data segments to produce a first derived value;

comparing the first derived value with a first expected value;

responsive to determining that the first derived value matches the first expected value, decrypting the first derived value using a first decryption key derived from the message key to produce a first decrypted data segment and a second derived value;

comparing the second derived value with a second expected value; and

responsive to determining that the second derived value matches the second expected value, decrypting the second derived value using a second decryption key derived from the message key to produce a second decrypted data segment.

18. The device of claim 13, wherein to verify that the encrypted data segment has not been modified the processing hardware:

computes a hash of the encrypted data segment;

generates an expected validator based on performing an additional plurality of entropy distribution operations on the message key using a key tree, wherein the hash indicates a path through the key tree, the path identifying the additional plurality of entropy distribution operations; and

compares the expected validator to the received validator.

19. The device of claim 13, wherein the processing hardware is further to receive and decrypt a plurality of encrypted data segments using hash chaining operations comprising:

decrypting a first encrypted data segment of the plurality of encrypted segments to produce a first plaintext segment comprising a first decrypted data segment and a first hash value;

validating the first hash value; and

responsive to validating the first hash value, decrypting a second encrypted data segment to produce a second plaintext segment comprising a second decrypted data segment and a second hash value.

20. The device of claim 13, wherein the processing hardware is further to decrypt the encrypted data segment using an intra-segment key change that comprises:

dividing the encrypted data segment into a plurality of encrypted data sub-segments;

transforming the decryption key into a plurality of decryption sub-keys using a plurality of cryptographic operations, each decryption sub-key corresponding to at least one of the plurality of encrypted data sub-segments;

decrypting a first encrypted data sub-segment of the plurality of encrypted data sub-segments with a first corresponding decryption sub-key of the plurality of decryption sub-keys; and

decrypting a second encrypted data sub-segment of the plurality of encrypted data sub-segments with a second corresponding decryption sub-key of the plurality of decryption sub-keys.

21. A method comprising:

receiving a message by processing hardware;

deriving, by the processing hardware, a message key for the message based at least in part on a stored secret value and a message identifier of the message, where the message key is derived using a plurality of entropy distribution operations;

encrypting, by the processing hardware, a data segment of the message using an encryption key derived from the message key to produce an encrypted data segment;

computing a validator based on the secret value and the encrypted data segment; and

outputting the encrypted data segment and the validator.

23. The method of claim 21, further comprising:

deriving the message key using a path through a key tree, wherein the path through the key tree is based on the message identifier and identifies the plurality of entropy distribution operations.

24. The method of claim 21, further comprising:

encrypting a plurality of data segments of the message using hash chaining operations comprising;

encrypting a first data segment of the plurality of data segments with a first encryption key derived from the message key to create a first encrypted data segment;

hashing the first encrypted data segment to create a first hash segment;

combining the first hash segment with a second data segment of the plurality of data segments to create a first combined data segment; and

encrypting the first combined data segment with a second encryption key derived from the message key.

25. The method of claim 21, further comprising:

encrypting a plurality of data segments of the message using hash chaining operations comprising;

constructing a first plaintext segment comprising at least a first data segment of the plurality of data segments;

hashing the first plaintext segment to create a first plaintext hash segment;

constructing a second plaintext segment comprising the first plaintext hash segment and a second data segment of the plurality of data segments;

encrypting the first plaintext segment with a first encryption key derived from the message key; and

encrypting the second plaintext segment with a second encryption key derived from the message key.

22. A method comprising:

receiving, by processing hardware, an encrypted data segment and a validator;

obtaining, by the processing hardware, a message identifier corresponding to the encrypted data segment;

deriving, by the processing hardware, a message key using the secret value and the message identifier, where the message key is derived using a plurality of entropy distribution operations;

verifying, using the received validator, that the encrypted data segment has not been modified; and

decrypting the encrypted data segment using a decryption key derived from the message key to produce a decrypted data segment responsive to verifying that the encrypted data segment has not been modified.

26. The method of claim 22, further comprising:

deriving the message key using a path through a key tree, wherein the path through the key tree is based on the message identifier and identifies the plurality of entropy distribution operations.

27. The method of claim 22, further comprising:

receiving and decrypting a plurality of encrypted data segments using hash chaining operations comprising;

cryptographically transforming a first encrypted data segment of the plurality of encrypted data segments to produce a first derived value;

comparing the first derived value with a first expected value;

responsive to determining that the first derived value matches the first expected value, decrypting the first derived value using a first decryption key derived from the message key to produce a first decrypted data segment and a second derived value;

comparing the second derived value with a second expected value; and

responsive to determining that the second derived value matches the second expected value, decrypting the second derived value using a second decryption key derived from the message key to produce a second decrypted data segment.

28. The method of claim 22, further comprising:

receiving and decrypting a plurality of encrypted data segments using hash chaining operations comprising;

decrypting a first encrypted data segment of the plurality of encrypted segments to produce a first plaintext segment comprising a first decrypted data segment and a first hash value;

validating the first hash value; and

responsive to validating the first hash value, decrypting a second encrypted data segment to produce a second plaintext segment comprising a second decrypted data segment and a second hash value.