1 Independent Submission R. Gieben
2 Request for Comments: 7129 Google
3 Category: Informational W. Mekking
4 ISSN: 2070-1721 NLnet Labs
5 February 2014
6
7
8 Authenticated Denial of Existence in the DNS
9
10 Abstract
11
12 Authenticated denial of existence allows a resolver to validate that
13 a certain domain name does not exist. It is also used to signal that
14 a domain name exists but does not have the specific resource record
15 (RR) type you were asking for. When returning a negative DNS
16 Security Extensions (DNSSEC) response, a name server usually includes
17 up to two NSEC records. With NSEC version 3 (NSEC3), this amount is
18 three.
19
20 This document provides additional background commentary and some
21 context for the NSEC and NSEC3 mechanisms used by DNSSEC to provide
22 authenticated denial-of-existence responses.
23
24 Status of This Memo
25
26 This document is not an Internet Standards Track specification; it is
27 published for informational purposes.
28
29 This is a contribution to the RFC Series, independently of any other
30 RFC stream. The RFC Editor has chosen to publish this document at
31 its discretion and makes no statement about its value for
32 implementation or deployment. Documents approved for publication by
33 the RFC Editor are not a candidate for any level of Internet
34 Standard; see Section 2 of RFC 5741.
35
36 Information about the current status of this document, any errata,
37 and how to provide feedback on it may be obtained at
38 http://www.rfc-editor.org/info/rfc7129.
39
40
41
42
43
44
45
46
47
48
49
50
51
52 Gieben & Mekking Informational [Page 1]
53 RFC 7129 Authenticated Denial in DNS February 2014
54
55
56 Copyright Notice
57
58 Copyright (c) 2014 IETF Trust and the persons identified as the
59 document authors. All rights reserved.
60
61 This document is subject to BCP 78 and the IETF Trust's Legal
62 Provisions Relating to IETF Documents
63 (http://trustee.ietf.org/license-info) in effect on the date of
64 publication of this document. Please review these documents
65 carefully, as they describe your rights and restrictions with respect
66 to this document.
67
68 Table of Contents
69
70 1. Introduction ....................................................3
71 2. Denial of Existence .............................................4
72 2.1. NXDOMAIN Responses .........................................4
73 2.2. NODATA Responses ...........................................5
74 3. Secure Denial of Existence ......................................6
75 3.1. NXT ........................................................7
76 3.2. NSEC .......................................................7
77 3.3. NODATA Responses ...........................................9
78 3.4. Drawbacks of NSEC .........................................10
79 4. Experimental and Deprecated Mechanisms: NO, NSEC2, and DNSNR ...11
80 5. NSEC3 ..........................................................12
81 5.1. Opt-Out ...................................................14
82 5.2. Loading an NSEC3 Zone .....................................15
83 5.3. Wildcards in the DNS ......................................15
84 5.4. CNAME Records .............................................18
85 5.5. The Closest Encloser NSEC3 Record .........................19
86 5.6. Three to Tango ............................................24
87 6. Security Considerations ........................................25
88 7. Acknowledgments ................................................25
89 8. References .....................................................26
90 8.1. Normative References ......................................26
91 8.2. Informative References ....................................26
92 Appendix A. Online Signing: Minimally Covering NSEC Records .......28
93 Appendix B. Online Signing: NSEC3 White Lies ......................29
94 Appendix C. List of Hashed Owner Names ............................29
95
96
97
98
99
100
101
102
103
104
105
106
107 Gieben & Mekking Informational [Page 2]
108 RFC 7129 Authenticated Denial in DNS February 2014
109
110
111 1. Introduction
112
113 DNSSEC can be somewhat of a complicated matter, and there are certain
114 areas of the specification that are more difficult to comprehend than
115 others. One such area is "authenticated denial of existence".
116
117 Denial of existence is a mechanism that informs a resolver that a
118 certain domain name does not exist. It is also used to signal that a
119 domain name exists but does not have the specific RR type you were
120 asking for.
121
122 The first is referred to as a nonexistent domain (NXDOMAIN)
123 ([RFC2308], Section 2.1) and the latter as a NODATA ([RFC2308],
124 Section 2.2) response. Both are also known as negative responses.
125
126 Authenticated denial of existence uses cryptography to sign the
127 negative response. However, if there is no answer, what is it that
128 needs to be signed? To further complicate this matter, there is the
129 desire to pre-generate negative responses that are applicable for all
130 queries for nonexistent names in the signed zone. See Section 3 for
131 the details.
132
133 In this document, we will explain how authenticated denial of
134 existence works. We begin by explaining the current technique in the
135 DNS and work our way up to DNSSEC. We explain the first steps taken
136 in DNSSEC and describe how NSEC and NSEC3 work. The NXT, NO, NSEC2,
137 and DNSNR records also briefly make their appearance, as they have
138 paved the way for NSEC and NSEC3.
139
140 To complete the picture, we also need to explain DNS wildcards as
141 these complicate matters, especially when combined with CNAME
142 records.
143
144 Note: In this document, domain names in zone file examples will have
145 a trailing dot, but in the running text they will not. This text is
146 written for people who have a fair understanding of DNSSEC. The
147 following RFCs are not required reading, but they help in
148 understanding the problem space.
149 o [RFC5155] -- DNS Security (DNSSEC) Hashed Authenticated Denial of
150 Existence;
151
152 o [RFC4592] -- The Role of Wildcards in the Domain Name System.
153
154 And, these provide some general DNSSEC information.
155
156 o [RFC4033], [RFC4034], and [RFC4035] -- DNSSEC specifications;
157
158
159
160
161
162 Gieben & Mekking Informational [Page 3]
163 RFC 7129 Authenticated Denial in DNS February 2014
164
165
166 o [RFC4956] -- DNS Security (DNSSEC) Opt-In. This RFC has an
167 Experimental status but is a good read.
168
169 These three documents give some background information on the NSEC3
170 development.
171
172 o The NO record [DNSEXT];
173
174 o The NSEC2 record [DNSEXT-NSEC2];
175
176 o The DNSNR record [DNSNR-RR].
177
178 2. Denial of Existence
179
180 We start with the basics and take a look at NXDOMAIN handling in the
181 DNS. To make it more visible, we are going to use a small DNS zone
182 with three names ("example.org", "a.example.org", and
183 "d.example.org") and four types (SOA, NS, A, and TXT). For brevity,
184 the class is not shown (defaults to IN) and the SOA record is
185 shortened, resulting in the following zone file:
186
187 example.org. SOA ( ... )
188 example.org. NS a.example.org.
189 a.example.org. A 192.0.2.1
190 TXT "a record"
191 d.example.org. A 192.0.2.1
192 TXT "d record"
193
194 Figure 1: The Unsigned "example.org" Zone
195
196 2.1. NXDOMAIN Responses
197
198 If a resolver asks the name server serving this zone for the TXT type
199 belonging to "a.example.org", it sends the following question:
200 "a.example.org TXT".
201
202 The name server looks in its zone data and generates an answer. In
203 this case, a positive one: "Yes, it exists and this is the data",
204 resulting in this reply:
205
206 ;; status: NOERROR, id: 28203
207
208 ;; ANSWER SECTION:
209 a.example.org. TXT "a record"
210
211 ;; AUTHORITY SECTION:
212 example.org. NS a.example.org.
213
214
215
216
217 Gieben & Mekking Informational [Page 4]
218 RFC 7129 Authenticated Denial in DNS February 2014
219
220
221 The "status: NOERROR" signals that everything is OK, and the "id" is
222 an integer used to match questions and answers. In the ANSWER
223 section, we find our answer. The AUTHORITY section holds the names
224 of the name servers that have information concerning the
225 "example.org" zone. Note that including this information is
226 optional.
227
228 If a resolver asks for "b.example.org TXT", it gets an answer that
229 this name does not exist:
230
231 ;; status: NXDOMAIN, id: 7042
232
233 ;; AUTHORITY SECTION:
234 example.org. SOA ( ... )
235
236 In this case, we do not get an ANSWER section, and the status is set
237 to NXDOMAIN. From this, the resolver concludes that "b.example.org"
238 does not exist. The AUTHORITY section holds the SOA record of
239 "example.org" that the resolver can use to cache the negative
240 response.
241
242 2.2. NODATA Responses
243
244 It is important to realize that NXDOMAIN is not the only type of
245 does-not-exist response. A name may exist, but the type you are
246 asking for may not. This occurrence of nonexistence is called a
247 NODATA response. Let us ask our name server for "a.example.org AAAA"
248 and look at the answer:
249
250 ;; status: NOERROR, id: 7944
251
252 ;; AUTHORITY SECTION:
253 example.org. SOA ( ... )
254
255 The status NOERROR shows that the "a.example.org" name exists, but
256 the reply does not contain an ANSWER section. This differentiates a
257 NODATA response from an NXDOMAIN response; the rest of the packet is
258 very similar. The resolver has to put these pieces of information
259 together and conclude that "a.example.org" exists, but it does not
260 have a "AAAA" record.
261
262
263
264
265
266
267
268
269
270
271
272 Gieben & Mekking Informational [Page 5]
273 RFC 7129 Authenticated Denial in DNS February 2014
274
275
276 3. Secure Denial of Existence
277
278 The above has to be translated to the security-aware world of DNSSEC.
279 But, there are a few principles DNSSEC brings to the table:
280
281 1. A name server is free to compute the answer and signature(s) on
282 the fly, but the protocol is written with a "first sign, then
283 load" attitude in mind. It is rather asymmetrical, but a lot of
284 the design in DNSSEC stems from fact that you need to accommodate
285 authenticated denial of existence. If the DNS did not have
286 NXDOMAIN, DNSSEC would be a lot simpler, but a lot less useful!
287
288 2. The DNS packet header is not signed. This means that a "status:
289 NXDOMAIN" cannot be trusted. In fact, the entire header may be
290 forged, including the AD bit (AD stands for Authentic Data; see
291 [RFC3655]), which may give some food for thought;
292
293 3. DNS wildcards and CNAME records complicate matters significantly.
294 See more about this later in Sections 5.3 and 5.4.
295
296 The first principle implies that all denial-of-existence answers need
297 to be precomputed, but it is impossible to precompute (all
298 conceivable) nonexistence answers.
299
300 A generic denial record that can be used in all denial-of-existence
301 proofs is not an option: such a record is susceptible to replay
302 attacks. When you are querying a name server for any record that
303 actually exists, a man in the middle could replay that generic denial
304 record that is unlimited in its scope, and it would be impossible to
305 tell whether the response was genuine or spoofed. In other words,
306 the generic record can be replayed to falsely deny _all_ possible
307 responses.
308
309 We could also use the QNAME in the answer and sign that, essentially
310 signing an NXDOMAIN response. While this approach could have worked
311 technically, it is incompatible with offline signing.
312
313 The way this has been solved is by introducing a record that defines
314 an interval between two existing names. Or, to put it another way,
315 it defines the holes (nonexisting names) in the zone. This record
316 can be signed beforehand and given to the resolver. Appendices A and
317 B describe online signing techniques that are compatible with this
318 scheme.
319
320 Given all these troubles, why didn't the designers of DNSSEC go
321 for the easy route and allow for online signing? Well, at that
322 time (pre 2000), online signing was not feasible with the then-
323 current hardware. Keep in mind that the larger servers get
324
325
326
327 Gieben & Mekking Informational [Page 6]
328 RFC 7129 Authenticated Denial in DNS February 2014
329
330
331 between 2000 and 6000 queries per second (qps), with peaks up to
332 20,000 qps or more. Scaling signature generation to these kind of
333 levels is always a challenge. Another issue was (and is) key
334 management. For online signing to work, _each_ authoritative name
335 server needs access to the private key(s). This is considered a
336 security risk. Hence, the protocol is required not to rely on
337 on-line signing.
338
339 The road to the current solution (NSEC/NSEC3) was long. It started
340 with the NXT (next) record. The NO (not existing) record was
341 introduced, but it never made it into an RFC. Later on, NXT was
342 superseded by the NSEC (next secure) record. From there, it went
343 through NSEC2/DNSNR to finally reach NSEC3 (Next SECure version 3) in
344 RFC 5155.
345
346 3.1. NXT
347
348 The first attempt to specify authenticated denial of existence was
349 NXT ([RFC2535]). Section 5.1 of RFC 2535 introduces the record:
350
351 The NXT resource record is used to securely indicate that RRs with
352 an owner name in a certain name interval do not exist in a zone
353 and to indicate what RR types are present for an existing name.
354
355 By specifying what you do have, you implicitly tell what you don't
356 have. NXT is superseded by NSEC. In the next section, we explain
357 how NSEC (and thus NXT) works.
358
359 3.2. NSEC
360
361 In [RFC3755], all the DNSSEC types were given new names: SIG was
362 renamed RRSIG, KEY became DNSKEY, and NXT was renamed NSEC, and a
363 minor issue was fixed in the process, namely the type bitmap was
364 redefined to allow more than 127 types to be listed ([RFC2535],
365 Section 5.2).
366
367 Just as NXT, NSEC is used to describe an interval between names: it
368 indirectly tells a resolver which names do not exist in a zone.
369
370 For this to work, we need our "example.org" zone to be sorted in
371 canonical order ([RFC4034], Section 6.1), and then create the NSECs.
372 We add three NSEC records, one for each name, and each one covers a
373 certain interval. The last NSEC record points back to the first as
374 required by RFC 4034 and depicted in Figure 2.
375
376 1. The first NSEC covers the interval between "example.org" and
377 "a.example.org";
378
379
380
381
382 Gieben & Mekking Informational [Page 7]
383 RFC 7129 Authenticated Denial in DNS February 2014
384
385
386 2. The second NSEC covers "a.example.org" to "d.example.org";
387
388 3. The third NSEC points back to "example.org" and covers
389 "d.example.org" to "example.org" (i.e., the end of the zone).
390
391 As we have defined the intervals and put those in resource records,
392 we now have something that can be signed.
393
394 example.org
395 **
396 +-- ** <--+
397 (1) / . . \ (3)
398 / . . \
399 | . . |
400 v . . |
401 ** (2) **
402 a.example.org ** ---------> ** d.example.org
403
404 Figure 2: The NSEC records of "example.org". The arrows represent
405 NSEC records, starting from the apex.
406
407 This signed zone is loaded into the name server. It looks like this:
408
409 example.org. SOA ( ... )
410 DNSKEY ( ... )
411 NS a.example.org.
412 NSEC a.example.org. NS SOA RRSIG NSEC DNSKEY
413 RRSIG(NS) ( ... )
414 RRSIG(SOA) ( ... )
415 RRSIG(NSEC) ( ... )
416 RRSIG(DNSKEY) ( ... )
417 a.example.org. A 192.0.2.1
418 TXT "a record"
419 NSEC d.example.org. A TXT RRSIG NSEC
420 RRSIG(A) ( ... )
421 RRSIG(TXT) ( ... )
422 RRSIG(NSEC) ( ... )
423 d.example.org. A 192.0.2.1
424 TXT "d record"
425 NSEC example.org. A TXT RRSIG NSEC
426 RRSIG(A) ( ... )
427 RRSIG(TXT) ( ... )
428 RRSIG(NSEC) ( ... )
429
430 Figure 3: The signed and sorted "example.org" zone with the added
431 NSEC records (and signatures). For brevity, the class is
432 not shown (defaults to IN) and the SOA, DNSKEY, and RRSIG
433 records are shortened.
434
435
436
437 Gieben & Mekking Informational [Page 8]
438 RFC 7129 Authenticated Denial in DNS February 2014
439
440
441 If a DNSSEC-aware resolver asks for "b.example.org", it gets back a
442 "status: NXDOMAIN" packet, which by itself is meaningless (remember
443 that the DNS packet header is not signed and thus can be forged). To
444 be able to securely detect that "b" does not exist, there must also
445 be a signed NSEC record that covers the name space where "b" lives.
446
447 The record:
448
449 a.example.org. NSEC d.example.org. A TXT RRSIG NSEC
450
451 does precisely that: "b" should come after "a", but the next owner
452 name is "d.example.org", so "b" does not exist.
453
454 Only by making that calculation is a resolver able to conclude that
455 the name "b" does not exist. If the signature of the NSEC record is
456 valid, "b" is proven not to exist. We have authenticated denial of
457 existence. A similar NSEC record needs to be included to deny
458 wildcard expansion, see Section 5.3.
459
460 Note that a man in the middle may still replay this NXDOMAIN response
461 when you're querying for, say, "c.example.org". But, it would not do
462 any harm since it is provable that this is the proper response to the
463 query.
464
465 3.3. NODATA Responses
466
467 NSEC records are also used in NODATA responses. In that case, we
468 need to look more closely at the type bitmap. The type bitmap in an
469 NSEC record tells which types are defined for a name. If we look at
470 the NSEC record of "a.example.org", we see the following types in the
471 bitmap: A, TXT, NSEC, and RRSIG. So, for the name "a", this
472 indicates we must have an A, TXT, NSEC, and RRSIG record in the zone.
473
474 With the type bitmap of the NSEC record, a resolver can establish
475 that a name is there, but the type is not. For example, if a
476 resolver asks for "a.example.org AAAA", the reply that comes back is:
477
478 ;; status: NOERROR, id: 44638
479
480 ;; AUTHORITY SECTION:
481 example.org. SOA ( ... )
482 example.org. RRSIG(SOA) ( ... )
483 a.example.org. NSEC d.example.org. A TXT RRSIG NSEC
484 a.example.org. RRSIG(NSEC) ( ... )
485
486
487
488
489
490
491
492 Gieben & Mekking Informational [Page 9]
493 RFC 7129 Authenticated Denial in DNS February 2014
494
495
496 The resolver should check the AUTHORITY section and conclude that:
497
498 (1) "a.example.org" exists (because of the NSEC with that owner
499 name); and
500
501 (2) the type (AAAA) does not exist as it is not listed in the type
502 bitmap.
503
504 The techniques used by NSEC form the basics of authenticated denial
505 of existence in DNSSEC.
506
507 3.4. Drawbacks of NSEC
508
509 There were two issues with NSEC (and NXT). The first is that it
510 allows for zone walking. NSEC records point from one name to
511 another; in our example: "example.org" points to "a.example.org",
512 which points to "d.example.org", which points back to "example.org".
513 So, we can reconstruct the entire "example.org" zone, thus defeating
514 attempts to administratively block zone transfers ([RFC2065],
515 Section 5.5).
516
517 The second issue is that when a large, delegation-centric ([RFC5155],
518 Section 1.1) zone deploys DNSSEC, every name in the zone gets an NSEC
519 plus RRSIG. So, this leads to a huge increase in the zone size (when
520 signed). This would in turn mean that operators of such zones who
521 are deploying DNSSEC face up-front costs. This could hinder DNSSEC
522 adoption.
523
524 These two issues eventually lead to NSEC3, which:
525
526 o Adds a way to garble the owner names thus thwarting zone walking;
527
528 o Makes it possible to skip names for the next owner name. This
529 feature is called Opt-Out (see Section 5.1). It means not all
530 names in your zone get an NSEC3 plus ditto signature, making it
531 possible to "grow into" your DNSSEC deployment.
532
533 Note that there are other ways to mitigate zone walking. RFC 4470
534 [RFC4470] prevents zone walking by introducing minimally covering
535 NSEC records. This technique is described in Appendix A.
536
537 Before we delve into NSEC3, let us first take a look at its
538 predecessors: NO, NSEC2, and DNSNR.
539
540
541
542
543
544
545
546
547 Gieben & Mekking Informational [Page 10]
548 RFC 7129 Authenticated Denial in DNS February 2014
549
550
551 4. Experimental and Deprecated Mechanisms: NO, NSEC2, and DNSNR
552
553 Long before NSEC was defined, the NO record was introduced. It was
554 the first record to use the idea of hashed owner names to fix the
555 issue of zone walking that was present with the NXT record. It also
556 fixed the type bitmap issue of the NXT record, but not in a space-
557 efficient way. At that time (around 2000), zone walking was not
558 considered important enough to warrant the new record. People were
559 also worried that DNSSEC deployment would be hindered by developing
560 an alternate means of denial of existence. Thus, the effort was
561 shelved and NXT remained.
562
563 When the new DNSSEC specification [RFC4034] was written, people were
564 still not convinced that zone walking was a problem that should be
565 solved. So, NSEC saw the light and inherited the two issues from
566 NXT.
567
568 Several years after, NSEC2 was introduced as a way to solve the two
569 issues of NSEC. The NSEC2 document [DNSEXT-NSEC2] contains the
570 following paragraph:
571
572 This document proposes an alternate scheme which hides owner names
573 while permitting authenticated denial of existence of non-existent
574 names. The scheme uses two new RR types: NSEC2 and EXIST.
575
576 When an authenticated denial-of-existence scheme starts to talk about
577 EXIST records, it is worth paying extra attention. The EXIST record
578 was defined as a record without RDATA that would be used to signal
579 the presence of a domain name. From [DNSEXT-NSEC2]:
580
581 In order to prove the nonexistence of a record that might be
582 covered by a wildcard, it is necessary to prove the existence of
583 its closest encloser. This record does that. Its owner is the
584 closest encloser. It has no RDATA. If there is another RR that
585 proves the existence of the closest encloser, this SHOULD be used
586 instead of an EXIST record.
587
588 The introduction of this record led to questions about what wildcards
589 actually mean (especially in the context of DNSSEC). It is probably
590 not a coincidence that "The Role of Wildcards in the Domain Name
591 System" [RFC4592] was standardized before NSEC3 was.
592
593 NSEC2 solved the zone-walking issue by hashing (with SHA1 and a salt)
594 the "next owner name" in the record, thereby making it useless for
595 zone walking. But, it did not have Opt-Out.
596
597 The DNSNR record was another attempt that used hashed names to foil
598 zone walking, and it also introduced the concept of opting out
599
600
601
602 Gieben & Mekking Informational [Page 11]
603 RFC 7129 Authenticated Denial in DNS February 2014
604
605
606 (called "Authoritative Only Flag"), which limited the use of DNSNR in
607 delegation-centric zones.
608
609 All of these proposals didn't make it, but they did provide valuable
610 insights. To summarize:
611
612 o The NO record introduced hashing, but this idea lingered in the
613 background for a long time;
614
615 o The NSEC2 record made it clear that wildcards were not completely
616 understood;
617
618 o The DNSNR record used a new flag field in the RDATA to signal Opt-
619 Out.
620
621 5. NSEC3
622
623 From the experience gained with NSEC2 and DNSNR, NSEC3 was forged.
624 It incorporates both Opt-Out and the hashing of names. NSEC3 solves
625 any issues people might have with NSEC, but it introduces some
626 additional complexity.
627
628 NSEC3 did not supersede NSEC; they are both defined for DNSSEC. So,
629 DNSSEC is blessed with two different means to perform authenticated
630 denial of existence: NSEC and NSEC3. In NSEC3, every name is hashed,
631 including the owner name. This means that the NSEC3 chain is sorted
632 in hash order, instead of canonical order. Because the owner names
633 are hashed, the next owner name for "example.org" is unlikely to be
634 "a.example.org". Because the next owner name is hashed, zone walking
635 becomes more difficult.
636
637 To make it even more difficult to retrieve the original names, the
638 hashing can be repeated several times, each time taking the previous
639 hash as input. To prevent the reuse of pre-generated hash values
640 between zones, a (per-zone) salt can also be added. In the NSEC3 for
641 "example.org", we have hashed the names thrice ([RFC5155], Section 5)
642 and used the salt "DEAD". Let's look at a typical NSEC3 record:
643
644 15bg9l6359f5ch23e34ddua6n1rihl9h.example.org. (
645 NSEC3 1 0 2 DEAD A6EDKB6V8VL5OL8JNQQLT74QMJ7HEB84
646 NS SOA RRSIG DNSKEY NSEC3PARAM )
647
648 On the first line, we see the hashed owner name:
649 "15bg9l6359f5ch23e34ddua6n1rihl9h.example.org"; this is the hashed
650 name of the fully qualified domain name (FQDN) "example.org" encoded
651 as Base32 [RFC4648]. Note that even though we hashed "example.org",
652 the zone's name is added to make it look like a domain name again.
653 In our zone, the basic format is "Base32(SHA1(FQDN)).example.org".
654
655
656
657 Gieben & Mekking Informational [Page 12]
658 RFC 7129 Authenticated Denial in DNS February 2014
659
660
661 The next hashed owner name "A6EDKB6V8VL5OL8JNQQLT74QMJ7HEB84" (line
662 2) is the hashed version of "d.example.org", represented as Base32.
663 Note that "d.example.org" is used as the next owner name because in
664 the hash ordering, its hash comes after the hash of the zone's apex.
665 Also, note that ".example.org" is not added to the next hashed owner
666 name, as this name always falls in the current zone.
667
668 The "1 0 2 DEAD" segment of the NSEC3 states:
669
670 o Hash Algorithm = 1 (SHA1 is the default; no other hash algorithms
671 are currently defined for use in NSEC3; see Section 3.1.1 of
672 [RFC5155]);
673
674 o Opt-Out = 0 (disabled; see Section 6 of [RFC5155]);
675
676 o Hash Iterations = 2 (this yields three iterations, as a zero value
677 is already one iteration; see Section 3.1.3 of [RFC5155]);
678
679 o Salt = "DEAD" (see Section 3.1.5 of [RFC5155].
680
681 At the end, we see the type bitmap, which is identical to NSEC's
682 bitmap, that lists the types present at the original owner name.
683 Note that the type NSEC3 is absent from the list in the example
684 above. This is due to the fact that the original owner name
685 ("example.org") does not have the NSEC3 type. It only exists for the
686 hashed name.
687
688 Names like "1.h.example.org" hash to one label in NSEC3 and
689 "1.h.example.org" becomes:
690 "117gercprcjgg8j04ev1ndrk8d1jt14k.example.org" when used as an owner
691 name. This is an important observation. By hashing the names, you
692 lose the depth of a zone -- hashing introduces a flat space of names,
693 as opposed to NSEC.
694
695 The name used above ("1.h.example.org") creates an empty non-
696 terminal. Empty non-terminals are domain names that have no RRs
697 associated with them and exist only because they have one or more
698 subdomains that do ([RFC5155], Section 1.3). The record:
699
700 1.h.example.org. TXT "1.h record"
701
702 creates two names:
703
704 1. "1.h.example.org" that has the type: TXT;
705
706 2. "h.example.org", which has no types. This is the empty non-
707 terminal.
708
709
710
711
712 Gieben & Mekking Informational [Page 13]
713 RFC 7129 Authenticated Denial in DNS February 2014
714
715
716 An empty non-terminal will get an NSEC3 record but not an NSEC
717 record. In Section 5.5, how the resolver uses these NSEC3 records to
718 validate the denial-of-existence proofs is shown.
719
720 Note that NSEC3 might not always be useful. For example, highly
721 structured zones, like the reverse zones ip6.arpa and in-addr.arpa,
722 can be walked even with NSEC3 due to their structure. Also, the
723 names in small, trivial zones can be easily guessed. In these cases,
724 it does not help to defend against zone walking, but it does add the
725 computational load on authoritative servers and validators.
726
727 5.1. Opt-Out
728
729 Hashing mitigates the zone-walking issue of NSEC. The other issue,
730 the high costs of securing a delegation to an insecure zone, is
731 tackled with Opt-Out. When using Opt-Out, names that are an insecure
732 delegation (and empty non-terminals that are only derived from
733 insecure delegations) don't require an NSEC3 record. For each
734 insecure delegation, the zone size can be decreased (compared with a
735 fully signed zone without using Opt-Out) with at least two records:
736 one NSEC3 record and one corresponding RRSIG record. If the insecure
737 delegation would introduce empty non-terminals, even more records can
738 be omitted from the zone.
739
740 Opt-Out NSEC3 records are not able to prove or deny the existence of
741 the insecure delegations. In other words, those delegations do not
742 benefit from the cryptographic security that DNSSEC provides.
743
744 A recently discovered corner case (see RFC Errata ID 3441 [Err3441])
745 shows that not only those delegations remain insecure but also the
746 empty non-terminal space that is derived from those delegations.
747
748 Because the names in this empty non-terminal space do exist according
749 to the definition in [RFC4592], the server should respond to queries
750 for these names with a NODATA response. However, the validator
751 requires an NSEC3 record proving the NODATA response ([RFC5155],
752 Section 8.5):
753
754 The validator MUST verify that an NSEC3 RR that matches QNAME is
755 present and that both the QTYPE and the CNAME type are not set in
756 its Type Bit Maps field.
757
758 A way to resolve this contradiction in the specification is to always
759 provide empty non-terminals with an NSEC3 record, even if it is only
760 derived from an insecure delegation.
761
762
763
764
765
766
767 Gieben & Mekking Informational [Page 14]
768 RFC 7129 Authenticated Denial in DNS February 2014
769
770
771 5.2. Loading an NSEC3 Zone
772
773 Whenever an authoritative server receives a query for a non-existing
774 record, it has to hash the incoming query name to determine into
775 which interval between two existing hashes it falls. To do that, it
776 needs to know the zone's specific NSEC3 parameters (hash iterations
777 and salt).
778
779 One way to learn them is to scan the zone during loading for NSEC3
780 records and glean the NSEC3 parameters from them. However, it would
781 need to make sure that there is at least one complete set of NSEC3
782 records for the zone using the same parameters. Therefore, it would
783 need to inspect all NSEC3 records.
784
785 A more graceful solution was designed. The solution was to create a
786 new record, NSEC3PARAM, which must be placed at the apex of the zone.
787 Its role is to provide a fixed place where an authoritative name
788 server can directly see the NSEC3 parameters used, and by putting it
789 in the zone, it allows for easy transfer to the secondaries.
790
791 5.3. Wildcards in the DNS
792
793 So far, we have only talked about denial of existence in negative
794 responses. However, denial of existence may also occur in positive
795 responses, i.e., where the ANSWER section of the response is not
796 empty. This can happen because of wildcards.
797
798 Wildcards have been part of the DNS since the first DNS RFCs. They
799 allow to define all names for a certain type in one go. In our
800 "example.org" zone, we could, for instance, add a wildcard record:
801
802 *.example.org. TXT "wildcard record"
803
804 For completeness, our (unsigned) zone now looks like this:
805
806 example.org. SOA ( ... )
807 example.org. NS a.example.org.
808 *.example.org. TXT "wildcard record"
809 a.example.org. A 192.0.2.1
810 TXT "a record"
811 d.example.org. A 192.0.2.1
812 TXT "d record"
813
814 Figure 4: The example.org Zone with a Wildcard Record
815
816
817
818
819
820
821
822 Gieben & Mekking Informational [Page 15]
823 RFC 7129 Authenticated Denial in DNS February 2014
824
825
826 If a resolver asks for "z.example.org TXT", the name server will
827 respond with an expanded wildcard instead of an NXDOMAIN:
828
829 ;; status: NOERROR, id: 13658
830
831 ;; ANSWER SECTION:
832 z.example.org. TXT "wildcard record"
833
834 Note, however, that the resolver cannot detect that this answer came
835 from a wildcard. It just sees the answer as is. How will this
836 answer look with DNSSEC?
837
838 ;; status: NOERROR, id: 51790
839
840 ;; ANSWER SECTION:
841 z.example.org. TXT "wildcard record"
842 z.example.org. RRSIG(TXT) ( ... )
843
844 ;; AUTHORITY SECTION:
845 d.example.org. NSEC example.org. A TXT RRSIG NSEC
846 d.example.org. RRSIG(NSEC) ( ... )
847
848 Figure 5: A Response with an Expanded Wildcard and DNSSEC
849
850 The RRSIG of the "z.example.org" TXT record indicates there is a
851 wildcard configured. The RDATA of the signature lists a label count,
852 [RFC4034], Section 3.1.3., of two (not visible in the figure above),
853 but the owner name of the signature has three labels. This mismatch
854 indicates there is a wildcard "*.example.org" configured.
855
856 An astute reader may notice that it appears as if a
857 "z.example.org" RRSIG(TXT) is created out of thin air. This is
858 not the case. The signature for "z.example.org" does not exist.
859 The signature you are seeing is the one for "*.example.org", which
860 does exist; only the owner name is switched to "z.example.org".
861 So, even with wildcards, no signatures have to be created on the
862 fly.
863
864 The DNSSEC standard mandates that an NSEC (or NSEC3) is included in
865 such responses. If it wasn't, an attacker could mount a replay
866 attack and poison the cache with false data. Suppose that the
867 resolver has asked for "a.example.org TXT". An attacker could modify
868 the packet in such way that it looks like the response was generated
869 through wildcard expansion, even though a record exists for
870 "a.example.org TXT".
871
872
873
874
875
876
877 Gieben & Mekking Informational [Page 16]
878 RFC 7129 Authenticated Denial in DNS February 2014
879
880
881 The tweaking simply consists of adjusting the ANSWER section to:
882
883 ;; status: NOERROR, id: 31827
884
885 ;; ANSWER SECTION:
886 a.example.org. TXT "wildcard record"
887 a.example.org. RRSIG(TXT) ( ... )
888
889 Figure 6: A Forged Response without the Expanded Wildcard
890
891 Note the subtle difference from Figure 5 in the owner name. In this
892 response, we see a "a.example.org TXT" record for which a record with
893 different RDATA (see Figure 4) exists in the zone.
894
895 That would be a perfectly valid answer if we would not require the
896 inclusion of an NSEC or NSEC3 record in the wildcard answer response.
897 The resolver believes that "a.example.org TXT" is a wildcard record,
898 and the real record is obscured. This is bad and defeats all the
899 security DNSSEC can deliver. Because of this, the NSEC or NSEC3 must
900 be present.
901
902 Another way of putting this is that DNSSEC is there to ensure the
903 name server has followed the steps as outlined in [RFC1034],
904 Section 4.3.2 for looking up names in the zone. It explicitly lists
905 wildcard lookup as one of these steps (3c), so with DNSSEC this must
906 be communicated to the resolver: hence, the NSEC or NSEC3 record.
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932 Gieben & Mekking Informational [Page 17]
933 RFC 7129 Authenticated Denial in DNS February 2014
934
935
936 5.4. CNAME Records
937
938 So far, the maximum number of NSEC records a response will have is
939 two: one for the denial of existence and another for the wildcard.
940 We say maximum because sometimes a single NSEC can prove both. With
941 NSEC3, this is three (as to why, we will explain in the next
942 section).
943
944 When we take CNAME wildcard records into account, we can have more
945 NSEC or NSEC3 records. For every wildcard expansion, we need to
946 prove that the expansion was allowed. Let's add some CNAME wildcard
947 records to our zone:
948
949 example.org. SOA ( ... )
950 example.org. NS a.example.org.
951 *.example.org. TXT "wildcard record"
952 a.example.org. A 192.0.2.1
953 TXT "a record"
954 *.a.example.org. CNAME w.b
955 *.b.example.org. CNAME w.c
956 *.c.example.org. A 192.0.2.1
957 d.example.org. A 192.0.2.1
958 TXT "d record"
959 w.example.org. CNAME w.a
960
961 Figure 7: A Wildcard CNAME Chain Added to the "example.org" Zone
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987 Gieben & Mekking Informational [Page 18]
988 RFC 7129 Authenticated Denial in DNS February 2014
989
990
991 A query for "w.example.org A" will result in the following response:
992
993 ;; status: NOERROR, id: 4307
994
995 ;; ANSWER SECTION:
996 w.example.org. CNAME w.a.example.org.
997 w.example.org. RRSIG(CNAME) ( ... )
998 w.a.example.org. CNAME w.b.example.org.
999 w.a.example.org. RRSIG(CNAME) ( ... )
1000 w.b.example.org. CNAME w.c.example.org.
1001 w.b.example.org. RRSIG(CNAME) ( ... )
1002 w.c.example.org. A 192.0.2.1
1003 w.c.example.org. RRSIG(A) ( ... )
1004
1005 ;; AUTHORITY SECTION:
1006 *.a.example.org. NSEC *.b.example.org. CNAME RRSIG NSEC
1007 *.a.example.org. RRSIG(NSEC) ( ... )
1008 *.b.example.org. NSEC *.c.example.org. CNAME RRSIG NSEC
1009 *.b.example.org. RRSIG(NSEC) ( ... )
1010 *.c.example.org. NSEC d.example.org. A RRSIG NSEC
1011 *.c.example.org. RRSIG(NSEC) ( ... )
1012
1013 The NSEC record "*.a.example.org" proves that wildcard expansion to
1014 "w.a.example.org" was appropriate: "w.a." falls in the gap "*.a" to
1015 "*.b". Similarly, the NSEC record "*.b.example.org" proves that
1016 there was no direct match for "w.b.example.org" and "*.c.example.org"
1017 denies the direct match for "w.c.example.org".
1018
1019 DNAME records and wildcard names should not be used as reiterated in
1020 [RFC6672], Section 3.3.
1021
1022 5.5. The Closest Encloser NSEC3 Record
1023
1024 We can have one or more NSEC3 records that deny the existence of the
1025 requested name and one NSEC3 record that denies wildcard synthesis.
1026 What do we miss?
1027
1028 The short answer is that due to the hashing in NSEC3, you lose the
1029 depth of your zone and everything is hashed into a flat plane. To
1030 make up for this loss of information, you need an extra record.
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042 Gieben & Mekking Informational [Page 19]
1043 RFC 7129 Authenticated Denial in DNS February 2014
1044
1045
1046 To understand NSEC3, we will need two definitions:
1047
1048 Closest encloser: Introduced in [RFC4592] as:
1049
1050 The closest encloser is the node in the zone's tree of existing
1051 domain names that has the most labels matching the query name
1052 (consecutively, counting from the root label downward).
1053
1054 In our example, if the query name is "x.2.example.org", then
1055 "example.org" is the "closest encloser";
1056
1057 Next closer name: Introduced in [RFC5155], this is the closest
1058 encloser with one more label added to the left. So, if
1059 "example.org" is the closest encloser for the query name
1060 "x.2.example.org", "2.example.org" is the "next closer name".
1061
1062 An NSEC3 "closest encloser proof" consists of:
1063
1064 1. An NSEC3 record that *matches* the "closest encloser". This
1065 means the unhashed owner name of the record is the closest
1066 encloser. This bit of information tells a resolver: "The name
1067 you are asking for does not exist; the closest I have is this".
1068
1069 2. An NSEC3 record that *covers* the "next closer name". This means
1070 it defines an interval in which the "next closer name" falls.
1071 This tells the resolver: "The next closer name falls in this
1072 interval, and therefore the name in your question does not exist.
1073 In fact, the closest encloser is indeed the closest I have".
1074
1075 These two records already deny the existence of the requested name,
1076 so we do not need an NSEC3 record that covers the actual queried
1077 name. By denying the existence of the next closer name, you also
1078 deny the existence of the queried name.
1079
1080 Note that with NSEC, the existence of all empty non-terminals between
1081 the two names are denied, hence it implicitly contains the closest
1082 encloser.
1083
1084 For a given query name, there is one (and only one) place where
1085 wildcard expansion is possible. This is the "source of synthesis"
1086 and is defined ([RFC4592], Sections 2.1.1 and 3.3.1) as:
1087
1088 <asterisk label>.<closest encloser>
1089
1090 In other words, to deny wildcard synthesis, the resolver needs to
1091 know the hash of the source of synthesis. Since it does not know
1092 beforehand what the closest encloser of the query name is, it must be
1093 provided in the answer.
1094
1095
1096
1097 Gieben & Mekking Informational [Page 20]
1098 RFC 7129 Authenticated Denial in DNS February 2014
1099
1100
1101 Take the following example. We have a zone with two TXT records to
1102 it. The records added are "1.h.example.org" and "3.3.example.org".
1103 It is signed with NSEC3, resulting in the following unsigned zone:
1104
1105 example.org. SOA ( ... )
1106 example.org. NS a.example.org.
1107 1.h.example.org. TXT "1.h record"
1108 3.3.example.org. TXT "3.3 record"
1109
1110 Figure 8: The TXT records in example.org. These records create two
1111 empty non-terminals: h.example.org and 3.example.org.
1112
1113 The resolver asks the following: "x.2.example.org TXT". This leads
1114 to an NXDOMAIN response from the server, which contains three NSEC3
1115 records. A list of hashed owner names can be found in Appendix C.
1116 Also, see Figure 9; the numbers in that figure correspond with the
1117 following NSEC3 records:
1118
1119 15bg9l6359f5ch23e34ddua6n1rihl9h.example.org. (
1120 NSEC3 1 0 2 DEAD 1AVVQN74SG75UKFVF25DGCETHGQ638EK NS SOA RRSIG
1121 DNSKEY NSEC3PARAM )
1122
1123 1avvqn74sg75ukfvf25dgcethgq638ek.example.org. (
1124 NSEC3 1 0 2 DEAD 75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ )
1125
1126 75b9id679qqov6ldfhd8ocshsssb6jvq.example.org. (
1127 NSEC3 1 0 2 DEAD 8555T7QEGAU7PJTKSNBCHG4TD2M0JNPJ TXT RRSIG )
1128
1129 If we would follow the NSEC approach, the resolver is only interested
1130 in one thing. Does the hash of "x.2.example.org" fall in any of the
1131 intervals of the NSEC3 records it got?
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152 Gieben & Mekking Informational [Page 21]
1153 RFC 7129 Authenticated Denial in DNS February 2014
1154
1155
1156 example.org
1157 **
1158 +-- ** . . . . . . . . . . .
1159 (1) / . ^ . .
1160 / . | . .
1161 | . | . .
1162 v . | . .
1163 ** | (2) ** ++
1164 h.example.org ** ----+----> ** 3.example.org ++ 2.example.org
1165 . / . | .
1166 . / (5) . | (3) .
1167 . / . | .
1168 . / . v .
1169 1.h.example.org ** ** ++
1170 ** <--------- ** 3.3.example.org ++ x.2.example.org
1171 (4)
1172
1173 Figure 9: "x.2.example.org" does not exist. The five arrows
1174 represent the NSEC3 records; the ones numbered (1), (2),
1175 and (3) are the NSEC3s returned in our answer.
1176 "2.example.org" is covered by (3) and "x.2.example.org" is
1177 covered by (4).
1178
1179 The hash of "x.2.example.org" is "ndtu6dste50pr4a1f2qvr1v31g00i2i1".
1180 Checking this hash on the first NSEC3 yields that it does not fall in
1181 between the interval: "15bg9l6359f5ch23e34ddua6n1rihl9h" to
1182 "1avvqn74sg75ukfvf25dgcethgq638ek". For the second NSEC3, the answer
1183 is also negative: the hash sorts outside the interval described by
1184 "1avvqn74sg75ukfvf25dgcethgq638ek" and
1185 "75b9id679qqov6ldfhd8ocshsssb6jvq". And, the third NSEC3, with
1186 interval "75b9id679qqov6ldfhd8ocshsssb6jvq" to
1187 "8555t7qegau7pjtksnbchg4td2m0jnpj" also isn't of any help.
1188
1189 What is a resolver to do? It has been given the maximum amount of
1190 NSEC3s and they all seem useless.
1191
1192 So, this is where the closest encloser proof comes into play. And,
1193 for the proof to work, the resolver needs to know what the closest
1194 encloser is. There must be an existing ancestor in the zone: a name
1195 must exist that is shorter than the query name. The resolver keeps
1196 hashing increasingly shorter names from the query name until an owner
1197 name of an NSEC3 matches. This owner name is the closest encloser.
1198
1199 When the resolver has found the closest encloser, the next step is to
1200 construct the next closer name. This is the closest encloser with
1201 the last chopped label from the query name prepended to it: "<last
1202 chopped label>.<closest encloser>". The hash of this name should be
1203 covered by the interval set in any of the NSEC3 records.
1204
1205
1206
1207 Gieben & Mekking Informational [Page 22]
1208 RFC 7129 Authenticated Denial in DNS February 2014
1209
1210
1211 Then, the resolver needs to check the presence of a wildcard. It
1212 creates the wildcard name by prepending the asterisk label to the
1213 closest encloser, "*.<closest encloser>", and uses the hash of that.
1214
1215 Going back to our example, the resolver must first detect the NSEC3
1216 that matches the closest encloser. It does this by chopping up the
1217 query name, hashing each instance (with the same number of iterations
1218 and hash as the zone it is querying), and comparing that to the
1219 answers given. So, it has the following hashes to work with:
1220
1221 x.2.example.org: "ndtu6dste50pr4a1f2qvr1v31g00i2i1", last chopped
1222 label: "<empty>";
1223
1224 2.example.org: "7t70drg4ekc28v93q7gnbleopa7vlp6q", last chopped
1225 label: "x";
1226
1227 example.org: "15bg9l6359f5ch23e34ddua6n1rihl9h", last chopped label:
1228 "2".
1229
1230 Of these hashes, only one matches the owner name of one of the NSEC3
1231 records: "15bg9l6359f5ch23e34ddua6n1rihl9h". This must be the
1232 closest encloser (unhashed: "example.org"). That's the main purpose
1233 of that NSEC3 record: tell the resolver what the closest encloser is.
1234
1235 When using Opt-Out, it is possible that the actual closest encloser
1236 to the QNAME does not have an NSEC3 record. If so, we will have to
1237 do with the closest provable encloser, which is the closest enclosing
1238 authoritative name that does have an NSEC3 record. In the worst
1239 case, this is the NSEC3 record corresponding to the apex; this name
1240 must always have an NSEC3 record.
1241
1242 With the closest (provable) encloser, the resolver constructs the
1243 next closer, which in this case is: "2.example.org"; "2" is the last
1244 label chopped when "example.org" is the closest encloser. The hash
1245 of this name should be covered in any of the other NSEC3s. And, it
1246 is -- "7t70drg4ekc28v93q7gnbleopa7vlp6q" falls in the interval set by
1247 "75b9id679qqov6ldfhd8ocshsssb6jvq" and
1248 "8555t7qegau7pjtksnbchg4td2m0jnpj" (this is our second NSEC3).
1249
1250 So, what does the resolver learn from this?
1251
1252 o "example.org" exists;
1253
1254 o "2.example.org" does not exist.
1255
1256 And, if "2.example.org" does not exist, there is also no direct match
1257 for "x.2.example.org". The last step is to deny the existence of the
1258 source of synthesis to prove that no wildcard expansion was possible.
1259
1260
1261
1262 Gieben & Mekking Informational [Page 23]
1263 RFC 7129 Authenticated Denial in DNS February 2014
1264
1265
1266 The resolver hashes "*.example.org" to
1267 "22670trplhsr72pqqmedltg1kdqeolb7" and checks that it is covered. In
1268 this case, by the last NSEC3 (see Figure 9), the hash falls in the
1269 interval set by "1avvqn74sg75ukfvf25dgcethgq638ek" and
1270 "75b9id679qqov6ldfhd8ocshsssb6jvq". This means there is no wildcard
1271 record directly below the closest encloser, and "x.2.example.org"
1272 definitely does not exist.
1273
1274 When we have validated the signatures, we have reached our goal:
1275 authenticated denial of existence.
1276
1277 5.6. Three to Tango
1278
1279 One extra NSEC3 record plus an additional signature may seem like a
1280 lot just to deny the existence of the wildcard record, but we cannot
1281 leave it out. If the standard would not mandate the closest encloser
1282 NSEC3 record but instead required two NSEC3 records -- one to deny
1283 the query name and one to deny the wildcard record -- an attacker
1284 could fool the resolver that the source of synthesis does not exist,
1285 while it in fact does.
1286
1287 Suppose the wildcard record does exist, so our unsigned zone looks
1288 like this:
1289
1290 example.org. SOA ( ... )
1291 example.org. NS a.example.org.
1292 *.example.org. TXT "wildcard record"
1293 1.h.example.org. TXT "1.h record"
1294 3.3.example.org. TXT "3.3 record"
1295
1296 The query "x.2.example.org TXT" should now be answered with:
1297
1298 x.2.example.org. TXT "wildcard record"
1299
1300 An attacker can deny this wildcard expansion by calculating the hash
1301 for the wildcard name "*.2.example.org" and searching for an NSEC3
1302 record that covers that hash. The hash of "*.2.example.org" is
1303 "fbq73bfkjlrkdoqs27k5qf81aqqd7hho". Looking through the NSEC3
1304 records in our zone, we see that the NSEC3 record of "3.3" covers
1305 this hash:
1306
1307 8555t7qegau7pjtksnbchg4td2m0jnpj.example.org. (
1308 NSEC3 1 0 2 DEAD 15BG9L6359F5CH23E34DDUA6N1RIHL9H TXT RRSIG )
1309
1310 This record also covers the query name "x.2.example.org"
1311 ("ndtu6dste50pr4a1f2qvr1v31g00i2i1").
1312
1313
1314
1315
1316
1317 Gieben & Mekking Informational [Page 24]
1318 RFC 7129 Authenticated Denial in DNS February 2014
1319
1320
1321 Now an attacker adds this NSEC3 record to the AUTHORITY section of
1322 the reply to deny both "x.2.example.org" and any wildcard expansion.
1323 The net result is that the resolver determines that "x.2.example.org"
1324 does not exist, while in fact it should have been synthesized via
1325 wildcard expansion. With the NSEC3 matching the closest encloser
1326 "example.org", the resolver can be sure that the wildcard expansion
1327 should occur at "*.example.org" and nowhere else.
1328
1329 Coming back to the original question: Why do we need up to three
1330 NSEC3 records to deny a requested name? The resolver needs to be
1331 explicitly told what the "closest encloser" is, and this takes up a
1332 full NSEC3 record. Then, the next closer name needs to be covered in
1333 an NSEC3 record. Finally, an NSEC3 must say something about whether
1334 wildcard expansion was possible. That makes three to tango.
1335
1336 6. Security Considerations
1337
1338 DNSSEC does not protect against denial-of-service attacks, nor does
1339 it provide confidentiality. For more general security considerations
1340 related to DNSSEC, please see [RFC4033], [RFC4034], [RFC4035], and
1341 [RFC5155].
1342
1343 These RFCs are concise about why certain design choices have been
1344 made in the area of authenticated denial of existence.
1345 Implementations that do not correctly handle this aspect of DNSSEC
1346 create a severe hole in the security DNSSEC adds. This is
1347 specifically troublesome for secure delegations. If an attacker is
1348 able to deny the existence of a Delegation Signer (DS) record, the
1349 resolver cannot establish a chain of trust, and the resolver has to
1350 fall back to insecure DNS for the remainder of the query resolution.
1351
1352 This document aims to fill this "documentation gap" and provide
1353 would-be implementors and other interested parties with enough
1354 background knowledge to better understand authenticated denial of
1355 existence.
1356
1357 7. Acknowledgments
1358
1359 This document would not be possible without the help of Ed Lewis, Roy
1360 Arends, Wouter Wijngaards, Olaf Kolkman, Carsten Strotmann, Jan-Piet
1361 Mens, Peter van Dijk, Marco Davids, Esther Makaay, Antoin Verschuren,
1362 Lukas Wunner, Joe Abley, Ralf Weber, Geoff Huston, Dave Lawrence,
1363 Tony Finch, and Mark Andrews. Also valuable was the source code of
1364 Unbound ("validator/val_nsec3.c") [Unbound].
1365
1366 Extensive feedback for early versions of this document was received
1367 from Karst Koymans.
1368
1369
1370
1371
1372 Gieben & Mekking Informational [Page 25]
1373 RFC 7129 Authenticated Denial in DNS February 2014
1374
1375
1376 8. References
1377
1378 8.1. Normative References
1379
1380 [RFC1034] Mockapetris, P., "Domain names - concepts and facilities",
1381 STD 13, RFC 1034, November 1987.
1382
1383 [RFC2065] Eastlake, D. and C. Kaufman, "Domain Name System Security
1384 Extensions", RFC 2065, January 1997.
1385
1386 [RFC2308] Andrews, M., "Negative Caching of DNS Queries (DNS
1387 NCACHE)", RFC 2308, March 1998.
1388
1389 [RFC4033] Arends, R., Austein, R., Larson, M., Massey, D., and S.
1390 Rose, "DNS Security Introduction and Requirements", RFC
1391 4033, March 2005.
1392
1393 [RFC4034] Arends, R., Austein, R., Larson, M., Massey, D., and S.
1394 Rose, "Resource Records for the DNS Security Extensions",
1395 RFC 4034, March 2005.
1396
1397 [RFC4035] Arends, R., Austein, R., Larson, M., Massey, D., and S.
1398 Rose, "Protocol Modifications for the DNS Security
1399 Extensions", RFC 4035, March 2005.
1400
1401 [RFC4592] Lewis, E., "The Role of Wildcards in the Domain Name
1402 System", RFC 4592, July 2006.
1403
1404 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data
1405 Encodings", RFC 4648, October 2006.
1406
1407 [RFC5155] Laurie, B., Sisson, G., Arends, R., and D. Blacka, "DNS
1408 Security (DNSSEC) Hashed Authenticated Denial of
1409 Existence", RFC 5155, March 2008.
1410
1411 [RFC6672] Rose, S. and W. Wijngaards, "DNAME Redirection in the
1412 DNS", RFC 6672, June 2012.
1413
1414 8.2. Informative References
1415
1416 [DNSEXT-NSEC2]
1417 Laurie, B., "DNSSEC NSEC2 Owner and RDATA Format", Work in
1418 Progress, October 2004.
1419
1420 [DNSEXT] Josefsson, S., "Authenticating denial of existence in DNS
1421 with minimum disclosure", Work in Progress, November 2000.
1422
1423
1424
1425
1426
1427 Gieben & Mekking Informational [Page 26]
1428 RFC 7129 Authenticated Denial in DNS February 2014
1429
1430
1431 [DNSNR-RR] Arends, R., "DNSSEC Non-Repudiation Resource Record", Work
1432 in Progress, June 2004.
1433
1434 [Err3441] RFC Errata, Errata ID 3441, RFC 5155,
1435 <http://www.rfc-editor.org>.
1436
1437 [RFC2535] Eastlake, D., "Domain Name System Security Extensions",
1438 RFC 2535, March 1999.
1439
1440 [RFC3655] Wellington, B. and O. Gudmundsson, "Redefinition of DNS
1441 Authenticated Data (AD) bit", RFC 3655, November 2003.
1442
1443 [RFC3755] Weiler, S., "Legacy Resolver Compatibility for Delegation
1444 Signer (DS)", RFC 3755, May 2004.
1445
1446 [RFC4470] Weiler, S. and J. Ihren, "Minimally Covering NSEC Records
1447 and DNSSEC On-line Signing", RFC 4470, April 2006.
1448
1449 [RFC4956] Arends, R., Kosters, M., and D. Blacka, "DNS Security
1450 (DNSSEC) Opt-In", RFC 4956, July 2007.
1451
1452 [Unbound] NLnet Labs, "Unbound: a validating, recursive, and caching
1453 DNS resolver", 2006, <http://unbound.net>.
1454
1455 [phreebird]
1456 Kaminsky, D., "Phreebird: a DNSSEC proxy", January 2011,
1457 <http://dankaminsky.com/phreebird/>.
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482 Gieben & Mekking Informational [Page 27]
1483 RFC 7129 Authenticated Denial in DNS February 2014
1484
1485
1486 Appendix A. Online Signing: Minimally Covering NSEC Records
1487
1488 An NSEC record lists the next existing name in a zone and thus makes
1489 it trivial to retrieve all the names from the zone. This can also be
1490 done with NSEC3, but an adversary will then retrieve all the hashed
1491 names. With DNSSEC online signing, zone walking can be prevented by
1492 faking the next owner name.
1493
1494 To prevent retrieval of the next owner name with NSEC, a different,
1495 non-existing (according to the existence rules in [RFC4592],
1496 Section 2.2) name is used. However, not just any name can be used
1497 because a validator may make assumptions about the size of the span
1498 the NSEC record covers. The span must be large enough to cover the
1499 QNAME but not too large that it covers existing names.
1500
1501 [RFC4470] introduces a scheme for generating minimally covering NSEC
1502 records. These records use a next owner name that is lexically
1503 closer to the NSEC owner name than the actual next owner name,
1504 ensuring that no existing names are covered. The next owner name can
1505 be derived from the QNAME with the use of so-called epsilon
1506 functions.
1507
1508 For example, to deny the existence of "b.example.org" in the zone
1509 from Section 3.2, the following NSEC record could have been
1510 generated:
1511
1512 a.example.org. NSEC c.example.org. RRSIG NSEC
1513
1514 This record also proves that "b.example.org" also does not exist, but
1515 an adversary _cannot_ use the next owner name in a zone-walking
1516 attack. Note the type bitmap only has the RRSIG and NSEC set because
1517 [RFC4470] states:
1518
1519 The generated NSEC record's type bitmap MUST have the RRSIG and
1520 NSEC bits set and SHOULD NOT have any other bits set.
1521
1522 This is because the NSEC records may appear at names that did not
1523 exist before the zone was signed. In this case, however,
1524 "a.example.org" exists with other RR types, and we could have also
1525 set the A and TXT types in the bitmap.
1526
1527 Because DNS ordering is very strict, the span should be shortened to
1528 a minimum. In order to do so, the last character in the leftmost
1529 label of the NSEC owner name needs to be decremented, and the label
1530 must be filled with octets of value 255 until the label length
1531 reaches the maximum of 63 octets. The next owner name is the QNAME
1532 with a leading label with a single null octet added. This gives the
1533 following minimally covering record for "b.example.org":
1534
1535
1536
1537 Gieben & Mekking Informational [Page 28]
1538 RFC 7129 Authenticated Denial in DNS February 2014
1539
1540
1541 a\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255
1542 \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255
1543 \255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255\255
1544 \255\255\255\255\255\255\255\255\255\255\255.example.org. (
1545 NSEC \000.b.example.org. RRSIG NSEC )
1546
1547 Appendix B. Online Signing: NSEC3 White Lies
1548
1549 The same principle of minimally covering spans can be applied to
1550 NSEC3 records. This mechanism has been dubbed "NSEC3 White Lies"
1551 when it was implemented in Phreebird [phreebird]. Here, the NSEC3
1552 owner name is the hash of the QNAME minus one, and the next owner
1553 name is the hash of the QNAME plus one.
1554
1555 The following NSEC3 white lie denies "b.example.org" (recall that
1556 this hashes to "iuu8l5lmt76jeltp0bir3tmg4u3uu8e7"):
1557
1558 iuu8l5lmt76jeltp0bir3tmg4u3uu8e6.example.org. (
1559 NSEC3 1 0 2 DEAD IUU815LMT76JELTP0BIR3TMG4U3UU8E8 )
1560
1561 The type bitmap is empty in this case. If the hash of
1562 "b.example.org" - 1 is a collision with an existing name, the bitmap
1563 should have been filled with the RR types that exist at that name.
1564 This record actually denies the existence of the next closer name
1565 (which is conveniently "b.example.org"). Of course, the NSEC3
1566 records to match the closest encloser and the one to deny the
1567 wildcard are still required. These can be generated too:
1568
1569 # Matching `example.org`: `15bg9l6359f5ch23e34ddua6n1rihl9h`
1570 15bg9l6359f5ch23e34ddua6n1rihl9h.example.org. (
1571 NSEC3 1 0 2 DEAD 15BG9L6359F5CH23E34DDUA6N1RIHL9I NS SOA RRSIG
1572 DNSKEY NSEC3PARAM )
1573
1574 # Covering `*.example.org`: `22670trplhsr72pqqmedltg1kdqeolb7`
1575 22670trplhsr72pqqmedltg1kdqeolb6.example.org.(
1576 NSEC3 1 0 2 DEAD 22670TRPLHSR72PQQMEDLTG1KDQEOLB8 )
1577
1578 Appendix C. List of Hashed Owner Names
1579
1580 The following owner names are used in this document. The origin for
1581 these names is "example.org".
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592 Gieben & Mekking Informational [Page 29]
1593 RFC 7129 Authenticated Denial in DNS February 2014
1594
1595
1596 +----------------+-------------------------------------+
1597 | Original Name | Hashed Name |
1598 +----------------+-------------------------------------+
1599 | "a" | "04sknapca5al7qos3km2l9tl3p5okq4c" |
1600 | "1.h" | "117gercprcjgg8j04ev1ndrk8d1jt14k" |
1601 | "@" | "15bg9l6359f5ch23e34ddua6n1rihl9h" |
1602 | "h" | "1avvqn74sg75ukfvf25dgcethgq638ek" |
1603 | "*" | "22670trplhsr72pqqmedltg1kdqeolb7" |
1604 | "3" | "75b9id679qqov6ldfhd8ocshsssb6jvq" |
1605 | "2" | "7t70drg4ekc28v93q7gnbleopa7vlp6q" |
1606 | "3.3" | "8555t7qegau7pjtksnbchg4td2m0jnpj" |
1607 | "d" | "a6edkb6v8vl5ol8jnqqlt74qmj7heb84" |
1608 | "*.2" | "fbq73bfkjlrkdoqs27k5qf81aqqd7hho" |
1609 | "b" | "iuu8l5lmt76jeltp0bir3tmg4u3uu8e7" |
1610 | "x.2" | "ndtu6dste50pr4a1f2qvr1v31g00i2i1" |
1611 +----------------+-------------------------------------+
1612
1613 Table 1: Hashed Owner Names for "example.org" in Hash Order
1614
1615 Authors' Addresses
1616
1617 R. (Miek) Gieben
1618 Google
1619
1620 EMail: miek@google.com
1621
1622
1623 W. (Matthijs) Mekking
1624 NLnet Labs
1625 Science Park 400
1626 Amsterdam 1098 XH
1627 NL
1628
1629 EMail: matthijs@nlnetlabs.nl
1630 URI: http://www.nlnetlabs.nl/
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647 Gieben & Mekking Informational [Page 30]
1648
The IETF is responsible for the creation and maintenance of the DNS RFCs. The ICANN DNS RFC annotation project provides a forum for collecting community annotations on these RFCs as an aid to understanding for implementers and any interested parties. The annotations displayed here are not the result of the IETF consensus process.
This RFC is included in the DNS RFCs annotation project whose home page is here.