[Docs] [txt|pdf|xml] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 05 06 07 08

Network Working Group                                          J. Vcelak
Internet-Draft                                                    CZ.NIC
Intended status: Standards Track                             S. Goldberg
Expires: March 24, 2016                                Boston University
                                                      September 21, 2015


            NSEC5, DNSSEC Authenticated Denial of Existence
                         draft-vcelak-nsec5-01

Abstract

   The Domain Name System Security (DNSSEC) Extensions introduced the
   NSEC resource record (RR) for authenticated denial of existence and
   the NSEC3 for hashed authenticated denial of existence.  The NSEC RR
   allows for the entire zone contents to be enumerated if a server is
   queried for carefully chosen domain names; N queries suffice to
   enumerate a zone containing N names.  The NSEC3 RR adds domain-name
   hashing, which makes the zone enumeration harder, but not impossible.
   This document introduces NSEC5, which provides an cryptographically-
   proven mechanism that prevents zone enumeration.  NSEC5 has the
   additional advantage of not requiring private zone-signing keys to be
   present on all authoritative servers for the zone.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

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

   This Internet-Draft will expire on March 24, 2016.

Copyright Notice

   Copyright (c) 2015 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents



Vcelak & Goldberg        Expires March 24, 2016                 [Page 1]


Internet-Draft                    NSEC5                   September 2015


   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Rationale . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.2.  Requirements  . . . . . . . . . . . . . . . . . . . . . .   4
     1.3.  Terminology . . . . . . . . . . . . . . . . . . . . . . .   4
   2.  Backward Compatibility  . . . . . . . . . . . . . . . . . . .   5
   3.  How NSEC5 Works . . . . . . . . . . . . . . . . . . . . . . .   5
   4.  NSEC5 Algorithms  . . . . . . . . . . . . . . . . . . . . . .   6
   5.  The NSEC5KEY Resource Record  . . . . . . . . . . . . . . . .   7
     5.1.  NSEC5KEY RDATA Wire Format  . . . . . . . . . . . . . . .   7
     5.2.  NSEC5KEY RDATA Presentation Format  . . . . . . . . . . .   7
   6.  The NSEC5 Resource Record . . . . . . . . . . . . . . . . . .   7
     6.1.  NSEC5 RDATA Wire Format . . . . . . . . . . . . . . . . .   7
     6.2.  NSEC5 Flags Field . . . . . . . . . . . . . . . . . . . .   8
     6.3.  NSEC5 RDATA Presentation Format . . . . . . . . . . . . .   9
   7.  The NSEC5PROOF Resource Record  . . . . . . . . . . . . . . .   9
     7.1.  NSEC5PROOF RDATA Wire Format  . . . . . . . . . . . . . .   9
     7.2.  NSEC5PROOF RDATA Presentation Format  . . . . . . . . . .  10
   8.  NSEC5 Proofs  . . . . . . . . . . . . . . . . . . . . . . . .  10
     8.1.  Name Error Responses  . . . . . . . . . . . . . . . . . .  10
     8.2.  No Data Responses . . . . . . . . . . . . . . . . . . . .  11
       8.2.1.  No Data Response, Opt-Out Not In Effect . . . . . . .  11
       8.2.2.  No Data Response, Opt-Out In Effect . . . . . . . . .  12
     8.3.  Wildcard Responses  . . . . . . . . . . . . . . . . . . .  12
     8.4.  Wildcard No Data Responses  . . . . . . . . . . . . . . .  12
   9.  Authoritative Server Considerations . . . . . . . . . . . . .  13
     9.1.  Zone Signing  . . . . . . . . . . . . . . . . . . . . . .  13
     9.2.  Zone Serving  . . . . . . . . . . . . . . . . . . . . . .  14
     9.3.  NSEC5KEY Rollover Mechanism . . . . . . . . . . . . . . .  15
     9.4.  Secondary Servers . . . . . . . . . . . . . . . . . . . .  16
     9.5.  Zones Using Unknown Hash Algorithms . . . . . . . . . . .  16
     9.6.  Dynamic Updates . . . . . . . . . . . . . . . . . . . . .  16
   10. Resolver Considerations . . . . . . . . . . . . . . . . . . .  16
   11. Validator Considerations  . . . . . . . . . . . . . . . . . .  16
     11.1.  Validating Responses . . . . . . . . . . . . . . . . . .  16
     11.2.  Validating Referrals to Unsigned Subzones  . . . . . . .  17
     11.3.  Responses With Unknown Hash Algorithms . . . . . . . . .  17
   12. Special Considerations  . . . . . . . . . . . . . . . . . . .  18
     12.1.  Transition Mechanism . . . . . . . . . . . . . . . . . .  18



Vcelak & Goldberg        Expires March 24, 2016                 [Page 2]


Internet-Draft                    NSEC5                   September 2015


     12.2.  NSEC5 Private Keys . . . . . . . . . . . . . . . . . . .  18
     12.3.  Domain Name Length Restrictions  . . . . . . . . . . . .  18
   13. Performance Considerations  . . . . . . . . . . . . . . . . .  19
     13.1.  Performance of Cryptographic Operations  . . . . . . . .  19
     13.2.  Authoritative Server Startup . . . . . . . . . . . . . .  20
     13.3.  NSEC5 Answer Generating and Processing . . . . . . . . .  21
   14. Security Considerations . . . . . . . . . . . . . . . . . . .  24
     14.1.  Zone Enumeration Attacks . . . . . . . . . . . . . . . .  24
     14.2.  Hash Collisions  . . . . . . . . . . . . . . . . . . . .  24
     14.3.  Compromise of the Private NSEC5 Key  . . . . . . . . . .  24
     14.4.  Key Length Considerations  . . . . . . . . . . . . . . .  25
     14.5.  Transitioning to a New NSEC5 Algorithm . . . . . . . . .  25
   15. IANA Considerations . . . . . . . . . . . . . . . . . . . . .  25
   16. Contributors  . . . . . . . . . . . . . . . . . . . . . . . .  26
   17. References  . . . . . . . . . . . . . . . . . . . . . . . . .  26
     17.1.  Normative References . . . . . . . . . . . . . . . . . .  26
     17.2.  Informative References . . . . . . . . . . . . . . . . .  27
   Appendix A.  Full Domain Hash Algorithm . . . . . . . . . . . . .  28
     A.1.  FDH signature . . . . . . . . . . . . . . . . . . . . . .  28
     A.2.  FDH verification  . . . . . . . . . . . . . . . . . . . .  29
   Appendix B.  Change Log . . . . . . . . . . . . . . . . . . . . .  29
   Appendix C.  Open Issues  . . . . . . . . . . . . . . . . . . . .  30

1.  Introduction

