[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
Expires: November 10, 2006                                     R. Arends
                                                                 Nominet
                                                             May 9, 2006


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

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 November 10, 2006.

Copyright Notice

   Copyright (C) The Internet Society (2006).

Abstract

   The DNS Security Extensions introduces the NSEC resource record for
   authenticated denial of existence.  This document introduces a new
   resource record as an alternative to NSEC that provides measures
   against zone enumeration and allows for gradual expansion of
   delegation-centric zones.





Laurie, et al.          Expires November 10, 2006               [Page 1]

Internet-Draft                    nsec3                         May 2006


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Rationale  . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.2.  Reserved Words . . . . . . . . . . . . . . . . . . . . . .  4
     1.3.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  The NSEC3 Resource Record  . . . . . . . . . . . . . . . . . .  5
     2.1.  RDATA fields . . . . . . . . . . . . . . . . . . . . . . .  6
       2.1.1.  Hash Algorithm . . . . . . . . . . . . . . . . . . . .  6
       2.1.2.  Opt-Out Flag . . . . . . . . . . . . . . . . . . . . .  6
       2.1.3.  Iterations . . . . . . . . . . . . . . . . . . . . . .  6
       2.1.4.  Salt Length  . . . . . . . . . . . . . . . . . . . . .  6
       2.1.5.  Salt . . . . . . . . . . . . . . . . . . . . . . . . .  6
       2.1.6.  Next Hashed Ownername  . . . . . . . . . . . . . . . .  7
       2.1.7.  Type Bit Maps  . . . . . . . . . . . . . . . . . . . .  7
     2.2.  NSEC3 RDATA Wire Format  . . . . . . . . . . . . . . . . .  7
       2.2.1.  Type Bit Map Encoding  . . . . . . . . . . . . . . . .  8
     2.3.  Presentation Format  . . . . . . . . . . . . . . . . . . .  8
   3.  Calculation of the Hash  . . . . . . . . . . . . . . . . . . .  9
   4.  Opt-out  . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
   5.  Authoritative Server Considerations  . . . . . . . . . . . . . 10
     5.1.  Zone Signing . . . . . . . . . . . . . . . . . . . . . . . 10
     5.2.  Secondary Servers  . . . . . . . . . . . . . . . . . . . . 11
     5.3.  Dynamic Update . . . . . . . . . . . . . . . . . . . . . . 12
     5.4.  Zone Serving . . . . . . . . . . . . . . . . . . . . . . . 12
       5.4.1.  Closest Encloser Proof . . . . . . . . . . . . . . . . 12
       5.4.2.  Proving Nonexistence (NAME ERROR)  . . . . . . . . . . 12
       5.4.3.  Proving Nonexistence (NODATA/NOERROR, QTYPE is not
               DS)  . . . . . . . . . . . . . . . . . . . . . . . . . 12
       5.4.4.  Proving Nonexistence (NODATA/NOERROR, QTYPE is DS) . . 12
       5.4.5.  Proving Nonexistence (NODATA/NOERROR, wildcard
               exists, no matching RRTYPE)  . . . . . . . . . . . . . 12
       5.4.6.  Proving a wildcard response  . . . . . . . . . . . . . 13
       5.4.7.  Proving a delegation to an unsigned zone . . . . . . . 13
       5.4.8.  Responding to NSEC3 Queries  . . . . . . . . . . . . . 13
   6.  Validator Considerations . . . . . . . . . . . . . . . . . . . 14
     6.1.  Responses with Unknown Hash Types  . . . . . . . . . . . . 14
     6.2.  Closest Encloser Proof . . . . . . . . . . . . . . . . . . 14
     6.3.  Proving Nonexistence (NAME ERROR)  . . . . . . . . . . . . 15
     6.4.  Proving Nonexistence (NODATA/NOERROR, QTYPE is not DS) . . 15
     6.5.  Proving Nonexistence (NODATA/NOERROR), QTYPE is DS . . . . 15
     6.6.  Proving Nonexistence (NODATA/NOERROR, wildcard exists,
           no matching RRTYPE)  . . . . . . . . . . . . . . . . . . . 15
     6.7.  Proving a wildcard response  . . . . . . . . . . . . . . . 15
     6.8.  Proving a delegation to an unsigned zone . . . . . . . . . 15
     6.9.  Validating responses to NSEC3 queries  . . . . . . . . . . 16
       6.9.1.  QTYPE is not NSEC3, NSEC3 RRset only . . . . . . . . . 16
       6.9.2.  QTYPE is NSEC3, QNAME does not match . . . . . . . . . 16



Laurie, et al.          Expires November 10, 2006               [Page 2]

Internet-Draft                    nsec3                         May 2006


   7.  Resolver Considerations  . . . . . . . . . . . . . . . . . . . 16
   8.  Special Considerations . . . . . . . . . . . . . . . . . . . . 16
     8.1.  Iterations . . . . . . . . . . . . . . . . . . . . . . . . 16
   9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 17
   11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
     11.1. Normative References . . . . . . . . . . . . . . . . . . . 19
     11.2. Informative References . . . . . . . . . . . . . . . . . . 20
   10. Security Considerations  . . . . . . . . . . . . . . . . . . . 17
   Editorial Comments . . . . . . . . . . . . . . . . . . . . . . . .
   Appendix A.  Example Zone  . . . . . . . . . . . . . . . . . . . . 21
   Appendix B.  Example Responses . . . . . . . . . . . . . . . . . . 26
     B.1.  answer . . . . . . . . . . . . . . . . . . . . . . . . . . 26
       B.1.1.  Authenticating the Example DNSKEY RRset  . . . . . . . 28
     B.2.  Name Error . . . . . . . . . . . . . . . . . . . . . . . . 29
     B.3.  No Data Error  . . . . . . . . . . . . . . . . . . . . . . 31
       B.3.1.  No Data Error, Empty Non-Terminal  . . . . . . . . . . 32
     B.4.  Referral to Signed Zone  . . . . . . . . . . . . . . . . . 33
     B.5.  Referral to Unsigned Zone using the Opt-Out Flag . . . . . 34
     B.6.  Wildcard Expansion . . . . . . . . . . . . . . . . . . . . 35
     B.7.  Wildcard No Data Error . . . . . . . . . . . . . . . . . . 37
     B.8.  DS Child Zone No Data Error  . . . . . . . . . . . . . . . 38
   Appendix C.  Special Considerations  . . . . . . . . . . . . . . . 39
     C.1.  Salting  . . . . . . . . . . . . . . . . . . . . . . . . . 40
     C.2.  Hash Collision . . . . . . . . . . . . . . . . . . . . . . 40
       C.2.1.  Avoiding Hash Collisions during generation . . . . . . 41
       C.2.2.  Second Preimage Requirement Analysis . . . . . . . . . 41
       C.2.3.  Possible Hash Value Truncation Method  . . . . . . . . 41
       C.2.4.  Server Response to a Run-time Collision  . . . . . . . 42
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 43
   Intellectual Property and Copyright Statements . . . . . . . . . . 44





















Laurie, et al.          Expires November 10, 2006               [Page 3]

Internet-Draft                    nsec3                         May 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 be under strict legal obligations to protect.  Many
   registries therefore prohibit copying of their zone file; 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 is used to describe the practice of discovering the
      contents of a zone via successive queries.  Zone enumeration was
      not practical prior to the introduction of DNSSEC.






Laurie, et al.          Expires November 10, 2006               [Page 4]

Internet-Draft                    nsec3                         May 2006


   Original ownername refers to the ownername corresponding to a hashed
      ownername.
   Hashed ownername refers to the ownername created after applying the
      hash function to an ownername.
   Hash order is the order in which hashed ownernames are arranged
      according to their numerical value, treating the leftmost (lowest
      numbered) octect 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 refers to a domain name that owns no resource
      records, but has subdomains that do.
   Opt-Out NSEC3 Record refers to an NSEC3 resource record which has the
      Opt-Out flag field set to 1.
   Opt-Out Zone refers to a zone with at least one Opt-Out NSEC3 record.
   Closest encloser refers to longest existing ancestor of a name.  See
      also section 3.3.1 [13].
   Closest Provable Encloser refers to 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 refers to the name one label longer than a name's
      Closest Provable Encloser.
   Base32 encoding refers to the "Base 32 Encoding with Extended Hex
      Alphabet" as specified in RFC 3548bis [14].
   Cover An NSEC3 record is said to cover a name if the hash of the name
      falls between the NSEC3's ownername and the next hashed ownername.
      In other words, if it proves the nonexistence of the name.


2.  The NSEC3 Resource Record

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

   The NSEC3 Resource Record (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 3.

   Hashed ownernames of unsigned delegations may be excluded from the



Laurie, et al.          Expires November 10, 2006               [Page 5]

Internet-Draft                    nsec3                         May 2006


   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.

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

2.1.  RDATA fields

2.1.1.  Hash Algorithm

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

   The values are as defined for the DS record (see RFC 3658 [10]).

2.1.2.  Opt-Out Flag

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

2.1.3.  Iterations

   The Iterations field defines the number of times the hash has been
   iterated.  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 3 for details of this field's use.

2.1.4.  Salt Length

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

2.1.5.  Salt

   The Salt field is appended to the original ownername before hashing
   in order to defend against precalculated dictionary attacks.  See



Laurie, et al.          Expires November 10, 2006               [Page 6]

Internet-Draft                    nsec3                         May 2006


   Section 3 for details on how the salt is used.

2.1.6.  Next Hashed Ownername

   The Next Hashed Ownername field contains the next hashed ownername in
   hash order.  That is, given the set of all hashed owernames, 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.

2.1.7.  Type Bit Maps

   The Type Bit Maps field identifies the RRset types which exist at the
   NSEC3 RR's original ownername.

2.2.  NSEC3 RDATA Wire Format

   The RDATA of the NSEC3 RR is as shown below:

                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Hash Alg.     |O|                Iterations                   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Salt Length  |                     Salt                      /
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   /                     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.

   If Salt Length is zero, the salt field is omitted.

   Salt, if present, is encoded as a sequence of Salt Length 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 hash algorithm.



Laurie, et al.          Expires November 10, 2006               [Page 7]

Internet-Draft                    nsec3                         May 2006


2.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].

   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.

   "|" 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 [11]
   (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.

2.3.  Presentation Format

   The presentation format of the RDATA portion is as follows:




Laurie, et al.          Expires November 10, 2006               [Page 8]

Internet-Draft                    nsec3                         May 2006


   o  The Opt-Out Flag Field is represented as an unsigned decimal
      integer.  The value is either 0 or 1.
   o  The Hash field is presented as either a mnemonic of the hash or as
      an unsigned decimal integer.  The value has a maximum of 255.
   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.
   o  The Next Hashed Ownername field is represented as a 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 [12] (section 5) MUST be
      used.


3.  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)

   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 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);
   This form is as defined in section 6.2 of RFC 4034 ([5]).





