Network Working Group                                          J. Vcelak
Internet-Draft                                                    CZ.NIC
Intended status: Standards Track                             S. Goldberg
Expires: March 23, September 08, 2017                            Boston University
                                                         D. Papadopoulos
                                                       Boston
                                                  University
                                                      September 19, 2016 of Maryland
                                                                S. Huque
                                                              Salesforce
                                                             D. Lawrence
                                                     Akamai Technologies
                                                          March 07, 2017

            NSEC5, DNSSEC Authenticated Denial of Existence
                         draft-vcelak-nsec5-03
                         draft-vcelak-nsec5-04

Abstract

   The Domain Name System Security (DNSSEC) Extensions (DNSSEC) introduced the
   NSEC resource record (RR) for authenticated denial of existence and
   the NSEC3 RR 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 NSEC5 as an cryptographically-
   proven alternative mechanism that prevents for DNSSEC
   authenticated denial of existence.  NSEC5 uses verifiable random
   functions (VRFs) to prevent offline enumeration of zone enumeration. contents.
   NSEC5 has also protects the
   additional advantage integrity of the zone contents even if an
   adversary compromises one of the authoritative servers for the zone.
   Integrity is preserved because NSEC5 does not requiring require private zone-signing zone-
   signing keys to be present on all authoritative servers for the zone. zone,
   in contrast to DNSSEC online signing schemes like NSEC3 White Lies.

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 23, September 08, 2017.

