Automated data re-encryption process in multi-tiered encryption system

• US 9,722,974 B1
• Filed: 12/18/2014
• Issued: 08/01/2017
• Est. Priority Date: 12/18/2014
• Status: Active Grant

• Current Assignee: AbeBooks, Inc. (Amazon.com, Inc.)
• Original Assignee: AbeBooks, Inc. (Amazon.com, Inc.)
• Inventors: Tilgner, Volker R. A., Wright, Kerry Michael, Fuller, Erik James, Nassaje, Ali Mustafa, Sparrow, Julie Anne Margaret
• Primary Examiner(s): Popham, Jeffrey D
• Application Number:
  US14/575,906
• Time in Patent Office: 957 Days
• Field of Search: 713171
• CPC Class Codes: H04L 2209/76 Proxy, i.e. using intermediary entity to perform cryptographic operations
• 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/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

A re-encryption service module in a multi-tiered encryption system that manages key rotation policies continuously or periodically re-encrypts data. Each encryption tier in the system can include a node programmed to service encryption, decryption, and/or re-encryption requests and a key store to store encryption keys. A computing node that interfaces with a requesting device may include the re-encryption service module. The re-encryption module may receive encrypted data and a key identifier identifying the key used to encrypt the data. The re-encryption module may decrypt the encrypted data using the identified key, retrieve a new key if the identified key is exhausted, and use the new key to encrypt the decrypted data. The key identifier may be updated to identify the new key and the re-encrypted data and the updated key identifier may be transmitted to the requesting device.

Claims

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

by execution of program instructions by one or more computing devices;

receiving, from a requesting device separate from the one or more computing devices, a first request to encrypt data;

encrypting the data using a first key that is not accessed by the requesting device;

generating a key identifier associated with the first key;

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

receiving, from the requesting device, a second request to re-encrypt the encrypted data, wherein the second request comprises the encrypted data and the key identifier;

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

generating a second key at least partly in response to determining that the first key is exhausted;

decrypting the encrypted data using the first key to generate a decrypted version of the encrypted data;

encrypting, using the second key, the decrypted version of the encrypted data to generate a re-encrypted version of the encrypted data;

associating the key identifier with the second key; and

transmitting, to the requesting device, the re-encrypted version of the data.

2. The computer-implemented method of claim 1, wherein an encrypted version of the first key is stored in a first data store associated with a first node, and wherein the first key is encrypted using a parent key stored in a second data store associated with a second node.

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

determining that the parent key can be used to encrypt data;

in response to determining that the parent key can be used to encrypt data, encrypting the second key using the parent key to generate an encrypted version of the second key; and

storing the encrypted version of the second key and a parent key identifier that identifies the parent key in the first data store.

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

determining that the parent key cannot be used to encrypt data;

in response to determining that the parent key cannot be used to encrypt data, generating a second parent key;

encrypting the second key using the second parent key to generate an encrypted version of the second key;

associating the parent key identifier with the second parent key; and

storing the encrypted version of the second key and the parent key identifier in the first data store.

5. The computer-implemented method of claim 2, wherein the parent key is a master key.

6. The computer-implemented method of claim 1, wherein determining that the first key is exhausted comprises at least one of determining that an amount of data encrypted by the first key has satisfied a first threshold value, determining that a number of times the first key has been used to encrypt data has satisfied a second threshold value, determining that the first key has been in existence for a time period satisfying a third threshold value, or determining that the first key was used to encrypt the data.

7. A system comprising:

a computer data repository maintained in a non-transitory storage device, the computer data repository configured to at least store keys; and

a computing system comprising one or more computing devices, the computing system in communication with the computer data repository and configured to at least;

receive, from a requesting device separate from the computing system, a first request to encrypt data;

transmit, to the requesting device, an encrypted version of the data and a key identifier associated with a first key that is not accessed by the requesting device, wherein the key identifier is used to encrypt the data;

receive, from the requesting device, a second request to re-encrypt the encrypted data, wherein the second request specifies the encrypted data and the key identifier;

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

generate a second key at least partly in response to determining that the first key is exhausted;

decrypt the encrypted data using the first key to generate a decrypted version of the encrypted data;

encrypt, using the second key, the decrypted version of the encrypted data to generate a re-encrypted version of the encrypted data; and

associate the key identifier with the second key; and

transmit, to the requesting device, the re-encrypted version of the data.

8. The system of claim 7, wherein an encrypted version of the first key is stored in a first data store associated with a first node, and wherein the computing system is further programmed to implement an encrypter configured to encrypt the first key using a parent key stored in a second data store associated with a second node.