Laurie, et al.          Expires November 10, 2006               [Page 9]

Internet-Draft                    nsec3                         May 2006


4.  Opt-out

   In DNSSEC, NS RRsets at delegation points are not signed, and may be
   accompanied by a DS record.  The security status of the subzone is
   determined by the presence or absence of the DS RRset,
   cryptographically proven by the NSEC record or the signed DS RRset.
   The presence of the Opt-Out flag expands this definition by allowing
   insecure delegations to exist within an otherwise signed zone without
   the corresponding NSEC3 record at the delegation's hashed owner name.
   These delegations are proven insecure by using a covering NSEC3
   record.

   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.

   In summary,
   o  An Opt-Out NSEC3 type is identified by an Opt-Out Flag field value
      of 1.
   o  A non Opt-Out NSEC3 type is identified by an Opt-Out Flag field
      value of 0.
   and,
   o  An Opt-Out NSEC3 record covers zero or more insecure delegations.
   o  An Opt-Out NSEC3 record does assert the (non)existence of RRsets
      with the same hashed owner name.


5.  Authoritative Server Considerations

5.1.  Zone Signing

   Zones using NSEC3 must satisfy the following properties:



Laurie, et al.          Expires November 10, 2006              [Page 10]

Internet-Draft                    nsec3                         May 2006


   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 included in the set of NSEC3 RRs.
   o  Each empty non-terminal MUST have an NSEC3 record.
   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 bitmap of every NSEC3 resource record in a signed zone
      MUST indicate the presence of both the NSEC3 RR type itself and
      its corresponding RRSIG RR type.

   The following steps describe a method of proper construction of NSEC3
   records.  [Comment.1]
   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.
   2.  For each RRset at the original owner name, set the corresponding
       bit in the type bit map.
   3.  If the difference in number of labels between the apex and the
       original ownername is greater then 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.
   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 map consisting of the union
       of the types represented by the set of NSEC3 RRs.
   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.

