[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits] [IPR]

Versions: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 RFC 5155

Network Working Group                                          B. Laurie
Internet-Draft                                                 G. Sisson
Intended status: Standards Track                               R. Arends
Expires: March 4, 2007                                           Nominet
                                                               D. Blacka
                                                          VeriSign, Inc.
                                                         August 31, 2006


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

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 March 4, 2007.

Copyright Notice

   Copyright (C) The Internet Society (2006).

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 March 4, 2007                 [Page 1]

Internet-Draft                    nsec3                      August 2006


   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  . . . . . . . . . . . . . . . . . .  6
     3.1.  RDATA fields . . . . . . . . . . . . . . . . . . . . . . .  7
       3.1.1.  Hash Algorithm . . . . . . . . . . . . . . . . . . . .  7
       3.1.2.  Opt-Out Flag . . . . . . . . . . . . . . . . . . . . .  7
       3.1.3.  Iterations . . . . . . . . . . . . . . . . . . . . . .  8
       3.1.4.  Salt Length  . . . . . . . . . . . . . . . . . . . . .  8
       3.1.5.  Salt . . . . . . . . . . . . . . . . . . . . . . . . .  8
       3.1.6.  Hash Length  . . . . . . . . . . . . . . . . . . . . .  8
       3.1.7.  Next Hashed Ownername  . . . . . . . . . . . . . . . .  8
       3.1.8.  Type Bit Maps  . . . . . . . . . . . . . . . . . . . .  8
     3.2.  NSEC3 RDATA Wire Format  . . . . . . . . . . . . . . . . .  8
       3.2.1.  Type Bit Map Encoding  . . . . . . . . . . . . . . . .  9
     3.3.  Presentation Format  . . . . . . . . . . . . . . . . . . . 10
   4.  The NSEC3-Parameters Resource Record . . . . . . . . . . . . . 11
     4.1.  RDATA fields . . . . . . . . . . . . . . . . . . . . . . . 11
       4.1.1.  Hash Algorithm . . . . . . . . . . . . . . . . . . . . 11
       4.1.2.  Opt-Out flag . . . . . . . . . . . . . . . . . . . . . 12
       4.1.3.  Iterations . . . . . . . . . . . . . . . . . . . . . . 12
       4.1.4.  Salt Length  . . . . . . . . . . . . . . . . . . . . . 12
       4.1.5.  Salt . . . . . . . . . . . . . . . . . . . . . . . . . 12
     4.2.  NSEC3PARAM RDATA Wire Format . . . . . . . . . . . . . . . 12
     4.3.  Presentation Format  . . . . . . . . . . . . . . . . . . . 12
   5.  Calculation of the Hash  . . . . . . . . . . . . . . . . . . . 13
   6.  Opt-Out  . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
   7.  Authoritative Server Considerations  . . . . . . . . . . . . . 14
     7.1.  Zone Signing . . . . . . . . . . . . . . . . . . . . . . . 15
     7.2.  Zone Serving . . . . . . . . . . . . . . . . . . . . . . . 16
       7.2.1.  Closest Encloser Proof . . . . . . . . . . . . . . . . 17
       7.2.2.  Name Error Responses . . . . . . . . . . . . . . . . . 17
       7.2.3.  No Data Responses, QTYPE is not DS . . . . . . . . . . 18
       7.2.4.  No Data Responses, QTYPE is DS . . . . . . . . . . . . 18
       7.2.5.  Wildcard No Data Responses . . . . . . . . . . . . . . 18
       7.2.6.  Wildcard Answer Responses  . . . . . . . . . . . . . . 18
       7.2.7.  Referrals to Unsigned Subzones . . . . . . . . . . . . 19
       7.2.8.  Responding to NSEC3 Queries  . . . . . . . . . . . . . 19
       7.2.9.  Server Response to a Run-time Collision  . . . . . . . 19
     7.3.  Secondary Servers  . . . . . . . . . . . . . . . . . . . . 20
     7.4.  Zones Using Unknown Hash Algorithms  . . . . . . . . . . . 20



Laurie, et al.            Expires March 4, 2007                 [Page 2]

Internet-Draft                    nsec3                      August 2006


     7.5.  Dynamic Update . . . . . . . . . . . . . . . . . . . . . . 20
   8.  Validator Considerations . . . . . . . . . . . . . . . . . . . 21
     8.1.  Responses with Unknown Hash Types  . . . . . . . . . . . . 21
     8.2.  Verifying NSEC3 RRsets . . . . . . . . . . . . . . . . . . 21
     8.3.  Closest Encloser Proof . . . . . . . . . . . . . . . . . . 22
     8.4.  Validating Name Error Responses  . . . . . . . . . . . . . 23
     8.5.  Validating No Data Responses, QTYPE is not DS  . . . . . . 23
     8.6.  Validating No Data Responses, QTYPE is DS  . . . . . . . . 23
     8.7.  Validating Wildcard No Data Responses  . . . . . . . . . . 23
     8.8.  Validating Wildcard Answer Responses . . . . . . . . . . . 23
     8.9.  Validating Referrals to Unsigned Subzones  . . . . . . . . 24
   9.  Resolver Considerations  . . . . . . . . . . . . . . . . . . . 24
     9.1.  NSEC3 Record Caching . . . . . . . . . . . . . . . . . . . 24
     9.2.  Use of the AD bit  . . . . . . . . . . . . . . . . . . . . 24
   10. Special Considerations . . . . . . . . . . . . . . . . . . . . 25
     10.1. Domain Name Length Restrictions  . . . . . . . . . . . . . 25
     10.2. Iterations . . . . . . . . . . . . . . . . . . . . . . . . 25
     10.3. Transitioning from a DNSSEC-standard Signed Zone . . . . . 26
   11. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 27
   12. Security Considerations  . . . . . . . . . . . . . . . . . . . 27
     12.1. Hashing Considerations . . . . . . . . . . . . . . . . . . 27
       12.1.1. Dictionary Attacks . . . . . . . . . . . . . . . . . . 27
       12.1.2. Collisions . . . . . . . . . . . . . . . . . . . . . . 28
       12.1.3. Using New or Unknown Hash Algorithms . . . . . . . . . 28
       12.1.4. Using High Iteration Values  . . . . . . . . . . . . . 28
     12.2. Opt-Out Considerations . . . . . . . . . . . . . . . . . . 29
     12.3. Other Considerations . . . . . . . . . . . . . . . . . . . 29
   13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30
     13.1. Normative References . . . . . . . . . . . . . . . . . . . 30
     13.2. Informative References . . . . . . . . . . . . . . . . . . 31
   Appendix A.  Example Zone  . . . . . . . . . . . . . . . . . . . . 31
   Appendix B.  Example Responses . . . . . . . . . . . . . . . . . . 35
     B.1.  Name Error . . . . . . . . . . . . . . . . . . . . . . . . 36
     B.2.  No Data Error  . . . . . . . . . . . . . . . . . . . . . . 37
       B.2.1.  No Data Error, Empty Non-Terminal  . . . . . . . . . . 38
     B.3.  Referral to an Opt-Out Unsigned Zone . . . . . . . . . . . 39
     B.4.  Wildcard Expansion . . . . . . . . . . . . . . . . . . . . 41
     B.5.  Wildcard No Data Error . . . . . . . . . . . . . . . . . . 43
     B.6.  DS Child Zone No Data Error  . . . . . . . . . . . . . . . 44
   Appendix C.  Special Considerations  . . . . . . . . . . . . . . . 45
     C.1.  Salting  . . . . . . . . . . . . . . . . . . . . . . . . . 45
     C.2.  Hash Collision . . . . . . . . . . . . . . . . . . . . . . 46
       C.2.1.  Avoiding Hash Collisions during generation . . . . . . 47
       C.2.2.  Second Preimage Requirement Analysis . . . . . . . . . 47
       C.2.3.  Possible Hash Value Truncation Method  . . . . . . . . 47
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 48
   Intellectual Property and Copyright Statements . . . . . . . . . . 50




Laurie, et al.            Expires March 4, 2007                 [Page 3]

Internet-Draft                    nsec3                      August 2006


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.

   An enumerated zone can be used either directly as a source of
   probable e-mail addresses for spam, or indirectly 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 for large delegation-centric
   zones and zones where insecure delegations will be updated rapidly.
   For these zones, the costs of maintaining the NSEC record chain may
   be extremely high relative to the gain of cryptographically
   authenticating existence of unsecured zones.

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

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 RFC 2119 [1].

1.3.  Terminology

   The reader is assumed to be familiar with the basic DNS and DNSSEC
   concepts described in RFC 1034 [2], RFC 1035 [3], RFC 4033 [4], RFC
   4034 [5], RFC 4035 [6] and subsequent RFCs that update them: RFC 2136
   [7], RFC2181 [8] and RFC2308 [9].

   The following terminology is used throughout this document:

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






Laurie, et al.            Expires March 4, 2007                 [Page 4]

Internet-Draft                    nsec3                      August 2006


   Original ownername:  the ownername corresponding to a hashed
      ownername.

   Hashed ownername:  the ownername created after applying the hash
      function to an ownername.

   Hash order:  the order in which hashed ownernames 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 RFC
      4034 [5] when the hashed ownernames are encoded using base32 with
      the chosen alphabet.

   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 subzone.

   Secure delegation:  a name containing a delegation (NS RRset), and a
      signed DS RRset, signifying a delegation to a signed subzone.

   Insecure delegation:  a name containing a delegation (NS RRset), but
      lacking a DS RRset, signifying a delegation to an unsigned
      subzone.

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

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

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

   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.

   Next Closer Name:  the name one label longer than a name's Closest
      Provable Encloser.

   Base32 encoding:  the "Base 32 Encoding with Extended Hex Alphabet"
      as specified in RFC 3548bis [14].  In this specification, the
      trailing padding characters ("=") are not used.







Laurie, et al.            Expires March 4, 2007                 [Page 5]

Internet-Draft                    nsec3                      August 2006


   To cover:  An NSEC3 record is said to "cover" a name if the hash of
      the name, or Next Closer Name, falls between the NSEC3's ownername
      and the next hashed ownername.  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 record is said to "match" a name if the NSEC3
      ownername is the same as the name's hashed ownername.


