draft-ietf-dnsext-not-existing-rr-01.txt

bind-3.2.

   As the previous NO RR format describe, the "next domain name" of NXT
   records is replaced by its hash value. This removes the possibility
   of chaining both backwards and forwards through a zone.

   But without also modifying the owner names of NO records it is still
   not difficult to chain through a zone. Consider querying a server
   for (say) "m._no.example.org", the reply could contain a NO record
   for "g._no.example.org", now an adversary can lookup records for
   "g._no.example.org", and then issue a query for a domain that would
   sort (in "the canonical order" described in RFC 2535) just before
   "g._no.example.org". Applying the technique over and over again, all
   records in the zone can still be collected.

   To prevent this, the owner names of NO records is replaced by its


Josefsson                 Expires May 25, 2001                  [Page 6]

Internet-Draft               The NO Record                 November 2000


   hash value.  As DNS places limits on what characters can be used in
   owner names, the owner name uses a base 16 "hex" encoding [6].

   In order to remove the (very small) chance of generated NO record
   names colliding with existing, "real", domains, all NO records MUST
   be stored directly in the "_no" domain of the zone.  I.e., a zone
   "example.org." store its NO records as, say,
   "35a4d1._no.example.org.".

   This change in owner names also make sure that the delegation point
   concerns of NXT records does not occur in NO records.

3.5 Additional Complexity Due To Wildcards

   Proving that a non-existent name response is correct, or that a
   wildcard expansion response is correct, makes things a little more
   complex.

   In particular, when a non-existent name response is returned, an NO
   must be returned showing that the exact name did not exist and, in
   general, one or more additional NO need to be returned to also prove
   that there wasn't a wildcard whose expansion should have been
   returned. (There is no need to return multiple copies of the same
   NO.) These NOs, if any, are returned in the authority section of the
   response.

   Furthermore, if a wildcard expansion is returned in a response, in
   general one or more NOs needs to also be returned in the authority
   section to prove that no more specific name (including possibly more
   specific wildcards in the zone) existed on which the response should
   have been based.

3.6 No Considerations at Delegation Points

   When NXT records are used to deny existance, there exists a special
   case at delegation points.  Namely, that two distinct RRsets exist
   for the same owner name, one in the parent zone and one in the child
   zone.

   $ORIGIN parent.example.org.
   @       SOA
           NS
           NXT     child   SOA NS SIG NXT
   child   NS      foo
           NXT     next    NS SIG NXT
   next    A       127.0.0.2





Josefsson                 Expires May 25, 2001                  [Page 7]

Internet-Draft               The NO Record                 November 2000


   $ORIGIN child.parent.example.org.
   @       SOA
           NS
           NXT     name    SOA NS SIG NXT
   name    A       127.0.2.1
           NXT     child.parent.example.org.

   With NO records, the parent would deny existance of domains in
   "_no.parent.example" and the child in
   "_no.child.parent.example.org".  Thus no NO RRset collision occur.

3.7 Hash Truncation and Dynamic Updates

   Entities that create NO records MAY truncate the hash field.  It
   MUST NOT truncate hash fields so they are no longer unique
   throughout a zone.  Hash truncations MUST only be done to octet
   offsets.  Truncation MUST be such that less significant bits are
   truncated, i.e. higher-order bits are preserved (see the examples).

   Zones that are dynamically updated will have to calculate and add NO
   records on-the-fly.  If hash truncation is used, adding a new name
   to the zone will require updating (and signing) NO records for the
   conflicting name(s).

   Since truncation (and also "compression" described in the next
   section) make it impossible to predict the corresponding NO record
   given a domain name, resolvers should not ask for a hashed NO record
   (aaaa._no.example.org. IN NO) for a known domain name if they want
   to find out what types exist at the domain.  Instead, a resolver
   might ask for NO records on the original name (www.example.org. IN
   NO).  Such records will never exist, and the correct NO record will
   be returned by the server.

   To summarize, the behaviour of hash truncation should be
   configurable in the entity that creates NO records, to accomodate
   different usage-patterns.  If the zone is intended to be dynamicly
   updated, hash truncation may be considered not worth the extra
   on-the-fly processing required.













Josefsson                 Expires May 25, 2001                  [Page 8]

Internet-Draft               The NO Record                 November 2000


3.8 Reducing Number of Records

   Entitities that create NO records MAY deny existence for several
   records per NO record.  Entities that create NO records should take
   care so that each resulting NO record is not "too large".  [Comments
   on this?  Should there be a specific limit? It might be left as a
   DNS Operational consideration]

   Merging several NO records into one record also place more work on
   the resolver.  Instead of parsing two hash values for each NO record
   to determine if it's applicaple, a resolver will have to parse
   several hash values and compare each.

   The NO RR record consist of one or more RR type list / hash values,
   described above, and a resolver need to parse the entire record to
   collect each individual field.  I.e., a NO parse algorithm could
   looke like: read RRs, stop when you read a zero RR type, read hash
   length indicator, read hash size, if the entire record is read stop,
   otherwise read RRs, stop when you read a zero RR type, etc..