5.2.  Secondary Servers

   Secondary servers (and perhaps other entities) need to reliably
   determine which NSEC3 parameters (that is, 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 the parameters at the apex: any set of parameters that
   is used in an NSEC3 record whose original ownername is the apex of
   the zone MUST be present throughout the zone.




Laurie, et al.          Expires November 10, 2006              [Page 11]

Internet-Draft                    nsec3                         May 2006


   A method to determine which NSEC3 in a complete chain corresponds to
   the apex is to look for a NSEC3 RRset which has the SOA bit set in
   the RDATA bit type maps field.

5.3.  Dynamic Update

   NSEC3 changes the semantics of Secure DNS Dynamic Update.  This
   document does not attempt to define these semantics.  Until these
   changes are defined, servers MUST NOT process DNS Dynamic Update
   requests against zones that use NSEC3 records.  Servers SHOULD return
   responses to update requests with RCODE=REFUSED.

5.4.  Zone Serving

5.4.1.  Closest Encloser Proof

   For most 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.  In order to do this an NSEC3 record whose owner
   corresponds to the hash of the closest encloser and an NSEC3 that
   covers the hash of the next name closer to the QNAME are shown.

5.4.2.  Proving Nonexistence (NAME ERROR)

   To prove the nonexistence of QNAME a closest encloser proof and an
   NSEC3 covering the wildcard record at the closest encloser MUST be
   shown.

5.4.3.  Proving Nonexistence (NODATA/NOERROR, QTYPE is not DS)

   The server MUST show the NSEC3 record at the hash of QNAME.

5.4.4.  Proving Nonexistence (NODATA/NOERROR, QTYPE is DS)

   If an NSEC3 record exists at the hash of QNAME, the server MUST show
   it.

   Otherwise, the server MUST show a closest provable encloser proof for
   QNAME.  The non-existence proof of the Next Closer Name will have the
   Opt-Out bit set.

   If a server is authoritative for both sides of a zone cut, the server
   MUST show the NSEC3 record of the parent side of a zone cut.

5.4.5.  Proving Nonexistence (NODATA/NOERROR, wildcard exists, no
        matching RRTYPE)

   In this case, there is a wildcard match for the QNAME, but QTYPE is



Laurie, et al.          Expires November 10, 2006              [Page 12]

Internet-Draft                    nsec3                         May 2006


   not present at that name.  To prove this, the response MUST contain a
   closest encloser proof for the ancestor of the wildcard RRset, and
   proof of the existence of the wildcard.

5.4.6.  Proving a wildcard response

   An NSEC3 that proves the nonexistence of the ancestor of QNAME whose
   ancestor is the closest encloser MUST be shown.  There is no need to
   prove the existence of the closest encloser as that is necessarily
   done while verifying the wildcard expansion (that is, the immediate
   ancestor of the verified wildcard exists).

5.4.7.  Proving a delegation to an unsigned zone

   Because NS records are not signed, a delegation to an unsigned zone
   has no cryptographic security.  Therefore a proof that the zone is
   unsigned MUST be shown.  This is achieved by including the NSEC3
   record corresponding to the delegated domain, which should not have
   the DS bit set.  If the zone is Opt-Out, then this record may not
   exist, in which case the NSEC3s proving the closest provable encloser
   of the delegated zone MUST be included in the response.

5.4.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
   two special cases.  All other cases MUST be handled normally.

5.4.8.1.  QTYPE is not NSEC3, NSEC3 RRset only

   This special case arises when the following are all true:
   o  The QNAME equals an existing NSEC3 ownername, and
   o  There are no other record types that exist at QNAME, and
   o  The QTYPE does not equal NSEC3.
   These conditions describe a particular case: the answer should be a
   NOERROR/NODATA response, but there is no NSEC3 RRset for H(QNAME) to
   include in the authority section.

   In this case the server MUST return NAME ERROR as if the NSEC3 record
   did not exist, together with a proof as for a normal NAME ERROR
   response.

5.4.8.2.  QTYPE is NSEC3, QNAME does not match

   [Note: we could restrict this to the case where there's no other data
   at the name, and do NOERROR/NODATA when there is]

   This special case arises when the following are all true:



Laurie, et al.          Expires November 10, 2006              [Page 13]

Internet-Draft                    nsec3                         May 2006


   o  The QNAME does not equal an existing NSEC3 ownername, and
   o  The QTYPE equals NSEC3.

   Because it is possible to "prove" the nonexistence of almost all
   NSEC3 records (the exceptions are those that have other record types
   at the name), it is necessary to vary the standard response when the
   QTYPE is NSEC3.  In this case the server MUST respond with the NSEC3
   record that covers the unhashed QNAME.

   Since the QNAME is not hashed, it is only possible to prove the
   nonexistence of NSEC3 records that actually don't exist.  If they do
   exist, then they will appear as the ownername of an NSEC3 record, and
   so it will be impossible to show the NSEC3 record that covers the
   unhashed name.


6.  Validator Considerations

6.1.  Responses with Unknown Hash Types

   A validator MUST ignore NSEC3 records with unknown hash types.  If no
   known hash types are present, the validator SHOULD treat the response
   as unsigned.

6.2.  Closest Encloser Proof

   In order to verify a closest encloser proof, the validator should
   start with the QNAME and see if an NSEC3 record proves its
   nonexistence.  It should then truncate by one label and see if there
   is an NSEC3 that proves the existence of that name.  If so, then the
   closest encloser has been proved, and is the name whose existence was
   just proved.  If not, then the process should be restarted using the
   truncated name.

   An algorithm to do this check is as follows:
   1.  Set SNAME=QNAME
   2.  Check whether SNAME exists
       *  No proof -> Clear flag
       *  Proof of nonexistence -> Set flag
       *  Proof of existence and flag is set, then SNAME is closest
          encloser
       *  Proof of existence and flag is not set, then the response is
          bogus
   3.  truncate SNAME by one label, go to 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.  Neither the NS nor the DNAME type bit are set.



Laurie, et al.          Expires November 10, 2006              [Page 14]

Internet-Draft                    nsec3                         May 2006


   This would be an indication that an attacker is using them to falsely
   deny the existence of records for which the server is not
   authoritative.

   When we say we want a closest encloser proof for X, then we want the
   algorithm above to yield X as the closest encloser.

6.3.  Proving Nonexistence (NAME ERROR)

   A validator MUST verify that there is a closest encloser proof for
   QNAME and that there is a nonexistence proof for the wildcard at the
   closest encloser.

6.4.  Proving Nonexistence (NODATA/NOERROR, QTYPE is not DS)

   The resolver MUST verify that an NSEC3 RR with the hash of QNAME is
   present and that the QTYPE is not set in its Type Bit Map.

   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 have an empty Type Bit Map.

6.5.  Proving Nonexistence (NODATA/NOERROR), QTYPE is DS

   The resolver MUST first attempt to verify a nonexistence proof as for
   NODATA/NOERROR where QTYPE is not DS.

   If this record does not exist, then the resolver MUST verify that a
   closest provable encloser proof for the QNAME is present, and that
   the non-existence proof has the Opt-Out bit set.

6.6.  Proving Nonexistence (NODATA/NOERROR, wildcard exists, no matching
      RRTYPE)

   A validator MUST verify that a closest encloser has been proved and
   that prepending the wildcard character onto that closest encloser
   yields a name whose existence has been proved.

6.7.  Proving a wildcard response

   Valdiators MUST verify that there is an NSEC3 showing the
   nonexistence of the ancestor of the QNAME whose ancestor is the
   closest encloser.  The domain name of the closest encloser is the
   immediate ancestor of the wildcard used to answer the query.

6.8.  Proving a delegation to an unsigned zone

   A validator MUST verify that there is an NSEC3 record present



Laurie, et al.          Expires November 10, 2006              [Page 15]

Internet-Draft                    nsec3                         May 2006


   corresponding to the delegation, and that the NS bit is set and the
   DS bit is not set in it.  It MUST also ensure that it is using the
   NSEC3 record from the parent zone and not the child zone.  This can
   be checked by examining the SOA bit, which will be set in the child
   NSEC3 and clear in the parent NSEC3.

   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.

   If such a record is not present, then the zone is Opt-Out, and the
   validator MUST verify that there is a closest provable encloser proof
   for an ancestor of the delegated zone, and that the Opt-Out bit is
   set in the nonexistence part of the proof.

6.9.  Validating responses to NSEC3 queries

   See Section 5.4.8.

6.9.1.  QTYPE is not NSEC3, NSEC3 RRset only

   The validator MUST check the response exactly as for a normal
   NXDOMAIN response.

6.9.2.  QTYPE is NSEC3, QNAME does not match

   The validator MUST check that an NSEC3 is present which covers the
   unhashed QNAME.


7.  Resolver Considerations


8.  Special Considerations

8.1.  Iterations

   [NOTE: should we actually base this on verifications, not signings?]

   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 the zone as well as the verifiers cost of verifying the
   zone.  We therefore impose an upper limit on the number of
   iterations.  We base this on the number of iterations that



Laurie, et al.          Expires November 10, 2006              [Page 16]

Internet-Draft                    nsec3                         May 2006


   approximately doubles the cost of signing the zone.

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

                     +--------------+------------+
                     | RSA Key Size | Iterations |
                     +--------------+------------+
                     | 1024         | 3,000      |
                     | 2048         | 20,000     |
                     | 4096         | 150,000    |
                     +--------------+------------+

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

   This table is based on 150,000 SHA-1's per second, 50 RSA signs per
   second for 1024 bit keys, 7 signs per second for 2048 bit keys, 1
   sign per second for 4096 bit keys, 100 DSA signs per second for 1024
   bit keys and 30 signs per second for 2048 bit keys.

   Note that since RSA verifications are 10-100 times faster than
   signatures (depending on key size), in the case of RSA the legal
   values of iterations can substantially increase the cost of
   verification.


9.  IANA Considerations

   IANA needs to allocate a RR type code for NSEC3 from the standard RR
   type space (type XXX requested).


10.  Security Considerations

   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.



Laurie, et al.          Expires November 10, 2006              [Page 17]

Internet-Draft                    nsec3                         May 2006


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

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

   Hash collisions may occur.  If they do, it will be impossible to
   prove the non-existence of the colliding domain - however, this is
   fantastically unlikely, and, in any case, DNSSEC already relies on
   SHA-1 to not collide.

   Responses to queries where QNAME equals an NSEC3 ownername that has
   no other types may be undetectably changed from a NOERROR/NODATA
   response to a NAME ERROR response.

   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 by cryptographically proven.

   In general:
      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").
      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).



