A Mutual Authenticating Protocol with Key Distribution in a Client/Server Environment

by Charles Cavaiani and Jim Alves-Foss

The explosive growth of networked and internetworked computer systems during the past decade has brought about a need for increased protection mechanisms. This paper discusses three authentication protocols that incorporate the use of methods that present effective user authentication. The first two protocols have been previously discussed in the literature; the third protocol draws from the first two and others to produce an authentication scheme that provides both mutual authentication and secure key distribution which is easy to use, is compatible with present operating systems, is transparent across systems, and provides password file protection.

Introduction

Within the last decade, computer crime has become a major threat to business and government. The Federal Bureau of Investigation indicates that computer crime is the most expensive form of commercial crime -- with an average cost of $450,000 per theft [6]. For various computing environments in 1992, the National Computer Security Association placed a $760 million price tag on the damage done by hacker attacks and computer virus infections [7]. Papers from the Computer Emergency Response Team (CERT) [2,8,9,10] cite example after example of increasing attacks on system and network security.

With the growing trend toward "open-system'' environments, there is an increasing concern by system administrators about system penetration, network eavesdropping, data alteration, or system disruption by unauthorized personnel. Coupled with the increasing access and popularity of the Internet and the increasing power of the desktop computers, this trend has created a dramatic increase in opportunities for system and network abuse [2,8,9,10].

To fight these abuses, people have historically turned to methods of hiding information by converting plain-text messages into hidden messages through the use of a cryptographic algorithm and a corresponding encryption key. In place of system isolation (a viable alternative for some secure systems, but not for most general use systems), one solution would be to enhance or develop a cryptographic mechanism to prevent messages from being viewed by unauthorized parties. The strength of a good cryptographic system will usually lie in the strength of the algorithm. A good algorithm can be made public without worry of being broken. For a person to obtain information to attack the algorithm, he or she must usually gain access to the computer system itself or information transferred between systems. To gain this access or information,a person may try one or several of the following intruder attacks:

These attacks may result in the following types of cryptoanalysis by the intruders:

The 1990s challenge is to be able to evaluate the risks that are present, measure their effects on systems we wish to control, and build computer security into our products and our daily routines through management protocols. All these requirements must be performed without unnecessarily impeding the ability to access the network, while providing the users an adequate assurance of security and privacy. In this paper we discuss authentication protocols as a mechanism for providing secure access to systems across the network.

Authentication

To provide security and privacy for a user, systems may need to support a method to determine the identities of two or more remote parties that wish to exchange information. This shared process of identification is called mutual authentication. Mutual authentication can provide assurance that the proper users or servers are being contacted by using one or a combination of the following [6,11]:

Passwords along with a user-identification code have been the predominant method of authentication in the client/server environment. Minimal factors for securing passwords are [12]:

Composition -- the acceptable character sequence that makes up a password (e.g., both uppercase and lower case letters of the alphabet, special characters, digits).

Length -- the longer the password, or more characters in the password, the more difficult it becomes to crack. The ``effort to crack'' is exponentially proportional to the number of characters in the password (i.e., if n = number of characters in the alphabet and x = number of characters in the password, then = number of possible passwords).

Other factors include:

  1. Lifetime -- the ability to compromise a password through disclosure and substitution can be minimized by frequent changes in a password.
  2. Source -- selection of a password by machine generation or user selection; the less predictable a password is, the more secure the system.
  3. Ownership -- passwords need to be used and owned by a single individual, not shared by a group.
  4. Distribution -- issuing or changing a password can be a highly sensitive area for security holes, since an intruder can eavesdrop or redirect during distribution of the password.
  5. Storage -- one of the most important factors is password storage on the system; storage refers to how password files are protected to prevent an intruder from learning the password.
  6. Entry -- deals with the difficult task of not being observed by an intruder while physically logging onto the terminal with a password that is transmitted to the system.
  7. Transmission -- a password is transmitted for authentication purposes from a terminal to a (possibly shared) computer system, over a communication line that connects the terminal and the computer.
  8. Authentication Period -- an effort to ensure that only authorized individuals are allowed on an interactive session (that may last for several hours) between a user and a computer system, via a remote terminal.

