Methods and apparatus for obscuring a valid password in a set of passwords in a password-hardening system

• US 9,230,092 B1
• Filed: 09/25/2013
• Issued: 01/05/2016
• Est. Priority Date: 09/25/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Juels, Ari
• Primary Examiner(s): Poltorak, Peter
• Application Number:
  US14/036,239
• Time in Patent Office: 832 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/46 by designing passwords or checking the strength of passwords
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226

Abstract

A password-hardening system comprises at least first and second servers. The first server is configured to store a plurality of sets of passwords for respective users with each such set comprising at least one valid password for the corresponding user and a plurality of chaff passwords for that user. The second server is configured to generate valid password indication information indicating for each of the sets which of the passwords in that set is a valid password. The valid password indication information comprises index values computed for respective ones of the password sets by the second server to identify respective valid passwords in the respective password sets. The second server may be further configured to compute the index values utilizing a keyed pseudorandom function, and to send the index values to the first server in association with respective values of a user number counter maintained in the second server.

Claims

1. A method comprising:

storing in a first server a plurality of sets of passwords for respective users with each such set comprising at least one valid password for the corresponding user and a plurality of chaff passwords for that user; and

generating in a second server valid password indication information indicating for each of the sets which of the passwords in that set is a valid password;

wherein the valid password indication information comprises index values that are computed for respective ones of the password sets by the second server and that identify respective valid passwords in the respective password sets;

wherein the second server conditions release of a given one of the index values to the first server on a result of a comparison of a user identifier with a value of a user number counter maintained in the second server;

wherein the given one of the index values is computed using the value of the user number counter;

wherein the user number counter indicates a current number of said users for which corresponding index values have been computed by the second server;

wherein, in conjunction with the conditioned release of the given one of the index values to the first server, the second server increments the user number counter; and

wherein the storing and generating are performed by at least one processing device.

2. The method of claim 1 wherein the second server computes the index values utilizing a keyed pseudorandom function.

3. The method of claim 2 wherein the keyed pseudorandom function is used to generate index values of the form:

c_x(i)→

{1,2, . . . k},

where iε

{0,1}^l is an l-bit user index and xε

{0,1}^l is an l-bit secret key, for a designated security parameter l, where k denotes the total number of passwords in the corresponding password set.

4. The method of claim 1 wherein the second server outputs index value c_x(i) for a given user u_i only when a current value of the user number counter is equal to i.

5. The method of claim 3 further comprising:

initializing the user number counter in the second server; and

randomly selecting the secret key in conjunction with the initializing.

6. The method of claim 1 wherein the second server computes the given one of the index values in response to a message received from the first server.

7. The method of claim 1 wherein the second server in response to a message received from the first server verifies that j=c_x(i) where j denotes an index of a received password for user u_i within the corresponding password set.

8. The method of claim 1 further comprising providing to a trusted third party information specifying an association between the user number counter value for the given index value and an identifier of the corresponding user u_i.

9. The method of claim 8 wherein the trusted third party comprises an access control system associated with a protected resource.

10. The method of claim 1 further comprising the steps of:

receiving a password from a user attempting to access a protected resource;

determining in the first server if the received password is in the set of passwords stored for the user;

if the received password is in the set of passwords stored for the user, determining in the second server if the received password is the valid password or one of the chaff passwords; and

if the received password is the valid password, granting access to the protected resource; and

if the received password is one of the chaff passwords, denying access to the protected resource and taking an appropriate remedial action in accordance with a specified policy.

11. The method of claim 1 wherein a given one of the sets of passwords stored in the first server for a user u_i is of the form:

W_i=(w_i,1,w_i,2, . . . ,w_i,k),

where k denotes the total number of passwords in the set W_i, a given one of the passwords w_i,j is a valid password p_i of user u_i, the remaining k−

1 passwords w_i,j are chaff passwords, and the valid password indication information comprises an index value denoting an index of the valid password p_i for user u_i in the set W_i.

12. The method of claim 11 wherein for a given received password having index j in the corresponding set W_i of passwords, the second server determines whether or not j is equal to the index value.

13. The method of claim 11 further comprising:

receiving a request from user u_i to change the corresponding valid password from p_i to p_i′

;

verifying that p_i=w_i,jε

W_i;

sending a message to the second server requesting that the second server verify that j=c_x(i);

responsive to the second server verifying that j=c_x(i), computing W_i′

=Gen(k, p_i′

) where Gen(•

) is a password set generation function, randomly reordering W_i′

so that p_i′

=w_i,j′

, and setting W_i←

W_i′

.

14. The method of claim 11 further comprising:

receiving a request to create an account for a user;

sending a message to the second server requesting computation of an index value for the user;

receiving an index value c_x(i) and a corresponding current value i of a user number counter from the second server; and

computing W_i=Gen(k, p) where Gen(•

) is a password set generation function and randomly reordering W_i so that p=w_i,cx(i)′

.

15. An article of manufacture comprising at least one non-transitory processor-readable storage medium having embodied therein one or more software programs, wherein the one or more software programs when executed by at least one processing device cause said at least one processing device:

to store in a first server a plurality of sets of passwords for respective users with each such set comprising at least one valid password for the corresponding user and a plurality of chaff passwords for that user; and

to generate in a second server valid password indication information indicating for each of the sets which of the passwords in that set is a valid password;

wherein the valid password indication information comprises index values that are computed for respective ones of the password sets by the second server and that identify respective valid passwords in the respective password sets;

wherein the second server conditions release of a given one of the index values to the first server on a result of a comparison of a user identifier with a value of a user number counter maintained in the second server;

wherein the given one of the index values is computed using the value of the user number counter;

wherein the user number counter indicates a current number of said users for which corresponding index values have been computed by the second server; and

wherein, in conjunction with the conditioned release of the given one of the index values to the first server, the second server increments the user number counter.

18. The article of manufacture of claim 15 wherein the second server computes the index values utilizing a keyed pseudorandom function.

19. The article of manufacture of claim 18 wherein the keyed pseudorandom function is used to generate index values of the form:

c_x(i)→

{1,2, . . . k},

where iε

{0,1}^l is an l-bit user index and xε

{0,1}^l is an l-bit secret key, for a designated security parameter l, where k denotes the total number of passwords in the corresponding password set.

16. An apparatus comprising:

at least one processing device comprising a processor coupled to a memory;

wherein said at least one processing device comprises;

a first server configured to store a plurality of sets of passwords for respective users with each such set comprising at least one valid password for the corresponding user and a plurality of chaff passwords for that user; and

a second server configured to generate valid password indication information indicating for each of the sets which of the passwords in that set is a valid password;

wherein the valid password indication information comprises index values that are computed for respective ones of the password sets by the second server and that identify respective valid passwords in the respective password sets;

wherein the second server conditions release of a given one of the index values to the first server on a result of a comparison of a user identifier with a value of a user number counter maintained in the second server;

wherein the given one of the index values is computed using the value of the user number counter;

wherein the user number counter indicates a current number of said users for which corresponding index values have been computed by the second server; and

wherein, in conjunction with the conditioned release of the given one of the index values to the first server, the second server increments the user number counter.

17. The apparatus of claim 16 wherein the first and second servers are implemented on respective distinct ones of a plurality of processing devices.

20. The apparatus of claim 16 wherein the second server computes the index values utilizing a keyed pseudorandom function.