Laurie, et al.          Expires November 10, 2006              [Page 18]

Internet-Draft                    nsec3                         May 2006


   For example, if a resolver received the following response from the
   example zone above:

   Example S.1: Response to query for WWW.DOES-NOT-EXIST.EXAMPLE.  A

           RCODE=NOERROR

           Answer Section:

           Authority Section:
           DOES-NOT-EXIST.EXAMPLE. NS     NS.FORGED.
           EXAMPLE.                NSEC   FIRST-SECURE.EXAMPLE. SOA NS \
                                          RRSIG DNSKEY
           abcd...                 RRSIG  NSEC3 ...

           Additional Section:

   The resolver would have no choice but to accept that the referral to
   NS.FORGED. is valid.  If a wildcard existed that would have been
   expanded to cover "WWW.DOES-NOT-EXIST.EXAMPLE.", an attacker could
   have undetectably removed it and replaced it with the forged
   delegation.

   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.


11.  References

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




Laurie, et al.          Expires November 10, 2006              [Page 19]

Internet-Draft                    nsec3                         May 2006


   [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]  Gudmundsson, O., "Delegation Signer (DS) Resource Record (RR)",
         RFC 3658, December 2003.

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

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

11.2  Informative References

   [13]  Lewis, E., "The Role of Wildcards in the Domain Name System",
         draft-ietf-dnsext-wcard-clarify-11 (work in progress),
         March 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.

Editorial Comments

   [Comment.1]  Note that this method makes it impossible to detect



Laurie, et al.          Expires November 10, 2006              [Page 20]

Internet-Draft                    nsec3                         May 2006


                (extremely unlikely) hash collisions.


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 data in the example zone is currently broken, as it uses a
   different base32 alphabet.  This shall be fixed in the next release.


   example.       3600 IN SOA ns1.example. bugs.x.w.example. (
                              1
                              3600
                              300
                              3600000
                              3600 )
                  3600 RRSIG  SOA 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              RtctD6aLUU5Md5wOOItilS7JXX1tf58Ql3sK
                              mTXkL13jqLiUFOGg0uzqRh1U9GbydS0P7M0g
                              qYIt90txzE/4+g== )
                  3600 NS     ns1.example.
                  3600 NS     ns2.example.
                  3600 RRSIG  NS 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              hNyyin2JpECIFxW4vsj8RhHcWCQKUXgO+z4l
                              m7g2zM8q3Qpsm/gYIXSF2Rhj6lAG7esR/X9d
                              1SH5r/wfjuCg+g== )
                  3600 MX     1 xx.example.
                  3600 RRSIG  MX 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              L/ZDLMSZJKITmSxmM9Kni37/wKQsdSg6FT0l
                              NMm14jy2Stp91Pwp1HQ1hAMkGWAqCMEKPMtU
                              S/o/g5C8VM6ftQ== )
                  3600 DNSKEY 257 3 5 (
                              AQOnsGyJvywVjYmiLbh0EwIRuWYcDiB/8blX
                              cpkoxtpe19Oicv6Zko+8brVsTMeMOpcUeGB1
                              zsYKWJ7BvR2894hX
                              ) ; Key ID = 21960
                  3600 DNSKEY 256 3 5 (
                              AQO0gEmbZUL6xbD/xQczHbnwYnf+jQjwz/sU
                              5k44rHTt0Ty+3aOdYoome9TjGMhwkkGby1TL
                              ExXT48OGGdbfIme5
                              ) ; Key ID = 62699
                  3600 RRSIG  DNSKEY 5 1 3600 20050712112304 (
                              20050612112304 62699 example.



Laurie, et al.          Expires November 10, 2006              [Page 21]

Internet-Draft                    nsec3                         May 2006


                              e6EB+K21HbyZzoLUeRDb6+g0+n8XASYe6h+Z
                              xtnB31sQXZgq8MBHeNFDQW9eZw2hjT9zMClx
                              mTkunTYzqWJrmQ== )
                  3600 RRSIG  DNSKEY 5 1 3600 20050712112304 (
                              20050612112304 21960 example.
                              SnWLiNWLbOuiKU/F/wVMokvcg6JVzGpQ2VUk
                              ZbKjB9ON0t3cdc+FZbOCMnEHRJiwgqlnncik
                              3w7ZY2UWyYIvpw== )
   5pe7ctl7pfs2cilroy5dcofx4rcnlypd.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              7nomf47k3vlidh4vxahhpp47l3tgv7a2
                              NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              PTWYq4WZmmtgh9UQif342HWf9DD9RuuM4ii5
                              Z1oZQgRi5zrsoKHAgl2YXprF2Rfk1TLgsiFQ
                              sb7KfbaUo/vzAg== )
   7nomf47k3vlidh4vxahhpp47l3tgv7a2.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              dw4o7j64wnel3j4jh7fb3c5n7w3js2yb
                              MX NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              YTcqole3h8EOsTT3HKnwhR1QS8borR0XtZaA
                              ZrLsx6n0RDC1AAdZONYOvdqvcal9PmwtWjlo
                              MEFQmc/gEuxojA== )
   a.example.     3600 IN NS  ns1.a.example.
                  3600 IN NS  ns2.a.example.
                  3600 DS     58470 5 1 3079F1593EBAD6DC121E202A8B
                              766A6A4837206C )
                  3600 RRSIG  DS 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              QavhbsSmEvJLSUzGoTpsV3SKXCpaL1UO3Ehn
                              cB0ObBIlex/Zs9kJyG/9uW1cYYt/1wvgzmX2
                              0kx7rGKTc3RQDA== )
   ns1.a.example. 3600 IN A   192.0.2.5
   ns2.a.example. 3600 IN A   192.0.2.6
   ai.example.    3600 IN A   192.0.2.9
                  3600 RRSIG  A 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              plY5M26ED3Owe3YX0pBIhgg44j89NxUaoBrU
                              6bLRr99HpKfFl1sIy18JiRS7evlxCETZgubq
                              ZXW5S+1VjMZYzQ== )
                  3600 HINFO  "KLH-10" "ITS"
                  3600 RRSIG  HINFO 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              AR0hG/Z/e+vlRhxRQSVIFORzrJTBpdNHhwUk
                              tiuqg+zGqKK84eIqtrqXelcE2szKnF3YPneg



Laurie, et al.          Expires November 10, 2006              [Page 22]