2.  Backwards Compatibility

   This specification describes a protocol change that is not generally
   backwards compatible with standard DNSSEC.  In particular, security-
   aware resolvers that are unaware of this specification (NSEC3-unaware
   resolvers) may fail to validate the changed responses dictated 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 [temporarily, 131] is an alias for the
   existing algorithm 3, DSA.  Algorithm YY [temporarily, 133] is an
   alias for the existing algorithm 5, RSASHA1.  These are not new
   algorithms, they are simply additional identifiers for the existing
   algorithms.

   Zones signed according to this specification SHOULD only use these
   algorithm identifiers for their secure entry point DNSKEY RRs (i.e.,
   DNSKEYs used as trust anchors, or represented as DS records in the
   parent zone.)  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 [6], section 5.2.

   Security aware resolvers that are aware of this specification MUST
   recognize the new algorithm identifiers and treat them as equivalent
   to the algorithms that they alias.

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


3.  The NSEC3 Resource Record

   The NSEC3 Resource Record (RR) provides authenticated denial of



Laurie, et al.            Expires March 4, 2007                 [Page 6]

Internet-Draft                    nsec3                      August 2006


   existence for DNS Resource Record Sets.

   The NSEC3 RR lists RR types present at the NSEC3 RR's original
   ownername.  It includes the next hashed ownername in the hash order
   of the zone.  The complete set of NSEC3 RRs in a zone indicates which
   RRsets exist for the original ownername of the RRset and form a chain
   of hashed ownernames in the zone.  This information is used to
   provide authenticated denial of existence for DNS data.  To provide
   protection against zone enumeration, the ownernames used in the NSEC3
   RR are cryptographic hashes of the original ownername prepended 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
   ownername.  The hashing technique is described fully in Section 5.

   Hashed ownernames of unsigned delegations may be excluded from the
   chain.  An NSEC3 record whose span covers the hash of an unsigned
   delegation's Next Closer Name is referred to as an Opt-Out NSEC3
   record and is indicated by the presence of a flag.

   The ownername for the NSEC3 RR is the base32 encoding of the hashed
   ownername prepended to the name of the zone.

   The type value for the NSEC3 RR is XX. [temporarily, 65324.]

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

   The class MUST be the same as the original ownername's class.

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

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 are defined in the NSEC3 hash algorithm registry,
   described in Section 11.

3.1.2.  Opt-Out Flag

   The Opt-Out Flag field indicates whether this NSEC3 RR may cover
   unsigned delegations.  See Section 6 for details about the use of
   this flag.



Laurie, et al.            Expires March 4, 2007                 [Page 7]

Internet-Draft                    nsec3                      August 2006


3.1.3.  Iterations

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

3.1.4.  Salt Length

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

3.1.5.  Salt

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

3.1.6.  Hash Length

   The Hash Length field defines the length of the next hashed
   ownername, ranging in value from 0 to 255 octets.

3.1.7.  Next Hashed Ownername

   The Next Hashed Ownername field contains the next hashed ownername in
   hash order, encoded as an unmodified binary value.  Given the ordered
   set of all hashed ownernames, the Next Hashed Ownername contains the
   hash of an ownername that immediately follows the ownername of the
   given NSEC3 record.  The value of the Next Hashed Ownername Field in
   the last NSEC3 record in the zone is the same as the ownername of the
   first NSEC3 RR in the zone in hash order.  Note that, unlike the
   NSEC3 ownername, 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
   NSEC3 RR's original ownername.

3.2.  NSEC3 RDATA Wire Format

   The RDATA of the NSEC3 RR is as shown below:








Laurie, et al.            Expires March 4, 2007                 [Page 8]

Internet-Draft                    nsec3                      August 2006


                        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.     |O|                Iterations                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Salt Length  |                     Salt                      /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Hash Length  |             Next Hashed Ownername             /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   /                         Type Bit Maps                         /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Hash Algorithm is single octet.

   "O" is the Opt-Out Flag field, a single bit in length.

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

   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 represents the length of the Next Hashed Ownername field
   in octets.

   Next Hashed Ownername is not encoded, unlike the NSEC3 RR's
   ownername.  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 Map Encoding

   The encoding of the Type Bit Map is the same as used by the NSEC
   record, described in RFC 4034 [5].  It is repeated 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 window block's
   bitmap, and up to 32 octets (256 bits) of bitmap.

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



Laurie, et al.            Expires March 4, 2007                 [Page 9]

