Password-based authentication protocol secure against server's dictionary attack

[0001] This application relies for priority upon Korean Patent Application No.2002-0010313, filed on Feb. 26, 2002, the contents of which are hereby incorporated by reference herein in their entirety as if fully set forth herein.

[0002] The present invention relates to a protocol for the authentication of a user, and more specifically to a password-based protocol secure against a server's dictionary attack.

[0003] If an application server is to be accessed for a network service, it is necessary for a terminal to succeed in an authentication process from the application server.

[0004] In this case, the authentication process implies a step of verifying if the accessing counterpart is a really authentic one whom the party intends to communicate with.

[0005] The approaches for user authentication can be classified into three categories depending upon a basis element of an authenticating process. An approach is a biometric authentication.

[0006] For instance, a tone of the voice, a radioscopy, or a fingerprint can be employed for the authentication of a user. Another approach is a token-based authentication.

[0007] For example, an ID (identification) card or a smart card personally carried by a user can be utilized for a safe authentication of a genuine user. The other approach is a knowledge-based authentication.

[0008] For instance, a password or a PIN (personal identification number) that is memorized by a user is frequently utilized for authentication.

[0009] Comparing the above-mentioned three kinds of approaches, it should be noted that both the first and the second approaches guarantee relatively a robust security despite of the cost expensiveness for the hardware implementation.

[0010] In the meanwhile, the third approach, which is based on knowledge such as password, has a merit of cost effectiveness because no further investment for hardware equipment is required.

[0011] As a consequence, a password-based authentication protocol is widely used as an essential technology for a roaming service, especially of an information protection company.

[0012] However, the password based authentication approach has a technical limitation because the password of a user tends to be selected with a combination of characters that is easy to be memorized, i.e. therefore with quite low entropy in terms of the quantity of information.

[0013] As a consequence, it is possible for an attacker to exhaustively guess the user's password by a dictionary attack and likely to determine the user's password if either the hash of the password and/or the ciphertext using the password is exposed to the attacker.

[0014] Here, the dictionary attack means that an attacker exhaustively guesses a user's password in accordance with a specific rule from the trial list of possible passwords.

[0015] In order to surmount the weakness of the password-based approach against a dictionary attack, it has been recommended to change the password from time to time and/or to use a longer and complicated combination of characters for a password.

[0016] However, the above-mentioned remedies cannot resolve the underlying issue of a dictionary attack on a user's password.

[0017] In 1992, S. M. Bellovin and M. Merrit proposed a password-based protocol secure against a dictionary attack for authentication and key exchange (Password-based protocols secure against dictionary attacks, Proceedings of the IEEE Symposium of Research in Security and Privacy, Oakland, May 1992).

[0018] The approach proposed by Bellovin and Merrit, however, still suffers from vulnerability against a dictionary attack.

[0019] In 1996, D. Jablon proposed a novel concept of SPEKE (strong password encrypted key exchange) secure against a dictionary attack, which is a further development of the previous approach of Bellovin and Merrit (Strong password only authenticated key exchange, Computer Communication Review, ACM SIGCOMM, Vol. 26, No. 5, pp.5-26, October 1996).

[0020] The afore-mentioned SPEKE is utilized for a roaming service by Entrust, which is a company for PKI (public key infrastructure). The SPEKE, however, still has a shortcoming that the attacker's acquisition of a user's password is possible if a server is attacked because the user shares the password with the server.