1.1.  Rationale

   The DNS Security Extensions (DNSSEC) provides data integrity
   protection using public-key cryptography, while not requiring that
   authoritative servers compute signatures on-the-fly.  The content of
   the zone is usually pre-computed and served as is.  The evident
   advantages of this approach are reduced performance requirements per
   query, as well as not requiring private zone-signing keys to be
   present on nameservers facing the network.

   With DNSSEC, each resource record (RR) set in the zone is signed.
   The signature is retained as an RRSIG RR directly in the zone.  This
   enables response authentication for data existing in the zone.  To
   ensure integrity of denying answers, an NSEC chain of all existing
   domain names in the zone is constructed.  The chain is made of RRs,
   where each RR represents two consecutive domain names in canonical
   order present in the zone.  The NSEC RRs are signed the same way as
   any other RRs in the zone, and each NSEC can be used to prove that a
   given name does not existing in a part of the domain name space.

   As side-effect, however, the NSEC chain allows for enumeration of the
   zone's contents by sequentially querying for the names immediately
   following those in the most-recently retrieved NSEC record; N queries



Vcelak & Goldberg        Expires March 24, 2016                 [Page 3]


Internet-Draft                    NSEC5                   September 2015


   suffice to enumerate a zone containing N names.  As such, the NSEC3
   hashed denial of existence was introduced to prevent zone
   enumeration.  In NSEC3, the original domain names in the NSEC chain
   are replaced by their cryptographic hashes.  While NSEC3 makes zone
   enumeration more difficult, offline dictionary attacks are still
   possible and have been demonstrated; this is because hashes may be
   computed offline and the space of possible domain names is restricted
   [nsec3walker][nsec3gpu].

   Zone enumeration can be prevented with NSEC3 if having the
   authoritative server compute NSEC3 RRs on-the-fly, in response to
   queries with denying responses.  Usually, this is done with Minimally
   Covering NSEC Records or NSEC3 White Lies [RFC7129].  One of the most
   significant disadvantage of this approach is a required presence of
   the private key on all authoritative servers for the zone.  This is
   often undesirable, as the holder of the private key can tamper with
   the zone content, and having private keys on many network-facing
   servers increases the risk that keys can be compromised.

   To prevent zone content enumeration without keeping private keys on
   all authoritative servers, NSEC5 replaces the unkeyed cryptographic
   hash function used in NSEC3 with a public-key hashing scheme.
   Hashing in NSEC5 is performed with a separate NSEC5 key.  The public
   portion of this key is distributed in an NSEC5KEY RR, and is used to
   validate NSEC5 hash values.  The private portion of the NSEC5 key is
   present on all authoritative servers for the zone, and is used to
   compute hash values.

   Importantly, the NSEC5KEY key cannot be used to modify the contents
   of the zone.  Thus, any compromise of the private NSEC5 key does not
   lead to a compromise of zone contents; all that is lost is privacy
   against zone enumeration, effectively downgrading the security of
   NSEC5 to that of NSEC3.  NSEC5 comes with a cryptographic proof of
   security, available in [nsec5].

   The NSEC5 is not intended to replace NSEC or NSEC3.  It is designed
   as an alternative mechanism for authenticated denial of existence.

1.2.  Requirements

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

1.3.  Terminology

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



Vcelak & Goldberg        Expires March 24, 2016                 [Page 4]


Internet-Draft                    NSEC5                   September 2015


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

   The following terminology is used through this document:

   Base32hex:  The "Base 32 Encoding with Extended Hex Alphabet" as
      specified in [RFC4648].  The padding characters ("=") are not used
      in NSEC5 specification.

   Base64:  The "Base 64 Encoding" as specified in [RFC4648].

   NSEC5 proof:  A signed hash of a domain name (hash-and-sign
      paradigm).  A holder of the private key (e.g., authoritative
      server) can compute the proof.  Anyone knowing the public key
      (e.g., client) can verify it's validity.

   NSEC5 hash:  A cryptographic hash (digest) of an NSEC5 proof.  If the
      NSEC5 proof is known, anyone can compute and verify it's NSEC5
      hash.

   NSEC5 algorithm:  A pair of algorithms used to compute NSEC5 proofs
      and NSEC5 hashes.

2.  Backward Compatibility

   The specification describes a protocol change that is not backward
   compatible with [RFC4035] and [RFC5155].  NSEC5-unaware resolver will
   fail to validate responses introduced by this document.

   To prevent NSEC5-unaware resolvers from attempting to validate the
   responses, new DNSSEC algorithms identifiers are introduced, the
   identifiers alias with existing algorithm numbers.  The zones signed
   according to this specification MUST use only these algorithm
   identifiers, thus NSEC5-unaware resolvers will treat the zone as
   insecure.

   The new algorithm identifiers defined by this document are listed in
   Section 15.

3.  How NSEC5 Works

   To prove non-existence of a domain name in a zone, NSEC uses a chain
   built from domain names present in the zone.  NSEC3 replaces the
   original domain names by their cryptographic hashes.  NSEC5 is very
   similar to NSEC3, however a public-key based hashing scheme is used.

   In NSEC5, the original domain name is hashed twice:




Vcelak & Goldberg        Expires March 24, 2016                 [Page 5]


Internet-Draft                    NSEC5                   September 2015


   1.  First, the domain name is hashed using the NSEC5 private key; the
       result is called the NSEC5 proof.  Only an authoritative server
       that knows the private NSEC5 key can compute the NSEC5 proof.
       Any client that knows the public NSEC5 key can validate the NSEC5
       proof.

   2.  Second, the NSEC5 proof is hashed using a cryptographic hash
       function; the result is called the NSEC5 hash.  This hash can be
       computed by any party that knows the input NSEC5 proof.

   The NSEC5 hash determines the position of a domain name in an NSEC5
   chain.  That is, all the NSEC5 hashes for a zone are sorted in their
   canonical order, and each consecutive pair forms an NSEC5 RR.

   To prove an non-existence of a particular domain name in response to
   a query, the server computes on the fly, the NSEC5 proof (using the
   private NSEC5 key).  Then it uses the NSEC5 proof to compute the
   corresponding NSEC5 hash.  It then identifies the NSEC5 RR that
   covers the hash.  In the response message, the server returns the
   NSEC5 RR, it's corresponding signature (RRSIG RRset), and synthesized
   NSEC5PROOF RR containing the NSEC5 proof it computed on the fly.

   To validate the response, the client first uses the public NSEC5 key
   (stored in the zone as an NSEC5KEY RR) to verify that the NSEC5 proof
   corresponds with the domain name to be disproved.  Then, the client
   computes the NSEC5 hash from the NSEC5 proof and checks if the NSEC5
   RR content and it's signature are valid.

4.  NSEC5 Algorithms

   The algorithms used for NSEC5 authenticated denial are independent of
   the algorithms used for DNSSEC signing.  An NSEC5 algorithm defines
   how the NSEC5 proof and the NSEC5 hash is computed and validated.

   The input for the NSEC5 proof computation is an RR owner name in the
   canonical form in the wire format and an NSEC5 private key; the
   output is an octet string.

   The input for the NSEC5 hash computation is the corresponding NSEC5
   proof; the output is an octet string.

   This document defines FDH-SHA256-SHA256 NSEC5 algorithm as follows:

   o  NSEC5 proof is an RSA based Full Domain Hash (FDH) with SHA-256
      hash function used internally for input preprocessing.  The FDH
      signature and verification is formally specified in Appendix A.

   o  NSEC5 hash is an SHA-256 hash function as specified in [RFC6234].