Internet-Draft                    nsec3                      August 2006


   "|" denotes concatenation

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

   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 NSEC3
   RR's ownername.  If a bit is set to 0, it indicates that no RRset of
   that type is present for the NSEC3 RR's ownername.

   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 RFC 2929 [10]
   (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 each block's
   bitmap is determined by the type code with the largest numerical
   value, within that block, among the set of RR types present at the
   NSEC3 RR's actual ownername.  Trailing zero 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 presented as an unsigned decimal
      integer.  The value has a maximum of 255.

   o  The Opt-Out Flag Field is represented as an unsigned decimal
      integer.  The value is either 0 or 1.

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

   o  The Salt Length field is not presented.

   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.



Laurie, et al.            Expires March 4, 2007                [Page 10]

Internet-Draft                    nsec3                      August 2006


   o  The Hash Length field is not presented.

   o  The Next Hashed Ownername 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 RFC 3597 [11] (section 5) MUST be
      used.


4.  The NSEC3-Parameters Resource Record

   The NSEC3PARAM RR contains the NSEC3 parameters (hash algorithm,
   iterations, and salt) needed to calculate hashed ownernames.  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 records for negative responses.

   If an NSEC3PARAM RR is present at the apex of a zone, then there MUST
   be an NSEC3 using the same parameters present at every hashed
   ownername in the zone.  That is, the zone MUST contain a complete set
   of NSEC3 RRs with the same, indicated parameters.

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

   The type value for the NSEC3PARAM RR is XX. [temporarily, 65325.]

   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 record
   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.






Laurie, et al.            Expires March 4, 2007                [Page 11]

Internet-Draft                    nsec3                      August 2006


4.1.2.  Opt-Out flag

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

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 ownername 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.     |Z|                Iterations                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Salt Length  |                     Salt                      /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Hash Algorithm is a single octet.

   "Z" is a single bit, set to zero.

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

   Salt Length represents the length of the following Salt field in
   octets.  If the value is zero, the Salt field is omitted.

4.3.  Presentation Format

   The presentation format of the RDATA portion is as follows:





Laurie, et al.            Expires March 4, 2007                [Page 12]

Internet-Draft                    nsec3                      August 2006


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

   o  The zero bit field is not presented.

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

   o  The Salt Length field is not presented.

   o  The Salt field is represented as a sequence of case-insensitive
      hexadecimal digits.  Whitespace is not allowed within the
      sequences.  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 record, 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 ownername is

      IH(salt, ownername, iterations),

   where the ownername is in the canonical form.

   The canonical form of the ownername is the wire format of the
   ownername where:

   1.  The ownername 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 ownername is a wildcard name, the ownername is in its
       original unexpanded form, including the "*" label (no wildcard
       substitution);




Laurie, et al.            Expires March 4, 2007                [Page 13]

Internet-Draft                    nsec3                      August 2006


   This form is as defined in section 6.2 of RFC 4034 ([5]).


6.  Opt-Out

   In this specification, as in standard DNSSEC, 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 delegation's
   hashed ownername.  The presence of the Opt-Out flag modifies this by
   allowing insecure delegations to exist within the signed zone without
   a corresponding NSEC3 record at the delegation's hashed ownername.
   These delegations are proven insecure with a covering Opt-Out NSEC3
   record.

   An Opt-Out NSEC3 record is said to cover a delegation if the hash of
   the delegation's Next Closer Name to its closest provable encloser is
   between the NSEC3 ownername and next hashed ownername.

   An Opt-Out NSEC3 record 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 resigning records in the NSEC3 chain.  However, Opt-
   Out NSEC3 records do assert the (non)existence of other,
   authoritative RRsets.

   An Opt-Out NSEC3 record 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 type map and the signed NSEC3 record does
   assert the existence of the delegation.

   Zones using Opt-Out MAY contain a mixture of Opt-Out NSEC3 records
   and non-Opt-Out NSEC3 records.  If an NSEC3 record is not Opt-Out,
   there MUST NOT be any hashed ownernames of insecure delegations (nor
   any other records) between it and the RRsets indicated by the Next
   Hashed Ownername in the NSEC3 RDATA.  If it is Opt-Out, it MUST only
   cover hashed ownernames (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






Laurie, et al.            Expires March 4, 2007                [Page 14]

Internet-Draft                    nsec3                      August 2006


7.1.  Zone Signing

   Zones using NSEC3 must satisfy the following properties:

   o  Each ownername within the zone that owns authoritative RRsets MUST
      have a corresponding NSEC3 RR.  Ownernames that correspond to
      unsigned delegations MAY have a corresponding NSEC3 RR.  However,
      if there is not, there MUST be an Opt-Out NSEC3 RR that covers the
      Next Closer Name to the delegation.  Other non-authoritative RRs
      are not represented in the set of NSEC3 RRs.

   o  Each empty non-terminal MUST have an NSEC3 record, 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 resource record in a signed
      zone MUST indicate the presence of all types present at the
      original ownername, 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
   records.  This is not the only such possible method.

   1.  For each unique original ownername in the zone add an NSEC3
       RRset.

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

       *  The ownername of the NSEC3 RR is the hashed equivalent of the
          original owner name, prepended to the zone name.

       *  The Next Hashed Ownername 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 ownername with the NSEC3 record.

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



Laurie, et al.            Expires March 4, 2007                [Page 15]

Internet-Draft                    nsec3                      August 2006


          temporary.

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

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

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

   5.  Combine NSEC3 RRs with identical hashed ownernames by replacing
       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 ownername was tracked, then collisions may be
       detected when combining as all of the matching NSEC3 RRs should
       have the same original ownername.  Discard any possible temporary
       NSEC3s.

   6.  In each NSEC3 RR, insert the Next Hashed Ownername by using the
       value of the next NSEC3 RR in hash order.  The Next Hashed
       Ownername of the last NSEC3 in the zone contains the value of the
       hashed ownername of the first NSEC3 in the hash order.

   7.  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 MUST 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
   records in such responses with NSEC3 records.

   In the following response cases, the NSEC records dictated by the
   DNSSEC standard [6] are replaced with NSEC3 records that prove the
   same facts.  Responses that would not contain NSEC records using
   standard DNSSEC 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



Laurie, et al.            Expires March 4, 2007                [Page 16]

Internet-Draft                    nsec3                      August 2006


   values.

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 RRsets:

   o  An NSEC3 RRset that matches the closest (provable) encloser is
      included.

   o  An NSEC3 RRset that covers the Next Closer Name to the closest
      encloser is included.

   The first NSEC3 essentially proposes a possible closest encloser, and
   proves that the particular encloser does, in fact, exist.  The second
   NSEC3 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 RRsets 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." ownername might prove that
   "gamma.example." is the closest encloser.  This response would
   contain the NSEC3 record that matches the hashed ownername of
   "gamma.example.", and would also contain the NSEC3 record that covers
   the hashed ownername of "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 only part of the
   names of insecure delegations covered by Opt-Out spans.  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
   RRsets 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 RRset covering the wildcard record at the closest encloser MUST
   be included in the response.  This collection of (up to) three NSEC3
   RRsets proves both that QNAME does not exist and that a wildcard that



Laurie, et al.            Expires March 4, 2007                [Page 17]

Internet-Draft                    nsec3                      August 2006


   could have matched QNAME also does not exist.

   For example, if "gamma.example." is the proven closest encloser to
   QNAME, then an NSEC3 RRset covering the hashed ownername of
   "*.gamma.example." is included in the authority section of the
   response.

7.2.3.  No Data Responses, QTYPE is not DS

   The server MUST include the NSEC3 record that matches QNAME.  This
   NSEC3 record MUST NOT have the bit corresponding to QTYPE set in its
   Type Bit Maps field.

7.2.4.  No Data Responses, QTYPE is DS

   If there is an NSEC3 record that matches QNAME, the server MUST
   return it in the response.  The DS bit in the type map MUST NOT be
   set in this NSEC3 record.

   If no NSEC3 record matches QNAME, the server MUST return a closest
   provable encloser proof for QNAME.  The NSEC3 record 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 RRset 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
   record (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 QNAME's closest encloser and wildcard's immediate
   ancestor are the same (i.e., the correct wildcard matched).



Laurie, et al.            Expires March 4, 2007                [Page 18]

Internet-Draft                    nsec3                      August 2006


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

7.2.7.  Referrals to Unsigned Subzones

   If there is an NSEC3 that matches the delegation name, then that
   NSEC3 RRset MUST be included in the response.  The DS bit in this
   NSEC3's type map MUST NOT be set.

   If the zone in Opt-Out, then there may not be a record 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 1 (note that this will be the case unless something has gone
   wrong).

7.2.8.  Responding to NSEC3 Queries

   Since NSEC3 ownernames are not represented in the NSEC3 chain like
   other zone ownernames, direct queries for NSEC3 ownernames present a
   special case: NSEC3 ownernames cannot be proven to exist, in general.

   If the following conditions are all true:

   o  The QNAME equals an existing NSEC3 ownername, and

   o  No record types other than RRSIG or NSEC3 exist at QNAME.

   Then the response MUST be constructed as a Name Error response
   (Section 7.2.2).  Or, in other words, the authoritative nameserver
   will act, for direct query purposes, as if the NSEC3 ownername 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 an existing NSEC3
   ownername, then the server will be unable to return a response that
   proves that QNAME does not exist.  In this case, the server MUST
   return a response with an RCODE of 2 (server failure).

   Note that with the hash algorithm specified in this document, SHA-1,
   such collisions are astronomically unlikely.



Laurie, et al.            Expires March 4, 2007                [Page 19]

Internet-Draft                    nsec3                      August 2006


7.3.  Secondary Servers

   Secondary servers (and perhaps other entities) need to reliably
   determine which NSEC3 parameters (i.e., hash, salt and iterations)
   are present at every hashed ownername, in order to be able to choose
   an appropriate set of NSEC3 records for negative responses.  This is
   indicated by an NSEC3PARAM RR present at the zone apex.

   If there are multiple NSEC3PARAM RRs present, there are multiple
   valid NSEC3 chains present.  The server must choose one of them, but
   may use any criteria to do so.

7.4.  Zones Using Unknown Hash Algorithms

   Zones that are signed according to this specification, but using an
   unrecognized NSEC3 Hash Algorithm value, cannot be effectively
   served.  Such zones SHOULD be rejected when loading.  Servers SHOULD
   respond with RCODE=2 (server failure) responses when handling queries
   that would fall under such zones.

7.5.  Dynamic Update

   A zone signed using NSEC3 may accept dynamic updates.  However, NSEC3
   introduces some special considerations for dynamic updates.

   Adding and removing names in a zone MUST account for the creation or
   removal of empty non-terminals.

   o  When removing a name with a corresponding NSEC3, checks must be
      made to remove any NSEC3s corresponding with possible empty non-
      terminals created by the name.  Note that more than one name may
      be asserting the existence of a particular empty non-terminal.

   o  When adding a name that requires adding an NSEC3 RR, NSEC3s MUST
      also be added for any empty non-terminals that are created.  That
      is, if there isn't an existing NSEC3 matching a empty non-
      terminal, it must be created and added.

   The presence of Opt-Out in a zone means that some additions or
   delegations of names will not require changes to the NSEC3 records in
   a zone.

   o  When removing a delegation RRset, if that delegation does not have
      a matching NSEC3 RR, then it was opted out.  In this case, nothing
      further needs to be done.

   o  When adding a delegation RRset, if the delegation's Next Closer
      Name is covered by an existing Opt-Out NSEC3 RR, then the



Laurie, et al.            Expires March 4, 2007                [Page 20]

Internet-Draft                    nsec3                      August 2006


      delegation MAY be added without modifying the NSEC3 RRs in the
      zone.

   The presence of Opt-Out in a zone means that when adding or removing
   NSEC3 records, the value of the Opt-Out flag that should be set in
   new or modified NSEC3 records is ambiguous.  Servers SHOULD follow
   this set of basic rules to resolve the ambiguity.

   The central concept to these rules is that the state of the Opt-Out
   flag of the covering NSEC3 is preserved.

   o  When removing an NSEC3 RR, the value of the Opt-Out flag for the
      previous NSEC3 (the one whose Next Hashed Ownername is modified)
      should not be changed.

   o  When adding an NSEC3 RR, the value of the Opt-Out flag is set the
      value of the NSEC3 that previously covered the new NSEC3 RR's
      ownername.  That is, the now previous NSEC3 RR.

   If the zone in question is consistent with its use of the Opt-Out
   flag (that is, all NSEC3 RRs in the zone have the same value for the
   flag) then these rules will retain that consistency.  If the zone is
   not consistent in the use of the flag (i.e., a partially Opt-Out
   zone), then these rules will not retain the same pattern of use of
   the Opt-Out flag.

   For zones that partially use the Opt-Out flag, if there is a logical
   pattern for that use, the pattern could be maintained by using a
   local policy on the server.


8.  Validator Considerations

8.1.  Responses with Unknown Hash Types

   A validator MUST ignore NSEC3 records with unknown hash types.  The
   practical result of this is that responses containing such NSEC3
   records will generally be considered bogus.

8.2.  Verifying NSEC3 RRsets

   A validator MAY treat a response as bogus if the response contains
   NSEC3 RRs that contain different values for hash algorithm,
   iterations, or salt from each other.







Laurie, et al.            Expires March 4, 2007                [Page 21]

Internet-Draft                    nsec3                      August 2006


8.3.  Closest Encloser Proof

   In order to verify a closest encloser proof, the validator MUST find
   the longest name, X, such that

   o  X is an ancestor of QNAME that matches an NSEC3 RR present in the
      response.  This is a candidate for the closest encloser.

   o  The name one label longer than X (but still an ancestor of--or
      equal to--QNAME) is covered by an NSEC3 RR present in the
      response.

   One possible algorithm for verifying this proof is as follows:

   1.  Set SNAME=QNAME.

   2.  Check whether SNAME exists:

       *  If there is no NSEC3 RR in the response that matches SNAME
          (i.e., an NSEC3 whose ownername is the same as the hash of
          SNAME, prepended to the zone name), clear the flag.

       *  If there is an NSEC3 RR in the response that covers SNAME, set
          the flag.

       *  If there is a matching NSEC3 RR in the response and the flag
          was set, then the proof is complete, and SNAME is the closest
          encloser.

       *  If there is a matching NSEC3 RR in the response, but the flag
          is not set, then the response is bogus.

   3.  Truncate SNAME by one label, go to step 2.

   Once the closest encloser has been discovered, the validator MUST
   check that the NSEC3 that has the closest encloser as an ownername is
   from the proper zone.  The DNAME type bit must not be set and the NS
   type bit may only be set if the SOA type bit is set.  If this is not
   the case, it would be an indication that an attacker is using them to
   falsely deny the existence of records for which the server is not
   authoritative.

   In the following descriptions, the phrase "a closest (provable)
   encloser proof for X" means that the algorithm above (or an
   equivalent algorithm) proves that X does not exist by proving that an
   ancestor of X is its closest encloser.





Laurie, et al.            Expires March 4, 2007                [Page 22]

Internet-Draft                    nsec3                      August 2006


8.4.  Validating Name Error Responses

   A validator MUST verify that there is a closest encloser proof for
   QNAME present in the response and that there is an NSEC3 that covers
   the wildcard at the closest encloser (i.e., the name formed by
   prepending the asterisk label to the closest encloser.)

8.5.  Validating No Data Responses, QTYPE is not DS

   The validator MUST verify that an NSEC3 RR that matches QNAME is
   present and that the QTYPE is not set in its Type Bit Maps field.

   Note that this test also covers the case where the NSEC3 record
   exists because it corresponds to an empty non-terminal, in which case
   the NSEC3 will usually have an empty Type Bit Maps field.

8.6.  Validating No Data Responses, QTYPE is DS

   If there is an NSEC3 RR that matches QNAME present in the response,
   then that NSEC3 MUST not have the bit corresponding to DS set in its
   Type Bit Maps field.

   If there is no such NSEC3 RR, then the validator MUST verify that a
   closest provable encloser proof for QNAME is present in the response,
   and that the NSEC3 that covers the Next Closer Name has the Opt-Out
   bit set.

8.7.  Validating Wildcard No Data Responses

   The validator MUST verify a closest encloser proof for QNAME and MUST
   find an NSEC3 RR present in the response that matches the wildcard
   name generated by prepending the asterisk label to the closest
   encloser.  Furthermore, the bit corresponding to QTYPE MUST NOT be
   set in the wildcard matching NSEC3 RR (this is true by definition.)

8.8.  Validating Wildcard Answer Responses

   The verified wildcard answer RRset in the response provides the
   validator with a (candidate) closest encloser for QNAME.  This
   closest encloser is the immediate ancestor to the generating
   wildcard.

   Validators MUST verify that there is an NSEC3 that covers the Next
   Closer Name to QNAME present in the response.  This proves that QNAME
   itself did not exist and that the correct wildcard was used to
   generate the response.





Laurie, et al.            Expires March 4, 2007                [Page 23]

Internet-Draft                    nsec3                      August 2006


8.9.  Validating Referrals to Unsigned Subzones

   The delegation name in a referral is the name of the NS RRset present
   in the authority section of the referral response.

   If there is an NSEC3 RR present in the response that matches the
   delegation name, then the validator MUST ensure that the NS bit is
   set and that the DS bit is not set in the NSEC3 RR's Type Bit Maps
   field.  The validator MUST also ensure that the NSEC3 record is from
   the correct (i.e., parent) zone.  This is done by ensuring that the
   SOA bit is not set in this NSEC3 RR's Type Bit Maps field.

   Note that the presence of an NS bit implies the absence of a DNAME
   bit, so there is no need to check for the DNAME bit in the NSEC3 RR's
   Type Bit Maps field.

   If there is no NSEC3 RR present that matches the delegation name,
   then the validator MUST verify a closest provable encloser proof for
   the delegation name.  The validator MUST verify that the Opt-Out bit
   is set in the NSEC3 RR that covers the Next Closer Name to the
   delegation name.


9.  Resolver Considerations

9.1.  NSEC3 Record Caching

   Caching resolvers MUST be able to retrieve the appropriate NSEC3
   RRsets when returning responses that contain them.  In standard
   DNSSEC, in many cases it is possible to find the correct NSEC record
   to return in a response by name (e.g., when returning a referral, the
   NSEC record will always have the same ownername as the delegation.)
   With this specification, that will not be true, nor will a cache be
   able to calculate the name(s) of the appropriate NSEC3 RR(s).
   Implementations may need to use new methods for caching and
   retrieving NSEC3 resource records.

9.2.  Use of the AD bit

   The AD bit, as defined by [12] and [6], MUST NOT be set when
   returning a response containing a closest (provable) encloser proof
   in which the NSEC3 RR that covers the Next Closer Name has the Opt-
   Out bit set.

   This rule is based on what this closest encloser proof actually
   proves: names that would be covered by the Opt-Out NSEC3 RR may or
   may not exist as insecure delegations.  As such, not all the data in
   responses containing such closest encloser proofs will have been



Laurie, et al.            Expires March 4, 2007                [Page 24]

Internet-Draft                    nsec3                      August 2006


   cryptographically verified, so the AD bit cannot be set.


10.  Special Considerations

10.1.  Domain Name Length Restrictions

   Zones signed using this specification have additional domain name
   length restrictions imposed upon them.  In particular, zone with
   names that, when converted into hashed ownernames, exceed the 255
   octet length limit imposed by RFC 1035 [3].

   Zones with names that exceed this limit cannot use this
   specification.

   The actual maximum length of a domain name in a particular zone
   depends on both the length of the zone name (versus the whole domain
   name) and the particular hash function used.

10.2.  Iterations

   Setting the number of iterations used allows the zone owner to choose
   the cost of computing a hash, and so the cost of generating a
   dictionary.  Note that this is distinct from the effect of salt,
   which prevents the use of a single precomputed dictionary for all
   time.

   Obviously the number of iterations also affects the zone owner's cost
   of signing and serving the zone as well as the validator's cost of
   verifying responses from the zone.  We therefore impose an upper
   limit on the number of iterations.  We base this on the number of
   iterations that approximates the cost of verifying an RRset.

   The limits, therefore, are based on the size of the smallest zone
   signing key, rounded up to the nearest table value (or rounded down
   if the key is larger than the largest table value.)

   A zone owner MUST NOT use a value higher than shown in the table
   below for iterations for the given key size.  A resolver MAY treat a
   response with a higher value as insecure.

                       +--------------+------------+
                       | RSA Key Size | Iterations |
                       +--------------+------------+
                       | 1024         | 150        |
                       | 2048         | 500        |
                       | 4096         | 2,500      |
                       +--------------+------------+



Laurie, et al.            Expires March 4, 2007                [Page 25]

Internet-Draft                    nsec3                      August 2006


                       +--------------+------------+
                       | DSA Key Size | Iterations |
                       +--------------+------------+
                       | 1024         | 1,500      |
                       | 2048         | 5,000      |
                       +--------------+------------+

   This table is based on 150,000 SHA-1's per second, 1000 RSA
   verifications per second for 1024 bit keys, 300 verifications per
   second for 2048 bit keys, 60 verifications per second for 4096 bit
   keys, 100 DSA verifications per second for 1024 bit keys and 30
   verifications per second for 2048 bit keys.

10.3.  Transitioning from a DNSSEC-standard Signed Zone

   When transitioning an already signed and trusted zone to this
   standard, care must be taken to prevent client validation failures
   during the process.

   The basic procedure is as follows:

   1.  Transition all DNSKEYs to DNSKEYs using the algorithm aliases
       described in Section 2.  The actual method for safely and
       securely changing the zone's DNSKEYs is outside the scope of this
       specification.  However, the end result MUST be that all DS RRs
       in the parent use the specified algorithm aliases.

       After this transition is complete, all non-NSEC3-aware clients
       will treat the zone as insecure.  At this point, the
       authoritative server is still returning negative and wildcard
       responses that contain NSEC records.

   2.  Add signed NSEC3 RRsets to the zone, either incrementally or all
       at once.  If adding incrementally, then the last RRset added MUST
       be the NSEC3PARAM RRset.

   3.  After the addition of the NSEC3PARAM RRset, the server is
       switched to serving negative and wildcard responses with NSEC3
       records according to this specification.

   4.  Remove the NSEC RRsets either incrementally or all at once.

   To safely transition back to a DNSSEC-standard signed zone, simply
   reverse this procedure:

   1.  Add NSEC RRsets incrementally or all at once.





Laurie, et al.            Expires March 4, 2007                [Page 26]

Internet-Draft                    nsec3                      August 2006


   2.  Remove the NSEC3PARAM RRset.  This will signal the server to use
       the NSEC RRsets for negative and wildcard responses.

   3.  Remove the remaining NSEC3 RRsets either incrementally or all at
       once.

   4.  (Optionally) transition all of the DNSKEYs to DNSSEC-standard
       algorithm identifiers..


11.  IANA Considerations

   IANA is asked to allocate RR type codes for NSEC3 and NSEC3PARAM from
   the standard RR type space (types XXX and XXY requested).

   IANA is asked to allocate two new DNSKEY algorithm identifiers.  One
   for DSA-NSEC3, one for RSASHA1-NSEC3.

   IANA is asked to create a new registry for NSEC3 hash algorithms.
   The initial contents of this registry are:

      0 is Reserved

      1 is SHA-1.


12.  Security Considerations

12.1.  Hashing Considerations

12.1.1.  Dictionary Attacks

   The NSEC3 records are still susceptible to dictionary attacks (i.e.
   the attacker retrieves all the NSEC3 records, then calculates the
   hashes of all likely domain names, comparing against the hashes found
   in the NSEC3 records, and thus enumerating the zone).  These are
   substantially more expensive than enumerating the original NSEC
   records would have been, and in any case, such an attack could also
   be used directly against the name server itself by performing queries
   for all likely names, though this would obviously be more detectable.
   The expense of this off-line attack can be chosen by setting the
   number of iterations in the NSEC3 RR.

   Domains are also susceptible to a pre-calculated dictionary attack -
   that is, a list of hashes for all likely names is computed once, then
   NSEC3 is scanned periodically and compared against the precomputed
   hashes.  This attack is prevented by changing the salt on a regular
   basis.



Laurie, et al.            Expires March 4, 2007                [Page 27]

Internet-Draft                    nsec3                      August 2006


12.1.2.  Collisions

   Hash collisions between QNAME and NSEC3 ownernames may occur.  When
   they do, it will be impossible to prove the non-existence of the
   colliding QNAME.  However, with SHA-1, this is fantastically unlikely
   (on the order of 1 in 2^160).  Note that DNSSEC already relies on the
   presumption that a cryptographic hash function is second pre-image
   resistant, since these hash functions are used for generating and
   validating signatures and DS records.

12.1.3.  Using New or Unknown Hash Algorithms

   Since validators are instructed to ignore NSEC3 RRs with unknown hash
   algorithms, simply using a new or unknown hash algorithm directly
   will lead to validation failures with clients that understand NSEC3
   but do not understand the hash algorithm.

   To prevent this, care must be taken to shield such clients.  It is
   suggested that a similar technique to the one being used in this
   specification to shield older clients be employed (see Section 2.)

12.1.4.  Using High Iteration Values

   Since validators should treat responses containing NSEC3 records with
   high iteration values as insecure, presence of just one signed NSEC3
   record with a high iteration value in a zone provides attackers with
   a possible downgrade attack.

   The attack is simply to remove any existing NSEC3 RRs from a
   response, and replace or add a single (or multiple) NSEC3 RR that
   uses a high iterations value to the response.  Validators will then
   be forced to treat the response as insecure.  This attack would be
   effective only when all of following conditions are met:

   o  There is at least one signed NSEC3 RRset that uses a high
      iterations value present in the zone.

   o  The attacker has access to one or more of these NSEC3 RRs.  This
      is trivially true when the NSEC3 RRs with high iterations values
      are being returned in typical responses, but may also be true if
      the attacker can access the zone via AXFR or IXFR queries, or any
      other methodology.

   Using a high number of iterations also introduces an additional
   denial-of-service opportunity against servers, since servers must
   calculate several hashes per negative or wildcard response.





Laurie, et al.            Expires March 4, 2007                [Page 28]

Internet-Draft                    nsec3                      August 2006


12.2.  Opt-Out Considerations

   The Opt-Out Flag (O) allows for unsigned names, in the form of
   delegations to unsigned subzones, to exist within an otherwise signed
   zone.  All unsigned names are, by definition, insecure, and their
   validity or existence cannot be cryptographically proven.

   In general:

   o  Records with unsigned names (whether existing or not) suffer from
      the same vulnerabilities as records in an unsigned zone.  These
      vulnerabilities are described in more detail in [15] (note in
      particular sections 2.3, "Name Chaining" and 2.6, "Authenticated
      Denial of Domain Names").

   o  Records with signed names have the same security whether or not
      Opt-Out is used.

   Note that with or without Opt-Out, an insecure delegation may be
   undetectably altered by an attacker.  Because of this, the primary
   difference in security when using Opt-Out is the loss of the ability
   to prove the existence or nonexistence of an insecure delegation
   within the span of an Opt-Out NSEC3 record.

   In particular, this means that a malicious entity may be able to
   insert or delete records with unsigned names.  These records are
   normally NS records, but this also includes signed wildcard
   expansions (while the wildcard record itself is signed, its expanded
   name is an unsigned name).

   Note that being able to add a delegation is functionally equivalent
   to being able to add any record type: an attacker merely has to forge
   a delegation to nameserver under his/her control and place whatever
   records needed at the subzone apex.

   While in particular cases, this issue may not present a significant
   security problem, in general it should not be lightly dismissed.
   Therefore, it is strongly RECOMMENDED that Opt-Out be used sparingly.
   In particular, zone signing tools SHOULD NOT default to using Opt-
   Out, and MAY choose to not support Opt-Out at all.

12.3.  Other Considerations

   Walking the NSEC3 RRs will reveal the total number of records in the
   zone (plus empty non-terminals), and also what types they are.  This
   could be mitigated by adding dummy entries, but certainly an upper
   limit can always be found.




Laurie, et al.            Expires March 4, 2007                [Page 29]

Internet-Draft                    nsec3                      August 2006


13.  References

13.1.  Normative References

   [1]   Bradner, S., "Key words for use in RFCs to Indicate Requirement
         Levels", BCP 14, RFC 2119, March 1997.

   [2]   Mockapetris, P., "Domain names - concepts and facilities",
         STD 13, RFC 1034, November 1987.

   [3]   Mockapetris, P., "Domain names - implementation and
         specification", STD 13, RFC 1035, November 1987.

   [4]   Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose,
         "DNS Security Introduction and Requirements", RFC 4033,
         March 2005.

   [5]   Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose,
         "Resource Records for the DNS Security Extensions", RFC 4034,
         March 2005.

   [6]   Arends, R., Austein, R., Larson, M., Massey, D., and S. Rose,
         "Protocol Modifications for the DNS Security Extensions",
         RFC 4035, March 2005.

   [7]   Vixie, P., Thomson, S., Rekhter, Y., and J. Bound, "Dynamic
         Updates in the Domain Name System (DNS UPDATE)", RFC 2136,
         April 1997.

   [8]   Elz, R. and R. Bush, "Clarifications to the DNS Specification",
         RFC 2181, July 1997.

   [9]   Andrews, M., "Negative Caching of DNS Queries (DNS NCACHE)",
         RFC 2308, March 1998.

   [10]  Eastlake, D., Brunner-Williams, E., and B. Manning, "Domain
         Name System (DNS) IANA Considerations", BCP 42, RFC 2929,
         September 2000.

   [11]  Gustafsson, A., "Handling of Unknown DNS Resource Record (RR)
         Types", RFC 3597, September 2003.

   [12]  Wellington, B. and O. Gudmundsson, "Redefinition of DNS
         Authenticated Data (AD) bit", RFC 3655, November 2003.







Laurie, et al.            Expires March 4, 2007                [Page 30]

Internet-Draft                    nsec3                      August 2006


13.2.  Informative References

   [13]  Lewis, E., "The Role of Wildcards in the Domain Name System",
         RFC 4592, July 2006.

   [14]  Josefsson, Ed., S,., "The Base16, Base32, and Base64 Data
         Encodings.", draft-josefsson-rfc3548bis-00 (work in progress),
         October 2005.

   [15]  Atkins, D. and R. Austein, "Threat Analysis of the Domain Name
         System (DNS)", RFC 3833, August 2004.


Appendix A.  Example Zone

   This is a zone showing its NSEC3 records.  They can also be used as
   test vectors for the hash algorithm.

   The overall TTL and class are specified in the SOA record, and are
   subsequently omitted for clarity.

   example. 3600  IN SOA  ns1.example. bugs.x.w.example. 1 3600 300 (
                          3600000 3600 )
                  RRSIG   SOA 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          hNIkW1xzn+c+9P3W7PUVVptI72xEmOtn+eqQ
                          ux0BE7Pfc6ikx4m7ivOVWETjbwHjqfY0X5G+
                          rynLZNqsbLm40Q== )
                  NS      ns1.example.
                  NS      ns2.example.
                  RRSIG   NS 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          D9+iBwcbeKL5+TorTfYn4/pLr2lSFwyGYCyM
                          gfq4TpFaZpxrCJPLxHbKjdkR18jAt7+SR7B5
                          JpiZcff2Cj2B0w== )
                  MX      1 xx.example.
                  RRSIG   MX 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          jsGuTpXTTrZHzUKnViUpJ8YyGNpDd6n/sy2g
                          HnSC0nj2jPxTC5VENLo3GxSpCSA5DlAz57p+
                          RllUJk3DWktkjw== )
                  DNSKEY  256 3 133 (
                          AQO0gEmbZUL6xbD/xQczHbnwYnf+jQjwz/sU
                          5k44rHTt0Ty+3aOdYoome9TjGMhwkkGby1TL
                          ExXT48OGGdbfIme5 )
                  DNSKEY  257 3 133 (
                          AQOnsGyJvywVjYmiLbh0EwIRuWYcDiB/8blX
                          cpkoxtpe19Oicv6Zko+8brVsTMeMOpcUeGB1



Laurie, et al.            Expires March 4, 2007                [Page 31]

Internet-Draft                    nsec3                      August 2006


                          zsYKWJ7BvR2894hX )
                  RRSIG   DNSKEY 133 1 3600 20150420235959 (
                          20051021000000 22088 example.
                          Xpo9ptByXb8M1JR1i0KuRmKGc/YeOLcc6Ptn
                          RJOx6ADLSL2mU6AYX5tAJRMTKTXk6waLIaxu
                          liqUBOkCjLUZMw== )
                  NSEC3PARAM 1 12 aabbccdd
                  RRSIG   NSEC3PARAM 133 1 3600 20150420235959 (
                          20051021000000 62827 example.
                          LIDOPjIUc2DtDpXUlOaLnJkHKbacDvXZlhRm
                          g4eFGnaEd794HnjRjeT9w5QwtLDpLyyMRbGt
                          4L0XlqhGJCcAsA== )
   0p9mhaveqvm6t7vbl5lop2u3t2rp3tom.example. NSEC3 1 1 12 aabbccdd (
                          2t7b4g4vsa5smi47k61mv5bv1a22bojr MX DNSKEY NS
                          SOA NSEC3PARAM RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          KrvAod6q0ad1+b3A7eesmBgyOSscU9ueuCw1
                          ZWC4MfTTe07vW3plBQheG4ma3mlCBU2uMG2x
                          110CS+ExlJoLdg== )
   2t7b4g4vsa5smi47k61mv5bv1a22bojr.example. A 127.0.0.1
                  RRSIG   A 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          Enu4zogLLDz0p/lLcuH3+jpfuWR/Uyw4fyvg
                          lsaFNvFfs7t+f5TPEt5GLX4U2eRycWmF9ZpY
                          McPgqAgrGZJ+jA== )
                  NSEC3   1 1 12 aabbccdd (
                          2vptu5timamqttgl4luu9kg21e0aor3s A RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          RCRMm8uYt8w//29S2Stmz481ECI4bjDuBg4R
                          kTM+/PTwu0W1JjGT+6kW5wzCrZ1CrpG52ROV
                          vqQ/wFCbUVlbUg== )
   2vptu5timamqttgl4luu9kg21e0aor3s.example. NSEC3 1 1 12 aabbccdd (
                          35mthgpgcu1qg68fab165klnsnk3dpvl MX RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          bkC87IljDVMn/dmqEXDMq/HD70r51j/of/Pw
                          lWTNU8HIw5nznDOJlbgI5UVvBfalR4Xt6NI4
                          VKNzDskFhHxxZA== )
   35mthgpgcu1qg68fab165klnsnk3dpvl.example. NSEC3 1 1 12 aabbccdd (
                          b4um86eghhds6nea196smvmlo4ors995 NS DS RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          tGRegqaWwRH2J/KlexKiwCYgvUV8kCOvm2Mq
                          roGWY2jfE4aMq7HKLd7YDuYYjSUpi30x3d2G
                          rBD4Lv8czVE/YQ== )
   a.example.     NS      ns1.a.example.



