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

System, method and software for remote password verification using multiple servers

BACKGROUND The present invention generally relates to computer security, and more specifically, to systems, methods, and software that provide remote password authentication using multiple servers.

Password-based authentication is the basis of most personal authentication systems. Even when supplemented with portable tokens, smart cards, and biometrics, easy-to-remember passwords are often still the main core factor used to establish personal identity in computer transactions. The type of low-level password that people can easily remember is a particularly serious problem for many other security systems. In order to adapt to low-level passwords, a zero-knowledge password protocol was developed to eliminate network threats. However, the remaining problem is how to prevent attacks on the password verification data when the data is useful to an adversary.

In a typical password system, the server saves verification data for the password, which may be a copy of the password itself. In the UNIX system, for the sake of special security, the authentication data is an iterative one-way function of the password, and the authentication data is usually stored in a file. The file is often further protected so that unprivileged users and programs cannot access it. A traditional UNIX password attack is that the attacker manages to have access to a file of password verification data, and runs a password cracking tool against it to determine or "decipher" as many passwords as possible. Password cracking is simply applying a one-way function to a list of candidate passwords. When the output of the one-way function matches the verification data, the attacker knows that he has guessed the correct password. This attack can be optimized to try the most common or most likely password first, so that as many passwords as possible can be deciphered in a specified period of time.

One purpose is to use the simplest possible security model in a password-based client/server authentication system-that is, to use as few assumptions as possible to reduce the threat of password-based server-based attacks as much as possible. The purpose is to prevent exposure of passwords even in the face of all unconstrained attacks on the server. In this model, it is assumed that the attacker has the ability to change the server software, access all the data available on that server and control the use of that server while verifying legitimate and unsuspected users.

In order to achieve this goal, it is obvious that no more than one machine needs to be used. In any single machine system, by simulating the actions of the user, the person who can access the user's password verification data or can access any encrypted password data has enough information to perform an unconstrained offline brute force attack. The problem is specifically how to split the password verification data in two or more servers in order to eliminate this risk. A single server should not be able to launch an offline brute force attack.

Public key cryptography is now gradually being recognized as the most important tool for secure personal electronic transactions. It is hoped that personal digital signatures have a wide range of applications. However, the big problem is how to protect and manage the user's private key. Putting it on the client machine may slightly encrypt the password, which is an undesirable security risk. It is considered foolish to put unchanging and decipherable password data on a client whose security is often known to be difficult to manage. In addition, in a model where multiple users can share a single machine, it is impractical to require local storage of user credentials.

One user authentication solution for so-called "roaming" users is to save the user's personal certificates stored on a remote server and use password-based authentication to retrieve these certificates. The strong zero-knowledge cryptography (ZKP) protocol addresses many of the threats in these solutions by eliminating network-based brute force attacks while eliminating the dependence on other stored keys and certificates on the client. The ZKP protocol is also important for multiple server scenarios.

Discuss two models for safe roaming systems with multiple servers: the strong model and the weaker model. In these two models, it is assumed that the attacker can access a copy of the password verification data, and at the same time has the ability to perform calculations in a reasonably long period of time (reasonable length means unconstrained, but within the limits of computational feasibility. Arbitrarily long calculations It can decipher arbitrarily large public keys. As in most cryptographic methods, some practical upper bounds on the time and power available to a potential attacker are assumed, and the corresponding security minimum reasonable size for the key may be determined.) In the weaker model, it is assumed that the attacker has accessed a copy of the server's persistent data, but cannot hinder the operation of the running server.

In the strong model, the method must maintain the security of the key, even in the face of the total active compromise of all servers except one authentication server. It is assumed that an attacker can modify the server software and access all useful information on the service while verifying valid users. The strong model is simpler and therefore the best. It is also stronger than earlier models used for similar systems that assume the existence of existing secure channels.

In all these models, by limiting the number of invalid access attempts allowed, each server can protect itself from unconstrained online attacks. There are many useful ways to enforce these restrictions. The preferred embodiment of the present invention also includes features that help the server better calculate reasonable errors made in password input.

The purpose of the roaming system is to allow mobile users to safely access and use their private keys to perform public key cryptographic operations. Mobility in a broad sense involves and includes the use of personal workstations and other people's workstations without having to store keys there, the use of public telephone terminals, and the use of modern handheld wireless network equipment. It is expected to provide users with password verification and access to private keys from anywhere, while reducing the chance of an opponent stealing or deciphering the password to obtain these keys.

Smart cards are expected to solve the key storage problem for roaming users, but the solution requires the configuration of the card and the installation of a card reader. The tendency of people to sacrifice security for convenience has proven to be an obstacle to widespread use of solutions requiring additional hardware. This is a motivation for software-based roaming agreements.

As used herein, roaming protocols involve secure password-based protocols for remote retrieval of private keys from one or more authentication servers. Using only an easy-to-remember password, without using other stored user credentials, the user authenticates to the authentication server and retrieves her private key for temporary use on any acceptable client. The customer uses the password for one or more transactions, and then deletes the key and any local data related to the key.

Here, the client representing a specific user is called Alice and the credential server is generally called Bob, or Bi respectively, using gender-specific pronouns for the female client and her male server.

The concept of a "roaming" system is very related to the authentication server. The SPX LEAF system published by J. Tardo and K. Alagapan in "SPX: Global Authentication Using Public Key Certificates", Proc.1991 IEEE Computer Society Symposium onSecurity and Privacy, 1991, pp.232-244 introduced the use of server authentication channels To transmit the password to the authentication server used for verification, and perform the subsequent search and decrypt the roaming agreement of the user's private key. The authentication server protects itself by limiting the speculative attacks it can detect, and the protocol prevents inconspicuous offline speculation of passwords.

When the authentication server can determine whether the password guess is correct, it can prevent or delay further exchanges after a predetermined failure threshold.

Password only protocols are another important related area. By S. Bellovin and M. Merritt in "Encrypted Key Exchange: Password-based protocols secure against dictionary attacks", Proceedings of the IEEE Symposium on Research in Security and Privacy, the EKE protocol published in May 1992 passed the security verification without requiring the previous The password on the insecure network of the server authentication action introduces the concept of a secure only password protocol. A series of other methods with similar purposes have been developed, including by L. Gong, TMALomas, RMNeedham, and JHSaltzer in "ProtectingPoorly Chosen Secret from Guessing Attacks", IEEE Journal onSelected Areas in Communications, vol, 11, no.5, June 1993 , Pp.648-656 and by L. Gong in "Increasing Availability and Security of anAuthentication Service", IEEE Journal on Selected Areas in Communications, vol.11, no.5, June 1993, "secretpublic key" method published by D. Jablon in "Strong password-onlyauthenticated key exchange" , ACM Computer CommunicationsReview, vol.26, no.5, October 1996, pp.5-26, http://www.IntegritvSciences.com/links.htm\#Jab96 discussed the SPEKE method, by S.Lucks in "Open Key Exchange: How to Defeat DictionaryAttacks Without Encrypting Public Keys", The Security ProtocolWorkshop'97, Ecole Normale The OKE method described by Superieure, April 7-9, 1997, was developed by T. Wu in "The Secure Remote Password Protocol", Proceedings of 1998 Network and Distributed System Security Symposium, Internet Society, January 1998, pp. The key model in the theoretical study of the growth of the subject of other methods, such as S. Halev and HoKrawczyk in "Public-key cryptography and password protocols", Proceddings of the Fifth ACM Conference on Computer and Communications Security, 1998, MKBoyarasky in "Public-key Cryptography and Password Protocols: The Multi-UsersCase", Proc.6thACM Conference on computer and Communications Security, Novemberl-4, 1999, singapore, V. Boyko, P. marc Kenzie and S. Patel in "Provably Secure Password Authertiated Notes in Computer Science, vol. 1807, Springer-Verlag, May 2000 and M. Bellare, D. Pointech and P .Rogaway in "Authenticated KeyExchange Secure Against Dictionary Attack", Advances inCryptology-EUROCRYPT 2000, Lecture Notes in computerScience, vol.1807, pp.139-155, Springer-Verlag, May 2000. Most of these papers emphasize that passwords must be appropriately changed The secrets associated with memorization are assumed to be brute-force crackable or at best indefinite entropy views, which ensures additional measures to protect the user.

The SPEKE method developed by the assignee of the present invention is a well-known authentication form of Diffie-Hellman (DH) exponential key exchange, in which the basis of the exchange is determined by a password. In the normal SPEKE usage form, the password provides manual verification of the derived Diffie-Hellman session key. In the pending US patent application serial number 08/823,961 and titled "Extended Password Protocols Immune to Dictionary Attack" by D. Jablon, Proceedings of the Sixth Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WET-ICE'97) Enterprise Security Workshop , IEEEComputer Society, June 18-20, 1997, pp.248-255, and published by R. Perlman and C. Kaufman, "Secure Password-Based Protocol for Downloading a Private Key", Proceedings of 1999 Network and Distributed System Security Symposium, Internet society, February3-5 1999 paper also described the changes of SPEKE.

On January 21, 1999, D. Jablon verbally introduced the split secret titled "Secret PublicKeys and Passwords" in <http:www.IntegritySciences.com/rsa99/index.html> italicized using multiple machines. Key, referred to here as SK1's running SPEKE system. In this system, Alices' private key U is divided into three shared parts, a password derived shared part P, and two large shared parts X and Y. Use the function (bitwise XOR), U=PXY to combine these shared parts, the following outlines the SK1 registration and key retrieval processing.

In the SK1 registration, Alice selects three shared parts (share) {P, X, Y}, combines the two shared parts to generate a secure private key S (where S=PX), remembers P and stores it on her machine Store X on it. Then, using the form of the B-SPEKE protocol, which is one of several other forms described in the Jablon paper in June 1997, she constructs a verification machine {g, V that is consistent with the password derived value {P, S} } As follows: Use an encrypted hash function to construct g=hash(S) and use an exponentiation from an appropriate group to construct V=P. Then she sends {g, V, Y} to Bob, and Bob stores them as her secret.

In SKi key retrieval, Alice (at some later time) obtains her private key U from Bob. Alice uses the B-SPEKE protocol to prove to Bob her knowledge of P and S, and agrees with Bob to verify the session key K. After Bob checks Alice with his {g,V} knowledge, he sends her Y encrypted under K symmetrically. Then Alice decrypts to retrieve Y and reconstruct U. The brute force attack on the password derived value P in this system requires the attacker to have accessed two shared parts x and Y stored on two different machines.

A: S=PXA:g=hash(S)AB:A,QA=g2RA]]>BA:QB=g2RB]]>A:K1=QBRA]]>A:K2=QBpB: K1=QBRA]]>B:K1=V2RB]]>AB: hash(hash(K1, K2)) BA: encrypt(K, Y) A: U=PXY is used in SKi In the brute force attack on P, the attacker needs to access X and Y.

In the Perlman and Kaufman papers, the roaming model and the password-only method are combined to create protocols based on EKE and SPEKE. The simple form of the password-only method shown by these authors is sufficient to secure roaming access certificates. In Gong.Lomas, Needham, and Saltzer papers, Wu papers, S.Halevi and H.Krawczyk papers "Public-keycryptography and password protocols", Proceedings of the FifthACM Conference on Computer and Communications Security, 1998 and P.MacKenzie and R. Swaminathan's paper "Secure Network Authentication with Password Identification" submitted to IEEEP1363 working group, http://grouper.ieee.org/groups/1363/, other roaming protocols on July 30, 1999, all of the above protocols are designed to be clients When storing keys is impractical, prevent offline guessing attacks on network messages to provide strong software-based protection.