Internet-Draft                    nsec3                         May 2006


                              VGNmbgPnqDVPiA== )
                  3600 AAAA   2001:db8:0:0:0:0:f00:baa9
                  3600 RRSIG  AAAA 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              PNF/t7+DeosEjhfuL0kmsNJvn16qhYyLI9FV
                              ypSCorFx/PKIlEL3syomkYM2zcXVSRwUXMns
                              l5/UqLCJJ9BDMg== )
   b.example.     3600 IN NS  ns1.b.example.
                  3600 IN NS  ns2.b.example.
   ns1.b.example. 3600 IN A   192.0.2.7
   ns2.b.example. 3600 IN A   192.0.2.8
   dw4o7j64wnel3j4jh7fb3c5n7w3js2yb.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              gmnfcccja7wkax3iv26bs75myptje3qk
                              MX DNSKEY NS SOA NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              VqEbXiZLJVYmo25fmO3IuHkAX155y8NuA50D
                              C0NmJV/D4R3rLm6tsL6HB3a3f6IBw6kKEa2R
                              MOiKMSHozVebqw== )
   gmnfcccja7wkax3iv26bs75myptje3qk.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              jt4bbfokgbmr57qx4nqucvvn7fmo6ab6
                              DS NS NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              ZqkdmF6eICpHyn1Cj7Yvw+nLcbji46Qpe76/
                              ZetqdZV7K5sO3ol5dOc0dZyXDqsJp1is5StW
                              OwQBGbOegrW/Zw== )
   jt4bbfokgbmr57qx4nqucvvn7fmo6ab6.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              kcll7fqfnisuhfekckeeqnmbbd4maanu
                              NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              FXyCVQUdFF1EW1NcgD2V724/It0rn3lr+30V
                              IyjmqwOMvQ4G599InTpiH46xhX3U/FmUzHOK
                              94Zbq3k8lgdpZA== )
   kcll7fqfnisuhfekckeeqnmbbd4maanu.example. 3600 NSEC3  1 1 1 (
                              deadbeaf
                              n42hbhnjj333xdxeybycax5ufvntux5d
                              MX NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              d0g8MTOvVwByOAIwvYV9JrTHwJof1VhnMKuA
                              IBj6Xaeney86RBZYgg7Qyt9WnQSK3uCEeNpx
                              TOLtc5jPrkL4zQ== )
   n42hbhnjj333xdxeybycax5ufvntux5d.example. 3600 NSEC3  0 1 1 (



Laurie, et al.          Expires November 10, 2006              [Page 23]

Internet-Draft                    nsec3                         May 2006


                              deadbeaf
                              nimwfwcnbeoodmsc6npv3vuaagaevxxu
                              A NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              MZGzllh+YFqZbY8SkHxARhXFiMDPS0tvQYyy
                              91tj+lbl45L/BElD3xxB/LZMO8vQejYtMLHj
                              xFPFGRIW3wKnrA== )
   nimwfwcnbeoodmsc6npv3vuaagaevxxu.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              vhgwr2qgykdkf4m6iv6vkagbxozphazr
                              HINFO A AAAA NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              c3zQdK68cYTHTjh1cD6pi0vblXwzyoU/m7Qx
                              z8kaPYikbJ9vgSl9YegjZukgQSwybHUC0SYG
                              jL33Wm1p07TBdw== )
   ns1.example.   3600 A      192.0.2.1
                  3600 RRSIG  A 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              QLGkaqWXxRuE+MHKkMvVlswg65HcyjvD1fyb
                              BDZpcfiMHH9w4x1eRqRamtSDTcqLfUrcYkrr
                              nWWLepz1PjjShQ== )
   ns2.example.   3600 A      192.0.2.2
                  3600 RRSIG  A 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              UoIZaC1O6XHRWGHBOl8XFQKPdYTkRCz6SYh3
                              P2mZ3xfY22fLBCBDrEnOc8pGDGijJaLl26Cz
                              AkeTJu3J3auUiA== )
   vhgwr2qgykdkf4m6iv6vkagbxozphazr.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              wbyijvpnyj33pcpi3i44ecnibnaj7eiw
                              HINFO A AAAA NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              leFhoF5FXZAiNOxK4OBOOA0WKdbaD5lLDT/W
                              kLoyWnQ6WGBwsUOdsEcVmqz+1n7q9bDf8G8M
                              5SNSHIyfpfsi6A== )
   *.w.example.   3600 MX     1 ai.example.
                  3600 RRSIG  MX 5 3 3600 20050712112304 (
                              20050612112304 62699 example.
                              sYNUPHn1/gJ87wTHNksGdRm3vfnSFa2BbofF
                              xGfJLF5A4deRu5f0hvxhAFDCcXfIASj7z0wQ
                              gQlgxEwhvQDEaQ== )
   x.w.example.   3600 MX     1 xx.example.
                  3600 RRSIG  MX 5 3 3600 20050712112304 (
                              20050612112304 62699 example.
                              s1XQ/8SlViiEDik9edYs1Ooe3XiXo453Dg7w



Laurie, et al.          Expires November 10, 2006              [Page 24]

Internet-Draft                    nsec3                         May 2006


                              lqQoewuDzmtd6RaLNu52W44zTM1EHJES8ujP
                              U9VazOa1KEIq1w== )
   x.y.w.example. 3600 MX     1 xx.example.
                  3600 RRSIG  MX 5 4 3600 20050712112304 (
                              20050612112304 62699 example.
                              aKVCGO/Fx9rm04UUsHRTTYaDA8o8dGfyq6t7
                              uqAcYxU9xiXP+xNtLHBv7er6Q6f2JbOs6SGF
                              9VrQvJjwbllAfA== )
   wbyijvpnyj33pcpi3i44ecnibnaj7eiw.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              zjxfz5o7t4ty4u3f6fa7mhhqzjln4mui
                              A NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              ledFAaDCqDxapQ1FvBAjjK2DP06iQj8AN6gN
                              ZycTeSmobKLTpzbgQp8uKYYe/DPHjXYmuEhd
                              oorBv4xkb0flXw== )
   xx.example.    3600 A      192.0.2.10
                  3600 RRSIG  A 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              XSuMVjNxovbZUsnKU6oQDygaK+WB+O5HYQG9
                              tJgphHIX7TM4uZggfR3pNM+4jeC8nt2OxZZj
                              cxwCXWj82GVGdw== )
                  3600 HINFO  "KLH-10" "TOPS-20"
                  3600 RRSIG  HINFO 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              ghS2DimOqPSacG9j6KMgXSfTMSjLxvoxvx3q
                              OKzzPst4tEbAmocF2QX8IrSHr67m4ZLmd2Fk
                              KMf4DgNBDj+dIQ== )
                  3600 AAAA   2001:db8:0:0:0:0:f00:baaa
                  3600 RRSIG  AAAA 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              rto7afZkXYB17IfmQCT5QoEMMrlkeOoAGXzo
                              w8Wmcg86Fc+MQP0hyXFScI1gYNSgSSoDMXIy
                              rzKKwb8J04/ILw== )
   zjxfz5o7t4ty4u3f6fa7mhhqzjln4mui.example. 3600 NSEC3  0 1 1 (
                              deadbeaf
                              5pe7ctl7pfs2cilroy5dcofx4rcnlypd
                              MX NSEC3 RRSIG )
                  3600 RRSIG  NSEC3 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              eULkdWjcjmM+wXQcr7zXNfnGLgHjZSJINGkt
                              7Zmvp7WKVAqoHMm1RXV8IfBH1aRgv5+/Lgny
                              OcFlrPGPMm48/A== )







Laurie, et al.          Expires November 10, 2006              [Page 25]

Internet-Draft                    nsec3                         May 2006


Appendix B.  Example Responses

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

B.1.  answer

   A successful query to an authoritative server.











































Laurie, et al.          Expires November 10, 2006              [Page 26]

