5. Non-existent Names and Types

The SIG RR mechanism described in Section 4 above provides strong authentication of RRs that exist in a zone. But is it not clear above how to authenticatably deny the existence of a name in a zone or a type for an existent name.

The nonexistence of a name in a zone is indicated by the NXT ("next") RR for a name interval containing the nonexistent name. A NXT RR and its SIG are returned in the authority section, along with the error, if the server is security aware. The same is true for a non-existent type under an existing name. This is a change in the existing standard which contemplates only NS and SOA RRs in the authority section. NXT RRs will also be returned if an explicit query is made for the NXT type.

The existence of a complete set of NXT records in a zone means that any query for any name and any type to a security aware server serving the zone will always result in an reply containing at least one signed RR.

NXT RRs do not appear in zone master files since they can be derived from the rest of the zone.

5.1. The NXT Resource Record

The NXT resource record is used to securely indicate that RRs with an owner name in a certain name interval do not exist in a zone and to indicate what zone signed RR types are present for an existing name.

The owner name of the NXT RR is an existing name in the zone. It's RDATA is a "next" name and a type bit map. The presence of the NXT RR means that generally no name between its owner name and the name in its RDATA area exists and that no other zone signed types exist under its owner name. This implies a canonical ordering of all domain names in a zone.

The ordering is to sort labels as unsigned left justified octet strings where the absence of a octet sorts before a zero value octet and upper case letters are treated as lower case letters. Names are then sorted by sorting on the highest level label and then, within those names with the same highest level label by the next lower label, etc. down to leaf node labels. Since we are talking about a zone, the zone name itself always exists and all other names are the zone name with some prefix of lower level labels. Thus the zone name itself always sorts first.

There is a potential problem with the last NXT in a zone as it wants to have an owner name which is the last existing name in canonical order, which is easy, but it is not obvious what name to put in its RDATA to indicate the entire remainder of the name space. This is handled by treating the name space as circular and putting the zone name in the RDATA of the last NXT in a zone.

There are special considerations due to interaction with wildcards as explained below.

The NXT RRs for a zone SHOULD be automatically calculated and added to the zone by the same recommended off-line process that signs the zone (see Section 7.2). The NXT RR's TTL SHOULD not exceed the zone minimum TTL.

5.2. NXT RDATA Format

The RDATA for an NXT RR consists simply of a domain name followed by a bit map.

The type number for the NXT RR is 30.

                           1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |         next domain name                                      /
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    type bit map                               /
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The NXT RR type bit map is one bit per RR type present for the owner name similar to the WKS socket bit map. The first bit represents RR type zero (an illegal type which should not be present.) A one bit indicates that at least one RR of that type is present for the owner name. A zero indicates that no such RR is present. All bits not specified because they are beyond the end of the bit map are assumed to be zero. Note that bit 30, for NXT, will always be on so the minimum bit map length is actually four octets. The NXT bit map should be printed as a list of RR type mnemonics or decimal numbers similar to the WKS RR.

The domain name may be compressed with standard DNS name compression when being transmitted over the network. The size of the bit map can be inferred from the RDLENGTH and the length of the next domain name.

5.3. Example

Assume zone foo.tld has entries for

               big.foo.tld,
               medium.foo.tld.
               small.foo.tld.
               tiny.foo.tld.

Then a query to a security aware server for huge.foo.tld would produce an error reply with the authority section data including something like the following:

   big.foo.tld. NXT medium.foo.tld. A MX SIG NXT
   big.foo.tld. SIG NXT 1 3 ( ;type-cov=NXT, alg=1, labels=3
                    19960102030405 ;signature expiration
                    19951211100908 ;time signed
                    21435          ;key footprint
                    foo.tld.       ;signer
    MxFcby9k/yvedMfQgKzhH5er0Mu/vILz45IkskceFGgiWCn/GxHhai6VAuHAoNUz4YoU
    1tVfSCSqQYn6//11U6Nld80jEeC8aTrO+KKmCaY= ;signature (640 bits)
                          )

Note that this response implies that big.foo.tld is an existing name in the zone and thus has other RR types associated with it than NXT. However, only the NXT (and its SIG) RR appear in the response to this query for huge.foo.tld, which is a non-existent name.

5.4. Interaction of NXT RRs and Wildcard RRs

Since, in some sense, a wildcard RR causes all possible names in an interval to exist, there should not be an NXT RR that would cover any part of this interval. Thus if *.X.ZONE exists you would expect an NXT RR that ends at X.ZONE and one that starts with the last name covered by *.X.ZONE. However, this "last name covered" is something very ugly and long like \255\255\255....X.zone. So the NXT for the interval following is simply given the owner name *.X.ZONE and an RDATA of the next name after the wildcard. This "*" type owner name is not expanded when the NXT is returned as authority information in connection with a query for a non-existent name.

If there could be any wildcard RRs in a zone and thus wildcard NXTs, care must be taken in interpreting the results of explicit NXT retrievals as the owner name may be a wildcard expansion.

The existence of one or more wildcard RRs covering a name interval makes it possible for a malicious server to hide any more specifically named RRs in the internal. The server can just falsely return the wildcard match NXT instead of the more specifically named RRs. If there is a zone wide wildcard, there will be an NXT RR whose owner name is the wild card and whose RDATA is the zone name. In this case a server could conceal the existence of any more specific RRs in the zone. It would be possible to design a more strict NXT feature which would eliminate this possibility. But it would be more complex and might be so constraining as to make any dynamic update feature very difficult.

5.5. Blocking NXT Pseudo-Zone Transfers

In a secure zone, a resolver can query for the initial NXT associated with the zone name. Using the next domain name RDATA field from that RR, it can query for the next NXT RR. By repeating this, it can walk through all the NXTs in the zone. If there are no wildcards, it can use this technique to find all names in a zone. If it does type ANY queries, it can incrementally get all information in the zone and thus defeat attempts to administratively block zone transfers.

If there are any wildcards, this NXT walking technique will not find any more specific RR names in the part of the name space the wildcard covers. By doing explicit retrievals for wildcard names, a resolver could determine what intervals are covered by wildcards but still could not, with these techniques, find any names inside such intervals except by trying every name.

If it is desired to block NXT walking, the recommended method is to add a zone wide wildcard of the KEY type with the no-key type value and with no type (zone, entity, or user) bit on. This will cause there to be one zone covering NXT RR and leak no information about what real names exist in the zone. This protection from pseudo-zone transfers is bought at the expense of eliminating the data origin authentication of the non-existence of names that NXT RRs can provide. If an entire zone is covered by a wildcard, a malicious server can return an RR produced by matching the resulting wildcard NXT and can thus hide all the real data and delegations in the zone that have more specific names.

5.6. Special Considerations at Delegation Points

A name (other than root) which is the head of a zone also appears as the leaf in a superzone. If both are secure, there will always be two different NXT RRs with the same name. They can be distinguished by their signers and next domain name fields. Security aware servers should return the correct NXT automatically when required to authenticate the non-existence of a name and both NXTs, if available, on explicit query for type NXT.

Insecure servers will never automatically return an NXT and some implementations may only return the NXT from the subzone on explicit queries.