Certifying Trust

Trust Models

Trust is a belief that an entity behaves in a certain way. Trust to a machinery is usually a belief that it works as specified. Trust to a person means that even if someone has the possibility to harm us, we believe he/she chooses not to. The trust requirements of a system form the system's trust model. All computer systems, protocols and security frameworks have trust requirements, i.e. they have trust relationships that the user needs to share. We may need to have some kind of trust to the implementor of a software which source code is not public, trust to the person with whom we communicate on a network, trust to the computer hardware that it provides us with correct computation results, and so on. The trust relationships that we are interested in here are those between us and some other networked entities. Those other entities may be fellow human beings or machines providing some service.

It is of equal importance to analyze the trust requirements of a protocol or a framework as it is to analyze the soundness of the technical methods that it uses to achieve security. Trust requirements may be analyzed in several ways. We may consider one generic notion of trust and find the entities that we need to trust. The next alternative would be to classify different types of trust and define the ways we need to trust each entity [YKB93]. Yet another refinement might be to define a degree of trust needed towards the other entities [BBK94]. The ways to categorize and analyze trust may be called trust modeling, but with a trust model we mean the set of trust relationships of a system.

As an example for analyzing trust, a bank may tell me that the most appropriate way to protect the data traffic between my workstation and their server is to use a cryptosystem where they provide me a good-quality keypair. (This is among the most reasonable security-related offers that banks seem to provide.) Not only need I trust this bank's capability to make good keys, I also need to trust the bank completely, because they have the key that is supposed to be secret and identifies the service user as me. Many people are willing to accept that, it is a bank after all. But the truth is that this trust extends to every employee of the bank that has access to those keys. Why would I want to take such a risk, if it is possible for me to create my own key, not known to anyone else? Of course, creating my own keys requires me to have enough trust in my own key generation software and hardware.

Security Policies

Closely related to the concept of trust is the concept of policy. A security policy is a manifestation of laws, rules and practices that regulate how sensitive information and other resources are managed, protected and distributed. Every entity may be seen to function under its own policy rules. In many cases today, these rules are very informal, probably even unwritten. The policy of an entity or part of it is often derived according to some hierarchy, e.g. next level in a corporate hierarchy.

Security policies can be meaningful not only as an internal code of function, but as a published document which defines some security-related practices. This could be important information when some outsider is trying to decide whether an organization can be trusted in some respect. This is one situation where it is of use to define the policy in a systematic manner, e.g. to have a formal policy model.

Another and a more important reason to have a formally specified policy is that a lot of the policy information should be directly accessible by the workstations and their software. Having a policy control enforced in software rather than relying on the users to follow some memorized rules is essential if the policy is meant to be followed. A lot of policy rules are already present in the operating systems, protocols, applications and their configuration files. A central policy storage and a policy supervising software would make these and other policy settings easier to maintain and analyze.

Digital Certificates

A certificate is a signed statement about the properties of some entity. In a digital certificate the signature is a number computed from the certificate data and the key of the issuer. If a certificate states something about the issuer, it is called a self-signed certificate or an auto-certificate.

Traditionally, the job of a certificate has been to bind a public key to the name of the keyholder. This is called an identity certificate. It typically has at least the following fields: the name of the issuer, the name of the subject, the associated key, the expiration date, a serial number and a signature that authenticates the rest of the certificate.

Not all applications benefit much from a name binding. Therefore certificates can also make a more specific statement, for example, that some entity is authorized to get a certain service. This would be called an authorization certificate. In addition to the fields in an identity certificate, more detailed validity fields are often needed. The "associated key" -field is replaced by the authorization definition field. The issuer and the subject are typically not defined with names but with keys.

In all certificate systems, but especially in identity certificates, it is important to choose a proper name space. The naming should be unique in the sense that no two principals have the same name, though one principal may have several names. Names should be permanent, if the principal so decides, so no enforced name changes should occur. In the authorization certificate naming schemes, the name binding may be early or late binding. Late means that when authority is bound to some name, the name need not yet be bound to a key, but this can be done afterwards.

Certificates and trust relationships are very closely connected. The meaning of a certificate is to make a reliable statement concerning some trust relationship. Certificates often form chains where the trust propagates transitively from an entity to another. In the case of an identity certificate, this is trust to some name binding. Authorization certificates often delegate some property or right of the issuer to the subject. It is also desirable that the system allows to limit the delegated authority in the middle of a path.

Certificate Loops