Laurie, et al.            Expires March 4, 2007                [Page 32]

Internet-Draft                    nsec3                      August 2006


                  NS      ns2.a.example.
                  DS      58470 5 1 (
                          3079F1593EBAD6DC121E202A8B766A6A4837206C )
                  RRSIG   DS 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          qxw4j5LNe70UDu121YqAaqQjyjYbdKNd/4bE
                          nH0kjQswuiGs9EuArCBhcWocWQDBku+A4HMH
                          JdLqJr5p4JctLg== )
   ns1.a.example. A       192.168.2.5
   ns2.a.example. A       192.168.2.6
   ai.example.    A       192.168.2.9
                  RRSIG   A 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          ZaXcOIABcqe1UbwBrisSfk1EBZN11ccgg81Z
                          vZ4qVRhQRdMTprjO9boMYL3q7nz993IqSyUg
                          jumoQ8qs1isY4Q== )
                  HINFO   "KLH-10" "ITS"
                  RRSIG   HINFO 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          BuDv+No06VEcIsEnvBdjdKm6kxQGrhOgKEKb
                          Gsb8DJRjY7Lia+YG2//s6OlOIfxPmLlLiYpA
                          i3q2sEjTJhocGQ== )
                  AAAA    2001:db8:0:0:0:0:f00:baa9
                  RRSIG   AAAA 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          m65zc0A16Xbx3jYb0t5vPwMzE2xS15mKh76M
                          hSuKfiFVhBFcQ9IilEM0pXnLzt3ozrM/3X0x
                          2ruyuN0zC+PABA== )
   b4um86eghhds6nea196smvmlo4ors995.example. NSEC3 1 1 12 aabbccdd (
                          gjeqe526plbf1g8mklp59enfd789njgi MX RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          qiW7xFGksrzOCrQvupZGXqw605PhTR7uy+KD
                          l4N9N/cvPwd9BBP12xxi6j2fE5rXJbg0m7em
                          ZLFajlX4ZPGq+A== )
   c.example.     NS      ns1.c.example.
                  NS      ns2.c.example.
   ns1.c.example. A       192.168.2.7
   ns2.c.example. A       192.168.2.8
   gjeqe526plbf1g8mklp59enfd789njgi.example. NSEC3 1 1 12 aabbccdd (
                          ji6neoaepv8b5o6k4ev33abha8ht9fgc HINFO A AAAA
                          RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          RZOm6sXo7D+/MiqeEQbOhpnJ9dhDnlInRVtn
                          U1lik4bO2fcVUJbTkQMMxBPn6/3PjZJe9eM1
                          MRRP/n+zYR+TBw== )
   ji6neoaepv8b5o6k4ev33abha8ht9fgc.example. NSEC3 1 1 12 aabbccdd (



Laurie, et al.            Expires March 4, 2007                [Page 33]

Internet-Draft                    nsec3                      August 2006


                          k8udemvp1j2f7eg6jebps17vp3n8i58h )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          a1jTDAzoahRgH/A5px0HTZudLiJggWOxYTa4
                          rzJg9jC2yvCiwpg3A6u9W0tDo4wkn7apkPmy
                          sbeZp4krdyVIHA== )
   k8udemvp1j2f7eg6jebps17vp3n8i58h.example. NSEC3 1 1 12 aabbccdd (
                          kohar7mbb8dc2ce8a9qvl8hon4k53uhi )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          mwkY31Hz4JgwTfaAqspc4SxBcgJGeVV9vXp3
                          f+wHsndgxoszkT6Ms/pgQlvVTg0JS6fRLpBq
                          TxLGCwQoBf7Yxw== )
   kohar7mbb8dc2ce8a9qvl8hon4k53uhi.example. NSEC3 1 1 12 aabbccdd (
                          q04jkcevqvmu85r014c7dkba38o0ji5r A RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          ChF2Ix5EksiTePcT57TIGGYKloqyF3eravfP
                          MxO++M0n62L8UdKMhf5Y8Kv6Q/g2e4Aj515L
                          LCwaF/XuGciQfA== )
   ns1.example.   A       192.168.2.1
                  RRSIG   A 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          KS4zeGDaXO99zFfZdkH8BPj5Mm2r9NdxrW5h
                          cwZbIngiTAlE0DcVVBNY8b0h2DZL2znQr8QJ
                          0/QDt8ufz6tZyg== )
   ns2.example.   A       192.168.2.2
                  RRSIG   A 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          Hc6i5zNssmqTB7zhORrMT9uvhLdQ9c3DPjuq
                          Ujw/UOw4xJIMjhG4qDwQRav4XpyI2mvVJFR1
                          1M07gNwzYG2Ypw== )
   q04jkcevqvmu85r014c7dkba38o0ji5r.example. NSEC3 1 1 12 aabbccdd (
                          r53bq7cc2uvmubfu5ocmm6pers9tk9en A RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          IIPqK4CDzRoQjCjXdw2vKtYmPnjrXcn/BaaA
                          nBB16kUBcSjySMkMu61E/ICZAqrQhOvkYyh7
                          iMABhMPHoGX21Q== )
   r53bq7cc2uvmubfu5ocmm6pers9tk9en.example. NSEC3 1 1 12 aabbccdd (
                          t644ebqk9bibcna874givr6joj62mlhv MX RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          nE3K1uASbFS235wgvWKlY2UJAVVS7dBU2HzO
                          8BuFArTrZdTYH5iWOjw1LrwS13Fl52ABBYzu
                          ag1i9RXlMl2Glg== )
   t644ebqk9bibcna874givr6joj62mlhv.example. NSEC3 1 1 12 aabbccdd (
                          0p9mhaveqvm6t7vbl5lop2u3t2rp3tom HINFO A AAAA



Laurie, et al.            Expires March 4, 2007                [Page 34]

Internet-Draft                    nsec3                      August 2006


                          RRSIG )
                  RRSIG   NSEC3 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          JOdpBM7/458W7wP+5G2IPTpD9XduIqzjuX4U
                          G1xGxja9ciKRbaeBVP93o3Z5j66eZqAbAEym
                          7f5Vg9IgvnhrEg== )
   *.w.example.   MX      1 ai.example.
                  RRSIG   MX 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          DnT0Y6dRBM8f3v8HdKmZUsGVkXh+b+htujCR
                          c423x6c8erEMGVnxcrmcrZ53qGXcMYJ+TDkq
                          a7Xfz/f9xzvSTw== )
   x.w.example.   MX      1 xx.example.
                  RRSIG   MX 133 3 3600 20150420235959 20051021000000 (
                          62827 example.
                          BLSDMos8kYR7+2U7iwwdqdhU82hzq0s57xtw
                          F08tWU/d19jrNO6LdWfBL/FJ8zL8ZpEjhh6b
                          8cj0f5yQOUyShw== )
   x.y.w.example. MX      1 xx.example.
                  RRSIG   MX 133 4 3600 20150420235959 20051021000000 (
                          62827 example.
                          GPzELyUCxrnyep8uMcqthUXjTqYBmgeaveb9
                          2vQgzUyPLLamNN/YqMHr6tGQNxeMAhclxUSQ
                          eoCggUBVhFfB1Q== )
   xx.example.    A       192.168.2.10
                  RRSIG   A 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          qxwCQAqdWxq4bDNPKyOVG679cSJwKVv/Q5Rj
                          9WKymDOhOPTmEs8xDxbiM4EXyv0ig50I3Wvb
                          kmyw4sQ5CspOcA== )
                  HINFO   "KLH-10" "TOPS-20"
                  RRSIG   HINFO 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          YJFwmD0By0NpGEvO1nE1ZTH10XrmpKnVuAEI
                          cAxLLHyPs3qyGQdDEG7sQX5+PfiOGZrNmZef
                          8NgQhW8kGEgN1Q== )
                  AAAA    2001:db8:0:0:0:0:f00:baaa
                  RRSIG   AAAA 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          VAJBlXoTOScrIM6yPlDsd9o05v39qIzFnemR
                          2vgw1s4l8maJVWi9IHEg8oiypJvGwSCP1nFs
                          EOlXyNFQJ0fWGA== )