The improved Diffie-Hellman was published by Eric Hughes in a paper entitled "An encryptedKey Transimmion Protocol", published at the CRYPTO'94 conference in August 1994 and published by John Wiley & Sons, 1996, page 515 by B A method described in the book "Applied Cryptography Second Edition" by Schneier. In the conventional Diffie-Hellman, the client and the server know the fixed g and mutually agree on K=gxy. However, in the improved Diffie-Hellman, the client (Alice) sends gx, accepts gxy, and retrieves K=gy from the server. Use her secret index x as the secret factor. Recover the key by multiplying the server value by the reciprocal power of x K:=(gxy)1/x. Unlike the conventional Diffie-Hellman method, the statistical value for K can be calculated again, even if the server receives the client's (Alice's) gx.

A form of SPEKE based on an improved Diffie-Hellman, referred to herein as an improved SPEKE, is described in US Patent Application Serial No. 08/823,961. In the improved SPEKE, Alice derives the key K based on her knowledge of P, from The value derived from her password, and the random value y known to Bob. Alice multiplies the password by the secret random x power, and sends the final result value (QA) to Bob. Bob multiplies QA by the power of y and returns the result (QA) to Alice. According to the result of K=Py, Alice calculates K by multiplying QB by the reciprocal power of x.

Alice BobQA:=Px QB:=QAyK:=QB(1/x) It is suggested that P is a cryptographic hash function of the password, such as SHA1 or MD5, which results in a suitably large generator of finite groups. Additional details can be found in US Patent Application Serial No. 018/823,961 and other papers on SPEKE.

In order to spread the risk of stealing verification data, the data can be split into multiple machines. In the design of the network protocol, multiple machines must be used carefully to avoid exposing new attack methods to the password-derived data.

Another method used to protect dictionary attacks is a technique called password masquerading (herein referred to as CC), as described by D. Hoover & B. Kausik in "Software Smart Cards via Cryptographic Camoflauge", Proceedins of 1999 IEEE Symposium onSecurity and Privacy discussed. The CC system is introduced to reduce the shortcomings of the private data stored by the client, and compared with the present invention, to reduce the weakness of the server to store the verification data.

At least one CC system has been improved to support roaming users, which provides two server roaming solutions. Before discussing the two server roaming solutions, the basic CC system will be discussed. The basic CC system includes the user, the client, and the CC authentication server (CCAS).

CC uses a public key technology that clearly violates some principles of public key technology to some extent but has a set of restricted public key technologies designed to achieve the purposes discussed in the Hoover and Kausik paper. The terms "CC private key" and "CC public key" are used to designate the two components of the system.

Note that the terms "private" and "public" used in the terms "CC private key" and "CC public key" have special meanings that are inconsistent with the common use of "private key" and "public key". Specifically, the CC model assumes that the CC private key is not known to the public.

Store the CC private key on the client, but to some extent it is hidden with a small personal identification number (PIN). It uses a special structure that decrypts the stored private key through the private key of any possible PIN that is also specious. (When considering the artificially selected machine-generated PIN, the opponents part of the PIN knowledge and related signs, this issue will be discussed later).

Only the trusted party must know the CC public key. If the encrypted CC private key is stolen, possessing the CC public key enables the thief to launch an attack on the PIN dictionary. In order to meet the security purpose, only CCAS must know the CC public key. In fact, the user may store the CC public key in a form encrypted under the CCAS public key so that only CCAS can read it. Each time the client authenticates to the CCAS, the client sends the encrypted packet to the CCAS.

Similarly, any digital signature signed with the user's CC private key must be visible only to CCAS. Therefore, the message is first signed with the CC private key, and then sealed with the CCAS public key.

Note that Hoover and Kausik talk about more restrictions, namely that only CCAS must know any message encrypted under the CC private key containing verifiable plaintext. Note that it is actually difficult to create useful messages that are not constrained by verifiable plaintext. The assumption that the plaintext is not verifiable leaves unresolved questions about the security of the system, which relies on the flexibility of the attacker to create an appropriate verification method. Pending issues such as those that are unacceptable in this model, so use the stricter statement of this restriction. The following is an overview of the CC system.

In CC registration, the customer selects PINP, private key Ec, and corresponding public key Dc. There are also other restrictions that we do not care about here, namely those restrictions imposed on the structure of Ec or Dc by CC. Client storage: CC(P, Ec) disguised private key Ds CCAS public key Ds(Dc) is the client private key sealed by CCAS In CC verification, the user enters P, and the client retrieves it from CC(P, Ec) Ec. The client sends to CCAS: Ds(Ec(message)), and Ds(Dc).

CCAS opens Ec (message) and Dc, and verifies the client's signature to verify the message.

For CCAS, it may be assumed that Dc carries an appropriate set of certificates to prove the validity of the key. Even assuming that Dc must keep a secret shared by the client and CCAS, this seems to rule out the usual method of using third-party authentication and authorization to prove Dc. Combined with these restrictions on the CC private key and CC public key, it is obvious that these are not suitable for use in any real private key system.

In CC, the PIN is effectively divided into two shared parts, CC(P, Ec) only the client knows, and Dc only the server knows.

Generally, all other messages signed under Ec or sealed under Dc must also be sealed under Ds. According to the present invention, this can be transformed into a two-server roaming solution.

The CC system handles password input errors in a special way by detecting the characteristics of typographical errors in password input on the client. The client compares a small number of hashed passwords with reference data stored locally on the client. However, this mechanism has a significant cost because it leaks some bits of information about the password to an adversary who accesses the stored client data. The result is that for the specified security level relative to online guessing attacks, the password in the CC system must be slightly larger or more complex, and therefore more difficult to remember. Under the premise that people work harder to reduce the computational burden on the system, the CC error handling feature is designed, because the previous error detection on the client prevents unnecessary work on the server. Another basic principle is that computers should be used to free people from work. The system should work hard to tolerate user errors without penalizing users, and still maintain the highest possible barrier to prevent password guessing attacks. The preferred embodiment of the present invention includes a system for optimizing processing of non-malicious errors in password input.

Roaming solutions have been designed and developed by many companies. In order to verify "roaming users", mainly where smart cards are not available, these solutions provide a public key architecture (PKI). In these systems, users can obtain from http://www.integritysciences.com/PKI50.html by J. Kerstetter, "Entrust, VeriSign clear path to PKI", PC Week, discussed on June 14, 1999 The remote authentication server securely retrieves the stored user profile (usually including the users private key). Other work on the authentication server uses the EKE and SPEKE variables described in the Perlman and Kaufman papers.

The password masquerading system described above assumes a single CC server, and assumes that user key information is stored on the client. By moving the data stored by the client to the CC Roaming Server (CCRS) and assigning additional verification data for the second user password to the CCRS, the solution can be transformed into a two-server roaming solution called CC Roaming Program.

The user authenticates to the CCRS using a password and an appropriate password verification protocol, which results in the CCRS having the ability to safely return information to the user. Preferably, this uses a verifier-based or so-called "extended" zero-knowledge cryptographic protocol. However, other structures are possible, including SSL (Secure Sockets Layer) or TLS channel verified by the server to transmit the plaintext password to the CCRS for verification. SSL was discussed by A. Frier, P. Karlton and P. Kocher in "The SSL3.0 Protocol", Netscape Communication Corp., Nov. 18, 1996, and by T. Dierks and C. Allen in "The TLS Protocol Version 1.0 ", IETF RFC2246, http://www.itef.org/rfc/rfc2246.txt, Intrenet ActiVities Board, TSL was discussed in January 1999. As mentioned above, for completeness, CCAS PIN and CCRS password must be selected as completely independent values. If they are related values, an attack on the password may result in the exposure of the PIN.

In general, CC roaming is a two-password system, one password is used for CCRS and the other (PIN) is used for CCAS. An obvious limitation of CC roaming is that the first server has the opportunity to launch a brute force attack on the first password. Two other related issues are the efficiency of using customer entropy and the independence of PIN and password.

When using CC roaming with SSL password to authenticate to CCRS, it also increases the risk of counterfeit server attacks and related password/PIN attacks that will be described below. Counterfeit server attacks are caused by F. Feiton, D. Balfanz, D. Dean and D. Wallach in "WebSpoofing: An Internet Con Game", 20th National Information Systems Security Conference, October 7-10, 1997, Baltimore, Maryland, and at http://www.cs.princenton.edu/sip/pub/spoofing.html Discussed. In all these cases, if only one of them is attacked, it is possible to lose some of the benefits of the two server approach. Using zero-knowledge password proof to verify to CCRS can eliminate counterfeit server attacks and make related PIN/password attacks more difficult.

The CC roaming system invalidates the use of entropy inherent in user passwords, and entropy must be considered a valuable and rare resource. The main purpose of the password method-recall is to reduce the amount of information (the number of valid bits) that the user must remember to achieve a specified security level. The CC roaming system wastes these bits and introduces several weaknesses. First, Hoover and Kausik suggest using certain bits of the PIN to restrict the PIN in advance before running the protocol. They do this by additionally storing a specially constructed small hash of the PIN in the client. Attackers can use hashed PINs to reduce the range of candidate PINs. Assuming that the size of the PIN has been reduced, this can be dangerous. If the user is allowed to select a PIN, this may reduce the range of valid PINs to a dangerous level.

The CC roaming system may also be sensitive to the relationship between the two passwords, AS PIN and RS password, and manually divide the user secret entropy. Hoover and Kausik clearly pointed out that the disguised AS PIN cannot be used for any other purpose. However, if the user accidentally combines the AS PIN in the RS password, or if there is some correspondence between these secrets that the attacker may know, the basic CC system in CC roaming becomes vulnerable.

Related passwords/PINs are possible when the user chooses them to be the same value or different values with obvious or possibly clever but discernible relationships. This is also risky for users with truly unrelated PINs and passwords when they incorrectly type one instead of the other.

If someone wants to attack multiple users extensively, the target range can be reduced by first deciphering users with weak RS passwords, and then focusing on the deciphering RS user groups to decipher their corresponding ASPINs. The leaked information about the RS password can reduce the overall work of a potential attacker. On the contrary, if the same RS password and AS PINs are combined, the ideal two servers (to be described) have a deciphering work factor determined by the password and PINs, requiring a larger overall work factor.

Manually dividing the secret into two factors for the CC roaming system introduces new weaknesses and weakens the model. In the description of the preferred embodiment, a more powerful, simpler, and at least a simpler alternative to CC roaming and CC roaming that protects the secrets remembered by the user is described.

All single-server roaming solutions have inherent limitations. In all of the above roaming methods, a single authentication server maintains data that can be used to verify information about the user's password. If it is assumed that the hashed password is cracked by brute force, the password verification server mainly indicates a single point of failure for the sensitive user data. The system to solve this problem will now be discussed.

Multi-server roaming represents another improvement. While single servers prevent guesses from attacking the client or network, they do not prevent guesses based on password verification data that may be stolen from the server. The multi-server roaming system can prevent such attacks to an alarming degree. At the cost of using n related authentication servers for verification, multiple servers extend the scope of protection to the authentication server database. In these systems, the adversary can control all n-1 servers and monitor the operation of these servers during the successful certificate retrieval with a valid user, but still cannot verify a single guess of anyones password, and will not be affected by the remaining unsuccessful ones. Compromise server detection.

In June 2000, Verisign issued a press release titled "VeriSignIntroduces New Technology to Enable Network-based Authentication, Digital Signature and Data Privacy" in May 2000, and published it at http://www.versign.com/ The webpage of rsc/wp/roaming/index.html describes the characteristics of multi-server roaming at a high level. In the IEEE Ni nth Internat ional Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises in Gaithersburg MD on June 14, 2000, the paper by W. Ford and B. Kaliski was introduced, titled "Server-Assisted Generation of a Strong Secret from apassword". The revised version of the paper was published in the journal in September 2000 (W. Ford and B. Kaliski, "Server-Assisted Generation of a Strong Secret from a password", Proceedings of 9th International Workshops onEnabling Technologies: Infrastructure for CollaborativeEnterprises, IEEE, 9, 2000). These papers describe the use of multiple servers to thwart server-based password cracking attacks. Note that in 20006 On April 14, the method described in the Ford&Kaliski paper relies on the existing server to verify the channel. This dependence on the existing secure channel for password security introduces unnecessary and potentially risky security assumptions. Eliminate this Dependency is an advantage of the present invention.

A method disclosed in the paper on June 14, 2000 uses the improved SPEKE protocol as described above, which is used in the preferred embodiment of the present invention. In the various methods described in the paper on June 14, 2000, two or more servers share the burden of keeping password verification data secret. Each server stores a secret for the user. The client obtains the password from the user and interacts with each server in the second stage of processing. First, the client obtains a password-based amplification key from each server, and then creates a "master" key to authenticate to each server (note that the term "amplified key" is used here (from Bellovin and Merritt's paper) Instead of Ford and Kaliski's "hardened key" term.) Each amplified key represents a shared part of the user's master key. The client uses any standard technique such as the use of a hash function to combine the enlarged key shared part to create the master key.

To obtain each amplified key, Ford and Kaliski suggested two basic methods. One is the improved SPEKE method described above, and the other is to use the secret RSA digital signature in "Security without Identification: Transaction System to Make Big Brother Obsolete" by D.Chaum, communication of the ACM, 28 (1985), 1030 Variables in the style described in -1044. These methods are compared as follows.

The server tracks invalid access attempts, and according to Ford and Kaliski, if there are "significantly more" password amplification steps than successful verification, the server takes action to restrict or lock down further requests. However, the system does not distinguish between errors made by valid users and other events that may more reflect the real attack on the password. Likewise, here their system for handling unsuccessful attempts does not give priority to ordinary human error. Unsuccessful enlargement due to simple typographical errors or other correction errors should not be counted as other unsuccessful attempts. The present invention provides a better way to deal with these situations.

The method in the June 14, 2000 paper further relies on the servers existing secure server-verified channel. This reliance on prior verification creates an unnecessarily complex security model and increases the risk of attacks. These risks may not be consistent with the goal of eliminating single points of error.

The RSA secret public key signature is used in a cryptographic amplification method described in the paper on June 14, 2000. This technique achieves the same effect as the improved SPEKE method-enlarge the password into a large key based on a random component known by the other party. However, the RSA method introduces additional complexity. The details of the RSA stealth method are not included in the Ford and Kaliski paper, but the method based on the reference to Chaum-blinding seems to work as follows.

Instead of a single value y, the server maintains the value {n, e, y} for each user. None of these values are derived from the password. The value n is equal to pq, where p and q are prime numbers suitable for RSA modulus, e is the RSA public key and y is the corresponding private key, so that e=1/mod(p-1)(q-1). Basically, the amplification key is the RSA signature KB on the password. Using x makes this a secret public key signature mode as described in the Chaum paper, where the secret factor x prevents the server from knowing the data it is signing (P).

In the paper on June 14, 2000, it was proposed to use SSL to verify the channel to ensure the authenticity of the KB for the client. The paper also pointed out that the advantage of SPEKE, an improved RSA stealth, is that the RSA stealth client does not have a good (that is, effective) method to confirm the values of n and e, except through the authentication server.

Ford and Kaliski further introduced the "special case" protocol, in which the "password hardened server" is used to amplify the password into a key K1 that is used to authenticate to the (conventional) authentication server. The K1 value is completely determined by the response of the password hardening server and the password. Any attacker controlling the first exchange must not be able to determine whether the K1 value calculated by the user is equal to the candidate K1' value constructed based on his guess of P'. Therefore, the attacker must never view K1. Similarly, if a message is encrypted with K1 containing verifiable plaintext, the attacker will also confirm the guess from there. To counter this threat, the author suggests that the communication channel of the authentication server should be fully protected. The June 14, 2000 paper specifically pointed out a clear method, but it recommended the use of SSL. (Note that the September 2000 paper did discuss how to avoid the need for pre-secure channels). If it is assumed that a common set of root certificates in the client can confirm the two servers, then one or more failure points are introduced into the system. There is a single point of failure in each location reserved for the root or any secondary authentication authority private key. This is important because the main purpose of the model is to eliminate a single point of failure.

The above attack is achieved by compromising any single system with the key to create a valid viewing certificate chain for the two servers described. In addition, as mentioned above, attacks on the security of the SSL/web browser model of security can trick users into using "valid" SSL to connect to malicious servers or not using SSL at all.

The reliance on existing server authentication is a severe limitation. In the user environment, such as public telephone booths or private desktop computers that can connect to various servers in different fields, the user must locate and connect to the appropriate server. The reliance on the user to connect securely to the appropriate server to maintain the security of the password introduces problems. Ford and Kaliski discuss how users can use SSL to create a secure server authentication channel. This implies that the user must (try to) confirm the identity of the server in order to maintain the security of the password. In a typical implementation, it also implies that the client stores server-specific state information to verify the communication channel to the server. To establish a secure channel to the server, SSL solutions usually require a pre-installed root key for one or more certificates installed in the client. It also requires access to an already constructed certificate chain that associates the root key with the public key of the specified server. The client must include certificate validation software and policy enforcement to validate the certificate of the appropriate server selected by the user. Finally, the user must ensure that the bundled server name is correct. This may require effective actions and attention from the user. The dependence on SSl, especially when used in the browser model, is an unnecessary risk. Users can be tricked into using "valid" SSL to connect to malicious servers or not using SSL at all. This process is prone to several types of failures that may be caused by "human error." Think of this problem as an overall system design error based on unrealistic expectations of human participants.

The dependence on the existing server authentication channel for password security is unnecessary. The preferred additional method of the present invention works with a simpler model that is more suitable for the behavior of ordinary people in a multi-roaming user or multi-server environment.

The preferred security model is similar to the June 14, 2000 paper in that both use multiple servers. However, in the preferred model of the present invention, it is assumed that the pre-authenticated secure channel is not stored between the client and the server. The preferred model frees users from having to confirm the identity of the server carefully in order to maintain the security of the password. In this model, the user independently locates the server at will through any insecure mechanisms such as those commonly used on the Internet. These methods include manually typing (or incorrectly typing) URLs, insecure DNS protocols, unreliable search engines, and clicking on items in a collection collected by unknown sources . All these methods and so on provide many ways to establish a connection with the correct server, but none of these methods must guarantee the chance of not connecting to a scammer. The worst threat presented in this simple model is a denial of service-threat that always appears in more complex models in any way. Another advantage of the preferred model is that the password will never be exposed, even when the client is connected to the fraudster in any way.

Most existing technologies deal with incorrect password input very simply. In the paper of June 14, 2000, it is recommended that each server be able to track the number of "password hardening" steps, and make this consistent with the number of successful verifications. If there is "significantly more" reinforcement than verification, then lock the account. This is usually used in password-based systems. However, be aware that unsuccessful logins can be quite common. The password is frequently entered incorrectly, and before the correct password is finally obtained, the user may often enter the wrong choice of multiple passwords. If long-term fixed limits are placed on these errors, effective clumsy users may be locked out. On the other hand, if the system allows a 3 to 1 trial success ratio, it may still not be able to detect the adversary's long-term accidental guessing attack.

To solve this error handling problem, the concept of "forgiveness" is introduced in the present invention. The system should forgive and disregard temporary mistakes made by valid users in the same way as unknown users invalid access. This problem is solved in the preferred embodiment of the present invention.

Therefore, an object of the present invention is to minimize the threat of several server-based attacks in the simple security model of a password-based client/server authentication system. Another object of the present invention is to provide remote user authentication using multiple servers. Another object of the present invention is to authenticate the client to the server using only a small password. Another object of the present invention is to provide verification that does not require storing keys or certificates on the client. An object of the present invention is to use multiple servers for fault tolerance. Another object of the present invention is to provide secure remote password verification even with a total effective compromise of any single server. Another object of the present invention is to better deal with common human errors in password input.

SUMMARY OF THE INVENTION In order to achieve the above and other objectives, the present invention provides a system, method and software for implementing remote password verification using multiple servers. The system, method and software adopt the form of improved SPEKE to realize the security in the multi-server system.

According to the present invention, an exemplary system includes one or more clients and a plurality of authentication servers coupled together through a network. In the exemplary system, the client uses the improved SPEKE to retrieve the shared portion Ki of the secure master key from each authentication server. Where i is a variable that specifies a specific server. The client combines the various shared parts from each server to create a master key Km, which is used to authenticate to the server and retrieve and decrypt sensitive data (including her private key) stored securely on the server or elsewhere.

Each verification server individually knows the random value yi consistent with the single shared part of the master key. Each verification server is also responsible for maintaining a list of recent access requests from clients and coordinating these access attempts by verifying attestation messages received from valid clients. Specifically, when it can confirm the valid request for forgiveness, each server must forgive the valid user for the recent mistakes made in the password input.

To prevent the possibility that the opponent controlling the communication channel can trick Alice into using the incorrect master key Km, Alice confirms that Km is correct before using it to create any data that may be shown to the opponent. The verification step uses signed messages from Alice to each server to verify valid logins and to verify and request forgiveness for the most recent legitimate but incorrect login attempts.

More specifically, at the time of registration, Alice creates n shared parts of the master symmetric key Km, where the i-th shared part Si is formed as a function of her password P multiplied by the random exponent yi. The shared part is combined with the function so that an attacker with correct knowledge of a subset of any shared part cannot distinguish Km from the same random value in the same range. However, Alice manages to convert each index yi that will be stored as a tightly protected secret through the i-th server. Alice also selects the public/private key pair {V, U} for digital signature, and uses the key derived from Km to symmetrically encrypt the private key U to create her encrypted private key UK. Finally, Alice creates proofPKm that links the key to her master key. Alice sends V to each of the n servers, and stores Uk and proofPKm on each server in a convenient place. The registration protocol flow is executed through the secure channel, and each i-th server Bi in the secure channel verifies Alice's identity A.

client: {enroll, A, V, yi} Biclient: {record, A, UKm, proofPKm} Bi During key retrieval, in order for Alice to reconstruct her master key and retrieve her private key, Alice will randomly The secret form of the password Q is sent to each server. Each server responds with a secret response Ri (Ri=Qyi) in turn. Ri is composed of the secret code multiplied by the power of the security exponent, and yi represents the secret shared part of the user's master key. At least one server also sends Alice her encrypted private signature key Uk and proofPKm.

Client: {request, Q} BiServer Bi: {reply, Qyi, Uk, proofPKm} Client Interestingly, Alice retrieves the channels of Uk and proofPKM without guaranteeing the integrity of these values. This will be discussed further in Section 4.4.

Alice unblind each response to obtain each shared part of the key and combine these shared parts to reconstruct her master key Km. Then, she uses the proof value proofPKm and her password P to verify whether the master key is correct. If it proves to be incorrect, it implies that at least one key sharing part is incorrect, and she must interrupt the protocol without displaying any additional information about Km or P to the network. Otherwise, use the key derived from Km to decrypt her encrypted private key (and any other data), and then, by proving her identity to each server, she completes the agreement. For each hidden secret code Q recently sent to each server, she sends a signed copy of the hidden secret code.

Client: {confirm, Q1, sign(U, Q1)} BiClient: {confirm, Q2, sign(U, Q2)} Bi Each server matches the signed Qx value from Alice with the list of hidden secret codes received recently , And delete any matching input with a valid signature. If it is not confirmed within a reasonable amount of time, the remaining input will be considered as a suspicious illegal access attempt and marked as invalid. If the count exceeds a certain threshold, invalid access attempts can be used to limit or delay responses to additional secret shared parts of the user account.

Alice must verify her master key. As mentioned above, Alice can perform authentication on an insecure channel. She retrieves (usually from a certificate server) her verification machine proofPKm, and then confirms the validity of the reconstructed master key by comparing the key hash of her password with proofPKm. If the values do not match, Alice aborts the protocol.

Another improvement of the method involves how Alice proves knowledge of the master key to each server, and how each server reconciles this information with its own record of access attempts.

Each server detects an illegal access attempt by looking at the message from Alice and by a proof that implies that she knows her password, the message includes a proof of her knowledge of the master key. If the valid proof has nothing to do with the hidden secret code value, the server must trigger an invalid access event for Alice's account. This method differs from the prior art in terms of constructing Alice's proof and how each server uses the proof to forgive Alice for errors in password output.

When the secure channel is not used, simply sending the proof to Bi can expose the method to reproduction attacks. To prevent this, the proof is given to the secret request value sent by Alice. In addition, recognize that Alice accidentally typed her password by mistake and incremented her illegal access count that could lead to premature account lockout without punishing her. I hope that when she can prove to the server that she can finally enter the correct password, each server will forgive her for her mistake.

Use forgiveness agreements to forgive users for their honest mistakes. After each successful verification, Alice sends proof of her most recent invalid access attempt in the form of a request for forgiveness. Once the evidence is received and verified, each server deletes the error from the record, or records the event as a corrected forgivable error. By fine-tuning the server's event login in this way, as opposed to when only valid users are frustrated, the system administrator gains a more detailed concept of when the system is truly at risk.

The forgiveness system seems to require at least one signature generation step on the client and one signature verification step for each server. In order to reduce computation (due to computational cost, it is important when using public key signature methods), the signature step provides a verification service and a combined function that proves that the request comes from that user. In constructing a valid authentication message for the user, the client includes all the most recent challenge message groups issued by that user, digitally signs the result with the appropriate user key and sends it to all servers. Each server verifies the signature to verify the user, and at the same time, verifies her proof of the most forgivable error. (These signatures can use the user's private key in the public key digital signature system to create and use the client's public key, or alternatively, use the key MAC encrypted by a separate symmetric key to verify that the symmetric key can be Shared by both the client and each server).

Upon receiving Alice's confirmation message, each server attempts to make the proof of her access attempt consistent with his list of records of recent attempts. He accomplishes this by verifying Alice's signature at each Q value. Once successfully verified, he knows that the Q value is indeed sent by someone who finally knows the key, regardless of whether the request message is specifically for rebuilding her master key.

In the preferred embodiment of the present invention, the weaknesses of the password verification machine are distributed among the servers so that no server can decipher the verification machine. Provide a system calibrated to N servers, in which any attack on the number of servers equal to N-1 cannot reveal the user's password or any protected password data. Provides a strong guarantee, even in the face of the total effective compromise of reaching all servers except one authentication server, and in the face of existing insecure communication channels. It should be understood that the password is only a factor in the realization of the system.

It should be understood that the password is only a verification factor required in implementing the present invention. Only password verification is the main method used today. In the present invention, the cryptographic factors are made as strong as possible, and do not rely on other factors.

It should also be understood that other additional keys or certificates may be used. It is foreseen that the present invention can be used in a multi-factor system. Obviously, in non-roaming applications, there is the ability to store local keys, and this operation can provide a layer of strength. For example, for the security of the password in the present invention, the use of an encrypted socket layer (SSL) channel is not required, but the use of SSL can provide other benefits, such as increasing the security level of the user's name when performing these transactions. By eliminating the dependence of other factors for password security, the strength of the entire system is greatly increased. Specifically, the present invention prevents a whole class of counterfeit Web server attacks that may be directed at the over-simple Web browser authentication that is widely used today through the SSL cryptosystem.

Brief description of the drawings The various characteristics and advantages of the present invention will be more easily understood with reference to the following detailed description in conjunction with the accompanying drawings, where the same reference numerals denote the same structural elements, and where: Figure 1 is according to the present invention The principle describes a block diagram of the client and server components of an exemplary system; Fig. 2 is a flowchart describing an exemplary method of client operation according to the principles of the present invention; Fig. 3 is a block diagram describing an exemplary method of server operation according to the principles of the present invention Fig. 4 is a flowchart describing an exemplary method according to the principles of the present invention; Fig. 5 is a flowchart illustrating an exemplary operation of a client communicating with only one of the two servers according to the principles of the present invention; Flow chart of the method.

DETAILED DESCRIPTION With reference to the accompanying drawings, FIG. 1 is a block diagram illustrating an exemplary multi-server system 100 according to the principles of the present invention. The exemplary system 100 shown includes a client 101 or a client computer 101 (Alice) and a plurality of authentication servers 103, 104, in this example two servers B1103 and B2104 coupled together via a network 102.

The present system 100 and method use an improved SPEKE method for the client 101 to retrieve the master key shared part from two or more servers 103, 104 (using the number n to designate the server 103, 104 used in a specific embodiment Quantity.) The model used in implementing the present invention allows authentication messages to be sent on an unprotected channel or network 102, and does not require a secure channel (such as SSL). To prevent the possibility that an adversary of the control channel can trick Alice into using an incorrect master key, Alice confirms that the master key is correct before using it to create any data that may be shown to the adversary. In addition, the verification step uses signed messages to verify valid logins, as well as previous legitimate but incorrect logins to adapt to the forgiveness agreement. A unique function is provided to create the basic elements of password derivation for exponential exchange, and a form that allows the client 101 and servers 103, 104 to be more flexibly constructed is described. Provide an alternative approach in a weaker security model that is important to the specific situation.

In a preferred embodiment, Alice's potential small password and all her protected password data are still safe, even in the face of a total effective compromise equal to n-1 servers 103, 104. The encryption of Alice's sensitive data under the key derived from Km ensures that through this verification process, her data will only be valid for the parties who use the correct password.

When registering, Alice chooses the password and many shared parts {y1, y2,...yn} used to create the master key Km. In this example, the master key derivation function is Km=hash(k1K2...Kn), and each shared part is calculated as Ki=pyi]]>, but other key derivation functions are described below. Alice pre-calculates Km through each Bi and stores the corresponding key sharing part yi and verification data for Km. The verification data is usually a digitally signed message using a public key digital signature or another symmetric key MAC function.

