Abstract:
A protocol designing method that securely performs a password-based authentication and key exchange protocol using a zero-knowledge interactive proof is disclosed. According to this method, various kinds of system parameters required for authentication are first set. Then, a user selects a certain random number in conformity with the set parameters, and sends to a server a message including a user ID, a test number A applying a one-way function, and a first question number generation value X known only to the server and the user. The server, using the message sent from the user, sends to the user a message including an authentication Auth of whether the server possesses a public key, and a second question number generation value Y known only to the server and the user. The user authenticates the server by verifying the authentication Auth, and computes a resultant value c of a secret coin tossing known only to the server and the user and a session key SK. Thereafter, the user sends to the server a witness number B for user authentication. The server that stores a password verifier V for the respective user verifies the witness number B using the value c, and exchanges the session key SK by computing the session key SK. Accordingly, a secure authentication and key exchange can be performed only using the password without the necessity of any tool such as a smart card.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a method of performing a key exchange for user authentication and secure communication using a password in a communication network, and more particularly, to a method of designing a password-based authentication and key exchange protocol using the existing zero-knowledge interactive proof. The user can prove his/her identity only by remembering the password without any other tools, and can securely share a session key to be used for the subsequent communication with a server. Here, the user is the subject that performs an authentication request, and the server is the subject that performs the authentication.  
           [0003]    2. Background of the Related Art  
           [0004]    The user authentication using a password means a procedure in that two subjects participating in the communication confirm if the counterpart is the subject desired to communicate with each other. At this time, any information except for the information required for the user authentication should not be exposed to the counterpart. Also, the key exchange using the password means a procedure in that two subjects participating in the communication share the key. At this time, the shared key should be protected from any eavesdropper.  
           [0005]    Also, since the password is very short and its randomness is not so big, being different from a symmetric-key or public-key encryption system, the user authentication and key exchange protocol using the password is liable to be under offline dictionary attacks.  
           [0006]    The general zero-knowledge proof has been used for the user authentication, but is not secure if the password is used as the key. However, the present invention provides a method of securely performing the general zero-knowledge proof protocol even if the password is used as the key.  
           [0007]    It is known that the currently used authentication protocol is very weak to the offline dictionary attacks. In order to complement this, SRP by Tom Wu, B-SPEKE by David Jacobson, and EKE by Belloving at al have been designed. However, in case of using the password, the security of the existing user authentication protocols has not been mathematically proved. Recently, the security has been proved with respect to a portion of the EKE (encrypted key exchange). Also, protocols having the mathematical security proof have been proposed, but most of them depend on the adhoc design.  
           [0008]    Also, in case of using a public key encryption system without using the password in the authentication protocol, the user should possess a security token such as a smart card that stores the user&#39;s secret key or note of authentication, causing the user inconvenience. Accordingly, the conventional techniques cannot provide the convenience of the authentication and key exchange protocol using the password.  
         SUMMARY OF THE INVENTION  
         [0009]    Accordingly, the present invention is directed to a method of designing a password-based authentication and key exchange protocol using a zero-knowledge interactive proof that substantially obviates one or more problems due to limitations and disadvantages of the related art.  
           [0010]    It is an object of the present invention to provide a method of designing a password-based authentication and key exchange protocol using a zero-knowledge interactive proof that has a mathematical security proof with respect to the offline dictionary attacks, and enables the design of a systematic password-based authentication protocol without depending on the adhoc design.  
           [0011]    It is another object of the present invention to provide a method of designing a password-based authentication and key exchange protocol using a zero-knowledge interactive proof that can perform the user&#39;s own authentication and the key exchange by making the user only remember the password when using the password-based authentication and key exchange protocol defined according to the present invention.  
           [0012]    In detail, the present invention provides a method of systematically designing the password-based authentication and key exchange protocol using a given zero-knowledge interactive proof. According to the present invention, when a certain zero-knowledge proof is given, it can be converted into a new authentication and key exchange protocol.  
           [0013]    Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objectives and other advantages of the invention may be realized and attained by the structure particularly pointed out in the written description and claims hereof as well as the appended drawings.  
           [0014]    To achieve these objects and other advantages and in accordance with the purpose of the invention, as embodied and broadly described herein, there is provided a method of designing a password-based authentication and key exchange protocol using a zero-knowledge interactive proof. According to this method, various kinds of system parameters required for authentication are first set. Thereafter, a user selects a certain random number (r, x) in conformity with the set parameters, and sends to a server a message including a user identifier ID user , a test number A=OWF(r) obtained by applying a one-way function (OWF), and a first question number generation value X known only to the server and the user. The server, using the message sent from the user, sends to the user a message including an authentication Auth of whether the server possesses a public key, and a second question number generation value Y known only to the server and the user. The user authenticates the server by verifying the authentication Auth, and computes a resultant value c of a secret coin tossing known only to the server and the user and a session key SK. The secret coin tossing known only to the server and the user as described above can defend against the offline dictionary attack. After the computation, the user sends to the server a witness number B for user authentication. The server that secretly stores a password verifier V=OWF(f(P)) for the respective user verifies the witness number B using the test number A, the password verifier V, and the value c, and exchanges the session key SK by computing the session key SK. Accordingly, the password-based authentication and the key exchange protocol can be systematically designed using the given zero-knowledge interactive proof.  
           [0015]    Also, according to the present invention, the respective password verifiers that cope with an RSA (Rivest, Shamir, Adleman) problem, a discrete logarithm problem, and a prime factorization problem in a framework of FIG. 1 are secretly stored in the server, the user makes the witness numbers B different from one another to cope with the above problems, and makes verification factors different from one another corresponding to the different witness numbers. They will be explained in detail later.  
           [0016]    As described above, the present invention provides a method that is capable of easily designing a new authentication and key exchange protocol, and that can be correspondingly applied to various problems without a deep knowledge of encryption and without proposing only one authentication protocol as in the conventional technique.  
           [0017]    It is to be understood that both the foregoing general description and the following detailed description of the present invention are exemplary and explanatory and are intended to provide further explanation of the invention as claimed.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]    The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this application, illustrate embodiment(s) of the invention and together with the description serve to explain the principle of the invention. In the drawings:  
         [0019]    [0019]FIG. 1 is a view illustrating a framework of a user authentication procedure and key exchange algorithm according to the present invention.  
         [0020]    [0020]FIG. 2 is a view illustrating a protocol for applying an RSA problem to the user authentication procedure and key exchange framework according to the present invention.  
         [0021]    [0021]FIG. 3 is a view illustrating a protocol for applying a discrete logarithm problem to the user authentication procedure and key exchange framework according to the present invention.  
         [0022]    [0022]FIG. 4 is a view illustrating a protocol for applying a square root problem based on a prime factorization to the user authentication procedure and key exchange framework according to the present invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0023]    The method of designing a password-based authentication and key exchange protocol using a zero-knowledge interactive proof according to the preferred embodiments of the present invention will now be explained in detail with reference to the accompanying drawings.  
         [0024]    [0024]FIG. 1 is a view illustrating a framework of a user authentication procedure and key exchange algorithm according to the present invention.  
         [0025]    First, system parameters are preset before a user  50  and a server  60  perform the protocol (step  100 ). The system parameters are set through the engagement between the user and the server, and the users share the system parameters through the whole system. G is a finite recursive group such as a multiplicative group Z* p  or an elliptic curve group, and g is a generator for generating the finite recursive group. For convenience&#39; sake, the present invention follows a multiplicative group notation. OWF is a one-way function. In the embodiments of the present invention, a one-way function based on the RSA (Rivest, Shamir, Adleman) problem, one-way finction based on the discrete logarithm problem, and one-way function based on the prime factorization problem, etc., are described as examples, but the present invention can be also applied to other one-way functions based on other problems. f(P) is a function that expands the length of a password P so that the password becomes an input value of the OWF, and it is not necessary for f(P) to have the encryption property. V(x) means a symmetric encryption of x with the key V, and V−1(x) means a symmetric decryption of x with the key V. Here, the symmetric-key encryption may be the well-known DES,  3 DES, RC 5 , AES, etc. H( ) is a hash function such as sha- 1 , md 5 , etc., and ∥ means concatenation.  
         [0026]    In FIG. 1, secret information of the user is only the password, and secret information of the server is a password verifier V=OWF(f(P)) for a respective user.  
         [0027]    In FIG. 1, a user  50  sends to a server  60  (step  101 ) a message including a user ID ID User , a test number A=OWF(r) computed by randomly selecting a random number x (step  101   a ), and a question number generation value X=V(g x ) known only to the server and the user and computed by randomly selecting the random number x (step  101   b ). Accordingly, the user and server authentication and key exchange protocol can be started.  
         [0028]    The server  60 , that has received the message from the user, sends to the user  50  (step  102 ) a message including an authentication Auth=H(K′∥1) of whether the server possesses a public key (step  102   a ) computed by randomly selecting the random number y using the message, and a question number generation value Y=V(g Y ) known only to the server and the user (step  102   b ). The authentication Auth=H(K′∥1) is computed using K=[V −1 (X)] y , K′=H(K∥g x ∥g y ∥ID User ∥ID Server ). During the next procedure, this enables the user to compute the server authentication information and random challenge (i.e., ‘c’ at a step  103   b ).  
         [0029]    The user  50 , that has received the message transmitted from the server  60  (step  102 ), verifies the authentication by computing K=[V −1 (Y)] x , K′=H(K∥g x ∥g y ∥ID User ∥ID Server ). If the authentication succeeds as a result of verification, the user  50  can be convinced that the server knows the password verifier V. Thus, the user can complete the server authentication by confirming whether the server possesses the password verifier V (step  103   a ). Then, the user computes c=H(TSK∥A) using A and TSK=H(K′∥0). At this time, c becomes a result of a secret coin tossing, and in the general zero-knowledge proof, c is a value known only to the server and the user, being different from that transmitted from the server to the user in the form of a text. Also, the server that is the subject of performing the authentication makes the random challenge (i.e., c) transmitted from the server to the user that is the subject of performing the authentication request known only to the server and the user, and this can defend against the offline dictionary attack. In the same manner, protocols illustrated in FIGS. 2, 3, and  4 , which will be explained later, can also defend against the offline dictionary attack by making the random challenge known only to the server and the user.  
         [0030]    After the above computation, the user computes the witness number B using the above c, r, and password P that the user has, and sends the witness number B to the server (step  103   b ). Also, the user computes the session key SK by SK=H(K′∥A∥B∥2) (step  103   c ). Through the above three steps  103   a  to  103   c , the user authenticates the server, and sends the witness number B.  
         [0031]    The server  60  computes c=H(TSK∥A), and verifies the user&#39;s witness number B using A, V, and c. If the verification succeeds, the server completes the user authentication (step  104   a ). Then, the server computes the session key SK by SK=H(K′∥A∥B∥2) (step  104   b ). After the completion of this protocol, the session key SK exchanged between the user and the server is SK=H(K′∥A∥B∥2) (step  104 ).  
         [0032]    [0032]FIG. 2 is a view illustrating a protocol for applying an RSA problem to the framework of FIG. 1. The system settings in FIG. 2 have the same meaning as those in FIG. 1, and the different portion (n=p*q, e) is an RSC public key. At this time, p and q are RSA fractions, e is a fraction, and thus the one-way function is OWF(r)=r e  mod n. f(P) is a function for expanding the password P into 1 g(n) bits (step  200 ).  
         [0033]    In FIG. 2, the secret information of the user is only the password, and the secret information of the server is a password verifier V=[f(P) −1 ] e  mod n for the respective user.  
         [0034]    In FIG. 2, the user  50  sends to the server  60  (step  201 ) a message including a user ID ID User , a test number A=r e  mod n computed by randomly selecting a random number x (step  201   a ), and a question number generation value X=V(g x ) known only to the server and the user and computed by randomly selecting the random number x (step  201   b ).  
         [0035]    The server  60 , that has received the message from the user, sends to the user  50  (step  202 ) a message including an authentication Auth=H(K′∥1) of whether the server possesses a public key (step  202   a ) computed by randomly selecting the random number y using the message, and a question number generation value Y=V(g y ) known only to the server and the user (step  202   b ). Meanwhile, Auth=H(K′∥1) is computed using K=[V −1 (X)] y , K′−H(K∥g x ∥g y ∥ID User ∥ID Server ).  
         [0036]    The user  50 , that has received the message transmitted from the server  60  (step  202 ), verifies the authentication by computing K=[V −1 (Y)] x , K′=H(K∥g x ∥g y ∥ID User ∥ID Server ). If the authentication succeeds as a result of verification, the user  50  can be convinced that the server knows the password verifier V. Thus, the user can complete the server authentication by confirming whether the server possesses the password verifier V (step  203   a ). Then, the user computes c=H(TSK∥A) using A and TSK=H(K′∥0). At this time, c becomes a result of a secret coin tossing, and in the general zero-knowledge proof, c is a value known only to the server and the user, being different from that sent from the server to the user in the form of a text. After the above computation, the user computes the witness number B using the above-described c, r, and password P that the user has, and sends the witness number B to the server (step  203   b ). At this time, the witness number B is B=r*f(P) c  mod n. Also, the user computes the session key SK by SK=H(K′∥A∥B∥2) (step  203   c ). Through the above three steps  203   a  to  203   c , the user authenticates the server, and sends the witness number B.  
         [0037]    The server  60  computes c=H(TSK∥A), and verifies the user&#39;s witness number B using B e *V c =A mod n. If the verification succeeds, the server completes the user authentication (step  204   a ). Then, the server computes the session key SK by SK=H(K′∥A∥B∥2) (step  204   b ). After the completion of this protocol, the session key SK exchanged between the user and the server is SK=H(K′∥A∥B∥2) (step  204 ).  
         [0038]    [0038]FIG. 3 is a view illustrating a protocol for applying a discrete logarithm problem to the framework of FIG. 1. The system settings in FIG. 3 have the same meaning as those in FIG. 1, and P is a fraction having a factor of q that is a fraction larger than p by p−1. a is a generator of Z* q , and thus is OWF(r)=a r  mod p. f(P) is a function for expanding the password P into 1g(q) bits (step  300 ).  
         [0039]    In FIG. 3, the secret information of the user is only the password, and the secret information of the server is a password verifier V=a −f(P)  mod p for the respective user.  
         [0040]    In FIG. 3, the user  50  sends to the server  60  (step  301 ) a message including a user ID ID User , a test number A=a r  mod p computed by randomly selecting a random number x (step  301   a ), and a question number generation value X=V(g X ) known only to the server and the user and computed by randomly selecting the random number x (step  301   b ).  
         [0041]    The server  60 , that has received the message from the user, sends to the user  50  (step  302 ) a message including an authentication Auth=H(K′∥1) of whether the server possesses a public key (step  302   a ) computed by randomly selecting the random number y using the message, and a question number generation value Y=V(g y ) known only to the server and the user (step  302   b ). Meanwhile, Auth=H(K′∥1) is computed using K=[V −1 (X)] y , K′=H(K∥g x ∥g y ∥ID User ∥ID Server ).  
         [0042]    The user  50 , that has received the message transmitted from the server  60  (step  302 ), verifies the authentication by computing K=[V −1 (Y)] x , K′=H(K∥g x ∥g y ∥ID User ∥ID Server ). If the authentication succeeds as a result of verification, the user  50  can be convinced that the server knows the password verifier V. Thus, the user can complete the server authentication by confirming whether the server possesses the password verifier V (step  303   a ). Then, the user computes c=H(TSK∥A) using A and TSK=H(K′∥0). At this time, c becomes a result of a secret coin tossing, and in the general zero-knowledge proof, c is a value known only to the server and the user, being different from that sent from the server to the user in the form of a text. After the above computation, the user computes the witness number B using the above-described c, r, and password P that the user has, and sends the witness number B to the server (step  303   b ). At this time, the witness number B is B=r+f(P)*c mod q. Also, the user computes the session key SK by SK=H(K′∥A∥B∥2) (step  303   c ). Through the above three steps  303   a  to  303   c , the user authenticates the server, and sends the witness number B.  
         [0043]    The server  60  computes c=H(TSK∥A), and verifies the user&#39;s witness number B using a B *V c −A mod p. If the verification succeeds, the server completes the user authentication (step  304   a ). Then, the server computes the session key SK by SK=H(K′∥A∥B∥2) (step  304   b ). After the completion of this protocol, the session key SK exchanged between the user and the server is SK=H(K′∥A∥B∥2) (step  304 ).  
         [0044]    [0044]FIG. 4 is a view illustrating a protocol for applying a square root problem based on a prime factorization to the framework of FIG. 1. The system settings in FIG. 4 have the same meaning as those in FIG. 1, and the different portion (n=p*q) is an RSC public key. Thus, the one-way function is OWF(r)=r 2  mod n. f(P) is a function for expanding the password P into 1g(n) bits (step  400 ).  
         [0045]    In FIG. 4, the secret information of the user is only the password, and the secret information of the server is a password verifier [V 1 =[f(P+1) −1 ] 2  mod n, V 2 =[f(P+2) −1 ] 2  mod n, V 3 =[f(P+3) −1 ] 2  mod n, . . . , V k =[f(P+k) −1 ] 2  mod n, V=H(V 1 , V 2 , . . . , V k )] for the respective user.  
         [0046]    In FIG. 4, the user  50  sends to the server  60  (step  401 ) a message including a user ID ID User , a test number A=r 2  mod n computed by randomly selecting a random number x (step  401   a ), and a question number generation value X=V(g x ) known only to the server and the user and computed by randomly selecting the random number x (step  401   b ).  
         [0047]    The server  60 , that has received the message from the user, sends to the user  50  (step  402 ) a message including an authentication Auth=H(K′∥1) of whether the server possesses a public key (step  402   a ) computed by randomly selecting the random number y using the message, and a question number generation value Y=V(g y ) known only to the server and the user (step  402   b ). Meanwhile, Auth=H(K′∥1) is computed using K=[V −1 (X)] y , K′=H(K∥g x ∥g y ∥ID User ∥ID Server ).  
         [0048]    The user  50 , that has received the message transmitted from the server  60  (step  402 ), verifies the authentication by computing K=[V−1(Y)]x, K′=H(K∥gx∥gy∥IDUser∥IDServer). If the authentication succeeds as a result of verification, the user  50  can be convinced that the server knows the password verifier V. Thus, the user can complete the server authentication by confirming whether the server possesses the password verifier V (step  403   a ). Then, the user computes c=H(TSK∥A) using A and TSK=H(K′∥0). At this time, c becomes a result of a secret coin tossing, and in the general zero-knowledge proof, c is a value known only to the server and the user, being different from that sent from the server to the user in the form of a text. After the above computation, the user computes the witness number B using the above-described c, r, and password P that the user has, and sends the witness number B to the server (step  403   b ). At this time, the witness number is given by  
       B   =     r   *       ∏       i   =   l     ,   k                         (     f        (     P   +   i     )       )       c   i                                 
 
         [0049]    Also, the user computes the session key SK by SK=H(K′∥A∥B∥2) (step  403   c ). Through the above steps, the user authenticates the server, and sends the witness number B.  
         [0050]    The server  60  computes c=H(TSK∥A), and verifies the user&#39;s witness number B using  
       A   =       B   2     *     ∏                  V   i     c   i          mod                 n                               
 
         [0051]    If the verification succeeds, the server completes the user authentication (step  404   a ). Then, the server computes the session key SK by SK=H(K′∥A∥B∥2) (step  404   b ). After the completion of this protocol, the session key SK exchanged between the user and the server is SK=H(K′∥A∥B∥2) (step  404 ).  
         [0052]    As described above, the present invention has the following effects.  
         [0053]    First, the protocols designed according to the present invention can make a strong defense against the offline dictionary attacks.  
         [0054]    Also, the present invention can be applied to the user authentication and key exchange protocol used in communication networks. For instance, it can be defined that the transport layer security (TLS), which is the transport layer security protocol established in the Internet engineering task force (IETF) and is used for the Internet information protection, is performed only by the password without the necessity of the note of authentication or secret key. Also, the present invention can be applied to the authentication protocol being discussed in the IEEE 802.11i group.  
         [0055]    Also, the present invention can substitute for the user authentication procedure of UNIX.  
         [0056]    In addition, a new authentication and key exchange protocol can be easily designed using the framework proposed in the present invention. Thus, a user can easily design a secure authentication and key exchange protocol even without a deep knowledge of encryption.  
         [0057]    The forgoing embodiments are merely exemplary and are not to be construed as limiting the present invention. The present teachings can be readily applied to other types of apparatuses. The description of the present invention is intended to be illustrative, and not to limit the scope of the claims. Many alternatives, modifications, and variations will be apparent to those skilled in the art.