Appendix B.  Example Responses

   The examples in this section show response messages using the signed
   zone example in Appendix A.



Laurie, et al.            Expires March 4, 2007                [Page 35]

Internet-Draft                    nsec3                      August 2006


B.1.  Name Error

   An authoritative name error.  The NSEC3 RRs prove that the name does
   not exist and that there is no wildcard RR that should have been
   expanded.

   ;; Header: QR AA DO RCODE=3
   ;;
   ;; Question
   a.c.x.w.example.         IN A

   ;; Answer
   ;; (empty)

   ;; Authority

   example.       SOA     ns1.example. bugs.x.w.example. 1 3600 300 (
                          3600000 3600 )
   example.       RRSIG   SOA 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          hNIkW1xzn+c+9P3W7PUVVptI72xEmOtn+eqQ
                          ux0BE7Pfc6ikx4m7ivOVWETjbwHjqfY0X5G+
                          rynLZNqsbLm40Q== )

   ;; NSEC3 that covers the Next Closer Name (c.x.w.example)
   ;; H(c.x.w.example) = 0va5bpr2ou0vk0lbqeeljri88laipsfh

   0p9mhaveqvm6t7vbl5lop2u3t2rp3tom.example. NSEC3 1 1 12 aabbccdd (
                          2t7b4g4vsa5smi47k61mv5bv1a22bojr MX DNSKEY NS
                          SOA NSEC3PARAM RRSIG )
   0p9mhaveqvm6t7vbl5lop2u3t2rp3tom.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          KrvAod6q0ad1+b3A7eesmBgyOSscU9ueuCw1
                          ZWC4MfTTe07vW3plBQheG4ma3mlCBU2uMG2x
                          110CS+ExlJoLdg== )

   ;; NSEC3 that matches the Closest Encloser (x.w.example)
   ;; H(x.w.example) = b4um86eghhds6nea196smvmlo4ors995

   b4um86eghhds6nea196smvmlo4ors995.example. NSEC3 1 1 12 aabbccdd (
                          gjeqe526plbf1g8mklp59enfd789njgi MX RRSIG )
   b4um86eghhds6nea196smvmlo4ors995.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          qiW7xFGksrzOCrQvupZGXqw605PhTR7uy+KD
                          l4N9N/cvPwd9BBP12xxi6j2fE5rXJbg0m7em
                          ZLFajlX4ZPGq+A== )

   ;; NSEC3 that covers wildcard at the Closest Encloser (*.x.w.example)