Vcelak & Goldberg        Expires March 24, 2016                 [Page 6]


Internet-Draft                    NSEC5                   September 2015


   o  The public key format to be used in NSEC5KEY RR is defined in
      Section 2 of [RFC3110] and thus is the same as the format used to
      store RSA public keys in DNSKEY RRs.

   The NSEC5 algorithm identifier for FDH-SHA256-SHA256 is 1.

5.  The NSEC5KEY Resource Record

   The NSEC5KEY RR stores an NSEC5 public key.  The key allows clients
   to verify a validity of NSEC5 proof sent by a server.

5.1.  NSEC5KEY RDATA Wire Format

   The RDATA for NSEC5KEY 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
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |   Algorithm   |                  Public Key                   /
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Algorithm is a single octet identifying NSEC5 algorithm.

   Public Key is a variable sized field holding public key material for
   NSEC5 proof verification.

5.2.  NSEC5KEY RDATA Presentation Format

   The presentation format of the NSEC5KEY RDATA is as follows:

   The Algorithm field is represented as an unsigned decimal integer.

   The Public Key field is represented in Base64 encoding.  Whitespace
   is allowed within the Base64 text.

6.  The NSEC5 Resource Record

   The NSEC5 RR provides authenticated denial of existence for an RRset.
   One NSEC5 RR represents one piece of an NSEC5 chain, proving
   existence of RR types present at the original domain name and also
   non-existence of other domain names in a part of the hashed domain
   name space.

6.1.  NSEC5 RDATA Wire Format

   The RDATA for NSEC5 RR is as shown below:




Vcelak & Goldberg        Expires March 24, 2016                 [Page 7]


Internet-Draft                    NSEC5                   September 2015


                          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
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |            Key Tag            |     Flags     |  Next Length  |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                     Next Hashed Owner Name                    /
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     /                         Type Bit Maps                         /
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Key Tag field contains the key tag value of the NSEC5KEY RR that
   validates the NSEC5 RR, in network byte order.  The value is computed
   from the NSEC5KEY RDATA using the same algorithm, which is used to
   compute key tag values for DNSKEY RRs.  The algorithm is defined in
   [RFC4034].

   Flags field is a single octet.  The meaning of individual bits of the
   field is defined in Section 6.2.

   Next length is an unsigned single octet specifying the length of the
   Next Hashed Owner Name field in octets.

   Next Hashed Owner Name field is a sequence of binary octets.  It
   contains an NSEC5 hash of the next domain name in the NSEC5 chain.

   Type Bit Maps is a variable sized field encoding RR types present at
   the original owner name matching the NSEC5 RR.  The format of the
   field is equivalent to the format used in NSEC3 RR, described in
   [RFC5155].

6.2.  NSEC5 Flags Field

   The following one-bit NSEC5 flags are defined:

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


      O - Opt-Out flag

      W - Wildcard flag

   All the other flags are reserved for future use and MUST be zero.





Vcelak & Goldberg        Expires March 24, 2016                 [Page 8]


Internet-Draft                    NSEC5                   September 2015


   The Opt-Out flag has the same semantics as in NSEC3.  The definition
   and considerations in [RFC5155] are valid, except that NSEC3 is
   replaced by NSEC5.

   The Wildcard flag indicates that a wildcard synthesis is possible at
   the original domain name level (i.e., there is a wildcard node
   immediately descending from the immediate ancestor of the original
   domain name).  The purpose of the Wildcard flag is to reduce a
   maximum number of RRs required for authenticated denial of existence
   proof.

6.3.  NSEC5 RDATA Presentation Format

   The presentation format of the NSEC5 RDATA is as follows:

   The Key Tag field is represented as an unsigned decimal integer.

   The Flags field is represented as an unsigned decimal integer.

   The Next Length field is not represented.

   The Next Hashed Owner Name field is represented as a sequence of
   case-insensitive Base32hex digits without any whitespace and without
   padding.

   The Type Bit Maps representation is equivalent to the representation
   used in NSEC3 RR, described in [RFC5155].

7.  The NSEC5PROOF Resource Record

   The NSEC5PROOF record is synthesized by the authoritative server on-
   the-fly.  The record contains the NSEC5 proof, proving a position of
   the owner name in an NSEC5 chain.

7.1.  NSEC5PROOF RDATA Wire Format

   The RDATA for NSEC5PROOF is as 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
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |            Key Tag            |        Owner Name Hash        /
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


   Key Tag field contains the key tag value of the NSEC5KEY RR that
   validates the NSEC5PROOF RR, in network byte order.




Vcelak & Goldberg        Expires March 24, 2016                 [Page 9]


Internet-Draft                    NSEC5                   September 2015


   Owner Name Hash is a variable sized sequence of binary octets
   encoding the NSEC5 proof of the owner name of the RR.

7.2.  NSEC5PROOF RDATA Presentation Format

   The presentation format of the NSEC5PROOF RDATA is as follows:

   The Key Tag field is represented as an unsigned decimal integer.

   The Owner Name Hash is represented in Base64 encoding.  Whitespace is
   allowed within the Base64 text.

8.  NSEC5 Proofs

   This section summarizes all possible types of authenticated denial of
   existence.  For each type the following lists are included:

   1.  Facts to prove.  The minimum amount of information an
       authoritative server must provide to a client to assure the
       client that the response content is valid.

   2.  Authoritative server proofs.  NSEC5 RRs an authoritative server
       must include in a response to prove the listed facts.

   3.  Validator checks.  Individual checks a validating server is
       required to perform on a response.  The response content is
       considered valid only if all the checks pass.

   If NSEC5 is said to match a domain name, the owner name of the NSEC5
   has to be equivalent to an NSEC5 hash of that domain name.  If NSEC5
   is said to cover a domain name, the NSEC5 hash of that name must lay
   strictly between the NSEC5 owner name and the NSEC5 Next Hashed Owner
   Name.

8.1.  Name Error Responses

   Facts to prove:

      No RRset matching the QNAME exactly exists.

      No RRset matching the QNAME via wildcard expansion exists.

      The QNAME does not fall into a delegation.

      The QNAME does not fall into a DNAME redirection.

   Authoritative server proofs:




Vcelak & Goldberg        Expires March 24, 2016                [Page 10]


Internet-Draft                    NSEC5                   September 2015


      Closest encloser.

      Next closer name.

   Validator checks:

      Closest encloser belongs to the zone.

      Closest encloser has the Wildcard flag cleared.

      Closest encloser does not have NS without SOA in the Type Bit Map.

      Closest encloser does not have DNAME in the Type Bit Maps.

      Next closer name is derived correctly.

