next up previous contents index
Next: 5 DNS Security Considerations Up: Network Application Security Using Previous: 3 Use Cases   Contents   Index


4 LDAP and DNS as Certificate Directories

This chapter extensively compare the model and implementation of the LDAP and the DNS, for use as a certificate directory.

4.1 Why Focus on LDAP and DNS?

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

4.1.1 How the Certificates are Used

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.

4.1.2 How the Directory is Used

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

Conclusion 1   The primary use of the directory services we study is fetching one certificate at a time. The queries consist of a complete email address, a domain name, a URL etc, rather than more complex queries.

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.

4.2 Locating Certificates

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, how would you get the keying material (his certificate)? If you want to establish a secure IP connection to 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:

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.

4.2.1 Certificate Naming

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

Figure 4.1: Example X.500 Directory

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 (, domain names (, email addresses (, 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 is not used to locate a certificate for sending mail to, how do I find out what should be used for locating the certificate?

4.2.2 Lightweight Directory Access Protocol

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

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.

4.2.3 Domain Name System

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.

Both issues stem from DNS being a less complex protocol than LDAP. Internal DNS and PKI hosting

We should mention two specialized uses of DNS as a certificate directory.

4.3 Updating Certificates in a Directory

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.

Figure 4.2: Update Certificate

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.

4.3.1 Updating in LDAP

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.

4.3.2 Updating in DNS

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:

4.3.3 Conclusions

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.

Table 4.1: Update operations supported in DNS and LDAP
Add Yes Yes
Delete Yes Yes
Modify Yes Yes
Rename No Yes

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].)

Table 4.2: Authentication support in DNS and LDAP
Kerberos Yes, GSSAPI Yes, SASL
CRAM/HMAC-MD5 Yes, native Yes, SASL
RSA SecurID No Yes, SASL

4.4 Performance and Overhead

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.

4.4.1 Caching in DNS and How it Affects Certificate Lookup

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.

4.4.2 The Domain Name System Protocol

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.

Figure 4.3: DNS envelope

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

4.4.3 The Lightweight Directory Access Protocol

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.

Figure 4.4: LDAP packet, with some structures expanded

4.4.4 Round Trips

A ``round trip'' denotes the time spent between sending one packet from an entity A (``client'') to an entity B (``server'') and back to the entity A. This is illustrated in figure 4.5.

Figure 4.5: Round Trip between two entities

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.

Figure 4.6: Setting up a TCP connection
Figure 4.7: Tearing down a TCP connection
\includegraphics[scale=0.25]{roundtriptcp2} Round Trips in a DNS query

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.

Figure 4.8: Round trips in a DNS Query over UDP

Figure 4.9: Round Trips in a DNS Query

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. Round Trips in a LDAP query

Figure 4.10: Round trips in a LDAP Query

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

Practical experimentation, using the network packet sniffer Ethereal [24], confirms our theoretical discussion. We summarize this sections' results in table 4.3.

Table 4.3: Number of round trips for a query using DNS and LDAP
Protocol and Number of Round trips on Round trips on
Transport mechanism packets Application level Transport level
DNS on UDP 2 1 1
DNS on UDP+TCP 12 2 5
DNS on TCP 10 1 4
LDAP on TCP $ \ge$ 15 3 5

4.4.5 Packet Size

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 (, 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: Typical certificate sizes
RSA 512 bit 519 bytes
RSA 1024 bit 587 bytes
VeriSign RSA 1024 bit 1160 bytes

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.

Observation 1   Use of UDP is not sufficient when looking up certificates in DNS in an IPv4 environment. Applications should use 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.

Observation 2   Use of UDP is sufficient when looking up certificates in DNS in an IPv6 environment.

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. Packet size of DNS and LDAP queries

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.

Table 4.5: Overhead of various layers
Ethernet header 14 bytes
IP header  20 bytes
UDP header 8 bytes
TCP header  32 bytes

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

Table 4.6: Bytes required to transfer a certificate that contains a 1024 bit RSA key with DNS and LDAP
  Data from Data from Total
  client server data
Certificate (data) - - 587
DNS over TCP 37 691 728
DNS over UDP/TCP 74 728 802
LDAP over TCP 80 772 852 Conclusions

Figure 4.11 illustrate table 4.6 and summarizes this section's results. LDAP uses almost twice as much overhead as DNS.

Figure 4.11: Bytes required to transfer a certificate with a 1024 bit RSA key with DNS and LDAP

4.4.6 Computer Resource Utilization

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

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.

Table 4.7: Queries per second to look up a certificate
  Implementation per second
DNS BIND version 9.0.0 485
LDAP OpenLDAP version 1.2.9 33

Figure 4.12: Queries per second to look up a certificate


... certificate[*]
Other kinds of PKIs that are not identity based exists. SDSI and SPKI are efforts for creating ``credential based'' public key infrastructures.
... packets[*]
Assuming no fragmentation occurs because of oversized packets.

next up previous contents index
Next: 5 DNS Security Considerations Up: Network Application Security Using Previous: 3 Use Cases   Contents   Index