Multiple authority key derivation

• US 10,044,503 B1
• Filed: 11/14/2014
• Issued: 08/07/2018
• Est. Priority Date: 03/27/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roth, Gregory B., Barbour, Marc R., Behm, Bradley Jeffery, Ilac, Cristian M., Brandwine, Eric Jason
• Primary Examiner(s): Kim, Tae
• Assistant Examiner(s): Kanaan, Simon
• Application Number:
  US14/542,492
• Time in Patent Office: 1,362 Days
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 63/064 Hierarchical key distribution, e.g. by multi-tier trusted parties
• 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

Systems and methods for authentication generate keys from secret credentials shared between authenticating parties and authenticators. Generation of the keys may involve utilizing specialized information in the form of parameters that are used to specialize keys. Keys and/or information derived from keys held by multiple authorities may be used to generate other keys such that signatures requiring such keys and/or information can be verified without access to the keys. Keys may also be derived to form a hierarchy of keys that are distributed such that a key holder'"'"'s ability to decrypt data depends on the key'"'"'s position in the hierarchy relative to the position of a key used to encrypt the data. Key hierarchies may also be used to distribute key sets to content processing devices to enable the devices to decrypt content such that sources or potential sources of unauthorized content are identifiable from the decrypted content.

Claims

1. A computer-implemented method, comprising:

receiving a root key from a key authority;

generating, based at least in part on the root key and using a cryptographic hash function that includes an operand associated with usage restrictions on at least some generated keys, a plurality of keys that corresponds to a plurality of levels hierarchically subordinate to the key authority;

generating a key hierarchy comprising the root key and the plurality of keys arranged according to the plurality of levels;

associating, based at least in part on the cryptographic hash function, a subset of the usage restrictions to an individual level of the key hierarchy;

receiving encrypted data having been encrypted using a particular key in the key hierarchy, the encrypted data being decryptable using any key in the key hierarchy at a level equal to or higher than that of the particular key but undecryptable by any key lower in the key hierarchy than the level;

decrypting the encrypted data using a key from the key hierarchy; and

providing access to the decrypted data.

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

each level of the plurality of levels corresponds to a level of authority within an organization.

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

accessing data that associates, by a data store, the encrypted data with an identifier of the particular key; and

identifying the key in the key hierarchy is based at least in part on the data that associates the encrypted data with the identifier of the particular key.

4. A system, comprising:

one or more processors; and

memory including instructions executable with the one or more processors to cause the system to at least;

receive a root key from a key authority;

generate a plurality of keys to form a key hierarchy that comprises the root key and a plurality of keys that corresponds to a plurality of levels hierachically subordinate to the key authority, each key of the plurality of keys being derived using a cryptographic hash function, the cryptographic hash function including an operand that is associated with a usage restriction on at least some keys of the plurality of keys;

associate, based on the cryptographic hash function, a particular combination of one or more usage restrictions to each key of the plurality of keys; and

cause one or more cryptographic operations to be performed using a particular key from the key hierarchy,

wherein causing performance of the one or more cryptographic operations includes encrypting data in a manner that results in the encrypted data being decryptable using any key in the key hierarchy at a level equal to or higher than that of the particular key, but undecryptable using any key lower in the key hierarchy than the level.

5. The system of claim 4, wherein the cryptographic hash function further includes a second operand, the second operand being associated with a particular key of the plurality of keys.

6. The system of claim 4, wherein causing performance of the one or more cryptographic operations includes distributing at least a subset of the plurality of keys among a set of one or more computer systems to enable each of the one or more computer systems to perform at least one of the one or more cryptographic operations.

7. The system of claim 4, wherein performance of the one or more cryptographic operations includes:

for data encrypted using the particular key from the key hierarchy;

identifying a key from which the particular key was derived;

deriving, based at least in part on the identified key, the particular key; and

providing the particular key for decryption of the encrypted data.

8. The system of claim 7, wherein the identified key used to derive the particular key is usable, without access to a previously derived and persistently stored copy of the particular key, to decrypt data encrypted by the particular key.

9. The system of claim 7, wherein deriving the particular key includes accessing data associated with a usage restriction on the particular key and is based at least in part on the data associated with the usage restriction.

10. The system of claim 7, wherein the particular key corresponds to a principal having a scope of data access ability and wherein the key from which the particular key was derived corresponds to another principal having another scope of data access ability that is larger than the scope of data access ability.

11. A non-transitory computer-readable storage medium having stored therein instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:

receive a root key from a key authority;

generate, based at least in part on the root key and using a cryptographic hash function that includes an operand associated with usage restrictions on at least some generated keys, a plurality of keys that corresponds to a plurality of levels hierarchically subordinate to the key authority;

generate a key hierarchy comprising the root key and the plurality of keys arranged according to the plurality of levels;

associate, based at least in part on the cryptographic hash function, a subset of the usage restrictions to an individual level of the key hierarchy;

obtain unencrypted data;

encrypt the unencrypted data to produce encrypted data using a particular key in the key hierarchy, the encrypted data being decryptable using a key in the key hierarchy at a level equal to or higher than that of the particular key and undecryptable by a key lower in the key hierarchy than the level; and

provide access to the encrypted data.

12. The non-transitory computer-readable storage medium of claim 11, wherein the encrypted data is decryptable using a key in the key hierarchy at a level equal to or higher than that of the particular key and undecryptable by a key lower in the key hierarchy than the level.

13. The non-transitory computer-readable storage medium of claim 11, wherein the cryptographic function includes another operand that is associated with another key in the key hierarchy.

14. The non-transitory computer-readable storage medium of claim 11, wherein the particular key functions as an identifier for one or more electronic devices.

15. The non-transitory computer-readable storage medium of claim 11, wherein a respective key in the key hierarchy corresponds to a principal having a particular scope of authority.

16. The non-transitory computer-readable storage medium of claim 11, wherein the operand is a first operand and the cryptographic hash function includes a second operand, wherein the first and second operand include another key in the key hierarchy and a usage restriction on the key.

17. The non-transitory computer-readable storage medium of claim 16, wherein the usage restriction is associated with one of a date, a time, a virtual computer system service, or a geographical region.

18. The non-transitory computer-readable storage medium of claim 11, wherein each hierarchy level corresponds to a level of authority within an organizational hierarchy.

19. The non-transitory computer-readable storage medium of claim 18, wherein a first key associated with a first level of authority, the first level of authority being higher in the organizational hierarchy than a second level of authority, decrypts data that has been encrypted by a second key, the second key being associated with the second level of authority.