8.2.  No Data Responses

   The processing of a No Data response for DS QTYPE differs if the Opt-
   Out is in effect.  For DS QTYPE queries, the validator has two
   possible checking paths.  The correct path can be simply decided by
   inspecting if the NSEC5 RR in the response matches the QNAME.

   Note that the Opt-Out is valid only for DS QTYPE queries.

8.2.1.  No Data Response, Opt-Out Not In Effect

   Facts to prove:

      An RRset matching the QNAME exists.

      No QTYPE RRset matching the QNAME exists.

      No CNAME RRset matching the QNAME exists.

   Authoritative server proofs:

      QNAME.

   Validator checks:

      The NSEC5 RR exactly matches the QNAME.

      The NSEC5 RR does not have QTYPE in the Type Bit Map.

      The NSEC5 RR does not have CNAME in the Type Bit Map.





Vcelak & Goldberg        Expires March 24, 2016                [Page 11]


Internet-Draft                    NSEC5                   September 2015


8.2.2.  No Data Response, Opt-Out In Effect

   Facts to prove:

      The delegation is not covered by the NSEC5 chain.

   Authoritative server proofs:

      Closest provable encloser.

   Validator checks:

      Closest provable encloser is in zone.

      Closest provable encloser covers (not matches) the QNAME.

      Closest provable encloser has the Opt-Out flag set.

8.3.  Wildcard Responses

   Facts to prove:

      No RRset matching the QNAME exactly exists.

      No wildcard closer to the QNAME exists.

   Authoritative server proofs:

      Next closer name.

   Validator checks:

      Next closer name is derived correctly.

      Next closer name covers (not matches).

8.4.  Wildcard No Data Responses

   Facts to prove:

      No RRset matching the QNAME exactly exists.

      No QTYPE RRset exists at the wildcard matching the QNAME.

      No CNAME RRset exists at the wildcard matching the QNAME.

      No wildcard closer to the QNAME exists.




Vcelak & Goldberg        Expires March 24, 2016                [Page 12]


Internet-Draft                    NSEC5                   September 2015


   Authoritative server proofs:

      Source of synthesis (i.e., wildcard at closest encloser).

      Next closer name.

   Validator checks:

      Source of synthesis matches exactly the QNAME.

      Source of synthesis does not have QTYPE in the Type Bit Map.

      Source of synthesis does not have CNAME in the Type Bit Map.

      Next closer name is derived correctly.

      Next closer name covers (not matches).

9.  Authoritative Server Considerations

9.1.  Zone Signing

   Zones using NSEC5 MUST satisfy the same properties as described in
   Section 7.1 of [RFC5155], with NSEC3 replaced by NSEC5.  In addition,
   the following conditions MUST be satisfied as well:

   o  If the original owner name has a wildcard label immediately
      descending from the original owner name, the corresponding NSEC5
      RR MUST have the Wildcard flag set in the Flags field.  Otherwise,
      the flag MUST be cleared.

   o  The zone apex MUST include an NSEC5KEY RRset containing a NSEC5
      public key allowing verification of the current NSEC5 chain.

   The following steps describe one possible method to properly add
   required NSEC5 related records into a zone.  This is not the only
   such existing method.

   1.  Select an algorithm for NSEC5.  Generate the public and private
       NSEC5 keys.

   2.  Add a NSEC5KEY RR into the zone apex containing the public NSEC5
       key.

   3.  For each unique original domain name in the zone and each empty
       non-terminal, add an NSEC5 RR.  If Opt-Out is used, owner names
       of unsigned delegations MAY be excluded.




Vcelak & Goldberg        Expires March 24, 2016                [Page 13]


Internet-Draft                    NSEC5                   September 2015


       a.  The owner name of the NSEC5 RR is the NSEC5 hash of the
           original owner name encoded in Base32hex without padding,
           prepended as a single label to the zone name.

       b.  Set the Key Tag field to be the key tag corresponding to the
           public NSEC5 key.

       c.  Clear the Flags field.  If Opt-Out is being used, set the
           Opt-Out flag.  If there is a wildcard label directly
           descending from the original domain name, set the Wildcard
           flag.  Note that the wildcard can be an empty non-terminal
           (i.e., the wildcard synthesis does not take effect and
           therefore the flag is not to be set).

       d.  Set the Next Length field to a value determined by the used
           NSEC5 algorithm.  Leave the Next Hashed Owner Name field
           blank.

       e.  Set the Type Bit Maps field based on the RRsets present at
           the original owner name.

   4.  Sort the set of NSEC5 RRs into canonical order.

   5.  For each NSEC5 RR, set the Next Hashed Owner Name field by using
       the owner name of the next NSEC5 RR in the canonical order.  If
       the updated NSEC5 is the last NSEC5 RR in the chain, the owner
       name of the first NSEC5 RR in the chain is used instead.

   The NSEC5KEY and NSEC5 RRs MUST have the same class as the zone SOA
   RR.  Also the NSEC5 RRs SHOULD have the same TTL value as the SOA
   minimum TTL field.

   Notice that a use of Opt-Out is not indicated in the zone.  This does
   not affect the ability of a server to prove insecure delegations.
   The Opt-Out MAY be part of the zone-signing tool configuration.

9.2.  Zone Serving

   This specification modifies DNSSEC-enabled DNS responses generated by
   authoritative servers.  In particular, it replaces use of NSEC or
   NSEC3 RRs in such responses with NSEC5 RRs and adds on-the-fly
   computed NSEC5PROOF RRs.

   The authenticated denial of existence proofs in NSEC5 are almost the
   same as in NSEC3.  However, due to introduction of Wildcard flag in
   NSEC5 RRs, the NSEC5 proof consists from (up to) two NSEC5 RRs,
   instead of (up to) three.




Vcelak & Goldberg        Expires March 24, 2016                [Page 14]


Internet-Draft                    NSEC5                   September 2015


   According to a type of a response, an authoritative server MUST
   include NSEC5 RRs in a response as defined in Section 8.  For each
   NSEC5 RR in the response a matching RRSIG RRset and a synthesized
   NSEC5PROOF MUST be added as well.

   A synthesized NSEC5PROOF RR has the owner name set to a domain name
   exactly matching the name required for the proof.  The class and TTL
   of the RR MUST be the same as the class and TTL value of the
   corresponding NSEC5 RR.  The RDATA are set according to the
   description in Section 7.1.

   Notice, that the NSEC5PROOF owner name can be a wildcard (e.g.,
   source of synthesis proof in wildcard No Data responses).  The name
   also always matches the domain name required for the proof while the
   NSEC5 RR may only cover (not match) the name in the proof (e.g.,
   closest encloser in Name Error responses).

   If NSEC5 is used, an answering server MUST use exactly one NSEC5
   chain for one signed zone.

   NSEC5 MUST NOT be used in parallel with NSEC, NSEC3, or any other
   authenticated denial of existence mechanism that allows for
   enumeration of zone contents.

   Similarly to NSEC3, the owner names of NSEC5 RRs are not represented
   in the NSEC5 chain and therefore NSEC5 records deny their own
   existence.  The desired behavior caused by this paradox is the same
   as described in Section 7.2.8 of [RFC5155].