The idea of certificate loops is a central one in analyzing trust. The source of trust is almost always the checking party itself. For example, if a user wants to authenticate that a networked server is, actually, providing the service the user wants to use, the certificates used for this check must be trusted by the user. Specifically, the first certificate in a certificate chain must be trusted, implicitly or explicitly. Similarly, when the server wants to check the user's access rights, the certificates used to authenticate the user must by trusted by the server. Again, the server must be configured to trust the certificates in the chain.

Thus, a chain of certificates, typically implicitly starting at the verifying party and ending at the party claiming authority, forms an open arc. This arc is closed into loop by the online authentication protocol where the claimant proves possession of its private key to the verifying party. Such a loop is called a certificate loop. In Section 4.1, we return to this issue in more detail.

Outline of This Paper

In the next section we will discuss the currently most popular certification systems and compare the different certification approaches. In section 3 we are going to take a closer look to the SPKI and some of the new ideas behind it. Section 4 shows our view of certificate loops and presents parts of our implementation. In section 5, we will discuss the possible future directions of Internet security. The last section sums up our key ideas.

Certifying Identity

We did briefly mention the name binding function of an identity certificate. More generally, with a binding we mean some important relationship or connection between two or more aspects of a system. In the case of certification, such aspects include the person, the person's name, the cryptographic key, or the remote operation about to be performed. We would wish all the relevant connections to be strong bindings instead of weak ones.

See Identification certificate bindings shows the bindings of an identity certification system used for access control. The certificate chain does the binding of a key to a name. Name is authorized to perform some operation according to an access control list (ACL), stored in the service provider's private storage. When the service is used, a key challenge between the participants binds a key to the operation to be performed. These three bindings can be made strong with appropriate cryptographic mechanisms.

The strength of a binding is here seen to come from the mathematics of cryptography. In reality the strength depends on the trust relationships involved and is always subjective. We could draw the private key and the public key separately. This would bring one more step to the 'loop'. The binding between these two keys is the strongest binding of all.

But, the person-name binding is subject to some vulnerability. It is rarely taken into serious consideration at all, but usually assumed to be common knowledge. The larger the name space, the less likely that anyone would know the name of a specific individual. Alice might suspect that her old friend Bob Smith has a name in the global directory service, but there are so many people named Bob Smith in the world that it is unlikely Alice would know which of the thousands of Bob Smiths was in fact her old friend [SPKI97]. In a few special cases where you know what to look for, this binding can intuitively be considered strong, but it's never strong in the sense of cryptographic strength.

It can be argued that identity-based certificates create an artificial layer of indirection between the information that is certified (which answers the question "who is the holder of this public key?") and the question that a secure application must answer ("can we trust this public key for this purpose?") [BLA96]. Currently each application has to re-implement the mapping of names to actions that they are trusted to perform.

Of the existing identity certifying systems around, two have been taken into quite a common usage. PGP [PGP] has been a success since its introduction. X.509 [X509], while not taking an actual flying start, has lately gained some popularity despite the lack of any working global scale X.500 directory service.

Certifying Authorization

The bindings of an authorization certificate system are shown in See Authorization certificate bindings . The certificate chain binds a key to an operation. A key challenge also operates between an operation and a key, thus closing the certification loop. These two bindings are based on cryptography and
can be made strong. Again, we have chosen to draw the two keys together for clarity. Drawing them separately would just lengthen the certificate loop by one step.

The person-key binding is different from the person-name binding in the case of identity certification. By definition, the keyholder of a key has sole possession of the private key. Therefore, either this private key or the corresponding public key can be used as an identifier (a name) of the keyholder. For any public key cryptosystem to work, it is essential that a principal will keep its private key to itself. If the principal does not keep the private key protected (if the private key gets out to others to use) then it is not possible to know what entity is using that key and no certificates will be able to restore the resulting broken security.

So, the person is the only one having access to the private key and the key has enough entropy so that nobody has the same key. Common names are not automatically unique even if we add company information or other such constructs. So, the identifying key is bound tightly to the person that controls it and all bindings are strong.

The problem with the person-key binding is that from the service provider's point of view it looks like an undefined binding. The provider does not know who has control over the key. However, neither is this question essential in the most usual applications, nor can the traditional identity certification always answer this question. For the cases where the real physical identity of a keyholder needs to be known, [ELL96a] discusses different possibilities how to bind persons to keys without certification authorities. [SPKI97] proposes so-called process server certificates, issued by commercial enterprises, to aid in handling the extreme cases.

The feature of not having to bind keys to names is especially convenient in systems that include anonymity as a security requirement [BLA96, ELL96b]. It is easy for a user to create new keys for such applications, while creating an authorized false identity is (hopefully) not possible.

