Table of Contents


Design Space 



Authentication tools provide the ability to determine the identity of a party to an interaction and to ensure that a message came from who it claims to have come from. Authentication is seldom used in isolation. Authentication is used as the basis for authorization (determining whether a privilege will be granted to a particular user or process), privacy (keeping information from becoming known to non-participants), and non-repudiation (not being able to deny having done something that was authorized to be done based on the authentication).

Design Space 

All authentication schemes are based on the possession of some secret information known only to the user and possibly (but not necessarily) to the authentication system itself. Interactions with other parties use this secret in a way that allows the recipient to verify that the user possesses the secret, but that does not divulge the secret itself. This means that the secret itself cannot be shared, since to do so would allow the recipient to impersonate the user on subsequent interactions with other parties. One of the major differences between authentication systems lies in how to prove you know the secret without telling it. This is reflected in the basic algorithm used for authentication.

Authentication system also provide differing levels of functionality. At minimum, they allow a recipient to verify that a message originated with a particular user (or user's agent; e.g., a program). More powerful systems ensure that messages cannot be copied and replayed in the future, that a client can prove to a third party that a message originated with a particular user (non-repudiation), and that require multiple users to validate a message (the equivalent to requiring multiple signatures on a checking account).

A final difference in authentication systems lies in who is trusted with the user's secret.

Authentication Algorithms

There are three main algorithms for authentication: passwords, Needham and Schroeder protocol (used in Kerberos), and public key encryption. In all of them, the central issue is to never allow the secret information outside a secured environment, while at the same time allowing the recipient to verify that the secret was used.

The descriptions that appear below only give a flavor of the algorithms and discuss their advantages and disadvantages. For a more complete description of the algorithms and their variants, see the references.


Passwords are simply secrets that are provided by the user upon request by a recipient. Passwords are often stored on a server in an encrypted form so that a penetration of the file system does not reveal password lists. The problem with password-based systems is that the password becomes known to the recipient, who can then impersonate the user. Even if the recipient is trusted not to do this, passwords are dangerous in network environments since they are susceptible to interception during transmission. In general, passwords are unacceptable security in a network environment.

Needham and Schroeder Protocol

In the Needham/Schroeder protocol used in Kerberos, the secret information used for verification is never transmitted in the clear and is never seen by a recipient. Instead, an "authentication server" creates a collection of "session secrets" (derived from its knowledge of the secrets of the sender and receiver in a particular interchange) that are used by the sender and receiver for authentication of messages during a particular interaction. Session information is good only between session participants, and can be timestamped to protect against replaying of messages. New interactions (even between the same client and server) require new session keys. The basic algorithm is given below; variants exist.

Each participant in an authentication realm possesses a secret encryption key know only to itself and an authentication server. This is its secret information. This key is used only for communication with the authentication server, which is presumed to be trusted and secure (i.e., it will neither misuse nor divulge the keys). An interaction between a client and a server begins with a client request to an authentication server for a "session encryption key" and an "authentication ticket" that will be used for client/server interactions. The session key will be used to encrypt messages between the client and server to protect the communications from eavesdroppers. The authentication ticket, which is encrypted using the server's secret encryption key, is handled, but is not readable by the client. The authentication ticket is shipped along with client request to the server in its encrypted form. Thus, a communication between a client and a server consists of a request, encrypted using the session key, and a ticket, encrypted (by the authentication server) using the server's key. Upon receipt of an encrypted message, the server decrypts the ticket. Inside, it finds the session key, which it can use to decrypt the message, and also authentication information put there by the authentication server verifying that the ticket is actually valid for a session with the particular client. Timestamps are also contained in the ticket to limit the time during which the session key will be considered valid.

Because session keys are known only to the client and server involved in a particular session, conventional encryption can be used (see Encryption). This is advantageous, since conventional encryption is typically much faster than public key encryption, which is necessary if an authentication server is not used to generate verifiable session keys. The disadvantage of the Needham/Schroeder protocol is the need for interactions with an authentication server, and the need to trust the authentication server.

Extensions exist to support hierarchical authentication servers across domain. Basically what happens is that if an authentication server does not know the secret key of a server for which a ticket has been requested, it communicates via the same algorithm with a higher level authentication server in much the same way that name servers do. Eventually, the collection of authentication servers produce a session key and ticket, which are then used in the session as if they were obtained from a single, global authentication server. Thus, the algorithm scales well and matches to name server domains nicely.

Security of messages during a session requires them to be encrypted with the session key, which in turn requires that the applications be "Kerberos aware". For a list of such software, see Kerberos Resources. Of course, all parties to a session must be Kerberos aware, else they cannot interpret the encrypted messages.

See Kerberos: An Authetication System for Computer Networks.

At least some projects to integrate DCE with the WWW use authentication based on Kerberos, see OSF's DCE/Web.

Public Key Encryption 

Public key encryption (see Encryption) can also be used for authentication using "digital signatures". In public key encryption, each user, i, has both a public key, Ei, which is made publicly available, and a private key, Di, which only user i knows. The keys are mathematically related, and both are generated by the user. Thus, there is no need for anyone else to hold the private key, which enhances security.

Public and private keys are inverses and are symmetrical, in the sense that for a given message m, Ei(Di(m)) = Di(Ei(m)) = m. To preserve privacy, a user X will obtain the public key Ey for user Y and compute Ey(m)). Since only Y knows Dy, only Y can decrypt. A checksum or some other identifying pattern is embedded into m so that a valid decryption can be verified.

