Systems, methods and software for remote password authentication using multiple servers

• US 20020067832A1
• Filed: 05/31/2001
• Published: 06/06/2002
• Est. Priority Date: 06/05/2000
• Status: Active Grant

• Current Assignee: Kinglite Holdings Inc.
• Original Assignee: Phoenix Technologies Limited (Pharaoh Acquisition LLC)
• Inventors: Jablon, David P.
• Granted Patent: US 7,139,917 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• 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/166 at the transport layer
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• 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/3257 using blind signatures
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps

Abstract

Systems, methods and software employ zero-knowledge password (ZKP) protocols to provide strong authentication using low-grade passwords that people can easily memorize. We describe protocols that enable multiple servers to verify a password, without providing any single server, client, or network attacker with the ability to validate guesses for the password off-line. Further improvements include removing dependency on a prior secure channel and client-stored keys or certificates, increasing performance without introducing new cryptographic assumptions, and better management of mistakes in password entry. To enroll, a user chooses a password and constructs a master key K composed of multiple shares. The master key may be used for a variety of purposes, such as encrypting the user'"'"'s private keys and other sensitive data. A set of random values {y₁, y₂, . . . y_N} is selected, and each share is computed as K_i=P^yi in a suitable finite group. Each y_i value is distributed to the i^th one of N servers. To authenticate, the client chooses a random secret x, and with each server, sends P^x, retrieves m_i=(P^x)^yi, and computes K_i=m_i^1/x. The client reconstructs K, performs a validation test on K, and uses K to decrypt a private digital signature key U. When the validation test succeeds, the client signs a message with U that contains P^x and optionally other values sent by the client based on incorrect passwords mistakenly entered by the same user in attempting to authenticate. Each server verifies the signed message to authenticate the user, and to forgive the user for some reasonable number of mistakes. With knowledge of valid messages, mistakes and all, the server fine-tunes the accounting of bad access attempts. No single server knows K, P, or any of the K_i shares, and no server receives sufficient information to mount a dictionary attack on K or P. Password security is maintained in a very simple model, requiring no previously secured or server-authenticated channel between the client and any servers. This model further prevents risks inherent in systems where people must authenticate servers, but don'"'"'t. Data protected by a small password, and no other keys, remains secret even against an enemy that compromises any, but not all, of two or more cooperating authentication servers.

Claims

1. A system that provides for remote password authentication comprising:

a client computer;

a plurality of authentication servers;

a network interconnecting the client computer and plurality of authentication servers;

software running on the client computer and plurality of authentication servers that cooperates to enter a password on the client, store a unique random value y_i on each of the servers, derive a group element (P) from the password, send a blinded password value (P^x) to the servers, retrieve blinded key shares (P^xyi) from the servers, unblind and combine the shares to create a master key (K_m), and decrypt encrypted private data on the client computer using the master key (K_m).

2. The system recited in claim 1 wherein the software operating on the client operates to validate the master key (K_m).

3. The system recited in claim 1 wherein the software operating on the client operates to decrypt encrypted private data using the master key (K_m).

4. The system recited in claim 2 wherein the software operating on the client operates to decrypt encrypted private data using the validated master key (K_m).

5. The system recited in claim 2 wherein the software operating on the client operates to send proof of the validated master key (K_m) and each blinded password value (P^X) to the servers.

16. The system recited in claim 1 wherein the software cooperates to:

maintain a count of bad login attempts, the number of recent amplifications, a list of recent P^x password amplification request values, and a list of timestamps associated with the list of recent password amplification request values on the server;

receives a blinded password (P^x) request

records the blinded password in a short-term list

checks a user account to see if it is locked;

creates a blinded key share (P^xyi); and

sends the blinded key share to the client computer if it is unlocked.

6. A method that provide for remote password authentication using a system comprising a client computer, a plurality of authentication servers, and a network interconnecting the client computer and plurality of authentication servers, the method comprising the steps of:

entering a password;

deriving group elements (P) from the password;

sending blinded password value (P^X) to the servers;

retrieving blinded key shares (P^xyi) from the servers;