Copyright Notice

   Copyright (c) 2016 2017 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
   (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  . . . . . . . . . . . . . . . . . . . . . .   5
     1.3.  Terminology . . . . . . . . . . . . . . . . . . . . . . .   5   6
   2.  Backward Compatibility  . . . . . . . . . . . . . . . . . . .   5   6
   3.  How NSEC5 Works . . . . . . . . . . . . . . . . . . . . . . .   6   7
   4.  NSEC5 Algorithms  . . . . . . . . . . . . . . . . . . . . . .   7   8
   5.  The NSEC5KEY Resource Record  . . . . . . . . . . . . . . . .   8
     5.1.  NSEC5KEY RDATA Wire Format  . . . . . . . . . . . . . . .   8
     5.2.  NSEC5KEY RDATA Presentation Format  . . . . . . . . . . .   8   9
   6.  The NSEC5 Resource Record . . . . . . . . . . . . . . . . . .   9
     6.1.  NSEC5 RDATA Wire Format . . . . . . . . . . . . . . . . .   9
     6.2.  NSEC5 Flags Field . . . . . . . . . . . . . . . . . . . .   9  10
     6.3.  NSEC5 RDATA Presentation Format . . . . . . . . . . . . .  10
   7.  The NSEC5PROOF Resource Record  . . . . . . . . . . . . . . .  10  11
     7.1.  NSEC5PROOF RDATA Wire Format  . . . . . . . . . . . . . .  11
     7.2.  NSEC5PROOF RDATA Presentation Format  . . . . . . . . . .  11
   8.  Types of Authenticated Denial of Existence with NSEC5 Proofs  . . . . . . . . . . . . . . . . . . . . . . . .  11  12
     8.1.  Name Error Responses  . . . . . . . . . . . . . . . . . .  12
     8.2.  No Data Responses . . . . . . . . . . . . . . . . . . . .  12  13
       8.2.1.  No Data Response, Opt-Out Not In Effect . . . . . . .  12  13
       8.2.2.  No Data Response, Opt-Out In Effect . . . . . . . . .  13
     8.3.  Wildcard Responses  . . . . . . . . . . . . . . . . . . .  13  14
     8.4.  Wildcard No Data Responses  . . . . . . . . . . . . . . .  14
   9.  Authoritative Server Considerations . . . . . . . . . . . . .  14  15
     9.1.  Zone Signing  . . . . . . . . . . . . . . . . . . . . . .  14  15
       9.1.1.  Precomputing Closest Provable Encloser Proofs . . . .  16
     9.2.  Zone Serving  . . . . . . . . . . . . . . . . . . . . . .  16  17
     9.3.  NSEC5KEY Rollover Mechanism . . . . . . . . . . . . . . .  17
     9.4.  Secondary Servers . . . . . . . . . . . . . . . . . . . .  17  18
     9.5.  Zones Using Unknown Hash NSEC5 Algorithms  . . . . . . . . . . .  17  18
     9.6.  Dynamic Updates . . . . . . . . . . . . . . . . . . . . .  17  18
   10. Resolver Considerations . . . . . . . . . . . . . . . . . . .  18
   11. Validator Considerations  . . . . . . . . . . . . . . . . . .  18  19
     11.1.  Validating Responses . . . . . . . . . . . . . . . . . .  18  19
     11.2.  Validating Referrals to Unsigned Subzones  . . . . . . .  19
     11.3.  Responses With Unknown Hash NSEC5 Algorithms  . . . . . . . . .  19  20
   12. Special Considerations  . . . . . . . . . . . . . . . . . . .  19  20
     12.1.  Transition Mechanism . . . . . . . . . . . . . . . . . .  19  20
     12.2.  NSEC5  Private Keys NSEC5 keys . . . . . . . . . . . . . . . . . . .  20
     12.3.  Domain Name Length Restrictions  . . . . . . . . . . . .  20
   13. Performance Considerations  . . . . . . . . . . . . . . . . .  20
     13.1.  Performance of Cryptographic Operations  . . . . . . . .  20
       13.1.1.  NSEC3 Hashing Performance  . . . . . . Implementation Status . . . . . . .  20
       13.1.2.  NSEC5 Hashing Performance . . . . . . . . . . . . .  21
       13.1.3.  DNSSEC Signing
   14. Performance . . . . . . . . . . . . .  22
     13.2.  Authoritative Server Startup . . . . . . . . . . . . . .  22
     13.3.  NSEC5 Answer Generating and Processing . . . . . . . . .  23
     13.4.  Precomputed NSEC5PROOF Values  . . . . . . . . . . . . .  24
     13.5.  Response Lengths . . . . . . . . . . . . . . . . . . . .  24
     13.6.  Summary  . . . . . . . Considerations  . . . . . . . . . . . . . . . . .  25
   14.  21
   15. Security Considerations . . . . . . . . . . . . . . . . . . .  26
     14.1.  21
     15.1.  Zone Enumeration Attacks . . . . . . . . . . . . . . . .  26
     14.2.  Hash Collisions  . . . . . . . . . . . . . . . . . . . .  26
     14.3.  21
     15.2.  Compromise of the Private NSEC5 Key  . . . . . . . . . .  26
     14.4.  21
     15.3.  Key Length Considerations  . . . . . . . . . . . . . . .  27
     14.5.  Transitioning to a New  22
     15.4.  NSEC5 Algorithm . . . . . . . . .  27
   15. IANA Considerations . . . . Hash Collisions  . . . . . . . . . . . . . . . . .  27  22
   16. Contributors  . . . IANA Considerations . . . . . . . . . . . . . . . . . . . . .  28  22
   17. References  . . . . . . . . . . . . . . . . . . . Contributors  . . . . . .  28
     17.1.  Normative References . . . . . . . . . . . . . . . . . .  28
     17.2.  Informative  23
   18. References  . . . . . . . . . . . . . . . . .  30
   Appendix A.  RSA Full Domain Hash Algorithm . . . . . . . . . . .  32
     A.1.  FDH signature . . . . . . .  23
     18.1.  Normative References . . . . . . . . . . . . . . .  32
     A.2.  FDH verification . . .  23
     18.2.  Informative References . . . . . . . . . . . . . . . . .  33  25
   Appendix B. A.  Elliptic Curve VRF . . . . . . . . . . . . . . . . .  33
     B.1.  ECVRF Hash To Curve . . . . . . . . . . . . . . . . . . .  34
     B.2.  ECVRF  26
     A.1.  EC-VRF Auxiliary Functions  . . . . . . . . . . . . . . . .  35
       B.2.1.  ECVRF  27
       A.1.1.  EC-VRF Hash Points . . To Curve  . . . . . . . . . . . . . . . .  35
       B.2.2.  ECVRF Proof To  27
       A.1.2.  EC-VRF Hash Points  . . . . . . . . . . . . . . . . .  36
       B.2.3.  ECVRF  28
       A.1.3.  EC-VRF Decode Proof . . . . . . . . . . . . . . . . .  36
     B.3.  ECVRF Signing . . .  28
     A.2.  EC-VRF Proving  . . . . . . . . . . . . . . . . . . .  37
     B.4.  ECVRF Verification . .  29
     A.3.  EC-VRF Proof To Hash  . . . . . . . . . . . . . . . . .  37
   Appendix C.  Change Log .  29
     A.4.  EC-VRF Verifying  . . . . . . . . . . . . . . . . . . . .  38  30
   Appendix D.  Open Issues  . . . . . . . . . . . . . . . . . . . .  39
   Authors' Addresses  . . B.  Change Log . . . . . . . . . . . . . . . . . . . . .  39  31

1.  Introduction

1.1.  Rationale

   The
   NSEC5 provides an alternative mechanism for authenticated denial of
   existence for the DNS Security Extensions (DNSSEC) provides data (DNSSEC).  NSEC5 has two
   key security properties.  First, NSEC5 protects the 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 contents even if an adversary compromises one 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
   authoritative servers for the zone.  Second, NSEC5 prevents offline
   zone is signed.
   The signature is retained as enumeration, where an RRSIG RR directly adversary makes a small number of online
   DNS queries and then processes them offline in order to learn all of
   the names in a zone.  This
   enables response authentication  Zone enumeration can be used to identify
   routers, servers or other "things" that could then be targeted in
   more complex attacks.  An enumerated zone can also be a source of
   probable email addresses for spam, or as a "key for multiple WHOIS
   queries to reveal registrant data existing in the zone.  To
   ensure integrity that many registries may have legal
   obligations to protect" [RFC5155].

   All other DNSSEC mechanisms for authenticated denial of denying answers, existence
   either fail to preserve integrity against a compromised server, or
   fail to prevent offline zone enumeration.

   When offline signing with NSEC is used [RFC4034], an NSEC chain of
   all existing domain names in the zone is constructed. constructed and signed
   offline.  The chain is made of RRs, resource records (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 authoritative server proves the zone.  Non-existence non-existence of a
   name can be thus
   proven by presenting a signed NSEC RR which covers the name.

   As side-effect, however,  Because
   the NSEC chain allows for enumeration authoritative server does not need not to know the private zone-
   signing key, the integrity of the
   zone's contents by sequentially querying for zone is protected even if the names immediately
   following those in
   server is compromised.  However, the most-recently retrieved NSEC record; chain allows for easy zone
   enumeration: N queries to the server suffice to enumerate a zone containing learn all N names.  As such, names in
   the NSEC3
   hashed denial of existence was introduced to prevent zone
   enumeration.  In NSEC3, (see e.g., [nmap-nsec-enum], [nsec3map], and [ldns-walk]).

   When offline signing with NSEC3 is used [RFC5155], the original domain names
   in the NSEC chain are replaced by their cryptographic hashes.  While
   Offline signing ensures that NSEC3 makes preserves integrity even if an
   authoritative server is compromised.  However, offline zone
   enumeration more difficult, offline dictionary attacks are is still possible with NSEC3 (see e.g., [nsec3walker],
   [nsec3gpu]), and have been demonstrated; this is because hashes may be
   computed offline and the space part of possible domain names standard network reconnaissance tools
   (e.g., [nmap-nsec3-enum], [nsec3map]).

   When online signing is restricted
   [nsec3walker][nsec3gpu].

   Zone enumeration can be prevented with NSEC3 if having used, the authoritative server compute NSEC3 RRs on-the-fly, in response to
   queries with denying responses.  Usually, holds the
   private zone-signing key and uses this is done with Minimally
   Covering key to synthesize NSEC Records or
   NSEC3 responses on the fly (e.g.  NSEC3 White Lies [RFC7129].  The
   disadvantage of this approach is a required presence of (NSEC3-WL) or
   Minimally-Covering NSEC, both described in [RFC7129]).  Because the private
   key on all authoritative servers for
   synthesized response only contains information about the zone.  This is often
   undesirable, as queried name
   (but not about any other name in the holder of zone), offline zone enumeration
   is not possible.  However, because the private key can tamper with authoritative server holds the
   zone contents, and having
   private keys on many network-facing servers
   increases zone-signing key, integrity is lost if the risk that keys can be authoritative
   server is compromised.

   To prevent

   +----------+-------------+---------------+----------------+---------+
   | Scheme   |   Integrity |  Integrity vs |       Prevents |  Online |
   |          |  vs network |   compromised |   offline zone | crypto? |
   |          |    attacks? | auth. server? |   enumeration? |         |
   +----------+-------------+---------------+----------------+---------+
   | Unsigned |          NO |            NO |            YES |      NO |
   | NSEC     |         YES |           YES |             NO |      NO |
   | NSEC3    |         YES |           YES |             NO |      NO |
   | NSEC3-WL |         YES |            NO |            YES |     YES |
   | NSEC5    |         YES |           YES |            YES |     YES |
   +----------+-------------+---------------+----------------+---------+

   NSEC5 prevents offline zone content enumeration without keeping private keys on
   all and also protects integrity
   even if a zone's authoritative servers, server is compromised.  To do this,
   NSEC5 replaces the unkeyed cryptographic hash function used in NSEC3
   with a public-key hashing scheme.
   Hashing in NSEC5 verifiable random function (VRF) [MRV99].  A VRF is performed with the
   public-key version of a separate NSEC5 key.  The keyed cryptographic hash.  Only the holder of
   the private VRF key can compute the hash, but anyone with public
   portion VRF
   key can verify the correctness of this the hash.

   The public VRF key is distributed in an NSEC5KEY RR, similar to a
   DNSKEY RR, and is used to
   validate verify NSEC5 hash values.  The private portion of the NSEC5 VRF
   key is present on all authoritative servers for the zone, and is used
   to compute hash values.

   Importantly,  For every query that elicits a negative
   response, the NSEC5KEY authoritative server hashes the query on the fly using
   the private VRF key, and also returns the corresponding precomputed
   NSEC5 record(s).  In contrast to the online signing approach
   [RFC7129], the private key that is present on all authoritative
   servers for NSEC5 cannot be used to modify the contents
   of the zone.  Thus, any compromise of the private zone contents.

   Like online signing approaches, NSEC5 key does not
   lead requires the authoritative
   server to perform online public key cryptographic operations for
   every query eliciting a compromise of zone contents.  All that denying response.  This is lost necessary; [nsec5]
   proved that online cryptography is privacy
   against required to prevent offline zone enumeration, effectively downgrading
   enumeration while still protecting the security of
   NSEC5 to that of NSEC3.  NSEC5 comes with a cryptographic proof integrity of
   security, available in [nsec5].

   The zone contents
   against network attacks.

   NSEC5 is not intended to replace NSEC or NSEC3.  It is designed
   as an alternative
   mechanism for authenticated denial of existence.  This document
   specifies NSEC5 based on the FIPS 186-3 P-256 elliptic curve and on
   the Ed25519 elliptic curve.  A formal cryptographic proof of security
   for elliptic curve (EC) NSEC5 is in [nsec5ecc].

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],
   [RFC4035], and
   [RFC4035]; subsequent RFCs that update them: them in [RFC2136], [RFC2181],
   [RFC2308], [RFC5155], and [RFC5155]. [RFC7129]; and DNS terms in [RFC7719].

   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 the NSEC5 specification.

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

   NSEC5 proof:  A signed hash of a

   QNAME:  The domain name (hash-and-sign
      paradigm). being queried (query name).

   Private NSEC5 key:  The private key for the verifiable random
      function (VRF).

   Public NSEC5 key:  The public key for the VRF.

   NSEC5 proof:  A VRF proof.  The holder of the private NSEC5 key
      (e.g., authoritative server) can compute the proof. NSEC5 proof for an
      input domain name.  Anyone knowing who knows the public VRF key
      (e.g., client) can verify it's validity.
      that the NSEC5 proof corresponds to the input domain name.

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

   NSEC5 algorithm:  A pair triple of VRF algorithms used to that compute an NSEC5 proofs
      proof, verify an NSEC5 proof, and process an NSEC5 hashes. proof to obtain
      its NSEC5 hash.

2.  Backward Compatibility

   The specification describes a protocol change that is not backward
   compatible with [RFC4035] and [RFC5155].  An 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 introduced in
   Section 16 which 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

   With NSEC5, the original domain names by their cryptographic hashes.  NSEC5 is very
   similar to NSEC3, except that the cryptographic hash name is replaced by
   hashes computed hashed using a verifiable random function (VRF).  A VRF is
   essentially the public-key version of a keyed cryptographic hash.  A VRF comes with a public/private key pair, and only the holder of the
   private key can compute the hash, but anyone with public key can
   verify the hash.

   In NSEC5, using
   the original domain name is hashed twice: following steps:

   1.  First, the  The domain name is hashed processed using a VRF keyed with the NSEC5
       private key; the result is called the NSEC5 proof.  Only an
       authoritative server that knows the private
       NSEC5 key can compute to obtain the NSEC5 proof.  Any client that  Anyone who knows the public
       NSEC5 key key, normally acquired via an NSEC5KEY RR, can
       validate the verify that
       a given NSEC5 proof. proof corresponds to a given domain name.

   2.  Second, the  The NSEC5 proof is hashed.  The result is called then processed using a publicly-computable VRF
       proof-to-hash function to obtain the NSEC5 hash value.  This hash.  The NSEC5 hash
       can be computed by any party that anyone who knows the input NSEC5 proof.

   The NSEC5 hash determines the position of a domain name in an NSEC5
   chain.  That is, all

   To sign a zone, the private NSEC5 key is used to compute the NSEC5
   hashes for a zone each name in the zone.  These NSEC5 hashes are sorted in their
   canonical order, order [RFC4034] , and each consecutive pair forms an NSEC5
   RR.  Each NSEC5 RR is signed offline using the private zone-signing
   key.  The resulting signed chain of NSEC5 RRs is provided to all
   authoritative servers for the zone, along with the private NSEC5 key.

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

   To validate the response, the client first verifies the following items:

   o  The client uses the public NSEC5 key
   (stored in key, normally acquired from the zone as an
      NSEC5KEY RR) RR, to verify that the NSEC5 proof
   corresponds with in the domain name NSEC5PROOF RR
      corresponds to be disproved.  Then, the queried name.

   o  The client
   computes uses the VRF proof-to-hash function to compute the
      NSEC5 hash from the NSEC5 proof and checks in the NSEC5PROOF RR.  The client
      verifies that it the NSEC5 hash is covered by the NSEC5 RR.  Finally, it checks

   o  The client verifies that the signature on
   the NSEC5 RR is valid. validly signed by the
      RRSIG RRset.

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 are computed and validated.

   The input for the NSEC5 proof computation is an RR owner name in the
   [RFC4034] canonical form in the wire format and an NSEC5 followed by a private key; the NSEC5 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 RSAFDH-SHA256-SHA256 NSEC5 algorithm as
   follows:

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

   o  NSEC5 hash is computed by hashing the NSEC5 proof with the SHA-256
      hash function as specified in [RFC6234].

   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.

   This document defines EC-P256-SHA256 NSEC5 algorithm as follows:

   o  The NSEC5 proof is computed using an Elliptic Curve VRF with FIPS
      186-3 P-256 curve.  The proof computation and verification is verification, and
      the proof-to-hash function are formally specified in Appendix B. A.
      The curve parameters are specified in [FIPS-186-3]
      (Section D.1.2.3) and [RFC5114] (Section 2.6).

   o  The NSEC5 hash is the x-coordinate of the group element gamma from
      the NSEC5 proof (specified in Appendix B), A), encoded as a fixed-width 32-octet
      unsigned integer in network byte order.  In practice, the hash is
      a substring of the proof ranging from 2nd to through 33th octet of
      the proof proof, inclusive.

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

   This document defines EC-ED25519-SHA256 NSEC5 algorithm as follows:

   o  The NSEC5 proof is and NSEC5 hash are the same as with EC-P256-SHA256
      but using Ed25519 elliptic curve with parameters defined in
      [RFC7748] (Section 4.1).

   o  NSEC5 hash is the same as with EC-P256-SHA256. Section 4.1.

   o  The public key format to be used in the NSEC5KEY RR is defined in
      Section 3 of [I-D.ietf-curdle-dnskey-ed25519] [RFC8080] and thus is the same as the format used to
      store Ed25519 public keys in DNSKEY RRs.