Each server Bi uses the improved SPEKE protocol to provide Alice with part of Ki based on his knowledge of yi. Each time the protocol is run, a shared part of her secret key is retrieved, which in this embodiment is the value mi=Pxyi]]>. Alice combines and hashes these shared parts to derive the master key. In this example, use: km=hash(m11/xM21/x...mn1/x) Because of the random yi value, these keys share parts Is irrelevant.

Referring to FIG. 2, later, Alice retrieves the master key from the servers 103, 104. The client 101 prompts the user to enter the password 201, and derives the group element 202 from the password according to the improved SPEKE method (when a large prime power subgroup zp* with a prime number of (p-1)/2 is used, an example of this function is p=hash(password)2modp). Using the improved SPEKE method, Alice sends the hidden secret code value Px to each server Bi2O3. Each server Bi multiplies the hidden secret code value by an appropriate power, as in mi=(px)yi]]>, and returns the result to Alice. Alice retrieves the corresponding secret value 204 of each key shared part mi, does not secret each result and combines them to create her master key 205. In this example, use the function km=hash(m1y1||m2y2||...mnyn).]]> Here is the general method for Alice to retrieve the key shared part Ki from any server, usually marked as Bi .

ABi: mn=PxBiA:mi=moyi]]>A:Ki=mi1/x=pyi]]>The safe value y1 known by B1 has nothing to do with the value y2 known by B2 and so on. Therefore, no server has enough information to launch Km or P dictionary attacks. With this protocol, each Bi stores yi in advance, and also stores the verification data V of the one-way function of the master key Km.