Internet-Draft                    nsec3                         May 2006


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

   ;; Answer
   x.w.example.   3600 IN MX  1 xx.example.
   x.w.example.   3600 IN RRSIG  MX 5 3 3600 20050712112304 (
                              20050612112304 62699 example.
                              s1XQ/8SlViiEDik9edYs1Ooe3XiXo453Dg7w
                              lqQoewuDzmtd6RaLNu52W44zTM1EHJES8ujP
                              U9VazOa1KEIq1w== )

   ;; Authority
   example.       3600 IN NS  ns1.example.
   example.       3600 IN NS  ns2.example.
   example.       3600 IN RRSIG  NS 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              hNyyin2JpECIFxW4vsj8RhHcWCQKUXgO+z4l
                              m7g2zM8q3Qpsm/gYIXSF2Rhj6lAG7esR/X9d
                              1SH5r/wfjuCg+g== )

   ;; Additional
   xx.example.    3600 IN A   192.0.2.10
   xx.example.    3600 IN RRSIG  A 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              XSuMVjNxovbZUsnKU6oQDygaK+WB+O5HYQG9
                              tJgphHIX7TM4uZggfR3pNM+4jeC8nt2OxZZj
                              cxwCXWj82GVGdw== )
   xx.example.    3600 IN AAAA   2001:db8::f00:baaa
   xx.example.    3600 IN RRSIG  AAAA 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              rto7afZkXYB17IfmQCT5QoEMMrlkeOoAGXzo
                              w8Wmcg86Fc+MQP0hyXFScI1gYNSgSSoDMXIy
                              rzKKwb8J04/ILw== )
   ns1.example.   3600 IN A   192.0.2.1
   ns1.example.   3600 IN RRSIG  A 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              QLGkaqWXxRuE+MHKkMvVlswg65HcyjvD1fyb
                              BDZpcfiMHH9w4x1eRqRamtSDTcqLfUrcYkrr
                              nWWLepz1PjjShQ== )
   ns2.example.   3600 IN A   192.0.2.2
   ns2.example.   3600 IN RRSIG  A 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              UoIZaC1O6XHRWGHBOl8XFQKPdYTkRCz6SYh3
                              P2mZ3xfY22fLBCBDrEnOc8pGDGijJaLl26Cz
                              AkeTJu3J3auUiA== )




Laurie, et al.          Expires November 10, 2006              [Page 27]

Internet-Draft                    nsec3                         May 2006


   The query returned an MX RRset for "x.w.example".  The corresponding
   RRSIG RR indicates that the MX RRset was signed by an "example"
   DNSKEY with algorithm 5 and key tag 62699.  The resolver needs the
   corresponding DNSKEY RR in order to authenticate this answer.  The
   discussion below describes how a resolver might obtain this DNSKEY
   RR.

   The RRSIG RR indicates the original TTL of the MX RRset was 3600,
   and, for the purpose of authentication, the current TTL is replaced
   by 3600.  The RRSIG RR's labels field value of 3 indicates that the
   answer was not the result of wildcard expansion.  The "x.w.example"
   MX RRset is placed in canonical form, and, assuming the current time
   falls between the signature inception and expiration dates, the
   signature is authenticated.

B.1.1.  Authenticating the Example DNSKEY RRset

   This example shows the logical authentication process that starts
   from a configured root DNSKEY RRset (or DS RRset) and moves down the
   tree to authenticate the desired "example" DNSKEY RRset.  Note that
   the logical order is presented for clarity.  An implementation may
   choose to construct the authentication as referrals are received or
   to construct the authentication chain only after all RRsets have been
   obtained, or in any other combination it sees fit.  The example here
   demonstrates only the logical process and does not dictate any
   implementation rules.

   We assume the resolver starts with a configured DNSKEY RRset for the
   root zone (or a configured DS RRset for the root zone).  The resolver
   checks whether this configured DNSKEY RRset is present in the root
   DNSKEY RRset (or whether a DS RR in the DS RRset matches some DNSKEY
   RR in the root DNSKEY RRset), whether this DNSKEY RR has signed the
   root DNSKEY RRset, and whether the signature lifetime is valid.  If
   all these conditions are met, all keys in the DNSKEY RRset are
   considered authenticated.  The resolver then uses one (or more) of
   the root DNSKEY RRs to authenticate the "example" DS RRset.  Note
   that the resolver may have to query the root zone to obtain the root
   DNSKEY RRset or "example" DS RRset.

   Once the DS RRset has been authenticated using the root DNSKEY, the
   resolver checks the "example" DNSKEY RRset for some "example" DNSKEY
   RR that matches one of the authenticated "example" DS RRs.  If such a
   matching "example" DNSKEY is found, the resolver checks whether this
   DNSKEY RR has signed the "example" DNSKEY RRset and the signature
   lifetime is valid.  If these conditions are met, all keys in the
   "example" DNSKEY RRset are considered authenticated.

   Finally, the resolver checks that some DNSKEY RR in the "example"



Laurie, et al.          Expires November 10, 2006              [Page 28]

Internet-Draft                    nsec3                         May 2006


   DNSKEY RRset uses algorithm 5 and has a key tag of 62699.  This
   DNSKEY is used to authenticate the RRSIG included in the response.
   If multiple "example" DNSKEY RRs match this algorithm and key tag,
   then each DNSKEY RR is tried, and the answer is authenticated if any
   of the matching DNSKEY RRs validate the signature as described above.

B.2.  Name Error

   An authoritative name error.  The NSEC3 RRs prove that the name does
   not exist and that no covering wildcard exists.









































Laurie, et al.          Expires November 10, 2006              [Page 29]

Internet-Draft                    nsec3                         May 2006


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

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       3600 IN SOA ns1.example. bugs.x.w.example. (
                              1
                              3600
                              300
                              3600000
                              3600
                              )
   example.       3600 IN RRSIG  SOA 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              RtctD6aLUU5Md5wOOItilS7JXX1tf58Ql3sK
                              mTXkL13jqLiUFOGg0uzqRh1U9GbydS0P7M0g
                              qYIt90txzE/4+g== )
   7nomf47k3vlidh4vxahhpp47l3tgv7a2.example. 3600 IN NSEC3  0 1 1 (
                              deadbeaf
                              dw4o7j64wnel3j4jh7fb3c5n7w3js2yb
                              MX NSEC3 RRSIG )
   7nomf47k3vlidh4vxahhpp47l3tgv7a2.example. 3600 IN RRSIG  NSEC3 (
                              5 2 3600 20050712112304
                              20050612112304 62699 example.
                              YTcqole3h8EOsTT3HKnwhR1QS8borR0XtZaA
                              ZrLsx6n0RDC1AAdZONYOvdqvcal9PmwtWjlo
                              MEFQmc/gEuxojA== )
   nimwfwcnbeoodmsc6npv3vuaagaevxxu.example. 3600 IN NSEC3  0 1 1 (
                              deadbeaf
                              vhgwr2qgykdkf4m6iv6vkagbxozphazr
                              HINFO A AAAA NSEC3 RRSIG )
   nimwfwcnbeoodmsc6npv3vuaagaevxxu.example. 3600 IN RRSIG  NSEC3 (
                              5 2 3600 20050712112304
                              20050612112304 62699 example.
                              c3zQdK68cYTHTjh1cD6pi0vblXwzyoU/m7Qx
                              z8kaPYikbJ9vgSl9YegjZukgQSwybHUC0SYG
                              jL33Wm1p07TBdw== )
   ;; Additional
   ;; (empty)

   The query returned two NSEC3 RRs that prove that the requested data
   does not exist and no wildcard applies.  The negative reply is
   authenticated by verifying both NSEC3 RRs.  The NSEC3 RRs are
   authenticated in a manner identical to that of the MX RRset discussed



Laurie, et al.          Expires November 10, 2006              [Page 30]

Internet-Draft                    nsec3                         May 2006


   above.  At least one of the owner names of the NSEC3 RRs will match
   the closest encloser.  At least one of the NSEC3 RRs prove that there
   exists no longer name.  At least one of the NSEC3 RRs prove that
   there exists no wildcard RRsets that should have been expanded.  The
   closest encloser can be found by hashing the apex ownername (The SOA
   RR's ownername, or the ownername of the DNSKEY RRset referred by an
   RRSIG RR), matching it to the ownername of one of the NSEC3 RRs, and
   if that fails, continue by adding labels.  In other words, the
   resolver first hashes example, checks for a matching NSEC3 ownername,
   then hashes w.example, checks, and finally hashes w.x.example and
   checks.

   In the above example, the name 'x.w.example' hashes to
   '7nomf47k3vlidh4vxahhpp47l3tgv7a2'.  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
   'qsgoxsf2lanysajhtmaylde4tqwnqppl' and
   'cvljzyf6nsckjowghch4tt3nohocpdka'.  The two NSEC3 records prove that
   these hashed ownernames do not exists, since the names are within the
   given intervals.