5.  The NSEC5KEY Resource Record

   The NSEC5KEY RR stores an NSEC5 a public NSEC5 key.  The key allows clients to verify a validity of
   validate an 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 the NSEC5 algorithm.

   Public Key is a variable sized 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. RRset
   or domain name.  One NSEC5 RR represents one piece of an NSEC5 chain,
   proving existence of RR types present at the original domain owner name and also non-existence of other domain
   names in a the part of the hashed domain space covered until the next
   owner name space. hashed in the RDATA.

6.1.  NSEC5 RDATA Wire Format

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

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

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

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

   The 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 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 the 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.

   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 the
   maximum number of RRs required for an authenticated denial of
   existence
   proof. proof, as originally described in [I-D.gieben-nsec4]
   Section 7.2.1.

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 not to be included in the authoritative server on-
   the-fly. zone file.  The
   NSEC5PROOF record contains the NSEC5 proof, proving a the 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.

   Owner Name Hash is a variable sized 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.  Types of Authenticated Denial of Existence with 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 prove: the minimum amount of information that an
       authoritative server must provide to a client to assure the
       client that the response content is valid.

   2.  Authoritative server proofs.  NSEC5 proofs: the names for which the NSEC5PROOF
       RRs an authoritative server
       must include in a are synthesized and added into the response to along the NSEC5
       RRs matching or covering each such name.  These records together
       prove the listed facts.

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

   If NSEC5 is said to match a domain name, the owner name of the NSEC5
   RR has to be equivalent to an NSEC5 hash of that domain name.  If an
   NSEC5 RR is said to cover a domain name, the NSEC5 hash of the domain
   name must lay strictly sort in canonical order between that NSEC5 RR's Owner Name
   and 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:

      Closest encloser.

      Next

      NSEC5PROOF for closest encloser and matching NSEC5 RR.

      NSEC5PROOF for next closer name. name and covering NSEC5 RR.

   Validator checks:

      Closest encloser belongs to is in 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.

      Next closer name is not in the zone.

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.

      NSEC5PROOF for the QNAME and matching NSEC5 RR.

   Validator checks:

      The NSEC5 RR exactly matches QNAME is in the QNAME. zone.

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

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

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

      NSEC5PROOF for closest provable encloser. encloser and matching NSEC5 RR.

   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

      NSEC5PROOF for next closer name. name and covering NSEC5 RR.

   Validator checks:

      Next closer name is derived correctly.

      Next closer name covers (not matches). is not in the zone.

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.

   Authoritative server proofs:

      Source

      NSEC5PROOF for source of synthesis (i.e., wildcard at closest encloser).

      Next
      encloser) and matching NSEC5 RR.

      NSEC5PROOF for next closer name. name and covering NSEC5 RR.

   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). is not in the zone.

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.

       A.

       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.

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

       C.

       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.

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

       E.

       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.1.1.  Precomputing Closest Provable Encloser Proofs

   The worst-case scenario when answering a negative query with NSEC5
   requires authoritative server to respond with two NSEC5PROOF RRs and
   two NSEC5 RRs.  Per Section 8, one pair of NSEC5PROOF and NSEC5 RRs
   corresponds to the closest provable encloser, and the other pair
   corresponds to the next closer name.  The NSEC5PROOF corresponding to
   the next closer name MUST be computed on the fly by the authoritative
   server when responding to the query.  However, the NSEC5PROOF
   corresponding to the closest provable encloser MAY be precomputed and
   stored as part of zone signing.

   Precomputing NSEC5PROOF RRs can halve the number of online
   cryptographic computations required when responding to a negative
   query.  NSEC5PROOF RRs MAY be precomputed as part of zone signing as
   follows: For each NSEC5 RR, compute an NSEC5PROOF RR corresponding to
   the original owner name of the NSEC5 RR.  The content of the
   precomputed NSEC5PROOF record MUST be the same as if the record was
   computed on the fly when serving the zone.  NSEC5PROOF records are
   not part of the zone and SHOULD be stored separately from the zone
   file.

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.

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

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

   Notice,

   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. contents, as this would defeat a principal
   security goal of NSEC5.

   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.

   The minimal minimum delay between the steps 1. 1 and 2. 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 minimum delay between the steps 2. 2 and 3. 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 NSEC5
   keys.  See Section 14.3 15.2 for discussion on the security requirements considerations for NSEC5 private NSEC5
   keys.