Using the key derived from Km, Alice can use Km to decrypt personal private data 208 that has been stored in the encrypted container. The container may be stored on any server 103, 104 or anywhere convenient, and can be retrieved on an insecure channel. However, before Alice can show any data derived from her knowledge of Km to any other parties, she must first determine that Km is valid208. The specific confirmation techniques are discussed below.

If Km is invalid, then according to the local password retry policy, the user may be required to try again by re-entering the password 201. If a retry is performed, the client 101 stores the Px value used in the failed exchange in the secure short-term memory.

If Km is valid, Alice constructs a proof Px of Km's knowledge and a list of any most recent Px values stored in short-term storage generated by the same user, and sends the proof to each server 103, 104 207. Now Alice can freely use the data derived from Km, such as a signed public document 209 with a private key stored in an encrypted container.

Using any appropriate zero-knowledge protocol, Alice can prove the knowledge of Km to any Bi. The zero-knowledge protocol does not have to be a zero-knowledge cryptographic protocol, because Km has a large entropy. Each server Bi has verification data information V that is consistent with Km and allows him to verify the zero-knowledge proof of Alice's Km.

For example, in one embodiment, Alice uses Km to retrieve the user's private key U for the public key digital signature mode, where V is the user's public signature key consistent with U. Alice can prove Km's knowledge to Bi in many ways, such as signing a message with a private key, where Bi verifies the signature and proves Alice's knowledge of Km.

U can also be derived from Km in many ways. In one embodiment, just use any data to directly derive the U and V values from Km.

In the preferred embodiment of the present invention, the U value is continued to be sealed in a container encrypted with a symmetric key derived from Km. In this case, Alice uses Km to derive the symmetric encryption key, and then turns on her private key U.

Then Alice signs the message that Bi knows to prove her Km knowledge, and sends the signed message to Bi. In an embodiment of the present invention, the message is the value RBi sent by Bob to Alice.

BiA: RBi, a random one-time number ABi: U(RBi) Her RBi signature. In addition, in the preferred embodiment of the present invention, Alice sends U(QA), and further uses QA to prove that she is the person who verifies . The following discusses why Alice should verify QA, and how it relates to how each server needs to distinguish good from invalid access attempts.

The third method is V=gKm, which is mainly used for the Diffie-Hellman public key of Km. In this case, Alice may verify as follows: BiA:gxABi:m:=hash(gx)Km)Bi: If (m=Vx), then Alice must know Km and then Alice may send Ekm(QA) To prove herself.

In any case, when Alice proves the knowledge of Km, she is also proving the knowledge of the password P.

There is a good reason not to want the server Bi to know the single shared part Ki, because the knowledge of the combination of Ki and yi enables that server to decipher P. In the case of a single server, it seems inevitable that the server must store certain data that can be used to decipher the password. But in an ideal multi-server situation, you don't want the server to know P, Km, or Ki, or any other data that can cause P to be deciphered.

In general, each Bi does not know P or Ki. Bi uses yi to run the improved SPEKE and verify Alice's knowledge of Km. Each Bi only knows yi and V, which are used for the verification data of Km, and the verification data is also used as verification data for Ki or more widely used for verification data of Alice's knowledge of P.

When registering, Alice chooses her password and the public/private key pair {V, U} suitable for performing public key digital signatures.

Alice performs the following steps offline: Construct a group element P based on a password, where: P=hash(password) 2mod pFor i=1 to n servers 103, 104 {choose yi as an irrelevant random number Computer Ki:=pyimod p} Use all Ki shared parts to form K, for example, Km=hash(K1K2...Kn) to construct universal verification data for the master key Km, such as V=gKmmod p, then Alice securely distributes these certificates to the n server 103, 104 Let "UserID" be the identifier for the user For i = 1 to n servers {store {UserID, yi, V}} on each server to verify that Alice retrieves each Ki shared part by using an improved SPEKE, Combine the shared parts to create Km, check the validity of Km, and provide knowledge of Km to verify to each server Bi.

For each server Bi{ABi:QA=PxmodpBiA:QB=QAyimodp,V]]>A:Ki=QB(1/xmod(m-1))modp} calculate Km: =hash(K1K2 ...Ki) Verify the validity of Km (described below) for each server Bi

{ABi: proof(Km, QA)} Note that each server Bi does not know Ki, and cannot calculate it without knowing the password P. Even better, each Bi does not know Km or P, and without knowledge of other shared parts, it cannot be calculated from V. Even with brute force, Bi cannot calculate it from yi unless he obtains all the shared part yi. Therefore, a malicious server cannot calculate P unless all n servers 103 and 104 compromise. Inability to access even if only one yi value makes brute force impossible.

Preventing Online Brute Force Attacks To prevent online guessing attacks, the servers 103, 104 will wish to limit the count or frequency of running protocols on a per-user basis. This technique is well known. However, in order to optimize this system, it is necessary for the servers 103 and 104 to distinguish between valid and invalid operation of the protocol. In addition, it is also useful to distinguish between legitimate user errors and suspicious attacks for invalidly operating protocols.

