INET Conferences




Other Conferences

[INET'98] [ Up ][Prev][Next]

A Novel Use of Distributed Directory Service

Information Sciences Institute


The inability of the existing tools to provide a consistent view of the public Internet to its constituents is beginning to hamper its growth. Currently there is a disconnection between Internet address delegations to service providers and the announcement of address delegations by those service providers to each other. In conjunction with this disconnect is the centralized nature of these registries. In the increasingly distributed Internet, it is harder and harder to reach through the maze and access these services in real time.

We think it is desirable to have a migration strategy that will provide a "chain of custody" from delegation to announcement that can be authenticated and will allow local sites to collect and cache the data they need to maintain a "world view" that, while not authoritative, is generally consistent and useful.

To build the system, we used DNS security to provide the authentication and chain of custody components and then added RPSL/RIDE syntax statements to the DNS zones so that each site may build a local copy of a routing registry. Since each site has one or more delegations and maintains the zone data locally, they can ensure that the authoritative routing data is also kept and maintained locally.

We then describe how this system was implemented and tested in the 6bone with the 6bone participants and we look to ways in which this system might be deployed in the IPv4 world.


Problem statement

A significant hurdle in the growth of the Internet is the lack of methods, tools, and techniques needed by operational staff as they attempt to determine the authenticity of information presented by their peers in normal exchange of routing information. There are two aspects of this problem. One, which we will not go into here, is that the current suite of routing protocols has a single trust level for all transactions. There are efforts underway which intend to add authentication tokens as part of the routing exchange. At present (circa January 1998) these approaches presume either the existence of one or more Internet-wide certification authorities that can validate these authentication tokens or one more round of bilateral agreements, where each site maintains its own certification process. The second, which will be the focus of this monograph, is the description of an out-of-band, non-real-time method of providing assurances of authentication of prefix delegation and prefix/as mapping. This method is based on yet another exploitation of the only existent operational Internet-wide distributed directory system, the DNS.

Current state of the art

The existing routing registry function is based on a design created by the RIPE NCC. An initial assumption in the creation of the RIPE-81 specification was a single, centralized repository where everyone would report and record not only the delegation information but also the authorized contacts, ASN tagging, and prefix announcements. As the number of users of this tool grew, enhancements were and are being made. Others took on some of the enhancement work and the number of sites that are using the children of the RIPE-81 specification (RIPE-181, RPSL) is growing. One of the significant problems with this scale of deployment is that unlike the RIPE NCC, few if any of these new sites are also recognized as a regional Internet Registry or RIR, and so there was no easy method to authenticate either the ASN tags or prefix announcements that were entered into these new routing registries.

There have been attempts to try to develop synchronization techniques to replicate the data stored in these registries so that they would have some semblance of global knowledge. Some of the earliest techniques, which are still in use, involve periodic file transfers of batch data between sites. It has been pointed out that this injects a level of uncertainty in the integrity of the routing registry data, as it may be as much as 36 hours or so out-of-date with data in the live routing system. It is also true that when the data is centralized, as the existent model calls for, it can be much harder to reach that centralized registry in the event of network instability.

So what we have is a system where, for the most part, the registries that perform prefix and ASN delegations are completely disconnected from the registries that record routing preference. This places each Internet service provider in an environment where they individually must create reasonably elaborate procedures to authenticate the accuracy of the routing data provided by and through each of their peers. As the Internet grows, the complexity of these procedures increases.

The vision

We believe that it is necessary for the creation and deployment of methods and processes that will provide the following attributes: 1) a "chain of custody" path that will exist between the delegation hierarchy and the announcement hierarchy; and 2) better techniques and tools to support distribution of responsibility for delegations and their corresponding announcements.

To meet these goals, we have explored the idea of using the existing structure of the DNS, adding one new zone for recording infrastructure components and then leveraging existing work from the IETF RPS and DNS-SEC working groups. Evidence from this experiment indicates that it is a reasonable approach but it does have one serious drawback, which is the need for cooperation across the Internet between all participants and the acceptance by participants of the responsibility to train their downstream clients and users on the use of these techniques.