9.5.  Zones Using Unknown Hash NSEC5 Algorithms

   Zones that are signed with unknown NSEC5 algorithm or by an unavailable NSEC5
   private NSEC5 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. updates [RFC2136].  The
   changes to the zone MUST be performed in a way, way that ensures that the
   zone satisfies the properties specified in Section 9.1 at any time.
   The process described in [RFC5155] Section 7.5 describes how to
   handle the issues surrounding the handling of empty non-terminals as
   well as Opt-Out.

   It is RECOMMENDED that the server rejects all updates containing
   changes to the NSEC5 chain (or and its related RRSIG RRs) 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.

   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 NSEC5 keys for the zone are
   required in addition to DNSSEC public keys.  Similarly to DNSKEY RRs,
   the NSEC5KEY RRs are present in at the zone apex.

   The NSEC5 RR is validated as follows:

   1.  Select a correct NSEC5 public NSEC5 key to validate the NSEC5PROOF. NSEC5 proof.
       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 NSEC5 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 on 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 are not satisfied, the
   response MUST be treated as bogus.

   Notice that determining the 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 NSEC5 Algorithms

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

12.  Special Considerations

12.1.  Transition Mechanism

   TODO: Not finished.  Following

   [TODO: The following information will be covered: covered.]

   o  Transition to NSEC5 from NSEC or NSEC3. NSEC/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. algorithms

12.2.  NSEC5  Private Keys NSEC5 keys

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

   The NSEC5 private NSEC5 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
   names, exceed the 255 octet length limit imposed by [RFC1035], [RFC1035] cannot
   use this specification.

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

   All NSEC5 algorithms defined in this document use 256-bit NSEC5 hash
   values.  Such a value can be encoded in 52 characters in Base32hex
   without padding.  When constructing the NSEC5 RR owner name, the
   encoded hash is prepended to the name of the zone as a single label
   which includes the length field of a single octet.  The maximal maximum
   length of the zone name in wire format using the 256-bit hash is
   therefore 202 octets (255 - 53).

13.  Performance Considerations

   This section compares NSEC, NSEC3, and  Implementation Status

   NSEC5 with regards to the size
   of denial-of-existence responses and performance impact on has been implemented for the Knot 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.2g, running an ordinary laptop on a single-core of a
   CPU manufactured in 2016.  The parameters of cryptographic operations
   were chosen to reflect the parameters used in the real-world
   application of DNSSEC.

13.1.1.  NSEC3 Hashing Performance

   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 authoritative server
   (version 1.6.4) and the salt.  We can assume that the
   input size will be smaller than 32 octets for most executions. Unbound recursive server (version 1.5.9).
   The measured implementation gives a stable performance for small
   input blocks up to 32 octets.  About 4e6 hashes per second can be
   computed given these parameters.

   The number of did not introduce 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 4e6 hashes per
   second.