[0021] In order to resolve the above-mentioned issue of the vulnerability of the server against an attacker's dictionary attack, Jablon et. al. proposed a so-called extended password key exchange protocol wherein only a password verifier can be stored at a server for confirming a user's password (Extended password key exchange protocols immune to dictionary attacks, Proceedings of the Sixth Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WET-ICE '97), pp. 248-255, IEEE Computer Society, Jun. 18-20, 1997, Cambridge, Mass., USA).

[0022] The Jablon's approach, however, still suffers from a technical limit of a possible dictionary attack when password verifier is exposed to an attacker even if the password is concealed itself. Therefore, it is still necessary to come up with a novel method that ensures security and robustness against a dictionary attack for an approach based on a password verifier because the password verifier is shared with a server.

[0023] In the year of 2000, W. Ford and B. Kaliski from VeriSign proposed a novel and quite robust password-based protocol.

[0024] The proposed approach can be thought to be quite robust to some extent because a multiple of servers should be simultaneously attacked for the success of an attacker's exhaustive guessing of a user's password. The feature of the Ford-Kaliski approach is that the key is generated with the assistance of a multiple of servers (Server-assisted generation of a strong secret from a password, Proceedings of IEEE 9th International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, NIST, Gathersburg, Md., Jun. 14-16, 2000).

[0025] Since the degree of complexity due to its randomness of the generated key is higher than that of the user's password, it is the stronger and more secure against a dictionary attack. The above mentioned authentication protocol proposed by Ford and Kaliski is disclosed at the U.S. Patent Publication No. 2001/0055388A.

[0026] FIGS. 1A and 1B illustrates an initial registration process and an authentication process of a user in accordance with the prior art of Ford-Kaliski, respectively.

[0027] Referring to FIG. 1A, it is assumed that a server authentication and a secret channel have been set up for an initial registration process. The parameters cited in the following description can be summarized as the following.

[0028] The letter p represents a prime integer wherein p2q1 (q is a large prime integer), while the letter g represents a primitive element of the group and has a relationship of order (g)q. Further, f is a function that maps passwords to elements of multiplicative order q in Z_p*.

[0029] In addition, KDF( ) is a computing function for an authentication key, while OWF( ) is a one-way function. Further, PWD represents a user's password.

[0030] Referring to FIG. 1A again, wf (PWD) is calculated at a user's terminal (10) with a user's password PWD and a pre-defined function f. Thereafter, a number k (1kq1) is randomly selected and r (w^k mod p) is calculated at the user's terminal (10).

[0031] Finally, the user's terminal 10 sends both the user's identifier A and the number r, namely (A, r) , to key servers KS₁, KS₂, . . . , KS_n (100, 101, 102, 103) (steps S20, S21, S22, and S23).

[0032] In the meanwhile, each key server KS_i (i1, 2, . . . , n) (100, 101, 102, 103) generates a random number d_i (1d_iq1), respectively, for the user's terminal (10) and calculates a number S_i, where S_ir^d_i mod p (i1, 2, . . . , n).

[0033] Thereafter, (A, d_i) is stored at a database of each key server and each S_i (i1, 2, . . . , n) is sent to a user's terminal (10) (steps S24, S25, S26, and S27). Finally, a number R_i (i1, . . . , n) is calculated at the user's terminal (10) with use of the numbers S_i (i1, . . . , n) and a number k from the following relationship.

[0034] Thereafter, the user's terminal (10) calculates an authentication key K with a function of KDF( ).

[0035] Now, a series of numbers K₁, K₂, . . . , K_m are calculated at the user's terminal (10) with equation (3) and safely delivered to a set of application servers AS_j (j1, . . . , m) (111, 112, 113).

[0036] It should be noted that a multiple of numbers K_j (j1, . . . , m) are delivered to a corresponding application servers AS_j (j1, . . . , m) (111, 112, 113), respectively, only once during the step of a user's registration.

[0037] Each application server AS_j (j1, . . . , m) (111, 112, 113) stores its own key K_j (j1, . . . , m) in a safe place. In some practical applications, it may be possible that the key servers and the application servers should be identical.

[0038] Now, the process for a user authentication according to the prior art can be understood with reference to FIG. 1B. Referring to FIG. 1B, a number wf (PWD) is calculated at a user's terminal (10) with a function f and a password PWD for the user authentication.

[0039] Thereafter, a number k (1kq1) is randomly selected and a number r is computed from a relationship of rw^k mod p at the user's terminal (10). The user's identifier A and the number r, namely (A, r), are sent to each key server KS₁, . . . , KS_n (100, 101, 102, 103) (steps S31, S32, S33, and S34).

[0040] Then the key server KS_i (i1, . . . , n) (100, 101, 102, 103) extracts d_i from the database (A, d_i). Now, each key server KS_i calculates a set of numbers S_i with d_i from the relationship of S_ir^d_i mod p, respectively, and transmits S_i (i1, . . . , n) to the user's terminal (10) (steps S35, S36, S37, and S38).

[0041] Finally, numbers R_i are computed at the user's terminal (10) from the number k and S_i (i1, . . . , n) that has been received from the key servers KS_i (i1, . . . , n) (100, 101, 102, 103).

[0042] The authentication key K and K_i are computed using KDF and OWF at the user's terminal (10).

[0043] In the meanwhile, a set of challenges c_j (1c_jq1) are generated at each application servers AS_j (j1, . . . , m) (111, 112, 113) and sent to the user's terminal (10) (steps S39, S40, and S41) Thereafter, the response OWF(K_j, c_j) to each challenge c_j is computed at the user's terminal (10) and sent to the application servers AS_j (j1, . . . , m) (111, 112, 113) (steps S42, S43, and S44).

[0044] Finally, the application server AS_j (j1, . . . , m) (111, 112, 113) computes OWF (K_j c_j) from the keys K_j (j1, . . . , m) stored at its database and then compare the computed value with the one that was sent from user's terminal (10) for the verification of authenticity.

[0045] In the foregoing paragraphs, both the initial registration process and the user authentication process of the Ford-Kaliski method have been explained in detail as a prior art.

[0046] The prior art as disclosed in Ford-Kaliski approach still has a shortcoming in that an attacker can get information that is enough for a dictionary attack if an attacker camouflages the key servers and/or the application servers. This is because the prior art does not include a step of authenticating the servers during the user authentication process.

[0047] Therefore, even the authors of the prior art, Ford and Kaliski, themselves pointed out the above-mentioned shortcoming at their published paper and made a recommendation to use an authentication protocol such as SSL (secure socket layer) for a tentative remedy.

[0048] The technical problems included in the Ford-Kaliski approach can be more easily understood with reference to FIGS. 2A and 2B. Referring to FIG. 2A, it is assumed that a couple of key servers and an application server are chosen for the simplicity of the explanation.

[0049] Now, when the numbers (A, r) are sent to key servers from the user's terminal (10), an attacker masquerading as key servers (200, 201) generates numbers d₁* and d₂*, and computes numbers S₁* and S₂*, which are to be transmitted to the user's terminal (10) (steps S52 and S53).

[0050] In this case, the user's terminal (10) is to compute an authentication key K* that is totally different from the genuine authentication key K generated during the initial registration process.

[0051] Furthermore, the keys K₁* and K₂* are also computed for a first application server and a second application server, respectively.

[0052] Now, if an attacker sends a challenge c₁* to the user's terminal (10) by camouflaging as an application server AS₁* (202) (step S61), the user's terminal (10) is deceived and provides the attacker with OWF (K₁*, c₁*) as a response (step S62).

[0053] Finally, the attacker (202) can try a dictionary attack with the following equation (11) from the information OWF (K₁*, c₁*) transmitted from the user's terminal (10).

[0054] In order to resolve the above-mentioned technical shortcoming, Ford and Kaliski recommend a conventional SSL to be used during the step of the user authentication.

[0055] In view of these problems, there is a need in the art for a password-based protocol, especially for a protocol secure against a server's dictionary attack, which is not subject to these limitations.

[0056] Accordingly, it is an object of the present invention to provide a password-based authentication protocol secure against a server's dictionary attack.

[0057] It is also an object of the present invention to provide a password-based authentication protocol that does not need an additional use of SSL for the security against a server's dictionary attack.

[0058] Yet it is another object of the present invention to provide a password-based authentication protocol that enhances the computing efficiency for the generation of authentication keys as well as the security against a server's dictionary attack.

[0059] In accordance with the present invention, a method for password-based authentication includes the following steps.

[0060] A user's identifier A with the number s computed from a secret data that is learned by heart are sent to a multiple of key servers KS_i (i1, . . . , n). Then each key server KS_i (i1, . . . , n) computes B_i (i1, . . . , n) with its own key (x_i, i1, . . . , n) and number s, followed by a step of sending the computed numbers B_i (i1, . . . , n) to the user's terminal (10) while the user's identifier A is stored at a database. The authentication key K is then generated with public key y of the group KS_i (i1, . . . , n) and B_i (i1, . . . , n).

[0061] These and other more detailed and specific objects and features of the present invention are more fully disclosed in the following specification, references being had to the accompanying drawings, in which:

[0062] FIGS. 1A and 1B are schematic diagrams illustrating the initial user registration process and the authentication process, respectively, of Ford-Kaliski approach as a prior art

[0063] FIGS. 2A and 2B are schematic diagrams illustrating a shortcoming of Ford-Kaliski approach as a prior art.

[0064] FIG. 3A is a schematic diagram illustrating a step of initial user registration in accordance with the present invention.

[0065] FIG. 3B is a schematic diagram illustrating a step of authentication in accordance with the present invention.

[0066] One of the features of the present invention is that there are provided a set of private keys x_i (i1, . . . , n) individually for each key server KS₁, KS₂, . . . , KS_n, and a public key y of the group KS₁, KS₂, . . . , KS_n. First of all, the parameters and terminology are briefly explained for the understanding of the specification.

[0067] In the followings, p is a prime integer where p2q1 (q is a large prime number). Additionally, g is a primitive element of the group with order (g)q.

[0068] In the meanwhile, f is a function that maps passwords to elements of multiplicative order q in Z_p*. Additionally, KDF ( ) is a function for computing an authentication key while OWF ( ) is a one-way function. The parameter PWD denotes a user's password while x_i (i1, . . . , n) is a private key for individual key server KS_i (i1, . . . , n) . Now, y is the public key of the group KS_i (i1, . . . , n). $\begin{array}{cc}y=\underset{i=1}{\overset{n}{}}{g}^{X_i}\mathrm{mod}p& \left(12\right)\end{array}$

[0069] FIG. 3A is a schematic diagram illustrating a step of initial user registration in accordance with the present invention.

[0070] Referring to FIG. 3A, a number w is computed from a relation of wf (PWD) at a user's terminal 10 with a user's password PWD and a function f. Thereafter, a number s is computed with a relationship of sg^zw mod p from a randomly selected number z (1zq1).

[0071] Finally, the computed number s with the user's identifier A is sent to the key server KS_i (i1, . . . , n) (100, 101, 102) (steps S80, S81, and S82).

[0072] Thereafter, each key server KS_i (i1, . . . , n) (100, 101, 102) computes B_i(s)^x_i mod p (i1, . . . , n) , transmits B_i to the user's terminal (10) and stores the user's identifier A at database (step S83, S84, and S85).

[0073] Now, the user's terminal (10) computes the authentication key K and K_j (j1, . . . , m) from the following equation. $\begin{array}{cc}K=\mathrm{KDF}\left(\left(\underset{i=1}{\overset{n}{}}{B}_i\right)/y^z\mathrm{mod}p\right)& \left(13\right)\end{array}$ K_jOWF (K, j) (j1, . . . , m)(14)

[0074] The user's terminal (10) sends (A, K_j) to each application server AS_j (j1, . . . , m) (111, 112, 113) (steps S86, S87, and S88). Now detailed description regarding the user authentication process will be made in the following with reference to FIG. 3B.

[0075] Referring to FIG. 3B, the user's terminal (10) computes sg^zw mod p (wf(PWD) ) from the user's password PWD and a random number z. The computed number s with A are then sent to each key server KS_i (i1, . . . , n) (100, 101, 102) (steps S90, S91, and S92).

[0076] Now, each key server KS_i (i1, . . . , n) (100, 101, 102) checks if the user is the one who is registered at database, computes B_i(s)^X_i mod p (i1, . . . , n), and sends B_i to the user's terminal (10) (steps S93, S94, and S95).

[0077] Then, the user's terminal computes the authentication key K and K_j (j1, . . . , m) from the following equation. $\begin{array}{cc}K=\mathrm{KDF}\left(\left(\underset{i=1}{\overset{n}{}}{B}_i\right)/y^z\mathrm{mod}p\right)& \left(15\right)\end{array}$ K_jOWF (K, j) (j1, . . . , m)(16)

[0078] Since the degree of complexity due to its randomness of the generated authentication key K is higher than that of the user's password, it is the stronger and more secure against a dictionary attack.

[0079] In the meanwhile, each application server AS_j (j1, . . . , m) (111, 112, 113) generates a challenge c_j (1c_jq1) and sends the challenge to the user's terminal (10) (steps S96, S97, and S98).

[0080] Thereafter, the user's terminal (10) computes a set of responses OWF (K_j, c_j) to each challenge C_j and send them to each application server AS_j (j1, . . . , m) (111, 112, 113) (steps S99, S100, and S101).

[0081] In the meanwhile, each application server AS_j (j1, . . . , m) (111, 112, 113) computes OWF (K_j, c_j) (j1, . . . , m) from K_j (j1, . . . , m) stored at database and compares the computed value with the received response in order to verify the authenticity of the user.

[0082] As a consequence, if the authentication of the user has been completed, the user's private key encrypted with K_j is then forwarded to the user's terminal. Then the user can utilize the private key to perform the cryptographic service such as a digital signature.

[0083] As explained in the foregoing, the password-based protocol in accordance with the present invention can efficiently compute the authentication key K even if the number of key server is increased.

[0084] This is because the protocol in accordance with the present invention requires only a couple of exponent calculation and subsequent (n1) times of multiplication while the prior art of Ford-Kaliski approach needs (n1) times of exponent calculation.

[0085] Furthermore, since the public key y of the group of key servers and a secret random number z are used during the step of computing the authentication key, a camouflaging server that is unaware of a private key of each key server can not get information to mount a dictionary attack on the user's password.

[0086] Although the invention has been illustrated and described with respect to exemplary embodiments thereof, it should be understood by those skilled in the art that various other changes, omissions and additions may be made therein and thereto, without departing from the spirit and scope of the present invention.

[0087] Therefore, the present invention should not be understood as limited to the specific embodiment set forth above but to include all possible embodiments which can be embodies within a scope encompassed and equivalents thereof with respect to the feature set forth in the appended claims.