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

bind-3.2.

Network Working Group                                       S. Josefsson
Internet-Draft                                              RSA Security
Expires: May 25, 2001                                  November 24, 2000


   Authenticating denial of existence in DNS with minimum disclosure
               (or; An alternative to DNSSEC NXT records)
                  draft-ietf-dnsext-not-existing-rr-01

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups. Note that
   other groups may also distribute working documents as
   Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six
   months and may be updated, replaced, or obsoleted by other documents
   at any time. It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on May 25, 2001.

Copyright Notice

   Copyright (C) The Internet Society (2000). All Rights Reserved.

Abstract

   This draft present an alternative to NXT records, used to achieve
   authenticated denial of existence of a domain name, class and type. 
   Problems with NXT records, as specified in RFC 2535, are identified.
   One solution, the NO record, is presented.

   The NO record differ from the NXT record by using a cryptographic
   hash value instead of the domain name.  This prevent an adversery
   from collecting information by "chaining" through a zone.  It also
   remove delegation point concerns that was a side effect of NXT
   records.  The document also describe hash truncation and record
   merging that reduces storage/network load.



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


Table of Contents

   1.     Introduction . . . . . . . . . . . . . . . . . . . . . . .   3
   2.     Context  . . . . . . . . . . . . . . . . . . . . . . . . .   3
   3.     The NO Resource Record . . . . . . . . . . . . . . . . . .   4
   3.1    Idea . . . . . . . . . . . . . . . . . . . . . . . . . . .   4
   3.2    NO RDATA Format  . . . . . . . . . . . . . . . . . . . . .   4
   3.3    NO RDATA on-the-wire format example  . . . . . . . . . . .   6
   3.4    Owner Names  . . . . . . . . . . . . . . . . . . . . . . .   6
   3.5    Additional Complexity Due To Wildcards . . . . . . . . . .   7
   3.6    No Considerations at Delegation Points . . . . . . . . . .   7
   3.7    Hash Truncation and Dynamic Updates  . . . . . . . . . . .   8
   3.8    Reducing Number of Records . . . . . . . . . . . . . . . .   9
   3.9    Hash Collisions  . . . . . . . . . . . . . . . . . . . . .   9
   3.10   Authenticating Denial of NO Records  . . . . . . . . . . .   9
   3.11   Case Considerations  . . . . . . . . . . . . . . . . . . .  10
   3.12   Presentation Format  . . . . . . . . . . . . . . . . . . .  10
   3.13   Examples . . . . . . . . . . . . . . . . . . . . . . . . .  10
   3.13.1 Adding NO Records to a Zone  . . . . . . . . . . . . . . .  10
   3.13.2 Simple NO creating entity  . . . . . . . . . . . . . . . .  11
   3.13.3 Advanced NO creating entity  . . . . . . . . . . . . . . .  11
   3.13.4 Resolver Query for Non-existing Domain . . . . . . . . . .  11
   3.13.5 Resolver Query for Non-existing Type At Existing Domain  .  12
   4.     Comparing NO and NXT . . . . . . . . . . . . . . . . . . .  13
   4.1    Denial Of Existence Of Non-Existing Names  . . . . . . . .  13
   4.2    Denial Of Types Of Existing Names  . . . . . . . . . . . .  13
   4.3    Information disclosure (chain problem) . . . . . . . . . .  13
   4.4    Delegation problem . . . . . . . . . . . . . . . . . . . .  13
   4.5    Zone size (Bytes)  . . . . . . . . . . . . . . . . . . . .  13
   4.6    Zone size (Number Of Records)  . . . . . . . . . . . . . .  13
   4.7    Zone size (Number Of Owner names)  . . . . . . . . . . . .  14
   4.8    SIG Labels field and Wildcard records  . . . . . . . . . .  14
   4.9    Dynamic Updates  . . . . . . . . . . . . . . . . . . . . .  14
   5.     Security Considerations  . . . . . . . . . . . . . . . . .  15
   6.     IANA Considerations  . . . . . . . . . . . . . . . . . . .  15
          References . . . . . . . . . . . . . . . . . . . . . . . .  16
          Author's Address . . . . . . . . . . . . . . . . . . . . .  16
          Full Copyright Statement . . . . . . . . . . . . . . . . .  17













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


1. Introduction

   "Domain Name Security Extensions", RFC 2535 [1], specifies several
   extensions to DNS that provides data integrity and authentication. 
   Among them is the NXT record, used to achieve authenticated denial
   of existence of domains, and authenticated denial of existence on
   certain class/types on existing domains.

   As a consequence of NXT records it is possible to "chain" through a
   zone secured by DNS security extensions, collecting all names and/or
   records in the zone.  NXT records also introduce a complication at
   delegation points.  These are the main problems that motivated this
   draft.

