INET Conferences

Conferences

INET


NDSS

Other Conferences

[INET'98] [ Up ][Prev][Next]

A Password Authentication Method and Its Applications

Tsutomu HORIOKA <horioka@aether.hil.ntt.co.jp>
Akihiro SHIMIZU <shimizu@aether.hil.ntt.co.jp>
Nippon Telegraph and Telephone Corporation
Japan

Abstract

This paper describes a password authentication method called PERM and its application to e-mail forwarding services. This method is advantageous and suitable for communications on insecure network environments such as the Internet. It can be easily adapted to Internet appliances or Java applets which have limited performance. With the PERM method in each authentication session, the prover has only to compute three pieces of authentication data and send them to the verifier. The PERM method does not require password resettings and enables high-speed authentication processing with a small-sized program.

The rest of the paper is devoted to verifying the feasibility of the PERM method by applying to an e-mail forwarding service, since e-mail has become indispensable for communications on the Internet, especially for the many business fields.

Contents

1. Introduction

As Internet penetration increases, it will become indispensable to authenticate the capacity of communication partners or users in communications. A wide variety of authentication methods have been proposed to meet this requirement. These methods can be roughly divided into those using public-key cryptosystems and those using common-key cryptosystems.

Those using the public-key cryptosystem, such as RSA [1], have excellent authentication ability and are applicable to electronic transactions or the like. However, because of their long execution time and large program size, their area of application is limited in their integration into terminals with poor processing ability, such as a PDA (Personal Digital Assistant: a portable terminal), and communication protocols related to the Internet.

A traditional way to solve this problem is to utilize common-key cryptosystems, such as DES [2] and FEAL [3][4], which are capable of far faster processing than public-key cryptosystems. Thus, password-based authentication methods are particularly popular for application in these areas.

The basic password authentication procedure is as follows. First, the prover registers his password with the verifier. At authentication, the prover transmits his password to the verifier. The verifier compares the received password with the registered one.

This method has the following problems:

  1. The password may be stolen by visual access to the password file.
  2. The password may be stolen by a wiretap on the communication line.
  3. The prover is required to reveal the password to the verifier, which is secret information of the prover.

A Lamport method [5] has been proposed to solve these problems. This method is enhanced as an original idea to S/Key a one-time password authentication method [6] and a CINON method [7][8].

With the Lamport method, a one-way function is pre-applied to the password a plurality of times and data of the immediately preceding authentication session are presented to the verifier for each authentication, thus enabling authentication to be done a plurality of times. With this method, the initially set maximum number of authentication sessions is decremented by one upon each authentication execution, and when the present number of authentication sessions is exhausted, the password must be reset. If the number of one-way function applications is increased with a view to increasing the maximum number of authentication sessions, the amount of processing would inevitably increase. Another problem is that the prover's processing workload is too large in terms of its processing ability, which is poor as compared to that of the verifier.

With the CINON method in each authentication session, the prover sends to the verifier three pieces of data: data from which authenticated data registered after its validity check in the immediately preceding authentication session is assumed to have originated; authenticated data for use in the authentication session after next; and data for checking the validity of the data transmitted in the previous authentication session and for use in the next session. In this way, it is possible to execute authentication sessions one after another while security updating the authentication information.

The CINON method involves the use of two previously generated random numbers when the user receives authentication from the verifier. Hence, when receiving the verifier's authentication from a terminal at a visiting site, the user needs to use a storage medium, such as an IC card, which has stored the random numbers. The terminal needs to have a random number generating function and an IC card read/write function.

This paper discusses a password authentication method called PERM (Privacy Enhanced information Reading and writing Management protocol) and its application to e-mail forwarding services. The method improves on the Lamport method in that it does not require password resettings and it enables high-speed authentication processing with a small-sized program. Moreover, it does not use facilities or mechanisms for generating random numbers and writing them into and reading them out of an IC card or similar storage medium.

2. PERM specifications

2.1 Notations

The notations used in this paper are described below, step-by-step:

  1. The prover is a user who is authenticated by the verifier and the verifier is a host who authenticates the prover;
  2. The one-way transform by the secret-key crypto-algorithm E is represented by C = E ( P, K ), where C is one-way transform data, P is plain text, and K is the secret key, and simply C <- P, K has the same function;
  3. S represents the prover's secret information, that is, the password;
  4. n is an integer equal to or greater than 0, which indicates the number of authentication sessions, i.e., the number of times authentication is executed;
  5. A represents the prover's identifier, that is, the user ID such as a mail account;
  6. Mn represents an authenticator generated to correspond to the number of authentication sessions;
  7. XOR denotes bit-wise exclusive OR operation;
  8. Wn = E ( A, Vn ) for setting Vn = E ( A, S XOR Nn ), that is, data resulting from a twice-applied one-way transform of S XOR n ; the difficulty in counting back S, n, or Vn from Wn is dependent on the strength or robustness of the secret-key crypto-algorithm.

2.2 Authentication procedure

In this section, the PERM authentication procedure is described.

(1) Initial registration processing

The initial registration processing of the PERM authentication procedure requires the following two steps:

Step 1: The user sets his identifier A and the initial value n = 0 of the authentication session number n directly in the verifier host.

Step 2: The prover follows the procedure described below to compute W0, W1, and M0 and registers them in correspondence with the prover's identifier A. Then, the verifier increments the authentication session number n by one and registers it in correspondence with the identifier A.

  • V0 = E ( A , S ),
  • W0 = E ( A , V0 ),
  • V1 = E ( A , S XOR 1 ),
  • W1 = E (A , V1 ),
  • M0 = E ( W1 , V0 ).

W0 represents data for use in the next authentication session, W1 is data for use in the authentication session after next, and M0 is data for checking the validity of the data W1.

(2) Authentication processing

Fig. 2 shows an n-th (n = 1, 2,...) authentication procedure after the initial registration processing.

Step 1: The prover, at a visiting site, for example, sends a service request to the verifier with the prover's identifier A.

Step 2: Upon receiving the service request from the prover, the verifier sends back the authentication session number n registered in correspondence with the prover's identifier A. At this point, data Wn-1, Wn, and Mn-1 are already registered in the verifier's equipment.

Step 3: The prover receives the value n from the verifier and computes Vn-1, Wn+1, and Mn, following the procedure described below.

  • Vn-1 = E ( A , S XOR ( n-1 ) ),
  • Vn = E ( A , S XOR n ),
  • Vn+1 = E ( A , S XOR( n+1 ) ),
  • Wn+1 = E ( A , Vn+1 ),
  • Mn = E ( Wn+1 , Vn ).

Step 4: The prover sends the verifier the data computed in Step 3. Of the above computed data, Vn-1 is data from which data (called one-way transformed data) transformed by a one-way function, submitted to a validity check on the verifier side in the previous session, and for use in the current authentication session, are assumed to have originated. Wn+1 is one-way transformed data for use in the authentication session after the next. Mn is data for checking, in the next authentication session, the validity of the one-way transformed data Wn+1 used in the authentication session after the next.

Step 5: The verifier performs the following authentication processing, using data Vn-1, Wn+1, and Mn received from the prover. The registered data Wn-1 and E (A , Vn-1) computed by a one-way function E, using the received data Vn-1, are compared, and when they agree, the prover is accepted as valid or authorized. If they do not agree, the prover is rejected or unauthorized and the processing ends. When the prover is accepted as valid, the data Mn-1 is compared with E (Wn, Vn-1), and if they agree, the data is accepted as valid. If they do not agree, the data Wn is rejected as invalid and the processing ends. The data Wn, if accepted as valid, is used as data Wn-1 to check the validity of received data Vn-1 (the validity of the prover) in the next authentication session (n+1).

Step 6: When the prover and the data Wn are accepted as valid, the requested service starts. If the prover sends some content to the verifier, it would be accepted.

Step 7: The verifier newly registers Wn, Wn+1, and Mn in place of the currently registered data Wn-1, Wn, and Mn-1, and increments the value n by one.

PERM Procedure
Fig. 1. An n-th authentication procedure of PERM

3. Performance evaluation

3.1 Security

PERM has almost the same level of security as CINON. As discussed in references [7] and [8], in the PERM method, an unauthorized deceiver could also fool the verifier by obtaining two lots of authentication data from the prover. Thus, the deceiver could impersonate the prover by sending fabricated data to the verifier. However, it would be difficult to do this without the prover noticing, because the deceiver has to make the prover accept situations which cause two consecutive faults immediately after each authorization. In a generally occurring network computing situation, the masquerade will usually be detected, enabling the prover to take appropriate corrective measures.

3.2 Performance comparison

Table 1 compares the basic authentication procedures of the three methods Lamport, CINON, and PERM when using a 64-bit block common-key crypto-system such as DES or FEAL. As with the CINON method, the PERM method does not require password resettings. Moreover, replacing random numbers in the CINON authentication procedure with the number of authentication sessions and adding a turnaround data communication is a simple procedure which does not need to generate the random numbers and write them into and read them out of an IC card or similar storage medium. Although not described in Table 1, the three methods have almost equal program sizes, but processing by the PERM method is significantly faster than processing by the Lamport method, whose speed is similar to that of the CINON method. As discussed above, the PERM method can be easily adapted to various kinds of Internet communications and does not require an IC card or similar storage medium. Furthermore, the PERM method can be written in a program of only about 1 Kbyte when both the verifier and prover sides include a 0.4 Kbyte FEAL program, and it has a light processing burden. Thus, the method can be easily applied to Internet appliances and Java applets which require processings in a limited number of situations.

E-mail message forwarding services in which the PERM authentication method is installed are discussed in the next section.

Table 1: Performance comparison in basic authentication procedure
Performance Remarks
Verifier (Host) Prover (User) Verifier-Prover
One-way function application
(times)		 Data storage for one prover
(bit)		 One-way function application
(times)		 Data Storage
(bit)		 The number of data sending
(times)		 Data transmission
(bit)
Method Lamport
(S/Key)		 1 about 70 100-1000
in general use		 A few bit for n 1
(one-way)		 about 70 requires password resetting
CINON 2 about 200 5 Several bit for random numbers 1
(one-way)		 about 200 requires random numbers generating and storage medium such as IC card
PERM 2 about 200 5 0 3 (a turnaround and one-way) about 200 does not require upper describing functions

4. E-mail message forwarding services

4.1 Background

With the recent proliferation of the Internet, e-mail has come into wider use for communication via the Internet, especially in the many business fields. Demand has been growing, mainly among business users, for services that permit e-mail messages to be sent and received in unfixed visiting places.

A connection request from an indefinite visiting site (i.e., an unspecified IP address) to an IP address level characteristic of the Internet is rejected by a firewall disposed at the entrance to an internal network in which a mail server is placed. That is, provision is only made for passage through the firewall of SMTP (simple mail transfer protocol) for use in e-mail.

This chapter describes the application of the PERM method to user authentication by mail server in e-mail message forwarding services which enable messages to be safely received and sent at the visiting site and to evade the firewall without using the telephone network.

First, the general requirements of the e-mail forwarding services are listed below:

  1. The user of this service has a unique mail account in a mail server on the Internet.
  2. The user can use an application of this service resident in an environment containing the user's unique mail account and an application program of this service in a visiting-site environment.
  3. By utilizing a temporary account at a visiting site, the user can receive e-mail messages sent to his true account. Similarly, he can transmit e-mail messages from his true account by utilizing the temporary account. This temporary account is, for example, a terminal connected to the Internet whose use is offered to the public or the account of a different Internet user.

Moreover, e-mail messages forwarding services need to meet the following security requirements:

  1. By authentication of his memorized password or the like, the user can evade the firewall set in the environment containing the mail server, and the user can safely receive e-mail message forwarding services at visited sites. However, no unauthorized person can send and receive e-mail messages.
  2. The user's password is protected on communication lines and in a database in the mail server.
  3. The processing workload for authentication is small both in the environment containing the user's mail account and in the environment at the visiting site.

The e-mail message forwarding services [9] that meet these requirements can easily be constructed using the PERM authentication method.

4.2 E-mail message forwarding services using SMTP

In general, an internal network such as a LAN is connected to the Internet, and the mail server (or verifier host equipment) which has the mail account of a user is connected to the internal network. The user receives e-mail messages sent to his mail account via the international network connected to the host equipment.

When a user moves out of the internal network, he can receive e-mail messages sent to his mail account by connecting to the Internet at a visiting site, then sending the user identifier A as an e-mail message to the host equipment that has his mail account, and finally performing the PERM authentication procedure between himself and the host equipment as illustrated in Fig. 1. In the authentication procedure, authentication data is transmitted by using SMTP to evade a firewall disposed at an entrance to an internal network containing the host equipment. Finally, the user can receive e-mail messages sent to his true account by temporarily using the account of another personal computer connected to the Internet at a visiting site.

E-mail messages can also be sent in a similar manner by sending a message with authentication data.

4.3 E-mail message forwarding services with a transit server

The Internet is almost always crowded and information often cannot be smoothly transmitted or received. As in the above example, authentication information exchange using the e-mail protocol may take several minutes depending on conditions at the time. When it is considered undesirable to keep the user waiting for such a long time, a transit server is placed between the user terminal and the mail server [10], as depicted in Fig. 2. In contrast to the mail server inside the firewall, that is, on the internal network of the intranet, the transit server is assumed to be placed on the Internet and to be open to the outside.

With such a configuration, a fast forwarding protocol such as HTTP can be used between the user and the transit server since the transit server is open to the public. Though the communications between the transit server and the mail server inside the intranet use SMTP with a view to evading the firewall, the forwarding rate can be increased as the communications are conducted through a smaller number of hosts.

Transit Server
Fig. 2. Outline of e-mail messages forwarding services with a transit server

At this point, the mail server already has data n, Wn-1, Wn, and Mn-1 registered in association with the identifier A, and the transit server already has data n', Wn'-1, Wn', and Mn'-1 registered in association with the identifier A.

In the initial step of the authentication procedure, the user sends the service request to forward e-mail messages stored in the mail server to the transit server and the user identifier A to the mail server via the transit server. The mail server sends back to the user authentication session number n corresponding to the received identifier A via the transit server. The user computes authentication data Vn-1, Wn+1, and Mn using the received authentication session number n, the identifier A, and the password S of the user's mail account. After sending three pieces of authentication data to the transit server, the user once breaks off the connection with the transit server. The transit server sends the received data to the mail server, that is, verifier equipment, to perform the authentication processing. If the user is recognized as an authorized user, the mail server forwards copies of the stored e-mail messages to the transit server, and the transit server stores them in correspondence with the user's identifier A.

At a given point after several minutes have elapsed, the user sends a service request to read e-mail messages stored in the transit server with the identifier A. The transit server sends back to the user session number n' in association with the identifier A. The user performs PERM procedure with n'. If the user is accepted as valid or authorized, the transit server forwards the stored e-mail messages to the user.

In this example, for the sake of brevity, the identifier A and the password S for use in calculating the authentication data between the user and the transit server can be the same as in the authentication processing between the user and the mail server, but different passwords S and S' may also be used.

Alternatively, the user may use the same password S and identifier A for the authentication processing between him and the transit server as those used for the authentication processing between the user and the mail server. That is, identifiers of the mail server and the transit server can be represented by different I* using a notation * for the each server; the authentication processing uses A XOR I* as a substitute for the identifier A in all equations using A in the authentication procedure. This method is advantageous because the user can use the same password S and identifier A for authentication processing with both the mail server and the transit server without impairing security.

Moreover, by sharing the authentication session number n by the mail server and the transit server and by updating in synchronism with each authentication so as to realize faster processing, the authentication procedure can be reduced by one information exchange stage between him and the mail server via the transit server.

4.4 E-mail message forwarding service with encryption functions

In the example in the previous section, the service consists of two requests of mail forwarding; one is from the mail server to the transit server and the other is from the transit server to the user. The user has to wait for a while until the transit server receives e-mail messages from the mail server. If a user feels it is troublesome to twice perform authentication procedures, he can set the mail server, in advance, to forward the e-mail messages to the transit server. However, e-mail message forwarding service requires strong security, since information exchange on the Internet contains the risk of eavesdropping from malicious users. The encryption of e-mail messages meets this requirement. A common-key cryptosystem as encryption function is suitable in this case, because those who encrypt and decrypt messages are the same users and it can be easily adapted to Internet appliances which have limited processing ability.

The outline of the e-mail forwarding service with encryption function is depicted in Fig. 3 and the procedures of service are listed below:


Fig. 3. Outline of the e-mail forwarding services with encryption functions

  1. A user sets the mail server to forward the received e-mail messages to the transit server and registers the encryption key before he moves out of the internal network.
  2. If a new message is delivered to the user's account, it is encrypted with the registered key and forwarded to the transit server using SMTP. When the transit server receives a forwarded e-mail message, the message is stored in correspondence with the user identifier A.
  3. When reading the e-mail messages stored in the transit server at a visiting site, the user connects to the transit server by HTTP and sends a service request. Then he starts PERM authentication procedure with the transit server. When admitted as an authorized user, the user receives a list of e-mail messages stored in the transit server in association with the user identifier A and selects one of the messages he reads. Then the user receives the encrypted body of the message based on his selection and Java Applets for decryption. By inputting the same key as registered in the mail server through Java Applets, the body is decrypted and the original e-mail message is reconstructed.

When the user replies to the e-mail messages he reads or sends a new message, it is possible to send a message from his original account in the mail server. After he edits an e-mail message and encrypts it with the same key as registered in the mail server, he sends to the mail server the encrypted message and PERM authentication data with the mail server via the transit server. If he is recognized as a valid user at the mail server, his encrypted message is decrypted with the registered key and delivered to the addressee from his original account.

5. Conclusion

This paper has described a password authentication method called PERM and its application to e-mail forwarding services. The PERM method does not require password resettings and performs high-speed authentication processing with a small-sized program occupying only about 1 Kbyte including a 0.4 Kbyte FEAL program on both verifier and prover sides. Moreover, the method does not use facilities or mechanisms for generating random numbers and writing them into and reading them out of an IC card or similar storage medium. Thus, it is important to be able to be easily adapted to various kinds of Internet contents communications including Internet appliances and Java applets which require processing in a limited number of situations, since Internet home appliances equipped with an Internet connection function, such as TV Set Top Box or portable terminal equipment, will soon be introduced on the market[11].

Future studies will be on Internet real applications containing the PERM method.

Acknowledgments

The authors would like to thank Hirohito Inagaki of NTT Human Interface Labs and Mr. Koji Tsurumaki, Miss Saori Takeuchi, and Mr. Takayuki Watanabe of NTT Intelligent Technology Co., Ltd. for their cooperation in the service system programming.

References

[1] R. Rivest, et al., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Commun. ACM, Vol.21, No.2, pp. 120-126, 1978.

[2] NBS, "Data Encryption Standard," FIPS-PUB-45, 1977.

[3] A. Shimizu and S. Miyaguchi, "Fast data encipherment algorithm FEAL," IEICE Trans. (D), Vol. J70-D, No. 7, pp. 1413-1423, 1987 (In Japanese).

[4] S. Miyaguchi, A. Shiraishi and A. Shimizu, "Fast data encipherment Algorithm FEAL-8," ECL Review, Vol. 36, No. 4, pp. 433-437, 1988.

[5] L. Lamport, "Password authentication with insecure communication," Commun. ACM, Vol. 24, No.11, pp. 770-772, 1981.

[6] N. Haller, "The S/KEY(TM) one-time password system," Proc. of the Internet Society Symposium on Network and Distributed System Security, pp. 151-158, 1994.

[7] A. Shimizu, "A dynamic password authentication method by one-way function," IEICE Trans.(D-I), Vol. J73-D-I, No. 7, pp. 630-636, 1990 (In Japanese).

[8] A. Shimizu, "A dynamic password authentication method by one-way function," System and Computers in Japan, Vol. 22, No. 7, 1991.

[9] A. Shimizu, "Public E-mail Messages Forwarding Services," IEICE Technical Report, OFS96-39, No. 380, pp. 19-24, 1996 (In Japanese).

[10] T. Horioka, M. Toda and A. Shimizu, "E-mail Messages Forwarding Services," IEICE Technical Report, OFS97-39, No. 280, pp. 37-42, 1997 (In Japanese).

[11] T. Arakawa and T. Kamada, "The Internet home electronics and the information network revolution," IEICE Technical Report, OFS96-1, No. 70, pp. 1-6, 1996 (In Japanese).

[INET'98] [ Up ][Prev][Next]