Using these techniques allows for incremental rollout, without the need for large-scale, top-down investment or flag-day operations. Entities that participate in the responsible use of the Internet's numbering plans are now genuinely authoritative for the delegation contact data and are also authoritative for any routing announcement information. If there is a need, sites may also collect data from other sites to create scoped global views from other participants in the global Internet. These collected views are nonauthoritative. Each site is responsible for maintaining the authoritative master for its delegation of responsibility.


The design exploits the address to name tree in the Domain Name System. For IPv4 this is represented in the domain. For IPv6 this is represented in the domain. These domains can be viewed as the root of the delegation hierarchy for IP addresses. It is possible to start at the root of the DNS and identify all the authoritative delegations. We note in passing that not all authoritative delegations are active or announced; however, we do have access to a mapping of the delegation hierarchy.

There have been a number of claims that these trees are unused and are mostly superfluous and few applications make use of the data present. It is not clear how useful applications such as FTP or HTTP are or how broadly they are used, but they are the principal applications which use these zones as a sanity check by mapping the results of the forward lookup with the results of the inverse lookup to see if the forward domain names match. In a series of zone audits over the last year, the accuracy of the data within the domain has been checked with numbers showing more than 57% of the delegations being managed accurately, and the percentage is increasing.

It is true that not all delegation points are managed by those to whom the delegations have been made and that this might become an issue if this idea gets broad-scale support.

However, given all the caveats on the weaknesses with these zones, they do form the delegation hierarchy of prefixes within the Internet and this hierarchy is distributed and is architecturally structured so that the site receiving a delegation becomes authoritative for the data within that delegation. It is nearly ideal as a starting point but requires the addition of one or two other features to be useful.

One item that is increasingly more important in today's Internet is the ability to authenticate information. With the addition of authentication tokens being added to the DNS, it is now possible to validate a prefix delegation from the root. The difficulty with this general idea is that given the DNS implementations in common use, there is lead time needed to propagate code that recognizes these new record types or tokens. In one online discussion, this response seemed to illuminate the problem of waiting for new RR support:

If an old version (4.9.4 or earlier?) of BIND attempts to zone-transfer a zone with T_AAAA records, it will pretty much silently fail. This means that your secondaries will silently stop working if they aren't running a recent version (which was more of a problem in the early days of the 6Bone). Not many people want to watch their production DNS silently fail, so separating the experimental stuff is commonly accepted as a good idea.

Note that any non-archaic version of BIND should be able to cache and recurse T_AAAA records happily; it's the zone transfers that are the problem. As caching/recursing nameservers, old versions of BIND abound and probably will continue to do so for many years to come. (Craig Metz)

The problem here is that it is hard to tell when to move your code base to support new features, but that topic is outside the purview of this paper.

With the addition of the hooks provided by the DNS-SEC working group to the inverse trees of the DNS, we now have the ability to authenticate delegations. We have our "chain of custody" that follows the delegation hierarchy. In and of itself, this pushes the DNS into a new realm. With the addition of support for storing and transmitting public keys and the ability to authenticate DNS transactions, the Internet will have available to it a truly public Certification Hierarchy. There will be the temptation to exploit this feature as a Certification Authority but it is unlikely to receive formal assurances as a public Certification Authority since it is decentralized. The temptation will be strong and so care should be given to explore the legal ramifications on the use of keys stored and moved through the DNS.

The use of zone signatures for tracking delegations has its own set of concerns. We have had to look again at the periodicity of change over the inverse tree in the DNS. Most people will recognize, if they think about it, that the changes that occur near the leaves of a DNS tree have a much higher frequency than changes that occur near the root. This fact has ramifications for authentication of zone contents by use of zone signatures. We expect that it is tractable to use zone level authentication at and near the root, while the closer we get to the leaves, the harder it will be to have verifiable signatures. To do so would require features within the DNS that we touched on in the paragraph above as well as other components that are outside the scope of this paper. For our purposes, we will only use the zone authentication features, leaving the topic of the DNS as a public certification authority to other venues.

The next step is to add routing policy information. This data applies to both prefixes, which are already mapped into the DNS, and to Autonomous System Numbers, which are tags used to identify administrative span of control. We'll look first at ASNs.

