WikiStart: draft-ietf-dnsext-nsec3-13.txt

Network Working Group                                          B. Laurie
Internet-Draft                                                 G. Sisson
Intended status: Standards Track                               R. Arends
Expires: June 2, 2008                                            Nominet
                                                               D. Blacka
                                                          VeriSign, Inc.
                                                       November 30, 2007


            DNSSEC Hashed Authenticated Denial of Existence
                       draft-ietf-dnsext-nsec3-13

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   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 June 2, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Abstract

   The Domain Name System Security Extensions (DNSSEC) introduced the
   NSEC resource record (RR) for authenticated denial of existence.
   This document introduces an alternative resource record, NSEC3, which
   similarly provides authenticated denial of existence.  However, it
   also provides measures against zone enumeration and permits gradual



Laurie, et al.            Expires June 2, 2008                  [Page 1]

Internet-Draft                    nsec3                    November 2007


   expansion of delegation-centric zones.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Rationale  . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.2.  Reserved Words . . . . . . . . . . . . . . . . . . . . . .  4
     1.3.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  Backwards Compatibility  . . . . . . . . . . . . . . . . . . .  6
   3.  The NSEC3 Resource Record  . . . . . . . . . . . . . . . . . .  7
     3.1.  RDATA Fields . . . . . . . . . . . . . . . . . . . . . . .  8
       3.1.1.  Hash Algorithm . . . . . . . . . . . . . . . . . . . .  8
       3.1.2.  Flags  . . . . . . . . . . . . . . . . . . . . . . . .  8
       3.1.3.  Iterations . . . . . . . . . . . . . . . . . . . . . .  8
       3.1.4.  Salt Length  . . . . . . . . . . . . . . . . . . . . .  8
       3.1.5.  Salt . . . . . . . . . . . . . . . . . . . . . . . . .  8
       3.1.6.  Hash Length  . . . . . . . . . . . . . . . . . . . . .  9
       3.1.7.  Next Hashed Owner Name . . . . . . . . . . . . . . . .  9
       3.1.8.  Type Bit Maps  . . . . . . . . . . . . . . . . . . . .  9
     3.2.  NSEC3 RDATA Wire Format  . . . . . . . . . . . . . . . . .  9
       3.2.1.  Type Bit Maps Encoding . . . . . . . . . . . . . . . . 10
     3.3.  Presentation Format  . . . . . . . . . . . . . . . . . . . 11
   4.  The NSEC3PARAM Record  . . . . . . . . . . . . . . . . . . . . 12
     4.1.  RDATA Fields . . . . . . . . . . . . . . . . . . . . . . . 12
       4.1.1.  Hash Algorithm . . . . . . . . . . . . . . . . . . . . 12
       4.1.2.  Flag Fields  . . . . . . . . . . . . . . . . . . . . . 12
       4.1.3.  Iterations . . . . . . . . . . . . . . . . . . . . . . 13
       4.1.4.  Salt Length  . . . . . . . . . . . . . . . . . . . . . 13
       4.1.5.  Salt . . . . . . . . . . . . . . . . . . . . . . . . . 13
     4.2.  NSEC3PARAM RDATA Wire Format . . . . . . . . . . . . . . . 13
     4.3.  Presentation Format  . . . . . . . . . . . . . . . . . . . 13
   5.  Calculation of the Hash  . . . . . . . . . . . . . . . . . . . 14
   6.  Opt-Out  . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
   7.  Authoritative Server Considerations  . . . . . . . . . . . . . 15
     7.1.  Zone Signing . . . . . . . . . . . . . . . . . . . . . . . 15
     7.2.  Zone Serving . . . . . . . . . . . . . . . . . . . . . . . 17
       7.2.1.  Closest Encloser Proof . . . . . . . . . . . . . . . . 18
       7.2.2.  Name Error Responses . . . . . . . . . . . . . . . . . 18
       7.2.3.  No Data Responses, QTYPE is not DS . . . . . . . . . . 19
       7.2.4.  No Data Responses, QTYPE is DS . . . . . . . . . . . . 19
       7.2.5.  Wildcard No Data Responses . . . . . . . . . . . . . . 19
       7.2.6.  Wildcard Answer Responses  . . . . . . . . . . . . . . 19
       7.2.7.  Referrals to Unsigned Subzones . . . . . . . . . . . . 20
       7.2.8.  Responding to Queries for NSEC3 Owner Names  . . . . . 20
       7.2.9.  Server Response to a Run-time Collision  . . . . . . . 20
     7.3.  Secondary Servers  . . . . . . . . . . . . . . . . . . . . 20
     7.4.  Zones Using Unknown Hash Algorithms  . . . . . . . . . . . 21



Laurie, et al.            Expires June 2, 2008                  [Page 2]