Specifically, it is desirable to distinguish users who occasionally type the wrong password from truly unauthorized attempts for verification. Unlike machine-to-machine verification, errors are common in user verification. Specifically, there are several common types of errors in password verification. Maybe Alice temporarily forgot her password and typed something similar, but it was wrong. Or maybe Alice knows the password, but made a mistake when typing it. Another common mistake is the wrong choice of typing in multiple passwords that she may obscurely remember. It is common for users to make these mistakes during a series of login attempts, where the last final attempt is valid. If the server counts all of these conditions as a suspicious hacking attack, and if the server places strict limits on attempt counts before locking the user out, it may generally accidentally lock the user out of their system.

In the system 100 described above, Alice can prove her combined {KmPx} knowledge to all verification servers 103, 104 so that they can distinguish her legitimate but erroneous access attempts from the attackers guess attempts Come. If the server does not retrieve such proofs, perhaps in a certain time interval, they should conservatively assume that the guess made with Px is an invalid and unauthorized access attempt by the attacker, and count them against the allowed invalid attempts.

One way to reduce the impact of typographical errors on invalid access calculations is to detect invalid input on the client 101 and avoid sending duplicate invalid passwords to the servers 103, 104. As long as the client software detects a special input that has been rejected by the server, it displays a rejection message to the user. If the user repeats the same invalid input, the client software can recognize this and avoid connecting to the server again. This optimization must be done in a short duration in order to reduce the exposure of the password stored on the client 101.

Forgiveness agreements now describe another novel approach to the problem, called "forgiveness" agreements. In this system 100, it is assumed that the correct password is entered after many accidentally entered incorrect passwords in a short period of time. When this happens, it is hoped that the servers 103, 104 will forgive the wrong input. This can be done by effectively eliminating the event from the recorded number of invalid access attempts, if it proves that these errors were made by legitimate users. By forgiveness, a user who frequently incorrectly types his password does not have to be penalized by the system 100 that maintains small long-term restrictions on unauthorized access attempts.

The natural way is to simply delete all previous and most recent invalid attempts after each successful attempt. However, this allows an attacker who knows the threshold of the system to alternate between the effective running protocols of the actual user to make the optimal number of guesses for the password.

The solution to this problem is to identify (as much as possible) that the wrong access attempt is only an accidental error of the valid user, and to prove the information to the server. This is done by the client during each successful run of the protocol to send evidence of previous errors that the user knows to make. Basically, users ask for forgiveness every time this kind of mistake. When the server verifies that a valid user has made a mistake, the server reduces (eliminates) the error from the record. The advantage is that it can tighten more stringent restrictions on the number of invalid access without penalizing the few users who repeatedly make typos.

Referring to FIG. 3, an exemplary forgiveness protocol 300 (implemented in software 300) used in the preferred embodiment of the improved SPEKE multi-server system 100 is described: the server 103 maintains the following data variables for the user: Z number of attempts N Number of recent amplification requests R[1...n] Px Password amplification request value list T[1...n] Timestamp list related to R[1...n] Server 103 receives the hidden secret code (Px) Request 301. According to the local policy, check the user account to see if it is locked 302. If it is locked, there is no need to send a response 303. If it is not locked, record the secret code 304 in the short-term suspicious list, create a secret key shared part (pxyi) 305, and send the secret key shared part (pxyi) to the client 101 at 306.

In the case that the account is not locked and the secret sharing part is sent to the client, only the request to record the secret code should be completed. However, to be safe, you should complete the recording before sending the secret shared part.

Therefore, for each login attempt, in which the password enlargement process occurs 305, the N value is decremented, and the server 103 records the used QA value in that run in the list value R[N] 315 in the short-term memory. The server 103 also records the relevant timestamp value in T[N] to record the time of receiving the request.

Periodically, the server 103 will run a process to find or check the invalidation request 313. When the difference between any timestamp value in T and the current time becomes greater than a certain time period, the server 103 will delete any corresponding R value 314. The length of the period can usually be the maximum count of attempts by a valid user who has made a mistake to continue logging in with the correct password. When each R value is deleted from the list, the corresponding T value and the most recent enlargement number N are also deleted. At each such event, the number of invalid attempts Z is decremented in the long-term storage 316 to indicate that the unverified user has had multiple password amplification events.

When a successful login occurs, at 308, the client 101 sends the QA value equal to the random power of the password and any previous value for QA from the previous run in the same login session to each in the digitally signed message. Individual servers 103. The message is signed using a key derived from the knowledge of the user's master key Km. It is better to perform the signature using the public key digital signature on the use message of the user's private key U that can be verified by any server 103 with the user's public key V.

In addition, the signature can be performed by calculating the key MAC encrypted by the shared key of the user and the server. In this case, the key can be derived directly from Km or obtained from the encrypted container symmetrically encrypted by Km, but usually the shared key must be unique for each user/server relationship.

The signed message 308 can be received from the server and confirmed 309. The confirmation step may be a public key digital signature confirmation using the user's public signature key, or in addition, an encrypted MAC confirmation using a user-specific key known to the server. The server 103 verifies the user list signatures of all recent QA values and compares them 309 with the list of values found in the previous run in the list R. When there is no match, the list R310 is not changed. Generally, the system should not process the received invalid certification as a successful or unsuccessful login event. When there is a match, the corresponding access attempt 311 is eliminated from the list R in the short-term memory 315, and the corresponding time stamp is eliminated and the N value is decremented.

The server 103 may choose to limit the number of invalid attempts Z, or perhaps the total number of invalid attempts and recent unconfirmed enlargements (Z+N). This restriction may be specific to users, user sets, or system-wide restrictions. Likewise, when the limit is exceeded, the action taken can be changed from permanently locking the account outside to temporarily locking the account outside, and/or presenting an alarm status to the system administrator. This change in technology is common in password-based systems.

The server 103 also wishes to record information related to the client 101 or the network 102 from the event access. The server 103 may even maintain an account of such events on a per-client basis.

Note that in the improved SPEKE system 100, even the record of the exposed QA value poses an insecurity threat to the client 101 or the server because the data has been disclosed.

When using forgiveness agreements, one concern is in the shared workstation settings. If a persistent login program runs at long intervals, the attacker may arrive at the workstation just before the desired destination user arrives, and the attacker can insert multiple guesses that will soon be forgiven. Therefore, the system designer needs to consider the likelihood of such events and may appropriately adjust the forgiveness time window. Another way to reduce this threat is to use a system that proposes a session-based method to log in. The client 101 can use the security attention key to start a login window that keeps valid for several access attempts, and then leave after a period of inactivity. The system never asks for forgiveness for invalid login attempts made in previous sessions, but it can forgive all invalid attempts in a single session. Users should also be trained to ensure that the latest login session is always used when using a shared workstation.

An obvious process of distributing U(QA) messages is to make Alice contact all N servers 103,104. However, in order to reduce the interruption on these busy machines, Alice can only contact one of the servers 103, 104. The server 103, 104 can then propagate the evidence to all other associated servers 103, 104 and complete it in a total batch request series. For example, an update may be performed every few minutes to distribute "forgive me" requests to all users currently arriving for the system. This technology can reduce the count of interruptions and the amount of communication overhead for each server.

Summary of Forgiveness Agreement The system 100 is "lenient" because it calculates the user account limit for valid users by mistake to prevent invalid attempts. It underestimates the effective transient error as not a threat to the system 100, while still maintaining the ability to calculate and restrict invalid access attempts by unknown users.

This is done by sending evidence of the most recent invalid access attempt after each successful verification. Once the evidence is received and confirmed, each server deletes the error from the record, or records the event as a corrected and forgivable error. By fine-tuning server event logins in this way, the system administrator obtains a more detailed overview when the system 100 is truly at risk, as opposed to when only valid users are frustrated.

The forgiveness system 100 requires at least one signature generation step on the client 101 and one signature verification step for each server 103, 104. To reduce the comparison, the signature step can be combined with the signature step of verifying the user. In constructing a valid verification message for the user, the client 101 includes all recent challenge message groups issued by that user, digitally signs the result with the user's private key, and sends it to all servers 103, 104. Each server 103, 104 confirms the signature to verify the user, and at the same time confirms evidence of her most recent forgivable error. This implementation of the forgiveness system 100 requires no significant additional calculations for any parties.

Denial of Service When setting a small limit for account lockout on invalid attempts, there is also an increased threat of denial of service attacks. An attacker can simply deny a specific user access to the system 100 by performing repeated deliberate invalid access attempts.

One way to alleviate this problem is to record information about the source of invalid access attempts in the server record, more specifically, make the server perform a lock operation on a per-source basis. When such information is valid, the source information may include the name or network address of the originating client computer 101.

Extension As long as the user obtains her master key Km, the basic system 100 described above can be extended in many ways. Each authentication server, and more generally any other server, can store private files for the client 101 that are symmetrically encrypted under the user's private key Km. You can even freely send the file to the user without verification, because it is strongly encrypted. This file can contain the user's private key and other sensitive data for the user.

The basic multi-server protocol described above can be extended to allow a situation where some subsets of servers 103, 104 can be temporarily disabled.

Note that the shared part Ki can be combined in many different ways. One example is to extend the system 100 to allow M out of N verifications, where access to a subset m of n servers 103, 104 is sufficient to obtain enough shared parts to form K. An example of this is as follows: Calculate a list of combinations of {C1, C2...Cx}, where Ci is all possible valid combinations of a Ki part. For example, when m=n-1, someone can calculate the effective combination of all n-1 shared parts in the following way: for i:=1 to nc:=null bit stringfor k:=1 to nif k! =ic:=CiKkCi=hash(c) Then the server stores K: C={excrypt(C1,K), encrypt(C2,K),...excrypt(Cx,K)) x different symmetric encryptions .

When verifying, the client 101 retrieves the list C, decrypts K, and proves the knowledge of K to the servers 103 and 104. This method may be practical for small values m and n.

The problem of short exponents is generally that the exponentiation of q is the main cost of the above method, and it is hoped to reduce the exponent. D. Jablon in "Password Key Exchange using a Composite Modulus", Document Disclosure No. 443510, a set of methods of the USPTO applied for on August 20, 1998 to provide effective zero-knowledge methods with short indices, hereby merge Reference.

Another method is to use the short index discussed by PCvan Oorschot and MJ Wiener in "OnDiffie-Hellman Key Agreement with Short Exponent" in Proceeding of Eurocrypt96, Springer-Verlag, May 1996. These authors discuss the relative cost of known computational attacks and discuss the appropriate size of the short index.

However, there is still a concern that this does not solve the possibility of developing techniques to leak information about the derived cryptographic base, assuming that the final domain obtained by exponentiating the short random exponent to different cryptographic values is very clear.

When using a random index x selected from the average distribution range in [1, o(G)], it is obvious that only knowledge of Px and no knowledge of x does not show information about P. But when the short exponent x in the range [1, m] is used, where m<o(G), the safety depends on some additional assumptions of the calculation. What if someone finds a special attack on the incident? Van Oorschot and Wiener discussed the use of short exponents in Diffie-Hellman, in which the author identified the Pollardλ method as the most effective known method to calculate a random exponent gx for some known fixed base g. λ Discrete Logarithm calculation requires x1/2 operation. An overly simple way to decipher the password generated by the Diffie-Hellman exchange is to calculate an exponent for each possible base P1, where P1 is constructed for each candidate password. However, one may be concerned that there may be a simpler solution.

Regarding problem (1) that may be simpler (unnecessary) than the brute force λ attack, we propose a method to reduce the calculations of Alice and Bob by using subgroups that are significantly smaller than the prime power of the modulus. It is hoped to eliminate any assumptions of calculating stabs, as for the situation where the opponent only determines the information from the customer's Px value.

The P=f(gh) method for the cryptographic derivation generator is used to solve this problem using a large prime power subgroup that is significantly smaller than the power of the modulus. Use functions to (relatively effectively) convert passwords into generators of the subgroup, and use devices that effectively maintain security by reducing leakage of information about the server security index with potentially less hypothetical calculations. In this embodiment, the value P is derived from two independent random group elements (g, h), where one of these elements h is multiplied by a power according to a cryptographic function.