9.3.  NSEC5KEY Rollover Mechanism

   Replacement of the NSEC5 key implies generating a new NSEC5 chain.
   The NSEC5KEY rollover mechanism is similar to "Pre-Publish Zone
   Signing Key Rollover" as specified in [RFC6781].  The NSEC5KEY
   rollover MUST be performed as a sequence of the following steps:

   1.  A new public NSEC5 key is added into the NSEC5KEY RRset in the
       zone apex.

   2.  The old NSEC5 chain is replaced by a new NSEC5 chain constructed
       using the new key.  This replacement MUST happen as a single
       atomic operation; the server MUST NOT be responding with RRs from
       both the new and old chain at the same time.

   3.  The old public key is removed from the NSEC5KEY RRset in the zone
       apex.





Vcelak & Goldberg        Expires March 24, 2016                [Page 15]


Internet-Draft                    NSEC5                   September 2015


   The minimal delay between the steps 1. and 2.  MUST be the time it
   takes for the data to propagate to the authoritative servers, plus
   the TTL value of the old NSEC5KEY RRset.

   The minimal delay between the steps 2. and 3.  MUST be the time it
   takes for the data to propagate to the authoritative servers, plus
   the maximum zone TTL value of any of the data in the previous version
   of the zone.

9.4.  Secondary Servers

   This document does not define mechanism to distribute NSEC5 private
   keys.

9.5.  Zones Using Unknown Hash Algorithms

   Zones that are signed with unknown NSEC5 algorithm or by an
   unavailable NSEC5 private key cannot be effectively served.  Such
   zones SHOULD be rejected when loading and servers SHOULD respond with
   RCODE=2 (Server failure) when handling queries that would fall under
   such zones.

9.6.  Dynamic Updates

   A zone signed using NSEC5 MAY accept dynamic updates.  The changes to
   the zone MUST be performed in a way, that the zone satisfies the
   properties specified in Section 9.1 at any time.

   It is RECOMMENDED that the server rejects all updates containing
   changes to the NSEC5 chain (or related RRSIG RRs) and performs itself
   any required alternations of the NSEC5 chain induced by the update.

   Alternatively, the server MUST verify that all the properties are
   satisfied prior to performing the update atomically.

10.  Resolver Considerations

   The same considerations as described in Section 9 of [RFC5155] for
   NSEC3 apply to NSEC5.  In addition, as NSEC5 RRs can be validated
   only with appropriate NSEC5PROOF RRs, the NSEC5PROOF RRs MUST be all
   together cached and included in responses with NSEC5 RRs.

11.  Validator Considerations

11.1.  Validating Responses

   The validator MUST ignore NSEC5 RRs with Flags field values other
   than the ones defined in Section 6.2.



Vcelak & Goldberg        Expires March 24, 2016                [Page 16]


Internet-Draft                    NSEC5                   September 2015


   The validator MAY treat responses as bogus if the response contains
   NSEC5 RRs that refer to a different NSEC5KEY.

   According to a type of a response, the validator MUST verify all
   conditions defined in Section 8.  Prior to making decision based on
   the content of NSEC5 RRs in a response, the NSEC5 RRs MUST be
   validated.

   To validate a denial of existence, zone NSEC5 public keys are
   required in addition to DNSSEC public keys.  Similarly to DNSKEY RRs,
   the NSEC5KEY RRs are present in the zone apex.

   The NSEC5 RR is validated as follows:

   1.  Select a correct NSEC5 public key to validate the NSEC5PROOF.
       The Key Tag value of the NSEC5PROOF RR must match with the key
       tag value computed from the NSEC5KEY RDATA.

   2.  Validate the NSEC5 proof present in the NSEC5PROOF Owner Name
       Hash field using the NSEC5 public key.  If there are multiple
       NSEC5KEY RRs matching the key tag, at least one of the keys must
       validate the NSEC5 proof.

   3.  Compute the NSEC5 hash value from the NSEC5 proof and check if
       the response contains NSEC5 RR matching or covering the computed
       NSEC5 hash.  The TTL values of the NSEC5 and NSEC5PROOF RRs must
       be the same.

   4.  Validate the signature of the NSEC5 RR.

   If the NSEC5 RR fails to validate, it MUST be ignored.  If some of
   the conditions required for an NSEC5 proof is not satisfied, the
   response MUST be treated as bogus.

   Notice that determining closest encloser and next closer name in
   NSEC5 is easier than in NSEC3.  NSEC5 and NSEC5PROOF RRs are always
   present in pairs in responses and the original owner name of the
   NSEC5 RR matches the owner name of the NSEC5PROOF RR.

11.2.  Validating Referrals to Unsigned Subzones

   The same considerations as defined in Section 8.9 of [RFC5155] for
   NSEC3 apply to NSEC5.

11.3.  Responses With Unknown Hash Algorithms






Vcelak & Goldberg        Expires March 24, 2016                [Page 17]


Internet-Draft                    NSEC5                   September 2015


   A validator MUST ignore NSEC5KEY RRs with unknown NSEC5 algorithms.
   The practical result of this is that zones sighed with unknown
   algorithms will be considered bogus.

12.  Special Considerations

12.1.  Transition Mechanism

   TODO: Not finished.  Following information will be covered:

   o  Transition from NSEC or NSEC3.

   o  Transition from NSEC5 to NSEC/NSEC3

   o  Transition to new algorithms within NSEC5

   Quick notes on transition from NSEC/NSEC3 to NSEC5:

   1.  Publish NSEC5KEY RR.

   2.  Wait for data propagation to slaves and cache expiration.

   3.  Instantly switch answering from NSEC/NSEC3 to NSEC5.

   Quick notes on transition from NSEC5 to NSEC/NSEC3:

   1.  Instantly switch answering from NSEC5 to NSEC/NSEC3.

   2.  Wait for NSEC5 RRs expiration in caches.

   3.  Remove NSEC5KEY RR from the zone.

12.2.  NSEC5 Private Keys

   This document does not define format to store NSEC5 private key.  Use
   of standardized and adopted format is RECOMMENDED.

   The NSEC5 private key MAY be shared between multiple zones, however a
   separate key is RECOMMENDED for each zone.

12.3.  Domain Name Length Restrictions

   The NSEC5 creates additional restrictions on domain name lengths.  In
   particular, zones with names that, when converted into hashed owner
   names exceed the 255 octet length limit imposed by [RFC1035], cannot
   use this specification.





Vcelak & Goldberg        Expires March 24, 2016                [Page 18]


Internet-Draft                    NSEC5                   September 2015


   The actual maximum length of a domain name depends on the length of
   the zone name and used NSEC5 algorithm.

   With FDH-SHA256-SHA256 defined in this document, the SHA-256 hash
   function is used to construct NSEC5 hash values.  SHA-256 produces a
   hash of 256 bits, which can be encoded in 52 characters in Base32hex
   without padding.  The encoded string is prepended to the name of the
   zone as a single label, which includes the length field of a single
   octet.  The maximal length of the zone name is therefore 202 octets
   (255 - 53).