Even with secure passwords the key to any system security is risk assessment. To set up appropriate safeguards, the potential risks and the costs of preventing or recovering from the damage associated with those risks need to be understood. Unfortunately, all risks can never be eliminated. No matter how secure a computer system becomes, it can be broken into, given sufficient resources, time, and money. To minimize the risk and increase the effort the intruder must expend to capture a passwords, efforts should be made to protect passwords when they are stored and transmitted.

Mutual Authentication Protocols

Most computer systems use an authentication method which requires the user to provide a password. This usually involves the user typing in a password at the system prompt and the system applying a transformation to the provided password and comparing it to a copy stored on local disk (the local copy is stored in the transformed state to prevent a user from easily reading passwords from the file). When such mechanisms are extended to networked or internetworked systems, the user's password (and corresponding ID) must be passed over the network, as typed by the user, to the remote server. This passing of the information in plain-text makes it very susceptible to attack by network eavesdroppers. A secure authentication protocol uses cryptographic techniques (or zero-knowledge mechanisms) to prevent this type of attack. In addition, some authentication protocols allow users to establish a session key that can be used to encrypt all messages during a session, providing security for the full transaction, beyond just security for authentication. In this section we will discuss such authentication protocols.

Basic Mutual Authentication Protocol

Using the Diffie-Hellman [14] key exchange protocol, two users can agree on a secret session key and then authenticate over an unsecured channel by encrypting the authentication information using the session key. This basic mutual authentication protocol may be illustrated in an example involving two parties, Alice and Bob, who both agree on a prime number p and a primitive element a in a finite field called the Galois field, GF(p). Prime p should be such that (p-1) has a large prime factor. This agreement could be based on published, system-wide constants, or could result from previous communications (the values must be known reliably by both parties). As the first step in deriving a key, Alice generates a random number x, She then calculates and sends this value to Bob. Bob generates a random number calculates and sends this value to Alice. Then Alice calculates and Bob calculates Both parties now know a common key,

This basic protocol prevents an eavesdropper from compromising and inverting the function to determine the key k. However, this still does not stop an intruder from spoofing through a man-in-the-middle attack.

The scheme described above for key derivations limits the impact of a cryptosystem compromise. If a non Diffie-Hellman cryptosystem is broken, or if the private key is compromised, then all the primary keys and message traffic protected under the private key system are compromised. However, if a Diffie-Hellman derivation is compromised, only the traffic protected under the one primary key is compromised, and authentication is unaffected.

One of the disadvantages of this system is that it uses public keys, which require significantly more computational power than traditional private-key systems such as Data Encryption Standard (DES).

University of Virginia Authentication Scheme

A scheme developed by W. A. Wulf, A. Yasinac, K. S. Oliver, and R. Peri from the University of Virginia (UofV) [5] addresses the weakness of the basic protocol. The UofV protocol takes the interesting approach of passing multiple one-way functions to protect against masquerade, password guessing, and replay attacks.

The UofV protocol proposes a method to provide user authentication with no shared knowledge between users. This provides an increased confidence level in the authentication of the user. This method is illustrated by the following example: When Alice requests services from Bob, Alice must answer a question that only Alice knows. This means no one else -- not even Bob -- knows the answer, but Bob must be able to verify that the answer received from Alice is correct.

This method removes the need for the traditional use of a password or secret key. Additionally, the problem of storage of passwords or secret keys is also eliminated.

The UofV is based on the following two properties:

The basic steps of the UofV protocol are:

The critical security elements of this protocol are functions f and g. Though the form of f and g can be public knowledge, the actual functions f and g and generator values a and b must remain secret. For it is critical to the UofV protocol that an intruder not be able to predict the value

g(f(x),f(y)).

If gshould become public knowledge, an intruder could obtain the values for

g(x,y), f(x), and y,

thereby, being able to masquerade as Alice after computing

f(g(x,y)) = g(f(x),f(y)).

Alternately, an intruder could masquerade as Alice if function f was compromised and values

f(y) and f(g(x,y))

were computed.

Even though the functions f and g cannot be made public, the authors of the UofV protocol feel that the forms of f and g can be made public. This allows for each user to choose an appropriate function for f in private and not require f to be passed over a channel or use a third party authentication service.