Laurie, et al.            Expires March 4, 2007                [Page 36]

Internet-Draft                    nsec3                      August 2006


   ;; H(*.x.w.example) = 92pqneegtaue7pjatc3l3qnk738c6v5m

   35mthgpgcu1qg68fab165klnsnk3dpvl.example. NSEC3 1 1 12 aabbccdd (
                          b4um86eghhds6nea196smvmlo4ors995 NS DS RRSIG )
   35mthgpgcu1qg68fab165klnsnk3dpvl.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          tGRegqaWwRH2J/KlexKiwCYgvUV8kCOvm2Mq
                          roGWY2jfE4aMq7HKLd7YDuYYjSUpi30x3d2G
                          rBD4Lv8czVE/YQ== )

   ;; Additional
   ;; (empty)

   The query returned three NSEC3 RRs that prove that the requested data
   does not exist and that no wildcard expansion applies.  The negative
   response is authenticated by verifying the NSEC3 RRs.  The
   corresponding RRSIGs indicate that the NSEC3s are signed by an
   "example" DNSKEY of algorithm 133 and with key tag 62827.  The
   resolver needs the corresponding DNSKEY RR in order to authenticate
   this answer.  One of the owner names of the NSEC3 RRs matches the
   closest encloser.  One of the NSEC3 RRs prove that there exists no
   longer name.  One of the NSEC3 RRs prove that there exists no
   wildcard RRsets that should have been expanded.  The closest encloser
   can be found by applying the algorithm in section Section 8.3

   In the above example, the name 'x.w.example' hashes to
   'b4um86eghhds6nea196smvmlo4ors995'.  This indicates that this might
   be the closest encloser.  To prove that 'c.x.w.example' and
   '*.x.w.example' do not exists, these names are hashed to respectively
   '0va5bpr2ou0vk0lbqeeljri88laipsfh' and
   '92pqneegtaue7pjatc3l3qnk738c6v5m'.  The first and last NSEC3 records
   prove that these hashed ownernames do not exists.

