Key derivation techniques

• US 9,197,409 B2
• Filed: 09/29/2011
• Issued: 11/24/2015
• Est. Priority Date: 09/29/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roth, Gregory B., Behm, Bradley Jeffery, Crahen, Eric D., Ilac, Cristian M., Fitch, Nathan R., Brandwine, Eric Jason, O'Neill, Kevin Ross
• Primary Examiner(s): TRAN, ELLEN C
• Application Number:
  US13/248,973
• Publication Number:
  US 20130086663A1
• Time in Patent Office: 1,517 Days
• Field of Search: 726/7, 713/155, 713/159, 713/168
• US Class Current: 1/1
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 2221/2115 Third party
• CPC Class Codes: H04L 63/0884 by delegation of authentication, e.g. a proxy authenticates an entity to be authenticated on behalf of this entity vis-à-vis an authentication entity
• CPC Class Codes: H04L 63/126 the source of the received data
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/088 Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068
• 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 that, as a result of being used to generate the keys, renders the generated keys usable for a smaller scope of uses than the secret credential. Further, key generation may involve multiple invocations of a function where each of at least a subset of the invocations of the function results in a key that has a smaller scope of permissible use than a key produced from a previous invocation of the function. Generated keys may be used as signing keys to sign messages. One or more actions may be taken depending on whether a message and/or the manner in which the message was submitted complies with restrictions of the a key'"'"'s use.

Claims

1. A computer-implemented method of authentication for providing access to one or more computing resources of a computing resource provider, the one or more computing resources of the computing resource provider being part of a logical grouping of computing resources in a key zone of a plurality of key zones, the method comprising:

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

receiving, by the one or more computer systems, a message and a signature of the message from an authenticating party;

generating, by the one or more computer systems and based at least in part on the received message, an expected signature by at least invoking a hash-based message authentication code function multiple times such that;

at least one invocation of the hash-based message authentication code function involves an input to the hash-based message authentication code function that is based at least in part on a secret credential shared with the authenticating party, the secret credential being received from a central key authority and corresponding to the key zone; and

at least another invocation of the hash-based message authentication code function involves a result from a previous invocation of the hash-based message authentication code function as an input to the hash-based message authentication code function;

determining, by the one or more computer systems, whether the received signature matches the expected signature; and

taking, by the one or more computer systems, when determined that the received signature matches the expected signature, one or more actions for which authentication of the received message is required.

2. The computer-implemented method of claim 1, wherein one or more of the multiple invocations is performed prior to receiving the message.

3. The computer-implemented method of claim 1, wherein the secret credential is usable by the authenticating party for a set of uses requiring authentication based at least in part on the secret credential and wherein at least one of the multiple invocations produces a key usable for a subset of the uses that is smaller than the set of uses.

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

the one or more computer systems include at least a first computer system in a first geographic region and a second computer system in second geographic region;

wherein at least one of the multiple invocations produces a key usable in the first geographic region and unusable in the second geographic region; and

wherein the key usable only in the first geographic region was used by the authenticating party to generate the signature.

5. The computer-implemented method of claim 1, wherein the input to the hash-based message authentication code function that is based at least in part on the secret credential is different from the secret credential.

6. The computer-implemented method of claim 1, wherein at least one invocation of the multiple invocations of the hash-based message authentication code includes inputting, into the hash-based message authentication code function information that, as a result of the information'"'"'s input into the hash-based message authentication code function, limits a scope of services accessible by submission of one or more messages signed with a signing key produced by at least one of the multiple invocations.

7. The computer-implemented method of claim 1, wherein at least one invocation of the multiple invocations of the hash-based message authentication code includes inputting, into the hash-based message authentication code function information that, as a result of the information'"'"'s input into the hash-based authentication code function, limits an amount of time a signing key produced by at least one of the multiple invocations is usable to sign messages that are acceptable as valid by the one or more computer systems.

8. A computer-implemented method of authenticating access to one or more computing resources of a computing resource provider, the one or more computing resources of the computing resource provider being part of a logical grouping of computing resources in a key zone of a plurality of key zones, comprising:

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

