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.

Abstract

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.

Introduction

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:

Inventor: The inventor participants corresponds to the inventor or a representative of his. The inventor can, among other things, search the database of already issued patents, file an application, perform payments, receive office actions, and answer these. The inventor, who will be situated at a site other than that of any of the main databases, is only allowed access to (some) documents related to his application.
Examiner: The examiner (which may correspond to more than one person) is handling the evaluation of the filed patent, performs office actions, receives the corresponding answers, and more. The examiner, who may be situated on a machine other than one of those where databases are kept, is allowed access to information relating to his or her current cases.
SRB: This is the interface between participants querying the databases (such as inventors and examiners) and the databases. The SRB connects and interfaces to databases and other SRB's. Some databases are only stored at particular sites, making it necessary for SRB's to query each other for data. The SRB has access to the MDAS, where (possibly encrypted) tables are stored. The SRB has full access rights to all data.
Database: The database (of which there are several) is an entity which can be queried by the SRB.

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 inventor trusts all the other participants to perform their intended tasks, but does not want these to be able to impersonate him or (unless intended) to be able to read the messages sent he sends and receives. At the end of each communication session, the inventor may want a receipt of the transaction.
The examiner is trusted with all information regarding the filed patent, and can grant agents access rights to sensitive data, such as not already issued patents. He signs office actions in a way that must not be possible for the receiver or any other participant to forge.
The SRB trusts the other participants to perform the tasks they are asked to perform, but may want to limit their access rights to sensitive data. The SRB can grant agents access rights to such sensitive data after verifying that the request is valid. The SRB handles and passes along requests, but does not produce any data or requests.
The databases may not have any way of controlling access, and must therefore be disconnected from participants without the right to query them (i.e., all participants but the SRB).

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:

Signatures: A signature is an authentication on a document that can be verified by anyone [1] using the public key of the signer, the message signed, and the signature on the message. It is necessary to have the secret key corresponding to the public key in order to compute the signature on a given message. Signatures can be transferred, i.e., their validity can be checked by anybody, and they are therefore useful for contracts, receipts, etc. Signatures are characterized by being long (e.g., 1024 bits), and are not very quick to produce and verify, and for these reasons, should only be used when the functionality MACs do not offer is needed.
MACs: A message authentication code corresponds to a short and quickly generated/verified non-transferable signature on a document. Since it cannot be transferred (i.e., verified by a participant other than the one it was intended for) it cannot be used for contracts or receipts (if these need to be saved in case of a conflict.) but can be used for participants to make sure that the message they obtain is from the person they expect. Since they are very efficient, this makes them very useful for individual, small messages in interactive protocols. Here, all of these messages can later be signed if a receipt is needed. MACs require that the sender and the receiver of the authenticated message both know a (symmetric) secret that is used both for generating and verifying the MAC. This secret can be produced by one of the participants, and sent over in an encrypted form to the other, using a public key encryption method. MAC's can be implemented using stream ciphers, e.g., RC5.

[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.

Public key encryption: A public key encryption is a function of a message (the cleartext) and the receiver's public key. The corresponding decryption can only be calculated by an entity who has the secret key corresponding to the public key used -- i.e., the intended receiver. The disadvantage of this type of encryption is its relatively low speed, and its relatively long minimum length of encryptions.
Symmetric key encryption: A symmetric key encryption is a function of a message and a secret key. The message can be retrieved only by somebody who has access to the same secret key as was used for the encryption. The disadvantage of this type of encryption is that it needs a common secret key, which has to be established before the method can be used.

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 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):

Pseudo-random generator: We need access to a cryptographically strong pseudo-random generator. One possible interface, giving only one random bit at a time, could be to call a function GoodRandom after some seed has been initialized.
Choosing the scheme: We can choose a scheme by setting a variable of a type schemetype, that has a kind of the scheme (e.g., public key or symmetric key,) a name of the scheme (e.g., DSS, RSA, MD5, SHA, etc.), public information (e.g., the modulo), and keylength parameters (e.g., 1024 bits.)
Creating keys: If we let scheme describe what scheme we use, the result of CreateKey(scheme) will be a record that either (in the case of public keys) contains a secret/public key pair, or (for symmetric key) one key.
Encrypting messages: If scheme describes the type of scheme, message is the cleartext, and ekey is the (public or symmetric) encryption key, then the output of Encrypt(scheme,message,ekey) is the encrypted message ciphertext.
Decrypting messages: Using the above denotation, message is the output of Decrypt(scheme,ciphertext,dkey), where dkey is the decryption key corresponding to ekey.
Authenticating messages: The output amessage of Authenticate(scheme,message,akey) is the authenticated message, where akey is the authentication key.
Verifying authentications: The validity of an authentication is the boolean output of Verify(scheme,message,amessage,vkey), where vkey is the verification key corresponding to akey.