LDAP and DNS are not the only solutions available. We first motivate our decision to compare these two. Our study concentrates on the use of PKIs in global, open network such as the Internet. Our basic needs are to be able to, interactively or automatically, look up application keying material or certificates using email addresses or hostnames as search keys. We do not need any additional cryptographic or security operations in the lookup service. Usually not even complex search capabilities are needed. Alternative protocols such as HTTP and FTP [45] do not meet our first requirement. However, both LDAP and DNS can meet this requirement.
Another way to see why LDAP and DNS are the two most relevant choices to consider is by looking at the currently most used certificate implementation on the Internet, the X.509-derived PKIX. X.509 certificates were designed to be used with the X.500 directory service. LDAP can be seen as ``X.500 for the Internet''. It is based on the X.500 protocol and the X.500 directory service model, but updated for use in the Internet. Thus LDAP is a good candidate for our study. X.509 certificates are often used by Internet hosts and Internet email users. DNS, via its security extensions, tries to solve similar goals, e.g., how to attach a public key to a host or email user. However, the security extensions of DNS have not been as successful as X.509 certificates for this purpose to this date. Thus, since X.509 certificates are used by entities addressed in the DNS model, we chose to study how to distribute the certificates through the same system. It is an appealing thought to combine a successful certificate format (X.509) with a less successful directory service (X.500), with a successful name lookup service (DNS) with a to this date rarely adopted security service (Secure DNS).
Certificates may be used in very different environments, from proprietary solutions within small companies with a handful of entities that need a security service, to world wide networks consisting of a multitude of protocols and applications without any organization in full control of everything. Different environments place different restrictions on what services are expected and needed. The environments we consider share the following characteristics:
We see that PKIX certificates stored in LDAP or DNS systems fulfill our needs.
Just like certificates, directories can be used in a variety of ways. Again, in open networks certain characteristics are interesting and others are not. For example, being able to locate and retrieve a certificate for a given email address is very important. Being able to list certificates for people named Adam is not very interesting for two reasons. First, it can be abused to collect information. Second, it does not scale; there are millions of Adams out there. More complex queries are, where deemed necessary at all, better handled by more specialized agents in local environments that need them (e.g., a company wide phone book).
Even though one of our protocols, LDAP, provides much more complex directory operations than DNS, we will not consider most of them for this reason. Both DNS and LDAP satisfy our needs here as well.
Perhaps the most important service of a Public Key Infrastructures in open networks (such as the Internet) is locating certificates. The problem is easy to understand; if you want to send encrypted email to kalle@josefsson.org, how would you get the keying material (his certificate)? If you want to establish a secure IP connection to www.seb.se using PKIX Certificates, how would you get their certificate?
There is no single generic solution to this problem today. One widespread solution for the email case, are large ``white-pages'' accessible through the world wide web [97] [92] [75]. A whitepage service is a centrally controlled directory of information, much like a phone book. Adding, deleting and updating information is done by contacting the service provider. This approach lacks several important features though, including:
Since organizations are not in direct control of their own data, there will be a delay when data is changed.
Most white-page services do not provide any means to protect the integrity of data. This means that it might be possible for an adversary to modify data at the white-page service, or in transit to or from the white-page service.
Most white-page services lack guarantees of the origin of data. Thus you do not know if the information you learn about X is what X, and no-one else, actually wants to have published.
For security related material, many organizations would prefer to be in control of what kind of information is published, and not to rely on an external partner.
This makes whitepage services unsuitable for storage of security sensitive information, such as certificates. Some of these, and other, problems can be solved by using directory technologies such as LDAP and DNS. However, before data can be located using these protocols, we must have a mean to identify data. The next section discusses this issue.
PKIX certificates are based on X.509 certificates. X.509 certificates
were developed to secure X.500 directory systems. However, these
certificates are not restricted for use only within the X.500
directory system. This is fortunate, as the X.500 directory system
itself has not been successful (at least compared to information
stored on the Internet). PKIX is an effort to make the original X.509
certificate more suitable for use on the Internet. Since X.509 defines
an identity based certificate![[*]](footnote.png)
these certificates
must include names of entities. Entities include certificate owners
and certificate issuers. Version 1 and 2 of X.509 use X.500 names
exclusively to identify these entities. An understanding of names used
in X.509 certificates thus requires a basic understanding of the X.500
directory service, which we now present.
The X.500 directory is much like a telephone directory. Given a name, you can find information stored under this name. Data in an X.500 directory consists of a set of entries each having an unambiguous Distinguished name (DN). Each entry represents a real-world object, such as a person, an organization, a computer, or a nation. The directory entries consist of attributes that have a type and one or more values. An entry can contain several attributes, such as phone number and addresses. Types are often abbreviated, ``C'' for country, ``O'' for organization, ``CN'' for common name, etc. All entries are stored in a tree-like structure called the Directory Information Tree (DIT), where each level in the hierarchy can introduce a Relative Distinguished name that, when combined, form the Distinguished name. Figure 4.1 illustrate these concepts.
This naming standard has prevailed even in current PKIX certificates. This is unfortunate, since most modern applications never use X.500 names or X.500 technology but rather internet names when addressing objects. By ``Internet names'' we mean IP addresses (130.237.72.201), domain names (www.kth.se), email addresses (someone@kth.se), URLs and similar names. However, X.509 version 3 certificates allow for ``alternative'' names in addition to X.500 names. This new standard defines how IP addresses, domain names, email addresses, URLs etc can be stored as names in certificates. This naming complexity can of course cause problems when certificate lookups are implemented in internet applications. If someone@kth.se is not used to locate a certificate for sending mail to someone@kth.se, how do I find out what should be used for locating the certificate?
LDAP is closely related to the X.500 model, and the Directory Access Protocol (DAP, the ``L'' in LDAP stands for Lightweight). LDAP is targetted for use on the Internet though. However, LDAP does not provide the global infrastructure that DAP was intended to operate in. To see how this is a serious problem, consider that we only replace the problem of locating certificates by locating the LDAP server! A number of techniques for solving that problem exist [42]:
One solution is to use a common and well-known domain name for LDAP
servers [39]. When an application is searching for a
certificate for kalle@jos
efsson.org the application
contacts ldap.josefsson.org and looks up the certificate. Of
course, this scheme relies on DNS to work.
This is a recent idea that also relies on DNS, but in a different way than the previous idea. Instead of using ``well known names'' as the previous idea, it uses the concept of ``well known services'' which is more robust. A well known service is ``LDAP'', ``HTTP'' or similar. It is possible to look up the well known services (e.g., the service ``LDAP'') for a domain, in order to find the server name [38]. This information is also stored in DNS. To illustrate, a client asks the josefsson.org domain server ``Give me the name of your LDAP servers'' and contact server hostnames are pointed out by the answer. In short, a layer of indirection is added.
LDAP version 3 allows LDAP servers to re-direct clients to other LDAP servers, based on the query [96]. This is similar to the previous idea in that it uses indirection, but it does not require other protocols than LDAP itself.
The simplest solution is to require administrators to configure applications to use the ``correct'' LDAP server. This is prone to errors and does not work well when the number of servers grows. A better approach might be to combine this approach with the previous, LDAP referrals.
We should also note that LDAP uses X.500 attributes when looking up data. Fortunately, common Internet names (email addresses, domain names, etc) have well defined X.500 types so this is not a serious problem.
Using DNS to store certificates is an appealing method. DNS is already an integral part of practically all computers on the Internet, used to look up addresses of World Wide Web sites, of mail servers for email, etc. Thus there is no need to introduce new technology that users (and applications) everywhere will have to adopt to be able to look up certificates. Also, the DNS protocol is more lightweight than LDAP (see section 4.4).
We should mention two serious drawbacks of DNS compared to LDAP as a certificate query protocol. However, both of these drawbacks might be considered as advantages in the scenario we are interested in, we include some rationale for this below.
We have discussed this earlier; searching for people named ``Adam'' is not productive on a global scale and may even open up for abuses.
The reason DNS cannot provide this functionality is that it is designed to contain public information without any access control. Thus this argument is moot, since the intended use of directories we are interested in are public by assumption. The ability to restrict access to resources would harm Internet wide usage of the system for certificate look up.
Both issues stem from DNS being a less complex protocol than LDAP.
We should mention two specialized uses of DNS as a certificate directory.
It is possible to set up a private DNS infrastructure within a company. This is known as an Internal DNS. All of the protocol benefits (small overhead, low latency, etc) remain, but the infrastructure of the Internet DNS is lost. Our study is intended towards the use of DNS as a certificate directory in open networks, so we will not discuss this kind of operation further.
Certain organizations may not want to handle the administrative burden of maintaining a certificate directory. Instead, they may purchase this service from a third party. This is possible to support with DNS, since it supports cross-domain aliases. As an example, consider an alias for the DNS domain jas.nada.kth.se that points at jas.nada.kth.se.trustedthirdparty.com. Since this mostly is an operational policy decision, we are satisfied with noting that this is possible.
Something related to looking up certificates from a directory, is to update certificates in a directory. This is illustrated in figure 4.2. Both LDAP and DNS provide this functionality.
However, neither LDAP nor DNS are primarily designed to store certificates. As a consequence, neither of them supports the cryptographically ``natural'' way of authenticating a certificate update: Proving that you posses the private key, corresponding to the public key in the certificate, allows you to update the certificate. Rather, both LDAP and DNS use other authentication mechanisms. The following sections describe how updating works in DNS and LDAP, focusing on authentication of updates.
LDAP supports addition, deletion, modification, and renaming of entries. Authentication is performed, in LDAP version 2, by means of clear text passwords or Kerberos [70]. The Secure Socket Layer (SSL) [43] [34] is often used to protect clear text passwords during transit. LDAP version 3 supports an extensible authentication framework called Simple Authentication and Security Layer (SASL) [73]. This is a successful security framework, used by other protocols such as IMAP4 [12] and POP3 [74]. It supports several authentication methods, which are more secure than password based schemes.
Updating data in DNS has traditionally only been done by manual editing of static ``zone files'' located at each DNS server. This works well when the frequency of changes is fairly low. If the frequency of changes increases, it can sometimes be solved by other means. One solution is to store data in generic databases. The information can be updated in the database, and trigger automatic generation of zone files.
Simply put, the DNS protocol was not designed for remote data updates. Recently, in 1997, a standard was published called ``Dynamic DNS'' [93]. It made updating possible within the DNS protocol. Dynamic DNS supports addition, deletion and modification of entries. Our concern here is how the updates are authenticated.
``Dynamic DNS'' assumes that authentication should be handled by other means (such as IPSEC), or by a security framework described in [19]. The IPSEC case is not interesting to us, as we wish to study DNS itself. The other alternative proved to be a failure after implementation experience. Thus, some new ideas had to be developed. Today, two solutions exist to authenticate DNS updates:
This standard, known informally as SIG(0), uses public keys stored in DNS to accomplish authentication of data. Data is digitally signed with a private key that has a corresponding public key stored in DNS. The digital signature is sent together with the data, and the remote system retrieves the public key from DNS and verifies the signature. This specification is as part of the Secure DNS specification [20], later updated by [1].
Transaction signatures (TSIG) [94] do not mandate any specific cryptographic operations, but is used to transport any kind of authentication data. It is intended to work with a variety of algorithms. One of the reason behind developing transaction signatures was that SIG(0) requires computationally expensive public-key operations and complex authentication logic. Transaction signatures, on the other hand, use message authentication codes (MACs). Currently two specifications make use of transaction signatures:
This is a simple algorithm to calculate message authentication codes. It uses shared preconfigured symmetric keys. [59]
This uses the extensible security framework of GSS-API [65] to perform message authentication. It establish shared secret keys that are used temporarily. GSS is a security framework, often used in combination with Kerberos [70], which provides security services such as privacy and integrity. It enables DNS updates to be securely updated using an already installed security infrastructure.
LDAP is without question the most flexible protocol when it comes to updating data and authenticating updates. In table 4.1 we list supported operations in DNS and LDAP. It should be noted that renaming is not an essential function as it can be emulated by deleting a record and adding it by another name.
Support for commonly used authentication methods in DNS and LDAP are shown in table 4.2. Clearly, authentication in LDAP version 3 is more complete than in DNS. (The authentication methods are Kerberos [70] GSSAPI [65], HMAC-MD5 [59] CRAM-MD5 [57], DIGEST-MD5 [63], RSA SecurID [78], and PKIX/TLS [15] [95].)
Looking up and retrieving certificates over a network will of course have a impact on both network and servers involved. In this section we will study the DNS and LDAP protocols. After a description of the protocols, we proceed with theoretical discussions of three different aspects of performance. The discussions are illustrated with real-world benchmarks.
The three different measurements we considered to be of importance are:
Before we begin, we wish to make a comment about the inherent caching in the Domain Name System.
The nature of DNS, being a caching distributed database, makes both measuring and predicting real-world numbers difficult. To be able to make good predictions, one would need to simulate a network consisting of, say, a hundred thousand servers and millions of clients. Clients and servers are connected by different types of networks, so different latencies and bandwidth would need to be simulated. This is not trivial. Instead of simulating a network, one can measure performance on a real network though, one such study is presented in [53].
In our DNS benchmark we will limit ourselves to studying one single server, connected to several clients. This is not without justification. An organization setting up a DNS environment is concerned with how their own server is performing. If we disregard caching in DNS, our comparison between DNS and LDAP would be on equal terms. We must consider caching though, since it is a key component of DNS. So, how much does it affect performance? First, at least it does not degrade performance. This means our results for DNS will reflect a worst case, while our LDAP results reflect the normal case. The discrepancy between our benchmark and the real world thus depends on how large the impact of caching is. We can make some conjectures about this, since the caching mechanism is well-defined. The main application we focus on, electronic mail, is such that the time between lookups is fairly long. You usually do not send more than a few messages to an individual per day. The size of these savings are thus only a small multiple of the differences in latency and bandwidth between the remote, official, server and your local, caching, server. For end users, the savings are hardly noticeable compared to the time to send the entire message. All in all, by studying the behavior of one DNS server we get a ``fair'' comparison between LDAP and DNS by ignoring the more complex issues of the whole system.
The DNS protocol is designed to be compact and simple. It runs over a datagram transport service, and does not require it to be reliable (e.g., DNS handle packet loss and packet size limits internally). The datagram service normally used is the Internet Protocol User Datagram Protocol (IP/UDP). UDP packets have a maximum size in practice, and the Internet Protocol Transmission Control Protocol (IP/TCP) is used as a fall-back when the maximum UDP packet size is exceeded. The protocol is binary, unlike many other Internet protocols that are text based. The binary encoding is used for compactness.
The DNS protocol uses the same envelope for all communication. The envelope is illustrated in figure 4.3. The envelope's first member, the header, is present in all packets and contains control information. Besides packet identity and packet length information, it contains information on whether the packet is a query or a response; if the packet is truncated (indicating that the question should be re-sent via TCP); etc. For query packets, the ``question'' field is present (e.g., has non-zero size) and the remaining fields are empty. For ``responses'' the question field is empty and remaining fields contains data. The ``question'' field, if present, contains a domain name (ASCII string), a domain type (integer) and a domain class (integer). The remaining three sections have the same structure, and contain Resource Records (RRs). Resource Records consists of a domain name, a type and a class, together with the corresponding data. (For comparison, the question section contains all fields except the data.)
Again, not all sections need to contain data. The header section specifies whether there is data or not in each section.
This is a brief overview of the DNS protocol. The protocol is described in [71], with a good hands on introduction in [8].
The Lightweight Directory Access Protocol (LDAP) [96] is based on the Directory Access Protocol, which is a part of the comprehensive online directory developed through the standardization process of ISO and ITU. This original standard and service is known as X.500 [10]. The LDAP protocol was designed to run over a connection-oriented, reliable transport. Both DAP and LDAP are described using ASN.1. We will not go into the details of ASN.1 but rather use familiar terms when talking about data structures.
Like DNS, all protocol operations are encapsulated in a common envelope. This envelope is shown in figure 4.4, where only some structures have been expanded. As can be guessed by the figure, the LDAP protocol is much more complex than DNS.
This is an overview of LDAP, [96] is the definitive source.
This measurement is of special importance in high latency environments, such as mobile application. Protocols that accomplish the same thing, by trading space, CPU processing or other resources to reduce the number of round trips, will be more efficient under these circumstances.
Since DNS can use both UDP and TCP, while LDAP only uses TCP, we first compare the ``round trip'' characteristics of these underlying transport protocols. UDP [81] does not incur any round trips other than those of the application protocol (e.g., DNS). Recall from the introduction section that TCP [83] on the other hand provides reliable connections on top of an unreliable transport layer. This requires some overhead, mostly due to round-trip costs of acknowledgments. If a packet or an acknowledgement is lost, it is re-transmitted. Retransmission only occur if packets are lost, this is relatively uncommon so we ignore this additional complication. Figure 4.6 and 4.7 illustrates the packets sent in setting up and tearing down a TCP connection.
A DNS query using UDP has the simplest characteristics, one packet is sent from the client A to the server B. The server B responds to the query by sending a packet to A. This is illustrated in figure 4.8.
A complication occurs when any of the packets exceed the size limit of the User Datagram Protocol. When UDP is transported via IPv4, this limit is around 600 bytes. For IPv6 this limit is around 1500 bytes. The protocol handles this by returning a truncated packet (via UDP), with control information in the header informing the client that the packet was indeed truncated. If the data the client was interested in is contained within the first, non-truncated, part, all is fine.
However, it is more likely that the client needs the entire response packet. DNS solves this problem by describing a fall-back mechanism to use TCP. Now, a client receiving a truncated response will query the server again, using TCP. Of course, this adds the round trip costs associated with TCP connections. This case is illustrated in figure 4.9, where the DNS packets are highlighted using thick lines.
An LDAP query is more complicated. The protocol is transported with TCP. This means that the round trip costs of setting up and tearing down TCP connections are always added. Also, the LDAP protocol itself is more ``heavy-weight'' than DNS. Figure 4.10 illustrates round trips involved in a complete LDAP query. Thin arrows are TCP packets, thick arrows are LDAP packets. We now describe each of the thick arrows, the application level.
LDAP uses one round trip to set up the connection, sending a ``bind request'' packet in the forward direction, and returning a ``bind result'' packet. The query itself is contained in one ``search request'' packet. The answer (e.g., certificates) to this query is sent in ``search entry'' packets. There may be zero or more such tokens sent, depending on how many records matched the search criteria. The status of the whole search is sent from the server to the client in a ``search response'' packet. The client closes the connection with by sending a ``unbind request'' and closing the TCP connection.
Practical experimentation, using the network packet sniffer Ethereal [24], confirms our theoretical discussion. We summarize this sections' results in table 4.3.
We are studying the usual representation of PKIX, but we should note that there are others which are more compact [66]. Of course, the choice of representation affects certificate size. A comparison between different representation formats is outside the scope of this section.
Typical sizes of PKIX certificates for common key lengths are shown in Table 4.4. The choice of algorithm and key length influence the size of certificates. There are other factors that affect certificate size as well. Certificates usually store other information, such as names and addresses too. In our examples, we are storing a name (User 0001, User 0002 etc) and email address (user0001@josefsson.org, user0002@josefsson.org etc). However, in practice these addresses are usually longer (complete X.500 addresses) and addresses exceeding 200 characters are known to exist. In practice, certificates also include pointers to CRL distribution points and a Certificate Policy. In our size comparison, we include a commercially available certificate. A detailed printout of the contents of these certificates can be found in Appendix B.
Table 4.4 is of special interest to our study. It shows that all common certificates are larger than the IPv4 UDP packet limit. This indicates that applications using DNS to look up certificates should instruct their DNS libraries to immediately use TCP, instead of letting it first try UDP and then fall back to TCP.
Table 4.4 also show that all common certificates are smaller than the corresponding IPv6 UDP packet limit. This is fortunate, and make the argument for using DNS to look up certificates stronger. This is especially true in mobile application, where two factors work together. The first factor is that bandwidth and latency savings are noticeable, and a small number of round trips is often a design requirement. The second factor is that IPv6 is likely to gain faster acceptance in mobile applications than in traditional networks. This is partly because of addressing issues, IPv6 make it possible to assign an Internet address to practically all electronic devices.
The previous discussion does not apply to LDAP. LDAP is ``designed to run over connection-oriented, reliable transports'' [96, paragraph 5.2] such as TCP. However, there exists a datagram version of LDAP as work in progress [41] that uses UDP. However, this is experimental and also does not support authentication. We were unable to find a open implemention of it.
Comparing the two protocols in a real-world situation, we used the ``RSA 1024 bit'' certificate. We stored the certificate in both DNS and LDAP directories. We fetched the certificate from the directories using a simple client. We measured the amount of data each of the protocols, DNS and LDAP, required to transfer the certificate. All tests were carried out using IPv4.
We did not measure the amount of overhead added by physical
layers, the IP layer, nor the UDP/TCP layer. This overhead does not
vary depending on the size of data packets, thus the size of
overhead from these layers is merely a function of number of round
trips, refer to section 4.4.4 where we study this aspect.
Table 4.5 illustrate header sizes of involved layers.
|
Both DNS and LDAP are open and widely implemented protocols. There are no differences in network characteristics depending purely on the implementation. This means we are actually benchmarking the protocols, and not the implementations. For reference, however, we note that the applications used were BIND [8] and Open LDAP [79].
Our results are listed in table 4.6. ``DNS over UDP/TCP'' depicts the case were DNS first tries UDP and falls back to TCP. For comparison, it also includes the ``raw'' certificate size. These values were collected using Ethereal [24]. The raw data is available electronically [52].
Figure 4.11 illustrate table 4.6 and summarizes this section's results. LDAP uses almost twice as much overhead as DNS.
The previous sections discuss facts and figures related to network bandwidth utilization and network latency, but in reality there are many factors combined that affect performance. This section makes a simple measurement of number of queries per second one can expect with common server implementations. Measurements on actual implementations must be considered carefully before anything can be said about the technology they implement, though.
The tests consisted of running a simple benchmark tool, developed for this purpose, that queries a server for a certificate and retrieves the certificate. The tool asks 5000 queries. The tool itself was run three times (with similar results) to assure that no external factors influenced the results. Since our LDAP implementation only runs on TCP, we are only comparing it to DNS over TCP. The source code of the benchmark tool used can be found in Appendix C.
Figure 4.12 illustrates table 4.7 and summarizes this section's result. The discrepancy between DNS and LDAP performance is quite large, to DNS's advantage. Some of it can be explained by our previous discussions on packet sizes, and especially round trips. A protocol using more than one round trip requires servers to somehow remember states in the protocol, which results in more complex software. But the large discrepancy cannot be explained by this alone. Rather, the reason has much to do with the design of, and expected use of, the protocols. The LDAP protocol was not designed for small, fast, simple queries but rather for sessions were programs (or users) may ask many questions, or search among answers interactively. Hence not much effort has gone into optimizing existing LDAP server software for the former case. DNS on the other hand has been designed with efficiency of implementations in mind, and this shows.
|
![\includegraphics[scale=0.5]{x500name}](img21.gif)
![\includegraphics[scale=0.35]{updatecert}](img22.gif)
![\includegraphics[width=\textwidth]{dns}](img23.gif)
![\includegraphics[width=\textwidth]{ldap}](img24.gif)
![\includegraphics[scale=0.3]{roundtrip}](img25.gif)
![\includegraphics[scale=0.25]{roundtriptcp1}](img26.gif)
![\includegraphics[scale=0.25]{roundtriptcp2}](img27.gif)
![\includegraphics[width=0.5\textwidth]{roundtripdns}](img28.gif)
![\includegraphics[width=0.4\textwidth]{roundtripdnsudptcp}](img29.gif)
![\includegraphics[width=0.4\textwidth]{roundtripldap}](img30.gif)
15![\includegraphics[]{certsize}](img32.gif)
![\includegraphics[]{cputime}](img33.gif)