generating, by the one or more computer systems and based at least in part on a received message, an expected signature by at least performing multiple invocations of a set of one or more functions such that at least one invocation involves a result from a first function from the set of one or more functions as an input to a second function of the set of one or more functions, the result being based at least in part on a secret credential shared with the authenticating party, the second credential being obtained from a central key authority and being associated with the key zone;

determining, by the one or more computer systems, whether a signature received in connection with the message matches the expected signature; and

taking, by the one or more computer systems, when determined that the received signature matches the expected signature, one or more actions for which authentication of the received message is required.

9. The computer-implemented method of claim 8, wherein the first function and second function are the same function.

10. The computer-implemented method of claim 8, wherein the first function and second function are different functions.

11. The computer-implemented method of claim 8, wherein at least one of the first function and second function is a symmetric message authentication function.

12. The computer-implemented method of claim 8, wherein the result is obtained by at least inputting information based at least in part on the secret credential into the first function.

13. The computer-implemented method of claim 8, wherein at least one of the first function and second function is a hash based message authentication function.

14. The computer-implemented method of claim 8, wherein generating the expected signature includes inputting to at least one of the first function and second function information that, as a result of the input of the information into the function, prevents a signing key produced from at least one of the multiple invocations from being used in one or more ways.

15. The computer-implemented method of claim 8, wherein one or more of the multiple invocations includes performing Hash-Based Message Authentication Code (HMAC).

16. The computer-implemented method of claim 8, wherein the signature was produced by invoking the function multiple times in the same manner as to generate the expected signature.

17. The computer-implemented method of claim 8, wherein a subset of the one or more computer systems that verifies the expected signature lacks access to the secret credential.

18. A computer system for authentication, comprising:

one or more processors; and

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

obtain a result of an algorithm used to process at least a first input based at least in part on a credential shared with an authenticating party, the secret credential corresponding to a grouping of computing resources in a key zone of a plurality of key zone;

apply the algorithm to input based at least in part on the obtained result and input based at least in part on information from an authenticating party to generate a second result;

determine whether the second result matches a received signature from the authenticating party; and

take one or more actions as a result of determining that the second result matches the received signature.

19. The system of claim 18, wherein the algorithm includes invocation of a hash function.

20. The system of claim 18, wherein obtaining the result includes receiving information that electronically encodes the result from another system.

21. The system of claim 18, wherein obtaining the result includes calculating the result.

22. The system of claim 18, wherein the first input based at least in part on a credential shared with the authenticating party is produced by multiple applications of the algorithm, each application of at least a subset of the multiple applications of the algorithm involving different input.

23. The system of claim 22, wherein each application of the at least one subset of the multiple applications of the algorithm results in a different key usable for authentication for a different set of activities.

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

obtain a signing key that is based at least in part on multiple inputs for a process involving one or more invocations of a function, at least one input of the multiple inputs being based at least in part on a secret credential shared with an authenticator computing device, the secret credential corresponding to one or more computing resources of a key zone of a plurality of key zones;

generate a signature for a message by at least inputting the obtained signing key into the function; and

submit the generated signature to the authenticator computing device in connection with the message to enable the authenticator computing device to determine, based at least in part on the shared credential, whether the signature is authentic and take one or more actions when the signature is determined to be authentic.

25. The non-transitory computer-readable storage medium of claim 24, wherein:

the function uses at least two inputs; and

the process includes using output of the function as one of the inputs to the function multiple times.

26. The non-transitory computer-readable storage medium of claim 25, wherein the process further includes, when using output of the function as one of the inputs to the function multiple times, using different input as second input into the function each time.

27. The non-transitory computer-readable storage medium of claim 24, further including instructions that, when executed by the one or more processors of the computer system, cause the computer system to:

obtain the multiple inputs from one or more external information sources; and

perform the process to generate the signing key.

28. The non-transitory computer-readable storage medium of claim 24, further including instructions that, when executed by the one or more processors of the computer system, cause the computer system to:

input at least the signing key into the function to generate a second signing key, wherein both the signing key and the second signing key are usable for authentication with a computer system that includes the authenticator computing device.

29. The non-transitory computer-readable storage medium of claim 28, wherein the signing key is usable for authentication in connection with a first scope of authority and second signing key is usable for a second scope of authority that is less than the first scope of authority.