Authentication Mechanisms

Chaitanya Baru, Markus Jakobsson, Wayne Schroeder

This document, combined with the associated Software design document, describes an Authentication/Privacy software system under development at SDSC/UCSD for MDAS/DOCT.


In the DOCT communication network, there is a need for authentication mechanisms: these are methods for one participant to convince another that some data originated with him or her. The type of authentication mechanism that has to be used depends on the trust model (i.e., whether the sender and receiver trust each other or not) and the use of the authentication (e.g., whether it needs to be transfered to a third partry, etc.) There is also a need for encryption, which is often obtained using methods related to those for authentication. The goal of this paper is to serve as an overview of the expected setting, and of what types of authentication and encryption mechanisms are suggested.


When two protocol participants communicate over an insecure channel (such as the Internet, LANs, etc.) there is a need for the sender to authenticate himself and the message sent so that the receiver can be convinced about the sender's identity. There are different types of authentication: It may somtimes be enough that the receiver knows that each message received is authentic (i.e., sent by the claimed entity,) but sometimes it is also necessary to be able to pass this authenticated message along to a third party, who must then also be able to verify that the message is authentic. The type of authentication used also depends on the trust model: if the participants communicating only need to establish that the messages sent are from whom they are claimed to be, and the sender does not mind that the receiver knows the secret he is using to authenticate with, then so called symmetric authentication can be used. If, on the other hand, the messages have the structure of contracts, or if the participants do not trust each other, then the sender does not want the receiver to know his secret, and so called assymetric (or public key) authentication can be used. The efficiency of the authentication depends directly on what type is chosen, and it is therefore important even from this point of view that the proper method is employed.

In this paper, we will look at the expected trust and communication model for the DOCT project, and discuss what types of authentication and encryption methods should be used in different situations -- this discussion will hopefully help DOCT participants choose the type of authentication they need. Instead of focusing on available commercial products (such as SSL, Kerberos, PGP, etc.) we will look only at the wanted properties, in order not to confuse the issues or to choose a method that was not designed for the purpose we would use it for. The importance of using a certain method is not only to have a well-understood and uniformly secure program, but it will also alleviate security analysis and make the often thorny issues of fault tolerance in conjunction with security needs easier to deal with.

In the DOCT communication network, there is a wide variety of participants; the level of trust (and therefore, the need for authentication) differs greatly between these. We present some of the anticipated participants along with a brief discussion of what their authetication needs may be, and how they differ in the trust model. These participants are thought to correspond not to physical entities so much as logical entities, e.g., the agents and the conceptual parties of the protocols.

The participants we will consider are as follows:

Trust Model: All the participants need protection against impersonation of them on a protocol level, but sometimes, e.g., in ``informal discussions,'' it is sufficient that the receiver knows who the sender of a message is, even if this message could be forged by the receiver to a third party (i.e. via a symmetric shared secret).

The SRB is on the same local network as the databases it controls, and therefore, no strong access control is needed here. If this network is used for other purposes, Kerberos (or similar) may be used to handle access and trust locally. However, since the other participants (inventor, examiner, SRB's) are connected by an untrusted network (on which eavesdropping, message injection and message removal are possible), and on which there is no trust manager established, a stronger type of authentication has to be used there.

Some of the above participants may need a public key, to which they know the secret key, and which some publicly trusted authentication agency has authenticated. However, the inventor only needs a pair of a public and a secret key. It is not necessary for him to have the public key authenticated if this is only going to be used to file the patent (if he would like to file the patent in somebody else's name, that is his own problem!) We assume that those participants that need to authenticate themselves to others have a (possibly authenticated) public key, to which they know the corresponding secret key.

Here, a participant (e.g., the SRB) may have its secret key distributed on several machines in order to increase availability and decrease trust, but this will be transparent to everybody but the persons specifically implementing this entity, and will therefore not be considered at this point (but may be important when the schemes are to be chosen, which is another reason why we only want to specify the interfaces and not at this point specify what is behind them.)

Authentication Methods

There are two types of authentication methods, one which is referred to as a digital signature (or plainly: signature), the other one often as message authentication code (MAC). These types can be described as follows:

[1] Certain types of signatures limit this verification ability, which may sometimes be of interest, but is not expected to be used in the DOCT environment.

Encryption Methods

Similar to authentication, there are two types of encryption methods, one which is based on public keys (and is therefore related to signatures) and one which is based on symmetric keys (and related to MACs.) Just as for the two related authentication methods, the public key based method is slower than the symmetric key version, but more versatile. These two methods are often used in conjunction, e.g., a symmetric key is used to encrypt a message, and this symmetric key is then encrypted using a public-key method, and the encrypted symmetric key is sent over along with the encrypted message. This combination combines the benefits of the two methods without inheriting their respective disadvantages.

Suggested Solution

We assume that there is a key directory, in which public keys with their corresponding names of entities are stored. Some participants, e.g., the inventor, only need to know a very limited number of such pairs, e.g., the PTO; others, such as the SRB's will have a more extensive list.

We suggest that for each session, the initiator of the session generates a request (possibly time-stamped) and signs the request using his signature scheme. He appends a symmetric key to be used for encryption and authentication of the following messages, and encrypts the signed request and the symmetric key using the receiver's public key. The encrypted message is sent to the intended receiver, who decrypts it.

If a reply is generated, this is autheticated (and simultaneously encrypted) by XOR-ing the message with the output of a stream cipher keyed with the received symmetric key. Further communication in the same session uses this method as well, unless a receipt (a transferable piece of authetication) has to be generated, in which case the sender signs the message using his signature scheme before encrypting it and sending it.

This type of solution will use the high security of the signature and public-key encryption scheme (e.g., RSA) to establish contact, and then a faster symmetric method to perform the rest of the transaction.

Suggested Interface

We need interfaces for generating a random numbers[2], generating symmetric keys and pairs of secret and public keys, signing a message, verifying a signature, generating a MAC, verifying a MAC, encrypting a message, and decrypting a message. We will elaborate on these:

The following high-level description of the interface should be seen as a possible interface (Comments and suggestions are much appreciated):

[2] (It is very important for the security that the right type of random number generator is used -- the random number generator supplied by the programming language can not be used.)