Multi-tiered encryption system for efficiently regulating use of encryption keys

• US 9,172,532 B1
• Filed: 11/19/2013
• Issued: 10/27/2015
• Est. Priority Date: 11/19/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Fuller, Erik James, Munro, Timothy Peter, Kelly, Adam Blair, Khan, KMR Mumit, Nishigaya, Andrew Norimasa, Wright, Kerry Michael
• Primary Examiner(s): POWERS, WILLIAM S
• Application Number:
  US14/084,440
• Time in Patent Office: 707 Days
• Field of Search: 380/44
• US Class Current: 1/1
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A multi-tiered encryption system efficiently regulates the use of encryption keys to encrypt and decrypt data. The system can include one or more encryption tiers. Each encryption tier can include a computing node programmed to service encryption and/or decryption requests and a key store to store encryption keys. At a root encryption tier, an unencrypted root encryption key can be stored in the key store. Each subsequent encryption tier includes encryption keys that are encrypted by encryption keys stored at a lower encryption tier. The encryption tiers collectively implement an encryption policy in which keys are automatically created and rotated such that a requesting device can request encryption services from the multi-tiered encryption system and receive the encryption services independent of key creation or key rotation and without access to the unencrypted root encryption key.

Claims

1. A computer-implemented method of encrypting data, the method comprising:

receiving, from a requesting device, a first request to encrypt data, wherein the first request comprises the data;

determining whether a first key can be used to encrypt the data;

requesting, in response to determining that the first key can be used to encrypt the data, an encrypted version of the first key from a first data store associated with a first node, wherein the first node is associated with a first tier of keys;

receiving the encrypted version of the first key and a parent key identifier from the data store, wherein the parent key identifier identifies a parent key stored in a second data store associated with a second node configured to decrypt the encrypted version of the first key, and wherein the second node is associated with a second tier of keys;

transmitting, to the second node, a second request to decrypt the encrypted version of the first key, wherein the second request comprises the encrypted version of the first key and the parent key identifier;

receiving, from the second node, a decrypted version of the first key, wherein the second node generates the decrypted version of the first key using the parent key after the parent key is retrieved from the second data store;

encrypting the data using the decrypted version of the first key;

generating a key identifier associated with the first key; and

transmitting, to the requesting device, the encrypted data and the key identifier.

2. The computer-implemented method of claim 1, further comprising storing the decrypted version of the first key in a memory cache.

3. The computer-implemented method of claim 2, further comprising:

receiving, from the requesting device, a third request to decrypt the encrypted data, wherein the third request comprises the encrypted data and the key identifier;

determining that the key identifier is associated with the first key;

retrieving the decrypted version of the first key from the memory cache;

decrypting the encrypted data using the decrypted version of the first key; and

transmitting, to the requesting device, the decrypted data.

4. The computer-implemented method of claim 1, further comprising determining that the first key can no longer be used to encrypt the data.

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

generating a second key;

transmitting, to the second node, a third request to encrypt the second key, wherein the third request comprises the second key and the parent key identifier;

receiving, from the second node, an encrypted version of the second key;

updating the key identifier so that the key identifier is associated with the second key;

storing the encrypted version of the second key in the first data store;

associating the parent key identifier with the second key; and

encrypting the data using the second key; and

transmitting, to the requesting device, the encrypted data and the updated key identifier.

6. The computer-implemented method of claim 4, wherein determining that the first key can no longer be used to encrypt the data comprises one of determining that an amount of data encrypted by the first key has exceeded a first threshold value or determining that a number of times that the first key has been used to encrypt all data has exceeded a second threshold value.

7. The computer-implemented method of claim 1, further comprising:

generating, in response to receiving the first request to encrypt data, a third tier of keys associated with a third node, wherein the third node is associated with a third data store that stores an encrypted version of a third key, and wherein the first key is configured to decrypt an encrypted version of the third key; and

encrypting the data using a decrypted version of the third key.

8. A system comprising:

a first computer data repository that stores an encrypted version of a first key and a parent

key identifier associated with the first key, the first computer data repository comprising a non-transitory storage device; and

a first computing system comprising one or more first computing devices, the first computing system in communication with the first computer data repository and programmed to implement;

a network interface configured to receive, from a requesting device, a first request to encrypt data, wherein the first request comprises the data;

a data retriever configured to retrieve the encrypted version of the first key and the parent key identifier from the first computer data repository, wherein the parent key identifier identifies a parent key stored in a second computer data repository that is configured to decrypt the encrypted version of the first key, wherein the network interface is further configured to transmit, to a second computing system comprising one or more second computing devices, a second request to decrypt the encrypted version of the first key, wherein the second request comprises the encrypted version of the first key and the parent key identifier, wherein the network interface is further configured to receive, from the second computing system, a decrypted version of the first key, and wherein the second computing system generates the decrypted version of the first key using the parent key;

an encrypter configured to encrypt the data using the decrypted version of the first key; and

a literal key identification generator configured to generate a key identifier associated with the first key, wherein the network interface is further configured to transmit, to the requesting device, the encrypted data and the key identifier.

9. The system of claim 8, wherein the network interface is further configured to store the decrypted version of the first key in a computer memory cache.

10. The system of claim 9, wherein the first computing system is further programmed to implement a decrypter configured to receive, from the requesting device, a third request to decrypt the encrypted data, wherein the third request comprises the encrypted data and the key identifier, wherein the decrypter is further configured to determine that the key identifier is associated with the first key, wherein the data retriever is further configured to retrieve the decrypted version of the first key from the computer memory cache, wherein the decrypter is further configured to decrypt the encrypted data using the decrypted version of the first key, and wherein the network interface is further configured to transmit, to the requesting device, the decrypted data.

