kerowe@cs.umbc.edu
Charles K. Nicholas
nicholas@cs.umbc.edu
The explosion in use of the Internet for distributed information services is a cause for increasing concern with respect to the reliability of the various name services, especially the Domain Name Server (DNS). Name servers must provide a distributed capability to scale up for the World Wide Web (WWW). Unfortunately, distributed name services that are reliable in closed, well-regulated networks become unreliable as we scale up to open, heterogeneously managed networks.
We will examine the inherent unreliability in name servers and propose a scalable-cost solution for providing reliable name services. The use of digital signature technology has been proposed as a solution to the reliability problem. While this technology does form a basis for a solution, it is not a panacea for the reliability problem.
We will look first at important characteristics of WWW naming schemes. Then we will discuss the inherent unreliability of name servers and the root cause of this unreliability in the context of a classical problem in distributed systems known as the Byzantine Generals Problem (BGP). We will see that the application of digital signature technology relies on the Authenticated BGP and some very strong assumptions. Finally, we will describe a scalable-cost reliability solution that depends on the class of transaction that uses a WWW name.
Many acronyms are used to talk about WWW names: URI, URC, URL, URN, and UR*. In this section we will look at the characteristics of two kinds of Universal Resource Identifiers (URIs): Uniform Resource Locators (URLs) and Uniform Resource Names (URNs). A third naming scheme, Relative URNs, will be introduced as well. In particular we are concerned with how each naming scheme enables distributed information management.
Global names are essential to distributed systems, in that they provide transparency in several forms. The ISO's Reference Model for Open Distributed Processing (RM-ODP) [COU94] identifies eight forms of transparency:
The URLs provide the basic global naming scheme for the WWW. All URL names are global
names enabling access transparency for the WWW. At first glance it may appear that the URL
naming scheme also provides location and concurrency transparency, but it does not. Look at a
typical URL, http://www.ncsa.uiuc.edu/. Since the machine's IP address is
determined by a DNS lookup on www.ncsa.uiuc.edu, it looks like the URL is providing location
transparency. But a user must still know the logical location
(i.e., http://www.ncsa.uiuc.edu/). Any location transparency comes from the DNS and not the
URL naming scheme.
The URL naming scheme only appears to provide concurrency transparency because the WWW is predominately used to read objects. The underlying operating systems are providing the concurrent read capabilities. But the URL naming scheme does not enable concurrent read and write operations without interference from each other. So the URL naming scheme does provide access transparency, one of the most important forms of transparency, but none of the other seven transparency forms.
The URN naming scheme is a very important step for the WWW. Attributes of URNs [SOL94] include: global scope, global uniqueness, persistence, and scaleability. Global scope and uniqueness guarantee that a URN has the same meaning anywhere it is accessed and that the URN determines a unique resource. An integral part of a URN is the owner of the URN (i.e., Naming Authority Identifier). This allows for distributed control on the creation of URNs (i.e., scaleability). The persistence characteristic of a URN means that at any point in time there may be zero or more URLs to which a URN resolves (because of replication or retirement of a resource). Besides access transparency, the URN naming scheme provides location transparency. The other six forms of transparency are also provided by the URN naming scheme. Recall that providing the transparency forms only enables the distributed computing characteristics, and is a means as opposed to an end. According to the current specification, URNs are intended to be used by computers and are not intended to be human-readable.
Name aliasing is another important capability for the WWW. We see it in use today in the "Hotlists" and in implied aliases in URI Partial Forms and Fragment IDs (e.g., HTML abbreviations in ANCHOR and BASE HREFs). It is not appropriate to use the URN for aliasing. An URN is always a global name and is therefore independent of any local context. We will refer to the name aliasing capability as a Relative URN (R_URN) in this paper. The R_URN capability is necessary for the WWW to provide a means for people to refer to URNs. The local context for an R_URN should allow an R_URN=>URN name server to unambiguously resolve to a URN. This means than an R_URN in a document accessed by two different users could be resolved to two different URNs. This would also be true for a single user accessing an R_URN from different contexts. Access rights are a good example of context characteristics that could be used for resolving R_URNs.
An area of database security research that focuses on security issues from context-dependent aliasing is called polyinstantiation [THU91]. Polyinstantiation is a difficult problem in inference and integrity concerns for database security. By separating name aliasing, R_URNs, from the URN naming scheme, we can isolate the polyinstantiation problem to R_URN=>URN name resolvers and allow URN=>URL name resolvers to focus on supporting the forms of transparency.
Before we look at reliability concerns for name servers, we need to look at the capabilities we should expect in URN=>URL and R_URN=>URN name servers. One of the best known name servers on the Internet is the Domain Name Server (DNS). The DNS is used to map Internet logical names to physical addresses (e.g., www.ncsa.uiuc.edu => 141.142.3.134). The distributed nature of the DNS makes its architecture [MOC87] a good beginning point for the WWW name servers.
The main components of a DNS on a local host are a Resolver, a Name Server, the Master Files, and a Shared Database (Figure 1).
Users (or their agents) send a query to the Resolver. The Resolver tries to find the answer to the query in its Shared Database. If the information is not locally known, the Resolver will forward the query to foreign Name Servers. As the Resolver receives answers to its queries from the foreign Name Servers, the Resolver will update the Shared Database. The Shared Database is a cache for the local DNS. A local Name Server initializes the Shared Database with information from the local Master Files. All the information in the Shared Database has a specified lifetime. As the lifespan of the information is expiring, the local Name Server will contact foreign Name Servers to update the local Shared Database (i.e., maintenance queries). The local Name Server also responds to queries from foreign Resolvers (or foreign Name Servers acting as agents for foreign Resolvers). The local Name Server also handles the maintenance queries from foreign Name Servers.
The DNS allows for primary and secondary Name Servers. This provides a basis for fault tolerance and dynamic load balancing. There are two very important distinctions of the DNS from WWW name servers: 1) the DNS names (i.e., Internet names) are global names only if they are fully referenced from the root; 2) a DNS global name can only resolve to one answer (e.g., www.ncsa.uiuc.edu cannot have two addresses). To have access transparency for a DNS query, a fully specified and root-ed name is used (e.g., www.ncsa.uiuc.edu instead of www.ncsa.uiuc. or www.ncsa.uiuc.edu. ). Then where ever the name query is resolved it will result in the same answer.
The URN=>URL Server will not respond in the same manner. If a URN (which is globally unique) references a replicated resource, then the answer (i.e., the URL) will quite possibly be different depending on where the query comes from. Let's look at an example using the DNS basic architecture (Figure 2).
Assume there is an URN, "X," that names a replicated resource. There are three different URN=>URL servers that can authoritatively resolve the URN to a URL: S1, S2, and S3. A local Resolver at Host_A sends a query to the foreign URN=>URL Name Server, S1. S1 looks at current network load and characteristics of the URN and returns "http://site1/resource_Z" as its answer. At the same time, a local Resolver on Host_B sends a query to the foreign URN=>URL Name Server, S2. S2 looks at current network loading and characteristics of the URN and returns "http://mirror_site_8/resource_Z" as its answer.
The characteristics of a URN require that the URLs received by Host_A and Host_B refer to equivalent objects. What equivalent means for the objects is determined by the owner of the URN. Since the caches for S1 and S2 were current and both were giving authoritative answers (i.e., were following the "equivalence" policy established by the URN owner), then the URLs that Host_A and Host_B received should have been equivalent. Because of inference and integrity concerns associated with polyinstantiation, equivalence of answers from R_URN=>URN name servers is not straightforward. For the rest of this paper we will only deal with URN=>URL name servers.
When a user requests a URN name to be resolved, they will expect a certain level of reliability in the response. For a URN=>URL Name Server, if Host_A and Host_B received equivalent URLs, then the servers gave correct answers. If Host_A and Host_B consistently receive correct answers, then they would assume that the URN=>URL name servers were reliable. In assuming the name servers were reliable, there are two assumptions that were being made: 1) that the answer came from the name server it was reported to have come from, and 2) that the name server answered correctly.
More formally, we can say that URN=>URL Name Servers are reliable if they meet the following conditions:
Unfortunately the DNS has well-known problems that make it inherently unreliable [SCH93]. Since Internet names can only have one address, it assumes that all the servers are following a simple equivalence policy (i.e., time-to-live values are being observed for the Shared Databases). Also, the initial assumption for DNS was that there were no unreliable name servers. Changes have been made to the way DNS works that provide some reliability. The underlying reason for the unreliability of DNS (and name servers in general) is the Byzantine Generals Problem [LAM82].
The Byzantine Generals Problem (BGP) discusses reliability in terms of Good Generals and Bad Generals. If N Bad Generals can lie, then it requires a total of 2N+1 Generals to be involved in a decision in order for the Good Generals to all come to the same decision. If a Bad General can also impersonate a Good General, then for N Bad Generals it requires 3N+1 Generals be involved in a decision. So if N = 2 (i.e., there are possibly two Bad Generals that can lie and impersonate Good Generals), then it requires a total of 7 generals being involved in a decision.
A Good General for a local DNS is the Name-to-Address cache and the Bad General is the Address-to-Name cache. The Bad General must give an answer before a query can be formulated for the Good General to see if the Bad General is lying. By the BGP, there must be three generals involved for the Good Generals to know what the correct answer is. The DNS is inherently unreliable since a local DNS cannot give any answer if there is a conflict between the caches.
For URN=>URL Name Servers we need to apply the BGP differently. The example with Host_A and Host_B can be revisited considering the BGP. Assume that a generalized DNS architecture is used with replication support added. That means that the owner of "X" can specify an equivalence policy for replication of "X" and servers S1, S2, and S3 understand the equivalence policy.
Since it is normal for a URN to resolve two different URLs (e.g., the different URLs given to Host_A and Host_B), there is no way to tell if a URN=>URL Name Server is reliable. Either S1 or S2 could be 'lying' to a host. Even getting a response from S3 would not help because it could give a different, yet correct, URL for an answer. Additionally, an answer thought to come from S1 could actually be from a different server that is impersonating S1.
For a URN to a replicated resource, there should typically be a group of servers that are cooperating on maintaining the replicated resources (e.g., updates). Assume that group is S1, S2, and S3. All other servers are only reporting answers they have cached from one or more of these servers. It is possible to construct a protocol to ensure a reliable answer. Assume that only one server may lie. Then by the BGP, three servers are sufficient (i.e., 2N+1). This also assumes that a server cannot be impersonated. However, assume a server can be impersonated. Then it will require a minimum of four URN=>URL Name Servers (i.e., 3N+1) to be involved in managing a replicated resource to ensure reliability. In this case our group of servers (S1, S2, S3) is too small to ensure reliability.
For a URN being managed across the Internet, the assumptions that at least one URN=>URL Name Server can lie and that there may be a name server impersonating another are not unrealistic. Therefore it requires a BGP solution with a cost factor on the order of 3N+1.
Digital signature technology provides a means to reduce the BGP solution cost. There are several approaches to digital signatures. In this paper we will focus on public key based technology using the Secure Hash Algorithm (SHA) [NIS94a] and the Digital Signature Standard (DSS) [NIS94b] published by the US NIST. Under this approach, a hash value is computed over the information to be signed using the SHA. Then the DSS uses the Secret Key (of the Public Key / Secret Key pair) to generate a signature. The recipient of the information is also given the signature (but not the hash value). To verify the signature, the hash value is recomputed and a verify operation is performed using the new hash value, the signature, and the Public Key (note that under DSS the verify operation is not a decryption of an encrypted hash word).
A solution to the BGP that uses digital signatures is called the Authenticated BGP [LAM82]. This solution appears to solve the reliability problem. Since all messages sent are signed, then a server cannot be impersonated. Also, since a resolver could get the information from many different servers it could detect a lying server. There are several strong assumptions that must be made for an Authenticated BGP solution. In particular:
The first assumption means that all public keys must be distributed to the name servers and hosts in some secure manner. Otherwise a chain of certificates can be used to verify the public keys so that only one (or a small number) of public-keys need to be known by everyone. This is called Certificate Management.
The second assumption, protecting the secret key, is a problem as well. Anyone that gets access to a secret key can impersonate the real owner of the secret key. Given the ubiquitous lack of security on the Internet, signatures will need to be generated on stand alone systems to protect the secret keys.
In essence, the Authenticated BGP solution pushed the reliability problem back onto certificate management. Unfortunately, certificate management is a name server problem in itself.
Reliability for the DNS seems attainable given the strong assumptions and since there is one correct answer for mapping a host name to an address. The host name to address information in the DNS is fairly static in nature (although SLIP and PPP services are changing that). Off-line generation of signatures seems an acceptable condition for protecting a DNS's secret key. The hierarchical nature of the Internet name space will help in establishing certificate management capabilities as well (but it is far from being a trivial problem).
For URN=>URL Name Servers, there are many 'correct' answers when there is replication of URLs. But since every URN has an "owner" part, we can establish a group of name servers (i.e., generals) that must agree about a URN. However, URNs will be dynamic by nature. That means that URN=>URL Name Servers will need to generate signatures on-line. This will make the secret keys much more susceptible to compromise.
It appeared that digital signatures provided a low cost solution for the Authenticated BGP. For DNS it is reasonable to believe that this solution took the 3N+1 cost down to 2N+1 (and down to N if we ignore certificate management costs). We see that the dynamic nature of URNs and the replication of resources they represent does not allow us to use the assumptions of the Authenticated BGP solution. So for URNs on the open Internet it will require a 3N+1 cost solution to provide for reliable name servers.
To reduce the cost of having reliable URN=>URL Name Servers, we need to find a way to be able to make some stronger assumptions. Our approach is to look at the kind of transaction in which a URN is used. Four example classes of transactions are: Local Workgroup, Enterprise Wide, Inter-Corporate, and Commercial Internet. These classes are significant because they allow different assumptions to be made that can reduce the cost for reliability.
Transactions in a local workgroup involve users that are co-located and interact on a continual, informal basis. Local workgroup networks are typically closed and centrally managed. URN=>URL name servers can be trusted not to lie. If the local workgroup is connected to outside networks, then impersonation can still be a concern. The URN=>URL name server should be on a protected machine on the local network. This will allow the URN=>URL name server to use digital signatures with minimal risk of compromising the secret key. Certificate management is simple since we are dealing with centrally managed workstations and only one public key must be known across the local workgroup. This provides us an N cost solution for these transactions.
Enterprise wide transactions are typified by geographically distributed resources managed under a single corporate policy. It is still reasonable to assume that URN=>URL name servers are truthful. However, impersonation is a larger concern because of increased network interconnections. A digital signature approach is still very cost effective. Only a small number of public keys need to be known across a corporation. The use of short certificate chains would be a better choice for lager corporations. Although certificate management will require more effort to set up and maintain, this is still an N cost solution.
Inter-corporate transactions are those that involve separate, autonomous corporations that have established an agreement for a joint activity. For this class of transaction there is an agreement for sharing some proprietary information. These inter-corporate transactions may involve multiple corporations (e.g., a contract teaming effort). Again, the truthfulness of the name servers is a lower risk assumption, yet impersonation becomes an even greater risk. The number of public keys involved in verifying signatures becomes more distributed. Compromise of the secret keys is a greater risk because of the heterogeneous management of the systems involved. A 2N+1 cost solution should be used to ensure the reliability of the URN=>URL name servers. The cost will come from the certificate management approach that should be used.
With the beginnings of commercial transactions on the Internet, we will see URN=>URL name servers involved in these transactions. Impersonation of either the buyer or seller is a major concern. The general lack of security capabilities on workstations makes the protection of a buyer's secret key very difficult. Public keys of sellers will change frequently enough that certificate chains must be used to verify a seller's signature. One approach is for a buyer to have one well-known source to go to for certificates (e.g., an internet service provider). It will be the responsibility of that source to implement a 2N+1 or 3N+1 cost solution for certificate management. The URN=>URL name server will still only need an N cost digital signature solution.
The examples with the four transaction classes were assuming that the URN=>URL name server was only providing access and location transparency. If replication transparency is implemented, the reliability solution cost will be higher. For the local workgroup we can still assume an N cost reliability solution with replication. For enterprise-wide transactions involving replication, URN=>URL name servers should implement a 2N+1 cost solution if they manage resource names that are important or sensitive. The inter-corporate transactions that involve replication should implement a 2N+1 cost solution. Commercial-internet transactions need at least a 2N+1 name server implementation in addition to the 2N+1 or 3N+1 certificate management cost solution.
Since a name server will probably handle all four classes of transactions, each URN=>URL name server should be able to provide the full reliability capabilities on a per URN basis. The digital signature isolates the 3N+1 cost to the certificate management reliability problem. In addition, any URN=>URL name server that implements the digital signature approach can also decide how strictly the policy is to be maintained. It may be sufficient to just detect if a problem occurs later on and not impose a delay on user tasks. At other times it may be necessary to prevent (i.e., reduce the risk of ) the occurrence of a problem from an unreliable name server.
It is essential for the growth of the WWW to implement URN capabilities that provide all the transparency forms. We have outlined the fundamental reliability concerns for the URN=>URL name servers. Understanding their basis in the Byzantine Generals Problem provides a path to a scalable-cost solution. The digital signature approach must be designed into these name servers. In particular the ability to identify the class of transaction that a URN may be involved in needs to be implemented.
The R_URN=>URN concept was also introduced. Through this we saw the importance of keeping aliasing capabilities separate from the URN. Further research is required for solutions to the polyinstantiation problem of R_URNs. However, being able to assume reliable URN=>URL name servers is fundamental to any solutions to the polyinstantiation problem.