Current routing protocols use them to define and apply routing policies. The DNS design did not comprehend ASNs. At the time, ASN usage was a crude method of "tagging" prefixes to be announced to your peers via the EGP (RFC 827). There were few enough peers and simple enough policies that there was no perceived need to track ASN usage within something like the DNS. In recent years, it was recognized that it would be useful to have a way to track aspects of routing domain identifiers and so the zone rdi int was created, initially to record routing domain identifiers for the IDRP routing protocol. It is in this zone that we record the mapping of ASN to administrative contact.

At this point we have the address or prefix delegation hierarchy in place, a zone to track ASN usage, and the methods for authentication at each step. For a functional system, we need to add descriptions of routing policy. The method we have experimented with is to utilize the record structure as defined in the routing policy specification language (RPSL) and encapsulate them inside DNS TXT records. The format is opaque, since we have built a specific structure inside the TXT RR so that a better and more robust approach can be taken if this proves viable. We selected the encapsulated TXT method since virtually all existent DNS code understands TXT records. We would prefer to have defined a new RR type, RPS, but will pursue that activity on a different timetable since new RR type support tends to track the deployment of new DNS code and that takes significant time to gain critical penetration rates.

With this opaque structure we have shown that it is possible to express policies on both an ASN and on a per prefix basis.

With this component in place it becomes possible to discriminate between authoritative and proxy delegations and announcements. There then exists a "chain of custody" between delegation and routing policy that can be independently verified by ISPs. And each delegation point maintains the authoritative data for its delegations and preferred routing policy locally.

Implementation review

The implementation occurs in two parts. The simplest part is the integration of routing information within the DNS so we look at that aspect first. The more complex part is the activation of DNS Security features as authentication tokens and we'll cover that last.

To test our theory, we began creating the needed components for adding routing services. To begin, we had delegated the RDI.INT zone to real servers and began populating the zone with test data. An example, shown below, is the first attempt to build out the data in this zone into something that could be meaningful:

Script started on Mon Jan 26 10:23:10 1998
26% dig axfr
; <<>> DiG 2.0 <<>> axfr   129600  SOA (
1925630 ;serial
10800   ;refresh
900     ;retry
604800  ;expire
129600 )        ;minim   129600  NS   129600  NS   129600  TXT     RPS 0000 person:Bill Manning   129600  TXT     RPS 0001 descr: LosAngelesPeering exchange   129600  TXT     RPS 0002 aut-num: AS4555   129600  TXT     RPS 0003 as-in: from AS226 100 AS226   129600  TXT     RPS 0004 as-in: from AS226 110 AS4554   129600  TXT     RPS 0005 interas-in: fron AS226 (pref=3) AS4554   129600  TXT     RPS 0007 admin-c: WM110-NSI   129600  TXT     RPS 0008 tech-c: WM110-NSI   129600  TXT     RPS 0009 remarks: The first live example of this technique   129600  TXT     RPS 0010 remarks: Check the SOA for mnt-by, changed data   129600  TXT     RPS 0011 source: DNS   129600  TXT     RPS 0012 route:   129600  TXT     RPS 0013 route: 3ffe:08/24
;  Matching SOA found
;; WHEN: Mon Jan 26 10:23:33 1998

Most of the historical ASN delegations may be found within the RDI.INT zone now as we populated it with the existing data from the Network Solutions database. Longer term there would need to be means negotiated with the existing regional IRs to ensure that their ASN delegations are properly encoded in this zone. This takes care of one side of the ASN to prefix mapping. The other side of the mapping occurs in the inverse tree of the DNS. An example is listed below:

26% dig axfr
; <<>> DiG 2.0 <<>> axfr  86400   SOA (
1928529 ;serial
10800   ;refresh
900     ;retry
604800  ;expire
86400 ) ;minim  86400   NS  86400   NS      NS.ISI.EDU.  86400   TXT     RPS 0000 descr: Application Testbed network  86400   TXT     RPS 0001 origin: 4555  86400   TXT     RPS 0002 notify:  86400   TXT     RPS 0003 address: PO 12317, MDR, CA. 90295  86400   TXT     RPS 0004 nic-hdl: WM110-NSI       86400   PTR       86400   PTR        86400   PTR
;  Matching SOA found
;; WHEN: Mon Jan 26 10:31:31 1998