Digital signatures work similarly, except that when X wants to sign a message to Y, X uses his/her private key Dx and computes Dx(m). Upon receipt, Y computes Ex(Dx(m)) = m. Since only X had knowledge of Dx, only X could have signed the message. Privacy encryption can be combined with digital signatures by computing Ey(Dx(m)), which is decrypted as Ex(Dy(Ey(Dx(m)))) = m.

The public key register of the Ei need not be read secure, since the Ei are given away freely. The registry must be protected against corruption, since that would allow fraudulent keys to be given out. The channel to the registry must be secure to prevent "spoofing" attacks, but this can be done using public key encryption.

The disadvantage of public key encryption is that it is several orders of magnitude slower than conventional encryption because of the nature of the encryption algorithms. Thus, for instances where a session involves many messages or where high performance is required, a Kerberos-based system may be more appropriate.


Both Needham/Schroeder and public key encryption can support different levels of functionality. Without going into the details, more functionality or security requires more messages/encryptions or more frequent messages. Thus it is important to balance the security required with the costs of obtaining it for a given application.

Replay Prevention

Timestamps can be embedded in authentication tickets or encrypted messages to limit the time during which the message is valid. The recipient can determine how old a message it is willing to accept. This time must be selected with regard to propagation time, clock skew, and server response time. Shorter intervals increase security at the cost of the increased likelihood that valid messages will be discarded and the additional costs of obtaining new tickets or re-encrypting. Kerberos uses 5 minutes as its default.


With non-repudiation, a client cannot claim that it did not send a particular message. Given a message, the server can prove to a third party that the message could only have originated with the client; specifically, the server itself could not have forged the message. Basic Kerberos does not provide this, but extensions do. Digital signatures provide non-repudiation.

Multiple User Signatures

Extensions provide the ability for m of n parties to sign or otherwise validate a message in order for it to be authenticated. These algorithms are considerably more expensive than single signers.


There are really two dominant systems for authentication, one based on Needham/Schroeder, and the other on public key encryption. These are:

This research is sponsored by the Defense Advanced Research Projects Agency and managed by the U.S. Army Research Laboratory under contract DAAL01-95-C-0112. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied of the Defense Advanced Research Projects Agency, U.S. Army Research Laboratory, or the United States Government. 

© Copyright 1996 Object Services and Consulting, Inc. Permission is granted to copy this document provided this copyright statement is retained in all copies. Disclaimer: OBJS does not warrant the accuracy or completeness of the information on this page. 

This page was written by David Wells. Send questions and comments about it to 

Last updated: 04/22/96 7:37 PM 

Back to Internet Tool Survey -- Back to OBJS