Decentralized verification in a distributed system

• US 9,258,118 B1
• Filed: 06/25/2012
• Issued: 02/09/2016
• Est. Priority Date: 06/25/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roth, Gregory B., Baer, Graeme D.
• Primary Examiner(s): KIM, TAE K
• Application Number:
  US13/532,768
• Time in Patent Office: 1,324 Days
• Field of Search: 713182-186, 380277-281
• US Class Current: 1/1
• CPC Class Codes: H04L 9/0863 involving passwords or one-time passwords network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/0872 using geo-location information, e.g. location data, time, relative position or proximity to other entities
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A credential, such as a password, for an entity is used to generate multiple keys. The generated keys are distributed to credential verification systems to enable the credential verification systems to perform authentication operations. The keys are generated such that access to a generated key allows for authentication with a proper subset of the credential verification systems. Thus, unauthorized access to information used by one authentication system does not, by itself, allow for successful authentication with other authentication systems.

Claims

1. A system for managing authentication credentials in a distributed computing environment, comprising:

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

one or more computing resources collectively having one or more processors and memory including executable instructions that, when executed by the one or more processors, cause the system to, for each password of a plurality of passwords, at least;

derive, based at least in part on the password and a first salt value, a preliminary key;

for each key-use zone of a plurality of key-use zones;

derive a key hash value based at least in part on a second salt value and a key-derivation parameter specific to the key-use zone, the key hash value being a hash value derived based at least in part on a key;

generate a verification key based at least in part on the preliminary key and the key hash value; and

configure a password verification system for the key-use zone to use the verification key to authenticate a computer system having access to the password without requiring the computer system to provide the password to the password verification system.

2. The system of claim 1, wherein the first salt value and the second salt value correspond to the password.

3. The system of claim 1, wherein:

the key-use zones are zones of an organization controlling a plurality of data processing facilities, each data processing facility of the plurality of data processing facilities being located in a different geographic location; and

each key-use zone of the plurality of key-use zones comprises a subset of the data processing facilities.

4. The system of claim 1, wherein:

the verification key is further generated based at least in part on a time-dependent key-derivation parameter; and

successful authentication of the computer system relies upon the computer system providing proof of access to the password, wherein the proof was generated based at least in part on the time-dependent key-derivation parameter.

5. The system of claim 1, wherein generating the preliminary key includes computing a value of at least one of Password-Based Key Derivation Function Two or bcrypt.

6. The system of claim 1, wherein generating the verification key includes inputting at least two inputs into a hash function, one of the at least two inputs being based at least in part on the preliminary key and another of the at least two inputs being based at least in part on the key-derivation parameter.

7. A computer-implemented method for authentication credential management, comprising:

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

for each key-use zone of a plurality of key-use zones;

generating, using the one or more computer systems, a verification key for the key-use zone based at least in part on a credential, a first salt that corresponds to the credential, a second salt that corresponds to the credential, and a key-derivation parameter specific to the key-use zone by at least;

generating, using the one or more computer systems, based at least in part on the credential and the first salt, a preliminary key; and

generating, using the one or more computer systems, based at least in part on the preliminary key, the second salt, and the key-derivation parameter, the verification key; and

causing, using the one or more computer systems, an authentication system for the key-use zone to be configured to perform authentication operations using the verification key.

8. The computer-implemented method of claim 7, wherein each key-use zone of the plurality of key-use zones corresponds to a different geographic area.

9. The computer-implemented method of claim 7, wherein causing the authentication system to be configured to perform the authentication operations includes transmitting, using the one or more computer systems, the verification key from the one or more computer systems to the authentication system.

10. The computer-implemented method of claim 7, wherein:

generating the verification key is further based at least in part on a time parameter that corresponds to a time period; and

the method further comprises causing, using the one or more computer systems, the authentication system for the key-use zone to be reconfigured to perform authentication operations using a different verification key instead of the verification key at a time after expiration of the time period.

11. The computer-implemented method of claim 7, wherein the credential is a password.

12. The computer-implemented method of claim 7, wherein:

each key-use zone of the plurality of key-use zones corresponds to a plurality of different services; and

generating the verification key is further based at least in part on an service parameter corresponding to one or more of the services for which the authentication operations are to be performed.

13. A computer system, comprising:

one or more processors; and

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

obtain information specific to an entity;

use the information specific to the entity to generate a set of verification keys comprising a verification key for each key-use zone of multiple different key-use zones, the verification key for a corresponding key-use zone generated based at least in part on a first salt, a second salt, and information specific to the corresponding key-use zone by causing the computer system to;

generate, based at least in part on the information specific to the entity and the first salt, a preliminary key; and

generate, based at least in part on the preliminary key, the second salt, and the information specific to the corresponding key-use zone, the verification key; and

provide the verification keys of the set of verification keys for use in authenticating the entity for corresponding key-use zones.

14. The computer system of claim 13, wherein:

the instructions that cause the computer system to obtain the information specific to the entity include instructions that cause the computer system to generate, based at least in part on a credential specific to the entity, a preliminary key; and

the instructions that cause the computer system to generate the set of verification keys include instructions that cause the computer system to generate each of at least a subset of the verification keys based at least in part on the preliminary key.

15. The computer system of claim 13, wherein the instructions that cause the computer system to provide the verification keys for use in authenticating the entity for corresponding key-use zones include instructions that cause the computer system to transmit, across a network, a different generated verification key for the entity to each of a plurality of authentication systems, each authentication system of the plurality of authentication systems.

16. The computer system of claim 13, wherein:

at least two of the key-use zones correspond to geographically separated facilities; and

the instructions that cause the computer system to provide the verification keys include instructions that cause the computer system to provide each key-use zone of the at least two key-use zones a different verification key of the set of verification keys.

17. The computer system of claim 13, wherein:

the verification key for the corresponding key-use zone is generated further based at least in part on information different from the information specific to the corresponding key-use zone; and

the information different from the information specific to the corresponding key-use zone corresponds to a restriction on use of the verification key.

18. The computer system of claim 17, wherein the restriction corresponds to a time period during which the key is to be used for authenticating the entity.

19. 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:

determine information specific to a key-use zone of a plurality of key-use zones;

generate, based at least in part on a plurality of salts specific to an entity and the information specific to the key-use zone, a verification key by causing the computer system to at least;

generate, based at least in part on the information specific to the entity and a first salt of the plurality of salts, a preliminary key; and

generate, based at least in part on the preliminary key, a second salt of the plurality of salts, and the information specific to the key-use zone, the verification key; and

electronically prove access to secret information to an authentication system of the key-use zone using the verification key but without providing the secret information to the authentication system.

20. The computer-readable storage medium of claim 19, wherein the instructions that cause the computer system to electronically prove access to the secret information cause the computer system to:

generate a request;

generate an electronic signature of the request; and

transmit an electronic communication based at least in part on the electronic signature and the request to the authentication system.

21. The computer-readable storage medium of claim 19, wherein the instructions that cause the computer system to electronically prove access to the secret information cause the computer system to:

receive a challenge value from the authentication system;

generate a challenge response based at least in part on the verification key; and

provide the challenge response to the authentication system.

22. The computer-readable storage medium of claim 19, wherein the secret information is a password of the entity.

23. The computer-readable storage medium of claim 19, wherein the instructions include instructions that, when executed by one or more processors of a computer system, cause the computer system to further:

determine information specific to a different key-use zone of the plurality of key-use zones;

generate, based at least in part on the plurality of salts specific to the entity and the information specific to the different key-use zone, another verification key; and

electronically prove access to secret information to a different authentication system of the different key-use zone using the other verification key but without providing the secret information to the authentication system.