Key generation for hierarchical data access

• US 9,215,076 B1
• Filed: 03/27/2012
• Issued: 12/15/2015
• 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): Okeke, Izunna
• Assistant Examiner(s): Wright, Bryan
• Application Number:
  US13/431,882
• Time in Patent Office: 1,358 Days
• Field of Search: 713/176
• US Class Current: 1/1
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 2463/061 applying further key derivation, e.g. deriving traffic keys from a pair-wise master key
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

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:

under the control of one or more computer systems configured with executable instructions,

obtaining a key-holder key set comprising a key for each key holder of a plurality of key holders, each obtained key having been derived based at least in part on a key-holder key for a corresponding key holder and a set of key-use restrictions;

calculating, by at least inputting into a function the set of key-use restrictions and a result of performing an operation on the key-holder set, a signing key;

generating, based at least in part on the signing key, an expected signature for a message submitted in connection with a message signature; and

transmitting an electronic message that indicates whether the expected signature matches the message signature, the electronic message being usable to evaluate whether access to one or more computing resources is permitted, the set of key-use restrictions preventing the expected signature from matching the message signature when the message signature is submitted out of compliance with the set of key-use restrictions.

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

each obtained key is derived based at least in part on a corresponding restriction set for the obtained key; and

the set of key-use restrictions includes at least a union of the restriction sets for the obtained keys.

3. The computer-implemented method of claim 1, wherein the operation is a commutative operation.

4. The computer-implemented method of claim 1, wherein each key of the key-holder key set is derived from a common key.

5. The computer-implemented method of claim 1, wherein the expected signature matching the message signature is requisite on the message submitted in connection with the message signature being in compliance with the set of key-use restrictions.

6. The computer-implemented method of claim 1, wherein the function is based at least in part on a cryptographic hash function.

7. A signature verification system, comprising:

one or more processors; and

memory including instructions that, when executed by one or more processors of a computer system, cause the computer system to;

obtain a key-holder key set comprising a key for each key holder of a plurality of key holders, each obtained key having been derived based at least in part on a key-holder key for a corresponding key holder and a set of key-use restrictions;

calculate, by at least inputting into a function the set of key-use restrictions and a result of performing an operation on the key-holder set, a signing key;

generate, based at least in part on the signing key, an expected signature for a message submitted in connection with a message signature; and

transmit an electronic message that indicates whether the expected signature matches the message signature, the electronic message being usable to evaluate whether access to one or more computing resources is permitted, the set of key-use restrictions preventing the expected signature from matching the message signature when the message signature is submitted out of compliance with the set of key-use restrictions.

8. The signature verification system of claim 7, wherein:

each key of the key-holder key set is derived based at least in part on a corresponding set of one or more specialization parameters; and

the instructions further include instructions that cause the computer system to compute whether the message signature is valid by causing the computer system to;

calculate, based at least in part on the key-holder key set and the corresponding sets of one or more specialization parameters, the expected signature; and

determine whether the expected signature matches the message signature.

9. The signature verification system of claim 8, wherein:

the instructions that cause the computer system to compute whether the message signature is valid further include instructions that cause the computer system to determine whether the message complies with the corresponding sets of one or more specialization parameters; and

the instructions further cause the computer system to cause one or more actions to be taken based at least in part on whether the message signature is valid and whether the message complies with the corresponding sets of one or more specialization parameters.

10. The signature verification system of claim 8, wherein the instructions that cause the computer system to calculate the expected signature include instructions that cause the computer system to input a combination of the key-holder key set and an encoding of the corresponding sets of one or more specialization parameters into a function based at least in part on a cryptographic hash function.

11. The signature verification system of claim 10, wherein the instructions further include instructions that cause the computer system to

calculate the combination of the key-holder key set in a manner by which ordering the keys within the key-holder key set is unnecessary.

12. The signature verification system of claim 7, wherein the instructions further include instructions that cause the computer system to cause one or more actions to be taken based at least in part on whether the message signature is valid, wherein the one or more actions to be taken at least include causing performance of a request encoded by the message.

13. The signature verification system of claim 7, wherein the instructions that cause the computer system to obtain the key-holder key set include instructions that cause the computer system to obtain at least one key from the key-holder key set from a computer system that lacks access to at least one other key in the key-holder key set.

14. A non-transitory computer-readable storage medium having stored thereon instructions that, when executed by a computer system, cause the computer system:

obtain a key-holder key set comprising a key for each key holder of a plurality of key holders, each obtained key having been derived based at least in part on a key-holder key for a corresponding key holder and a set of key-use restrictions;

calculate, by at least inputting into a function the set of key-use restrictions and a result of performing an operation on the key-holder set, a signing key;

generate, based at least in part on the signing key, an expected signature for a message submitted in connection with a message signature; and

transmit an electronic message that indicates whether the expected signature matches the message signature, the electronic message being usable to evaluate whether access to one or more computing resources is permitted, the set of key-use restrictions preventing the expected signature from matching the message signature when the message signature is submitted out of compliance with the set of key-use restrictions.

15. The non-transitory computer-readable storage medium of claim 14, wherein the set of key-use restrictions comprises one or more restrictions for each of the keys in the key-holder key set.

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

the instructions that cause the computer system to obtain the key-holder key set include instructions that cause the computer system to derive, based at least in part on a key shared with another computer system, at least one key in the key-holder key set.

17. The non-transitory computer-readable storage medium of claim 16, wherein the instructions that cause the computer system to derive the one at least one key in the key-holder set include instructions that cause the computer system to at least compute a value for a function based at least in part on the key shared with the other computer system.

18. The non-transitory computer-readable storage medium of claim 14, wherein the instructions that cause the computer system to obtain the key-holder key set include instructions that cause the computer system to obtain at least one of the keys in the key-holder key set from a computer system that lacks access to another of the keys in the key-holder key set.

19. The non-transitory computer-readable storage medium of claim 14, wherein the instructions that cause the computer system to calculate the signing key includes instructions that cause the computer system to input a combination of the key-holder key set into a function with the set of key-use restrictions, the combination being based at least in part on a commutative operation on the key-holder key set.