Since the UofV protocol requires no centralized support, it can be well-suited to a fully distributed environment. It allows authenticators to change identifiers (i.e., x, f(x)), providing for a high degree of flexibility in subsequent authentication sequences and thereby providing protection from replay attacks. Finally, since there are no keys in the method, the number of transmitted information pairs used for authentication (x, f(x)) and the number of functions available as f and g are unbounded when carefully selected.

3.3 Augmented Encrypted Key Exchange

Another scheme that provides an excellent method for mutual authentication is a protocol developed by S. M. Bellovin and M. Merritt [3,4] from AT&T Bell Laboratories. The Augmented Encrypted Key Exchange (A-EKE) protocol allows two parties sharing a password to communicate without exposing the shared password. The mutual authentication protocol uses one-way hash functions in conjunction with public-key encryption. The A-EKE presents a mechanism in which a host does not have to store clear-text passwords, and protects against masquerade, dictionary, and man-in-the-middle attacks.

Bellovin and Merritt [4] presented their protocol as a novel combination of asymmetric and symmetric cryptography that allows two parties sharing a common password to exchange confidential and authenticated information over an unsecured network. Since then, they have modified their protocol to include the use of hash functions [3]. In reviewing Bellovin's and Merritt's mutual authentication protocol, we first need to be familiar with their notations, shown in Table 1.

Bellovin and Merritt assume that there is a one-way function H, such that it is not feasible to recover P from H(P), and the host should try to keep H(P) secret. Their goal is to prevent an intruder who has captured H(P) from mounting a dictionary attack against P or in mimicking the host to the requester.

The Bellovin and Merritt protocol is as follows (note: both Alice and Bob know plain-text P):

An attacker who does obtain H(P) from the host could mimic the host in communicating with Alice; however, without knowledge of P, the attacker still cannot mimic communication with Alice to the host. EKE's use of functions T(), F(), and H() in the protocol's last step is an effort to prevent an intruder from spoofing the host to Alice if the password P has been compromised, possibly by a dictionary attack. The protocol can be further strengthened against a dictionary attack by letting Bob pick a random value s before the start of the protocol. The stored H(P) is then replaced by [H(s,P), s]. Bob could now send s in the clear to Alice as an added initial step of the EKE protocol. This provides the advantage of making it infeasible to tell if two hashed passwords use the same plain-text, and to build a dictionary of pre-hashed password guesses [3]. However, the change can add a degree of uncertainty that must be addressed in the design for a secure implementation of the protocol.

Proposed Authentication Protocol

In this section, we present a new protocol, the Mutual Authenticating Protocol (MAP). The development of the protocol was predominately influenced by the works of W. A. Wulf, A. Yasinac, K. S. Oliver, and R. Peri from the University of Virginia [5] and Bellovin's and Merritt's A-EKE [3,4] protocols. MAP has taken from the UofV protocol the ability to use one-way functions to provide authentication with zero-knowledge proof. MAP has also taken from A-EKE the idea of using hash functions to protect the password and the mechanism for providing mutual authentication.

Using the specific mechanisms from UofV and A-EKE protocols, we developed MAP to provide a specified level of network and system security to meet the following basic design goals:

Protocol Development

The development of MAP from the parts of other protocols requires some definitions. First, taken from A-EKE, MAP uses H(PW) as the password one-way hashing function. This one-way hash function must prevent the recovery of PW from H(PW). Both the user that owns PW and the host that stores H(PW) must keep these secret. The user will register a hashed password (in a UNIX operating system this would be in a shadow password file) and agree on a modulus n that will be used in the one-way functions with the host. However, if an intruder obtains PW, he or she must also determine the one-way hash function used; or if the intruder obtains the H(PW), he or she may be able to mimic the host to Alice, but MAP draws from the operating system's file access capabilities to minimize this possibility.

Additionally, with the use of user independent one-way functions and session key generation, MAP is designed to prevent intruders from forming attacks such as masquerade, replay, man-in-the-middle, and spoofing. The forms of the discrete exponentiation function f and g can be public, but the function f, g, and values: f(x), g(y), x, y, a, b, and n are secret.

Prior to the execution of the protocol Alice will pre-register values H(PW) and n with Bob. The protocol is presented below in full:





4.2 Discussion of MAP Effectiveness