13.  Performance Considerations

   This section compares NSEC, NSEC3, and NSEC5 with regards to the size
   of denial-of-existence responses and performance impact on the DNS
   components.

13.1.  Performance of Cryptographic Operations

   Additional performance costs depend on the costs of cryptographic
   operations to a great extent.  The following results were retrieved
   with OpenSSL 1.0.1k, running an ordinary laptop on a single-core of a
   CPU manufactured in 2011.  The parameters of cryptographic operations
   were chosen to reflect the parameters used in the real-world
   application of DNSSEC.

   Comparison of NSEC3 and NSEC5 hashing performance:

   o  NSEC3 uses multiple iterations of the SHA-1 function with an
      arbitrary salt.  The input of the first iteration is the domain
      name in wire format together with binary salt; the input of the
      subsequent iterations is the binary digest and the salt.  We can
      assume that the input size will be smaller than 32 octets for most
      executions.

      The measured implementation gives a stable performance for small
      input blocks up to 32 octets.  About 3e6 hashes per second can be
      computed given these parameters.

      The number of additional iterations in NSEC3 parameters will
      probably vary between 0 and 20 in reality.  Therefore we can
      expect the NSEC3 hash computation performance to be between 2e5
      and 3e6 hashes per second.

   o  The NSEC5 hash is computed in two steps: NSEC5 proof computation
      followed by hashing of the result.  The NSEC5 proof is basically
      an RSA signature and the performance will therefore vary for
      signing and verification and also for different key sizes.  We can



Vcelak & Goldberg        Expires March 24, 2016                [Page 19]


Internet-Draft                    NSEC5                   September 2015


      expect that the final hashing will have insignificant impact on
      the overall hashing performance.

      The measurement of NSEC5 proof computation and verification
      resulted into the following numbers: 3e3 sign/s and 4e4 verify/s
      for 1024-bit key; 4e2 sign/s and 1e4 verify/s for 2048-bit key;
      and 5e1 sign/s and 3e3 verify/s for 4096-bit key.

      The final SHA-256 hashing is about two orders of magnitude faster
      given the input block size matching the NSEC5 proof result size.

      Picking a moderate key size of 2048-bits, the NSEC5 hash
      computation performance will be in the order of 10^2 issued hashes
      per second and 10^4 validated hashes per second.

   According to the results, the NSEC5 hashing is about three orders of
   magnitude slower than NSEC3 hashing and the NSEC5 hash verification
   is about one order of magnitude slower than NSEC3 hash verification.

   Comparison of signing and verification performance of different
   DNSSEC signing algorithms:

   +-----------------+---------+-----------+-------------+-------------+
   | Algorithm       |     Key | Signature | Performance | Performance |
   |                 |    size |      size |    (sign/s) |  (verify/s) |
   |                 |  (bits) |  (octets) |             |             |
   +-----------------+---------+-----------+-------------+-------------+
   | RSASHA256       |    1024 |       128 |        2000 |       40000 |
   | RSASHA256       |    2048 |       256 |         400 |       10000 |
   | RSASHA256       |    4096 |       512 |          50 |        3000 |
   | ECDSAP256SHA256 |     256 |        64 |        5000 |        1000 |
   | ECDSAP384SHA384 |     384 |        96 |        3000 |         600 |
   +-----------------+---------+-----------+-------------+-------------+


   The retrieved values are important primarily for the purpose of
   evaluating performance of response validation.  The signing
   performance is not that important because the zone is usually signed
   offline.

13.2.  Authoritative Server Startup

   This section compares additional server startup cost based on the
   used authenticated denial mechanism.







Vcelak & Goldberg        Expires March 24, 2016                [Page 20]


Internet-Draft                    NSEC5                   September 2015


   NSEC  There are no special requirements on processing of a NSEC-
      signed zone during an authoritative server startup.  The server
      handles the NSEC RRs the same way as any other records in the
      zone.

   NSEC3  The authoritative server can precompute NSEC3 hashes for all
      domain names in the NSEC3-signed zone on startup.  With respect to
      query answering, this can speed up inclusion of NSEC3 RRs for
      existing domain names (i.e., Closest provable encloser and QNAME
      for No Data response).

   NSEC5  Very similar considerations apply for NSEC3 and NSEC5.  There
      is a strong motivation to precompute the NSEC5 proofs because they
      are costly to compute.  A possible solution to reduce the startup
      time is to store the precomputed NSEC5 proofs and NSEC5 hashes in
      a persistent storage.

   The impact of NSEC3 and NSEC5 on the authoritative server startup
   performance is greatly implementation specific.  The server software
   vendor has to seek balance between answering performance, startup
   slowdown, and additional storage cost.

13.3.  NSEC5 Answer Generating and Processing

   An authenticated denial proof is required for No Data, Name Error,
   Wildcard Match, and Wildcard No Data answer.  The number of required
   records depends on used authenticated denial mechanism.  Their size,
   generation cost, and validation cost depend on various zone and
   signing parameters.

   In the worst case, the following additional records authenticating
   the denial will be included into the response:

   o  Up to two NSEC records and their associated RRSIG records.

   o  Up to three NSEC3 records and their associated RRSIG records.

   o  Up to two NSEC5 records and their associated NSEC5PROOF and RRSIG
      records.

   The following table compares the size of NSEC, NSEC3, and NSEC5
   records.  We assume the SHA-1 hash algorithm for NSEC3 and the FDH-
   SHA256-SHA256 algorithm for NSEC5.

      +-------+------------+---------------+-----------------------+
      |       | Fixed part | Common part   | RR type-specific part |
      +-------+------------+---------------+-----------------------+
      | NSEC  | 10 octets  | Type Bit Maps | Owner Name, Next Name |



Vcelak & Goldberg        Expires March 24, 2016                [Page 21]


Internet-Draft                    NSEC5                   September 2015


      | NSEC3 | 64 octets  | Type Bit Maps | Salt                  |
      | NSEC5 | 101 octets | Type Bit Maps | -                     |
      +-------+------------+---------------+-----------------------+


   The size covers complete RR representation in wire format:

   o  The Fixed part includes length of all fixed-size fields in the RR;
      and also a size of generally variable-sized fields whose length
      can determined from the used parameters (e.g., the NSEC3 owner
      name consists from one label encoding the hash and a compression
      pointer to zone apex).

   o  The Common part includes the only field shared among the RR types.

   o  The RR type-specific part contains unique fields present in the RR
      types whose length will vary.  Note that the Owner Name can be
      compressed, but Next Name must not.  Also note that the Salt in
      NSEC3 will have constant size for all NSEC3 records in the chain.

   The size of RRSIG RR is a sum of length of possibly compressed RR
   owner name, 28 octets for fixed-size fields, the length of
   uncompressed signer name, and the length of the signature.

   The size of NSEC5PROOF RR is a sum of length of possibly compressed
   RR owner name, 2 octets for fixed-size fields, and the length of the
   proof.

   The following list summarizes the increase of the DNS response size
   for authenticated denial worst-case scenario.  As a significant part
   of the increase is caused by the used DNSSEC signing algorithm, the
   summary includes two variants: RSA stands for the RSASHA256 algorithm
   with 2048-bit key and ECDSA stands for the ECDSAP256SHA256 algorithm.
   For NSEC5, FDH-SHA256-SHA256 with 2048-bit key is used.

   o  NSEC:

      *  4 x compressed domain name

      *  4 x uncompressed domain name

      *  2 x type bit bitmap

      *  588 octets (RSA) or 204 octets (ECDSA)

   o  NSEC3:

      *  3 x compressed domain name