Fixed system parameters: let p=k·q+1 where 21023<p<21024, and 2159<q<2160, p and q are prime numbers let g=hash("g") kmod p let h=hash("h ") kmod p, the q-th power hash function of two unrelated elements is a standard cryptographic hash function such as SHA1. The input string to the function in this example is an arbitrary constant, and in this example it is a single ASCII string "g" and "h". It is important that g and h are arbitrary independent numbers, so that g is not known to be related to h by any exponential power.

Registering Alice performs the following steps when registering: select yR[1,q] a random number in the range of 1 to q, calculate t=hash(password)mod q, calculate P=g.htmod p, calculate K=Pymod p Using server B to store the password t derived from y in the exponent adds to concerns about the "password-in-exponent" problem identified in the Jablon paper in June 1997. The attacker does not have to be able to create an "exponential dictionary" {e1, e2,...} to establish the correspondence between the fixed base g and the dictionary {P1, P2,...} of candidate values for P so that gei=Pi.] ]>If g and h are independently selected so that they cannot be linked by the index of any book, then prevent the problem. The structure of the fixed system parameters as described above guarantees this.

Note that if variable parameters are desired for some reason, the client 101 may verify that g and h are appropriate by verifying a public certificate that proves their validity. The certificate can simply be entered into the hash function-in this example the strings "g" and "h". If the hash function must be reasonable and the hash range must be large enough to prevent collisions, the final value should be basically indistinguishable from the random number. The discrete logarithm problem ensures that the exponential relationship between these two random elements cannot be determined. A suitable hash function is SHA1 described in "Secure Hash Standard", FIPS 180-1, US National Institude of Standards and Technology.

Verify that in the password amplification protocol performed by Alice and Bob, Alice performs the following: calculate t=hash(password)mod q calculate P=g·htmod p select yR[1,q], random in the range 1 to q Calculate the number r=Px and send r to Bob and then Bob performs the following: If (rqmod p)1 or r=1, abort the process. Calculate s=ry and send s to Alice. Then Alice performs the following steps if (sqmod p) 1 or s=1 to stop calculating km=s1/xmod p. In this method, Bob and Alice perform two exponents with 160-bit exponents. When compared with similar Ford and Kaliski methods, this method provides a roughly equivalent level of security with fairly low calculations, assuming that the short index problem can be solved.

This is described as "rough" equivalence, because it is difficult to determine any exact equivalence between the minimum size used for the exponent and the symmetric key. In this example, it is assumed that the higher random exponent and the subgroup are 160 bits, the symmetric key has a strength of 80 bits and the modulus size is 1024 bits. This relationship is difficult to explain accurately. As a point of view cited, note that the DSS signature standard uses a 160-seat subgroup with a 512-bit modulus. Other standards usually assume a large modulus size for the 160-seat subgroup. In any case, since the standard used to increase the size of the key changes, the size of the value in the method described here is also appropriately adjusted.

Constructing with a modulus of p=f(gh) in the above method, where p=kq+1, and using the count q of the subgroup, there are concerns about the factor k. For all small factors k, where small means less than some minimum safe size, the adversary can test the server with a specific value T to obtain Tymod p. This result may allow the adversary to know information about the index y of the server. Let S be a multiple of all small factors k, and recognize that for each small factor, there is a corresponding small subgroup. By constructing K so that S=2, the attack can be reduced to the smallest program, and only the low bits of y are leaked. In one embodiment, p=kq+1, where K=Sr, S=2, and r, q, and p are prime numbers.

Leaking only the low bits of y should not be an important issue if the index y is truly random. Assuming that the low bit is an independent random number, the minimum safety index size can be simply increased by 1 bit to compensate. This 1-bit leakage can be prevented by spreading the low-order y of a fixed constant value throughout the system 100.

The security and effectiveness of p=f(gh) is to ensure that y is a multiple of S to reduce information leakage from probing attacks. Also here, the size of y must be appropriately increased to compensate for the randomness loss, so that if S is 10 digits, y is greater than 10 digits in the case of S=2.

With the p=f(gh) method, we can use a short exponent with more confidence and only increase the small computational cost for the client 101. The performance of this method can be compared with that of a method that uses a similar short exponent but has a value P that can produce a larger group. This method obtains the additional protection of the provable security of the client's first message without significantly increasing the server's calculations. The cost added by the customer is h to the power of t.

Finally, the method used in the present invention to increase security by eliminating the assumption of computational stabs will one day prove to be irrelevant. It may prove possible that the computational security of using short exponents is similar to other assumptions that we take the method as a whole, such as the assumption that discrete arithmetic problems are difficult to handle.

Another key derivation function Another key derivation function is possible for deriving the master key from the key share {y1, y2...yn}. Here are three such functions, the first one is the same as the above example.

Km=hash(Py1Py2...Py2), using cascade, Km=hash(Py1py2...Py2), using XOR function, Km=hash(Py1*py2*...Py2), Use group operators.

Under certain circumstances, it is more advantageous to use combined key sharing for exponentiation in the group and the combined key derivation function shown here, which will be discussed further below.

Km=hash(Py1.y2....yn), using repeated groups for exponentiation.

In the next section, these different additional key derivation functions have advantages in different method embodiments.

Another stream and combination key derivation function is used to authenticate with multiple servers 103, 104. A simple method has a client 101 that performs a series of challenges with each of two or more servers 103, 104. Response protocol, where: Method (1) A: m1=PxAB1: m1B1:m2=m1y1]]>B1A: m2AB2: m1B2:m3=m1y2]]>B2A: m3A: Km=hash (m3(1/x), m3(1/x)) Another method for the client 101 to send a single Px to multiple servers 103 and 104 at the same time (2) It is possible in an environment where the client 101 can collect responses asynchronously It is very advantageous to let the servers 103 and 104 (B1 and B2) work at the same time to compute and send responses in parallel.

Method (2) A: m1=PxAB1: m1AB2: m1B1:m2=m1y1]]>B2:m3=m1y2]]>B1A:m2B2A:m3A: Km=hash(m2(1/ x), m3(1/x))

When compared with method (1), method (2) can reduce the overall running time.

The further optimization in method (2) is to derive the master key from the group product of the key sharing part, such as Km=hash(K1*K2*...Kn). In this case, Alice can perform the calculation Km=hash(m2*m3)(1/x)), which reduces the number of fingers she must perform.

Specifically, FIG. 4 is a flowchart describing an exemplary method 400 according to the principles of the present invention, showing the operation of a client and two servers using a group product key derivation function with optimized calculations.

In step 401, at the registration time {UserID, yi, V} are stored on each server 103, 104, and the encrypted copy of P (Hp=hash(P)) and the users private key are stored in the user identity {UserID , Encrypt(Km,{Hp,U}) in the related dictionary. Note that the encrypted container includes the message authentication code to ensure that the container cannot be modified to destroy U and not to destroy Hp.

When logging in, in step 402, a group element (P) of an appropriate function for inputting a password is created (as described above). In step 403, a secret key sharing part (m1=Px) is formed. In step 404, the secret key shared part is sent to each server B1103 and B2104.

In step 405, a secret key sharing part (m2=m1y1) is formed in the first server (B1) 103h. In step 406, the server B1 stores the secret code in the short-term memory, and in step 407, sends the secret key shared part (m2) to Alice. In step 408, Alice obtains her encrypted password verifier Hp and private key U from the public dictionary (step 408 can be completed at any convenient time). In step 409, a secret key sharing part (m3=m2y2) is formed on the second server (B2) 104. In step 410, the second server (B2) 104 records m1 in the short-term storage and sends m2 to Alice in step 411. In step 412, Alice 101 does not conceal these shared parts and creates her master key Km=hash(m3*m3)(1/x). Note that Km=hash(Py1*Py2),]]> uses the group product of the shared part for key derivation.

In step 413, the client 101 uses Km to decrypt the dictionary data to retrieve Hp and U. In steps 414 and 415, if Hp is not equal to hash(P), the client 101 is interrupted. In step 416, the client 101 uses her private key U to create a signed message containing the hidden secret code m1, and sends it to B1 and B2 as evidence that she is operating on behalf of a legitimate user. In step 417, each server uses the user public key V to verify the signature on m1 in the message m4. In steps 418 and 419, if the signature on m1 is verified and m1 is found in the short-term list of suspicious login requests, the secret key shared part m1 is deleted from the list.

However, there may be situations where the serialization of the message stream is inevitable, as in the example of the chain method, where the server B1 acts as an intermediary between the client 101 and the server B2. In this case, using the sequence index of the secret key, such as in Km=hash(Py1*y2...yn)]]>, another combination of key derivation function can be used to derive the master key.

Method (3) A: m1=PxAB1: m1B1:m2=m1y1]]>B1B2: m2B2:m3=m2y2]]>B2B1: m3B1A: m3A: Km=hash(m3(1/ x)) Note that the order of calculations performed by B1 and B2 can be interchanged, and that B2 can simply send m3 to A directly. The method is described in detail below and is represented in FIG. 5. Another equivalent sequence is as follows: Method (4) A: m1=PxAB1: m1B1B2: m1B2---m2=m1y21]]>B2B1m2B1:m3=m2y1]]>B1A: m3A: Km=hash(m3(1/x)) Alice can also use the combined key derivation function as a medium in the serialization method: Method (5) A: m1=PxAB1: m1B1:m2=m1y1]]> B1A: m2AB2m2B2:m3=m2y2]]>B2A: m3A: Km=hash(m3(1/x))

The process in the method (5) of using a combined key derivation function to reduce Alice's exponent calculation in deriving K can be extended to any number of servers 103 and 104 in various ways. In this method, Alice should send the proof of her knowledge of m1 to the server B1, the proof of m2 to B2, and so on.

However, when the servers 103, 104 act as the medium in the calculation, and Alice does not have access to the intermediate results, another method may be needed to prove her effective participation. A special example of the structure of two servers using the combined key derivation function is shown in Figure 5, where Alice only directly communicates with the server B1. More specifically, FIG. 5 is a flowchart describing an exemplary method 500 representing the operation of a client 101 communicating with only one of the two servers 103, 104 in accordance with the principles of the present invention.

In step 501, when registering, store {UserID, yi, V} on each server 103, 104, encrypt a copy of the hash of the password (Hp=hash(P)) and store the user's private key U In the dictionary related to the user identity {UserID, encrypt(Km, {Hp, U})}. Note that the encrypted container includes a message verification code to ensure that the container cannot be modified to break U without destroying Hp.

When logging in, in step 502, a group element (P) is created, and the group element (P) is a function of the appropriate password input (as described above). In step 503, a secret key part (m1=Px) is formed. In step 504, the secret key shared part is sent to the server B1103.

In step 505, a secret key sharing part (m2=m1y1)]]> is formed on the first server (B1) 103. In step 506, the server B1 records the secret code in the short-term storage, and in step 507, sends the secret key shared part (m2) to the server B2104. In step 508, Alice obtains her encrypted key verifier Hp and private key U from the public dictionary (step 508 can be performed at any convenient time). In step 509, a secret combination form of two key parts (m3=m2y2) is formed on the second server (B2) 104. In step 510, the second server (B2) records m3 in the short-term memory (note that he records the response value, not the request value. See further description below). In step 511, B2 sends m3 to B1, and B1 forwards it to Alice. In step 512, Alice101 does not secretly combine the shared parts and creates her master key Km=hash(m3(1/x)). Note that Km=hash(m3(1/x)), the exponent used for key derivation is reused.

In step 513, using Km, the client 101 decrypts the dictionary data to retrieve Hp and U. In steps 514 and 515, if Hp is not equal to hash(P), the client 101 stops. In step 516, the client 101 uses her private key U to create a signed message m4 containing the secret key m1 and the secret combined key shared part value, and sends it to B1 as proof that she is acting on behalf of the legitimate user. B1 also forwards the message to B2. In step 517, the server B1103 uses the user's private key V to verify the signature on m1 in the message m4. In steps 518 and 519, if the signature on m1 is verified and m1 is found in the short-term list of suspicious login requests, the secret key shared part m1 is deleted from the list.