Internet-Draft                    nsec3                    November 2007


     7.5.  Dynamic Update . . . . . . . . . . . . . . . . . . . . . . 21
   8.  Validator Considerations . . . . . . . . . . . . . . . . . . . 22
     8.1.  Responses with Unknown Hash Types  . . . . . . . . . . . . 22
     8.2.  Verifying NSEC3 RRs  . . . . . . . . . . . . . . . . . . . 22
     8.3.  Closest Encloser Proof . . . . . . . . . . . . . . . . . . 23
     8.4.  Validating Name Error Responses  . . . . . . . . . . . . . 24
     8.5.  Validating No Data Responses, QTYPE is not DS  . . . . . . 24
     8.6.  Validating No Data Responses, QTYPE is DS  . . . . . . . . 24
     8.7.  Validating Wildcard No Data Responses  . . . . . . . . . . 24
     8.8.  Validating Wildcard Answer Responses . . . . . . . . . . . 24
     8.9.  Validating Referrals to Unsigned Subzones  . . . . . . . . 25
   9.  Resolver Considerations  . . . . . . . . . . . . . . . . . . . 25
     9.1.  NSEC3 Resource Record Caching  . . . . . . . . . . . . . . 25
     9.2.  Use of the AD Bit  . . . . . . . . . . . . . . . . . . . . 25
   10. Special Considerations . . . . . . . . . . . . . . . . . . . . 26
     10.1. Domain Name Length Restrictions  . . . . . . . . . . . . . 26
     10.2. DNAME at the Zone Apex . . . . . . . . . . . . . . . . . . 26
     10.3. Iterations . . . . . . . . . . . . . . . . . . . . . . . . 26
     10.4. Transitioning a Signed Zone from NSEC to NSEC3 . . . . . . 27
     10.5. Transitioning a Signed Zone From NSEC3 to NSEC . . . . . . 28
   11. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 28
   12. Security Considerations  . . . . . . . . . . . . . . . . . . . 30
     12.1. Hashing Considerations . . . . . . . . . . . . . . . . . . 30
       12.1.1. Dictionary Attacks . . . . . . . . . . . . . . . . . . 30
       12.1.2. Collisions . . . . . . . . . . . . . . . . . . . . . . 30
       12.1.3. Transitioning to a New Hash Algorithm  . . . . . . . . 30
       12.1.4. Using High Iteration Values  . . . . . . . . . . . . . 31
     12.2. Opt-Out Considerations . . . . . . . . . . . . . . . . . . 31
     12.3. Other Considerations . . . . . . . . . . . . . . . . . . . 32
   13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 32
     13.1. Normative References . . . . . . . . . . . . . . . . . . . 32
     13.2. Informative References . . . . . . . . . . . . . . . . . . 33
   Appendix A.  Example Zone  . . . . . . . . . . . . . . . . . . . . 34
   Appendix B.  Example Responses . . . . . . . . . . . . . . . . . . 39
     B.1.  Name Error . . . . . . . . . . . . . . . . . . . . . . . . 39
     B.2.  No Data Error  . . . . . . . . . . . . . . . . . . . . . . 41
       B.2.1.  No Data Error, Empty Non-Terminal  . . . . . . . . . . 41
     B.3.  Referral to an Opt-Out Unsigned Zone . . . . . . . . . . . 42
     B.4.  Wildcard Expansion . . . . . . . . . . . . . . . . . . . . 44
     B.5.  Wildcard No Data Error . . . . . . . . . . . . . . . . . . 46
     B.6.  DS Child Zone No Data Error  . . . . . . . . . . . . . . . 47
   Appendix C.  Special Considerations  . . . . . . . . . . . . . . . 48
     C.1.  Salting  . . . . . . . . . . . . . . . . . . . . . . . . . 48
     C.2.  Hash Collision . . . . . . . . . . . . . . . . . . . . . . 49
       C.2.1.  Avoiding Hash Collisions During Generation . . . . . . 49
       C.2.2.  Second Preimage Requirement Analysis . . . . . . . . . 50
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 50
   Intellectual Property and Copyright Statements . . . . . . . . . . 52



Laurie, et al.            Expires June 2, 2008                  [Page 3]

Internet-Draft                    nsec3                    November 2007


1.  Introduction

1.1.  Rationale

   The DNS Security Extensions included the NSEC RR to provide
   authenticated denial of existence.  Though the NSEC RR meets the
   requirements for authenticated denial of existence, it introduces a
   side-effect in that the contents of a zone can be enumerated.  This
   property introduces undesired policy issues.

   The enumeration is enabled by the set of NSEC records that exists
   inside a signed zone.  An NSEC record lists two names that are
   ordered canonically, in order to show that nothing exists between the
   two names.  The complete set of NSEC records lists all the names in a
   zone.  It is trivial to enumerate the content of a zone by querying
   for names that do not exist.

   An enumerated zone can be used, for example, as a source of probable
   e-mail addresses for spam, or as a key for multiple WHOIS queries to
   reveal registrant data which many registries may have legal
   obligations to protect.  Many registries therefore prohibit copying
   of their zone data; however, the use of NSEC RRs renders these
   policies unenforceable.

   A second problem is that the cost to cryptographically secure
   delegations to unsigned zones is high, relative to the perceived
   security benefit, in two cases: large, delegation-centric zones, and
   zones where insecure delegations will be updated rapidly.  In these
   cases, the costs of maintaining the NSEC RR chain may be extremely
   high and use of the "Opt-Out" convention may be more appropriate (for
   these unsecured zones).

   This document presents the NSEC3 Resource Record which can be used as
   an alternative to NSEC to mitigate these issues.

   Earlier work to address these issues include [I-D.jas-dnsext-no],
   [RFC4956] and [I-D.laurie-dnsext-nsec2v2].

