Multiple authority key derivation

• US 10,425,223 B2
• Filed: 05/18/2018
• Issued: 09/24/2019
• 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 Jeffrey, Ilac, Cristian M., Brandwine, Eric Jason
• Primary Examiner(s): Kanaan, Simon P
• Application Number:
  US15/984,198
• Publication Number:
  US 20180270051A1
• Time in Patent Office: 494 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:

generating a key hierarchy that comprises a root key and a plurality of levels of subordinate keys, a first level of the plurality of levels including a first subordinate key derived from the root key and associated with a first usage restriction, and a second level of the plurality of levels including a second subordinate key derived from the first subordinate key and associated with a second usage restriction that includes the first usage restriction;

receiving a request having been encrypted using the second subordinate key;

determining that the request indicates non-compliance with at least one of the first usage restriction or the second usage restriction; and

denying the request as a result of the non-compliance.

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

receiving a second request having been encrypted using the first subordinate key;

determining that the second request indicates compliance with the first usage restriction;

decrypting the second request using one of the root key, any subordinate key of the first level, or any subordinate key of a different level of the plurality of levels from which subordinate keys of the first level were derived; and

processing of the decrypted second request.

3. The computer-implemented method of claim 1, further comprising identifying the second subordinate key based on data associating the request with the second subordinate key.

4. A system, comprising:

one or more processors; and

memory including instructions that, if executed by the one or more processors, cause the system to at least;

derive a plurality of keys to form a key hierarchy that comprises a root key and a plurality of levels of subordinate keys, each subordinate key being derived based on information encoding a usage restriction associated with a corresponding level of the plurality of levels;

associate, based on the encoded information, a particular combination of one or more usage restrictions to each subordinate key in accordance with a respective level of the plurality of levels; and

cause one or more cryptographic operations to be performed using a subordinate key from the key hierarchy.

5. The system of claim 4, wherein the information includes a cryptographic hash function that includes a first operand associated with the usage restriction.

6. The system of claim 5, wherein the cryptographic hash function includes a second operand associated with a particular subordinate key of the plurality of levels.

7. The system of claim 4, wherein causing performance of the one or more cryptographic operations includes distributing a subset of the plurality of keys to a computer system to enable the computer systems to perform a subset of the one or more cryptographic operations.

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

receiving data encrypted using a given subordinate key of the plurality of keys;

identifying a key from which the given subordinate key was derived;

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

providing the given subordinate key for decryption of the encrypted data.

9. The system of claim 8, wherein the identified key used to derive the given subordinate key is usable to decrypt other data encrypted by the given subordinate key.

10. The system of claim 8, wherein deriving the given subordinate key is based at least in part on other information associated with a usage restriction associated with the given subordinate key.

11. The system of claim 4, 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 a subordinate key of the plurality of keys or another key from which the subordinate key was derived, but undecryptable using a key of the plurality of keys that was derived from the subordinate key.

12. A non-transitory computer-readable storage medium having stored thereon instructions that, if 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;

derive a plurality of keys to form a key hierarchy that comprises the root key and a plurality of levels of subordinate keys, each subordinate key being derived using information encoding a usage restriction associated with a respective level of the plurality of levels;

associate a particular combination of one or more usage restrictions to a level of the plurality of levels; and

process a request associated with a particular subordinate key corresponding to the level based on compliance, for the request, with the particular combination of the one or more usage restrictions.

13. The non-transitory computer-readable storage medium of claim 12, wherein the request is encrypted and decryptable using the particular subordinate key or another key from which the particular subordinate key was derived, but undecryptable using a key of the plurality of keys that was derived from the particular subordinate key.

14. The non-transitory computer-readable storage medium of claim 12, wherein the information encoding the usage restriction includes a cryptographic function identifying the usage restriction.

15. The non-transitory computer-readable storage medium of claim 12, wherein the particular subordinate key is usable as an identifier to correspond with the request.

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

17. The non-transitory computer-readable storage medium of claim 12, wherein the information encoding the usage restriction also identifies another key in the key hierarchy.

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

19. The non-transitory computer-readable storage medium of claim 12, wherein the key hierarchy comprises a plurality of hierarchy levels and each hierarchy level corresponds to a level of authority within an organizational hierarchy.

20. The non-transitory computer-readable storage medium of claim 19, 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.