3.9 Hash Collisions

   Hash value collisions are expected not to occur.  For SHA-1, the
   probability that this should happen is 1 out of 2^80 on average.

   However, collisions are actually only a problem if the domain names
   producing the same hash value have different sets of existing types.

   Consider the following records

   ; SHA-1(one.example.org) = SHA-1(two.example.org)

   one.example.org.	IN A 1.2.3.4
   two.example.org.	IN A 5.6.7.8

   Given that no other RR types exist for neither domain, both
   "one.example.org" and "two.example.org" would be authenticated not
   to exist by the same NO record.

3.10 Authenticating Denial of NO Records

   NO records (together with SIG records) authenticate denial for other
   types in a zone.  Unlike NXT records that re-use the namespace in
   the zone, NO records are not intended to authenticate denial of
   other NO records.






Josefsson                 Expires May 25, 2001                  [Page 9]

Internet-Draft               The NO Record                 November 2000


3.11 Case Considerations

   Before calculating SHA-1 hash values, domain names MUST be converted
   into canonical format as described in RFC 2535. This is to make hash
   comparisons possible.

3.12 Presentation Format

   NO RRs do not appear in original unsigned zone master files since
   they should be derived from the zone as it is being signed.

   If a signed file with NO records is printed or NO records are
   printed by debugging code, they appear as a list of unsigned
   integers or RR mnemonics, and the hash value in base 16 hex
   representation [6] with "0x" prepended (to distinguish it from
   integer RR codes).  The zero RR that terminate the list of RR types,
   and the hash value length indicator, does not appear.

   See the next section for examples of printed NO RRs.

3.13 Examples

   This section contain examples of NO records, using the reserved
   domain exmaple.org [3].

3.13.1 Adding NO Records to a Zone

   Consider the following zone file.

   $ORIGIN example.org.
   @	IN SOA ...
   @	IN NS ns
   @	IN MX 0 server
   ns	IN A ...
   www	IN A ...
   sERVEr	IN A ...
   sERVEr	IN TXT "text"

   ; SHA1(example.org.)          = 0x222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1
   ; SHA1(ns.example.org.)       = 0x1b7838c69a66eb50cc215f66ee4554d0c4c940a5
   ; SHA1(www.example.org.)      = 0x839ebd4386c0b26d81f147421b5b7036e61438cf
   ; SHA1(server.example.org.)   = 0x906a0ad5e604b1905828499dc8672ecb8de73e2f

   Note that hash values are calculcated on the canonical form.

   The following two sections describe two valid ways of adding NO
   records to a zone.




Josefsson                 Expires May 25, 2001                 [Page 10]

Internet-Draft               The NO Record                 November 2000


3.13.2 Simple NO creating entity

   A simple NO creator entity might not implement truncation or provide
   the possibility to deny more than one records per NO record.  In
   this case, the following would be added to the zone file.

   $ORIGIN _no.example.org.
   1b7838c69a66eb50cc215f66ee4554d0c4c940a5
   		IN NO A 0x222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1
   222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1
   		IN NO NS SOA MX 0x839ebd4386c0b26d81f147421b5b7036e61438cf
   839ebd4386c0b26d81f147421b5b7036e61438cf
   		IN NO A 0x906a0ad5e604b1905828499dc8672ecb8de73e2f
   906a0ad5e604b1905828499dc8672ecb8de73e2f
   		IN NO A TXT 0x1b7838c69a66eb50cc215f66ee4554d0c4c940a5

3.13.3 Advanced NO creating entity

   A more advanced NO creator entity might append the following
   instead, using both truncation and "compression".

   $ORIGIN _no.example.org
   1b	IN NO A 0x22 NS SOA MX 0x83 A 0x90 A TXT 0x1b A

   Note that this contain 5 hash values while the zone only contain 4
   records, the last value in the line above is in fact the first hash
   value in the zone, closing the circular NO chain.

3.13.4 Resolver Query for Non-existing Domain

   Consider a client looking up the non-existant domain name
   "baz.example.org.", using the zone file from the previous section. 
   First, we note the following calculations.

   SHA-1(baz.example.org.) = 0xd5d0f98783eec6e9943750f35904304bd1a4090e
   SHA-1(*.example.org.)   = 0x7ab3776e3b529eb42467cc5d279c88ec951cf021

   A server would reply with an RCODE of NXDOMAIN and the authority
   section data including the following:












Josefsson                 Expires May 25, 2001                 [Page 11]

Internet-Draft               The NO Record                 November 2000


   ; backwards compatibility
   example.org.		IN SOA

   ; prove no baz.example.org
   906a0ad5e604b1905828499dc8672ecb8de73e2f._no.example.org.
   		IN NO A TXT 0x1b7838c69a66eb50cc215f66ee4554d0c4c940a5
   906a0ad5e604b1905828499dc8672ecb8de73e2f._no.example.org. IN SIG NO

   ; prove no *.example.org:
   222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1._no.example.org.
   		IN NO NS SOA MX 0x839ebd4386c0b26d81f147421b5b7036e61438cf
   222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1._no.example.org. IN SIG NO

   In order for a client to verify the authenticity of this reply, in
   addition of verifying the SIG record, it will also need to calculate
   the one-way hash of "baz.example.org." and verify it is contained
   inside the interval of any NO record in the authority section.