13.1.2.  NSEC5 Hashing Performance

   The NSEC5 hash is computed in two steps: NSEC5 proof computation
   followed by hashing of the result.  As the proof computation involves
   relatively expensive RSA/EC library dependencies;
   all cryptographic operations, the final
   hashing will have insignificant impact on the overall performance.
   We can also expect difference between NSEC5 hashing (signing) and
   verification time.

   The measurement results for various NSEC5 algorithms and key sizes primitives are summarized in the following table:

   +----------------------+--------+-----------+----------+------------+
   | NSEC5 algorithm      |    Key |     Proof |    Perf. |      Perf. |
   |                      |   size |      size | (hash/s) | (verify/s) |
   |                      | (bits) |  (octets) |          |            |
   +----------------------+--------+-----------+----------+------------+
   | RSAFDH-SHA256-SHA256 |   1024 |       128 |     9500 |     120000 |
   | RSAFDH-SHA256-SHA256 |   2048 |       256 |     1500 |      46000 |
   | RSAFDH-SHA256-SHA256 |   4096 |       512 |      200 |      14000 |
   | EC-P256-SHA256       |    256 |        81 |     4700 |       4000 |
   +----------------------+--------+-----------+----------+------------+

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

   EC-P256-SHA256 trades off verification performance for shorter proof
   size and faster query processing at the nameserver.  In that case,
   both hash computation and verification performance will be already present in the
   order of 10^3 hashes per second.

13.1.3.  DNSSEC Signing Performance

   For completeness, the following table sumarrizes the signing and
   verification performance for different DNSSEC signing algorithms:

   +------------------+--------+-----------+-------------+-------------+
   | Algorithm        |    Key | Signature | Performance | Performance |
   |                  |   size |      size |    (sign/s) |  (verify/s) |
   |                  | (bits) |  (octets) |             |             |
   +------------------+--------+-----------+-------------+-------------+
   | RSASHA256        |   1024 |       128 |        9000 |      140000 |
   | RSASHA256        |   2048 |       256 |        1500 |       47000 |
   | RSASHA256        |   4096 |       512 |         200 |       14000 |
   | ECDSAP256SHA256  |    256 |        64 |        7400 |        4000 |
   | ECDSAP384SHA384  |    384 |        96 |        5000 |        1000 |
   | ECDSAP256SHA256* |    256 |        64 |       24000 |       11000 |
   +------------------+--------+-----------+-------------+-------------+

   * highly optimized implementation

   The retrieved values are important primarily for the purpose of
   evaluating performance of response validation.  The signing
   performance is usually not that important because the zone is signed
   offline.  However, when online signing is used, signing performace OpenSSL v1.0.2j,
   which is
   also important.

13.2.  Authoritative Server Startup

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

   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 by both implementations.  The authoritative server can precompute NSEC3 hashes for all
      domain names in implementation supports
   the NSEC3-signed zone on startup.  With respect to
      query answering, this can speed up inclusion full spectrum of NSEC3 RRs for
      existing domain names negative responses, (i.e., Closest provable encloser and QNAME
      for No Data response).

   NSEC5  Very similar considerations apply for NSEC3 NXDOMAIN, NODATA,
   Wildcard, Wildcard NODATA, and NSEC5.  There
      is a strong motivation to store the NSEC5PROOF values for existing
      domain names in order to reduce query processing time.  A possible
      way to do this, without inceasing the zone size, is to store
      NSEC5PROOF values in a persistent storage structure, as explained
      in Section 13.4. unsigned delegation).  The impact of NSEC3 and NSEC5 on the authoritative server startup
   performance is greatly
   implementation specific. supports the EC-P256-SHA256 algorithm.  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 code 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
   deliberately modular, so that the denial will EC-ED25519-SHA256 algorithm could
   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 list summarizes additional cryptographic operations
   performed implemented by using the authoritative server for authenticated denial worst-
   case scenario:

   o  NSEC:

      *  No cryptographic operations required.

   o  NSEC3:

      *  NSEC3 hash for Closest provable encloser

      *  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

13.4.  Precomputed NSEC5PROOF Values

   As we dicussed in the previous section, the worst-case authenticated
   denial scenario with NSEC5 entails the computation of two NSEC5 proof
   and hash values, one for the Closest provable encloser and one for
   the Next closer name.  For the latter, these values must be computed
   from scratch at query time.  However, the proof value for the former
   had been computed during startup, without being stored, Ed25519 elliptic curve [RFC8080] as part of
   the NSEC5 hash computation.

   The query processing time can be drastically reduced if the NSEC5
   proof values a
   drop-in replacement for all existing names in the zone are stored by the
   authoritative.  In that case, the P256 elliptic curve.  The authoritative identifies the
   Closest provable encloser name for the given query and looks up both
   the NSEC5 proof and hash value.  This limits the necessary
   computation during query processing to just one NSEC5 proof and hash
   value (that of the Next closer name).  For both variants of NSEC5,
   the proof computation time strongly dominates the final NSEC5 hash
   computation.  Therefore, by storing NSEC5 proof values query
   processing time is almost halved.

   On the other hand, this slightly increases the used storage space at
   the authoritative.  It should be noted that these values should not
   be part of
   server implements the zone explicitly.  They can be stored at an additional
   data structure.

13.5.  Response Lengths

   [nsec5ecc] precisely measured response lengths for NSEC, NSEC3 and
   NSEC5 using empirical data optimization from a sample second-level domain
   containing about 1000 names.  The sample zone was signed several
   times with different DNSSEC signing algorithms and different
   authenticated denial of existence mechanisms.

   For DNSKEY algorithms, RSASHA256 (2048-bit) and ECDSAPSHA256 were
   considered.  For authenticated denial, NSEC, NSEC3, NSEC5 with
   RSAFDH-SHA256-SHA256 (2048-bit), and NSEC5 with EC-P256-SHA256 were
   considered.  (Note that NSEC5 with EC-ED25519-SHA256 is identical Section 9.1.1 to
   EC-P256-SHA256 as for response size.)

   For each instance of precompute
   the signed zone, Name Error responses were
   collected by issuing DNS queries with a random five-character label
   prepended to NSEC5PROOF RRs matching each actual record name from the zone.  The average and
   standard deviation of the length of these responses are shown below.

   +-----------+--------------+------------------+---------------------+
   |           | DNSKEY       |   Average length |  Standard deviation |
   |           | algorithm    |         (octets) |            (octets) |
   +-----------+--------------+------------------+---------------------+
   | NSEC      | RSA          |             1116 |                  48 |
   | NSEC      | ECDSA        |              543 |                  24 |
   | NSEC3     | RSA          |             1440 |                 170 |
   | NSEC3     | ECDSA        |              752 |                  84 |
   | NSEC5/RSA | RSA          |             1767 |                   7 |
   | NSEC5/EC  | ECDSA        |              839 |                   7 |
   +-----------+--------------+------------------+---------------------+

13.6.  Summary

   As anticipated, NSEC and NSEC3 are the most efficient authenticated
   denial mechanisms, in terms of computation for authoritative server
   and resolver.  NSEC also has the shortest response lengths.  However,
   these mechanisms do not prevent zone enumeration.

   Regarding mechanisms that do prevent zone enumeration, NSEC5 should
   be examined in contrast with Minimally Covering NSEC Records or NSEC3
   White Lies [RFC7129]. record.