unblinding and combining the shares to create a master key (K_m); and

decrypting encrypted private data on the client computer using the master key (K_m).

7. The method recited in claim 6 further comprising the step of validating the master key (K_m).

8. The method recited in claim 6 wherein the software operating on the client operates to decrypt encrypted private data using the master key (K_m).

9. The method recited in claim 7 further comprising the step of decrypting encrypted private data using the validated master key (K_m).

10. The method recited in claim 7 further comprising the step of sending proof of the validated master key (K_m) and each blinded password value (P^x) to the servers.

19. The method recited in claim 6 further comprising the steps of maintaining a count of bad login attempts, the number of recent amplifications, a list of recent P^x password amplification request values, and a list of timestamps associated with the list of recent password amplification request values on the server;

receiving a blinded password (P^x) request

recording the blinded password in a short-term list

checking a user account to see if it is locked;

creating a blinded key share (P_xyi); and

sending the blinded key share to the client computer if it is unlocked.

11. A computer program embodied on a computer-readable medium for enabling remote password authentication in a multiple-server system comprising a client computer, a plurality of authentication servers, and a network interconnecting the client computer and plurality of authentication servers, the computer program comprising:

a code segment that enters a password;

a data storage area that contains a unique random value yⁱ on each of the servers,

a code segment that derives a group element (P) from the password;

a code segment that sends blinded password value (P^x) to the servers;

a code segment that retrieves blinded key shares (P^XYi) from the servers;

a code segment that unblinds and combines the shares to create a master key (K_m); and

a code segment that decrypts encrypted private data on the client computer using the master key (K_m).

12. The computer program recited in claim 11 further comprising a code segment that validates the master key (K_m).

13. The computer program recited in claim 11 further comprising a code segment that decrypts encrypted private data using the master key (K_m)

14. The computer program recited in claim 12 further comprising a code segment that decrypts encrypted private data using the validated master key (K_m).

15. The computer program recited in claim 12 further comprising a code segment that sends proof of the validated master key (K_m) and the blinded password value (P^x) to the servers.

17. The system recited in claim 16 wherein the software:

records a timestamp value to note the time that the request was received;

periodically checks for stale requests which are determined when the difference between any timestamp value and the current time becomes greater than a specific period of time;

deletes corresponding password amplification request values and timestamps; and

increments the count of bad attempts.

18. The system recited in claim 16 wherein, when a successful login occurs, the software:

sends a value of Q_A, equal to the password raised to a random power, along with any prior values for Q_A from earlier runs in the same login session, to each server in an encrypted message; and

authenticates this message using the master key K_m.

20. The system recited in claim 19 wherein the software:

records a timestamp value to note the time that the request was received;

periodically checks for stale requests which are determined when the difference between any timestamp value and the current time becomes greater than a specific period of time;

deletes corresponding password amplification request values and timestamps; and

increments the count of bad attempts.

21. The method recited in claim 19 further comprising the steps of sending the value of Q_A, equal to the password raised to a random power, along with any prior values for Q_A from earlier runs in the same login session, to each server in an encrypted message;

and

authenticating this message using the master key K_m.

22. The computer program recited in claim 11 further comprising a code segment that:

maintains a count of bad login attempts, the number of recent amplifications, a list of recent P^x password amplification request values, and a list of timestamps associated with the list of recent password amplification request values on the server;

receives a blinded password (P^x) request

records the blinded password in a short-term suspect list

checks a user account to see if it is locked;

creates a blinded key share (P^xyi) if it is unlocked; and

sends the blinded key share to the client computer.

23. The computer program recited in claim 22 further comprising a code segment that:

records a timestamp value to note the time that the request was received;

periodically checks for stale requests which are determined when the difference between any timestamp value and the current time becomes greater than a specific period of time;

deletes corresponding password amplification request values and timestamps; and

increments the count of bad attempts.

24. The computer program recited in claim 22 further comprising a code segment that:

sends the value of Q_A, equal to the password raised to a random power, along with any prior values for Q_A from earlier runs in the same login session, to each server in an encrypted message; and

authenticates this message using the master key K_m.