PASSWORD-BASED AUTHENTICATION

• US 20150341335A1
• Filed: 05/22/2015
• Published: 11/26/2015
• Est. Priority Date: 05/23/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Camenisch, Jan L., Lehmann, Anja, Neven, Gregory
• Granted Patent: US 9,537,658 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/40 by quorum, i.e. whereby two or more security principals are required
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 63/0876 based on the identity of the terminal or configuration, e.g. MAC address, hardware or software configuration or device fingerprint
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• 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

Abstract

A password authentication system includes an access control server configured to control access by a user computer to a resource dependent on authentication of user passwords associated with user IDs. The system further includes a plurality of authentication servers, storing respective secret values. For each user ID, the access control server stores a first ciphertext produced by encrypting the user password associated with that ID using a predetermined algorithm dependent on the secret values. In response to receipt of a user ID and an input password, the access control server communicates with the plurality of authentication servers to implement password authentication, requiring use of the secret values, in which a second ciphertext is produced by encrypting the input password using said predetermined algorithm. The access control server compares the first and second ciphertexts to determine whether the input password equals the user password to permit access to the resource.

Claims

1. A system comprising:

an access control server configured to communicate with user computers via a network and control access by the user computers to a resource in dependence on authentication of user passwords associated with respective user IDs; and

a plurality n of authentication servers configured to store respective secret values and communicate with the access control server via the network;

wherein the access control server is further configured to store, for each said user ID, a first ciphertext produced by encrypting a user password associated with a user ID using a predetermined algorithm dependent on said secret values; and

wherein, in response to receipt from a user computer of a received user ID and an input password, the access control server is further configured to communicate with a plurality k≦

n of authentication servers to implement a password authentication protocol, requiring use by the plurality k of authentication servers of the respective secret values, in which a second ciphertext is produced by encrypting the input password using said predetermined algorithm, and the access control server is further configured to use the first and second ciphertexts to determine whether the input password equals the user password for the received user ID to permit access to the resource by the user computer.

2. The system as claimed in claim 1, wherein, in response to initial input of said user password and associated user ID in a setup operation, the access control server is further configured to communicate with the plurality n of authentication servers to implement a password setup protocol, comprising generation of said first ciphertext for the user ID, and store the first ciphertext at the access control server, to permit subsequent implementation of said password authentication protocol for the user ID.

3. The system as claimed in claim 1, wherein:

the first ciphertext comprises first pseudorandom values, each of which encrypts, via a pseudorandom function, a secret value of a respective authentication server and an initial pseudorandom value;

the initial pseudorandom value encrypts, via said pseudorandom function, the user password for the respective user ID; and

the access control server is further configured to communicate with a plurality k=n of authentication servers to implement the password authentication protocol.

4. The system as claimed in claim 3, wherein the access control server is further configured to store a further secret value and wherein said initial pseudorandom value encrypts the further secret value via the pseudorandom function.

5. The system as claimed in claim 3, wherein the initial pseudorandom value encrypts, via said pseudorandom function, the user ID associated with the user password encrypted therein.

6. The system as claimed in claim 3, wherein to implement said password authentication protocol:

the access control server is further configured to use the input password to produce a test pseudorandom value, which corresponds to said initial pseudorandom value, and send the test pseudorandom value to each of the plurality n of authentication servers;

each of the plurality n of authentication servers are further configured to use the test pseudorandom value to produce a respective server pseudorandom value, which corresponds to a first pseudorandom value, and send the server pseudorandom value to the access control server; and

the access control server is further configured to produce the second ciphertext from the server pseudorandom values, and compare the first and second ciphertexts to determine whether the input password equals the user password for the received user ID.

7. The system as claimed in claim 3, wherein, in the password authentication protocol:

the access control server is further configured to send the received user ID to each of the plurality n of authentication servers; and

each of the plurality n of authentication servers are further configured to implement a throttling mechanism for each user ID.

8. The system as claimed in claim 3, wherein, to implement said password setup protocol in response to said initial input:

the access control server is further configured to produce the initial pseudorandom value and send the initial pseudorandom value to each of the plurality n of authentication servers;

each of the plurality n of authentication servers are further configured to use the initial pseudorandom value to produce a respective first pseudorandom value and send the first pseudorandom values to the access control server; and

the access control server is further configured to produce the first ciphertext from the first pseudorandom values.

9. The system as claimed in claim 8, wherein the first ciphertext comprises a modulo-2 sum of the first pseudorandom values.

10. The system as claimed in claim 9, wherein:

each of the first pseudorandom values comprise a modulo-2 sum of second and third pseudorandom values;

the second pseudorandom value encrypts said initial pseudorandom value via said pseudorandom function; and

the third pseudorandom value encrypts, via said pseudorandom function, said secret value of the respective authentication server and the user ID associated with the user password encrypted in said initial pseudorandom value.

11. The system as claimed in claim 10, wherein the second pseudorandom value encrypts, via said pseudorandom function, a server ID for said respective authentication server.

12. The system as claimed in claim 10, wherein the access control server and each of the plurality n of authentication servers are further configured to implement an update protocol, wherein:

the authentication server is further configured to update the further secret value to a new secret value and use the new secret value to produce an updated pseudorandom value which corresponds to said third pseudorandom value;

the plurality n of authentication servers are further configured to produce an update value, comprising a modulo-2 sum of the updated pseudorandom value and the third pseudorandom value, and send the update value to the access control server; and

the access control server is further configured to update the first ciphertext by producing a modulo-2 sum of the first ciphertext and the update value.