14.  Performance Considerations

   The following table summarizes their
   comparison in terms of response size, performance at the
   authoritative server, and performance at the resolver.  For NSEC3
   White Lies, RSASHA256 (2048-bit) and ECDSAPSHA256 were considered,
   and for NSEC5, RSAFDH-SHA256-SHA256 (2048-bit) and EC-P256-SHA256
   were considered.

   +---------------+-----------------+------------------+--------------+
   | Algorithm     | Response length |    Authoritative |     Resolver |
   |               |        (octets) |        (ops/sec) |    (ops/sec) |
   +---------------+-----------------+------------------+--------------+
   | NSEC3WL/RSA   |            1440 |             1500 |        47000 |
   | NSEC3WL/ECDSA |             752 |             7400 |         4000 |
   | NSEC5/RSA     |            1767 |             1500 |        46000 |
   | NSEC5/EC      |             839 |             4700 |         4000 |
   +---------------+-----------------+------------------+--------------+ of NSEC5 responses lengths are only slighly longer than NSEC3 response
   lengths: NSEC5/RSA has responses that are about 22% longer than
   NSEC3/RSA, while NSEC5/EC has responses that are about 13% longer
   than NSEC3/ECDSA.  For both NSEC3 and NSEC5, it is clear that EC-
   based solutions give much shorter responses.

   Regarding the computation performance, with RSA the difference is
   negligible for both nameserver and resolver, whereas with the EC-
   based schemes there is no slowdown for the resolver, and a slowdown
   of 1.5x for the server.  Importantly, we expect the slowdown to be
   smaller in practice because NSEC3 entails three signing/verifying
   computations per query been evaluated in the worst case (closest encloser, next
   closer, wildcard at closest encloser) whereas NSEC5 requires only
   two.  The table above does not capture this issue, it just measures
   number of signing/verifying operations per second.  Future versions
   of this draft will more accurately measure and compare NSEC5
   performance.

   Note also that while NSEC3 White Lies outperforms NSEC5 for certain
   cases, NSEC3 White Lies require authoratitive nameserver to store the
   private zone-signing key, making each nameserver a potential point of
   compromise.

14. [nsec5ecc].

15.  Security Considerations

14.1.

15.1.  Zone Enumeration Attacks

   NSEC5 is robust to zone enumeration via offline dictionary attacks by
   any attacker that does not know the NSEC5 private NSEC5 key.  Without the
   private NSEC5 key, that attacker cannot compute the NSEC5 proof that
   corresponds to a given name; the domain name.  The only way it can learn the
   NSEC5 proof value for a given domain name is by sending a queries for that name to querying the authoritative server.
   server for that name.  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 [nsec5] and DS RRs.  See also the
   discussion on key lengths in [nsec5].

14.3. [nsec5ecc].

15.2.  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 be used to modify the contents of the zone; this is zone contents, 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, key.  As
   such, a compromise of the private NSEC5 keys key 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 zone.  An adversary that knows learns the private NSEC5
   key can compute NSEC5 hashes
   offline, and thus launch can, however, perform offline dictionary zone-enumeration attacks.  Thus, a
   compromise of  For this
   reason, the private NSEC5 key effectively downgrades need only be as secure as the
   security of NSEC5 to that of NSEC3. DNSSEC
   records whose privacy (against zone enumeration) is being protected
   by NSEC5.  A formal cryptographic proof of this property is in [nsec5].

   If a zone owner wants to
   [nsec5] and [nsec5ecc].

   To preserve this property of NSEC5, the zone
   owner SHOULD choose the NSEC5 private NSEC5 key to MUST be
   different from the private zone-signing keys or key-signing keys for
   the zone.

14.4.

15.3.  Key Length Considerations

   The NSEC5 key must be long enough to withstand attacks for as long as
   the privacy of the zone contents 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  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.) 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 contents, need to remain
   secure only during their lifetime.

14.5.  Transitioning to a New

15.4.  NSEC5 Algorithm

   Although Hash Collisions

   If the NSEC5KEY RR formats include a NSEC5 hash algorithm parameter,
   this document does not define of a particular mechanism for safely
   transitioning from one QNAME collides with the 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 of the only practical and
   palatable transition mechanisms may require an intermediate
   transition to
   owner name of an insecure state, or NSEC5 RR, it will be impossible to prove the non-
   existence of the colliding QNAME.  However, the NSEC5 VRFs ensure
   that obtaining such a state collision is as difficult as obtaining a
   collision in the SHA-256 hash function (requiring approximately 2^128
   effort).  Note that uses NSEC or
   NSEC3 records instead of NSEC5.

15. DNSSEC already relies on the assumption 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].

16.  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. TBD.

      NSEC5 value XXX. TBD.

      NSEC5PROOF value XXX. TBD.

   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.

      1 is RSAFDH-SHA256-SHA256.

      2 is EC-P256-SHA256.

      3

      2 is EC-ED25519-SHA256.

      4-255

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

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

      XXX

      TBD is NSEC5-ECDSAP384SHA384 NSEC5-ED25519, alias for ECDSAP384SHA384 (14).

16. ED25519 (15).

17.  Contributors

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

17. performance.

18.  References

17.1.