Vcelak & Goldberg        Expires March 24, 2016                [Page 22]


Internet-Draft                    NSEC5                   September 2015


      *  3 x uncompressed domain name

      *  3 x salt

      *  3 x type bit map

      *  969 octets (RSA) or 393 octets (ECDSA)

   o  NSEC5:

      *  4 x compressed domain name

      *  2 x uncompressed domain name

      *  2 x type bit map

      *  1286 octets (RSA) or 902 octets (ECDSA)

   The following list summarizes additional cryptographic operations
   performed by the authoritative server for authenticated denial worst-
   case scenario:

   o  NSEC:

      *  No cryptographic operations required.

   o  NSEC3:

      *  NSEC3 hash for Closest provable encloser (possibly precomputed)

      *  NSEC3 hash for Next closer name

      *  NSEC3 hash for wildcard at the closest encloser

   o  NSEC5:

      *  NSEC5 proof and hash for Closest provable encloser (possibly
         precomputed)

      *  NSEC5 proof and hash for Next closer name

   As anticipated, NSEC is the most efficient authenticated denial
   mechanism as for response size and performance cost.  The bottleneck
   of NSEC5 is the NSEC5 proof computation.  If the proofs are
   precomputed for domain names in the zone, the server has to compute
   just one NSEC5 proof per answer.  But it will still be more expensive
   than NSEC3 and the same applies for the response size.




Vcelak & Goldberg        Expires March 24, 2016                [Page 23]


Internet-Draft                    NSEC5                   September 2015


   As for the response processing, the validation cost reflects from the
   records present in the response.  Again, the NSEC validation seems to
   be the most inexpensive.  However the difference between RSA and
   ECDSA verification performance is huge and for some parameters, NSEC3
   is faster to validate than NSEC5 and vice versa.

14.  Security Considerations

14.1.  Zone Enumeration Attacks

   NSEC5 is robust to zone enumeration via offline dictionary attacks by
   any attacker that does not know the NSEC5 private key.  Without the
   private NSEC5 key, that attacker cannot compute the NSEC5 proof that
   corresponds to a given name; the only way it can learn the NSEC5
   proof value for a given name is by sending a queries for that name to
   the authoritative server.  Without the NSEC5 proof value, the
   attacker cannot learn the NSEC5 hash value.  Thus, even an attacker
   that collects the entire chain of NSEC5 RR for a zone cannot use
   offline attacks to "reverse" that NSEC5 hash values in these NSEC5 RR
   and thus learn which names are present in the zone.  A formal
   cryptographic proof of this property is in [nsec5].

14.2.  Hash Collisions

   Hash collisions between QNAME and the owner name of an NSEC5 RR may
   occur.  When they do, it will be impossible to prove the non-
   existence of the colliding QNAME.  However, with SHA-256, this is
   highly unlikely (on the order of 1 in 2^128).  Note that DNSSEC
   already relies on the presumption that a cryptographic hash function
   is collision resistant, since these hash functions are used for
   generating and validating signatures and DS RRs.  See also the
   discussion on key lengths in [nsec5].

14.3.  Compromise of the Private NSEC5 Key

   NSEC5 requires authoritative servers to hold the private NSEC5 key,
   but not the private zone-signing keys or the private key-signing keys
   for the zone.  The private NSEC5 key needs only be as secure as the
   DNSSEC records whose the privacy (against zone-enumeration attacks)
   that NSEC5 is protecting.  This is because even an adversary that
   knows the private NSEC5 key cannot modify the contents of the zone;
   this is because the zone contents are signed using the private zone-
   signing key, while the private NSEC5 key is only used to compute
   NSEC5 proof values.  Thus, a compromise of the private NSEC5 keys
   does not lead to a compromise of the integrity of the DNSSEC record
   in the zone; instead, all that is lost is privacy against zone
   enumeration, if the attacker that knows the private NSEC5 key can
   compute NSEC5 hashes offline, and thus launch offline dictionary



Vcelak & Goldberg        Expires March 24, 2016                [Page 24]


Internet-Draft                    NSEC5                   September 2015


   attacks.  Thus, a compromise of the private NSEC5 key effectively
   downgrades the security of NSEC5 to that of NSEC3.  A formal
   cryptographic proof of this property is in [nsec5].

14.4.  Key Length Considerations

   The NSEC5 key must be long enough to withstand attacks for as long as
   the privacy of the zone is important.  Even if the NSEC5 key is
   rolled frequently, its length cannot be too short, because zone
   privacy may be important for a period of time longer than the
   lifetime of the key.  (For example, an attacker might collect the
   entire chain of NSEC5 RR for the zone over one short period, and
   then, later (even after the NSEC5 key expires) perform an offline
   dictionary attack that attempt to "reverse" the NSEC5 hash values
   present in the NSEC5 RRs.)  This is in contrast to zone-signing and
   key-signing keys used in DNSSEC; these keys, which ensure the
   authenticity and integrity of the zone contents need to remain secure
   only during their lifetime.

14.5.  Transitioning to a New NSEC5 Algorithm

   Although the NSEC5KEY RR formats include a hash algorithm parameter,
   this document does not define a particular mechanism for safely
   transitioning from one NSEC5 algorithm to another.  When specifying a
   new hash algorithm for use with NSEC5, a transition mechanism MUST
   also be defined.  It is possible that the only practical and
   palatable transition mechanisms may require an intermediate
   transition to an insecure state, or to a state that uses NSEC or
   NSEC3 records instead of NSEC5.

15.  IANA Considerations

   This document updates the IANA registry "Domain Name System (DNS)
   Parameters" in subregistry "Resource Record (RR) TYPEs", by defining
   the following new RR types:

      NSEC5KEY value XXX.

      NSEC5 value XXX.

      NSEC5PROOF value XXX.

   This document creates a new IANA registry for NSEC5 algorithms.  This
   registry is named "DNSSEC NSEC5 Algorithms".  The initial content of
   the registry is:

      0 is Reserved.




Vcelak & Goldberg        Expires March 24, 2016                [Page 25]


