Supporting a fixed transaction rate with a variably-backed logical cryptographic key

• US 9,942,036 B2
• Filed: 08/29/2016
• Issued: 04/10/2018
• Est. Priority Date: 06/27/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roth, Gregory Branchek, Campagna, Matthew John, Seidenberg, Benjamin Elias
• Primary Examiner(s): BAYOU, YONAS A
• Application Number:
  US15/250,738
• Publication Number:
  US 20170093569A1
• Time in Patent Office: 589 Days
• CPC Class Codes: H04L 63/065 for group communications cryptographic mechanisms or cryptographic arrangements for key management involving conference or group key H04L9/0833
• 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/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

A request a request to perform a cryptographic operation is received, the request including a first identifier assigned to a key group, the key group comprising a plurality of second identifiers, with the plurality of second identifiers corresponding to a plurality of cryptographic keys. A second identifier is determined, according to a distribution scheme, from the plurality of second identifiers, and the cryptographic operation is performed using a cryptographic key of the plurality of cryptographic keys that corresponds to the second identifier that was determined.

Claims

1. A computer-implemented method, comprising:

receiving a request to perform a cryptographic operation, the request identifying a plurality of keys where a usage rate of an individual key in the plurality of keys is limited at an associated individual usage rate;

selecting a key from the plurality of keys according to a distribution scheme that distributes requests over the plurality of keys, the distribution scheme allowing the plurality of keys to be used at an aggregate rate greater than each associated individual usage rate limit; and

performing the cryptographic operation on one or more hardware processors using the key.

2. The computer-implemented method of claim 1, wherein the distribution scheme is one of:

a round-robin selection scheme,

a stochastic distribution scheme,

a probabilistic distribution scheme, or

a distribution scheme that assigns a weight to a cryptographic key based at least in part on proximity to an exhaustion threshold of a current usage of the cryptographic key.

3. The computer-implemented method of claim 1, wherein selecting the key further depends at least in part on a type of the cryptographic operation being requested.

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

the plurality of keys has an aggregate usage rate requirement;

individual cryptographic keys of the plurality of keys have separate key usage rate limits; and

a quantity of cryptographic keys in the plurality is dependent at least in part on an aggregation of the separate key usage rate exceeding the aggregate usage rate requirement.

5. The computer-implemented method of claim 4, further comprising:

receiving a second request, the second request being a request to change the aggregate usage rate requirement; and

as a result of receiving the second request, making a change to the plurality of keys.

6. The computer-implemented method of claim 5, wherein making the change includes changing the quantity of cryptographic keys in the plurality of keys.

7. The computer-implemented method of claim 5, wherein making the change includes changing a key usage rate limit of at least one cryptographic key in the plurality of keys.

8. A system, comprising:

one or more processors; and

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

receive a request to perform a cryptographic operation, the request identifying a plurality of cryptographic keys where a usage rate of an individual key in the plurality of cryptographic keys is limited at an associated individual usage rate;

select a key from the plurality of cryptographic keys according to a distribution scheme that distributes requests over the plurality of cryptographic keys, the distribution scheme allowing the plurality of cryptographic keys to be used at an aggregate rate greater than each associated individual usage rate; and

perform the cryptographic operation using the key.

9. The system of claim 8, wherein:

the instructions further include instructions that cause the system to receive an aggregate key usage rate requirement, the aggregate key usage rate requirement to be associated with the plurality of cryptographic keys;

each cryptographic key in the plurality of cryptographic keys has a corresponding maximum usage rate for the cryptographic key; and

the number of cryptographic keys in the plurality of cryptographic keys is determined based at least in part on the corresponding maximum usage rate for each key and the aggregate key usage rate requirement.

10. The system of claim 8, wherein the instructions further include instructions that cause the system to:

determine that usage of the key exceeds a maximum usage threshold corresponding to the key; and

deprovision the key such that the key is prevented from being used to perform additional cryptographic operations.

11. The system of claim 8, wherein the plurality of cryptographic keys are distributed over multiple fault zones.

12. The system of claim 11, wherein the multiple fault zones are logical divisions of resources to mitigate correlated failures, the multiple fault zones being separated by:

geographic region,

individual server, or

hard drive cluster in a server.

13. The system of claim 11, wherein:

a first key is distributed to a first fault zone of the multiple fault zones; and

a second key is distributed to a second fault zone, different from the first fault zone, of the multiple fault zones.

14. The system of claim 13, wherein the second key is selected as a result of an occurrence of a failure at the first fault zone.

15. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:

receive a request to perform a cryptographic operation, the request identifying a plurality of cryptographic keys where a usage rate of an individual key in the plurality of cryptographic keys is limited at an associated individual usage rate;

select a key from the plurality of cryptographic keys according to a distribution scheme that distributes requests over the plurality of cryptographic keys, the distribution scheme allowing the plurality of cryptographic keys to be used at an aggregate rate greater than each associated individual usage rate; and

perform the cryptographic operation using the key.

16. The non-transitory computer-readable storage medium of claim 15, wherein:

the cryptographic operation is an encryption operation; and

the key is a public key of an asymmetric encryption key pair.

17. The non-transitory computer-readable storage medium of claim 15, wherein the executable instructions further that include executable instructions that cause the computer system to:

determine an aggregate key usage rate requirement to associate with the plurality of crytographic keys; and

a quantity of cryptographic keys are generated that depends at least in part on an aggregation of respective maximum usage rate thresholds of the plurality of cryptographic keys exceeding the aggregate key usage rate requirement.

18. The non-transitory computer-readable storage medium of claim 17, wherein the aggregate key usage rate requirement is determined based at least in part on a historic rate of performing cryptographic operations using the plurality of cryptographic keys.

19. The non-transitory computer-readable storage medium of claim 15, wherein:

each cryptographic key generated has a corresponding exhaustion threshold;

on a condition that the cryptographic operation is of a first type of cryptographic operation, performing the cryptographic operation is applied toward the exhaustion threshold of the key; and

on a condition that the cryptographic operation is of a second type of cryptographic operation, performing the cryptographic operation is not applied toward the exhaustion threshold of the key.

20. The non-transitory computer-readable storage medium of claim 19, wherein:

the first type of cryptographic operation is an encryption operation; and

the second type of cryptographic operation is a decryption operation.