B.2.  No Data Error

   A "no data" response.  The NSEC3 RR proves that the name exists and
   that the requested RR type does not.














Laurie, et al.            Expires March 4, 2007                [Page 37]

Internet-Draft                    nsec3                      August 2006


   ;; Header: QR AA DO RCODE=0
   ;;
   ;; Question
   ns1.example.        IN MX

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       SOA     ns1.example. bugs.x.w.example. 1 3600 300 (
                          3600000 3600 )
   example.       RRSIG   SOA 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          hNIkW1xzn+c+9P3W7PUVVptI72xEmOtn+eqQ
                          ux0BE7Pfc6ikx4m7ivOVWETjbwHjqfY0X5G+
                          rynLZNqsbLm40Q== )

   ;; NSEC3 matches the QNAME and shows that the MX type bit is not set.

   2t7b4g4vsa5smi47k61mv5bv1a22bojr.example. NSEC3 1 1 12 aabbccdd (
                          2vptu5timamqttgl4luu9kg21e0aor3s A RRSIG )
   2t7b4g4vsa5smi47k61mv5bv1a22bojr.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          RCRMm8uYt8w//29S2Stmz481ECI4bjDuBg4R
                          kTM+/PTwu0W1JjGT+6kW5wzCrZ1CrpG52ROV
                          vqQ/wFCbUVlbUg== )

   ;; Additional
   ;; (empty)

   The query returned an NSEC3 RR that proves that the requested name
   exists ("ns1.example." hashes to "2t7b4g4vsa5smi47k61mv5bv1a22bojr"),
   but the requested RR type does not exist (type MX is absent in the
   type code list of the NSEC3 RR).

B.2.1.  No Data Error, Empty Non-Terminal

   A "no data" response because of an empty non-terminal.  The NSEC3 RR
   proves that the name exists and that the requested RR type does not.












Laurie, et al.            Expires March 4, 2007                [Page 38]

Internet-Draft                    nsec3                      August 2006


   ;; Header: QR AA DO RCODE=0
   ;;
   ;; Question
   y.w.example.        IN A

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       SOA     ns1.example. bugs.x.w.example. 1 3600 300 (
                          3600000 3600 )
   example.       RRSIG   SOA 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          hNIkW1xzn+c+9P3W7PUVVptI72xEmOtn+eqQ
                          ux0BE7Pfc6ikx4m7ivOVWETjbwHjqfY0X5G+
                          rynLZNqsbLm40Q== )

   ;; NSEC3 matches the QNAME and shows that the A type bit is not set.

   ji6neoaepv8b5o6k4ev33abha8ht9fgc.example. NSEC3 1 1 12 aabbccdd (
                          k8udemvp1j2f7eg6jebps17vp3n8i58h )
   ji6neoaepv8b5o6k4ev33abha8ht9fgc.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          a1jTDAzoahRgH/A5px0HTZudLiJggWOxYTa4
                          rzJg9jC2yvCiwpg3A6u9W0tDo4wkn7apkPmy
                          sbeZp4krdyVIHA== )

   ;; Additional
   ;; (empty)


   The query returned an NSEC3 RR that proves that the requested name
   exists ("y.w.example." hashes to "ji6neoaepv8b5o6k4ev33abha8ht9fgc"),
   but the requested RR type does not exist (Type A is absent in the
   type-bit-maps of the NSEC3 RR).  Note that, unlike empty non terminal
   proof using NSECs, this is identical to a No Data Error.  This
   example is solely mentioned to be complete.

B.3.  Referral to an Opt-Out Unsigned Zone

   The NSEC3 RR prove that nothing for this delegation was signed.
   There is no proof that the unsigned delegation exists









Laurie, et al.            Expires March 4, 2007                [Page 39]

Internet-Draft                    nsec3                      August 2006


   ;; Header: QR DO RCODE=0
   ;;
   ;; Question
   mc.c.example.       IN MX

   ;; Answer
   ;; (empty)

   ;; Authority
   c.example.     NS      ns1.c.example.
                  NS      ns2.c.example.

   ;; NSEC3 that covers the Next Closer Name (c.example)
   ;; H(c.example) = 4g6p9u5gvfshp30pqecj98b3maqbn1ck

   35mthgpgcu1qg68fab165klnsnk3dpvl.example. NSEC3 1 1 12 aabbccdd (
                          b4um86eghhds6nea196smvmlo4ors995 NS DS RRSIG )
   35mthgpgcu1qg68fab165klnsnk3dpvl.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          tGRegqaWwRH2J/KlexKiwCYgvUV8kCOvm2Mq
                          roGWY2jfE4aMq7HKLd7YDuYYjSUpi30x3d2G
                          rBD4Lv8czVE/YQ== )

   ;; NSEC3 that matches the Closest Encloser (example)
   ;; H(example) = 0p9mhaveqvm6t7vbl5lop2u3t2rp3tom

   0p9mhaveqvm6t7vbl5lop2u3t2rp3tom.example. NSEC3 1 1 12 aabbccdd (
                          2t7b4g4vsa5smi47k61mv5bv1a22bojr MX DNSKEY NS
                          SOA NSEC3PARAM RRSIG )
   0p9mhaveqvm6t7vbl5lop2u3t2rp3tom.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          KrvAod6q0ad1+b3A7eesmBgyOSscU9ueuCw1
                          ZWC4MfTTe07vW3plBQheG4ma3mlCBU2uMG2x
                          110CS+ExlJoLdg== )

   ;; Additional
   ns1.c.example. A       192.168.2.7
   ns2.c.example. A       192.168.2.8


   The query returned a referral to the unsigned "c.example." zone.  The
   response contains the Closest Provable Encloser of "c.example" to be
   "example", since the hash of "c.example"
   ("4g6p9u5gvfshp30pqecj98b3maqbn1ck") is covered by the first NSEC3
   record and its Opt-Out bit is set.






Laurie, et al.            Expires March 4, 2007                [Page 40]

Internet-Draft                    nsec3                      August 2006


B.4.  Wildcard Expansion

   A query that was answered with a response containing a wildcard
   expansion.  The label count in the answer's RRSIG RR indicates that a
   wildcard RRset was expanded to produce this response, and the NSEC3
   RR proves that no Next Closer Name exists in the zone.













































Laurie, et al.            Expires March 4, 2007                [Page 41]

Internet-Draft                    nsec3                      August 2006


   ;; Header: QR AA DO RCODE=0
   ;;
   ;; Question
   a.z.w.example. IN MX

   ;; Answer
   a.z.w.example. MX      1 ai.example.
   a.z.w.example. RRSIG   MX 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          DnT0Y6dRBM8f3v8HdKmZUsGVkXh+b+htujCR
                          c423x6c8erEMGVnxcrmcrZ53qGXcMYJ+TDkq
                          a7Xfz/f9xzvSTw== )

   ;; Authority
   example.       NS      ns1.example.
   example.       NS      ns2.example.
   example.       RRSIG   NS 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          D9+iBwcbeKL5+TorTfYn4/pLr2lSFwyGYCyM
                          gfq4TpFaZpxrCJPLxHbKjdkR18jAt7+SR7B5
                          JpiZcff2Cj2B0w== )

   ;; NSEC3 that covers the Next Closer Name (z.w.example)
   ;; H(z.w.example) = qlu7gtfaeh0ek0c05ksfhdpbcgglbe03

   q04jkcevqvmu85r014c7dkba38o0ji5r.example. NSEC3 1 1 12 aabbccdd (
                          r53bq7cc2uvmubfu5ocmm6pers9tk9en A RRSIG )
   q04jkcevqvmu85r014c7dkba38o0ji5r.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          IIPqK4CDzRoQjCjXdw2vKtYmPnjrXcn/BaaA
                          nBB16kUBcSjySMkMu61E/ICZAqrQhOvkYyh7
                          iMABhMPHoGX21Q== )

   ;; Additional
   ai.example.    A       192.168.2.9
   ai.example.    RRSIG   A 133 2 3600 20150420235959 20051021000000 (
                          62827 example.
                          ZaXcOIABcqe1UbwBrisSfk1EBZN11ccgg81Z
                          vZ4qVRhQRdMTprjO9boMYL3q7nz993IqSyUg
                          jumoQ8qs1isY4Q== )
   ai.example.    AAAA    2001:db8:0:0:0:0:f00:baa9
   ai.example.    RRSIG   AAAA 133 2 3600 20150420235959 (
                          20051021000000 62827 example.
                          m65zc0A16Xbx3jYb0t5vPwMzE2xS15mKh76M
                          hSuKfiFVhBFcQ9IilEM0pXnLzt3ozrM/3X0x
                          2ruyuN0zC+PABA== )





Laurie, et al.            Expires March 4, 2007                [Page 42]

Internet-Draft                    nsec3                      August 2006


   The query returned an answer that was produced as a result of
   wildcard expansion.  The answer section contains a wildcard RRset
   expanded as it would be in a traditional DNS response.  The RRSIG
   labels field value of 2 indicates that the answer is the result of
   wildcard expansion, as the "a.z.w.example" name contains 4 labels.
   This also shows that "w.example" exists, so there is no need for an
   NSEC3 that matches the Closest Encloser.

   The NSEC3 proves that no closer match could have been used to answer
   this query.

B.5.  Wildcard No Data Error

   A "no data" response for a name covered by a wildcard.  The NSEC3 RRs
   prove that the matching wildcard name does not have any RRs of the
   requested type and that no closer match exists in the zone.

   ;; Header: QR AA DO RCODE=0
   ;;
   ;; Question
   a.z.w.example.      IN AAAA

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       SOA     ns1.example. bugs.x.w.example. 1 3600 300 (
                          3600000 3600 )
   example.       RRSIG   SOA 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          hNIkW1xzn+c+9P3W7PUVVptI72xEmOtn+eqQ
                          ux0BE7Pfc6ikx4m7ivOVWETjbwHjqfY0X5G+
                          rynLZNqsbLm40Q== )

   ;; NSEC3 that matches the Closest Encloser (w.example)
   ;; H(w.example) = k8udemvp1j2f7eg6jebps17vp3n8i58h

   k8udemvp1j2f7eg6jebps17vp3n8i58h.example. NSEC3 1 1 12 aabbccdd (
                          kohar7mbb8dc2ce8a9qvl8hon4k53uhi )
   k8udemvp1j2f7eg6jebps17vp3n8i58h.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          mwkY31Hz4JgwTfaAqspc4SxBcgJGeVV9vXp3
                          f+wHsndgxoszkT6Ms/pgQlvVTg0JS6fRLpBq
                          TxLGCwQoBf7Yxw== )

   ;; NSEC3 that covers the Next Closer Name (z.w.example)
   ;; H(z.w.example) = qlu7gtfaeh0ek0c05ksfhdpbcgglbe03