The most important authorization certification proposals are SDSI [SDSI96], SPKI and PolicyMaker [BLA96]. In section 3, we will have a more detailed discussion about SPKI.

Principals and Naming

The SPKI principals are keys. Delegations are made to a key, not to the keyholder. However, long keys are inconvenient for a mere human to handle. Using names instead of keys is necessary at least in the user interfaces. Names in the certificates also allow late binding, which means that one can attach some properties to a name and later define or change the name-key binding. Names can also serve the purpose of a certain role. Therefore it is useful to also have other names than keys. SDSI abandoned the idea of a global name space and introduced linked local name spaces. SPKI uses this same naming scheme, where everyone can attach names to keys and every name is relative to some principal. The names can be chained so that speaking about Alice's Mother consists of a name Alice in my name space and a name Mother in Alice's name space.

Names need not always refer to single users, but they can refer to a set of users as well. If an issuer makes a name-key binding while another similar binding to the same name is still valid, these two certificates do not conflict but define a group with at least two members. It is, of course, possible to revoke the earlier one, if the intention is to change the binding to a new. In fact, because SPKI certificates always increase the subject's properties, we will never have to deal with a situation where two certificates would conflict.

An SPKI certificate is closer to a "capability" as defined by [LANDAU] than to an identity certificate. There is the difference that in a traditional capability system the capability itself is a secret ticket, the possession of which grants some authority. An SPKI certificate identifies the specific key to which it grants authority. Therefore the mere ability to read (or copy) the certificate grants no authority. The certificate itself does not need to be as tightly controlled. [SPKI97]

From the certificate usage point of view, the involved principals are called the prover and the verifier. It is the responsibility of the prover to present the needed certificates. Based on these, the verifier determines whether access is granted.

Certificate Format

The current SPKI proposal uses S-expressions, a recursive syntax for representing octet-strings and lists. An S-expression can be either an octet-string or a parenthesized list of zero or more simpler S-expressions.

The core of the syntax is called a sequence. It is an ordered collection of certificates, signatures, public keys and opcodes taken together by the prover. A signature refers to the immediately preceding non-signature object. Opcodes are operating instructions, or hints, to the sequence verifier. They may, for example, say that the previous item is to be hashed and saved because there is known to be a hash-reference to it in some subsequent object.

The fields of an SPKI certificate are: version , cert-display , issuer , issuer location , subject , subject location , delegation , tag , validity , and comment . All of these, except issuer, subject and tag, are optional fields.

Version is the version number of the format. Cert-display is a display hint for the entire certificate. Issuer is a normal SPKI principal, i.e. a key or a hash of key. The location-fields define a place where to find additional information about that principal. For example, the issuer location may help the prover to track down previous certificates in the chain. Delegation is a true/false -type field defining whether the authority can be delegated further. Comment-field allows the issuer to attach human readable comments. Validity defines the conditions which must be fulfilled for the certificate to be valid. It is possible to define a time range of the validity and a detailed description of the chosen validation method.

The most complex fields are the subject and the tag. The subject can be either a key, a hash of key, a keyholder, an SDSI name, an object or a threshold subject. A keyholder subject refers to the flesh and blood (or iron and silicon) holder of the referenced key instead of to the principal (the key). A threshold subject defines N subjects, K of which are needed to get the authority. The tag contains the exact definition of the delegated authority.

5-tuple Reduction

Five of the certificate fields have relevance for security enforcement purposes: issuer, subject, delegation, authority (tag) and validity. These security-relevant fields can be represented by a "5-tuple":

 

(I,S,D,A,V)

 

In the basic case, a pair of 5-tuples can be reduced as follows [SPKI97]:

 

(I1,S1,D1,A1,V1) + (I2,S2,D2,A2,V2)

 

becoming

 

(I1,S2,D2,A,V)

 

if S1=I2 (meaning that they are the same public key)

and (D1 = TRUE)

and A = intersection(A1,A2)

and V = intersection(V1,V2)

 

The validity intersections are trivial. The authority intersections are defined by the tag algebra. The user does not have to specify an intersection algorithm for his tags, but one does have to write the used tags in such a way that the standard intersection algorithm gives the desired behavior [SPKI97].

By reduction, some chains of authorization statements will be reduced to the form:

 

(Self, X, D, A, V)

 

where "Self" represents the entity doing the verification. Any authorization chain not reducing to a 5-tuple with Self as an issuer is not relevant to decisions by Self.

Typical Transaction

So far we have talked about certificates and certificate chains. When a service is used, it must be known that the contacting user really is the entity that is authorized by the given chain. At this point, if not before, the user proves the possession of the identifying key to the verifier. This action closes the authorization chain so that every useful chain can be seen as a loop.