9. The system of claim 8, wherein the computing system is further configured to at least:

determine that the parent key can be used to encrypt data;

in response to determining that the parent key can be used to encrypt data, encrypt the second key using the parent key to generate an encrypted version of the second key;

store the encrypted version of the second key and a parent key identifier that identifies the parent key in the first data store.

10. The system of claim 8, wherein the computing system is further configured to at least:

determine that the parent key cannot be used to encrypt data;

in response to determining that the parent key cannot be used to encrypt data, generate a second parent key;

encrypt the second key using the second parent key to generate an encrypted version of the second key;

associate the parent key identifier with the second parent key; and

store the encrypted version of the second key and the parent key identifier in the first data store.

11. The system of claim 8, wherein the parent key is a master key.

12. The system of claim 7, wherein the encrypted version of data comprises a plurality of data elements, and wherein each data element comprises an encrypted value.

13. The system of claim 12, wherein the computing system is further configured to at least:

for each data element in the plurality of data elements;

decrypt the encrypted value using the first key;

determine that the second key can be used to encrypt data; and

in response to determining that the second key can be used to encrypt data, encrypt the decrypted version of the encrypted value using the second key.

14. The system of claim 12, wherein the computing system is further configured to at least:

for each data element in the plurality of data elements;

decrypt the encrypted value using the first key;

determine that the second key cannot be used to encrypt data;

in response to determining that the second key cannot be used to encrypt data, generate a third key; and

encrypt the decrypted version of the encrypted value using the third key.

15. The system of claim 7, wherein the computing system is further configured to at least determine at least one of:

an amount of data encrypted by the first key has satisfied a first threshold value;

that a number of times that the first key has been used to encrypt data has exceeded a second threshold value;

that the first key has been in existence for a time period satisfying a third threshold value;

or

that the first key was used to encrypt the data.

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 separate from the computer system, a first request to encrypt data;

encrypt the data using a first key that is not accessed by the requesting device;

generate a key identifier associated with the first key;

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

receive, from the requesting device, a second request to re-encrypt data, wherein the second request specifies the encrypted data and the key identifier;

determine that the first key is exhausted;

generate a second key at least partly in response to determining that the first key is exhausted;

decrypt the encrypted data using the first key to generate a decrypted version of the encrypted data;

encrypt, using the second key, the decrypted version of the encrypted data to generate a re-encrypted version of the encrypted data;

associate the key identifier with the second key; and

transmit, to the requesting device, the re-encrypted version of the data.

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

determine that a parent key can be used to encrypt data;

in response to determining that the parent key can be used to encrypt data, encrypt the second key using the parent key to generated an encrypted version of the second key; and

store the encrypted version of the second key and a parent key identifier that identifies the parent key in a first data store.

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

determine that a parent key cannot be used to encrypt data;

in response to determining that the parent key cannot be used to encrypt data, generate a second parent key;

encrypt the second key using the second parent key to generate an encrypted version of the second key;

associate the parent key identifier with the second parent key; and

store the encrypted version of the second key and the parent key identifier in a first data store.

19. The computer storage system of claim 18, wherein the parent key is a master key.

20. The computer storage system of claim 16, wherein the encrypted data comprises a plurality of data elements, and wherein each data element comprises an encrypted value.

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

for each data element in the plurality of data elements,

decrypt the encrypted value using the first key; and

encrypt the decrypted version of the encrypted value using the second key.

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

partition the plurality of data elements into a first plurality of data elements and a second plurality of data elements;

provision a first re-encryption service module and a second re-encryption service module;

direct the first re-encryption service module to at least;

decrypt the encrypted value in each data element of the first plurality of data elements using the first key, and

encrypt the decrypted version of the encrypted value in each data element of the first plurality of data elements using the second key; and

direct the second re-encryption service module to at least;

decrypt the encrypted value in each data element of the second plurality of data elements using the first key, and

encrypt the decrypted version of the encrypted value in each data element of the second plurality of data elements using the second key.

23. The computer storage system of claim 16, wherein the executable program instructions further direct the computer system to at least receive, from the requesting device, requests to re-encrypt the encrypted data at periodic intervals.

24. The computer storage system of claim 16, wherein the executable program instructions further direct the computer system to at least determine at least one of:

that an amount of data encrypted by the first key has satisfied a first threshold value;

that a number of times that the first key has been used to encrypt data has satisfied a second threshold value;

that the first key has been in existence for a time period satisfying a third threshold value;

or

that the first key was used to encrypt the data.

25. The computer storage system of claim 16, wherein the executable program instructions further direct the computer system to receive, from the requesting device, requests to re-encrypt the encrypted data at periodic intervals.