idnits 2.17.1 draft-vcelak-nsec5-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 07, 2017) is 2607 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Downref: Normative reference to an Informational RFC: RFC 5114 ** Downref: Normative reference to an Informational RFC: RFC 6234 ** Downref: Normative reference to an Informational RFC: RFC 7748 -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS-186-3' -- Possible downref: Non-RFC (?) normative reference: ref. 'SECG1' -- Obsolete informational reference (is this intentional?): RFC 7719 (Obsoleted by RFC 8499) Summary: 3 errors (**), 0 flaws (~~), 1 warning (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group J. Vcelak 3 Internet-Draft CZ.NIC 4 Intended status: Standards Track S. Goldberg 5 Expires: September 08, 2017 Boston University 6 D. Papadopoulos 7 University of Maryland 8 S. Huque 9 Salesforce 10 D. Lawrence 11 Akamai Technologies 12 March 07, 2017 14 NSEC5, DNSSEC Authenticated Denial of Existence 15 draft-vcelak-nsec5-04 17 Abstract 19 The Domain Name System Security Extensions (DNSSEC) introduced the 20 NSEC resource record (RR) for authenticated denial of existence and 21 the NSEC3 RR for hashed authenticated denial of existence. This 22 document introduces NSEC5 as an alternative mechanism for DNSSEC 23 authenticated denial of existence. NSEC5 uses verifiable random 24 functions (VRFs) to prevent offline enumeration of zone contents. 25 NSEC5 also protects the integrity of the zone contents even if an 26 adversary compromises one of the authoritative servers for the zone. 27 Integrity is preserved because NSEC5 does not require private zone- 28 signing keys to be present on all authoritative servers for the zone, 29 in contrast to DNSSEC online signing schemes like NSEC3 White Lies. 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at http://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on September 08, 2017. 48 Copyright Notice 50 Copyright (c) 2017 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (http://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 66 1.1. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 3 67 1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 5 68 1.3. Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 69 2. Backward Compatibility . . . . . . . . . . . . . . . . . . . 6 70 3. How NSEC5 Works . . . . . . . . . . . . . . . . . . . . . . . 7 71 4. NSEC5 Algorithms . . . . . . . . . . . . . . . . . . . . . . 8 72 5. The NSEC5KEY Resource Record . . . . . . . . . . . . . . . . 8 73 5.1. NSEC5KEY RDATA Wire Format . . . . . . . . . . . . . . . 8 74 5.2. NSEC5KEY RDATA Presentation Format . . . . . . . . . . . 9 75 6. The NSEC5 Resource Record . . . . . . . . . . . . . . . . . . 9 76 6.1. NSEC5 RDATA Wire Format . . . . . . . . . . . . . . . . . 9 77 6.2. NSEC5 Flags Field . . . . . . . . . . . . . . . . . . . . 10 78 6.3. NSEC5 RDATA Presentation Format . . . . . . . . . . . . . 10 79 7. The NSEC5PROOF Resource Record . . . . . . . . . . . . . . . 11 80 7.1. NSEC5PROOF RDATA Wire Format . . . . . . . . . . . . . . 11 81 7.2. NSEC5PROOF RDATA Presentation Format . . . . . . . . . . 11 82 8. Types of Authenticated Denial of Existence with NSEC5 . . . . 12 83 8.1. Name Error Responses . . . . . . . . . . . . . . . . . . 12 84 8.2. No Data Responses . . . . . . . . . . . . . . . . . . . . 13 85 8.2.1. No Data Response, Opt-Out Not In Effect . . . . . . . 13 86 8.2.2. No Data Response, Opt-Out In Effect . . . . . . . . . 13 87 8.3. Wildcard Responses . . . . . . . . . . . . . . . . . . . 14 88 8.4. Wildcard No Data Responses . . . . . . . . . . . . . . . 14 89 9. Authoritative Server Considerations . . . . . . . . . . . . . 15 90 9.1. Zone Signing . . . . . . . . . . . . . . . . . . . . . . 15 91 9.1.1. Precomputing Closest Provable Encloser Proofs . . . . 16 92 9.2. Zone Serving . . . . . . . . . . . . . . . . . . . . . . 17 93 9.3. NSEC5KEY Rollover Mechanism . . . . . . . . . . . . . . . 17 94 9.4. Secondary Servers . . . . . . . . . . . . . . . . . . . . 18 95 9.5. Zones Using Unknown NSEC5 Algorithms . . . . . . . . . . 18 96 9.6. Dynamic Updates . . . . . . . . . . . . . . . . . . . . . 18 97 10. Resolver Considerations . . . . . . . . . . . . . . . . . . . 18 98 11. Validator Considerations . . . . . . . . . . . . . . . . . . 19 99 11.1. Validating Responses . . . . . . . . . . . . . . . . . . 19 100 11.2. Validating Referrals to Unsigned Subzones . . . . . . . 19 101 11.3. Responses With Unknown NSEC5 Algorithms . . . . . . . . 20 102 12. Special Considerations . . . . . . . . . . . . . . . . . . . 20 103 12.1. Transition Mechanism . . . . . . . . . . . . . . . . . . 20 104 12.2. Private NSEC5 keys . . . . . . . . . . . . . . . . . . . 20 105 12.3. Domain Name Length Restrictions . . . . . . . . . . . . 20 106 13. Implementation Status . . . . . . . . . . . . . . . . . . . . 21 107 14. Performance Considerations . . . . . . . . . . . . . . . . . 21 108 15. Security Considerations . . . . . . . . . . . . . . . . . . . 21 109 15.1. Zone Enumeration Attacks . . . . . . . . . . . . . . . . 21 110 15.2. Compromise of the Private NSEC5 Key . . . . . . . . . . 21 111 15.3. Key Length Considerations . . . . . . . . . . . . . . . 22 112 15.4. NSEC5 Hash Collisions . . . . . . . . . . . . . . . . . 22 113 16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 114 17. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 23 115 18. References . . . . . . . . . . . . . . . . . . . . . . . . . 23 116 18.1. Normative References . . . . . . . . . . . . . . . . . . 23 117 18.2. Informative References . . . . . . . . . . . . . . . . . 25 118 Appendix A. Elliptic Curve VRF . . . . . . . . . . . . . . . . . 26 119 A.1. EC-VRF Auxiliary Functions . . . . . . . . . . . . . . . 27 120 A.1.1. EC-VRF Hash To Curve . . . . . . . . . . . . . . . . 27 121 A.1.2. EC-VRF Hash Points . . . . . . . . . . . . . . . . . 28 122 A.1.3. EC-VRF Decode Proof . . . . . . . . . . . . . . . . . 28 123 A.2. EC-VRF Proving . . . . . . . . . . . . . . . . . . . . . 29 124 A.3. EC-VRF Proof To Hash . . . . . . . . . . . . . . . . . . 29 125 A.4. EC-VRF Verifying . . . . . . . . . . . . . . . . . . . . 30 126 Appendix B. Change Log . . . . . . . . . . . . . . . . . . . . . 31 128 1. Introduction 130 1.1. Rationale 131 NSEC5 provides an alternative mechanism for authenticated denial of 132 existence for the DNS Security Extensions (DNSSEC). NSEC5 has two 133 key security properties. First, NSEC5 protects the integrity of the 134 zone contents even if an adversary compromises one of the 135 authoritative servers for the zone. Second, NSEC5 prevents offline 136 zone enumeration, where an adversary makes a small number of online 137 DNS queries and then processes them offline in order to learn all of 138 the names in a zone. Zone enumeration can be used to identify 139 routers, servers or other "things" that could then be targeted in 140 more complex attacks. An enumerated zone can also be a source of 141 probable email addresses for spam, or as a "key for multiple WHOIS 142 queries to reveal registrant data that many registries may have legal 143 obligations to protect" [RFC5155]. 145 All other DNSSEC mechanisms for authenticated denial of existence 146 either fail to preserve integrity against a compromised server, or 147 fail to prevent offline zone enumeration. 149 When offline signing with NSEC is used [RFC4034], an NSEC chain of 150 all existing domain names in the zone is constructed and signed 151 offline. The chain is made of resource records (RRs), where each RR 152 represents two consecutive domain names in canonical order present in 153 the zone. The authoritative server proves the non-existence of a 154 name by presenting a signed NSEC RR which covers the name. Because 155 the authoritative server does not need not to know the private zone- 156 signing key, the integrity of the zone is protected even if the 157 server is compromised. However, the NSEC chain allows for easy zone 158 enumeration: N queries to the server suffice to learn all N names in 159 the zone (see e.g., [nmap-nsec-enum], [nsec3map], and [ldns-walk]). 161 When offline signing with NSEC3 is used [RFC5155], the original names 162 in the NSEC chain are replaced by their cryptographic hashes. 163 Offline signing ensures that NSEC3 preserves integrity even if an 164 authoritative server is compromised. However, offline zone 165 enumeration is still possible with NSEC3 (see e.g., [nsec3walker], 166 [nsec3gpu]), and is part of standard network reconnaissance tools 167 (e.g., [nmap-nsec3-enum], [nsec3map]). 169 When online signing is used, the authoritative server holds the 170 private zone-signing key and uses this key to synthesize NSEC or 171 NSEC3 responses on the fly (e.g. NSEC3 White Lies (NSEC3-WL) or 172 Minimally-Covering NSEC, both described in [RFC7129]). Because the 173 synthesized response only contains information about the queried name 174 (but not about any other name in the zone), offline zone enumeration 175 is not possible. However, because the authoritative server holds the 176 private zone-signing key, integrity is lost if the authoritative 177 server is compromised. 179 +----------+-------------+---------------+----------------+---------+ 180 | Scheme | Integrity | Integrity vs | Prevents | Online | 181 | | vs network | compromised | offline zone | crypto? | 182 | | attacks? | auth. server? | enumeration? | | 183 +----------+-------------+---------------+----------------+---------+ 184 | Unsigned | NO | NO | YES | NO | 185 | NSEC | YES | YES | NO | NO | 186 | NSEC3 | YES | YES | NO | NO | 187 | NSEC3-WL | YES | NO | YES | YES | 188 | NSEC5 | YES | YES | YES | YES | 189 +----------+-------------+---------------+----------------+---------+ 191 NSEC5 prevents offline zone enumeration and also protects integrity 192 even if a zone's authoritative server is compromised. To do this, 193 NSEC5 replaces the unkeyed cryptographic hash function used in NSEC3 194 with a verifiable random function (VRF) [MRV99]. A VRF is the 195 public-key version of a keyed cryptographic hash. Only the holder of 196 the private VRF key can compute the hash, but anyone with public VRF 197 key can verify the correctness of the hash. 199 The public VRF key is distributed in an NSEC5KEY RR, similar to a 200 DNSKEY RR, and is used to verify NSEC5 hash values. The private VRF 201 key is present on all authoritative servers for the zone, and is used 202 to compute hash values. For every query that elicits a negative 203 response, the authoritative server hashes the query on the fly using 204 the private VRF key, and also returns the corresponding precomputed 205 NSEC5 record(s). In contrast to the online signing approach 206 [RFC7129], the private key that is present on all authoritative 207 servers for NSEC5 cannot be used to modify the zone contents. 209 Like online signing approaches, NSEC5 requires the authoritative 210 server to perform online public key cryptographic operations for 211 every query eliciting a denying response. This is necessary; [nsec5] 212 proved that online cryptography is required to prevent offline zone 213 enumeration while still protecting the integrity of zone contents 214 against network attacks. 216 NSEC5 is not intended to replace NSEC or NSEC3. It is an alternative 217 mechanism for authenticated denial of existence. This document 218 specifies NSEC5 based on the FIPS 186-3 P-256 elliptic curve and on 219 the Ed25519 elliptic curve. A formal cryptographic proof of security 220 for elliptic curve (EC) NSEC5 is in [nsec5ecc]. 222 1.2. Requirements 223 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 224 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 225 document are to be interpreted as described in [RFC2119]. 227 1.3. Terminology 229 The reader is assumed to be familiar with the basic DNS and DNSSEC 230 concepts described in [RFC1034], [RFC1035], [RFC4033], [RFC4034], and 231 [RFC4035]; subsequent RFCs that update them in [RFC2136], [RFC2181], 232 [RFC2308], [RFC5155], and [RFC7129]; and DNS terms in [RFC7719]. 234 The following terminology is used through this document: 236 Base32hex: The "Base 32 Encoding with Extended Hex Alphabet" as 237 specified in [RFC4648]. The padding characters ("=") are not used 238 in the NSEC5 specification. 240 Base64: The "Base 64 Encoding" as specified in [RFC4648]. 242 QNAME: The domain name being queried (query name). 244 Private NSEC5 key: The private key for the verifiable random 245 function (VRF). 247 Public NSEC5 key: The public key for the VRF. 249 NSEC5 proof: A VRF proof. The holder of the private NSEC5 key 250 (e.g., authoritative server) can compute the NSEC5 proof for an 251 input domain name. Anyone who knows the public VRF key can verify 252 that the NSEC5 proof corresponds to the input domain name. 254 NSEC5 hash: A cryptographic digest of an NSEC5 proof. If the NSEC5 255 proof is known, anyone can compute its corresponding NSEC5 hash. 257 NSEC5 algorithm: A triple of VRF algorithms that compute an NSEC5 258 proof, verify an NSEC5 proof, and process an NSEC5 proof to obtain 259 its NSEC5 hash. 261 2. Backward Compatibility 263 The specification describes a protocol change that is not backward 264 compatible with [RFC4035] and [RFC5155]. An NSEC5-unaware resolver 265 will fail to validate responses introduced by this document. 267 To prevent NSEC5-unaware resolvers from attempting to validate the 268 responses, new DNSSEC algorithms identifiers are introduced in 269 Section 16 which alias existing algorithm numbers. The zones signed 270 according to this specification MUST use only these algorithm 271 identifiers, thus NSEC5-unaware resolvers will treat the zone as 272 insecure. 274 3. How NSEC5 Works 276 With NSEC5, the original domain name is hashed using the VRF using 277 the following steps: 279 1. The domain name is processed using a VRF keyed with the private 280 NSEC5 key to obtain the NSEC5 proof. Anyone who knows the public 281 NSEC5 key, normally acquired via an NSEC5KEY RR, can verify that 282 a given NSEC5 proof corresponds to a given domain name. 284 2. The NSEC5 proof is then processed using a publicly-computable VRF 285 proof-to-hash function to obtain the NSEC5 hash. The NSEC5 hash 286 can be computed by anyone who knows the input NSEC5 proof. 288 The NSEC5 hash determines the position of a domain name in an NSEC5 289 chain. 291 To sign a zone, the private NSEC5 key is used to compute the NSEC5 292 hashes for each name in the zone. These NSEC5 hashes are sorted in 293 canonical order [RFC4034] , and each consecutive pair forms an NSEC5 294 RR. Each NSEC5 RR is signed offline using the private zone-signing 295 key. The resulting signed chain of NSEC5 RRs is provided to all 296 authoritative servers for the zone, along with the private NSEC5 key. 298 To prove non-existence of a particular domain name in response to a 299 query, the server uses the private NSEC5 key to compute the NSEC5 300 proof and NSEC5 hash corresponding to the queried name. The server 301 then identifies the NSEC5 RR that covers the NSEC5 hash. The server 302 then responds with the NSEC5 RR and its corresponding RRSIG signature 303 RRset, as well as a synthesized NSEC5PROOF RR that contains the NSEC5 304 proof corresponding to the queried name. 306 To validate the response, the client verifies the following items: 308 o The client uses the public NSEC5 key, normally acquired from the 309 NSEC5KEY RR, to verify that the NSEC5 proof in the NSEC5PROOF RR 310 corresponds to the queried name. 312 o The client uses the VRF proof-to-hash function to compute the 313 NSEC5 hash from the NSEC5 proof in the NSEC5PROOF RR. The client 314 verifies that the NSEC5 hash is covered by the NSEC5 RR. 316 o The client verifies that the NSEC5 RR is validly signed by the 317 RRSIG RRset. 319 4. NSEC5 Algorithms 321 The algorithms used for NSEC5 authenticated denial are independent of 322 the algorithms used for DNSSEC signing. An NSEC5 algorithm defines 323 how the NSEC5 proof and the NSEC5 hash are computed and validated. 325 The input for the NSEC5 proof computation is an RR owner name in 326 [RFC4034] canonical wire format followed by a private NSEC5 key. The 327 output is an octet string. 329 The input for the NSEC5 hash computation is the corresponding NSEC5 330 proof; the output is an octet string. 332 This document defines EC-P256-SHA256 NSEC5 algorithm as follows: 334 o The NSEC5 proof is computed using an Elliptic Curve VRF with FIPS 335 186-3 P-256 curve. The proof computation and verification, and 336 the proof-to-hash function are formally specified in Appendix A. 337 The curve parameters are specified in [FIPS-186-3] 338 (Section D.1.2.3) and [RFC5114] (Section 2.6). 340 o The NSEC5 hash is the x-coordinate of the group element gamma from 341 the NSEC5 proof (specified in Appendix A), encoded as a 32-octet 342 unsigned integer in network byte order. In practice, the hash is 343 a substring of the proof ranging from 2nd through 33th octet of 344 the proof, inclusive. 346 o The public key format to be used in the NSEC5KEY RR is defined in 347 Section 4 of [RFC6605] and thus is the same as the format used to 348 store ECDSA public keys in DNSKEY RRs. 350 This document defines EC-ED25519-SHA256 NSEC5 algorithm as follows: 352 o The NSEC5 proof and NSEC5 hash are the same as with EC-P256-SHA256 353 but using Ed25519 elliptic curve with parameters defined in 354 [RFC7748] Section 4.1. 356 o The public key format to be used in the NSEC5KEY RR is defined in 357 Section 3 of [RFC8080] and thus is the same as the format used to 358 store Ed25519 public keys in DNSKEY RRs. 360 5. The NSEC5KEY Resource Record 362 The NSEC5KEY RR stores a public NSEC5 key. The key allows clients to 363 validate an NSEC5 proof sent by a server. 365 5.1. NSEC5KEY RDATA Wire Format 366 The RDATA for NSEC5KEY RR is as shown below: 368 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 369 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 370 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 371 | Algorithm | Public Key / 372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 374 Algorithm is a single octet identifying the NSEC5 algorithm. 376 Public Key is a variable-sized field holding public key material for 377 NSEC5 proof verification. 379 5.2. NSEC5KEY RDATA Presentation Format 381 The presentation format of the NSEC5KEY RDATA is as follows: 383 The Algorithm field is represented as an unsigned decimal integer. 385 The Public Key field is represented in Base64 encoding. Whitespace 386 is allowed within the Base64 text. 388 6. The NSEC5 Resource Record 390 The NSEC5 RR provides authenticated denial of existence for an RRset 391 or domain name. One NSEC5 RR represents one piece of an NSEC5 chain, 392 proving existence of the owner name and non-existence of other domain 393 names in the part of the hashed domain space covered until the next 394 owner name hashed in the RDATA. 396 6.1. NSEC5 RDATA Wire Format 398 The RDATA for NSEC5 RR is as shown below: 400 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 401 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 402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 403 | Key Tag | Flags | Next Length | 404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 405 | Next Hashed Owner Name / 406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 407 / Type Bit Maps / 408 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 410 The Key Tag field contains the key tag value of the NSEC5KEY RR that 411 validates the NSEC5 RR, in network byte order. The value is computed 412 from the NSEC5KEY RDATA using the same algorithm, which is used to 413 compute key tag values for DNSKEY RRs. The algorithm is defined in 414 [RFC4034]. 416 The Flags field is a single octet. The meaning of individual bits of 417 the field is defined in Section 6.2. 419 The Next Length field is an unsigned single octet specifying the 420 length of the Next Hashed Owner Name field in octets. 422 The Next Hashed Owner Name field is a sequence of binary octets. It 423 contains an NSEC5 hash of the next domain name in the NSEC5 chain. 425 Type Bit Maps is a variable-sized field encoding RR types present at 426 the original owner name matching the NSEC5 RR. The format of the 427 field is equivalent to the format used in the NSEC3 RR, described in 428 [RFC5155]. 430 6.2. NSEC5 Flags Field 432 The following one-bit NSEC5 flags are defined: 434 0 1 2 3 4 5 6 7 435 +-+-+-+-+-+-+-+-+ 436 | |W|O| 437 +-+-+-+-+-+-+-+-+ 439 O - Opt-Out flag 441 W - Wildcard flag 443 All the other flags are reserved for future use and MUST be zero. 445 The Opt-Out flag has the same semantics as in NSEC3. The definition 446 and considerations in [RFC5155] are valid, except that NSEC3 is 447 replaced by NSEC5. 449 The Wildcard flag indicates that a wildcard synthesis is possible at 450 the original domain name level (i.e., there is a wildcard node 451 immediately descending from the immediate ancestor of the original 452 domain name). The purpose of the Wildcard flag is to reduce the 453 maximum number of RRs required for an authenticated denial of 454 existence proof, as originally described in [I-D.gieben-nsec4] 455 Section 7.2.1. 457 6.3. NSEC5 RDATA Presentation Format 458 The presentation format of the NSEC5 RDATA is as follows: 460 The Key Tag field is represented as an unsigned decimal integer. 462 The Flags field is represented as an unsigned decimal integer. 464 The Next Length field is not represented. 466 The Next Hashed Owner Name field is represented as a sequence of 467 case-insensitive Base32hex digits without any whitespace and without 468 padding. 470 The Type Bit Maps representation is equivalent to the representation 471 used in NSEC3 RR, described in [RFC5155]. 473 7. The NSEC5PROOF Resource Record 475 The NSEC5PROOF record is not to be included in the zone file. The 476 NSEC5PROOF record contains the NSEC5 proof, proving the position of 477 the owner name in an NSEC5 chain. 479 7.1. NSEC5PROOF RDATA Wire Format 481 The RDATA for NSEC5PROOF is shown below: 483 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 484 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 485 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 486 | Key Tag | Owner Name Hash / 487 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 489 Key Tag field contains the key tag value of the NSEC5KEY RR that 490 validates the NSEC5PROOF RR, in network byte order. 492 Owner Name Hash is a variable-sized sequence of binary octets 493 encoding the NSEC5 proof of the owner name of the RR. 495 7.2. NSEC5PROOF RDATA Presentation Format 497 The presentation format of the NSEC5PROOF RDATA is as follows: 499 The Key Tag field is represented as an unsigned decimal integer. 501 The Owner Name Hash is represented in Base64 encoding. Whitespace is 502 allowed within the Base64 text. 504 8. Types of Authenticated Denial of Existence with NSEC5 506 This section summarizes all possible types of authenticated denial of 507 existence. For each type the following lists are included: 509 1. Facts to prove: the minimum amount of information that an 510 authoritative server must provide to a client to assure the 511 client that the response content is valid. 513 2. Authoritative server proofs: the names for which the NSEC5PROOF 514 RRs are synthesized and added into the response along the NSEC5 515 RRs matching or covering each such name. These records together 516 prove the listed facts. 518 3. Validator checks: the individual checks that a validating server 519 is required to perform on a response. The response content is 520 considered valid only if all of the checks pass. 522 If NSEC5 is said to match a domain name, the owner name of the NSEC5 523 RR has to be equivalent to an NSEC5 hash of that domain name. If an 524 NSEC5 RR is said to cover a domain name, the NSEC5 hash of the domain 525 name must sort in canonical order between that NSEC5 RR's Owner Name 526 and Next Hashed Owner Name. 528 8.1. Name Error Responses 530 Facts to prove: 532 No RRset matching the QNAME exists. 534 No RRset matching the QNAME via wildcard expansion exists. 536 The QNAME does not fall into a delegation. 538 The QNAME does not fall into a DNAME redirection. 540 Authoritative server proofs: 542 NSEC5PROOF for closest encloser and matching NSEC5 RR. 544 NSEC5PROOF for next closer name and covering NSEC5 RR. 546 Validator checks: 548 Closest encloser is in the zone. 550 Closest encloser has the Wildcard flag cleared. 552 Closest encloser does not have NS without SOA in the Type Bit Map. 554 Closest encloser does not have DNAME in the Type Bit Maps. 556 Next closer name is derived correctly. 558 Next closer name is not in the zone. 560 8.2. No Data Responses 562 The processing of a No Data response for DS QTYPE differs if the Opt- 563 Out is in effect. For DS QTYPE queries, the validator has two 564 possible checking paths. The correct path can be simply decided by 565 inspecting if the NSEC5 RR in the response matches the QNAME. 567 Note that the Opt-Out is valid only for DS QTYPE queries. 569 8.2.1. No Data Response, Opt-Out Not In Effect 571 Facts to prove: 573 An RRset matching the QNAME exists. 575 No QTYPE RRset matching the QNAME exists. 577 No CNAME RRset matching the QNAME exists. 579 Authoritative server proofs: 581 NSEC5PROOF for the QNAME and matching NSEC5 RR. 583 Validator checks: 585 The QNAME is in the zone. 587 The QNAME does not have QTYPE in the Type Bit Map. 589 The QNAME does not have CNAME in the Type Bit Map. 591 8.2.2. No Data Response, Opt-Out In Effect 593 Facts to prove: 595 The delegation is not covered by the NSEC5 chain. 597 Authoritative server proofs: 599 NSEC5PROOF for closest provable encloser and matching NSEC5 RR. 601 Validator checks: 603 Closest provable encloser is in zone. 605 Closest provable encloser covers (not matches) the QNAME. 607 Closest provable encloser has the Opt-Out flag set. 609 8.3. Wildcard Responses 611 Facts to prove: 613 No RRset matching the QNAME exists. 615 No wildcard closer to the QNAME exists. 617 Authoritative server proofs: 619 NSEC5PROOF for next closer name and covering NSEC5 RR. 621 Validator checks: 623 Next closer name is derived correctly. 625 Next closer name is not in the zone. 627 8.4. Wildcard No Data Responses 629 Facts to prove: 631 No RRset matching the QNAME exists. 633 No QTYPE RRset exists at the wildcard matching the QNAME. 635 No CNAME RRset exists at the wildcard matching the QNAME. 637 No wildcard closer to the QNAME exists. 639 Authoritative server proofs: 641 NSEC5PROOF for source of synthesis (i.e., wildcard at closest 642 encloser) and matching NSEC5 RR. 644 NSEC5PROOF for next closer name and covering NSEC5 RR. 646 Validator checks: 648 Source of synthesis matches the QNAME. 650 Source of synthesis does not have QTYPE in the Type Bit Map. 652 Source of synthesis does not have CNAME in the Type Bit Map. 654 Next closer name is derived correctly. 656 Next closer name is not in the zone. 658 9. Authoritative Server Considerations 660 9.1. Zone Signing 662 Zones using NSEC5 MUST satisfy the same properties as described in 663 Section 7.1 of [RFC5155], with NSEC3 replaced by NSEC5. In addition, 664 the following conditions MUST be satisfied as well: 666 o If the original owner name has a wildcard label immediately 667 descending from the original owner name, the corresponding NSEC5 668 RR MUST have the Wildcard flag set in the Flags field. Otherwise, 669 the flag MUST be cleared. 671 o The zone apex MUST include an NSEC5KEY RRset containing a NSEC5 672 public key allowing verification of the current NSEC5 chain. 674 The following steps describe one possible method to properly add 675 required NSEC5 related records into a zone. This is not the only 676 such existing method. 678 1. Select an algorithm for NSEC5. Generate the public and private 679 NSEC5 keys. 681 2. Add a NSEC5KEY RR into the zone apex containing the public NSEC5 682 key. 684 3. For each unique original domain name in the zone and each empty 685 non-terminal, add an NSEC5 RR. If Opt-Out is used, owner names 686 of unsigned delegations MAY be excluded. 688 a. The owner name of the NSEC5 RR is the NSEC5 hash of the 689 original owner name encoded in Base32hex without padding, 690 prepended as a single label to the zone name. 692 b. Set the Key Tag field to be the key tag corresponding to the 693 public NSEC5 key. 695 c. Clear the Flags field. If Opt-Out is being used, set the 696 Opt-Out flag. If there is a wildcard label directly 697 descending from the original domain name, set the Wildcard 698 flag. Note that the wildcard can be an empty non-terminal 699 (i.e., the wildcard synthesis does not take effect and 700 therefore the flag is not to be set). 702 d. Set the Next Length field to a value determined by the used 703 NSEC5 algorithm. Leave the Next Hashed Owner Name field 704 blank. 706 e. Set the Type Bit Maps field based on the RRsets present at 707 the original owner name. 709 4. Sort the set of NSEC5 RRs into canonical order. 711 5. For each NSEC5 RR, set the Next Hashed Owner Name field by using 712 the owner name of the next NSEC5 RR in the canonical order. If 713 the updated NSEC5 is the last NSEC5 RR in the chain, the owner 714 name of the first NSEC5 RR in the chain is used instead. 716 The NSEC5KEY and NSEC5 RRs MUST have the same class as the zone SOA 717 RR. Also the NSEC5 RRs SHOULD have the same TTL value as the SOA 718 minimum TTL field. 720 Notice that a use of Opt-Out is not indicated in the zone. This does 721 not affect the ability of a server to prove insecure delegations. 722 The Opt-Out MAY be part of the zone-signing tool configuration. 724 9.1.1. Precomputing Closest Provable Encloser Proofs 726 The worst-case scenario when answering a negative query with NSEC5 727 requires authoritative server to respond with two NSEC5PROOF RRs and 728 two NSEC5 RRs. Per Section 8, one pair of NSEC5PROOF and NSEC5 RRs 729 corresponds to the closest provable encloser, and the other pair 730 corresponds to the next closer name. The NSEC5PROOF corresponding to 731 the next closer name MUST be computed on the fly by the authoritative 732 server when responding to the query. However, the NSEC5PROOF 733 corresponding to the closest provable encloser MAY be precomputed and 734 stored as part of zone signing. 736 Precomputing NSEC5PROOF RRs can halve the number of online 737 cryptographic computations required when responding to a negative 738 query. NSEC5PROOF RRs MAY be precomputed as part of zone signing as 739 follows: For each NSEC5 RR, compute an NSEC5PROOF RR corresponding to 740 the original owner name of the NSEC5 RR. The content of the 741 precomputed NSEC5PROOF record MUST be the same as if the record was 742 computed on the fly when serving the zone. NSEC5PROOF records are 743 not part of the zone and SHOULD be stored separately from the zone 744 file. 746 9.2. Zone Serving 748 This specification modifies DNSSEC-enabled DNS responses generated by 749 authoritative servers. In particular, it replaces use of NSEC or 750 NSEC3 RRs in such responses with NSEC5 RRs and adds NSEC5PROOF RRs. 752 According to the type of a response, an authoritative server MUST 753 include NSEC5 RRs in the response, as defined in Section 8. For each 754 NSEC5 RR in the response, a corresponding RRSIG RRset and an 755 NSEC5PROOF MUST be added as well. The NSEC5PROOF RR has its owner 756 name set to the domain name required according to Section 8. The 757 class and TTL of the NSEC5PROOF RR MUST be the same as the class and 758 TTL value of the corresponding NSEC5 RR. The RDATA payload of the 759 NSEC5PROOF is set according to the description in Section 7.1. 761 Notice that the NSEC5PROOF owner name can be a wildcard (e.g., source 762 of synthesis proof in wildcard No Data responses). The name also 763 always matches the domain name required for the proof while the NSEC5 764 RR may only cover (not match) the name in the proof (e.g., closest 765 encloser in Name Error responses). 767 If NSEC5 is used, an answering server MUST use exactly one NSEC5 768 chain for one signed zone. 770 NSEC5 MUST NOT be used in parallel with NSEC, NSEC3, or any other 771 authenticated denial of existence mechanism that allows for 772 enumeration of zone contents, as this would defeat a principal 773 security goal of NSEC5. 775 Similarly to NSEC3, the owner names of NSEC5 RRs are not represented 776 in the NSEC5 chain and therefore NSEC5 records deny their own 777 existence. The desired behavior caused by this paradox is the same 778 as described in Section 7.2.8 of [RFC5155]. 780 9.3. NSEC5KEY Rollover Mechanism 782 Replacement of the NSEC5 key implies generating a new NSEC5 chain. 783 The NSEC5KEY rollover mechanism is similar to "Pre-Publish Zone 784 Signing Key Rollover" as specified in [RFC6781]. The NSEC5KEY 785 rollover MUST be performed as a sequence of the following steps: 787 1. A new public NSEC5 key is added into the NSEC5KEY RRset in the 788 zone apex. 790 2. The old NSEC5 chain is replaced by a new NSEC5 chain constructed 791 using the new key. This replacement MUST happen as a single 792 atomic operation; the server MUST NOT be responding with RRs from 793 both the new and old chain at the same time. 795 3. The old public key is removed from the NSEC5KEY RRset in the zone 796 apex. 798 The minimum delay between steps 1 and 2 MUST be the time it takes for 799 the data to propagate to the authoritative servers, plus the TTL 800 value of the old NSEC5KEY RRset. 802 The minimum delay between steps 2 and 3 MUST be the time it takes for 803 the data to propagate to the authoritative servers, plus the maximum 804 zone TTL value of any of the data in the previous version of the 805 zone. 807 9.4. Secondary Servers 809 This document does not define mechanism to distribute private NSEC5 810 keys. See Section 15.2 for security considerations for private NSEC5 811 keys. 813 9.5. Zones Using Unknown NSEC5 Algorithms 815 Zones that are signed with unknown NSEC5 algorithm or an unavailable 816 private NSEC5 key cannot be effectively served. Such zones SHOULD be 817 rejected when loading and servers SHOULD respond with RCODE=2 (Server 818 failure) when handling queries that would fall under such zones. 820 9.6. Dynamic Updates 822 A zone signed using NSEC5 MAY accept dynamic updates [RFC2136]. The 823 changes to the zone MUST be performed in a way that ensures that the 824 zone satisfies the properties specified in Section 9.1 at any time. 825 The process described in [RFC5155] Section 7.5 describes how to 826 handle the issues surrounding the handling of empty non-terminals as 827 well as Opt-Out. 829 It is RECOMMENDED that the server rejects all updates containing 830 changes to the NSEC5 chain and its related RRSIG RRs, and performs 831 itself any required alternations of the NSEC5 chain induced by the 832 update. Alternatively, the server MUST verify that all the 833 properties are satisfied prior to performing the update atomically. 835 10. Resolver Considerations 837 The same considerations as described in Section 9 of [RFC5155] for 838 NSEC3 apply to NSEC5. In addition, as NSEC5 RRs can be validated 839 only with appropriate NSEC5PROOF RRs, the NSEC5PROOF RRs MUST be all 840 together cached and included in responses with NSEC5 RRs. 842 11. Validator Considerations 844 11.1. Validating Responses 846 The validator MUST ignore NSEC5 RRs with Flags field values other 847 than the ones defined in Section 6.2. 849 The validator MAY treat responses as bogus if the response contains 850 NSEC5 RRs that refer to a different NSEC5KEY. 852 According to a type of a response, the validator MUST verify all 853 conditions defined in Section 8. Prior to making decision based on 854 the content of NSEC5 RRs in a response, the NSEC5 RRs MUST be 855 validated. 857 To validate a denial of existence, public NSEC5 keys for the zone are 858 required in addition to DNSSEC public keys. Similarly to DNSKEY RRs, 859 the NSEC5KEY RRs are present at the zone apex. 861 The NSEC5 RR is validated as follows: 863 1. Select a correct public NSEC5 key to validate the NSEC5 proof. 864 The Key Tag value of the NSEC5PROOF RR must match with the key 865 tag value computed from the NSEC5KEY RDATA. 867 2. Validate the NSEC5 proof present in the NSEC5PROOF Owner Name 868 Hash field using the public NSEC5 key. If there are multiple 869 NSEC5KEY RRs matching the key tag, at least one of the keys must 870 validate the NSEC5 proof. 872 3. Compute the NSEC5 hash value from the NSEC5 proof and check if 873 the response contains NSEC5 RR matching or covering the computed 874 NSEC5 hash. The TTL values of the NSEC5 and NSEC5PROOF RRs must 875 be the same. 877 4. Validate the signature on the NSEC5 RR. 879 If the NSEC5 RR fails to validate, it MUST be ignored. If some of 880 the conditions required for an NSEC5 proof are not satisfied, the 881 response MUST be treated as bogus. 883 Notice that determining the closest encloser and next closer name in 884 NSEC5 is easier than in NSEC3. NSEC5 and NSEC5PROOF RRs are always 885 present in pairs in responses and the original owner name of the 886 NSEC5 RR matches the owner name of the NSEC5PROOF RR. 888 11.2. Validating Referrals to Unsigned Subzones 889 The same considerations as defined in Section 8.9 of [RFC5155] for 890 NSEC3 apply to NSEC5. 892 11.3. Responses With Unknown NSEC5 Algorithms 894 A validator MUST ignore NSEC5KEY RRs with unknown NSEC5 algorithms. 895 The practical result of this is that zones signed with unknown 896 algorithms will be considered bogus. 898 12. Special Considerations 900 12.1. Transition Mechanism 902 [TODO: The following information will be covered.] 904 o Transition to NSEC5 from NSEC/NSEC3 906 o Transition from NSEC5 to NSEC/NSEC3 908 o Transition to new NSEC5 algorithms 910 12.2. Private NSEC5 keys 912 This document does not define a format to store private NSEC5 keys. 913 Use of a standardized and adopted format is RECOMMENDED. 915 The private NSEC5 key MAY be shared between multiple zones, however a 916 separate key is RECOMMENDED for each zone. 918 12.3. Domain Name Length Restrictions 920 NSEC5 creates additional restrictions on domain name lengths. In 921 particular, zones with names that, when converted into hashed owner 922 names, exceed the 255 octet length limit imposed by [RFC1035] cannot 923 use this specification. 925 The actual maximum length of a domain name depends on the length of 926 the zone name and the NSEC5 algorithm used. 928 All NSEC5 algorithms defined in this document use 256-bit NSEC5 hash 929 values. Such a value can be encoded in 52 characters in Base32hex 930 without padding. When constructing the NSEC5 RR owner name, the 931 encoded hash is prepended to the name of the zone as a single label 932 which includes the length field of a single octet. The maximum 933 length of the zone name in wire format using the 256-bit hash is 934 therefore 202 octets (255 - 53). 936 13. Implementation Status 938 NSEC5 has been implemented for the Knot DNS authoritative server 939 (version 1.6.4) and the Unbound recursive server (version 1.5.9). 940 The implementation did not introduce additional library dependencies; 941 all cryptographic primitives are already present in OpenSSL v1.0.2j, 942 which is used by both implementations. The implementation supports 943 the full spectrum of negative responses, (i.e., NXDOMAIN, NODATA, 944 Wildcard, Wildcard NODATA, and unsigned delegation). The 945 implementation supports the EC-P256-SHA256 algorithm. The code is 946 deliberately modular, so that the EC-ED25519-SHA256 algorithm could 947 be implemented by using the Ed25519 elliptic curve [RFC8080] as a 948 drop-in replacement for the P256 elliptic curve. The authoritative 949 server implements the optimization from Section 9.1.1 to precompute 950 the NSEC5PROOF RRs matching each NSEC5 record. 952 14. Performance Considerations 954 The performance of NSEC5 has been evaluated in [nsec5ecc]. 956 15. Security Considerations 958 15.1. Zone Enumeration Attacks 960 NSEC5 is robust to zone enumeration via offline dictionary attacks by 961 any attacker that does not know the private NSEC5 key. Without the 962 private NSEC5 key, that attacker cannot compute the NSEC5 proof that 963 corresponds to a given domain name. The only way it can learn the 964 NSEC5 proof value for a domain name is by querying the authoritative 965 server for that name. Without the NSEC5 proof value, the attacker 966 cannot learn the NSEC5 hash value. Thus, even an attacker that 967 collects the entire chain of NSEC5 RR for a zone cannot use offline 968 attacks to "reverse" that NSEC5 hash values in these NSEC5 RR and 969 thus learn which names are present in the zone. A formal 970 cryptographic proof of this property is in [nsec5] and [nsec5ecc]. 972 15.2. Compromise of the Private NSEC5 Key 974 NSEC5 requires authoritative servers to hold the private NSEC5 key, 975 but not the private zone-signing keys or the private key-signing keys 976 for the zone. 978 The private NSEC5 key cannot be used to modify zone contents, because 979 zone contents are signed using the private zone-signing key. As 980 such, a compromise of the private NSEC5 key does not compromise the 981 integrity of the zone. An adversary that learns the private NSEC5 982 key can, however, perform offline zone-enumeration attacks. For this 983 reason, the private NSEC5 key need only be as secure as the DNSSEC 984 records whose privacy (against zone enumeration) is being protected 985 by NSEC5. A formal cryptographic proof of this property is in 986 [nsec5] and [nsec5ecc]. 988 To preserve this property of NSEC5, the private NSEC5 key MUST be 989 different from the private zone-signing keys or key-signing keys for 990 the zone. 992 15.3. Key Length Considerations 994 The NSEC5 key must be long enough to withstand attacks for as long as 995 the privacy of the zone contents is important. Even if the NSEC5 key 996 is rolled frequently, its length cannot be too short, because zone 997 privacy may be important for a period of time longer than the 998 lifetime of the key. For example, an attacker might collect the 999 entire chain of NSEC5 RR for the zone over one short period, and 1000 then, later (even after the NSEC5 key expires) perform an offline 1001 dictionary attack that attempt to "reverse" the NSEC5 hash values 1002 present in the NSEC5 RRs. This is in contrast to zone-signing and 1003 key-signing keys used in DNSSEC; these keys, which ensure the 1004 authenticity and integrity of the zone contents, need to remain 1005 secure only during their lifetime. 1007 15.4. NSEC5 Hash Collisions 1009 If the NSEC5 hash of a QNAME collides with the NSEC5 hash of the 1010 owner name of an NSEC5 RR, it will be impossible to prove the non- 1011 existence of the colliding QNAME. However, the NSEC5 VRFs ensure 1012 that obtaining such a collision is as difficult as obtaining a 1013 collision in the SHA-256 hash function (requiring approximately 2^128 1014 effort). Note that DNSSEC already relies on the assumption that a 1015 cryptographic hash function is collision-resistant, since these hash 1016 functions are used for generating and validating signatures and DS 1017 RRs. See also the discussion on key lengths in [nsec5]. 1019 16. IANA Considerations 1021 This document updates the IANA registry "Domain Name System (DNS) 1022 Parameters" in subregistry "Resource Record (RR) TYPEs", by defining 1023 the following new RR types: 1025 NSEC5KEY value TBD. 1027 NSEC5 value TBD. 1029 NSEC5PROOF value TBD. 1031 This document creates a new IANA registry for NSEC5 algorithms. This 1032 registry is named "DNSSEC NSEC5 Algorithms". The initial content of 1033 the registry is: 1035 0 is Reserved. 1037 1 is EC-P256-SHA256. 1039 2 is EC-ED25519-SHA256. 1041 3-255 is Available for assignment. 1043 This document updates the IANA registry "DNS Security Algorithm 1044 Numbers" by defining following aliases: 1046 TBD is NSEC5-ECDSAP256SHA256 alias for ECDSAP256SHA256 (13). 1048 TBD is NSEC5-ED25519, alias for ED25519 (15). 1050 17. Contributors 1052 This document would not be possible without help of Moni Naor 1053 (Weizmann Institute), Sachin Vasant (Cisco Systems), Leonid Reyzin 1054 (Boston University), and Asaf Ziv (Weizmann Institute) who 1055 contributed to the design of NSEC5. Ondrej Sury (CZ.NIC Labs), and 1056 Duane Wessels (Verisign Labs) provided advice on the implementation 1057 of NSEC5, and assisted with evaluating its performance. 1059 18. References 1061 18.1. Normative References 1063 [RFC1034] Mockapetris, P., "Domain names - concepts and facilities", 1064 STD 13, RFC 1034, DOI 10.17487/RFC1034, November 1987, 1065 . 1067 [RFC1035] Mockapetris, P., "Domain names - implementation and 1068 specification", STD 13, RFC 1035, November 1987. 1070 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1071 Requirement Levels", BCP 14, RFC 2119, March 1997. 1073 [RFC2136] Vixie, P., Ed., Thomson, S., Rekhter, Y., and J. Bound, 1074 "Dynamic Updates in the Domain Name System (DNS UPDATE)", 1075 RFC 2136, DOI 10.17487/RFC2136, April 1997, 1076 . 1078 [RFC2181] Elz, R. and R. Bush, "Clarifications to the DNS 1079 Specification", RFC 2181, DOI 10.17487/RFC2181, July 1997, 1080 . 1082 [RFC2308] Andrews, M., "Negative Caching of DNS Queries (DNS 1083 NCACHE)", RFC 2308, DOI 10.17487/RFC2308, March 1998, 1084 . 1086 [RFC4033] Arends, R., Austein, R., Larson, M., Massey, D., and S. 1087 Rose, "DNS Security Introduction and Requirements", RFC 1088 4033, March 2005. 1090 [RFC4034] Arends, R., Austein, R., Larson, M., Massey, D., and S. 1091 Rose, "Resource Records for the DNS Security Extensions", 1092 RFC 4034, March 2005. 1094 [RFC4035] Arends, R., Austein, R., Larson, M., Massey, D., and S. 1095 Rose, "Protocol Modifications for the DNS Security 1096 Extensions", RFC 4035, March 2005. 1098 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data 1099 Encodings", RFC 4648, DOI 10.17487/RFC4648, October 2006, 1100 . 1102 [RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman 1103 Groups for Use with IETF Standards", RFC 5114, DOI 1104 10.17487/RFC5114, January 2008, 1105 . 1107 [RFC5155] Laurie, B., Sisson, G., Arends, R., and D. Blacka, "DNS 1108 Security (DNSSEC) Hashed Authenticated Denial of 1109 Existence", RFC 5155, March 2008. 1111 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 1112 (SHA and SHA-based HMAC and HKDF)", RFC 6234, DOI 10.17487 1113 /RFC6234, May 2011, 1114 . 1116 [RFC6605] Hoffman, P. and W. Wijngaards, "Elliptic Curve Digital 1117 Signature Algorithm (DSA) for DNSSEC", RFC 6605, April 1118 2012. 1120 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1121 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1122 2016, . 1124 [RFC8080] Sury, O. and R. Edmonds, "Edwards-Curve Digital Security 1125 Algorithm (EdDSA) for DNSSEC", RFC 8080, DOI 10.17487/ 1126 RFC8080, February 2017, 1127 . 1129 [FIPS-186-3] 1130 National Institute for Standards and Technology, "Digital 1131 Signature Standard (DSS)", FIPS PUB 186-3, June 2009. 1133 [SECG1] Standards for Efficient Cryptography Group (SECG), "SEC 1: 1134 Elliptic Curve Cryptography", Version 2.0, May 2009, 1135 . 1137 18.2. Informative References 1139 [nsec5] Goldberg, S., Naor, M., Papadopoulos, D., Reyzin, L., 1140 Vasant, S., and A. Ziv, "NSEC5: Provably Preventing DNSSEC 1141 Zone Enumeration", in NDSS'15, July 2014, . 1144 [nsec5ecc] 1145 Papadopoulos, D., Wessels, D., Huque, S., Vcelak, J., 1146 Naor, M., Reyzin, L., and S. Goldberg, "Can NSEC5 be 1147 Practical for DNSSEC Deployments?", in ePrint Cryptology 1148 Archive 2017/099, February 2017, . 1151 [nsec3gpu] 1152 Wander, M., Schwittmann, L., Boelmann, C., and T. Weis, 1153 "GPU-Based NSEC3 Hash Breaking", in IEEE Symp. Network 1154 Computing and Applications (NCA), 2014. 1156 [nsec3walker] 1157 Bernstein, D., "Nsec3 walker", 2011, 1158 . 1160 [nmap-nsec-enum] 1161 Bond, J., "nmap: dns-nsec-enum", 2011, . 1164 [nmap-nsec3-enum] 1165 Nikolic, A. and J. Bond, "nmap: dns-nsec3-enum", 2011, 1166 . 1168 [nsec3map] 1169 anonion0, ., "nsec3map with John the Ripper plugin", 2015, 1170 . 1172 [ldns-walk] 1173 NLNetLabs, ., "ldns", 2015, 1174 . 1176 [MRV99] Michali, S., Rabin, M., and S. Vadhan, "Verifiable Random 1177 Functions", in FOCS, 1999. 1179 [RFC6781] Kolkman, O., Mekking, W., and R. Gieben, "DNSSEC 1180 Operational Practices, Version 2", RFC 6781, DOI 10.17487/ 1181 RFC6781, December 2012, 1182 . 1184 [RFC7129] Gieben, R. and W. Mekking, "Authenticated Denial of 1185 Existence in the DNS", RFC 7129, DOI 10.17487/RFC7129, 1186 February 2014, . 1188 [RFC7719] Hoffman, P., Sullivan, A., and K. Fujiwara, "DNS 1189 Terminology", RFC 7719, DOI 10.17487/RFC7719, December 1190 2015, . 1192 [I-D.gieben-nsec4] 1193 Gieben, R. and M. Mekking, "DNS Security (DNSSEC) 1194 Authenticated Denial of Existence", draft-gieben-nsec4-01 1195 (work in progress), July 2012. 1197 Appendix A. Elliptic Curve VRF 1199 The Elliptic Curve Verifiable Random Function (EC-VRF) operates in a 1200 cyclic group G of prime order with generator g. The cyclic group G 1201 MAY be over the NIST-P256 elliptic curve, with curve parameters as 1202 specified in [FIPS-186-3] (Section D.1.2.3) and [RFC5114] 1203 (Section 2.6). The group G MAY alternatively be over the Ed25519 1204 elliptic curve with parameters defined in [RFC7748] (Section 4.1). 1205 The security of this VRF follows from the decisional Diffie-Hellman 1206 (DDH) assumption in the cyclic group G in the random oracle model. 1207 Formal security proofs for this VRF are in [nsec5ecc]. 1209 Fixed options: 1211 G - elliptic curve (EC) group 1213 Used parameters: 1215 g^x - EC public key 1217 x - EC private key 1219 q - prime order of group G 1220 g - generator of group G 1222 Used primitives: 1224 "" - empty octet string 1226 || - octet string concatenation 1228 p^k - EC point multiplication 1230 p1*p2 - EC point addition 1232 SHA256 - hash function SHA-256 as specified in [RFC6234] 1234 ECP2OS - EC point to octet string conversion with point 1235 compression as specified in Section 2.3.3 of [SECG1] 1237 OS2ECP - octet string to EC point conversion with point 1238 compression as specified in Section 2.3.4 of [SECG1] 1240 A.1. EC-VRF Auxiliary Functions 1242 A.1.1. EC-VRF Hash To Curve 1244 ECVRF_hash_to_curve(m) 1246 Input: 1248 m - value to be hashed, an octet string 1250 Output: 1252 h - hashed value, EC point 1254 Steps: 1256 1. c = 0 1258 2. C = I2OSP(c, 4) 1260 3. xc = SHA256(m || C) 1262 4. p = 0x02 || xc 1264 5. If p is not a valid octet string representing encoded compressed 1265 point in G: 1267 a. c = c + 1 1268 b. Go to step 2. 1270 6. h = OS2ECP(p) 1272 7. Output h 1274 A.1.2. EC-VRF Hash Points 1276 ECVRF_hash_points(p_1, p_2, ..., p_n) 1278 Input: 1280 p_x - EC point in G 1282 Output: 1284 h - hash value, integer between 0 and 2^128-1 1286 Steps: 1288 1. P = "" 1290 2. for p in [p_1, p_2, ... p_n]: 1291 P = P || ECP2OS(p) 1293 3. h' = SHA256(P) 1295 4. h = OS2IP(first 16 octets of h') 1297 5. Output h 1299 A.1.3. EC-VRF Decode Proof 1301 ECVRF_decode_proof(pi) 1303 Input: 1305 pi - VRF proof, octet string (81 octets) 1307 Output: 1309 gamma - EC point 1311 c - integer between 0 and 2^128-1 1313 s - integer between 0 and 2^256-1 1315 Steps: 1317 1. let gamma', c', s' be pi split after 33-rd and 49-th octet 1319 2. gamma = OS2ECP(gamma') 1321 3. c = OS2IP(c') 1323 4. s = OS2IP(s') 1325 5. Output gamma, c, and s 1327 A.2. EC-VRF Proving 1329 ECVRF_PROVE(g^x, x, alpha) 1331 Input: 1333 g^x - EC public key 1335 x - EC private key 1337 alpha - message to be signed, octet string 1339 Output: 1341 pi - VRF proof, octet string (81 octets) 1343 beta - VRF hash, octet string (32 octets) 1345 Steps: 1347 1. h = ECVRF_hash_to_curve(alpha) 1349 2. gamma = h^x 1351 3. choose a nonce k from [0, q-1] 1353 4. c = ECVRF_hash_points(g, h, g^x, h^x, g^k, h^k) 1355 5. s = k - c*q mod q 1357 6. pi = ECP2OS(gamma) || I2OSP(c, 16) || I2OSP(s, 32) 1359 7. beta = h2(gamma) 1361 8. Output pi and beta 1363 A.3. EC-VRF Proof To Hash 1364 ECVRF_PROOF2HASH(gamma) 1366 Input: 1368 gamma - VRF proof, EC point in G with coordinates (x, y) 1370 Output: 1372 beta - VRF hash, octet string (32 octets) 1374 Steps: 1376 1. beta = I2OSP(x, 32) 1378 2. Output beta 1380 Note: Because of the format of the compressed form of an elliptic 1381 curve, the hash can be retrieved from an encoded gamma simply by 1382 omitting the first octet of the gamma. 1384 A.4. EC-VRF Verifying 1386 ECVRF_VERIFY(g^x, pi, alpha) 1388 Input: 1390 g^x - EC public key 1392 pi - VRF proof, octet string 1394 alpha - message to verify, octet string 1396 Output: 1398 "valid signature" or "invalid signature" 1400 beta - VRF hash, octet string (32 octets) 1402 Steps: 1404 1. gamma, c, s = ECVRF_decode_proof(pi) 1406 2. u = (g^x)^c * g^s 1408 3. h = ECVRF_hash_to_curve(alpha) 1410 4. v = gamma^c * h^s 1411 5. c' = ECVRF_hash_points(g, h, g^x, gamma, u, v) 1413 6. beta = ECVRF_PROOF2HASH(gamma) 1415 7. If c and c' are the same, output "valid signature"; else output 1416 "invalid signature". Output beta. 1418 [[TODO: check validity of gamma before hashing]] 1420 Appendix B. Change Log 1422 Note to RFC Editor: if this document does not obsolete an existing 1423 RFC, please remove this appendix before publication as an RFC. 1425 pre 00 - initial version of the document submitted to mailing list 1426 only 1428 00 - fix NSEC5KEY rollover mechanism, clarify NSEC5PROOF RDATA, 1429 clarify inputs and outputs for NSEC5 proof and NSEC5 hash 1430 computation. 1432 01 - Add Performance Considerations section. 1434 02 - Add elliptic curve based VRF. Add measurement of response 1435 sizes based on empirical data. 1437 03 - Mention precomputed NSEC5PROOF Values in Performance 1438 Considerations section. 1440 04 - Edit Rationale, How NSEC5 Works, and Security Consideration 1441 sections for clarity. Edit Zone Signing section, adding 1442 precomputation of NSEC5PROOFs. Remove RSA-based NSEC5 1443 specification. Rewrite Performance Considerations and 1444 Implementation Status sections. 1446 Authors' Addresses 1448 Jan Vcelak 1449 CZ.NIC 1450 Milesovska 1136/5 1451 Praha 130 00 1452 CZ 1454 EMail: jan.vcelak@nic.cz 1455 Sharon Goldberg 1456 Boston University 1457 111 Cummington St, MCS135 1458 Boston, MA 02215 1459 USA 1461 EMail: goldbe@cs.bu.edu 1463 Dimitrios Papadopoulos 1464 University of Maryland 1465 8223 Paint Branch Dr 1466 College Park, MD 20740 1467 USA 1469 EMail: dipapado@umd.edu 1471 Shumon Huque 1472 Salesforce 1473 2550 Wasser Terrace 1474 Herndon, VA 20171 1475 USA 1477 EMail: shuque@gmail.com 1479 David C Lawrence 1480 Akamai Technologies 1481 150 Broadway 1482 Boston, MA 02142-1054 1483 USA 1485 EMail: tale@akamai.com