18.1.  Normative References

   [RFC1034]  Mockapetris, P., "Domain names - concepts and facilities",
              STD 13, RFC 1034, DOI 10.17487/RFC1034, November 1987,
              <http://www.rfc-editor.org/info/rfc1034>.

   [RFC1035]  Mockapetris, P., "Domain names - implementation and
              specification", STD 13, RFC 1035, DOI 10.17487/RFC1035, November 1987, <http://www.rfc-editor.org/info/rfc1035>. 1987.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <http://www.rfc-editor.org/info/rfc2119>. 1997.

   [RFC2136]  Vixie, P., Ed., Thomson, S., Rekhter, Y., and J. Bound,
              "Dynamic Updates in the Domain Name System (DNS UPDATE)",
              RFC 2136, DOI 10.17487/RFC2136, April 1997,
              <http://www.rfc-editor.org/info/rfc2136>.

   [RFC2181]  Elz, R. and R. Bush, "Clarifications to the DNS
              Specification", RFC 2181, DOI 10.17487/RFC2181, July 1997,
              <http://www.rfc-editor.org/info/rfc2181>.

   [RFC2308]  Andrews, M., "Negative Caching of DNS Queries (DNS
              NCACHE)", RFC 2308, DOI 10.17487/RFC2308, March 1998,
              <http://www.rfc-editor.org/info/rfc2308>.

   [RFC3110]  Eastlake 3rd, D., "RSA/SHA-1 SIGs and RSA KEYs in the
              Domain Name System (DNS)", RFC 3110, DOI 10.17487/RFC3110,
              May 2001, <http://www.rfc-editor.org/info/rfc3110>.

   [RFC3447]  Jonsson, J. and B. Kaliski, "Public-Key Cryptography
              Standards (PKCS) #1: RSA Cryptography Specifications
              Version 2.1", RFC 3447, DOI 10.17487/RFC3447, February
              2003, <http://www.rfc-editor.org/info/rfc3447>.

   [RFC4033]  Arends, R., Austein, R., Larson, M., Massey, D., and S.
              Rose, "DNS Security Introduction and Requirements", RFC
              4033, DOI 10.17487/RFC4033, March 2005,
              <http://www.rfc-editor.org/info/rfc4033>. 2005.

   [RFC4034]  Arends, R., Austein, R., Larson, M., Massey, D., and S.
              Rose, "Resource Records for the DNS Security Extensions",
              RFC 4034, DOI 10.17487/RFC4034, March 2005,
              <http://www.rfc-editor.org/info/rfc4034>. 2005.

   [RFC4035]  Arends, R., Austein, R., Larson, M., Massey, D., and S.
              Rose, "Protocol Modifications for the DNS Security
              Extensions", RFC 4035, DOI 10.17487/RFC4035, March 2005,
              <http://www.rfc-editor.org/info/rfc4035>. 2005.

   [RFC4648]  Josefsson, S., "The Base16, Base32, and Base64 Data
              Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006,
              <http://www.rfc-editor.org/info/rfc4648>.

   [RFC5114]  Lepinski, M. and S. Kent, "Additional Diffie-Hellman
              Groups for Use with IETF Standards", RFC 5114, DOI
              10.17487/RFC5114, January 2008,
              <http://www.rfc-editor.org/info/rfc5114>.

   [RFC5155]  Laurie, B., Sisson, G., Arends, R., and D. Blacka, "DNS
              Security (DNSSEC) Hashed Authenticated Denial of
              Existence", RFC 5155, DOI 10.17487/RFC5155, March 2008,
              <http://www.rfc-editor.org/info/rfc5155>. 2008.

   [RFC6234]  Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
              (SHA and SHA-based HMAC and HKDF)", RFC 6234, DOI 10.17487/RFC6234, 10.17487
              /RFC6234, May 2011,
              <http://www.rfc-editor.org/info/rfc6234>.

   [RFC6605]  Hoffman, P. and W. Wijngaards, "Elliptic Curve Digital
              Signature Algorithm (DSA) for DNSSEC", RFC 6605,
              DOI 10.17487/RFC6605, April 2012,
              <http://www.rfc-editor.org/info/rfc6605>.
              2012.

   [RFC7748]  Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
              for Security", RFC 7748, DOI 10.17487/RFC7748, January
              2016, <http://www.rfc-editor.org/info/rfc7748>.

   [I-D.ietf-curdle-dnskey-ed25519]

   [RFC8080]  Sury, O. and R. Edmonds, "Ed25519 "Edwards-Curve Digital Security
              Algorithm (EdDSA) for DNSSEC", draft-ietf-
              curdle-dnskey-ed25519-01 (work in progress), RFC 8080, DOI 10.17487/
              RFC8080, February
              2016. 2017,
              <http://www.rfc-editor.org/info/rfc8080>.

   [FIPS-186-3]
              National Institute for Standards and Technology, "Digital
              Signature Standard (DSS)", FIPS PUB 186-3, June 2009.

   [SECG1]    Standards for Efficient Cryptography Group (SECG), "SEC 1:
              Elliptic Curve Cryptography", Version 2.0, May 2009,
              <http://www.secg.org/sec1-v2.pdf>.

17.2.

18.2.  Informative References

   [nsec5]    Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L.,
              Vasant, S., and A. Ziv, "NSEC5: Provably Preventing DNSSEC
              Zone Enumeration", in NDSS'15, July 2014. 2014, <https://
              eprint.iacr.org/2014/582.pdf>.

   [nsec5ecc]
              Goldberg,
              Papadopoulos, D., Wessels, D., Huque, S., Vcelak, J.,
              Naor, M., Papadopoulos, D., and L. Reyzin,
              "NSEC5 from Elliptic Curves", L., and S. Goldberg, "Can NSEC5 be
              Practical for DNSSEC Deployments?", in ePrint Cryptology
              Archive
              2016/083, January 2016. 2017/099, February 2017, <https://eprint.iacr.org/
              2017/099.pdf>.

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

   [nmap-nsec-enum]
              Bond, J., "nmap: dns-nsec-enum", 2011, <https://nmap.org/
              nsedoc/scripts/dns-nsec-enum.html>.

   [nmap-nsec3-enum]
              Nikolic, A. and J. Bond, "nmap: dns-nsec3-enum", 2011,
              <https://nmap.org/nsedoc/scripts/dns-nsec3-enum.html>.

   [nsec3map]
              anonion0, ., "nsec3map with John the Ripper plugin", 2015,
              <https://github.com/anonion0/nsec3map.>.

   [ldns-walk]
              NLNetLabs, ., "ldns", 2015,
              <http://git.nlnetlabs.nl/ldns/tree/examples/ldns-walk.c>.

   [MRV99]    Michali, S., Rabin, M., and S. Vadhan, "Verifiable Random
              Functions", in FOCS, 1999.

   [RFC6781]  Kolkman, O., Mekking, W., and R. Gieben, "DNSSEC
              Operational Practices, Version 2", RFC 6781, DOI 10.17487/RFC6781, 10.17487/
              RFC6781, December 2012,
              <http://www.rfc-editor.org/info/rfc6781>.

   [RFC7129]  Gieben, R. and W. Mekking, "Authenticated Denial of
              Existence in the DNS", RFC 7129, DOI 10.17487/RFC7129,
              February 2014, <http://www.rfc-editor.org/info/rfc7129>.

   [RFC7719]  Hoffman, P., Sullivan, A., and K. Fujiwara, "DNS
              Terminology", RFC 7719, DOI 10.17487/RFC7719, December
              2015, <http://www.rfc-editor.org/info/rfc7719>.

   [I-D.gieben-nsec4]
              Gieben, R. and M. Mekking, "DNS Security (DNSSEC)
              Authenticated Denial of Existence", draft-gieben-nsec4-01
              (work in progress), July 2012.

Appendix A.  RSA Full Domain Hash Algorithm  Elliptic Curve VRF

   The Full Domain Hash (FDH) is Elliptic Curve Verifiable Random Function (EC-VRF) operates in 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
   cyclic group G of the RSA modulus n in octets

   Fixed options:

      Hash - hash function to prime order with generator g.  The cyclic group G
   MAY be used over the NIST-P256 elliptic curve, 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 curve parameters as
      defined
   specified in Section 4.2 of [RFC3447]

      RSASP1 - RSA signature primitive as [FIPS-186-3] (Section D.1.2.3) and [RFC5114]
   (Section 2.6).  The group G MAY alternatively be over the Ed25519
   elliptic curve with parameters defined in Section 5.2.1 [RFC7748] (Section 4.1).
   The security of
      [RFC3447]

      RSAVP1 - RSA verification primitive as defined this VRF follows from the decisional Diffie-Hellman
   (DDH) assumption in Section 5.2.2 of
      [RFC3447]

      MGF1 - Mask Generation Function based on a hash function as
      defined the cyclic group G 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

   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.  Elliptic Curve random oracle model.
   Formal security proofs for this VRF

   The Elliptic Curve Verifiable Random Function (VRF) is a EC-based
   scheme that allows authentication of hashes using public-key
   cryptography. are in [nsec5ecc].

   Fixed options:

      G - EC elliptic curve (EC) group

   Used parameters:

      g^x - EC public key

      x - EC private key

      q - primer prime order of group G
      g - generator of group G

   Used primitives:

      "" - empty octet string

      || - octet string concatenation

      p^k - EC point multiplication

      p1*p2 - EC point addition

      SHA256 - hash function SHA-256 as specified in [RFC6234]

      ECP2OS - EC point to octet string conversion with point
      compression as specified in Section 2.3.3 of [SECG1]

      OS2ECP - octet string to EC point conversion with point
      compression as specified in Section 2.3.4 of [SECG1]

