next up previous contents index
Next: 6 Conclusions Up: Network Application Security Using Previous: 4 LDAP and DNS   Contents   Index


5 DNS Security Considerations

This chapter is about protecting your Certificate Directory, which is assumed here to be a public directory, from privacy abuses. We first need to discuss this concept on an abstract level. How can public information be of privacy concern? On the surface, this might look like a contradiction. This introduction borrows some ideas from ``The Ethics of Information: Protecting Privacy in the Computer Age'' [36].

The concepts of private information and public information are key to this discussion. The traditional notation of privacy is that of protecting private information. Here, we will try to argue that, in the light of computer technology, the notation of privacy needs to be reconsidered.

Information about a person such as name, address, telephone number, employment, passport photo, etc are by the strictest sense of the definition public. These seemingly unrelated pieces of information, taken together, present a privacy concern to most people. Traditionally the ``taken together'' part means costly intelligence work. It would cost a lot of time and money. Traditionally, you are safe. But with public databases and high-speed connections, it is easy to collect information about a vast number of people at the same time and process it locally. All such databases with ``public'' information are a privacy concern.

Today we thus have to replace the ``time and money'' factor that secured privacy in older times, with a new factor that makes ``data mining'' infeasible.

Now, if we return to our application, we have a certificate directory. Certificates often carry additional information, used to authenticate the certificate holder for certain purposes. Examples of additional information are qualification, licenses (attorney, doctor, ...), official approvals (vehicle driving licenses, ...). One can imagine a credit card vendor using certificates containing users credit card numbers. This information presents the privacy concern.

Secure DNS [20] contains a serious problem in this regard, when used as a Certificate Directory. This chapter presents this problem in detail, and a new idea to solve this problem.

5.1 Secure DNS

Secure DNS is a recent development in the DNS field. It is currently in testing for deployment by various organizations [67] [76]. The following three distinct services are the goal of Secure DNS [20]:

Outside the goals of Secure DNS, and hence not implemented, are means for confidentiality of queries or responses (e.g., information is considered to be public), and protection against denial of service attacks.

5.1.1 Data Non-existence

This section gives an abstract description of how Secure DNS achieves strong data non-existence. Again, ``data non-existence'' is how clients (securely) trust that a certain domain, say, does not exist.

We illustrate this by presenting a scenario, a naive first attempt at a solution to this scenario, and then discuss some problem with that solution. We proceed to describe the currently implemented solution, NXT records [20, section 5], that overcomes these problems. Since we have found further problems with this solution, we describe these problems. We conclude by presenting our own solution, that overcomes these new problems [50].