Laurie, et al.            Expires March 4, 2007                [Page 43]

Internet-Draft                    nsec3                      August 2006


   q04jkcevqvmu85r014c7dkba38o0ji5r.example. NSEC3 1 1 12 aabbccdd (
                          r53bq7cc2uvmubfu5ocmm6pers9tk9en A RRSIG )
   q04jkcevqvmu85r014c7dkba38o0ji5r.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          IIPqK4CDzRoQjCjXdw2vKtYmPnjrXcn/BaaA
                          nBB16kUBcSjySMkMu61E/ICZAqrQhOvkYyh7
                          iMABhMPHoGX21Q== )

   ;; NSEC3 that matches a wildcard at the Closest Encloser.
   ;; H(*.w.example) = r53bq7cc2uvmubfu5ocmm6pers9tk9en

   r53bq7cc2uvmubfu5ocmm6pers9tk9en.example. NSEC3 1 1 12 aabbccdd (
                          t644ebqk9bibcna874givr6joj62mlhv MX RRSIG )
   r53bq7cc2uvmubfu5ocmm6pers9tk9en.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          nE3K1uASbFS235wgvWKlY2UJAVVS7dBU2HzO
                          8BuFArTrZdTYH5iWOjw1LrwS13Fl52ABBYzu
                          ag1i9RXlMl2Glg== )

   ;; Additional
   ;; (empty)

   The query returned NSEC3 RRs that prove that the requested data does
   not exist and no wildcard RR applies.

B.6.  DS Child Zone No Data Error

   A "no data" response for a QTYPE=DS query that was mistakenly sent to
   a name server for the child zone.






















Laurie, et al.            Expires March 4, 2007                [Page 44]

Internet-Draft                    nsec3                      August 2006


   ;; Header: QR AA DO RCODE=0
   ;;
   ;; Question
   example.            IN DS

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       SOA     ns1.example. bugs.x.w.example. 1 3600 300 (
                          3600000 3600 )
   example.       RRSIG   SOA 133 1 3600 20150420235959 20051021000000 (
                          62827 example.
                          hNIkW1xzn+c+9P3W7PUVVptI72xEmOtn+eqQ
                          ux0BE7Pfc6ikx4m7ivOVWETjbwHjqfY0X5G+
                          rynLZNqsbLm40Q== )

   ;; NSEC3 matches the QNAME and shows that the DS type bit is not set.

   0p9mhaveqvm6t7vbl5lop2u3t2rp3tom.example. NSEC3 1 1 12 aabbccdd (
                          2t7b4g4vsa5smi47k61mv5bv1a22bojr MX DNSKEY NS
                          SOA NSEC3PARAM RRSIG )
   0p9mhaveqvm6t7vbl5lop2u3t2rp3tom.example. RRSIG NSEC3 133 2 3600 (
                          20150420235959 20051021000000 62827 example.
                          KrvAod6q0ad1+b3A7eesmBgyOSscU9ueuCw1
                          ZWC4MfTTe07vW3plBQheG4ma3mlCBU2uMG2x
                          110CS+ExlJoLdg== )

   ;; Additional
   ;; (empty)

   The query returned an NSEC3 RR that show that the requested was
   answered by the server authoritative for the zone "example".  The
   NSEC3 RR indicates the presence of an SOA RR, showing that this NSEC3
   is from the apex of the child, not from the zone cut of the parent.
   Queries for the "example" DS RRset should be sent to the parent
   servers (which are in this case the root servers).


Appendix C.  Special Considerations

   The following paragraphs clarify specific behavior and explain
   special considerations for implementations.

C.1.  Salting

   Augmenting original ownernames with salt before hashing increases the
   cost of a dictionary of pre-generated hash-values.  For every bit of



Laurie, et al.            Expires March 4, 2007                [Page 45]

Internet-Draft                    nsec3                      August 2006


   salt, the cost of a precomputed dictionary doubles (because there
   must be an entry for each word combined with each possible salt
   value).  The NSEC3 RR can use a maximum of 2040 bits (255 octets) of
   salt, multiplying the cost by 2^2040.  This means that an attacker
   must, in practice, recompute the dictionary each time the salt is
   changed.

   There MUST be at least one complete set of NSEC3s for the zone using
   the same salt value.

   The salt SHOULD be changed periodically to prevent pre-computation
   using a single salt.  It is RECOMMENDED that the salt be changed for
   every resigning.

   Note that this could cause a resolver to see records with different
   salt values for the same zone.  This is harmless, since each record
   stands alone (that is, it denies the set of ownernames whose hashes,
   using the salt in the NSEC3 record, fall between the two hashes in
   the NSEC3 record) - it is only the server that needs a complete set
   of NSEC3 records with the same salt in order to be able to answer
   every possible query.

   There is no prohibition with having NSEC3 with different salts within
   the same zone.  However, in order for authoritative servers to be
   able to consistently find covering NSEC3 RRs, the authoritative
   server MUST choose a single set of parameters (algorithm, salt, and
   iterations) to use when selecting NSEC3s.  In the absence of any
   other metadata, the server does this by using the parameters from the
   zone apex NSEC3, recognizable by the presence of the SOA bit in the
   type map.  If there is more than one NSEC3 record that meets this
   description, then the server may arbitrarily choose one.  Because of
   this, if there is a zone apex NSEC3 RR within a zone, it MUST be part
   of a complete NSEC3 set.  Conversely, if there exists an incomplete
   set of NSEC3 RRs using the same parameters within a zone, there MUST
   NOT be an NSEC3 RR using those parameters with the SOA bit set.

C.2.  Hash Collision

   Hash collisions occur when different messages have the same hash
   value.  The expected number of domain names needed to give a 1 in 2
   chance of a single collision is about 2^(n/2) for a hash of length n
   bits (i.e. 2^80 for SHA-1).  Though this probability is extremely
   low, the following paragraphs deal with avoiding collisions and
   assessing possible damage in the event of an attack using hash
   collisions.






Laurie, et al.            Expires March 4, 2007                [Page 46]

Internet-Draft                    nsec3                      August 2006


C.2.1.  Avoiding Hash Collisions during generation

   During generation of NSEC3 RRs, hash values are supposedly unique.
   In the (academic) case of a collision occurring, an alternative salt
   MUST be chosen and all hash values MUST be regenerated.

C.2.2.  Second Preimage Requirement Analysis

   A cryptographic hash function has a second-preimage resistance
   property.  The second-preimage resistance property means that it is
   computationally infeasible to find another message with the same hash
   value as a given message, i.e. given preimage X, to find a second
   preimage X' != X such that hash(X) = hash(X').  The work factor for
   finding a second preimage is of the order of 2^160 for SHA-1.  To
   mount an attack using an existing NSEC3 RR, an adversary needs to
   find a second preimage.

   Assuming an adversary is capable of mounting such an extreme attack,
   the actual damage is that a response message can be generated which
   claims that a certain QNAME (i.e. the second pre-image) does exist,
   while in reality QNAME does not exist (a false positive), which will
   either cause a security aware resolver to re-query for the non-
   existent name, or to fail the initial query.  Note that the adversary
   can't mount this attack on an existing name but only on a name that
   the adversary can't choose and does not yet exist.

C.2.3.  Possible Hash Value Truncation Method

   The previous sections outlined the low probability and low impact of
   a second-preimage attack.  When impact and probability are low, while
   space in a DNS message is costly, truncation is tempting.  Truncation
   might be considered to allow for shorter ownernames and RDATA for
   hashed labels.  In general, if a cryptographic hash is truncated to n
   bits, then the expected number of domains required to give a 1 in 2
   probability of a single collision is approximately 2^(n/2) and the
   work factor to produce a second preimage is 2^n.

   An extreme hash value truncation would be truncating to the shortest
   possible unique label value.  This would be unwise, since the work
   factor to produce second preimages would then approximate the size of
   the zone (sketch of proof: if the zone has k entries, then the length
   of the names when truncated down to uniqueness should be proportional
   to log_2(k).  Since the work factor to produce a second pre-image is
   2^n for an n-bit hash, then in this case it is 2^(C log_2(k)) (where
   C is some constant), i.e.  C'k - a work factor of k).

   Though the mentioned truncation can be maximized to a certain
   extreme, the probability of collision increases exponentially for



Laurie, et al.            Expires March 4, 2007                [Page 47]

Internet-Draft                    nsec3                      August 2006


   every truncated bit.  Given the low impact of hash value collisions
   and limited space in DNS messages, the balance between truncation
   profit and collision damage may be determined by local policy.  Of
   course, the size of the corresponding RRSIG RR is not reduced, so
   truncation is of limited benefit.

   Truncation could be signaled simply by reducing the length of the
   first label in the ownername.  Note that there would have to be a
   corresponding reduction in the length of the Next Hashed Ownername
   field.


Authors' Addresses

   Ben Laurie
   Nominet
   17 Perryn Road
   London  W3 7LR
   England

   Phone: +44 (20) 8735 0686
   Email: ben@algroup.co.uk


   Geoffrey Sisson
   Nominet
   Sandford Gate
   Sandy Lane West
   Oxford  OX4 6LB
   UNITED KINGDOM

   Phone: +44 1865 332211
   Email: geoff@nominet.org.uk


   Roy Arends
   Nominet
   Sandford Gate
   Sandy Lane West
   Oxford  OX4 6LB
   UNITED KINGDOM

   Phone: +44 1865 332211
   Email: roy@nominet.org.uk







Laurie, et al.            Expires March 4, 2007                [Page 48]

Internet-Draft                    nsec3                      August 2006


   David Blacka
   VeriSign, Inc.
   21355 Ridgetop Circle
   Dulles, VA  20166
   US

   Phone: +1 703 948 3200
   Email: davidb@verisign.com











































Laurie, et al.            Expires March 4, 2007                [Page 49]

Internet-Draft                    nsec3                      August 2006


Full Copyright Statement

   Copyright (C) The Internet Society (2006).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Laurie, et al.            Expires March 4, 2007                [Page 50]


Html markup produced by rfcmarkup 1.109, available from https://tools.ietf.org/tools/rfcmarkup/