or, more appropriately, for our testing, an IPv6 prefix:

79% dig axfr
; <<>> DiG 8.1 <<>> axfr
; (1 server found)
@                       1d12h IN SOA (
1925873         ; serial
3H              ; refresh
15M             ; retry
1W              ; expiry
1d12h )         ; minimum
1d12h IN NS
1d12h IN NS
1d12h IN TXT    "RPS 0000 descr: Application Testbed network"
1d12h IN TXT    "RPS 0001 origin: 4555"
1d12h IN TXT    "RPS 0002 notify:"
1d12h IN TXT    "RPS 0003 address: PO 12317, MDR, CA. 90295"
1d12h IN TXT    "RPS 0004 nic-hdl: WM110-NSI"
10                      1d12h IN NS
1d12h IN NS
0.0                     1d12h IN NS     NS.ISI.EDU.
1d12h IN NS
1.0                     1d12h IN NS
@                       1d12h IN SOA (
1925873         ; serial
3H              ; refresh
15M             ; retry
1W              ; expiry
1d12h )         ; minimum
;; Received 14 answers (14 records).
;; WHEN: Mon Jan 26 14:46:52 1998

These zones now have coded in them the basic data used by the RA projects routing policy toolset to build router configurations. It is fairly easy to extract the zone data, as has been done above using the DNS tool DiG, if your servers do not already carry the zone as a caching server or a real master or slave. If one or more of the machines are acting in the capacity of master or slave, then you already have access to the data.

The process that we took was the following:

  • Check our Peers for their ASN data both real-time and in the DNS
  • Pull ASN policy and then poll for specific prefix policy
  • Run the resulting RPSL/RIDE format policy statements through the RAToolSet to build cisco config statements.

This process is functionally identical to the same steps used by the Routing Arbiter project except that the input data is not stored in a remote repository but is collected from authoritative sources and processed locally.

This second part of the vision is easily deployable and may be done by any of those who are delegated address prefixes and/or ASNs.

The more difficult task is developing the "chain of custody" and the deployment of the features in DNS-Security to provide the authentication tokens needed to instantiate the "chain of custody." Our experiments were hampered by the same issues noted earlier in that there are new DNS resource records required for DNS Security deployment -- to wit, the KEY, NXT, and SIG types are all used.

Testing was also hampered by the lack of supported code and stable specifications. During the course of testing, the specifications for how authentication and validation were to be done changed three times from inception to the time of this writing. It is expected that further changes may occur as we gain more experience. It is also true that the initial code base was the proof of concept code released by Trusted Information Systems as initially announced at the Munich IETF. We continue to work with this code because although the Internet Software Consortium has announced that they will have a supported release with DNS Security features available, no such code has been forthcoming as of this writing. And so, given the fluid nature of the specifications and the code, it is very difficult to persuade other operators to run servers with our modifications, except on an experimental basis. Until there is better support for these new RR types within a broader code base, our ability to create authentication chains is very limited. Nonetheless, we were able to demonstrate proof of concept within a restricted scope.

To utilize DNS Security features, we need to understand how the various tokens are used and how they interact. Given the fluid nature of the NXT and SIG records, we will only examine how to use the KEY resource record. The KEY record is used to "sign" or stamp a zone with a "signature" that is created with cryptographic techniques that attempt to ensure that the contents of the zone are known to be authentic by the person who generates the signature over the zone contents. As this is exactly what we are looking for, that is all we need to proceed.

Since many people are unable to do cryptographic computations in their heads, TIS has created a wonderful tool that provides some level of automation in the creation of KEY records on a per-zone basis. They call this tool zone_sign, and as of this writing, it is available from the TIS ftp site. Here is their description of what zone_sign does:


This executable is the primary executable. It reads in a zone master data file, following all $INCLUDE directives, and outputs the signed data and sometimes other files. The other files represent data designated as being signed by something other than the zone.

For example,

For a zone file that looks like:

$ORIGIN something.
$SIGNER something. <foot print>
@ SOA name name # # # # #
NS name 
KEY key stuff 
a A address 
b A address 

