3 Network Working Group B. Laurie
5 Expires: March 2, 2005 R. Loomis
11 Requirements related to DNSSEC Signed Proof of Non-Existence
12 draft-ietf-dnsext-signed-nonexistence-requirements-01
18 This document is an Internet-Draft and is subject to all provisions
19 of section 3 of RFC 3667. By submitting this Internet-Draft, each
20 author represents that any applicable patent or other IPR claims of
21 which he or she is aware have been or will be disclosed, and any of
22 which he or she become aware will be disclosed, in accordance with
26 Internet-Drafts are working documents of the Internet Engineering
27 Task Force (IETF), its areas, and its working groups. Note that
28 other groups may also distribute working documents as
32 Internet-Drafts are draft documents valid for a maximum of six months
33 and may be updated, replaced, or obsoleted by other documents at any
34 time. It is inappropriate to use Internet-Drafts as reference
35 material or to cite them other than as "work in progress."
38 The list of current Internet-Drafts can be accessed at
39 http://www.ietf.org/ietf/1id-abstracts.txt.
42 The list of Internet-Draft Shadow Directories can be accessed at
43 http://www.ietf.org/shadow.html.
46 This Internet-Draft will expire on March 2, 2005.
52 Copyright (C) The Internet Society (2004).
58 DNSSEC-bis uses the NSEC record to provide authenticated denial of
59 existence of RRsets. NSEC also has the side-effect of permitting
60 zone enumeration, even if zone transfers have been forbidden.
61 Because some see this as a problem, this document has been assembled
62 to detail the possible requirements for denial of existence A/K/A
63 signed proof of non-existence.
68 Laurie & Loomis Expires March 2, 2005 [Page 1]
69 Internet-Draft signed-nonexistence-requirements September 2004
76 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
77 2. Non-purposes . . . . . . . . . . . . . . . . . . . . . . . . 3
78 3. Zone Enumeration . . . . . . . . . . . . . . . . . . . . . . 3
79 4. Zone Enumeration II . . . . . . . . . . . . . . . . . . . . 4
80 5. Zone Enumeration III . . . . . . . . . . . . . . . . . . . . 4
81 6. Exposure of Contents . . . . . . . . . . . . . . . . . . . . 4
82 7. Zone Size . . . . . . . . . . . . . . . . . . . . . . . . . 4
83 8. Single Method . . . . . . . . . . . . . . . . . . . . . . . 5
84 9. Empty Non-terminals . . . . . . . . . . . . . . . . . . . . 5
85 10. Prevention of Precomputed Dictionary Attacks . . . . . . . . 6
86 11. DNSSEC-Adoption and Zone-Growth Relationship . . . . . . . . 6
87 12. Non-overlap of denial records with possible zone records . . 7
88 13. Exposure of Private Keys . . . . . . . . . . . . . . . . . . 7
89 14. Minimisation of Zone Signing Cost . . . . . . . . . . . . . 8
90 15. Minimisation of Asymmetry . . . . . . . . . . . . . . . . . 8
91 16. Minimisation of Client Complexity . . . . . . . . . . . . . 8
92 17. Completeness . . . . . . . . . . . . . . . . . . . . . . . . 8
93 18. Purity of Namespace . . . . . . . . . . . . . . . . . . . . 8
94 19. Replay Attacks . . . . . . . . . . . . . . . . . . . . . . . 8
95 20. Compatibility with NSEC . . . . . . . . . . . . . . . . . . 8
96 21. Compatibility with NSEC II . . . . . . . . . . . . . . . . . 9
97 22. Compatibility with NSEC III . . . . . . . . . . . . . . . . 9
98 23. Coexistence with NSEC . . . . . . . . . . . . . . . . . . . 9
99 24. Coexistence with NSEC II . . . . . . . . . . . . . . . . . . 9
100 25. Protocol Design . . . . . . . . . . . . . . . . . . . . . . 9
101 26. Process . . . . . . . . . . . . . . . . . . . . . . . . . . 9
102 27. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 9
103 28. Requirements notation . . . . . . . . . . . . . . . . . . . 9
104 29. Security Considerations . . . . . . . . . . . . . . . . . . 10
105 30. References . . . . . . . . . . . . . . . . . . . . . . . . . 10
106 30.1 Normative References . . . . . . . . . . . . . . . . . . . 10
107 30.2 Informative References . . . . . . . . . . . . . . . . . . 10
108 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 10
109 Intellectual Property and Copyright Statements . . . . . . . 11
126 Laurie & Loomis Expires March 2, 2005 [Page 2]
127 Internet-Draft signed-nonexistence-requirements September 2004
134 NSEC records allow trivial enumeration of zones - a situation that
135 has existed for several years but which has recently been raised as a
136 significant concern for DNSSECbis deployment in several zones.
137 Alternate proposals have been made that make zone enumeration more
138 difficult, and some previous proposals to modify DNSSEC had related
139 requirements/desirements that are relevant to the discussion. In
140 addition the original designs for NSEC/NXT records were based on
141 working group discussions and the choices made were not always
142 documented with context and requirements-- so some of those choices
143 may need to be restated as requirements. Overall, the working group
144 needs to better understand the requirements for denial of existence
145 (and certain other requirements related to DNSSECbis deployment) in
146 order to evaluate the proposals that may replace NSEC.
149 In the remainder of this document, "NSEC++" is used as shorthand for
150 "a denial of existence proof that will replace NSEC". "NSECbis" has
151 also been used as shorthand for this, but we avoid that usage since
152 NSECbis will not be part of DNSSECbis and therefore there might be
159 This document does not currently document the reasons why zone
160 enumeration might be "bad" from a privacy, security, business, or
161 other perspective--except insofar as those reasons result in
162 requirements. Once the list of requirements is complete and vaguely
163 coherent, the trade-offs (reducing zone enumeration will have X cost,
164 while providing Y benefit) may be revisited. The editors of this
165 compendium received inputs on the potential reasons why zone
166 enumeration is bad (and there was significant discussion on the
167 DNSEXT WG mailing list) but that information fell outside the scope
171 Note also that this document does not assume that NSEC *must* be
172 replaced with NSEC++, if the requirements can be met through other
173 methods (e.g., "white lies" with the current NSEC). As is stated
174 above, this document is focused on requirements collection and
175 (ideally) prioritization rather than on the actual implementation.
181 Authenticated denial should not permit trivial zone enumeration.
184 Additional discussion: NSEC (and NXT before it) provide a linked
185 list that could be "walked" to trivially enumerate all the signed
186 records in a zone. This requirement is primarily (though not
191 Laurie & Loomis Expires March 2, 2005 [Page 3]
192 Internet-Draft signed-nonexistence-requirements September 2004
196 exclusively) important for zones that either are delegation-only/
197 -mostly or do not have reverse lookup (PTR) records configured, since
198 enterprises that have PTR records for all A records have already
199 provided a similar capability to enumerate the contents of DNS zones.
205 4. Zone Enumeration II
208 Zone enumeration should be at least as difficult as it would be to
209 effect a dictionary attack using simple DNS queries to do the same in
213 (Editor comment: it is not clear how to measure difficulty in this
214 case. Some examples could be monetary cost, bandwidth, processing
215 power or some combination of these. It has also been suggested that
216 the requirement is that the graph of difficulty of enumeration vs.
217 the fraction of the zone enumerated should be approximately the same
218 shape in the two cases)
224 5. Zone Enumeration III
227 Enumeration of a zone with random contents should computationally
231 Editor comment: this is proposed as a way of evaluating the
232 effectiveness of a proposal rather than as a requirement anyone would
233 actually have in practice.
236 Contributor: Alex Bligh
239 6. Exposure of Contents
242 NSEC++ should not expose any of the contents of the zone (apart from
243 the NSEC++ records themselves, of course).
246 Editor comment: this is a weaker requirement than prevention of
247 enumeration, but certainly any zone that satisfied this requirement
248 would also satisfy the trivial prevention of enumeration requirement.
251 Contributor: Ed Lewis
257 Requirement: NSEC++ should make it possible to take precautions
258 against trivial zone size estimates. Since not all zone owners care
263 Laurie & Loomis Expires March 2, 2005 [Page 4]
264 Internet-Draft signed-nonexistence-requirements September 2004
268 about others estimation of the size of a zone, it is not always
269 necessary to prohibit trivial estimation of the size of the zone but
270 NSEC++ should allow such measures.
273 Additional Discussion: Even with proposals based on obfuscating names
274 with hashes it is trivial to give very good estimates of the number
275 of domains in a certain zone. Just send 10 random queries and look
276 at the range between the two hash values returned in each NSEC++. As
277 hash output can be assumed to follow a rectangular random
278 distribution, using the mean difference between the two values, you
279 can estimate the total number of records. It is probably sufficient
280 to look at even one NSEC++, since the two hash values should follow a
281 (I believe) Poisson distribution.
284 The concern is motivated by some wording remembered from NSEC, which
285 stated that NSEC MUST only be present for existing owner names in the
286 zone, and MUST NOT be present for non-existing owner names. If
287 similar wording were carried over to NSEC++, introducing bogus owner
288 names in the hash chain (an otherwise simple solution to guard
289 against trivial estimates of zone size) wouldn't be allowed.
292 One simple attempt at solving this is to describe in the
293 specifications how zone signer tools can add a number of random
297 Editor's comment: it is interesting that obfuscating names might
298 actually make it easier to estimate zone size.
301 Contributor: Simon Josefsson.
307 Requirement: A single NSEC++ method must be able to carry both
308 old-style denial (i.e. plain labels) and whatever the new style
309 looks like. Having two separate denial methods could result in
310 cornercases where one method can deny the other and vice versa.
313 Additional discussion: This requirement can help -bis folks to a
314 smooth upgrade to -ter. First they'd change the method while the
315 content is the same, then they can change content of the method.
318 Contributor: Roy Arends.
321 9. Empty Non-terminals
324 Requirement: Empty-non-terminals (ENT) should remain empty. In
325 other words, adding NSEC++ records to an existing DNS structure
326 should not cause the creation of NSEC++ records (or related records)
331 Laurie & Loomis Expires March 2, 2005 [Page 5]
332 Internet-Draft signed-nonexistence-requirements September 2004
336 at points that are otherwise ENT.
339 Additional discussion: Currently NSEC complies with ENT requirement:
340 b.example.com NSEC a.c.example.com implies the existence of an ENT
341 with ownername c.example.com. NSEC2 breaks that requirement, since
342 the ownername is entirely hashed causing the structure to disappear.
343 This is why EXIST was introduced. But EXIST causes ENT to be
344 non-empty-terminals. Next to the dissappearance of ENT, it causes
345 (some) overhead since an EXIST record needs a SIG, NSEC2 and
346 SIG(NSEC2). DNSNR honours this requirement by hashing individual
347 labels instead of ownernames. However this causes very long labels.
348 Truncation is a measure against very long ownernames, but that is
349 controversial. There is a fair discussion of the validity of
350 truncation in the DNSNR draft, but that hasn't got proper review yet.
353 Contributor: Roy Arends.
356 (Editor comment: it is not clear to us that an EXIST record needs an
357 NSEC2 record, since it is a special purpose record only used for
361 10. Prevention of Precomputed Dictionary Attacks
364 Requirement: NSEC++ needs to provide a method to reduce the
365 effectiveness of precomputed dictionary attacks.
368 Additional Discussion: Salt is a measure against dictionary attacks.
369 There are other possible measures (such as iterating hashes in
370 NSEC2). The salt needs to be communicated in every response, since
371 it is needed in every verification. Some have suggested to move the
372 salt to a special record instead of the denial record. I think this
373 is not wise. Response size has more priority over zone size. An
374 extra record causes a larger response than a larger existing record.
377 Contributor: Roy Arends.
380 (Editor comment: the current version of NSEC2 also has the salt in
384 11. DNSSEC-Adoption and Zone-Growth Relationship
387 Background: Currently with NSEC, when a delegation centric zone
388 deploys DNSSEC, the zone-size multiplies by a non-trivial factor even
389 when the DNSSEC-adoption rate of the subzones remains low--because
390 each delegation point creates at least one NSEC record and
391 corresponding signature in the parent even if the child is not
398 Laurie & Loomis Expires March 2, 2005 [Page 6]
399 Internet-Draft signed-nonexistence-requirements September 2004
403 Requirements: A delegation-only (or delegation-mostly) zone that is
404 signed but which has no signed child zones should initially need only
405 to add SIG(SOA), DNSKEY, and SIG(DNSKEY) at the apex, along with some
406 minimal set of NSEC++ records to cover zone contents. Further,
407 during the transition of a delegation-only zone from 0% signed
408 children to 100% signed children, the growth in the delegation-only
409 zone should be roughly proportional to the percentage of signed child
413 Additional Discussion: This is why DNSNR has the Authoritative Only
414 bit. This is similar to opt-in for delegations only. This (bit) is
415 currently the only method to help delegation-centric zone cope with
416 zone-growth due to DNSSEC adoption. As an example, A delegation only
417 zone which deploys DNSSEC with the help of this bit, needs to add
418 SIG(SOA), DNSKEY, SIG(DNSKEY), DNSNR, SIG(DNSNR) at the apex. No
422 Contributor: Roy Arends.
425 12. Non-overlap of denial records with possible zone records
428 Requirement: NSEC++ records should in some way be differentiated
429 from regular zone records, so that there is no possibility that a
430 record in the zone could be duplicated by a non-existence proof
434 Additional discussion: This requirement is derived from a discussion
435 on the DNSEXT mailing list related to copyrights and domain names.
436 As was outlined there, one solution is to put NSEC++ records in a
437 separate namespace, e.g.: $ORIGIN co.uk.
438 873bcdba87401b485022b8dcd4190e3e IN NS jim.rfc1035.com ; your
439 delegation 873bcdba87401b485022b8dcd4190e3e._no IN NSEC++ 881345...
446 (Editor comment: One of us still does not see why a conflict
447 matters. Even if there is an apparent conflict or overlap, the
448 "conflicting" NSEC2 name _only_ appears in NSEC2 records, and the
449 other name _never_ appears in NSEC2 records.)
452 13. Exposure of Private Keys
455 Private keys associated with the public keys in the DNS should be
456 exposed as little as possible. It is highly undesirable for private
457 keys to be distributed to nameservers, or to otherwise be available
458 in the run-time environment of nameservers.
464 Laurie & Loomis Expires March 2, 2005 [Page 7]
465 Internet-Draft signed-nonexistence-requirements September 2004
469 Contributors: Nominet, Olaf Kolkman, Ed Lewis
472 14. Minimisation of Zone Signing Cost
475 The additional cost of creating an NSEC++ signed zone should not
476 significantly exceed the cost of creating an ordinary signed zone.
482 15. Minimisation of Asymmetry
485 Nameservers should have to do as little additional work as necessary.
486 More precisely, it is desirable for any increase in cost incurred by
487 the nameservers to be offset by a proportionate increase in cost to
488 DNS `clients', e.g. stub and/or `full-service' resolvers.
494 16. Minimisation of Client Complexity
497 Caching, wildcards, CNAMEs, DNAMEs should continue to work without
498 adding too much complexity at the client side.
501 Contributor: Olaf Kolkman
507 A proof of nonexistence should be possible for all nonexistent data
511 Contributor: Olaf Kolkman
514 18. Purity of Namespace
517 The name space should not be muddied with fake names or data sets.
520 Contributor: Ed Lewis
526 NSEC++ should not allow a replay to be used to deny existence of an
527 RR that actually exists.
530 Contributor: Ed Lewis
533 20. Compatibility with NSEC
536 NSEC++ should not introduce changes incompatible with NSEC.
541 Laurie & Loomis Expires March 2, 2005 [Page 8]
542 Internet-Draft signed-nonexistence-requirements September 2004
546 Contributor: Ed Lewis
549 21. Compatibility with NSEC II
552 NSEC++ should differ from NSEC in a way that is transparent to the
553 resolver or validator.
556 Contributor: Ed Lewis
559 22. Compatibility with NSEC III
562 NSEC++ should differ from NSEC as little as possible whilst achieving
566 Contributor: Alex Bligh
569 23. Coexistence with NSEC
572 NSEC++ should be optional, allowing NSEC to be used instead.
575 Contributor: Ed Lewis, Alex Bligh
578 24. Coexistence with NSEC II
581 NSEC++ should not impose extra work on those content with NSEC.
584 Contributor: Ed Lewis
590 A good security protocol would allow signing the nonexistence of some
591 selected names without revealing anything about other names.
594 Contributor: Dan Bernstein
600 Clearly not all of these requirements can be met. Therefore the next
601 phase of this document will be to either prioritise them or narrow
602 them down to a non-contradictory set, which should then allow us to
603 judge proposals on the basis of their fit.
609 28. Requirements notation
612 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
613 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
618 Laurie & Loomis Expires March 2, 2005 [Page 9]
619 Internet-Draft signed-nonexistence-requirements September 2004
623 document are to be interpreted as described in [RFC2119].
626 29. Security Considerations
629 There are currently no security considerations called out in this
630 draft. There will be security considerations in the choice of which
631 requirements will be implemented, but there are no specific security
632 requirements during the requirements collection process.
638 30.1 Normative References
642 "DNSSECbis Protocol Definitions", BCP XX, RFC XXXX, Some
646 30.2 Informative References
649 [RFC2026] Bradner, S., "The Internet Standards Process -- Revision
650 3", BCP 9, RFC 2026, October 1996.
653 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
654 Requirement Levels", BCP 14, RFC 2119, March 1997.
657 [RFC2418] Bradner, S., "IETF Working Group Guidelines and
658 Procedures", BCP 25, RFC 2418, September 1998.
672 Phone: +44 (20) 8735 0686
673 EMail: ben@algroup.co.uk
678 Science Applications International Corporation
679 7125 Columbia Gateway Drive, Suite 300
684 EMail: gilbert.r.loomis@saic.com
689 Laurie & Loomis Expires March 2, 2005 [Page 10]
690 Internet-Draft signed-nonexistence-requirements September 2004
694 Intellectual Property Statement
697 The IETF takes no position regarding the validity or scope of any
698 Intellectual Property Rights or other rights that might be claimed to
699 pertain to the implementation or use of the technology described in
700 this document or the extent to which any license under such rights
701 might or might not be available; nor does it represent that it has
702 made any independent effort to identify any such rights. Information
703 on the procedures with respect to rights in RFC documents can be
704 found in BCP 78 and BCP 79.
707 Copies of IPR disclosures made to the IETF Secretariat and any
708 assurances of licenses to be made available, or the result of an
709 attempt made to obtain a general license or permission for the use of
710 such proprietary rights by implementers or users of this
711 specification can be obtained from the IETF on-line IPR repository at
712 http://www.ietf.org/ipr.
715 The IETF invites any interested party to bring to its attention any
716 copyrights, patents or patent applications, or other proprietary
717 rights that may cover technology that may be required to implement
718 this standard. Please address the information to the IETF at
723 Disclaimer of Validity
726 This document and the information contained herein are provided on an
727 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
728 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
729 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
730 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
731 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
732 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
739 Copyright (C) The Internet Society (2004). This document is subject
740 to the rights, licenses and restrictions contained in BCP 78, and
741 except as set forth therein, the authors retain all their rights.
748 Funding for the RFC Editor function is currently provided by the
755 Laurie & Loomis Expires March 2, 2005 [Page 11]