MAP allows Alice and Bob to change the one-way functions f and g, respectively, with virtually every iteration of the authentication sequence. This provides a high level of security by the guaranteed privacy and unpredictability of f and g. Coupled with the characteristics of these functions being very difficult to invert, the minimal amount of information passed across the network for each specific f and g provides an intruder with a limited amount of information to break the protocol. Even if an intruder was able to capture the function values f(x), g(x), g(y), and g(x,y), the functions will change on the next iteration of the authentication, and a new session key will be generated.

A potential weak point of MAP is where the intruder obtains H(PW) from Bob, the host. This same weakness is in A-EKE [3], and as noted in the Bellovin and Merritt paper, the intruder could then mimic the host to Alice. MAP tries to improve on this condition by using the operating system's file capabilities (for UNIX this would be the use of shadow password) to protect the security of the H(PW). However, this area still requires additional work.

To help strengthen the protocol, the use of a session key k was incorporated, which is independently generated by both Alice and Bob, to provide the following two functions:

  1. The individual authentication of each user by the verification of the user non-repeating value.
  2. The use of a session key to pass information in a secure manner.

If an intruder were able to capture the session key k, it would still be highly unlikely that the intruder would be able to invert the one-way functions that created the key. In addition, the window of vulnerability for the session key is only good for the one session between Alice and Bob.

4.3 MAP Advantages/Disadvantages

In performing a review of MAP, several implementation advantages were noted:

  1. Minimum external communication in the agreement of values.
  2. Generation of discrete logarithm functions are dependent on the selection of the individual user, and can be changed at the beginning of each new session.
  3. The functional values (i.e., the values generated from functions f and g) provide no information to a third party viewing the transaction.
  4. Minimum knowledge is exchanged during authentication.
  5. The session key is never transmitted during the authentication process. The session key is generated independently by each user after the decryption of the one-way functions.
  6. MAP takes advantage of shadow password files to secure the stored user password.
  7. Each authenticating session can use different discrete logarithm functions.
  8. MAP protects against masquerading, spoofing, replay, and password guessing attacks, by the use of one-way functions, hashing, and shadow password.

These eight advantages establish that MAP has met or exceeded the goals previously listed. MAP clearly provides a mechanism through the use of encryption, non-encryption, hashing and one-way functions to provide a protocol for effective authentication between users or user and server. In addition, MAP provides minimal information transfer between users to provide this authentication. Since MAP will be implemented high in the protocol layer, this will enhance portability between platforms and will provide an almost transparent implementation to the user.

Enhancements to MAP are necessary to address the following perceived disadvantages:

  1. If H(PW) in the operating system password file is compromised, an intruder could decrypt the encrypted one-way functions and non-repeatable values, and mount masquerading or spoofing attacks against user Alice.
  2. Leakage of functions f and g can allow an intruder to mount masquerade and/or spoofing attacks.
  3. Policy must prevent compromise of hash function and user password to prevent intruder from determining H(PW).
  4. Coding of MAP would be complex, requiring extensive testing and verification of the protocol.
  5. Each user must pre-agree on the modulus n value.

These advantages and disadvantages need to be addressed at the time a test-bed of the protocol is developed. With the testing of MAP, alternatives for improvement can be better evaluated. The final desired result of the testing would be to ``fine-tune'' the protocol to ensure the following:

  1. A protocol with minimum preliminary knowledge to provide mutual authentication.
  2. A zero-knowledge proof for authentication of each user.
  3. Easy implementation of the protocol, where the bulk of the protocol is transparent to the users.
  4. Widest range of protocol implementation over varying operating systems.

Overall, the MAP provides mutual authentication between users, or user and servers. Also, it provides integrity and a secure means of password storage. The protocol appears to be compatible with existing operating system infrastructures since it will be implemented in the top layer of the TCP/IP model or the OSI model.

Conclusion

MAP is not a completely original protocol, but like most works, is built upon other existing works, in an effort to improve upon specific areas of interest, such as user authentication and security of information transfer.

MAP does provide a method for the mutual authentication and secure message traffic between two or more users, and performs this with very little preliminary knowledge or interaction. It has the ability to be implemented across platforms and operating systems, and provides minimal steps for a user to implement.

In addressing system security, MAP provides a method of protection against an intruder's attack on password files with the implementation of shadow password and password encryption. This is accomplished by using a one-way hash function to provide ``hard'' protection for stored passwords with the secure feature of shadow password.