and is in a file named "zone.something.", zone_sign will produce a file named "zone.something..signed" The dots are significant. This unseemly file naming convention comes in handy when things get more complicated.

For a zone file that looks like the following, with the keys for a and b not available:

$ORIGIN something.
$SIGNER something. <foot print>
@ SOA name name # # # # #
NS name 
KEY key stuff 
a KEY key stuff 
$SIGNER a.something. 
A address 
$SIGNER something. 
b KEY key stuff 
$SIGNER b.something. 
A address 
c A address 

and with the same name as the previous, zone_sign will produce the following:


Along the way to producing these files, zone_sign performs the following steps:

1) Handles all input directives, $SIGNER, $INCLUDE, $ORIGIN and isliberal in the handling of parenthesis and escaped binary sequences in the input stream. Note that at times, the allowable syntax for zone_sign differs from BIND, zone_sign allows superset of acceptable records. (Not guaranteed to be a true superset.)

In zone_sign, I tried to adhere more strictly to the RFCs than has been done in BIND.

2) Does preliminary input error checking, looking for malformed records and records it does not understand. Errors are reported to standard output.

3) Sorts all records into the order specified in RFC 2065.

4) Examines records set by set for some semantic errors (such as missing CNAMES with others). Records are separated into files by their designated signer.

5) Records that are to be signed by the zone key are signed. All records in the zone are processed to produce the NXT records. In addition, all keys that are available to the zone_sign are used.

6) zone_sign completes giving some measured data on the run, such as time, what happened to the records, and reports memory leaked. (For details on how signatures are generated, and how the signer is designated, refer to RFC 2065 and/or carefully read the source.)

What this means in practice is that we need to modify the zone file to add the following new directive, the $SIGNER directive. The zone file starts out like this:

% more 
$ORIGIN int. 
$SIGNER 19769 
ip6 IN SOA ( 
1925623 10800 900 604800 129600 ) 
e IN NS 

What we will not discuss here in detail is the format of $SIGNER directive even though it is pretty simple. The format is the name of the zone and a "footprint" or cryptographic key that is associated with the zone and the person signing it. Generation of the "footprint" may be done with another program from TIS or may be done via other means. In any case we take the zone, modified with the $SIGNER directive, and then we then run through zone_sign, which generates a signature for the zone.

%zone_sign -f -z 
Starting at Mon, 02/02/98 01:01:47 PM 
zone_sign -f -z 
Warning: appending a '.' to zone '' 
Warning: Assuming a default signer for zone 
Running zone_sign with following settings: 
Initial input file : 
Initial zone suffix : 
Initial signer : 
Resulting files in : . 
Sorting mechanism : In memory tree 
Tracing directives : none 
Interim results file: ./ 
(will be removed by this process before ending) 
All RR's are to be resigned (all SIG RR's discarded). 
All new signatures will expire Mon, 03/02/1998 01:01:47 PM.
All names (wildcard covered and not) are in NXT chain 
The following files are created ONLY if necessary. 
Unsigned record file: ./ 
Signed record file : ./ 
Note: Records signed by other signers (whose keys 
are not available) will be placed in files 
$INCLUDEd in the signed records file. 
Input lines breakdown: 15 in file(s), 1 continuation, 4 directive,
0 invalid or discarded, 0 blank or comment 
Total records accepted for sorting: 10 
Input lines unaccounted: 0 (should be 0) 
Beginning to sort at Mon, 02/02/98 01:01:47 PM 
Key decryption Password: 
Found key for, footprint 19769 
dst_read_public_key(): Public Key not found
Could not find key for, footprint 0 
Beginning to sign at Mon, 02/02/98 01:20:25 PM 
Finished signing at Mon, 02/02/98 01:20:29 PM 
Total records processed: 10 
Total signatures generated: 7 in 4 seconds 
Average 1.75 signatures per second 
Total signatures verified: 0 successful: 0 
Average 0.00 verifications per second 
Output lines breakdown: 25 in file(s), 15 generated, 0 recalculated,
0 duplicates found 
Missing lines 0 (should be 0) 
Ending at Mon, 02/02/98 01:20:29 PM 

And the output of the run looks like this.