2. Context

   There have been arguments that the "chain" problem of NXT records is
   a non-issue.  Often used is the argument that information in DNS is
   public, and if you wish to keep information private, you shouldn't
   publish it in DNS.  This might be true, but nonetheless major
   service providers and companies are restricting access to zone
   transfers.  Also, people have debated whether NXT records should be
   part of DNSSEC at all because of this problem [5].

   Another aspect exist.  When DNS is used to store certificates, as
   described in RFC 2538 [2], certificates can identify individuals
   and/or carry authentication information for special purposes. This
   context has been the motivation for developing this draft.

   The "chain" problem is not the only concern with NXT records.  The
   delegation considerations for NXT records (different RRsets in the
   parent and child for the same domain) has also been regarded as a
   flaw of the NXT records.


















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


3. The NO Resource Record

   This section describe the NO Resource Record.

3.1 Idea

   A straight-forward extension to the NXT record that minimize
   disclosure of information is to store a one-way function value
   instead of the actual domain name.  This is similar to NXT records;
   where NXT records secure a interval where no existing domain names
   are to be found, NO records secure a interval where no one-way value
   of existing domain names are to be found.

   The benefit, of course, is that an adversary does not yield any
   useful information from the record.  Specifically, "chaining"
   through a zone to collect all records is no longer possible.

   This idea has been extended in this document into allowing (but not
   requiring) one record to deny existence of several records, and
   truncating the hash value to the shortest unique prefix to preserve
   space.

3.2 NO RDATA Format

   The RDATA for a NO RR consists of one or more fields with the
   following structure.  The structure have the following elements: a
   zero-terminated list of RR types, a hash length specifier, and a
   hash value, as shown below.  Both the "RR type" list and the "next
   hash value" fields are of variable width.

                        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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               /
   /                       owner RR type list                      /
   /                                                               |
   +---------------+-----------------------------------------------+
   | # hash octets |       SHA-1 hash value                        /
   +---------------+                                               /
   /                                                               /
   +---------------------------------------------------------------+

   Replacing the NXT RR "type bit map" field is a variable length list
   of RR types.  Each RR type is 16 bits.  As the list is of variable
   length, a end-of-list indicator is require.  End of the list is
   signalled by a all-zero RR type. Each element is a 2 byte RR type. 
   The list MUST be sorted in RR type order.  The change from NXT's
   bitmap field removes the limit of authenticating only the first 127
   RR types.


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


   The RR type list indicates what types exist at the previous hash
   value -- i.e. the first RR type list in the RRdata of a NO record
   indicate what RR types exist at the domain name that hashes to the
   owner name of that NO record.  The second RR type list, if any, in
   the RRdata of a NO record indicate what RR types exist at the domain
   name that hashes the first SHA-1 value in the RRdata.  And so on. 
   See below for a complete example of the on-the-wire-format of a NO
   record with hash truncation and record merging and its
   interpretation.

   Length of the hash value field is denoted by the # hash octets
   fields, it is a unsigned integer ranging from 0 to 255. The meaning
   of a zero length integer is reserved.

   The SHA-1 hash value field is a variable length field containing the
   actual hash value.

   The NO RRs for a zone SHOULD be automatically calculated and added
   to the zone when SIGs are added.  The NO RR's TTL SHOULD NOT exceed
   the zone minimum TTL.

   The type number for the NO RR is TBD.

   NO RR's MUST only be signed by zone level keys [7].



























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


3.3 NO RDATA on-the-wire format example

   The following is a example of the on-the-wire-format of a complete
   NO resource record were hash truncation and record merging is used. 
   It is the on-the-wire format of the NO record in section 3.13.1.2.

                        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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         RR type 1 (A)         |   RR type 0 (end-of-list)     |
   +---------------+-----------------------------------------------+
   |  1 hash octet |  Hash 0x22    |        RR type 2 (NS)         |
   +---------------+---------------+-------------------------------+
   |         RR type 6 (SOA)       |        RR type 15 (MX)        |
   +-------------------------------+---------------+---------------+
   |    RR type 0 (end-of-list)    |  1 hash octet |  Hash 0x83    |
   +-------------------------------+---------------+---------------+
   |         RR type 1 (A)         |   RR type 0 (end-of-list)     |
   +---------------+-----------------------------------------------+
   |  1 hash octet |  Hash 0x90    |        RR type 1 (A)          |
   +---------------+---------------+-------------------------------+
   |         RR type 16 (TXT)      |   RR type 0 (end-of-list)     |
   +---------------+---------------+-------------------------------+
   |  1 hash octet |  Hash 0x1b    |
   +-------------------------------+

   The intepretation here is that the domain that corresponds with the
   NO owner name ("1b._no.example.org.", not shown above) have a A
   record, that the domain that hash to 0x22 (truncated to one octet)
   have a NS, SOA and MX record, that the domain that hash to 0x83
   (truncated to 1 octet) have a A record etc. Note that the last hash
   value of NO RRdata does not have a RR type list in the same record.

3.4 Owner Names