1.2.  Reserved Words

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

1.3.  Terminology

   The reader is assumed to be familiar with the basic DNS and DNSSEC
   concepts described in [RFC1034], [RFC1035], [RFC4033], [RFC4034],



Laurie, et al.            Expires June 2, 2008                  [Page 4]

Internet-Draft                    nsec3                    November 2007


   [RFC4035] and subsequent RFCs that update them: [RFC2136], [RFC2181]
   and [RFC2308].

   The following terminology is used throughout this document:

   Zone enumeration:  the practice of discovering the full content of a
      zone via successive queries.  Zone enumeration was non-trivial
      prior to the introduction of DNSSEC.

   Original owner name:  the owner name corresponding to a hashed owner
      name.

   Hashed owner name:  the owner name created after applying the hash
      function to an owner name.

   Hash order:  the order in which hashed owner names are arranged
      according to their numerical value, treating the leftmost (lowest
      numbered) octet as the most significant octet.  Note that this
      order is the same as the canonical DNS name order specified in
      [RFC4034] when the hashed owner names are in base32 encoded with
      Extended Hex Alphabet [RFC4648].

   Empty non-terminal:  a domain name that owns no resource records, but
      has one or more subdomains that do.

   Delegation:  an NS RRSet with a name different from the current zone
      apex (non-zone-apex), signifying a delegation to a child zone.

   Secure delegation:  a name containing a delegation (NS RRSet), and a
      signed DS RRSet, signifying a delegation to a signed child zone.

   Insecure delegation:  a name containing a delegation (NS RRSet), but
      lacking a DS RRSet, signifying a delegation to an unsigned child
      zone.

   Opt-Out NSEC3 resource record:  an NSEC3 resource record which has
      the Opt-Out flag set to 1.

   Opt-Out zone:  a zone with at least one Opt-Out NSEC3 RR.

   Closest encloser:  the longest existing ancestor of a name.  See also
      section 3.3.1 of [RFC4592].

   Closest provable encloser:  the longest ancestor of a name that can
      be proven to exist.  Note that this is only different from the
      closest encloser in an Opt-Out zone.





Laurie, et al.            Expires June 2, 2008                  [Page 5]

Internet-Draft                    nsec3                    November 2007


   Next closer name:  the name one label longer than the closest
      provable encloser of a name.

   Base32:  the "Base 32 Encoding with Extended Hex Alphabet" as
      specified in [RFC4648].  Note that trailing padding characters
      ("=") are not used in the NSEC3 specification.

   To cover:  An NSEC3 RR is said to "cover" a name if the hash of the
      name or "next closer" name falls between the owner name and the
      next hashed owner name of the NSEC3.  In other words, if it proves
      the nonexistence of the name, either directly or by proving the
      nonexistence of an ancestor of the name.

   To match:  An NSEC3 RR is said to "match" a name if the owner name of
      the NSEC3 RR is the same as the hashed owner name of that name.


2.  Backwards Compatibility

   This specification describes a protocol change that is not generally
   backwards compatible with [RFC4033], [RFC4034] and [RFC4035].  In
   particular, security-aware resolvers that are unaware of this
   specification (NSEC3-unaware resolvers) may fail to validate the
   responses introduced by this document.

   In order to aid deployment, this specification uses a signaling
   technique to prevent NSEC3-unaware resolvers from attempting to
   validate responses from NSEC3-signed zones.

   This specification allocates two new DNSKEY algorithm identifiers for
   this purpose.  Algorithm XX, DSA-NSEC3-SHA1 [### RFC-editor update
   required, temporarily, XX=131] is an alias for algorithm 3, DSA.
   Algorithm YY, RSASHA1-NSEC3-SHA1 [### RFC-editor update required,
   temporarily, YY=133] is an alias for algorithm 5, RSASHA1.  These are
   not new algorithms, they are additional identifiers for the existing
   algorithms.

   Zones signed according to this specification MUST only use these
   algorithm identifiers for their DNSKEY RRs.  Because these new
   identifiers will be unknown algorithms to existing, NSEC3-unaware
   resolvers, those resolvers will then treat responses from the NSEC3
   signed zone as insecure, as detailed in [RFC4035], section 5.2.

   These algorithm identifiers are used with the NSEC3 hash algorithm
   SHA1.  Using other NSEC3 hash algorithms requires allocation of a new
   alias (see Section 12.1.3).

   Security aware resolvers that are aware of this specification MUST



Laurie, et al.            Expires June 2, 2008                  [Page 6]

Internet-Draft                    nsec3                    November 2007


   recognize the new algorithm identifiers and treat them as equivalent
   to the algorithms that they alias.

   A methodology for transitioning from a DNSSEC signed zone to a zone
   signed using NSEC3 is discussed in Section 10.4.