B.3.  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 November 10, 2006              [Page 31]

Internet-Draft                    nsec3                         May 2006


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

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       3600 IN SOA ns1.example. bugs.x.w.example. (
                              1
                              3600
                              300
                              3600000
                              3600
                              )
   example.       3600 IN RRSIG  SOA 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              RtctD6aLUU5Md5wOOItilS7JXX1tf58Ql3sK
                              mTXkL13jqLiUFOGg0uzqRh1U9GbydS0P7M0g
                              qYIt90txzE/4+g== )
   wbyijvpnyj33pcpi3i44ecnibnaj7eiw.example. 3600 IN NSEC3  0 1 1 (
                              deadbeaf
                              zjxfz5o7t4ty4u3f6fa7mhhqzjln4mui
                              A NSEC3 RRSIG )
   wbyijvpnyj33pcpi3i44ecnibnaj7eiw.example. 3600 IN RRSIG  NSEC3 (
                              5 2 3600 20050712112304
                              20050612112304 62699 example.
                              ledFAaDCqDxapQ1FvBAjjK2DP06iQj8AN6gN
                              ZycTeSmobKLTpzbgQp8uKYYe/DPHjXYmuEhd
                              oorBv4xkb0flXw== )
   ;; Additional
   ;; (empty)

   The query returned an NSEC3 RR that proves that the requested name
   exists ("ns1.example." hashes to "wbyijvpnyj33pcpi3i44ecnibnaj7eiw"),
   but the requested RR type does not exist (type MX is absent in the
   type code list of the NSEC RR).  The negative reply is authenticated
   by verifying the NSEC3 RR.  The NSEC3 RR is authenticated in a manner
   identical to that of the MX RRset discussed above.

B.3.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 November 10, 2006              [Page 32]

Internet-Draft                    nsec3                         May 2006


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

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       3600 IN SOA ns1.example. bugs.x.w.example. (
                              1
                              3600
                              300
                              3600000
                              3600
                              )
   example.       3600 IN RRSIG  SOA 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              RtctD6aLUU5Md5wOOItilS7JXX1tf58Ql3sK
                              mTXkL13jqLiUFOGg0uzqRh1U9GbydS0P7M0g
                              qYIt90txzE/4+g== )
   jt4bbfokgbmr57qx4nqucvvn7fmo6ab6.example. 3600 IN NSEC3  0 1 1 (
                              deadbeaf
                              kcll7fqfnisuhfekckeeqnmbbd4maanu
                              NSEC3 RRSIG )
   jt4bbfokgbmr57qx4nqucvvn7fmo6ab6.example. 3600 IN RRSIG  NSEC3 (
                              5 2 3600 20050712112304
                              20050612112304 62699 example.
                              FXyCVQUdFF1EW1NcgD2V724/It0rn3lr+30V
                              IyjmqwOMvQ4G599InTpiH46xhX3U/FmUzHOK
                              94Zbq3k8lgdpZA== )

   The query returned an NSEC3 RR that proves that the requested name
   exists ("y.w.example." hashes to "jt4bbfokgbmr57qx4nqucvvn7fmo6ab6"),
   but the requested RR type does not exist (Type A is absent in the
   type-bit-maps of the NSEC3 RR).  The negative reply is authenticated
   by verifying the NSEC3 RR.  The NSEC3 RR is authenticated in a manner
   identical to that of the MX RRset discussed above.  Note that, unlike
   generic empty non terminal proof using NSECs, this is identical to
   proving a No Data Error.  This example is solely mentioned to be
   complete.

B.4.  Referral to Signed Zone

   Referral to a signed zone.  The DS RR contains the data which the
   resolver will need to validate the corresponding DNSKEY RR in the
   child zone's apex.




Laurie, et al.          Expires November 10, 2006              [Page 33]

Internet-Draft                    nsec3                         May 2006


   ;; Header: QR DO RCODE=0
   ;;

   ;; Question
   mc.a.example.       IN MX

   ;; Answer
   ;; (empty)

   ;; Authority
   a.example.     3600 IN NS  ns1.a.example.
   a.example.     3600 IN NS  ns2.a.example.
   a.example.     3600 IN DS  58470 5 1 (
                              3079F1593EBAD6DC121E202A8B766A6A4837
                              206C )
   a.example.     3600 IN RRSIG  DS 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              QavhbsSmEvJLSUzGoTpsV3SKXCpaL1UO3Ehn
                              cB0ObBIlex/Zs9kJyG/9uW1cYYt/1wvgzmX2
                              0kx7rGKTc3RQDA== )

   ;; Additional
   ns1.a.example. 3600 IN A   192.0.2.5
   ns2.a.example. 3600 IN A   192.0.2.6

   The query returned a referral to the signed "a.example." zone.  The
   DS RR is authenticated in a manner identical to that of the MX RRset
   discussed above.  This DS RR is used to authenticate the "a.example"
   DNSKEY RRset.

   Once the "a.example" DS RRset has been authenticated using the
   "example" DNSKEY, the resolver checks the "a.example" DNSKEY RRset
   for some "a.example" DNSKEY RR that matches the DS RR.  If such a
   matching "a.example" DNSKEY is found, the resolver checks whether
   this DNSKEY RR has signed the "a.example" DNSKEY RRset and whether
   the signature lifetime is valid.  If all these conditions are met,
   all keys in the "a.example" DNSKEY RRset are considered
   authenticated.

B.5.  Referral to Unsigned Zone using the Opt-Out Flag

   The NSEC3 RR proves that nothing for this delegation was signed in
   the parent zone.  There is no proof that the delegation exists








Laurie, et al.          Expires November 10, 2006              [Page 34]

Internet-Draft                    nsec3                         May 2006


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

   ;; Answer
   ;; (empty)

   ;; Authority
   b.example.     3600 IN NS  ns1.b.example.
   b.example.     3600 IN NS  ns2.b.example.
   kcll7fqfnisuhfekckeeqnmbbd4maanu.example. 3600 IN NSEC3  1 1 1 (
                              deadbeaf
                              n42hbhnjj333xdxeybycax5ufvntux5d
                              MX NSEC3 RRSIG )
   kcll7fqfnisuhfekckeeqnmbbd4maanu.example. 3600 IN RRSIG  NSEC3 (
                              5 2 3600 20050712112304
                              20050612112304 62699 example.
                              d0g8MTOvVwByOAIwvYV9JrTHwJof1VhnMKuA
                              IBj6Xaeney86RBZYgg7Qyt9WnQSK3uCEeNpx
                              TOLtc5jPrkL4zQ== )

   ;; Additional
   ns1.b.example. 3600 IN A   192.0.2.7
   ns2.b.example. 3600 IN A   192.0.2.8

   The query returned a referral to the unsigned "b.example." zone.  The
   NSEC3 proves that no authentication leads from "example" to
   "b.example", since the hash of "b.example"
   ("ldjpfcucebeks5azmzpty4qlel4cftzo") is within the NSEC3 interval and
   the NSEC3 Opt-Out bit is set.  The NSEC3 RR is authenticated in a
   manner identical to that of the MX RRset discussed above.

B.6.  Wildcard Expansion

   A successful query that was answered via 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 closer match exists in the zone.