B.1.  ECVRF

A.1.  EC-VRF Auxiliary Functions

A.1.1.  EC-VRF Hash To Curve

   ECVRF_hash_to_curve(m)

   Input:

      m - value to be hashed, an octet string

   Output:

      h - hashed value, EC point

   Steps:

   1.  c = 0

   2.  C = I2OSP(c, 4)

   3.  xc = SHA256(m || C)

   4.  p = 0x02 || xc

   5.  If p is not a valid octet string representing encoded compressed
       point in G:

       A.

       a.  c = c + 1

       B.
       b.  Go to step 2.

   6.  h = OS2ECP(p)

   7.  Output h

B.2.  ECVRF Auxiliary Functions

B.2.1.  ECVRF

A.1.2.  EC-VRF Hash Points

   ECVRF_hash_points(p_1, p_2, ..., p_n)

   Input:

      p_x - EC point in G

   Output:

      h - hash value, integer between 0 and 2^128-1

   Steps:

   1.  P = ""

   2.  for p in [p_1, p_2, ... p_n]:
       P = P || ECP2OS(p)

   3.  h' = SHA256(P)

   4.  h = OS2IP(first 16 octets of h')

   5.  Output h

B.2.2.  ECVRF Proof To Hash

   ECVRF_proof_to_hash(gamma)

   Input:

      gamma - VRF proof, EC point in G with coordinates (x, y)

   Output:

      beta - VRF hash, octet string (32 octets)

   Steps:

   1.  beta = I2OSP(x, 32)

   2.  Output beta

   Note: Because of the format of compressed form of an elliptic curve,
   the hash can be retrieved from an encoded gamma simply by omitting
   the first octet of the gamma.

B.2.3.  ECVRF

A.1.3.  EC-VRF Decode Proof

   ECVRF_decode_proof(pi)

   Input:

      pi - VRF proof, octet string (81 octets)

   Output:

      gamma - EC point

      c - integer between 0 and 2^128-1

      s - integer between 0 and 2^256-1

   Steps:

   1.  let gamma', c', s' be pi split after 33-rd and 49-th octet

   2.  gamma = OS2ECP(gamma')

   3.  c = OS2IP(c')

   4.  s = OS2IP(s')

   5.  Output gamma, c, and s

B.3.  ECVRF Signing

   ECVRF_sign(g^x,

A.2.  EC-VRF Proving

   ECVRF_PROVE(g^x, x, alpha)

   Input:

      g^x - EC public key

      x - EC private key

      alpha - message to be signed, octet string

   Output:

      pi - VRF proof, octet string (81 octets)

      beta - VRF hash, octet string (32 octets)

   Steps:

   1.  h = ECVRF_hash_to_curve(alpha)

   2.  gamma = h^x

   3.  choose a nonce k from [0, q-1]

   4.  c = ECVRF_hash_points(g, h, g^x, h^x, g^k, h^k)

   5.  s = k - c*q mod q

   6.  pi = ECP2OS(gamma) || I2OSP(c, 16) || I2OSP(s, 32)

   7.  beta = h2(gamma)

   8.  Output pi and beta

B.4.  ECVRF Verification

A.3.  EC-VRF Proof To Hash
   ECVRF_PROOF2HASH(gamma)

   Input:

      gamma - VRF proof, EC point in G with coordinates (x, y)

   Output:

      beta - VRF hash, octet string (32 octets)

   Steps:

   1.  beta = I2OSP(x, 32)

   2.  Output beta

   Note: Because of the format of the compressed form of an elliptic
   curve, the hash can be retrieved from an encoded gamma simply by
   omitting the first octet of the gamma.

A.4.  EC-VRF Verifying

   ECVRF_VERIFY(g^x, pi, alpha)

   Input:

      g^x - EC public key

      pi - VRF proof, octet string

      alpha - message to verify, octet string

   Output:

      "valid signature" or "invalid signature"

      beta - VRF hash, octet string (32 octets)

   Steps:

   1.  gamma, c, s = ECVRF_decode_proof(pi)

   2.  u = (g^x)^c * g^s

   3.  h = ECVRF_hash_to_curve(alpha)

   4.  v = gamma^c * h^s
   5.  c' = ECVRF_hash_points(g, h, g^x, gamma, u, v)

   6.  beta = ECVRF_proof_to_hash(gamma) ECVRF_PROOF2HASH(gamma)

   7.  If c and c' are the same, output "valid signature"; else output
       "invalid signature".  Output beta.

   [[CREF1: TODO:

   [[TODO: check validity of gamma before hashing --Jan]] hashing]]

Appendix C. B.  Change Log

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

      01 - added Add Performance Considerations section section.

      02 - Elliptic Curve Add elliptic curve based VRF for NSEC5 proofs; VRF.  Add measurement of response
      sizes based on empirical data data.

      03 - Precomputed Mention precomputed NSEC5PROOF Values (section Section 13.4)

Appendix D.  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. Performance
      Considerations section.

      04 - Edit Rationale, How to add new NSEC5 hashing algorithm.  We will need to add new
       DNSSEC algorithm identifiers again.

   3.  NSEC Works, and NSEC3 define optional steps Security Consideration
      sections 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 clarity.  Edit Zone Signing section, adding
      precomputation of NSEC5PROOFs.  Remove RSA-based NSEC5
      specification.  Rewrite Performance Considerations section.

   5.  Contributor list has to be completed. and
      Implementation Status sections.

Authors' Addresses

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

   EMail: jan.vcelak@nic.cz
   Sharon Goldberg
   Boston University
   111 Cummington St, MCS135
   Boston, MA  02215
   USA

   EMail: goldbe@cs.bu.edu

   Dimitrios Papadopoulos
   Boston
   University
   111 Cummington St, MCS135 of Maryland
   8223 Paint Branch Dr
   College Park, MD  20740
   USA

   EMail: dipapado@umd.edu

   Shumon Huque
   Salesforce
   2550 Wasser Terrace
   Herndon, VA  20171
   USA

   EMail: shuque@gmail.com

   David C Lawrence
   Akamai Technologies
   150 Broadway
   Boston, MA  02215  02142-1054
   USA

   EMail: dipapado@bu.edu tale@akamai.com