CS 513 System Security -- Lecture Notes for March 16, 1999

Authentication and Delegation in Distributed Systems (cont'd)

CS 513 -- System Security -- March 14, 1999 -- Lecture 14
Lecturer: Professor Fred B. Schneider

Lecture notes by Borislav Deianov

Recall that authorization and authentication are closely linked. In order for a reference monitor to make authorization decisions, the reference monitor needs to look up the identity of the user making a request.

Authentication of human "subjects" (users) is easy to treat in isolation; authentication of machines somewhat less so, for it involves two main questions:

Who is saying this?
On who's behalf is it saying this?

In centralized systems, we used capabilities and they had to be unforgeable. This functionality is achieved in a distributed system by using digitally signed certificates.

Last time we presented a method of using delegation certificates for authenticating machines. Typically, each workstation involved in implementing a service will keep cached copies of all delegation certificates for client systems, so it can forward these copies along with requests to any servers that it must contact in order to satisfy a request for service.

When a delegation certificate is no longer needed (e.g. the user logs out), the system should no longer have the right to represent the user. But how do we revoke these certificates?

Let us start with some simple (almost) solutions:

Include timeouts in certificates. There is a trade-off here. If we set the timeout too high, then there is a chance that an attacker might be able to make use of the certificate after the user logs out but before it expires. If we set the timeout too low, then the certificate might expire during an interactive session, forcing the user to create a new certificate (i.e. inconvenience). There is no general solution to this problem.
Deletion. Upon logout, the user can instruct all workstation that might have cached certificates to delete them. But how does the user know that they are really deleted? The certificates might have been intercepted by an attacker who can store them indefinitely.

We now consider a solution using delation keys, private/public key pairs. The public key will appear in the delegation certificate, the private key is held by the system. When a workstation wants to verify the validity of a certificate it challenges the owner of the private key to prove that it holds it. This is easily achievable without disclosing the private key (by employing a challenge-response protocol). To revoke a certificate, a system simply forget its private key.

More concretely, in our example from last lecture, the scheme changes as follows:

W₁ generates a (private, public) key pair (k, K);
the certificate D₁ becomes [K, W₁ for P]_SC;
when challenged to prove that it holds the private key for the public key K, W₁ can do that;
to revoke D₁, W₁ forgets the private key k -- D₁ no longer works since nobody else has k.

How can P know that W₁ will forget k when instructed to do so? As before, if P does not trust W₁ to do that, then P should not have given D₁ to W₁ in the first place.