PROBABILISTIC KEY ROTATION

• US 20160191237A1
• Filed: 03/03/2016
• Published: 06/30/2016
• Est. Priority Date: 02/12/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roth, Gregory Branchek
• Granted Patent: US 10,075,295 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

Abstract

Information, such as a cryptographic key, is used repeatedly in the performance of operations, such as certain cryptographic operations. To prevent repeated use of the information from enabling security breaches, the information is rotated (replaced with other information). To avoid the resource costs of maintaining a counter on the number of operations performed, decisions of when to rotate the information are performed based at least in part on the output of stochastic processes.

Claims

1. A computer-implemented method for managing cryptographic keys in a distributed system, comprising:

under the control of one or more computer systems configured with executable instructions,

receiving a request to perform an operation, the performance of which involves an encryption operation using a first cryptographic key specified in the request; and

as a result of receiving the request;

causing a device to perform the encryption operation using the first cryptographic key;

obtaining a stochastically-generated value; and

as a result of the stochastically-generated value satisfying a set of key rotation criteria, causing the first cryptographic key to be replaced with a second cryptographic key.

2. The computer-implemented method of claim 1, wherein:

the device is a hardware security module of a plurality of hardware security modules with access to the first cryptographic key at the time the request is received; and

causing the first cryptographic key to be replaced causes each hardware security module of the plurality of hardware security modules to replace the first cryptographic key with the second cryptographic key.

3. The computer-implemented method of claim 1, wherein the stochastically-generated value is output of a random or pseudorandom value generator.

4. The computer-implemented method of claim 1, wherein:

obtaining the stochastically-generated value comprises;

randomly or pseudorandomly generating an initial value to obtain a generated initial value; and

as a result of the generated initial value satisfying a set of counter update conditions, determining the stochastically-generated value by updating a counter.

5. The computer-implemented method of claim 1, wherein causing the device to perform the encryption operation using the first cryptographic key includes causing the device to use the stochastically-generated as input into an encryption algorithm.

6. The computer-implemented method of claim 1, wherein the set of key rotation criteria are applied to a property of the stochastically-generated value.

7. A system, comprising:

one or more processors; and

memory storing instructions that, as a result of execution by the one or more processors, cause the system to;

determine a stochastically-generated value;

as a result of the stochastically-generated value satisfying a set of rotation criteria, replacing first information with second information; and

as a result of the stochastically generated value failing to satisfy the set of rotation criteria, allowing the first information to be used to perform an operation at least one additional time in response to a request.

8. The system of claim 7, wherein:

the first information is a cryptographic key; and

the operation includes a cryptographic operation using the cryptographic key.

9. The system of claim 7, wherein determining the stochastically-generated value comprises determining a random or pseudorandom value and checking whether the random or pseudorandom value satisfies one or more conditions.

10. The system of claim 7, wherein:

the stochastically-generated value is a value of a counter; and

determining the stochastically-generated value comprises stochastically determining whether to update the counter.

11. The system of claim 7, the stochastically-generated value is a value of a counter;

and

determining the stochastically-generated value comprises stochastically determining an amount by which to update the counter.

12. The system of claim 7, wherein determination of the stochastically-generated value is triggered by a received request whose fulfillment involves use of the first information to perform an operation.

13. A computer-readable storage medium having stored thereon instructions that, as a result of execution by one or more processors of a system, cause the system to:

probabilistically generate rotation determinations, each rotation determination indicating whether to replace first information with second information for processing requests;

as a result of a generated rotation determination being positive, cause the first information used in processing requests to be replaced with the second information; and

as a result of a generated rotation determination being negative, allow the first information to be used for processing additional requests to be processed using the first information.

14. The computer-readable storage medium of claim 13, wherein the first information is a first cryptographic key of a plurality cryptographic keys managed by the system.

15. The computer-readable storage medium of claim 13, wherein each of at least a subset of the rotation determinations is generated as a result of a received request to perform an operation using the first information.

16. The computer-readable storage medium of claim 13, wherein:

the first information is accessible to a plurality of devices of the system; and

causing the first information to be replaced with the second information includes causing the second information to become accessible to each device of the plurality of devices.

17. The computer-readable storage medium of claim 13, wherein each rotation determination of at least a subset of the rotation determinations is based at least in part on one or more conditions and a randomly or pseudorandomly generated value.

18. The computer-readable storage medium of claim 13, wherein:

probabilistically generating rotation determinations includes probabilistically determining whether to update a counter; and

each rotation determination of at least a subset of the rotation determinations is based at least in part on whether the counter has reached a threshold.

19. The computer-readable storage medium of claim 13, wherein each probabilistically generated rotation determination of at least a subset of the probabilistically generated rotation determinations is based at least in part on a determination whether a stochastically generated value is divisible by another value.

20. The computer-readable storage medium of claim 13, wherein each probabilistically generated rotation determination of at least a subset of the probabilistically generated rotation determinations is based at least in part on a determination whether a stochastically generated sequence of bits satisfies one or more conditions on the sequence.