Updating cryptographic key pair

• US 9,893,885 B1
• Filed: 03/13/2015
• Issued: 02/13/2018
• Est. Priority Date: 03/13/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Miller, Derek Del, Potlapally, Nachiketh Rao
• Primary Examiner(s): Reza, Mohammad W
• Application Number:
  US14/658,136
• Time in Patent Office: 1,068 Days
• Field of Search: 380 44
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/0897 involving additional devices, e.g. trusted platform module [TPM], smartcard or USB
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

A computing device has a processor and a persistent memory, e.g., a fuse-based memory, storing two or more reduced sets of information. The processor is configured to derive a first cryptographic key using a first reduced set of information, e.g., prime numbers, and to use the first cryptographic key for performing cryptographic operations. The processor is also configured to detect a trigger event and, in response to the detected trigger event, derive a second cryptographic key using a second reduced set of information. The processor can then use the second cryptographic key for performing cryptographic operations.

Claims

1. A system-on-chip, comprising:

a processor;

an electrically erasable programmable non-volatile memory; and

a fuse-based memory having a plurality of prime numbers stored therein, and having a plurality of indices each associated with a respective pair of prime numbers from the plurality of prime numbers, wherein the fuse-based memory includes a fuse-based structure configured to remain unchanged after being burnt;

wherein the processor is configured to;

retrieve a first pair of prime numbers associated with a first index of the indices from the fuse-based memory;

derive a first private key using the first pair of prime numbers;

use the first private key with an asymmetric cryptographic algorithm for performing cryptographic operations;

detect a trigger event for generating a new cryptographic key;

in response to the detected trigger event, retrieve a second pair of prime numbers associated with a second index of the indices from the fuse-based memory, and derive a second private key for the asymmetric cryptographic algorithm as a new cryptographic key, using the second pair of prime numbers; and

use the second private key for performing additional cryptographic operations.

2. The system-on-chip of claim 1, wherein the first and second private keys comprise respective RSA (Rivest-Shamir-Adleman) private keys.

3. The system-on-chip of claim 1, wherein the trigger event comprises receiving information indicating that the first private key is compromised.

4. The system-on-chip of claim 1, wherein the trigger event comprises a fixed number of cryptographic operations performed using the first private key or a preset volume of data encrypted using the first private key.

5. A computing device, comprising:

a processor; and

a persistent memory having reduced sets of information stored therein, the reduced sets of information comprising parameters for deriving cryptographic keys, wherein the reduced sets of information have fewer bits than the cryptographic keys, and the persistent memory is configured to remain unchanged after being written;

wherein the processor is configured to;

retrieve a first reduced set of information from the persistent memory;

derive a first cryptographic key using the first reduced set of the reduced sets of information;

use the first cryptographic key for performing cryptographic operations;

detect a trigger event for generating a new cryptographic key;

in response to the detected trigger event, retrieve a second reduced set of information from the persistent memory and derive a second cryptographic key as a new cryptographic key, using the second reduced set of the reduced sets of information; and

use the second cryptographic key for performing the cryptographic operations.

6. The device of claim 5, further comprising indices, wherein each of the indices is associated with a respective reduced set of the reduced sets of information.

7. The device of claim 6, wherein the processor is configured to access the reduced sets of information using the indices.

8. The device of claim 5, wherein the persistent memory is immutable and comprises a fuse-based memory.

9. The device of claim 5, wherein each of the first and second reduced sets of information comprises a respective pair of prime numbers from a plurality of prime numbers for deriving an RSA (Rivest-Shamir-Adleman) key pair.

10. The device of claim 5, wherein each of the first and second reduced sets of information comprises parameters for an elliptic curve cryptography (ECC) key pair.

11. The device of claim 10, wherein each of the first and second reduced sets of information comprises an elliptic curve specification and a prime number for the elliptic curve cryptography (ECC) key pair.

12. The device of claim 5, wherein the trigger event comprises an indication from a server to change an index of the reduced set of information used for generating the private key.

13. The device of claim 5, wherein the trigger event comprises receiving information indicating that the first cryptographic key is compromised.

14. The device of claim 5, wherein the trigger event comprises a preset elapsed time of using the first cryptographic key.

15. The device of claim 5, wherein the trigger event comprises a fixed number of cryptographic operations performed using the first private key or a preset volume of data encrypted using the first cryptographic key.

16. The device of claim 5, wherein the first cryptographic key is configured for a first identity of the computing device, and wherein the trigger event comprises a request for generating the second cryptographic key for a second identity of the computing device.

17. A computing device, comprising:

a processor; and

a fuse-based memory having a plurality of prime numbers stored therein by a provisioning system, wherein the fuse-based memory includes a fuse-based structure configured to remain unchanged after being burnt;

wherein the processor is configured to;

retrieve two or more pairs of prime numbers of the plurality of prime numbers from the fuse-based memory;

assign an index to each selected pair of prime numbers;

derive a first private key associated with an asymmetric cryptographic algorithm using a first pair of the prime numbers associated with a first index;

use the first private key for performing cryptographic operations;

detect a trigger event for generating a new cryptographic key;

in response to the detected trigger event, derive a second private key associated with the asymmetric cryptographic algorithm as a new cryptographic key, using a second pair of the prime numbers associated with a second index; and

use the second private key for performing the cryptographic operations.

18. The device of claim 17, wherein the first and second private keys are RSA (Rivest-Shamir-Adleman) private keys.

19. The device of claim 17, wherein the first private key is configured for a first identity of the computing device, and wherein the trigger event comprises a request for generating the second private key for a new identity of the computing device.

20. The device of claim 17, wherein the trigger event comprises a fixed number of cryptographic operations performed using the first private key or a preset volume of data encrypted using the first private key.