Laurie, et al.          Expires November 10, 2006              [Page 35]

Internet-Draft                    nsec3                         May 2006


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

   ;; Answer
   a.z.w.example. 3600 IN MX  1 ai.example.
   a.z.w.example. 3600 IN RRSIG  MX 5 3 3600 20050712112304 (
                              20050612112304 62699 example.
                              sYNUPHn1/gJ87wTHNksGdRm3vfnSFa2BbofF
                              xGfJLF5A4deRu5f0hvxhAFDCcXfIASj7z0wQ
                              gQlgxEwhvQDEaQ== )
   ;; Authority
   example.       3600 NS     ns1.example.
   example.       3600 NS     ns2.example.
   example.       3600 IN RRSIG  NS 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              hNyyin2JpECIFxW4vsj8RhHcWCQKUXgO+z4l
                              m7g2zM8q3Qpsm/gYIXSF2Rhj6lAG7esR/X9d
                              1SH5r/wfjuCg+g== )
   zjxfz5o7t4ty4u3f6fa7mhhqzjln4mui.example. 3600 IN NSEC3  0 1 1 (
                              deadbeaf
                              5pe7ctl7pfs2cilroy5dcofx4rcnlypd
                              MX NSEC3 RRSIG )
   zjxfz5o7t4ty4u3f6fa7mhhqzjln4mui.example. 3600 IN RRSIG  NSEC3 (
                              5 2 3600 20050712112304
                              20050612112304 62699 example.
                              eULkdWjcjmM+wXQcr7zXNfnGLgHjZSJINGkt
                              7Zmvp7WKVAqoHMm1RXV8IfBH1aRgv5+/Lgny
                              OcFlrPGPMm48/A== )
   ;; Additional
   ai.example.    3600 IN A   192.0.2.9
   ai.example.    3600 IN RRSIG  A 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              plY5M26ED3Owe3YX0pBIhgg44j89NxUaoBrU
                              6bLRr99HpKfFl1sIy18JiRS7evlxCETZgubq
                              ZXW5S+1VjMZYzQ== )
   ai.example.    3600 AAAA   2001:db8::f00:baa9
   ai.example.    3600 IN RRSIG  AAAA 5 2 3600 20050712112304 (
                              20050612112304 62699 example.
                              PNF/t7+DeosEjhfuL0kmsNJvn16qhYyLI9FV
                              ypSCorFx/PKIlEL3syomkYM2zcXVSRwUXMns
                              l5/UqLCJJ9BDMg== )

   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, and the
   corresponding RRSIG indicates that the expanded wildcard MX RRset was



Laurie, et al.          Expires November 10, 2006              [Page 36]

Internet-Draft                    nsec3                         May 2006


   signed by an "example" DNSKEY with algorithm 5 and key tag 62699.
   The RRSIG indicates that the original TTL of the MX RRset was 3600,
   and, for the purpose of authentication, the current TTL is replaced
   by 3600.  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.  The name "a.z.w.example" is replaced by
   "*.w.example", the MX RRset is placed in canonical form, and,
   assuming that the current time falls between the signature inception
   and expiration dates, the signature is authenticated.

   The NSEC3 proves that no closer match (exact or closer wildcard)
   could have been used to answer this query, and the NSEC3 RR must also
   be authenticated before the answer is considered valid.

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
































Laurie, et al.          Expires November 10, 2006              [Page 37]

Internet-Draft                    nsec3                         May 2006


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

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       3600 IN SOA ns1.example. bugs.x.w.example. (
                              1
                              3600
                              300
                              3600000
                              3600
                              )
   example.       3600 IN RRSIG  SOA 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              RtctD6aLUU5Md5wOOItilS7JXX1tf58Ql3sK
                              mTXkL13jqLiUFOGg0uzqRh1U9GbydS0P7M0g
                              qYIt90txzE/4+g== )
   zjxfz5o7t4ty4u3f6fa7mhhqzjln4mui.example. 3600 IN NSEC3  0 1 1 (
                              deadbeaf
                              5pe7ctl7pfs2cilroy5dcofx4rcnlypd
                              MX NSEC3 RRSIG )
   zjxfz5o7t4ty4u3f6fa7mhhqzjln4mui.example. 3600 IN RRSIG  NSEC3 (
                              5 2 3600 20050712112304
                              20050612112304 62699 example.
                              eULkdWjcjmM+wXQcr7zXNfnGLgHjZSJINGkt
                              7Zmvp7WKVAqoHMm1RXV8IfBH1aRgv5+/Lgny
                              OcFlrPGPMm48/A== )
   ;; Additional
   ;; (empty)

   The query returned NSEC3 RRs that prove that the requested data does
   not exist and no wildcard applies.  The negative reply is
   authenticated by verifying both NSEC3 RRs.

B.8.  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 November 10, 2006              [Page 38]

Internet-Draft                    nsec3                         May 2006


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

   ;; Answer
   ;; (empty)

   ;; Authority
   example.       3600 IN SOA ns1.example. bugs.x.w.example. (
                              1
                              3600
                              300
                              3600000
                              3600
                              )
   example.       3600 IN RRSIG  SOA 5 1 3600 20050712112304 (
                              20050612112304 62699 example.
                              RtctD6aLUU5Md5wOOItilS7JXX1tf58Ql3sK
                              mTXkL13jqLiUFOGg0uzqRh1U9GbydS0P7M0g
                              qYIt90txzE/4+g== )
   dw4o7j64wnel3j4jh7fb3c5n7w3js2yb.example. 3600 IN NSEC3  0 1 1 (
                              deadbeaf
                              gmnfcccja7wkax3iv26bs75myptje3qk
                              MX DNSKEY NS SOA NSEC3 RRSIG )
   dw4o7j64wnel3j4jh7fb3c5n7w3js2yb.example. 3600 IN RRSIG  NSEC3 (
                              5 2 3600 20050712112304
                              20050612112304 62699 example.
                              VqEbXiZLJVYmo25fmO3IuHkAX155y8NuA50D
                              C0NmJV/D4R3rLm6tsL6HB3a3f6IBw6kKEa2R
                              MOiKMSHozVebqw== )

   ;; Additional
   ;; (empty)

   The query returned NSEC RRs that shows the requested was answered by
   a child server ("example" server).  The NSEC RR indicates the
   presence of an SOA RR, showing that the answer is from the child .
   Queries for the "example" DS RRset should be sent to the parent
   servers ("root" servers).


Appendix C.  Special Considerations

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





Laurie, et al.          Expires November 10, 2006              [Page 39]

Internet-Draft                    nsec3                         May 2006


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
   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 precomputation
   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



Laurie, et al.          Expires November 10, 2006              [Page 40]

Internet-Draft                    nsec3                         May 2006


   collisions.

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




Laurie, et al.          Expires November 10, 2006              [Page 41]

Internet-Draft                    nsec3                         May 2006


   Though the mentioned truncation can be maximized to a certain
   extreme, the probability of collision increases exponentially for
   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.

C.2.4.  Server Response to a Run-time Collision

   In the astronomically unlikely event that a server is unable to prove
   nonexistence because the hash of the name that does not exist
   collides with a name that does exist, the server is obviously broken,
   and should, therefore, return a response with an RCODE of 2 (server
   failure).































Laurie, et al.          Expires November 10, 2006              [Page 42]

Internet-Draft                    nsec3                         May 2006


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 November 10, 2006              [Page 43]

Internet-Draft                    nsec3                         May 2006


Intellectual Property Statement

   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.


Disclaimer of Validity

   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.


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.


Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.




Laurie, et al.          Expires November 10, 2006              [Page 44]


Html markup produced by rfcmarkup 1.107, available from http://tools.ietf.org/tools/rfcmarkup/