See Basic authorization certificate loop shows a basic authorization loop implemented with SPKI certificates. The three certificates are possibly created long before they are used. The server has delegated the permission to access the service to its policy administrator. In this certificate, the delegate-property is set to true so that the policy admin may make further delegations. The permission propagates through the policy administrators and their certificates to the service user.

To be complete, this example needs also another loop. See Basic service identification loop shows the corresponding service identification loop. This is used by the user to authenticate the identity of the service provider, and it may even be completed before the service is used for the first time. This loop does not have to travel the same path as the authorization loop. The middle nodes need necessarily not be official Certification Authorities (CAs) as perhaps suggested by the graph, but the assurance of the server identity and services may sometimes be gained via less official paths.

When the actual service usage takes place, the user provides the authorization certificates to the server. Some systems have proposed a central repository from where the server makes a search. SPKI could use such a storage. However, in the case of authorization certificates, the central repository can be seen as a privacy threat unless it is somehow protected against general searches.

In addition to the server and the user, there may be other participants in the certificate usage process. Some other entity may reduce part of the chain and issue a Certificate Reduction Certificate (CRC), which the server may use as part of the final reduction. One reason for using CRCs may be that the full chain contains certificate formats which the server does not understand. The server may also make its own CRCs for performance reasons, so that it need not make the same reduction several times.

Design Patterns

Design patterns are simple and elegant solutions to specific problems in object-oriented software design. [GAMMA] describes a set of such patterns to start with. These pattern descriptions can widen our design vocabulary in an important way. Instead of describing the designs on the level of algorithms, data structures and classes, we can catch different aspects of the larger behavior with a single word. The benefits of using a pattern are greatly amplified at the stage of documentation or when discussing the design with another person who is familiar with patterns. [GAMMA] classifies patterns for three different purposes: creational, structural and behavioral patterns.

Policy Manager Implementation

Our prototype consists of a main module and a number of protocol adapters. The latter ones interface the policy manager to various security protocols such as IPSEC and ISAKMP. We plan to add support for additional security protocols later on.

The basic structure of the Policy Manager is shown in See The structure and connections of Policy Manager . It has a control part, which is the main thread waiting for some tasks to appear to the task queue. The interface mechanisms are called adapters and each of them is implemented as a separate thread. The primary task queue is filled by the three different adapters: the applications adapter, the ISAKMP-adapter and the IPSEC-adapter. The exact usage and output of the Policy Manager depends on the interface created by the specific adapter.

The certificate handling subsection of the main module reads in chains of SPKI certificates, reduces them on demand, and participates on ISAKMP based authentication protocols. The result is a highly configurable ISAKMP security association policy that allows the properties of the created associations to be set up according to the restrictions and limitations expressed with the certificates.

In addition to handling certificate data, the system makes access control decisions, maintains secure network connections and stores policy information. It may also help other protocols and applications in their security-related tasks.

The function of maintaining network connections consists of establishing secure connections to other workstations, accepting connection requests and storing connection information. This may have to be done for the purposes of several different protocols. A secure connection between the parties is usually a prerequisite for any other communication, e.g. requesting a service. The protocols can also have other questions or mappings for the Policy Manager to resolve.

The service provider may use another trusted policy server, which may assist it in access control decisions. There may, for example, be one such a trusted server in an organization. Even if the service provider has all the needed information concerning the requested resource, it may have to ask for help in understanding all components of the request. Besides answering access control requests, the Policy Manager may need to create such requests or to parse and store other credential information. One of the resources to control is the policy database that it maintains: who can read or change what policies?

SPKI Implementation

We have designed an internal format for certificates. This format can hold the certificate information from several different transfer formats, for example PGP, X.509 and SPKI. This generic format is largely based on the SPKI structure and can therefore also contain and reduce certificate sequences. Certificate data can be stored to a certificate cache, which is a part of the trusted security variables of the system.

The data of a single certificate is stored in a tree-like class structure, part of which is shown in See Fields of a certificate . The structure is implemented according to the Composite pattern, which is a way to represent part-whole hierarchies in a tree structure. It enables clients to treat all objects in the composite tree uniformly. All of the classes in the structure are either composites or byte strings. Composites contain other composites and byte strings.

Arriving certificate data is first stored in an instance of a class specific to that format. The conversions between specific formats and generic format are done using the Visitor pattern. Visitor travels through an object structure performing some operation to the components. The operation is defined in the particular visitor and not in the component classes. This way we can define new operations by making a new visitor and without touching the complex object structure.