3.  The NSEC3 Resource Record

   The NSEC3 Resource Record (RR) provides authenticated denial of
   existence for DNS Resource Record Sets.

   The NSEC3 RR lists RR types present at the original owner name of the
   NSEC3 RR.  It includes the next hashed owner name in the hash order
   of the zone.  The complete set of NSEC3 RRs in a zone indicates which
   RRSets exist for the original owner name of the RR and form a chain
   of hashed owner names in the zone.  This information is used to
   provide authenticated denial of existence for DNS data.  To provide
   protection against zone enumeration, the owner names used in the
   NSEC3 RR are cryptographic hashes of the original owner name
   prepended as a single label to the name of the zone.  The NSEC3 RR
   indicates which hash function is used to construct the hash, which
   salt is used, and how many iterations of the hash function are
   performed over the original owner name.  The hashing technique is
   described fully in Section 5.

   Hashed owner names of unsigned delegations may be excluded from the
   chain.  An NSEC3 RR whose span covers the hash of an owner name or
   "next closer" name of an unsigned delegation is referred to as an
   Opt-Out NSEC3 RR and is indicated by the presence of a flag.

   The owner name for the NSEC3 RR is the base32 encoding of the hashed
   owner name prepended as a single label to the name of the zone.

   The type value for the NSEC3 RR is NN. [### RFC-editor update
   required, the examples assume NN=50]

   The NSEC3 RR RDATA format is class independent and is described
   below.

   The class MUST be the same as the class of the original owner name.

   The NSEC3 RR SHOULD have the same TTL value as the SOA minimum TTL
   field.  This is in the spirit of negative caching [RFC2308].







Laurie, et al.            Expires June 2, 2008                  [Page 7]

Internet-Draft                    nsec3                    November 2007


3.1.  RDATA Fields

3.1.1.  Hash Algorithm

   The Hash Algorithm field identifies the cryptographic hash algorithm
   used to construct the hash-value.

   The values for this field are defined in the NSEC3 hash algorithm
   registry, described in Section 11.

3.1.2.  Flags

   The Flags field contains 8 one-bit flags that can be used to indicate
   different processing.  All undefined flags must be zero.  The only
   flag defined by this specification is the Opt-Out flag.

3.1.2.1.  Opt-Out Flag

   If the Opt-Out flag is set, the NSEC3 record covers zero or more
   unsigned delegations.

   If the Opt-Out flag is clear, the NSEC3 record covers zero unsigned
   delegations.

   The Opt-Out Flag indicates whether this NSEC3 RR may cover unsigned
   delegations.  It is the least significant bit in the Flags field.
   See Section 6 for details about the use of this flag.

3.1.3.  Iterations

   The Iterations field defines the number of additional times the hash
   function has been performed.  More iterations result in greater
   resiliency of the hash value against dictionary attacks, but at a
   higher computational cost for both the server and resolver.  See
   Section 5 for details of the use of this field, and Section 10.3 for
   limitations on the value.

3.1.4.  Salt Length

   The Salt Length field defines the length of the Salt field in octets,
   ranging in value from 0 to 255.

3.1.5.  Salt

   The Salt field is appended to the original owner name before hashing
   in order to defend against pre-calculated dictionary attacks.  See
   Section 5 for details on how the salt is used.




Laurie, et al.            Expires June 2, 2008                  [Page 8]

Internet-Draft                    nsec3                    November 2007


3.1.6.  Hash Length

   The Hash Length field defines the length of the Next Hashed Owner
   Name field, ranging in value from 1 to 255 octets.

3.1.7.  Next Hashed Owner Name

   The Next Hashed Owner Name field contains the next hashed owner name
   in hash order.  This value is in binary format.  Given the ordered
   set of all hashed owner names, the Next Hashed Owner Name field
   contains the hash of an owner name that immediately follows the owner
   name of the given NSEC3 RR.  The value of the Next Hashed Owner Name
   field in the last NSEC3 RR in the zone is the same as the hashed
   owner name of the first NSEC3 RR in the zone in hash order.  Note
   that, unlike the owner name of the NSEC3 RR, the value of this field
   does not contain the appended zone name.

3.1.8.  Type Bit Maps

   The Type Bit Maps field identifies the RRSet types which exist at the
   original owner name of the NSEC3 RR.

3.2.  NSEC3 RDATA Wire Format

   The RDATA of the NSEC3 RR is as shown below:

                        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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Hash Alg.   |     Flags     |          Iterations           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Salt Length  |                     Salt                      /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Hash Length  |             Next Hashed Owner Name            /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   /                         Type Bit Maps                         /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Hash Algorithm is a single octet.

   Flags field is a single octet, the Opt-Out flag is the least
   significant bit, as shown below:

    0 1 2 3 4 5 6 7
   +-+-+-+-+-+-+-+-+
   |             |O|
   +-+-+-+-+-+-+-+-+




Laurie, et al.            Expires June 2, 2008                  [Page 9]

Internet-Draft                    nsec3                    November 2007


   Iterations is represented as a 16-bit unsigned integer, with the most
   significant bit first.

   Salt Length is represented as an unsigned octet.  Salt Length
   represents the length of the Salt field in octets.  If the value is
   zero, the following Salt field is omitted.

   Salt, if present, is encoded as a sequence of binary octets.  The
   length of this field is determined by the preceding Salt Length
   field.

   Hash Length is represented as an unsigned octet.  Hash Length
   represents the length of the Next Hashed Owner Name field in octets.

   The next hashed owner name is not base32 encoded, unlike the owner
   name of the NSEC3 RR.  It is the unmodified binary hash value.  It
   does not include the name of the containing zone.  The length of this
   field is determined by the preceding Hash Length field.