MAP provides mutual authentication by using the Diffie-Hellman discrete logarithm problem, in a finite Galois field, and by the passing of one-way functions, followed by the generation of a session key to provide a mechanism for secure message traffic. The session key provides ``hard'' protection by using one-way functions that are conditionally secure and present a computationally infeasible time for breaking the key. Additionally, the window of vulnerability for the session key is limited to the current user session. The session keys are generated by the independent user functions that are created at the time of the session initialization. This prevents old session keys from providing clues to breaking future session keys. Therefore, this would prevent an attacker from obtaining any useful information by breaking into current message transmissions.

The work described in this paper is a beginning in the development of a working prototype of MAP. By programming, applying, testing, and evaluating algorithms for random generators, hash algorithms, and one way functions, along with data storage methods, MAP will be developed into a working protocol.

References

1
Bruce Sterling. History of the Internet, Literary Freeware, The Magazine of Fantasy and Science Fiction, February 1993. gopher://gopher.isoc.org:70/00/Internet/history/short.history.of.internet.
2
Computer Emergency Response Team (CERT) Coordination Center, 1994 Annual Report (Summary). http://www.cmu.edu/SEI/programs/cert/1994_CERT_Summary.html.
3
Steven M. Bellovin and Michael Merritt. Augmented Encrypted Key Exchange: A Password-Based Protocol Secure Against Dictionary Attacks and Password File Compromise, AT&T Bell Laboratories. Available via anonymous FTP from idea.sec.dsi.unimi.it.
4
Steven M. Bellovin and Michael Merritt. Encrypted Key Exchange: Password-Based Protocol Secure Against Dictionary Attacks, In Proceeding IEEE Computer Society Symposium on Research in Security and Privacy, May 1992: pp. 72-84. Available via anonymous FTP from ftp.research.att.com.
5
William A.Wulf, Alec Yasinac, Katie S. Oliver and Ramesh Peri. A Technique for Remote Authentication, University of Virginia, Charlottesville, VA. Available via anonymous FTP from ftp.research.att.com.
6
Warwick Ford. Computer Communications Security, Principles, Standard Protocols and Techniques, Englewood Cliffs, New Jersey: PRT Prentice Hall, 1994.
7
Lynn Haber. Security. InformationWeek, March 7, 1994: pp. 35-41.
8
Susan Landau, Stepten Kent, Clint Brooks, Scott Charney, Dorothy Denning, Whitfield Diffie, Anthony Lauck, Doug Miller, Peter Neumann and David Sobel. Crypto Policy Perspectives Communications of the ACM, vol 37, no. 8, August 1994: page 115-121.
9
Computer Emergency Response Team (CERT), CA-95: 01. IP Spoofing Attacks and Hijacked Terminal Connections, January 23, 1995. Availabe via anonymous FTP from coast.cs.purdue.edu.
10
Computer Emergency Response Team (CERT), CA-94: 14. Trojan Horse in IRC Client for UNIX, : October 19, 1994. Availabe via anonymous FTP from coast.cs.purdue.edu.
11
Deborah Russell and G.T. Gangemi, Sr, Computer Security Basics, Sebastopol, CA: O'Reilly & Associates, Inc., 1991.
12
Federal Information Processing Standards Publication 112, Password Usage, U. S. Department of Commerce/National Bureau of Standards: 30 May 1985.
13
Mark H. Linehan, Comparison of Network-Level Security Protocols, IBM T. J. Watson Research Center, Hawthorne, NY, June 29, 1994. Available via anonymous FTP from idea.sec.dsi.unimi.it.
14
Whitfield Diffie and Martin E. Hellman, New directions in Cryptography, IEEE Transactions on Information Theory, vol. IT-22, no. 6, 1976: pp.644-654.
15
Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, New York: John Wiley & Sons, 1993.

Dr. Jim Alves-Foss (jimaf@uidaho.edu) has been an Assistant Professor of Computer Science at the University of Idaho since 1991. He received his MS and PhD at the University of California at Davis under the guidance of Dr. Karl Levitt. His research interests include computer security, formal methods and the design of reliable distributed systems.

Copyright 1996 by Charles Cavaiani and Jim Alves-Foss

Want more Crossroads articles about Security? Go to the index, the next one or the previous one.

Last Modified:
Location: www.acm.org/crossroads/xrds2-4/authen.html