Scenario: Consider a set of keys[*]that uniquely identify a domain name (e.g., from an alphabet (strings of alphabetic characters, ``a''-''z''[*]) that each is attached to one or more data item(s) (e.g., certificates). Client entities (DNS resolvers) can send queries to server entities (DNS servers) for a key, expecting the corresponding data back. The data is cryptographically signed to provide authentication of data origin. However, if a certain key does not have any attached data, a message need to be returned with that information. The problem of data non-existence is to strongly authenticate this last piece of information.

The naive implementation, illustrated in figure 5.1, is for a client A to query a server B and expect a cryptographically signed answer back. To prevent replay-attacks to occur after new names have been introduced, the signature should have limited life length.

Figure 5.1: Naive data non-existence implementation

First we convince ourself that the naive implementation does indeed work. It does, since we have:

Three major limitations that this naive implementation faces, and that Secure DNS had to overcome, are the following:

These problems are easily translated into requirements for a better solution:

We first mention that a naive approach of signing all possible keys is not feasible, since this is practically a infinite set. We are now going to study the currently implemented solution, NXT records, but first we need som data to work with. Consider table 5.1.

Table 5.1: Example of (partial) DNS information for a zone
Key Data [Kalle Josefsson's Certificate] [Simon Josefsson's Certificate] [Lotta Josefsson's Certificate]

By introducing a canonical ordering[*] of keys, we can enumerate all keys that have data attached to them. By ordering keys we can construct links between each key in the sorting order. This piece of information can be signed and used as a ``data non-existence proof'' (discussion below). To illustrate this, consider table 5.2 where some new keys and data are added to our previous table.

Table 5.2: Example of non-existence proof data for data in table 5.1
Key Data [Kalle Josefsson's Certificate] Next key: [Lotta Josefsson's Certificate] Next key: [Simon Josefsson's Certificate] Next key:

We now describe how this new information is used in a clever way to achieve a ``non-existence proof''. Entity A queries for a non-existent key The server replies with a tuple, (, Next key: simon.josefsson.
. This is illustrated in figure 5.2. The ``next'' tuple is cryptographically signed, to provide authentication of data non-existence. These ``Next'' tuples can be calculated in advance, and be cryptographically signed off line. Thus it fulfills our two earlier requirements.

Now, how does the entity A know that does not exist? By using the canonical ordering process, it knows that sort later than and earlier than Since these ``next'' records were created using all existing keys, the entity A now can be certain that indeed do not exist. (Of course, assuming that the cryptographic signature was correctly verified.)

5.1.2 NXT Chaining

This form of non-existence proof raises an immediate problem. From the previous paragraph, the entity A that queried for learned more than that it does not exist. Explicitly, it learned that both and do exist. Continuing by asking for a domain that sorts earlier than, it is easy to see how this can be abused to learn the entire content of the entire data set.

Figure 5.2: ``NXT'' Data-nonexistence implementation

Observation 3   Secure DNS's non-existence proofs ``NXT'' can be used to collect all data in a DNS zone. We call this ``NXT chaining''.

Besides privacy concerns, gaining knowledge of a victim's DNS information opens up more direct forms of attacks [6]. In short, the knowledge of a certain organization's DNS information provides clues that help an intruder. Although most of the dangers in the scenarios described in the document have become obsolete (like allowing zone transfers), NXT chaining in Secure DNS re-introduces one of the concerns.

An alternative that reduces information revealed by non-existence responses is needed. The next section presents our idea.

5.2 Data Non-existence with Minimum Disclosure

The idea is to replace the sensitive information of NXT records of figure 5.2 with something that serves the same purpose, but cannot be used to discover names of other keys in the data collection. This is illustrated in figure 5.2.

Figure 5.3: Minimum information disclosure and data non-existence

Obviously the function ``f'' of figure 5.2 should not be possible to invert, or the idea of replacing the original data is lost. We suggest using a well-known cryptographic hash function, SHA-1 [77]. We illustrate the corresponding DNS data in table 5.3.[*] We see encoded SHA-1 values as valid keys, thus re-using the same canonical ordering process of Secure DNS.

Table 5.3: Example of non-existence proof data for data in table 5.1
Key Data [Kalle Josefsson's Certificate] Next key: [Lotta Josefsson's Certificate] Next key: [Simon Josefsson's Certificate] Next key:

We first verify that this solution still works. We do this by describing how a client builds trust that its query for does not exist. Assume this key hashes to 142. As illustrated in figure 5.4, the server can respond to the query with a tuple (, Next key: A client now makes sure a hash calculation of its query hashes to a value between the two returned hash values. If this is the case, it can be certain that the query did not ave any corresponding data. (Of course, it must also verify the corresponding cryptographic signature.)

Figure 5.4: Final example of how minimum information disclosure and data non-existence would work using NO records

We return to our problem with NXT records, that a client learns additional information from the non-existence proof. This is now replaced by only learning the hash value of two existing keys in the data collection. This can be abused to chain through hash values of all existing names in the zone. Assuming the hash function is not invertible, this is not a problem. However, it is possible to use this to determine the number of names in the zone[*].

5.3 Implementing the Idea in DNS

The previous idea has been described in a standards document [50, work in progress]. It introduces two further technicalities that are of interest here:

Besides mentioning these, going more into the details of the technical description is outside the scope of this chapter. The technical document, with a complete description, can be found in Appendix A.


Do not confuse this with cryptographic keys. In this chapter, we will explicitly mention ``cryptographic key'' when we talk about them.
... ``a''-''z''[*]
DNS today is US and ASCII centric. Work on supporting internationalized domain names is under way
... ordering[*]
The canonical ordering used in Secure DNS are simple byte-by-byte comparison of the ASCII encoding of strings. See [20, Section 8].
For brevity, the table uses small values. In practice, the values would have been an encoded form of a 160 bit SHA-1 value.
... zone[*]
Good estimates on the number of names in a zone can be calculated using only a few non-existence proofs though (assuming hash values are equally distributed.) A rough estimate can be done using only one non-existence proof, assuming a Poisson distribution.

next up previous contents index
Next: 6 Conclusions Up: Network Application Security Using Previous: 4 LDAP and DNS   Contents   Index