In step 520, the server B1103 uses the user public key V to verify the signature on m3 in the message m4. In steps 521 and 522, if the signature on m3 is verified and m3 is found in the short-term list of suspicious login requests, the secret key shared part m3 is deleted from the list.

In this case, B1 is the intermediary between Alice and B2. Alice proves to B1 the knowledge of the requested value Px and proves to B2 the response value knowledge. A change like this is needed because the server B2 may not be able to believe that B1 is honest, and it needs to have proof that the specific value known to B2 and Alice is used in the Km calculation. In this case, the specific value can be a server input value or a server response value.

Note the asymmetry of the verification operations of B1 and B2 in the foregoing exemplary embodiment. It may be desirable to use another method, where B1 and B2 perform similar operations. For example, both can store input request values (m1 for B1 and m2 for B2) in the short-term list and perform verification operations by checking both. When a signature is received, where the request or response value matches the value stored in the short-term list, then the key retrieval process can be considered valid. The hash function in all these methods can be implemented as a one-way hash function of a variable as a fixed-length bit string. Multiple variables can be connected, as shown in the implementation of the SHA1 standard hash function discussed in "Secure Hash Standard", FIP 180-1, US National Institute of Standards and Technology: hash(x,y)=SHA1( x|y) Other similar key derivation functions are well known.

The validity of Km and the existing server verification. Because the security of the communication channel cannot be counted on, the user's client 101 performs the validity check of the combined master key before using the combined master key in any way that displays information to the opponent. If the validity check fails, the user aborts the process.

One way for users to check Km is to obtain another message that has been symmetrically encrypted with a key based on the correct registered value of Km. The user can obtain the encrypted message from any convenient place, such as any authentication server 103, 104. Using the agreed value for Km, the user decrypts the message and performs a necessary check for the validity of the decrypted data. If it is invalid, the client 101 will abort the process and ensure that information about the agreed value of Km is not displayed.

One way to confirm the message is to embed a large fixed system constant value J in the data. When the decrypted value matches J, the client 101 is assured that the key is correct. However, depending on the encryption system, there may be concerns that the adversary can specially construct the message in order to decrypt messages with several different keys to generate plaintext data containing the value J. But this should not be possible in a well-designed encryption system. One way to prevent this is to make J a function of the password.

In one embodiment, J is calculated as a one-way hash of the password, such as used in SHA1 ("J"|password). The client 101 uses Km to decrypt the information and compares the decrypted value of J with SHA1 ("J"|password), and if they match, assumes that Km is valid. If they do not match, the client 101 immediately aborts the verification process and ensures that the value derived from his invalid value for Km is not validated against potential opponents.

Confirmation of Km implies confirmation of all the enlarged key shared parts used to create Km.

Another problem that may cause concern about the small subgroup restriction of the shared part is that the opponent controlling the network 102 may only return the small subgroup, like identity element 1, and not Py. In the case that all server responses are small group elements, Km will be set to one of the small values. For example, in the special case where all server responses are 1, Km is calculated as having a constant value, such as: Km=hash(11/x, 11/x,...)=hash(1, 1,... ).

Note that with the preferred confirmation method for Km, the subgroup restriction will not be a problem, but if the value used for J is a fixed system constant, it will be a problem. In this case, the attacker can construct the confirmation data so that regardless of the password, the cell decrypts the message to always display the known fixed value for J. Similarly, in the case where {y1, y2,...} are all elements of a small subgroup, the adversary can construct a message so that it is possible that the client 101 will decrypt the message in order to find the importance of a fixed value for J opportunity.

Another way to prevent the small subgroup from restricting K is to make the client 101 directly detect this, such as in the US patent application serial number 08/823/961 and S. Bellovin and M. Merrit, named "Encrypted Key Exchange: Password-based protocolssecure against dictionary attacks", Proceedings of the IEEESymposium on Research in Security and Privacy, May 1992 and W. Diffie, PCvan Oorschot, and M. Wiener, named "Authentication and Authenticated Key Exchanges", Designs Codes and Cryptography, 2, 107-125, (1992). In order to reduce the number of special cases that the client 101 must check, the client 101 can also multiply the received value to make the result a smaller set of elements, perhaps the power of the set {1}, and then perform these cases Tested as described in US Patent Application Serial No. 08/823,961. By excluding those special cases, it is possible to safely use more kinds of confirmation tests for Km.

Note that it is always possible to control the use of {y1, y2,...yN} and make special guesses for the heuristic attack of the person who uses the value of P. The purpose of restoring this time is to make the opponent speculate on P at least once in each run, which is not what the protocol cares about.

The variables in the group parameters usually assume that the system parameters of the group to be used by the group, including the modulus m and any necessary factors (m-1), are fixed system parameters built into the client and server implementations. These values may be used for all users of the system 100.

In addition, these methods can use any appropriate group, such as dotted lines on the elliptic curve, as used in the Diffie-Hellman elliptic curve encryption method and in IEEE Std 1363-2000, IEEE Standard Specifications for Public-Key Cryptography, IEEE, 2000 August 29, 2008, A.11.1, P.131, the general practice in the relevant agreement.

The method can also use variable parameters sent from the server to the client 101, or vice versa. In this case, the parties must be responsible for or pass the original test, or by confirming the certificates issued by the trusted parties for the parameters, or by any other means that give these parties sufficient guarantees of validity to ensure the parameters It is vaild.

The "random" exponential security index {y1, y2,...} should be independent numbers, and choose those numbers that will not be obtained by any potential opponent. As long as they appear to be independent random values from the point of view of any potential opponent, it may be sufficient to derive these numbers from the pseudo-random number generator. A common encryption practice is to use a hash function to derive a sequence of pseudo-random numbers for this encryption purpose from one or more secure sources of random input.

Alternative solutions in the weaker model During the development of the preferred embodiment of the present invention, as described below, additional methods were developed that operate in the weaker model without certain zero-knowledge cryptography techniques. Although not ideal, these methods provide alternative solutions that are useful in special situations. The three embodiments described herein are a single server system 100, a dual server roaming system (AM2) 100, and a multi-server roaming system (AMM) 100 with client storage (herein referred to as AM1).

Alternative solution for CC The AM1 system 100 is an alternative solution for the CC system 100 for a single server environment. The AM1 system 100 eliminates all the special restrictions imposed by the CC, expands the functionality of the user's private key, and still provides the same level of security for the user's password as the CC. When the CC system 100 introduces some harsh restrictions into the use of the basic public key system and the use of the user's private/public key pair, the AM1 method eliminates these restrictions. This method can provide a better alternative solution than CC, which is easier to understand and analyze than CC.

In the AM1 registration, the client 101 selects the PIN code P, the private key Ec and the corresponding public key Dc for the asymmetric encryption system. Here, no special restrictions are imposed on the structure of Ec and Dc. The client 101 uses the function f applicable to the zero-knowledge registration process or any other suitable strong cryptographic system to construct S=f(salt, P)c and V used as the verification data for S. Preferably, this uses a strong extended cryptosystem with low entropy S by default, such as B-SPEKE discussed in the June 1997 Jablon paper.

Client storage: salt security salt value, only stored on client 101. Ds authentication server (AS) public key Ds(V) is the client password verification data sealed by AS Ds(encrypt(K, Ec) under K Encrypted client private key, then sealed Dc client public key for AS, not secret verification In AM1 verification, the user enters P, and client 101 calculates S=f(salt, P), and sends Ds(V) to the server , And perform appropriate strong password authentication with the server based on S and V. This may best be done using the B-SPEKE method.

Once the user is authenticated with S, and also verified with V, the server sends back encrypt(K, Ec) so that only the user who proves the knowledge of S can read it. Preferably, the server can send EncK2(encrypt(K,Ec)),]]> where K2 is a session key generated by the B-SPEKE protocol to prove the clients S knowledge. The client 101 knows K2 and K, and therefore can decrypt Ec.

The client 101 then freely uses the {Ec/Dc} key pair for universal public key purposes. In contrast to the CC system, there are no restrictions on the use of Ec and Dc. The CC system restricts their use to only service transactions with the authentication server. In the same way, the certificate or certificate chain may be related to the client's public key.

Alternative Solution for CC Roaming of Two Servers The AM2 system 100 will now be described, which provides an alternative solution when the CC is modified to be used in a two server roaming solution. The AM2 system 100 is a simpler solution than the CC roaming solution described above.

Registration In the AM2 registration, the user chooses two passwords P1 and P2, preferably two independent values, so that the knowledge of P1 does not show information about P2, or vice versa. The user separately constructs authentication data for each password V1 and V2. The user also selects two random keys Y1 and Y2, and constructs K=hash(Y1, Y2). The user uses the master key K to symmetrically encrypt private data that preferably includes the private key DA.

The first authentication server securely stores {V1, Y1, and optionally encrypt(K, DA))} The second authentication server AS2 securely stores {V2, Y2, and optionally encrypt(K, DA)}} as the client 101 When verifying with P1 or P2, if encrypt(K, DA) is not stored elsewhere, then one of these servers 103, 104 must store it and return a copy of it to the client 101.

The user uses S1 to authenticate to AS1 to obtain Y1.

The user uses S2 to authenticate to AS2 to obtain Y2.

User master key K=hash(Y1, Y2, S1, S2).

The user uses the key K to open her encrypted private key encrypt(K, DA).

Because there are no special restrictions on the EA, one or more servers can publicly store the EA and send it to the client 101 in an unencrypted form.

Verification In AM2 verification, the client 101 uses P1 to obtain the verification session key KS1, and the server AS1 uses the verification data V1 of AS1. AS1 returns Y1 that is symmetrically encrypted under KS1.

At the same time, the client 101 uses P2 to repeat a similar process to authenticate with the server AS2 to retrieve Y2.

One of the two servers 103, 104 returns encrypt(K, DA).

Now DA and EA can be used as full-featured private or public keys.

Another embodiment In another embodiment of AM2, when the client 101 and/or the user, or one or two authentication servers 103, 104 can pre-store or verify the authenticity of the servers public password, pass Sealing the server's stored data with the server's public key can encapsulate it. This makes the data accessible only by that server, assuming that the server is the only entity possessing the corresponding private key. Then, as needed, this sealed data group can be stored on the client 101 or other authentication servers.

Also note that this method adjusts the number of servers 103, 104 in various ways, where N>2. The process for registering and obtaining the key sharing part from the Nth server may be the same as the process for the first or second server 103, 104. Of course, the following formula can be used to calculate the combined key K=hash(K1K2...Kn).

The following discusses the adjustment problem and launches to solve the fault tolerance problem to allow only m servers 103 and 104 out of n to be used for successful verification, where n>m>1.

The non-zero knowledge multi-server approach will now describe the AMM system 100 used in a multi-server environment. The AMM system 100 operates in a weaker security mode than the preferred multi-server roaming system 100 described above. An example does not use the zero-knowledge key agreement at all, but still maintains the feature that each Bi does not store keys or decipherable data in his database. Discuss the design and or comparative limitations of the system 100.

Each AMM server Bi stores the yi value for the user, as in the preferred system 100 described above. Each Bi receives P from Alice, but in an unsecret form. He responds with K=hash(P, yi). Since Bi does not store any password export data, there is no threat of dictionary attacks on the stolen database.

For each server Bi, ABi: PBiA: Ki=hash(P, yi), calculate Km and prove it according to the above.

This method needs to use the communication channel for additional protection, otherwise the eavesdropper can attack the P-to-dictionary. One solution here is to use an SSL/TLS server to verify the channel.

Restriction: The attack on BoB does not implement effective restrictions in the AMM system 100 because the password may be stolen and used on the server. An attacker who gains highly privileged access to Bob may also have the opportunity to maliciously alter Bob's software. Such changes can be done by malicious administrators, malicious or curious hackers, or even indirectly through virus patches or updates. When Bob briefly receives the value P for the user of the system 100, the patching software can control, intercept, and collect these passwords, although such a database is usually not presented on the server 100.

Limitations: Attacks on communication channels Another limitation of AMM, or any other non-zero-knowledge multi-server method, is that it requires some other means to protect the channel to prevent eavesdropper dictionary attacks on P. When implementing this operation with SLL or some other protocol, the process places additional requirements on the client 101 to maintain a key or certificate that tends to make the system 100 weaker or unacceptable for roaming solutions.

