idnits 2.17.1 draft-gieben-auth-denial-of-existence-dns-01.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: ---------------------------------------------------------------------------- == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 2) being 60 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- -- The document has examples using IPv4 documentation addresses according to RFC6890, but does not use any IPv6 documentation addresses. Maybe there should be IPv6 examples, too? Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 23, 2012) is 4171 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 2535 (Obsoleted by RFC 4033, RFC 4034, RFC 4035) -- Obsolete informational reference (is this intentional?): RFC 3655 (Obsoleted by RFC 4033, RFC 4034, RFC 4035) -- Obsolete informational reference (is this intentional?): RFC 3755 (Obsoleted by RFC 4033, RFC 4034, RFC 4035) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group R. Gieben 3 Internet-Draft SIDN Labs 4 Intended status: Informational W. Mekking 5 Expires: May 25, 2013 NLnet Labs 6 November 23, 2012 8 Authenticated Denial of Existence in the DNS 9 draft-gieben-auth-denial-of-existence-dns-01 11 Abstract 13 Authenticated denial of existence allows a resolver to validate that 14 a certain domain name does not exist. It is also used to signal that 15 a domain name exists, but does not have the specific RR type you were 16 asking for. When returning a negative DNSSEC response, a name server 17 usually includes up to two NSEC records. With NSEC3 this amount is 18 three. This document provides extra documentation and context on the 19 mechanisms behind NSEC and NSEC3 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on May 25, 2013. 38 Copyright Notice 40 Copyright (c) 2012 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 53 2. Denial of Existence . . . . . . . . . . . . . . . . . . . . . 3 54 2.1. NXDOMAIN Responses . . . . . . . . . . . . . . . . . . . . 4 55 2.2. NODATA Responses . . . . . . . . . . . . . . . . . . . . . 4 56 3. Secure Denial of Existence . . . . . . . . . . . . . . . . . . 5 57 3.1. NXT . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 58 3.2. NSEC . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 59 3.3. NODATA Responses . . . . . . . . . . . . . . . . . . . . . 8 60 3.4. Drawbacks of NSEC . . . . . . . . . . . . . . . . . . . . 9 61 3.5. NO, NSEC2 and DNSNR . . . . . . . . . . . . . . . . . . . 9 62 3.6. NSEC3 . . . . . . . . . . . . . . . . . . . . . . . . . . 10 63 3.7. Loading an NSEC3 Zone . . . . . . . . . . . . . . . . . . 11 64 3.8. Wildcards in the DNS . . . . . . . . . . . . . . . . . . . 12 65 3.9. CNAME Records . . . . . . . . . . . . . . . . . . . . . . 14 66 3.10. The Closest Encloser NSEC3 Record . . . . . . . . . . . . 15 67 3.11. Three To Tango . . . . . . . . . . . . . . . . . . . . . . 19 68 4. List of Hashed Owner Names . . . . . . . . . . . . . . . . . . 20 69 5. Security Considerations . . . . . . . . . . . . . . . . . . . 20 70 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 71 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 72 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 73 8.1. Normative References . . . . . . . . . . . . . . . . . . . 21 74 8.2. Informative References . . . . . . . . . . . . . . . . . . 21 75 Appendix A. Changelog . . . . . . . . . . . . . . . . . . . . . . 22 76 A.1. -00 . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 77 A.2. -01 . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22 80 1. Introduction 82 DNSSEC can be somewhat of a complicated matter, and there are certain 83 areas of the specification that are more difficult to comprehend than 84 others. One such area is "authenticated denial of existence". 86 Authenticated denial of existence allows a DNSSEC enabled resolver to 87 validate that a certain domain name does not exist. It is also used 88 to signal that a domain name exists, but does not have the specific 89 RR type you were asking for. 91 The first is referred to as an NXDOMAIN [RFC2308] (non-existent 92 domain) and the latter a NODATA [RFC2308] response. Both are also 93 known as negative responses. 95 In this document, we will explain how authenticated denial of 96 existence works. We begin by explaining the current technique in the 97 DNS and work our way up to DNSSEC. We explain the first steps taken 98 in DNSSEC and describe how NXT, NSEC and NSEC3 work. The NO, NSEC2 99 and DNSNR records also briefly make their appearance, as they have 100 paved the way for NSEC3. 102 To complete the picture, we also need to explain DNS wildcards as 103 these complicate matters, especially combined with CNAME records. 105 Note: In this document, domain names in zone file examples will have 106 a trailing dot, in the running text they will not. This text is 107 written for people who have a fair understanding of DNSSEC. NSEC3 108 opt-out and secure delegations are out of scope for this document. 110 The following RFCs are not required reading, but they help in 111 understanding the problem space. 113 o RFC 5155 [RFC5155] - Hashed Authenticated Denial of Existence; 115 o RFC 4592 [RFC4592] - The Role of Wildcards in the DNS. 117 And these provide some general DNSSEC information. 119 o RFC 4033, RFC 4034, RFC 4035 [RFC4033], [RFC4034], [RFC4035] - 120 DNSSEC Specification; 122 o RFC 4956 [RFC4956] - DNS Security (DNSSEC) Opt-In. This RFC has 123 experimental status, but is a good read. 125 These three drafts give some background information on the NSEC3 126 development. 128 o The NO record [I-D.ietf-dnsext-not-existing-rr]; 130 o The NSEC2 record [I-D.laurie-dnsext-nsec2v2]; 132 o The DNSNR record [I-D.arends-dnsnr]. 134 2. Denial of Existence 136 We start with the basics and take a look at NXDOMAIN handling in the 137 DNS. To make it more visible we are going to use a small DNS zone, 138 with 3 names ("example.org", "a.example.org" and "d.example.org") and 139 3 types (SOA, A and TXT). For brevity, the class is not shown 140 (defaults to IN), the NS records are left out and the SOA record is 141 shortened, resulting in the following zone file: 143 example.org. SOA ( ... ) 144 a.example.org. A 192.0.2.1 145 TXT "a record" 146 d.example.org. A 192.0.2.1 147 TXT "d record" 149 The unsigned "example.org" zone. 151 Figure 1 153 2.1. NXDOMAIN Responses 155 If a resolver asks for the TXT type belonging to "a.example.org" to 156 the name server serving this zone, it sends the following question: 157 "a.example.org TXT" 159 The name server looks in its zone data and generates an answer. In 160 this case a positive one: "Yes it exists and this is the data", 161 resulting in this reply: 163 ;; status: NOERROR, id: 28203 165 ;; ANSWER SECTION: 166 a.example.org. TXT "a record" 168 ;; AUTHORITY SECTION: 169 example.org. NS a.example.org. 171 The "status: NOERROR" signals that everything is OK, "id" is an 172 integer used to match questions and answers. In the ANSWER section, 173 we find our answer. The AUTHORITY section holds the names of the 174 name servers that have information concerning the "example.org" zone. 175 Note that including this information is optional. 177 If a resolver asks for "b.example.org TXT" it gets an answer that 178 this name does not exist: 180 ;; status: NXDOMAIN, id: 7042 182 ;; AUTHORITY SECTION: 183 example.org. SOA ( ... ) 185 In this case, we do not get an ANSWER section and the status is set 186 to NXDOMAIN. From this the resolver concludes that "b.example.org" 187 does not exist. The AUTHORITY section holds the SOA record of 188 "example.org" that the resolver can use to cache the negative 189 response. 191 2.2. NODATA Responses 193 It is important to realize that NXDOMAIN is not the only type of 194 does-not-exist. A name may exist, but the type you are asking for 195 may not. This occurrence of non-existence is called a NODATA 196 [RFC2308] response. Let us ask our name server for "a.example.org 197 AAAA", and look at the answer: 199 ;; status: NOERROR, id: 7944 201 ;; AUTHORITY SECTION: 202 example.org. SOA ( ... ) 203 The status is NOERROR meaning that the "a.example.org" name exists, 204 but the reply does not contain an ANSWER section. This 205 differentiates a NODATA response from an NXDOMAIN response, the rest 206 of the packet is very similar. The resolver has to put these pieces 207 of information together and conclude that "a.example.org" exists, but 208 it does not have an "AAAA" record. 210 3. Secure Denial of Existence 212 The above has to be translated to the security aware world of DNSSEC. 213 But there are a few requirements DNSSEC brings to the table: 215 1. There is no online signing defined in DNSSEC. Although a name 216 server is free to compute the answer and signature(s) on-the-fly, 217 the protocol is written with a "first sign, then load" attitude 218 in mind. It is rather asymmetrical, but a lot of the design in 219 DNSSEC stems from fact that you need to accommodate authenticated 220 denial of existence. If the DNS did not have NXDOMAIN, DNSSEC 221 would be a lot simpler, but a lot less useful! 223 2. The DNS packet header is not signed. This means that a "status: 224 NXDOMAIN" can not be trusted. In fact the entire header may be 225 forged, including the AD bit (AD stands for Authentic Data, see 226 RFC 3655 [RFC3655]), which may give some food for thought; 228 3. DNS wildcards and CNAME records complicate matters significantly. 229 More about this in later sections (Section 3.8 and Section 3.9). 231 The first requirement implies that all denial of existence answers 232 need to be pre-computed, but it is impossible to precompute (all 233 conceivable) non-existence answers. A generic denial record which 234 can be used in all denial of existence proofs is not an option: such 235 a record is susceptible to replay attacks. When you are querying a 236 name server for a record that actually exists, a man-in-the-middle 237 may replay that generic denial record and it would be impossible to 238 tell whether the response was genuine or spoofed. 240 This has been solved by introducing a record that defines an interval 241 between two existing names. Or to put it another way: it defines the 242 holes (non-existing names) in the zone. This record can be signed 243 beforehand and given to the resolver. 245 Given all these troubles, why didn't the designers of DNSSEC go 246 for the (easy) route and allowed for online signing? Well, at 247 that time (pre 2000), online signing was not feasible with the 248 current hardware. Keep in mind that the larger servers get 249 between 2000 and 6000 queries per second (qps), with peaks up to 250 20,000 qps or more. Scaling signature generation to these kind of 251 levels is always a challenge. Another issue was (and is) key 252 management, for online signing to work you need access to the 253 private key(s). This is considered a security risk. 255 The road to the current solution (NSEC/NSEC3) was long. It started 256 with the NXT (next) record. The NO (not existing) record was 257 introduced, but never made it to RFC. Later on, NXT was superseded 258 by the NSEC (next secure) record. From there it went through NSEC2/ 259 DNSNR to finally reach NSEC3 (next secure, version 3) in RFC 5155. 261 3.1. NXT 263 The first attempt to specify authenticated denial of existence was 264 NXT (RFC 2535 [RFC2535]). Section 5.1 of that RFC introduces the 265 record: 267 "The NXT resource record is used to securely indicate that RRs 268 with an owner name in a certain name interval do not exist in a 269 zone and to indicate what RR types are present for an existing 270 name." 272 By specifying what you do have, you implicitly tell what you don't 273 have. NXT is superseded by NSEC. In the next section we explain how 274 NSEC (and thus NXT) works. 276 3.2. NSEC 278 In RFC 3755 [RFC3755] all the DNSSEC types were given new names, SIG 279 was renamed RRSIG, KEY became DNSKEY and NXT was renamed to NSEC and 280 a few minor issues were fixed in the process. 282 Just as NXT, NSEC is used to describe an interval between names: it 283 indirectly tells a resolver which names do not exist in a zone. 285 For this to work, we need our "example.org" zone to be sorted in 286 canonical order ([RFC4034], Section 6.1), and then create the NSECs. 287 We add three NSEC records, one for each name, and each one "covers" a 288 certain interval. The last NSEC record points back to the first as 289 required by the RFC, as depicted in Figure 2. 291 1. The first NSEC covers the interval between "example.org" and 292 "a.example.org"; 294 2. The second NSEC covers "a.example.org" to "d.example.org"; 296 3. The third NSEC points back to "example.org", and covers 297 "d.example.org" to "example.org" (i.e. the end of the zone). 299 As we have defined the intervals and put those in resource records, 300 we now have something that can be signed. 302 example.org 303 ** 304 +-- ** <--+ 305 (1) / . . \ (3) 306 / . . \ 307 | . . | 308 v . . | 309 ** (2) ** 310 a.example.org ** ---------> ** d.example.org 312 The NSEC records of "example.org". The arrows represent NSEC 313 records, starting from the apex. 315 Figure 2 317 This signed zone is loaded into the name server. It looks like this: 319 example.org. SOA ( ... ) 320 DNSKEY ( ... ) 321 NSEC a.example.org. SOA NSEC DNSKEY RRSIG 322 RRSIG(SOA) ( ... ) 323 RRSIG(DNSKEY) ( ... ) 324 RRSIG(NSEC) ( ... ) 325 a.example.org. A 192.0.2.1 326 TXT "a record" 327 NSEC d.example.org. A TXT NSEC RRSIG 328 RRSIG(A) ( ... ) 329 RRSIG(TXT) ( ... ) 330 RRSIG(NSEC) ( ... ) 331 d.example.org. A 192.0.2.1 332 TXT "d record" 333 NSEC example.org. A TXT NSEC RRSIG 334 RRSIG(A) ( ... ) 335 RRSIG(TXT) ( ... ) 336 RRSIG(NSEC) ( ... ) 338 The signed and sorted "example.org" zone with the added NSEC records 339 (and signatures). For brevity, the class is not shown (defaults to 340 IN), the NS records are left out and the SOA, DNSKEY and RRSIG 341 records are shortened. 343 Figure 3 345 If a DNSSEC aware resolver asks for "b.example.org", it gets back a 346 "status: NXDOMAIN" packet, which by itself is meaningless as the 347 header can be forged. To be able to securely detect that "b" does 348 not exist, there must also be a signed NSEC record which covers the 349 name space where "b" lives. The record: 351 a.example.org. NSEC d.example.org. 353 does just do that: "b" should come after "a", but the next owner name 354 is "d.example.org", so "b" does not exist. 356 Only by making that calculation, is a resolver able to conclude that 357 the name "b" does not exist. If the signature of the NSEC record is 358 valid, "b" is proven not to exist. We have: authenticated denial of 359 existence. 361 Note that a man-in-the-middle may still replay this NXDOMAIN response 362 when you're querying for, say, "c.example.org". But it would not do 363 any harm since it is provably the proper response to the query. In 364 the future, there may be data published for "c.example.org". 365 Therefore, the RRSIGs RDATA include a validity period (not visible in 366 the zone above), so that an attacker cannot replay this NXDOMAIN 367 response for "c.example.org" forever. 369 3.3. NODATA Responses 371 NSEC records are also used in NODATA responses. In that case we need 372 to look more closely at the type bitmap. The type bitmap in an NSEC 373 record tells which types are defined for a name. If we look at the 374 NSEC record of "a.example.org", we see the following types in the 375 bitmap: A, TXT, NSEC and RRSIG. So for the name "a" this indicates 376 we must have an A, TXT, NSEC and RRSIG record in the zone. 378 With the type bitmap of the NSEC record, a resolver can establish 379 that a name is there, but the type is not. For example, if a 380 resolver asks for "a.example.org AAAA", the reply that comes back is: 382 ;; status: NOERROR, id: 44638 384 ;; AUTHORITY SECTION: 385 example.org. SOA ( ... ) 386 example.org. RRSIG(SOA) ( ... ) 387 a.example.org. NSEC d.example.org. A TXT NSEC RRSIG 388 a.example.org. RRSIG(NSEC) ( ... ) 390 The resolver should check the AUTHORITY section and conclude that: 392 (1) "a.example.org" exists (because of the NSEC with that owner name) 393 and; 395 (2) the type (AAAA) does not as it is not listed in the type bitmap. 397 The techniques used by NSEC, form the basics of authenticated denial 398 of existence in DNSSEC. 400 3.4. Drawbacks of NSEC 402 There were two issues with NSEC (and NXT). The first is that it 403 allows for zone walking. NSEC records point from one name to 404 another, in our example: "example.org", points to "a.example.org" 405 which points to "d.example.org" which points back to "example.org". 406 So we can reconstruct the entire "example.org" zone even when zone 407 transfers (AXFR) on the server are denied. 409 The second issue is that when a large, delegation heavy, zone deploys 410 DNSSEC, every name in the zone gets an NSEC plus RRSIG. This leads 411 to a huge increase in the zone size (when signed). This would in 412 turn mean that operators of such zones who are deploying DNSSEC, face 413 up front costs. This could hinder DNSSEC adoption. 415 These two issues eventually lead to NSEC3 which: 417 o Adds a way to garble the next owner name, thus thwarting zone- 418 walking; 420 o Makes it possible to skip names for the next owner name. This 421 feature is called opt-out. It means not all names in your zone 422 get an NSEC3 plus ditto signature, making it possible to "grow 423 into" your DNSSEC deployment. Describing opt-out is out of scope 424 for this document. For those interested, opt-out is explained in 425 RFC 4956 [RFC4956], which is curiously titled "(DNSSEC) Opt-In". 426 Later this was incorporated into RFC 5155 [RFC5155]. 428 But before we delve into NSEC3, let us first take a look at its 429 predecessors: NO, NSEC2 and, DNSNR. 431 3.5. NO, NSEC2 and DNSNR 433 The NO record was the first to introduce the idea of hashed owner 434 names. It also fixed other shortcomings of the NXT record. At that 435 time (around 2000) zone walking was not considered important enough 436 to warrant the new record. People were also worried that DNSSEC 437 deployment would be hindered by developing an alternate means of 438 denial of existence. Thus the effort was shelved and NXT remained. 439 When the new DNSSEC specification was written, NSEC saw the light and 440 inherited the two issues from NXT. 442 Several years after that NSEC2 was introduced as a way to solve the 443 two issues of NSEC. The NSEC2 draft contains the following 444 paragraph: 446 "This document proposes an alternate scheme which hides owner 447 names while permitting authenticated denial of existence of non- 448 existent names. The scheme uses two new RR types: NSEC2 and 449 EXIST." 451 When an authenticated denial of existence scheme starts to talk about 452 EXIST records, it is worth paying extra attention. 454 NSEC2 solved the zone walking issue, by hashing (with SHA1 and a 455 salt) the "next owner name" in the record, thereby making it useless 456 for zone walking. 458 But it did not have opt-out. Although promising, the proposal did 459 not make it because of issues with wildcards and the odd EXIST 460 resource record. 462 The DNSNR record was another attempt that used hashed names to foil 463 zone walking and it also introduced the concept of opting out (called 464 "Authoritative Only Flag") which limited the use of DNSNR in 465 delegation heavy zones. This proposal didn't make it either, but it 466 provided valuable insights into the problem. 468 3.6. NSEC3 470 From the experience gained with NSEC2 and DNSNR, NSEC3 was forged. 471 It incorporates both opt-out and the hashing of names. NSEC3 solves 472 any issues people might have with NSEC, but it introduces some 473 additional complexity. 475 NSEC3 did not supersede NSEC, they are both defined for DNSSEC. So 476 DNSSEC is blessed with two different means to perform authenticated 477 denial of existence: NSEC and NSEC3. In NSEC3 every name is hashed, 478 including the owner name. This means that NSEC3 chain is sorted in 479 hash order, instead of canonical order. Because the owner names are 480 hashed, the next owner name for "example.org" is unlikely to be 481 "a.example.org". Because the next owner name is hashed, zone walking 482 becomes more difficult. 484 To make it even more difficult to retrieve the original names, the 485 hashing can be repeated several times each time taking the previous 486 hash as input. To thwart rainbow table attacks, a custom salt is 487 also added. In the NSEC3 for "example.org" we have hashed the names 488 thrice ([RFC5155], Section 5) and use the salt "DEAD". Lets look at 489 typical NSEC3 record: 491 15BG9L6359F5CH23E34DDUA6N1RIHL9H.example.org. ( 492 NSEC3 1 0 2 DEAD A6EDKB6V8VL5OL8JNQQLT74QMJ7HEB84 493 SOA RRSIG DNSKEY NSEC3PARAM ) 495 On the first line we see the hashed owner name: 496 "15BG9L6359F5CH23E34DDUA6N1RIHL9H.example.org", this is the hashed 497 name of the fully qualified domain name (FQDN) "example.org". Note 498 that even though we hashed "example.org", the zone's name is added to 499 make it look like a domain name again. In our zone, the basic format 500 is "SHA1(FQDN).example.org". 502 The next hashed owner name "A6EDKB6V8VL5OL8JNQQLT74QMJ7HEB84" (line 503 2) is the hashed version of "d.example.org". Note that 504 ".example.org" is not added to the next hashed owner name, as this 505 name always falls in the current zone. 507 The "1 0 2 DEAD" section of the NSEC3 states: 509 o Hash Algorithm = 1 (SHA1, this is the default, no other hash 510 algorithms are currently defined for use in NSEC3); 512 o Opt Out = 0 (disabled); 514 o Hash Iterations = 2, this yields three iterations, as a zero value 515 is already one iteration; 517 o Salt = "DEAD". 519 At the end we see the type bitmap, which is identical to NSEC's 520 bitmap, that lists the types present at the original owner name. 521 Note that the type NSEC3 is absent from the list in the example 522 above. This is due to the fact that the original owner name 523 ("example.org") does not have the NSEC3 type. It only exists for the 524 hashed name. 526 Names like "1.h.example.org" hash to one label in NSEC3, 527 "1.h.example.org" becomes: 528 "117GERCPRCJGG8J04EV1NDRK8D1JT14K.example.org" when used as an owner 529 name. This is an important observation. By hashing the names you 530 lose the depth of a zone - hashing introduces a flat space of names, 531 as opposed to NSEC. 533 The domain name used above ("1.h.example.org") creates an empty non- 534 terminal. Empty non-terminals are domain names that have no RRs 535 associated with them, and exist only because they have one or more 536 subdomains that do ([RFC5155], Section 1.3). The record: 538 1.h.example.org. TXT "1.h record" 540 creates two names: 542 1. "1.h.example.org" that has the type: TXT; 544 2. "h.example.org" which has no types. This is the empty non- 545 terminal. An empty non-terminal will get an NSEC3 records, but 546 not an NSEC record. 548 3.7. Loading an NSEC3 Zone 550 Whenever an authoritative server receives a query for a non-existing 551 record, it has to hash the incoming query name to determine into 552 which interval between two existing hashes it falls. To do that it 553 needs to know the zone's specific NSEC3 parameters (hash iterations 554 and salt). 556 One way to learn them is to scan the zone during loading for NSEC3 557 records and glean the NSEC3 parameters from them. However, it would 558 need to make sure that there is at least one complete set of NSEC3 559 records for the zone using the same parameters. Therefore, it would 560 need to inspect all NSEC3 records. 562 A more graceful solution was designed. The solution was to create a 563 new record, NSEC3PARAM, which must be placed at the apex of the zone. 564 Its sole role is to provide a single, fixed place where an 565 authoritative name server can directly see the NSEC3 parameters used. 566 If NSEC3 were designed in the early days of DNS (+/- 1984) this 567 information would probably have been put in the SOA record. 569 3.8. Wildcards in the DNS 571 So far, we have only talked about denial of existence in negative 572 responses. However, denial of existence may also occur in positive 573 responses, i.e., where the ANSWER section of the response is not 574 empty. This can happen because of wildcards. 576 Wildcards have been part of the DNS since the first DNS RFCs. They 577 allow to define all names for a certain type in one go. In our 578 "example.org" zone we could for instance add a wildcard record: 580 *.example.org. TXT "wildcard record" 582 For completeness, our (unsigned) zone now looks like this: 584 example.org. SOA ( ... ) 585 *.example.org. TXT "wildcard record" 586 a.example.org. A 192.0.2.1 587 TXT "a record" 588 d.example.org. A 192.0.2.1 589 TXT "d record" 591 The example.org zone with a wildcard record. 593 Figure 4 595 If a resolver asks for "z.example.org TXT", the name server will 596 respond with an expanded wildcard, instead of an NXDOMAIN: 598 ;; status: NOERROR, id: 13658 600 ;; ANSWER SECTION: 601 z.example.org. TXT "wildcard record" 603 Note however that the resolver can not detect that this answer came 604 from a wildcard. It just sees the answer as-is. How will this 605 answer look with DNSSEC? 606 ;; status: NOERROR, id: 51790 608 ;; ANSWER SECTION: 609 z.example.org. TXT "wildcard record" 610 z.example.org. RRSIG(TXT) ( ... ) 612 ;; AUTHORITY SECTION: 613 d.example.org. NSEC example.org. A TXT RRSIG NSEC 614 d.example.org. RRSIG(NSEC) ( ... ) 616 The RRSIG of the "z.example.org" TXT record indicates there is a 617 wildcard configured. The RDATA of the signature lists a label count 618 [RFC4034], Section 3.1.3., of two (not visible in the answer above), 619 but the owner name of the signature has three labels. This mismatch 620 indicates there is a wildcard "*.example.org" configured. 622 An astute reader may notice that it appears as if a 623 "z.example.org" RRSIG(TXT) is created out of thin air. This is 624 not the case. The signature for "z.example.org" does not exist. 625 The signature you are seeing is the one for "*.example.org" which 626 does exist, only the owner name is switched to "z.example.org". 627 So even with wildcards, no signatures have to be created on the 628 fly. 630 The DNSSEC standard mandates that an NSEC (or NSEC3) is included in 631 such responses. If it wasn't, an attacker could mount a replay 632 attack and poison the cache with false data: Suppose that the 633 resolver has asked for "a.example.org TXT". An attacker could modify 634 the packet in such way that it looks like the response was generated 635 through wildcard expansion, even though there exists a record for 636 "a.example.org TXT". 638 The tweaking simply consists of adjusting the ANSWER section to: 640 ;; status: NOERROR, id: 31827 642 ;; ANSWER SECTION 643 a.example.org. TXT "wildcard record" 644 a.example.org. RRSIG(TXT) ( ... ) 646 Which would be a perfectly valid answer if we would not require the 647 inclusion of an NSEC or NSEC3 record in the wildcard answer response. 648 The resolver believes that "a.example.org TXT" is a wildcard record, 649 and the real record is obscured. This is bad and defeats all the 650 security DNSSEC can deliver. Because of this, the NSEC or NSEC3 must 651 be present. 653 Another way of putting this is that DNSSEC is there to ensure the 654 name server has followed the steps as outlined in [RFC1034], Section 655 4.3.2 for looking up names in the zone. It explicitly lists wildcard 656 look up as one of these steps (3c), so with DNSSEC this must be 657 communicated to the resolver: hence the NSEC(3) record. 659 3.9. CNAME Records 661 So far, the maximum number of NSEC records a response will have is 662 two: one for the denial of existence and another for the wildcard. 663 We say maximum, because sometimes a single NSEC can prove both. With 664 NSEC3, this is three (as to why, we will explain in the next 665 section). 667 When we take CNAME wildcard records into account, we can have more 668 NSEC(3) records. For every wildcard expansion, we need to prove that 669 the expansion was allowed. Lets add some CNAME wildcard records to 670 our zone: 672 example.org. SOA ( ... ) 673 *.example.org. TXT "wildcard record" 674 a.example.org. A 192.0.2.1 675 TXT "a record" 676 *.a.example.org. CNAME w.b 677 *.b.example.org. CNAME w.c 678 *.c.example.org. A 192.0.2.1 679 d.example.org. A 192.0.2.1 680 TXT "d record" 681 w.example.org. CNAME w.a 683 A wildcard CNAME chain added to the "example.org" zone. 685 Figure 5 687 A query for "w.example.org A" will result in the following response: 689 ;; status: NOERROR, id: 4307 691 ;; ANSWER SECTION: 692 w.example.org. CNAME w.a.example.org. 693 w.example.org. RRSIG(CNAME) ( ... ) 694 w.a.example.org. CNAME w.b.example.org. 695 w.a.example.org. RRSIG(CNAME) ( ... ) 696 w.b.example.org. CNAME w.c.example.org. 697 w.b.example.org. RRSIG(CNAME) ( ... ) 698 w.c.example.org. A 192.0.2.1 699 w.c.example.org. RRSIG(A) ( ... ) 701 ;; AUTHORITY SECTION: 702 *.a.example.org. NSEC *.b.example.org. CNAME RRSIG NSEC 703 *.a.example.org. RRSIG(NSEC) ( ... ) 704 *.b.example.org. NSEC *.c.example.org. CNAME RRSIG NSEC 705 *.b.example.org. RRSIG(NSEC) ( ... ) 706 *.c.example.org. NSEC d.example.org. A RRSIG NSEC 707 *.c.example.org. RRSIG(NSEC) ( ... ) 709 The NSEC record "*.a.example.org" proves that wildcard expansion to 710 "w.a.example.org" was appropriate: "w.a." falls in the gap "*.a" to 711 "*.b". Similar, the NSEC record "*.b.example.org" proves that there 712 was no direct match for "w.b.example.org" and "*.c.example.org" 713 denies the direct match for "w.c.example.org". 715 3.10. The Closest Encloser NSEC3 Record 717 We can have one or more NSEC3 records that deny the existence of the 718 requested name and one NSEC3 record that deny wildcard synthesis. 719 What do we miss? 721 The short answer is that, due to the hashing in NSEC3 you loose the 722 depth of your zone: Everything is hashed into a flat plane. To make 723 up for this loss of information you need an extra record. The more 724 detailed explanation is quite a bit longer... 726 To understand NSEC3, we will need two definitions: 728 Closest encloser: Introduced in [RFC4592], "The closest encloser is 729 the node in the zone's tree of existing domain names that has the 730 most labels matching the query name (consecutively, counting from 731 the root label downward)." In our example, if the query name is 732 "x.2.example.org" then "example.org" is the "closest encloser"; 734 Next closer name: Introduced in the NSEC3 RFC, this is the closest 735 encloser with one more label added to the left. So if 736 "example.org" is the closest encloser for the query name 737 "x.2.example.org", "2.example.org" is the "next closer name". 739 An NSEC3 "closest encloser proof" consists of: 741 1. An NSEC3 record that *matches* the "closest encloser". This 742 means the unhashed owner name of the record is the closest 743 encloser. This bit of information tells a resolver: "The name 744 you are asking for does not exist, the closest I have is this". 746 2. An NSEC3 record that *covers* the "next closer name". This means 747 it defines an interval in which the "next closer name" falls. 748 This tells the resolver: "The next closer name falls in this 749 interval, and therefore the name in your question does not exist. 750 In fact, the closest encloser is indeed the closest I have". 752 These two records already deny the existence of the requested name, 753 so we do not need an NSEC3 record that covers the actual queried 754 name: By denying the existence of the next closer name, you also deny 755 the existence of the queried name. 757 For a given query name, there is one (and only one) place where 758 wildcard expansion is possible. This is the "source of synthesis", 759 and is defined ([RFC4592], Section 2.1.1 and Section 3.3.1) as: 761 . 763 In other words, to deny wildcard synthesis, the resolver needs to 764 know the hash of the source of synthesis. Since it does not know 765 beforehand what the closest encloser of the query name is, it must be 766 provided in the answer. 768 Take the following example. We take our zone, and put two TXT 769 records to it. The records added are "1.h.example.org" and 770 "3.3.example.org". It is signed with NSEC3, resulting in the 771 following unsigned zone. 773 example.org. SOA ( ... ) 774 1.h.example.org. TXT "1.h record" 775 3.3.example.org. TXT "3.3 record" 777 The added TXT records in example.org. These records create two non- 778 terminals: `h.example.org` and `3.example.org`. 780 Figure 6 782 The resolver asks the following: "x.2.example.org TXT". This leads 783 to an NXDOMAIN response from the server, which contains three NSEC3 784 records. A list of hashed owner names can be found in Section 4. 785 Also see Figure 7 the numbers in that figure correspond with the 786 following NSEC3 records: 788 15BG9L6359F5CH23E34DDUA6N1RIHL9H.example.org. ( 789 NSEC3 1 0 2 DEAD 1AVVQN74SG75UKFVF25DGCETHGQ638EK SOA 790 RRSIG DNSKEY NSEC3PARAM ) 792 75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ.example.org. ( 793 NSEC3 1 0 2 DEAD 8555T7QEGAU7PJTKSNBCHG4TD2M0JNPJ TXT 794 RRSIG ) 796 1AVVQN74SG75UKFVF25DGCETHGQ638EK.example.org. ( 797 NSEC3 1 0 2 DEAD 75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ ) 799 If we would follow the NSEC approach, the resolver is only interested 800 in one thing. Does the hash of "x.2.example.org" fall in any of the 801 intervals of the NSEC3 records it got? 802 example.org 803 ** 804 +-- ** . . . . . . . . . . . 805 (1) / . /\ . . 806 / . | . . 807 | . | . . 808 v . | . . 809 ** | ** -- 810 h.example.org ** ----+----> ** 3.example.org -- 2.example.org 811 . / (3) . | . 812 . / . | (2) . 813 . / . | . 814 . / . v . 815 1.h.example.org ** ** -- 816 ** <--------- ** 3.3.example.org -- x.2.example.org 818 x.2.example.org does not exist. The arrows represent the NSEC3 819 records, the ones numbered (1), (2) and (3) are the NSEC3s returned 820 in our answer. 822 Figure 7 824 The hash of "x.2.example.org" is "NDTU6DSTE50PR4A1F2QVR1V31G00I2I1". 825 Checking this hash on the first NSEC3 yields that it does not fall in 826 between the interval: "15BG9L6359F5CH23E34DDUA6N1RIHL9H" and 827 "1AVVQN74SG75UKFVF25DGCETHGQ638EK". For the second NSEC3 the answer 828 is also negative: the hash sorts outside the interval described by 829 "75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ" and 830 "8555T7QEGAU7PJTKSNBCHG4TD2M0JNPJ". And the last NSEC3 also isn't of 831 any help. What is a resolver to do? It has been given the maximum 832 amount of NSEC3s and they all seem useless. 834 So this is where the closest encloser proof comes into play. And for 835 the proof to work, the resolver needs to know what the closest 836 encloser is. There must be an existing ancestor in the zone: a name 837 must exist that is shorter than the query name. The resolver keeps 838 hashing increasingly shorter names from the query name until an owner 839 name of an NSEC3 matches. This owner name is the closest encloser. 841 When the resolver has found the closest encloser, the next step is to 842 construct the next closer name. This is the closest encloser with 843 the last chopped label from query name prepended to it: ".". The hash of this name should be 845 covered by the interval set in any of the NSEC3 records. 847 Then the resolver needs to check the presence of a wildcard. It 848 creates the wildcard name by prepending the asterisk label to the 849 closest encloser: "*.", and uses the hash of that. 851 Going back to our example, the resolver must first detect the NSEC3 852 that matches the closest encloser. It does this by chopping up the 853 query name, hashing each instance (with the same number of iterations 854 and hash as the zone it is querying) and comparing that to the 855 answers given. So it has the following hashes to work with: 857 x.2.example.org: "NDTU6DSTE50PR4A1F2QVR1V31G00I2I1", last chopped 858 label: ""; 860 2.example.org: "7T70DRG4EKC28V93Q7GNBLEOPA7VLP6Q", last chopped 861 label: "x"; 863 example.org: "15BG9L6359F5CH23E34DDUA6N1RIHL9H", last chopped label: 864 "2"; 866 Of these hashes only one matches the owner name of one of the NSEC3 867 records: "15BG9L6359F5CH23E34DDUA6N1RIHL9H". This must be the 868 closest encloser (unhashed: "example.org"). That's the main purpose 869 of that NSEC3 record: tell the resolver what the closest encloser is. 871 From that knowledge the resolver constructs the next closer, which in 872 this case is: "2.example.org"; "2" is the last label chopped, when 873 "example.org" is the closest encloser. The hash of this name should 874 be covered in any of the other NSEC3s. And it is, 875 "7T70DRG4EKC28V93Q7GNBLEOPA7VLP6Q" falls in the interval set by: 876 "75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ" and 877 "8555T7QEGAU7PJTKSNBCHG4TD2M0JNPJ" (this is our second NSEC3). 879 So what does the resolver learn from this? 881 o "example.org" exists; 883 o "2.example.org" does not exist. 885 And if "2.example.org" does not exist, there is also no direct match 886 for "x.2.example.org". The last step is to deny the existence of the 887 source of synthesis, to prove that no wildcard expansion was 888 possible. 890 The resolver hashes "*.example.org" to 891 "22670TRPLHSR72PQQMEDLTG1KDQEOLB7" and checks that it is covered: in 892 this case by the last NSEC3 (see Figure 7), the hash falls in the 893 interval set by "1AVVQN74SG75UKFVF25DGCETHGQ638EK" and 894 "75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ". This means there is no wildcard 895 record directly below the closest encloser and "x.2.example.org" 896 definitely does not exist. 898 When we have validated the signatures, we reached our goal: 899 authenticated denial of existence. 901 3.11. Three To Tango 903 One extra NSEC3 record plus additional signature may seem a lot just 904 to deny the existence of the wildcard record, but we cannot leave it 905 out. If the standard would not mandate the closest encloser NSEC3 906 record, but instead required two NSEC3 records: one to deny the query 907 name and one to deny the wildcard record. An attacker could fool the 908 resolver that the source of synthesis does not exist, while it in 909 fact does. 911 Suppose the wildcard record does exist, so our unsigned zone looks 912 like this: 914 example.org. SOA ( ... ) 915 *.example.org. TXT "wildcard record" 916 1.h.example.org. TXT "1.h record" 917 3.3.example.org. TXT "3.3 record" 919 The query "x.2.example.org TXT" should now be answered with: 921 x.2.example.org. TXT "wildcard record" 923 An attacker can deny this wildcard expansion by calculating the hash 924 for the wildcard name "*.2.example.org" and searching for an NSEC3 925 record that covers that hash. The hash of "*.2.example.org" is 926 "FBQ73BFKJLRKDOQS27K5QF81AQQD7HHO". Looking through the NSEC3 927 records in our zone we see that the NSEC3 record of "3.3" covers this 928 hash: 930 8555T7QEGAU7PJTKSNBCHG4TD2M0JNPJ.example.org. ( 931 NSEC3 1 0 2 DEAD 15BG9L6359F5CH23E34DDUA6N1RIHL9H TXT RRSIG ) 933 This record also covers the query name "x.2.example.org" 934 ("NDTU6DSTE50PR4A1F2QVR1V31G00I2I1"). 936 Now an attacker adds this NSEC3 record to the AUTHORITY section of 937 the reply to deny both "x.2.example.org" and any wildcard expansion. 938 The net result is that the resolver determines that "x.2.example.org" 939 does not exist, while in fact it should have been synthesized via 940 wildcard expansion. With the NSEC3 matching the closest encloser 941 "example.org", the resolver can be sure that the wildcard expansion 942 should occur at "*.example.org" and nowhere else. 944 Coming back to the original question: why do we need up to three 945 NSEC3 records to deny a requested name? The resolver needs to be 946 explicitly told what the "closest encloser" is and this takes up a 947 full NSEC3 record. Then, the next closer name needs to be covered in 948 an NSEC3 record, and finally an NSEC3 must say something about 949 whether wildcard expansion was possible. That makes three to tango. 951 4. List of Hashed Owner Names 953 The following owner names are used in this document. The origin for 954 these names is "example.org". 956 +----------------+-------------------------------------+ 957 | Original Name | Hashed Name | 958 +----------------+-------------------------------------+ 959 | "a" | "04SKNAPCA5AL7QOS3KM2L9TL3P5OKQ4C" | 960 | "1.h" | "117GERCPRCJGG8J04EV1NDRK8D1JT14K" | 961 | "@" | "15BG9L6359F5CH23E34DDUA6N1RIHL9H" | 962 | "h" | "1AVVQN74SG75UKFVF25DGCETHGQ638EK" | 963 | "*" | "22670TRPLHSR72PQQMEDLTG1KDQEOLB7" | 964 | "3" | "75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ" | 965 | "2" | "7T70DRG4EKC28V93Q7GNBLEOPA7VLP6Q" | 966 | "3.3" | "8555T7QEGAU7PJTKSNBCHG4TD2M0JNPJ" | 967 | "d" | "A6EDKB6V8VL5OL8JNQQLT74QMJ7HEB84" | 968 | "*.2" | "FBQ73BFKJLRKDOQS27K5QF81AQQD7HHO" | 969 | "b" | "IUU8L5LMT76JELTP0BIR3TMG4U3UU8E7" | 970 | "x.2" | "NDTU6DSTE50PR4A1F2QVR1V31G00I2I1" | 971 +----------------+-------------------------------------+ 973 Hashed owner names for example.org in hash order. 975 Table 1 977 5. Security Considerations 979 DNSSEC does not protect against denial of service attacks, nor does 980 it provide confidentiality. For more general security considerations 981 related to DNSSEC, please see RFC 4033, RFC 4034, RFC 4035 and RFC 982 5155 ([RFC4033], [RFC4034], [RFC4035] and [RFC5155]). 984 These RFCs are concise about why certain design choices have been 985 made in the area of authenticated denial of existence. 986 Implementations that do not correctly handle this aspect of DNSSEC, 987 create a severe hole in the security DNSSEC adds. This is 988 specifically troublesome for secure delegations: If an attacker is 989 able to deny the existence of a DS record, the resolver cannot 990 establish a chain of trust, and the resolver has to fall back to 991 insecure DNS for the remainder of the query resolution. 993 This document aims to fill this "documentation gap" and provide 994 would-be implementors and other interested parties with enough 995 background knowledge to better understand authenticated denial of 996 existence. 998 6. IANA Considerations 1000 This document has no actions for IANA. 1002 7. Acknowledgments 1004 This document would not be possible without the help of Ed Lewis, Roy 1005 Arends, Wouter Wijngaards, Olaf Kolkman, Carsten Strotmann, Jan-Piet 1006 Mens, Peter van Dijk, Marco Davids, Esther Makaay, Antoin Verschuren 1007 and Lukas Wunner. Also valuable was the source code of Unbound 1008 ("validator/val_nsec3.c"). Extensive feedback was received from 1009 Karst Koymans. 1011 8. References 1013 8.1. Normative References 1015 [RFC1034] Mockapetris, P., "Domain names - concepts and facilities", 1016 STD 13, RFC 1034, November 1987. 1018 [RFC2308] Andrews, M., "Negative Caching of DNS Queries (DNS 1019 NCACHE)", RFC 2308, March 1998. 1021 [RFC4033] Arends, R., Austein, R., Larson, M., Massey, D., and S. 1022 Rose, "DNS Security Introduction and Requirements", RFC 1023 4033, March 2005. 1025 [RFC4034] Arends, R., Austein, R., Larson, M., Massey, D., and S. 1026 Rose, "Resource Records for the DNS Security Extensions", 1027 RFC 4034, March 2005. 1029 [RFC4035] Arends, R., Austein, R., Larson, M., Massey, D., and S. 1030 Rose, "Protocol Modifications for the DNS Security 1031 Extensions", RFC 4035, March 2005. 1033 [RFC4592] Lewis, E., "The Role of Wildcards in the Domain Name 1034 System", RFC 4592, July 2006. 1036 [RFC5155] Laurie, B., Sisson, G., Arends, R., and D. Blacka, "DNS 1037 Security (DNSSEC) Hashed Authenticated Denial of 1038 Existence", RFC 5155, March 2008. 1040 8.2. Informative References 1042 [I-D.arends-dnsnr] 1043 Arends, R., "DNSSEC Non-Repudiation Resource Record", 1044 Internet-Draft draft-arends-dnsnr-00, July 2004. 1046 [I-D.ietf-dnsext-not-existing-rr] 1047 Josefsson, S., "Authenticating denial of existence in DNS 1048 with minimum disclosure", Internet-Draft draft-ietf- 1049 dnsext-not-existing-rr-01, November 2000. 1051 [I-D.laurie-dnsext-nsec2v2] 1052 Laurie, B., "DNSSEC NSEC2 Owner and RDATA Format", 1053 Internet-Draft draft-laurie-dnsext-nsec2v2-00, December 1054 2004. 1056 [RFC2535] Eastlake, D., "Domain Name System Security Extensions", 1057 RFC 2535, March 1999. 1059 [RFC3655] Wellington, B. and O. Gudmundsson, "Redefinition of DNS 1060 Authenticated Data (AD) bit", RFC 3655, November 2003. 1062 [RFC3755] Weiler, S., "Legacy Resolver Compatibility for Delegation 1063 Signer (DS)", RFC 3755, May 2004. 1065 [RFC4956] Arends, R., Kosters, M., and D. Blacka, "DNS Security 1066 (DNSSEC) Opt-In", RFC 4956, July 2007. 1068 Appendix A. Changelog 1070 [This section should be removed by the RFC editor before publishing] 1072 A.1. -00 1074 1. Initial document. 1076 A.2. -01 1078 1. Style and language changes; 1080 2. Figure captions; 1082 3. Security considerations added; 1084 4. Fix erroneous NSEC3 RR; 1086 5. Section on CNAMEs added; 1088 6. More detailed text on closest encloser proof. 1090 Authors' Addresses 1092 R. (Miek) Gieben 1093 SIDN Labs 1094 Meander 501 1095 Arnhem 6825 MD 1096 NL 1098 EMail: miek.gieben@sidn.nl 1099 URI: https://sidn.nl/ 1100 W. (Matthijs) Mekking 1101 NLnet Labs 1102 Science Park 400 1103 Amsterdam 1098 XH 1104 NL 1106 EMail: matthijs@nlnetlabs.nl 1107 URI: http://www.nlnetlabs.nl/