A Password Authentication Method and Its Applications
Tsutomu HORIOKA <firstname.lastname@example.org>
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.
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 , 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  and FEAL , 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:
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.
The notations used in this paper are described below, step-by-step:
In this section, the PERM authentication procedure is described.
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.
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.
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.
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 has almost the same level of security as CINON. As discussed in references  and , 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.
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.
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:
Moreover, e-mail messages forwarding services need to meet the following security requirements:
The e-mail message forwarding services  that meet these requirements can easily be constructed using the PERM authentication method.
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.
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 , 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.
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.
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:
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.
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.
Future studies will be on Internet real applications containing the PERM method.
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.
 R. Rivest, et al., "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Commun. ACM, Vol.21, No.2, pp. 120-126, 1978.
 NBS, "Data Encryption Standard," FIPS-PUB-45, 1977.
 A. Shimizu and S. Miyaguchi, "Fast data encipherment algorithm FEAL," IEICE Trans. (D), Vol. J70-D, No. 7, pp. 1413-1423, 1987 (In Japanese).
 S. Miyaguchi, A. Shiraishi and A. Shimizu, "Fast data encipherment Algorithm FEAL-8," ECL Review, Vol. 36, No. 4, pp. 433-437, 1988.
 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.
 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).
 A. Shimizu, "A dynamic password authentication method by one-way function," System and Computers in Japan, Vol. 22, No. 7, 1991.
 A. Shimizu, "Public E-mail Messages Forwarding Services," IEICE Technical Report, OFS96-39, No. 380, pp. 19-24, 1996 (In Japanese).
 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).
 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).