Internet-Draft                    NSEC5                   September 2015


      1 is FDH-SHA256-SHA256.

      2-255 is Available for assignment.

   This document updates the IANA registry "DNS Security Algorithm
   Numbers" by defining following aliases:

      XXX is NSEC5-RSASHA256, alias for RSASHA256 (8).

      XXX is NSEC5-RSASHA512, alias for RSASHA512 (10).

      XXX is NSEC5-ECDSAP256SHA256 alias for ECDSAP256SHA256 (13).

      XXX is NSEC5-ECDSAP384SHA384 alias for ECDSAP384SHA384 (14).

16.  Contributors

   This document would not be possible without help of Moni Naor
   (Weizmann Institute), Dimitrios Papadopoulos (Boston University),
   Sachin Vasant (Cisco Systems), Leonid Reyzin (Boston University), and
   Asaf Ziv (Weizmann Institute) who contributed to the design of NSEC5,
   and Ondrej Sury (CZ.NIC Labs) who provided advice on its
   implementation.

17.  References

17.1.  Normative References

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

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

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

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

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

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





Vcelak & Goldberg        Expires March 24, 2016                [Page 26]


Internet-Draft                    NSEC5                   September 2015


   [RFC3110]  Eastlake, D., "RSA/SHA-1 SIGs and RSA KEYs in the Domain
              Name System (DNS)", RFC 3110, May 2001.

   [RFC3447]  Jonsson, J. and B. Kaliski, "Public-Key Cryptography
              Standards (PKCS) #1: RSA Cryptography Specifications
              Version 2.1", RFC 3447, February 2003.

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

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

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

   [RFC4648]  Josefsson, S., "The Base16, Base32, and Base64 Data
              Encodings", RFC 4648, October 2006.

   [RFC5155]  Laurie, B., Sisson, G., Arends, R., and D. Blacka, "DNS
              Security (DNSSEC) Hashed Authenticated Denial of
              Existence", RFC 5155, March 2008.

   [RFC6234]  Eastlake, D. and T. Hansen, "US Secure Hash Algorithms
              (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 2011.

17.2.  Informative References

   [nsec5]    Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L.,
              Vasant, S., and A. Ziv, "NSEC5: Provably Preventing DNSSEC
              Zone Enumeration", July 2014.

   [nsec3gpu]
              Wander, M., Schwittmann, L., Boelmann, C., and T. Weis,
              "GPU-Based NSEC3 Hash Breaking", in IEEE Symp. Network
              Computing and Applications (NCA), 2014.

   [nsec3walker]
              Bernstein, D., "Nsec3 walker", 2011,
              <http://dnscurve.org/nsec3walker.html>.

   [RFC6781]  Kolkman, O., Mekking, W., and R. Gieben, "DNSSEC
              Operational Practices, Version 2", RFC 6781, December
              2012.




Vcelak & Goldberg        Expires March 24, 2016                [Page 27]


Internet-Draft                    NSEC5                   September 2015


   [RFC7129]  Gieben, R. and W. Mekking, "Authenticated Denial of
              Existence in the DNS", RFC 7129, February 2014.

Appendix A.  Full Domain Hash Algorithm

   The Full Domain Hash (FDH) is a RSA-based scheme that allows
   authentication of hashes using public-key cryptography.

   In this document, the notation from [RFC3447] is used.

   Used parameters:

      (n, e) - RSA public key

      K - RSA private key

      k - length of the RSA modulus n in octets

   Fixed options:

      Hash - hash function to be used with MGF1

   Used primitives:

      I2OSP - Coversion of a nonnegative integer to an octet string as
      defined in Section 4.1 of [RFC3447]

      OS2IP - Coversion of an octet string to a nonnegative integer as
      defined in Section 4.2 of [RFC3447]

      RSASP1 - RSA signature primitive as defined in Section 5.2.1 of
      [RFC3447]

      RSAVP1 - RSA verification primitive as defined in Section 5.2.2 of
      [RFC3447]

      MGF1 - Mask Generation Function based on a hash function as
      defined in Section B.2.1 of [RFC3447]

A.1.  FDH signature

   FDH_SIGN(K, M)

   Input:

      K - RSA private key

      M - message to be signed, an octet string



Vcelak & Goldberg        Expires March 24, 2016                [Page 28]


Internet-Draft                    NSEC5                   September 2015


   Output:

      S - signature, an octet string of length k

   Steps:

   1.  EM = MGF1(M, k - 1)

   2.  m = OS2IP(EM)

   3.  s = RSASP1(K, m)

   4.  S = I2OSP(s, k)

   5.  Output S

A.2.  FDH verification

   FDH_VERIFY((n, e), M, S)

   Input:

      (n, e) - RSA public key

      M - message whose signature is to be verified, an octet string

      S - signature to be verified, an octet string of length k

   Output:

      "valid signature" or "invalid signature"

   Steps:

   1.  s = OS2IP(S)

   2.  m = RSAVP1((n, e), s)

   3.  EM = I2OSP(m, k - 1)

   4.  EM' = MGF1(M, k - 1)

   5.  If EM and EM' are the same, output "valid signature"; else output
       "invalid signature".

Appendix B.  Change Log





Vcelak & Goldberg        Expires March 24, 2016                [Page 29]


Internet-Draft                    NSEC5                   September 2015


   Note to RFC Editor: if this document does not obsolete an existing
   RFC, please remove this appendix before publication as an RFC.

      pre 00 - initial version of the document submitted to mailing list
      only

      00 - fix NSEC5KEY rollover mechanism, clarify NSEC5PROOF RDATA,
      clarify inputs and outputs for NSEC5 proof and NSEC5 hash
      computation

      01 - added Performance Considerations section

Appendix C.  Open Issues

   Note to RFC Editor: please remove this appendix before publication as
   an RFC.

   1.  Consider alternative way to signalize NSEC5 support.  The NSEC5
       could use only one DNSSEC algorithm identifier, and the actual
       algorithm to be used for signing can be the first octet in DNSKEY
       public key field and RRSIG signature field.  Similar approach is
       used by PRIVATEDNS and PRIVATEOID defined in [RFC4034].

   2.  How to add new NSEC5 hashing algorithm.  We will need to add new
       DNSSEC algorithm identifiers again.

   3.  NSEC and NSEC3 define optional steps for hash collisions
       detection.  We don't have a way to avoid them if they really
       appear (unlikely).  We would have to drop the signing key and
       generate a new one.  Which cannot be done instantly.

   4.  Write Special Considerations section.

   5.  Contributor list has to be completed.

Authors' Addresses

   Jan Vcelak
   CZ.NIC
   Milesovska 1136/5
   Praha  130 00
   CZ

   EMail: jan.vcelak@nic.cz







Vcelak & Goldberg        Expires March 24, 2016                [Page 30]


Internet-Draft                    NSEC5                   September 2015


   Sharon Goldberg
   Boston University
   111 Cummington St, MCS135
   Boston, MA  02215
   USA

   EMail: goldbe@cs.bu.edu












































Vcelak & Goldberg        Expires March 24, 2016                [Page 31]


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