3.2.1.  Type Bit Maps Encoding

   The encoding of the Type Bit Maps field is the same as that used by
   the NSEC RR, described in [RFC4034].  It is explained and clarified
   here for clarity.

   The RR type space is split into 256 window blocks, each representing
   the low-order 8 bits of the 16-bit RR type space.  Each block that
   has at least one active RR type is encoded using a single octet
   window number (from 0 to 255), a single octet bitmap length (from 1
   to 32) indicating the number of octets used for the bitmap of the
   window block, and up to 32 octets (256 bits) of bitmap.

   Blocks are present in the NSEC3 RR RDATA in increasing numerical
   order.

      Type Bit Maps Field = ( Window Block # | Bitmap Length | Bitmap )+

      where "|" denotes concatenation.

   Each bitmap encodes the low-order 8 bits of RR types within the
   window block, in network bit order.  The first bit is bit 0.  For
   window block 0, bit 1 corresponds to RR type 1 (A), bit 2 corresponds
   to RR type 2 (NS), and so forth.  For window block 1, bit 1
   corresponds to RR type 257, bit 2 to RR type 258.  If a bit is set to
   1, it indicates that an RRSet of that type is present for the
   original owner name of the NSEC3 RR.  If a bit is set to 0, it
   indicates that no RRSet of that type is present for the original
   owner name of the NSEC3 RR.



Laurie, et al.            Expires June 2, 2008                 [Page 10]

Internet-Draft                    nsec3                    November 2007


   Since bit 0 in window block 0 refers to the non-existing RR type 0,
   it MUST be set to 0.  After verification, the validator MUST ignore
   the value of bit 0 in window block 0.

   Bits representing Meta-TYPEs or QTYPEs as specified in [RFC2929]
   (section 3.1) or within the range reserved for assignment only to
   QTYPEs and Meta-TYPEs MUST be set to 0, since they do not appear in
   zone data.  If encountered, they must be ignored upon reading.

   Blocks with no types present MUST NOT be included.  Trailing zero
   octets in the bitmap MUST be omitted.  The length of the bitmap of
   each block is determined by the type code with the largest numerical
   value, within that block, among the set of RR types present at the
   original owner name of the NSEC3 RR.  Trailing octets not specified
   MUST be interpreted as zero octets.

3.3.  Presentation Format

   The presentation format of the RDATA portion is as follows:

   o  The Hash Algorithm field is represented as an unsigned decimal
      integer.  The value has a maximum of 255.

   o  The Flags field is represented as an unsigned decimal integer.
      The value has a maximum of 255.

   o  The Iterations field is represented as an unsigned decimal
      integer.  The value is between 0 and 65535, inclusive.

   o  The Salt Length field is not represented.

   o  The Salt field is represented as a sequence of case-insensitive
      hexadecimal digits.  Whitespace is not allowed within the
      sequence.  The Salt field is represented as "-" (without the
      quotes) when the Salt Length field has value 0.

   o  The Hash Length field is not represented.

   o  The Next Hashed Owner Name field is represented as an unpadded
      sequence of case-insensitive base32 digits, without whitespace.

   o  The Type Bit Maps field is represented as a sequence of RR type
      mnemonics.  When the mnemonic is not known, the TYPE
      representation as described in [RFC3597] (section 5) MUST be used.







Laurie, et al.            Expires June 2, 2008                 [Page 11]

Internet-Draft                    nsec3                    November 2007


4.  The NSEC3PARAM Record

   The NSEC3PARAM RR contains the NSEC3 parameters (hash algorithm,
   flags, iterations and salt) needed by authoritative servers to
   calculate hashed owner names.  The presence of an NSEC3PARAM RR at a
   zone apex indicates that the specified parameters may be used by
   authoritative servers to choose an appropriate set of NSEC3 RRs for
   negative responses.  The NSEC3PARAM RR is not used by validators or
   resolvers.

   If an NSEC3PARAM RR is present at the apex of a zone with a Flags
   field value of zero, then there MUST be an NSEC3 RR using the same
   hash algorithm, iterations and salt parameters present at every
   hashed owner name in the zone.  That is, the zone MUST contain a
   complete set of NSEC3 RRs with the same hash algorithm, iterations
   and salt parameters.

   The owner name for the NSEC3PARAM RR is the name of the zone apex.

   The type value for the NSEC3PARAM RR is MM. [### RFC-editor update
   required, the examples assume MM=51]

   The NSEC3PARAM RR RDATA format is class independent and is described
   below.

   The class MUST be the same as the NSEC3 RRs to which this RR refers.

4.1.  RDATA Fields

   The RDATA for this RR mirrors the first four fields in the NSEC3 RR.

4.1.1.  Hash Algorithm

   The Hash Algorithm field identifies the cryptographic hash algorithm
   used to construct the hash-value.

   The acceptable values are the same as the corresponding field in the
   NSEC3 RR.

4.1.2.  Flag Fields

   The Opt-Out flag is not used and is set to zero.

   All other flags are reserved for future use, and must be zero.

   NSEC3PARAM RRs with a Flags field value other than zero MUST be
   ignored.




Laurie, et al.            Expires June 2, 2008                 [Page 12]

Internet-Draft                    nsec3                    November 2007


4.1.3.  Iterations

   The Iterations field defines the number of additional times the hash
   is performed.

   Its acceptable values are the same as the corresponding field in the
   NSEC3 RR.

4.1.4.  Salt Length

   The Salt Length field defines the length of the salt in octets,
   ranging in value from 0 to 255.

4.1.5.  Salt

   The Salt field is appended to the original owner name before hashing.

4.2.  NSEC3PARAM RDATA Wire Format

   The RDATA of the NSEC3PARAM RR is as shown below:

                        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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   Hash Alg.   |     Flags     |          Iterations           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Salt Length  |                     Salt                      /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Hash Algorithm is a single octet.

   Flags field is a single octet.

   Iterations is represented as a 16-bit unsigned integer, with the most
   significant bit first.

   Salt Length is represented as an unsigned octet.  Salt Length
   represents the length of the following Salt field in octets.  If the
   value is zero, the Salt field is omitted.

   Salt, if present, is encoded as a sequence of binary octets.  The
   length of this field is determined by the preceding Salt Length
   field.

4.3.  Presentation Format

   The presentation format of the RDATA portion is as follows:




Laurie, et al.            Expires June 2, 2008                 [Page 13]

Internet-Draft                    nsec3                    November 2007


   o  The Hash Algorithm field is represented as an unsigned decimal
      integer.  The value has a maximum of 255.

   o  The Flags field is represented as an unsigned decimal integer.
      The value has a maximum value of 255.

   o  The Iterations field is represented as an unsigned decimal
      integer.  The value is between 0 and 65535, inclusive.

   o  The Salt Length field is not represented.

   o  The Salt field is represented as a sequence of case-insensitive
      hexadecimal digits.  Whitespace is not allowed within the
      sequence.  This field is represented as "-" (without the quotes)
      when the Salt Length field is zero.


5.  Calculation of the Hash

   The hash calculation uses three of the NSEC3 RDATA fields: Hash
   Algorithm, Salt, and Iterations.

   Define H(x) to be the hash of x using the Hash Algorithm selected by
   the NSEC3 RR, k to be the number of Iterations, and || to indicate
   concatenation.  Then define:

      IH(salt, x, 0) = H(x || salt), and

      IH(salt, x, k) = H(IH(salt, x, k-1) || salt), if k > 0

   Then the calculated hash of an owner name is

      IH(salt, owner name, iterations),

   where the owner name is in the canonical form, defined as:

   The wire format of the owner name where:

   1.  The owner name is fully expanded (no DNS name compression) and
       fully qualified;

   2.  All uppercase US-ASCII letters are replaced by the corresponding
       lowercase US-ASCII letters;

   3.  If the owner name is a wildcard name, the owner name is in its
       original unexpanded form, including the "*" label (no wildcard
       substitution);




Laurie, et al.            Expires June 2, 2008                 [Page 14]

Internet-Draft                    nsec3                    November 2007


   This form is as defined in section 6.2 of [RFC4034].

   The method to calculate the Hash is based on [RFC2898].


6.  Opt-Out

   In this specification, as in [RFC4033], [RFC4034] and [RFC4035], NS
   RRSets at delegation points are not signed and may be accompanied by
   a DS RRSet.  With the Opt-Out bit clear, the security status of the
   child zone is determined by the presence or absence of this DS RRSet,
   cryptographically proven by the signed NSEC3 RR at the hashed owner
   name of the delegation.  Setting the Opt-Out flag modifies this by
   allowing insecure delegations to exist within the signed zone without
   a corresponding NSEC3 RR at the hashed owner name of the delegation.

   An Opt-Out NSEC3 RR is said to cover a delegation if the hash of the
   owner name or "next closer" name of the delegation is between the
   owner name of the NSEC3 RR and the next hashed owner name.

   An Opt-Out NSEC3 RR does not assert the existence or non-existence of
   the insecure delegations that it may cover.  This allows for the
   addition or removal of these delegations without recalculating or re-
   signing RRs in the NSEC3 RR chain.  However, Opt-Out NSEC3 RRs do
   assert the (non)existence of other, authoritative RRSets.

   An Opt-Out NSEC3 RR MAY have the same original owner name as an
   insecure delegation.  In this case, the delegation is proven insecure
   by the lack of a DS bit in the type map and the signed NSEC3 RR does
   assert the existence of the delegation.

   Zones using Opt-Out MAY contain a mixture of Opt-Out NSEC3 RRs and
   non-Opt-Out NSEC3 RRs.  If an NSEC3 RR is not Opt-Out, there MUST NOT
   be any hashed owner names of insecure delegations (nor any other RRs)
   between it and the name indicated by the next hashed owner name in
   the NSEC3 RDATA.  If it is Opt-Out, it MUST only cover hashed owner
   names or hashed "next closer" names of insecure delegations.

   The effects of the Opt-Out flag on signing, serving, and validating
   responses are covered in following sections.


7.  Authoritative Server Considerations

7.1.  Zone Signing

   Zones using NSEC3 must satisfy the following properties:




Laurie, et al.            Expires June 2, 2008                 [Page 15]

Internet-Draft                    nsec3                    November 2007


   o  Each owner name within the zone that owns authoritative RRSets
      MUST have a corresponding NSEC3 RR.  Owner names that correspond
      to unsigned delegations MAY have a corresponding NSEC3 RR.
      However, if there is not a corresponding NSEC3 RR, there MUST be
      an Opt-Out NSEC3 RR that covers the "next closer" name to the
      delegation.  Other non-authoritative RRs are not represented by
      NSEC3 RRs.

   o  Each empty non-terminal MUST have a corresponding NSEC3 RR, unless
      the empty non-terminal is only derived from an insecure delegation
      covered by an Opt-Out NSEC3 RR.

   o  The TTL value for any NSEC3 RR SHOULD be the same as the minimum
      TTL value field in the zone SOA RR.

   o  The Type Bit Maps field of every NSEC3 RR in a signed zone MUST
      indicate the presence of all types present at the original owner
      name, except for the types solely contributed by an NSEC3 RR
      itself.  Note that this means that the NSEC3 type itself will
      never be present in the Type Bit Maps.

   The following steps describe a method of proper construction of NSEC3
   RRs.  This is not the only such possible method.

   1.  Select the hash algorithm and the values for salt and iterations.

   2.  For each unique original owner name in the zone add an NSEC3 RR.

       *  If Opt-Out is being used, owner names of unsigned delegations
          MAY be excluded.

       *  The owner name of the NSEC3 RR is the hash of the original
          owner name, prepended as a single label to the zone name.

       *  The Next Hashed Owner Name field is left blank for the moment.

       *  If Opt-Out is being used, set the Opt-Out bit to one.

       *  For collision detection purposes, optionally keep track of the
          original owner name with the NSEC3 RR.

       *  Additionally, for collision detection purposes, optionally
          create an additional NSEC3 RR corresponding to the original
          owner name with the asterisk label prepended (i.e., as if a
          wildcard existed as a child of this owner name) and keep track
          of this original owner name.  Mark this NSEC3 RR as temporary.





Laurie, et al.            Expires June 2, 2008                 [Page 16]

Internet-Draft                    nsec3                    November 2007


   3.  For each RRSet at the original owner name, set the corresponding
       bit in the Type Bit Maps field.

   4.  If the difference in number of labels between the apex and the
       original owner name is greater than 1, additional NSEC3 RRs need
       to be added for every empty non-terminal between the apex and the
       original owner name.  This process may generate NSEC3 RRs with
       duplicate hashed owner names.  Optionally, for collision
       detection, track the original owner names of these NSEC3 RRs and
       create temporary NSEC3 RRs for wildcard collisions in a similar
       fashion to step 1.

   5.  Sort the set of NSEC3 RRs into hash order.

   6.  Combine NSEC3 RRs with identical hashed owner names by replacing
       them with a single NSEC3 RR with the Type Bit Maps field
       consisting of the union of the types represented by the set of
       NSEC3 RRs.  If the original owner name was tracked, then
       collisions may be detected when combining, as all of the matching
       NSEC3 RRs should have the same original owner name.  Discard any
       possible temporary NSEC3 RRs.

   7.  In each NSEC3 RR, insert the next hashed owner name by using the
       value of the next NSEC3 RR in hash order.  The next hashed owner
       name of the last NSEC3 RR in the zone contains the value of the
       hashed owner name of the first NSEC3 RR in the hash order.

   8.  Finally, add an NSEC3PARAM RR with the same Hash Algorithm,
       Iterations and Salt fields to the zone apex.

   If a hash collision is detected, then a new salt has to be chosen and
   the signing process restarted.

7.2.  Zone Serving

   This specification modifies DNSSEC-enabled DNS responses generated by
   authoritative servers.  In particular, it replaces the use of NSEC
   RRs in such responses with NSEC3 RRs.

   In the following response cases, the NSEC RRs dictated by DNSSEC
   [RFC4035] are replaced with NSEC3 RRs that prove the same facts.
   Responses that would not contain NSEC RRs are unchanged by this
   specification.

   When returning responses containing multiple NSEC3 RRs, all of the
   NSEC3 RRs MUST use the same hash algorithm, iteration, and salt
   values.  The Flags field value MUST be either zero or one.




Laurie, et al.            Expires June 2, 2008                 [Page 17]

Internet-Draft                    nsec3                    November 2007


7.2.1.  Closest Encloser Proof

   For many NSEC3 responses a proof of the closest encloser is required.
   This is a proof that some ancestor of the QNAME is the closest
   encloser of QNAME.

   This proof consists of (up to) two different NSEC3 RRs:

   o  An NSEC3 RR that matches the closest (provable) encloser.

   o  An NSEC3 RR that covers the "next closer" name to the closest
      encloser.

   The first NSEC3 RR essentially proposes a possible closest encloser,
   and proves that the particular encloser does, in fact, exist.  The
   second NSEC3 RR proves that the possible closest encloser is the
   closest, and proves that QNAME (and any ancestors between QNAME and
   the closest encloser) do not exist.

   These NSEC3 RRs are collectively referred to as the "closest encloser
   proof" in the subsequent descriptions.

   For example, the closest encloser proof for the nonexistent
   "alpha.beta.gamma.example." owner name might prove that
   "gamma.example." is the closest encloser.  This response would
   contain the NSEC3 RR that matches "gamma.example.", and would also
   contain the NSEC3 RR that covers "beta.gamma.example." (which is the
   "next closer" name.)

   It is possible, when using Opt-Out (Section 6), to not be able to
   prove the actual closest encloser because it is, or is part of an
   insecure delegation covered by an Opt-Out span.  In this case,
   instead of proving the actual closest encloser, the closest provable
   encloser is used.  That is, the closest enclosing authoritative name
   is used instead.  In this case, the set of NSEC3 RRs used for this
   proof is referred to as the "closest provable encloser proof."

7.2.2.  Name Error Responses

   To prove the nonexistence of QNAME a closest encloser proof and an
   NSEC3 RR covering the (nonexistent) wildcard RR at the closest
   encloser MUST be included in the response.  This collection of (up
   to) three NSEC3 RRs proves both that QNAME does not exist and that a
   wildcard that could have matched QNAME also does not exist.

   For example, if "gamma.example." is the closest provable encloser to
   QNAME, then a NSEC3 RR covering "*.gamma.example." is included in the
   authority section of the response.



Laurie, et al.            Expires June 2, 2008                 [Page 18]

Internet-Draft                    nsec3                    November 2007


7.2.3.  No Data Responses, QTYPE is not DS

   The server MUST include the NSEC3 RR that matches QNAME.  This NSEC3
   RR MUST NOT have the bits corresponding to either the QTYPE or CNAME
   set in its Type Bit Maps field.

7.2.4.  No Data Responses, QTYPE is DS

   If there is an NSEC3 RR that matches QNAME, the server MUST return it
   in the response.  The bits corresponding with DS and CNAME MUST NOT
   be set in the Type Bit Maps field of this NSEC3 RR.

   If no NSEC3 RR matches QNAME, the server MUST return a closest
   provable encloser proof for QNAME.  The NSEC3 RR that covers the
   "next closer" name MUST have the Opt-Out bit set (note that this is
   true by definition - if the Opt-Out bit is not set, something has
   gone wrong).

   If a server is authoritative for both sides of a zone cut at QNAME,
   the server MUST return the proof from the parent side of the zone
   cut.

7.2.5.  Wildcard No Data Responses

   If there is a wildcard match for QNAME, but QTYPE is not present at
   that name, the response MUST include a closest encloser proof for
   QNAME and MUST include the NSEC3 RR that matches the wildcard.  This
   combination proves both that QNAME itself does not exist and that a
   wildcard that matches QNAME does exist.  Note that the closest
   encloser to QNAME MUST be the immediate ancestor of the wildcard RR
   (if this is not the case, then something has gone wrong).

7.2.6.  Wildcard Answer Responses

   If there is a wildcard match for QNAME and QTYPE, then, in addition
   to the expanded wildcard RRSet returned in the answer section of the
   response, proof that the wildcard match was valid must be returned.

   This proof is accomplished by proving that both QNAME does not exist,
   and that the closest encloser of the QNAME and the immediate ancestor
   of the wildcard are the same (i.e., the correct wildcard matched).

   To this end, the NSEC3 RR that covers the "next closer" name of the
   immediate ancestor of the wildcard MUST be returned.  It is not
   necessary to return an NSEC3 RR that matches the closest encloser, as
   the existence of this closest encloser is proven by the presence of
   the expanded wildcard in the response.




Laurie, et al.            Expires June 2, 2008                 [Page 19]

Internet-Draft                    nsec3                    November 2007


7.2.7.  Referrals to Unsigned Subzones

   If there is an NSEC3 RR that matches the delegation name, then that
   NSEC3 RR MUST be included in the response.  The DS bit in the type
   bit maps of the NSEC3 RR MUST NOT be set.

   If the zone is Opt-Out, then there may not be an NSEC3 RR
   corresponding to the delegation.  In this case, the closest provable
   encloser proof MUST be included in the response.  The included NSEC3
   RR that covers the "next closer" name for the delegation MUST have
   the Opt-Out flag set to one.  (Note that this will be the case unless
   something has gone wrong).

7.2.8.  Responding to Queries for NSEC3 Owner Names

   The owner names of NSEC3 RRs are not represented in the NSEC3 RR
   chain like other owner names.  As a result, each NSEC3 owner name is
   covered by another NSEC3 RR, effectively negating the existence of
   the NSEC3 RR.  This is a paradox, since the existence of an NSEC3 RR
   can be proven by its RRSIG RRSet.

   If the following conditions are all true:

   o  The QNAME equals the owner name of an existing NSEC3 RR, and

   o  No RR types exist at the QNAME, nor at any descendant of QNAME.

   Then the response MUST be constructed as a Name Error response
   (Section 7.2.2).  Or, in other words, the authoritative name server
   will act, as if the owner name of the NSEC3 RR did not exist.

   Note that NSEC3 RRs are returned as a result of an AXFR or IXFR
   query.

7.2.9.  Server Response to a Run-time Collision

   If the hash of a non-existing QNAME collides with the owner name of