There may be many non-zero-knowledge forms of password verification, but usually Bob receives information to initiate his dictionary attack every time these protocols are run. Therefore, this information may also be leaked to an attacker who endangers Bob. The zero-knowledge cryptographic protocol is essential to prevent attacks that compromise effective servers.

The current simplified security model. The advantage of our methods is that they operate under a very simple security model. The client computer 101 does not need to store any user or server specific status, and we do not need any prior secure or authenticated communication channels between any components. This model is simpler than the model provided in any previous method for secure multi-server password authentication.

In a preferred embodiment, the client 101 does not need to maintain a long-term certificate for the client or any server. This more simplified model reduces the additional points of failure that may occur in the general SSL/browser model of multi-root certificate authentication. The SSL/browser model creates multiple potential weak links in a complex chain of trust, which requires actual actions and/or attention from users. Our more simplified model relies on the verification of the previous servers 103, 104 to eliminate the actual risks that are typically "human error" in the model.

The invention has a wide range of applications. The benefits of the method of the present invention are not limited to roaming applications. For non-roaming applications, the above-mentioned preferred system 100 is used to retrieve the user master key Km, and the Km is used to access or decrypt the certificate stored locally on the user's personal desktop computer. Using non-special software, this provides undecipherable local storage protected by passwords selected by small users and remotely stored key sharing partial factors {y1, y2,...}. There is also another guarantee that Km and protected data will not be shown to the adversary, even if he attacks all relevant web servers 103, 104, as long as he does not access the local laptop data at the same time.

It is possible to use the master key to create a symmetric key to decrypt private data stored in a publicly accessible location, create a symmetric key to verify, and directly derive the public/private key pair used to receive the sealed message.

The aforementioned system 100 provides a software-based alternative solution that may be best for smart cards.

The detailed protocol description uses the notation outlined in Table 1 below, and the detailed implementation of the protocol is given below.

Table 1. The meaning of the symbols (reasonable example) Ci is a list of certificates stored by Bi P. The elements of Gq derived from the password [hash(password)2rmod P] are Gq prime number q power group [where Zp*, p=2rq+ 1, 22j>q>22j-1, 2k>p>2k-1, p and r are prime numbers]hash password hash function [SHA1]j is used to reside the security parameters of brute force attacks [80]K is used to reside The security parameters of the NFS discrete registration attack

[1024] The shared key between KiAlice and Bi [hash(Kmi)] KmAlices master key [the hash of the shared part of the connection, hash(S1...Sn)mod 2j]password user password, 0 <password<22j[SHA1(ASCII password)] Ri secret key shared part=pxyiSi key part=(P)yiU Alices private signature key UKAlices encryption private key=encrypt(K, U) V is consistent with U Alices public key yi is stored by Bi. Alices secure shared part exponent encrypt(x, y) A message encrypted with a symmetric key x ydecrypt(x, y) A message decrypted with a symmetric key x ysign(x, y) with private The parameters of the message y (so that the message y can be read) signed by the key x. Two security parameters are defined in this protocol, j represents the bit strength required for a symmetric function, and k represents the number of bits required by the modulus of the asymmetric function.

Define Gq as a subgroup of the qth power in Zp*, where p, q, and r are odd prime numbers, p=2rq+1, 2k>p>2k-1, rq, and 22j>q>22j- 1. Use a function to map the password to the group element PεGq, where P=hash(password)^2rmod p.

(Another solution might be to use an elliptic curve group in GF(p) with a point group approximately equal to p to the power of rq, a prime number q, and a small cofactor r[1,100]. In this case Next, replace all exponents with scalar point multiplication and define P=r.pojnt(hash(password)), where point uses hash(password) to arrange pseudo-random number generators to find any point on the curve. This is D. Jablon, named "Strong password-only authenticated key exchange", discussed in ACM Computer Communicatoins Review, vol. 26, no. 5.10.1996.

registered. Alice selects the key P, calculates the user P:=hash(password) 2r, and creates a private key U and a corresponding public key V suitable for executing digital signatures. Then, she creates n key sharing parts, which uses randomly selected yiR[1,q-1] to form every i-th shared part SiGq as Si:=Pyi]]>. Then, she uses Km:=hash(S1...Sn)mod2j to create the master j-bit symmetric key, press Uk:=encrypt(Km, U) to create her encrypted private key, and to create her Key verification data proofPKm:=hash(Km||g).]]> In order to register these certificates, the client 101 sends Alice's certificate to be stored in the list Ci on each Bi. They must use a verification communication method that ensures the correct identity of A to perform these actions: Client: for each i [1, n, {enroll, A, yi, V, Uk, proofPKm} BiServers: change (A, yi, V, Uk, proofPKm) are stored in Ci for verification and retrieval. To verify the certificate retrieval, the client 101 and the servers 103, 104 perform the operations listed below. During this process, each server maintains a list Li containing records of suspicious invalid access attempts.

Client: select random number X[1, q-1] Q: Pxmod p{request, A, Q) server server: retrieve {A, yi, V, UK, proofPKm} from Ci

t: CurrenTime appends {A, Q, V, t} to LiRi:Qyi]]>{reply, Ri, Uk, proofPKm}Client client: i[1,n], Si: Ril/xmodpK: =hash(S1S2...Sn) For each if proofPKme hash(kg), stop U: = decrypt(K, UK) for Qin{Q, Q1, Q2,... .}{confirm, Q', sign(U, Q')}Servers} server: for each received {confirm, Q', Q'u} to any {A, Q, V, t in Li }, where Q=Q' Use V to verify sign(U, Q') as the signature of Q. If the signature is valid, remove {A, Q, V, t} from Li {A, Q, V, t} periodically, maybe every minute, every Bi scan It is used for a list Li of invalid inputs {A, Q, V, t} that are too large to accept (CurrentTime-t). When an invalid input is found, the input is eliminated from the list, and an invalid attempt event for user A is triggered. Note that as an optimized solution, Alice only needs to calculate and send a single signature to verify the list of all recent Q values to all servers 103, 104.

Performance improvement When comparing the FK1 protocol with our protocol, several factors should be considered, including the cost of the basic secret function group algorithm, the cost of the related verification functions, and the cost, benefits, and risks of using each server's server verification channel .

The cost of covert operations. Let the safety factor j=80 and k=1024, the new protocol provides significantly higher performance than the FK1 protocol. Using q=(p-1)/2, each FK1 server must execute one 1023-bit exponent and the client must execute two 1023-bit exponents.

When using p=2rq+1 as shown in our method, we use the power subgroup 2160>q>2159. In the latter case, the calculation of two clients and one server was reduced to about 1/6 of the former. Given different ways to estimate the equivalent symmetric and asymmetry safety algorithms, your mileage may change.

However, when Alice has to execute an 864-bit index in P:=hash(password)2r, the customer benefit cannot be realized. However, some advantages such as those described below can be utilized in another structure of P.

The comparison so far ignores all the additional savings by eliminating the need to establish a server authentication channel. However, by verifying all servers of the message, the savings are at the cost of allowing some online guesses made by the fake servers 103, 104 and possibly revealing the identity A to the eavesdropper.

Another structure of P. Another structure P can be used: g1·g2hash(password) mod q. This uses fixed references g1 and g2, and g1 and g2 are two random elements of the q power that have no known exponential relationship with each other. One possibility for generating universally acceptable values for g1 and g2 is to use a hash function as a random predictor, as used in g1:=hash("g1")2rmodp.

With the same security parameters, another structure requires three 160-bit indices for the client 101 and one for the server. When compared with FK1, this structure reduces the client cost by 53% and the server cost by 84%.

The cost of the verification function. The above method requires a digital signature for the user to prove the authenticity of her hidden secret code set. Fortunately, the client signature generation can be done only once to create a message containing one or more of the most recently sent password requests for all servers 103, 104, and when RSA is used, the server signature verification is very fast.

In addition, in order to reduce the cost of the public key signature operation on the client 101, using the shared security key Ki=hash(Kmi) registered with Bi, Alice may use an encrypted message verification code instead of "signing" her secret password. In this case, she registers a unique key and constructs a unique signature for each server.

Security parameters. A few simple variables related to the safety of the present invention are described below.

Each key sharing part is strong security. Only the key data for each shared part is stored in the security value yi on the promising security certificate server, and only released in the index of the improved Diffie-Hellman exchange. The calculation is based on a prime number in the form of p=2rq+1, which severely limits the information about yi that an attacker can obtain. All that is determined by the heuristic attack is whether yi has the same factor as 2rq. However, since yi is random and all factors except 2 are large, the probability tends to zero. Therefore, as mentioned in the Ford and Kaliski paper in June 2000, the only information that can be determined is the low level of yi.

Alice has zero information about P in her secret request message, because for any displayed value, there is an equal probability of any given P. Similarly, even if additional data appears, such as the Pxy value, it will not help the attacker determine P, because y has nothing to do with P for any data known to the attacker.

The possibility of leaking information from Alice to the opponent of the control channel in her confirmation message can be ignored, because if she receives any invalid response from the server, she will abort before releasing all useful information. Due to the combined hash function, if a shared part of the master key is incorrect, consistent with the overwhelming possibility, the combined key will be incorrect. Similarly, if the master key is incorrect, the hash value of the verifier will be incorrect for the same reason. So if they really match, Alice can be sure that her master key is correct.

The communication channel does not have to guarantee the integrity of the Uk and proofPKm values sent by the server. To understand why, suppose there is a malicious party who forged these values and sent them to Alice. In the worst case, the adversary will either verify a single guess of the password in each run or perform a service suppression attack. If the client 101 is designed to not tolerate invalid speculation more than the server, then these attacks are generally equivalent to possible attacks in the secure channel model. Fortunately, people tend to have low tolerance to logic errors and may complain to system administrators about looping issues. However, the client 101 must be designed to ensure that at least the user is aware of all failures. In both models, in at least one direction, the adversary can make a limited number of online guesses and cause a denial of service by modifying or deleting messages.

The above-mentioned Hash(password)2r function and other structures guarantee the q-th power of the elements and prevent the problems of passwords and short exponents in the index proposed in the D. Jablon paper in 1997 and the Ford and Kaliski paper in June 2000.

Another way to calculate the short exponent reduction is to use a shorter exponent. For example, in a group with p=2q+1, 1023 bits q, one might use an exponent in the range [1,2160-1]. The short index used in Diffie-Hellman was discussed in a paper in van Oorschot, et al, May 1996. When short exponents are used, the Pollard lambda method is the most effective known method for calculating random exponents x-gx for a known fixed base g. λ Discrete Logarithm calculation requires operations related to x1/2. However, there is no guarantee that an easier method will not be discovered in the future.

Consider the termination protocol, in which the user simply displays the hidden secret code series and no other information is valid for the attacker. When using the random index xR[1, o(Gq)] that is averaged by actual size, the Px value shows zero information about P.

When using short exponents xεR[1,m]m<<q, security may require additional assumptions that are tricky to calculate, and it is hoped that unnecessary assumptions can be eliminated. Whether this assumption is valid is still an open question.

Therefore, with regard to the (perhaps unnecessary) concern that short exponents introduce undesirable assumptions, the preferred method of reducing the calculation is to use subgroups that are significantly smaller than the prime power of the modulus.

The present invention uses a simpler model than that used in the prior art. In operation, the problems inherent in the system are eliminated. In this system, people must safely identify the servers 103 and 104, but this is not necessary for the present invention. The present invention uses a simpler model to achieve all previous purposes without the need for a server to store keys or certificates, has increased performance and enhanced accountability in order to better manage human errors in password input. These methods can also provide the same level of security and use relatively little calculation to prevent login attacks.

Therefore, a system, method, and software for remote password verification using multiple servers are disclosed. It should be understood that the above-mentioned embodiments are merely illustrative of some of the many specific embodiments that represent the application of the principles of the present invention. Obviously, those skilled in the art can easily derive many and other solutions without departing from the scope of the present invention.