13. The system as claimed in claim 1, wherein:

the first ciphertext is produced using a predetermined homomorphic encryption algorithm for encrypting the user password under a public key of a cryptographic key-pair; and

the secret values of the plurality n of authentication servers comprise respective key-shares of a secret key of said cryptographic key-pair.

14. The system as claimed in claim 13, wherein to implement the password authentication protocol in response to receipt of a said user ID and input password:

the access control server is further configured to produce the second ciphertext from the input password using said homomorphic encryption algorithm;

the access control server is further configured to produce a test value by combining the second ciphertext and the first ciphertext for the received user ID such that, due to the homomorphism encryption algorithm, the test value decrypts to a predetermined value if the input password equals the user password associated with the user ID;

the access control server is further configured to send the test value to the plurality k of authentication servers;

each of the plurality k of authentication servers are further configured to use the respective key-share to produce a k decryption share dependent on the test value, and send the k decryption share to the access control server; and

the access control server is further configured to determine whether the input password equals the user password by determining from the k decryption shares whether the test value decrypts to said predetermined value.

15. The system as claimed in claim 14, wherein:

said homomorphic encryption algorithm comprises a threshold encryption algorithm which requires p<

n decryption shares for decryption; and

in the password authentication protocol, the access control server is further configured to send said test value to a plurality k=p of authentication servers.

16. The system as claimed in claim 14, wherein each of the plurality n of authentication servers are further configured to store the first ciphertext for each said user ID and, in the password authentication protocol:

the access control server is further configured to send the received user ID to the plurality n of authentication servers with said test value; and

each of the plurality n of authentication servers is configured to implement a throttling mechanism for each user ID.

17. The system as claimed in claim 14, wherein the access control server is further configured to produce the second ciphertext by applying said homomorphic encryption algorithm to a function of the input password.

18. The system as claimed in claim 17, wherein each of the plurality n of authentication servers are further configured to store the first ciphertext for each said user ID, and in the password authentication protocol:

the access control server is further configured to generate a cryptographic proof for proving that said test value comprises the second ciphertext and the first ciphertext for the received user ID;

the access control server is further configured to send the received user ID and said cryptographic proof to the plurality k of authentication servers with said test value; and

each of the plurality k of authentication servers are further configured to validate said cryptographic proof before producing said k decryption share.

19. The system as claimed in claim 14, wherein said test value decrypts to unity if the input password equals the user password associated with said user ID and, in the password authentication protocol:

each of the plurality k of authentication servers are further configured to produce a randomized value, comprising the test value raised to a power of a respective random exponent, and send the randomized value to the access control server;

the access control server is further configured to forward the randomized value received from each of the plurality k of authentication servers to each of a plurality (k−

1) of other authentication servers;

each of the plurality k of authentication servers are further configured to combine a set of randomized values to produce a randomized ciphertext and use respective key-shares to produce said k decryption share from the randomized ciphertext; and

the access control server is further configured to determine whether the input password equals the user password by determining from the k decryption shares whether the randomized ciphertext decrypts to unity.

20. The system as claimed in claim 16, wherein:

the access control server is further configured to store the k decryption shares produced from said randomized ciphertext by respective authentication servers in the password authentication protocol for a said user ID; and

prior to blocking the user ID due to said throttling mechanism in a subsequent implementation of the password authentication protocol for the user ID, an authentication server is further configured to communicate with the access control server to implement an unblock protocol wherein the access control server is further configured to send said k decryption shares to the authentication server, and the authentication server is further configured to determine from the k decryption shares whether said randomized ciphertext decrypts to unity.

21. The system as claimed in claim 2, wherein to implement said password setup protocol in response to said initial input, the access control server is further configured to produce the first ciphertext from the user password using said homomorphic encryption algorithm.

22. The system as claimed in claim 21, wherein in said password setup protocol, the access control server is further configured to send the first ciphertext to the plurality n of authentication servers with the user ID associated with the user password.

23. The system as claimed in any one of claim 13, wherein the plurality n of authentication servers are further configured to implement a share renewal protocol for updating the key-shares of said secret key.

24. A server comprising memory, a communications interface, and control logic configured to implement an access control server of the system as claimed in claim 1, wherein said memory stores said first ciphertext for each user ID in use.

25. A server comprising memory, a communications interface, and control logic configured to implement an authentication server of the system as claimed in claim 1, wherein said memory stores said secret value of the authentication server in use.

26. A computer program comprising program code configured to cause a computer to implement the control logic of the server as claimed in claim 24.

27. A computer program comprising program code configured to cause a computer to implement the control logic of the server as claimed in claim 25.

28-30. -30. (canceled)

31. A computer program product configured to control access by user computers to a resource in dependence on authentication of user passwords, associated with respective user IDs, at an access control server configured to communicate via a network with the user computers and a plurality n of authentication servers, the computer program product comprising a computer readable storage medium having program instructions, the program instructions readable by an access control server which, when executed, causes the access control server to:

for each said user ID, store a first ciphertext produced by encrypting a user password associated with a user ID using a predetermined algorithm dependent on said secret values;

in response to receipt from a user computer of a received user ID and an input password, communicate with a plurality k≦

n of authentication servers to implement a password authentication protocol, requiring use by the plurality k of authentication servers of the respective secret values, in which a second ciphertext is produced by encrypting the input password using said predetermined algorithm;

at the access control server, use the first and second ciphertexts to determine whether the input password equals the user password for the received user ID; and

permit access to the resource by the user computer if the input password equals the user password.