11. The system of claim 8, wherein the first computing system is further programmed to implement a literal key generator configured to generate a second key in response to a determination that the first key can no longer be used to encrypt the data.

12. The system of claim 11, wherein the network interface is further configured to transmit, to the second computing system, a third request to encrypt the second key, wherein the third request comprises the second key and the parent key identifier, wherein the network interface is further configured to receive, from the second computing system, an encrypted version of the second key, wherein the literal key identification generator is further configured to update the key identifier so that the key identifier is associated with the second key, wherein the data retriever is further configured to store the encrypted version of the second key in the first computer data repository, wherein the data retriever is further configured to associate the parent key identifier with the second key, wherein the encrypter is further configured to encrypt the data using the second key, and wherein the network interface is further configured to transmit, to the requesting device, the encrypted data and the updated key identifier.

13. The system of claim 11, wherein the literal key generator is configured to determine that the first key can no longer be used to encrypt the data if one of an amount of data encrypted by the first key has exceeded a first threshold value or a number of times that the first key has been used to encrypt all data has exceeded a second threshold value.

14. The system of claim 8, wherein the computing system is further programmed to implement a tier generator configured to access, in response to reception of the first request to encrypt data, a third computing system comprising one or more third computing devices and a third computer data repository, wherein the third computer data repository stores an encrypted version of a third key, and wherein the first key is configured to decrypt an encrypted version of the third key.

15. The system of claim 14, wherein the encrypter is further configured to encrypt the data using a decrypted version of the third key.

16. A computer storage system comprising a non-transitory

storage device, said computer storage system having stored thereon executable

program instructions that direct a computer system to at least:

receive, from a requesting device, a first request to encrypt data, wherein the first request

comprises the data;

retrieve an encrypted version of a first key and a parent key identifier from a computer

data repository, wherein the parent key identifier identifies a parent key stored in the computer

data repository that is configured to decrypt the encrypted version of the first key;

transmit, to a second computer system, a second request to decrypt the encrypted version

of the first key, wherein the second request comprises the encrypted version of the first key and

the parent key identifier;

receive, from the second computer system, a decrypted version of the first key, wherein

the second computing system generates the decrypted version of the first key using the parent key;

encrypt the data using the decrypted version of the first key;

generate a key identifier associated with the first key; and

transmit, to the requesting device, the encrypted data and the key identifier.

17. The computer storage system of claim 16, wherein the executable program instructions further direct the computer system to at least store the decrypted version of the first key in a computer memory cache.

18. The computer storage system of claim 17, wherein the executable program instructions further direct the computer system to at least:

receive, from the requesting device, a third request to decrypt the encrypted data, wherein the third request comprises the encrypted data and the key identifier;

determine that the key identifier is associated with the first key;

retrieve the decrypted version of the first key from the computer memory cache;

decrypt the encrypted data using the decrypted version of the first key; and

transmit, to the requesting device, the decrypted data.

19. The computer storage system of claim 16, wherein the executable program instructions direct the computer system to generate a second key in response to a determination that the first key can no longer be used to encrypt the data.

20. The computer storage system of claim 19, wherein the executable program instructions further direct the computer system to at least:

transmit, to the second computing system, a third request to encrypt the second key, wherein the third request comprises the second key and the parent key identifier;

receive, from the second computing system, an encrypted version of the second key;

update the key identifier so that the key identifier is associated with the second key;

store the encrypted version of the second key in the computer data repository;

associate the parent key identifier with the second key;

encrypt the data using the second key; and

transmit, to the requesting device, the encrypted data and the updated key identifier.

21. The computer storage system of claim 19, wherein the executable program instructions further direct the computer system to at least determine that the first key can no longer be used to encrypt the data if one of an amount of data encrypted by the first key has exceeded a first threshold value or a number of times that the first key has been used to encrypt all data has exceeded a second threshold value.

22. A computer-implemented method of decrypting data, the method comprising:

receiving, by a first computing system from a requesting device, a first request to decrypt encrypted data, wherein the first request comprises the encrypted data and a key identifier;

determining that the key identifier is associated with a first key;

retrieving, from a data store, an encrypted version of the first key and a parent key identifier that is associated with the first key;

transmitting, to a second computing system, a second request to decrypt the encrypted version of the first key, wherein the second request comprises the encrypted version of the first key and the parent key identifier;

receiving, from the second computing system, a decrypted version of the first key, wherein the second computing system generates the decrypted version of the first key using the parent key;

decrypting the encrypted data using the decrypted version of the first key; and

transmitting, to the requesting device, the decrypted data.

23. The computer-implemented method of claim 22, further comprising decrypting the encrypted data using the decrypted version of the first key even if use of the first key is revoked.

24. The computer-implemented method of claim 22, further comprising storing the decrypted version of the first key in a memory cache.

25. The computer-implemented method of claim 24, further comprising:

receiving, from the requesting device, a third request to decrypt encrypted second data, wherein the third request comprises the encrypted second data and a second key identifier;

determining that the second key identifier is associated with a second key;

retrieving, from the data store, an encrypted version of the second key and the key identifier that is associated with the second key;

determining that the key identifier is associated with the first key;

retrieving, from the memory cache, the decrypted version of the first key;

decrypting the encrypted version of the second key using the decrypted version of the first key;

decrypting the encrypted second data using the decrypted version of the second key; and

transmitting, to the requesting device, the decrypted second data.