% more 
$SIGNER 19769 SOA 886453307 10800 900 604800 129600 SIG SOA 1 129600 19980302210147 19980202212025 19769 Uv70yA0c9c9eGbBSTAktCBh94xE20ZKBmOIfhsQi1dqKyS5mTfcaQYUrMKwoKXLfEMm/xr5qt9hVxVELLVwsVQ NS NS NS SIG NS 1 129600 19980302210147 19980202212025 19769 OqT2wMmnUdnccVtNb3ml58GHoasnCi9KDURfHgJJc2VixUtXUSfCSVWS7gzKa69KCKN9e3ISvyH/BN3rKuJDlA NXT NS SOA SIG KEY NXT SIG NXT 1 129600 19980302210147 19980202212025 19769 gqgjVACuGJBpvsraMZmzITaOK4B6a7TYZvbesRG2EDTA+1mJ7oRQsmBSR4YWJdYY9KTl0btcKyD9VV8paBkKQw NS NS SIG NS 1 129600 19980302210147 19980202212025 19769 fac9MHeWkMpJRywGHpkYVkXxTpIg/jumgPD4mXeoD1fs/Ohr5D8u1uxsX2M8Y41pZmzRLVau49O7sIhqyJe08w NXT NS SIG NXT SIG NXT 1 129600 19980302210147 19980202212025 19769 gP/wq/qIpBEq4Wm9XsRP9lsyVFgEkn5FwkU5DCf3U0Le399vbPOz3//v8mv4nJtMZSIbFxrOfDO8wgfYRz3BXA NS NS.ISI.EDU. NS NS SIG NS 1 129600 19980302210147 19980202212025 19769 cUt9dX+VJGDtSz6DIWQZi6bAwM1RwHaQVP3U+rrGnJmc9cZTeh06ST0O12BlRYsmYCRjVrkP8++WHoupiKtT1A== NXT NS SIG NXT SIG NXT 1 129600 19980302210147 19980202212025 19769 YgDU1C4X4cfXH4U72fs2+Hod+7wpA9VP9N1Yo982BftIBjQ+BSFrvNisDgytnv9rqumLims0Y8oi49O2tRxkOw
; Zone minimum TTL is 129600 
; Expiration date is 19980302210147 KEY 257 255 1 AQOsEDhLAnKsPiz3Q5y091btFVchctNfs16XFULO02qNyKafPWErCitd62WNEKSxL7BSPzX2kkiMOZ92HR1dTTmz

Here we have the nascent ability to have authentication at each delegation point. Adding this feature to the processes described above, it will be possible to utilize these infrastructure zones to track not only authoritative delegations but also desired routing capabilities as well. There are still areas that need a lot of work.

Other areas of weakness:

  • The DNS currently lacks reasonable support for classless delegations. This will cause problems with small delegations. The current method in use is a documented hack. A cleaner approach would be to support bitwise delegations within the DNS. A recent proposal, called the DBIT proposal, is being circulated for comment. When such features are integrated into DNS, there will be one less objection to integration of the delegation and routing preference publication methods.
  • Use of TXT records as opaque envelopes will cause a migration problem with support tools when a new RR type is defined. It is hoped that an old proposal for supporting dynamic RR definitions will be integrated into the DNS in the near future.
  • Each ISP must act responsibly and actively maintain the data in the DNS. This is more a social statement. It is hoped that by reducing the number of databases that an ISP must keep up-to-date, the data will be more accurate.
  • It must be recognized that data placed in the DNS is for public consumption, at least in the global Internet. This is often a hard concept for entities coming on to the Internet to internalize. This too becomes a social issue.


The tools and facilities are available or will shortly be available to allow everyone who receives a delegation of IP space to authoritatively publish their desired routing policy as part of their DNS zones. No longer will there need to be a requirement for registering in one or more centralized routing registries.

To ensure the integrity of the data, it is becoming possible to generate cryptographic signatures on zone files, allowing independent authentication of the accuracy of a zone's contents, including authentication tokens and routing hints. Continued work on the remaining problem areas will lead to tools and techniques that will foster the continued explosive growth in the Internet by encouraging local control and administration of certain infrastructure components. We hope that our experiments may lead to a more productive and stable Internet.

[INET'98] [ Up ][Prev][Next]