DNS Extensions Working Group                                   G. SissonInternet-Draft                                                 B. LaurieExpires: January 11, 2006                                        Nominet                                                           July 10, 2005            Derivation of DNS Name Predecessor and Successor                   draft-ietf-dnsext-dns-name-p-s-00Status of this Memo   By submitting this Internet-Draft, each author represents that any   applicable patent or other IPR claims of which he or she is aware   have been or will be disclosed, and any of which he or she becomes   aware will be disclosed, in accordance with Section 6 of BCP 79.   Internet-Drafts are working documents of the Internet Engineering   Task Force (IETF), its areas, and its working groups.  Note that   other groups may also distribute working documents as Internet-   Drafts.   Internet-Drafts are draft documents valid for a maximum of six months   and may be updated, replaced, or obsoleted by other documents at any   time.  It is inappropriate to use Internet-Drafts as reference   material or to cite them other than as "work in progress."   The list of current Internet-Drafts can be accessed at   http://www.ietf.org/ietf/1id-abstracts.txt.   The list of Internet-Draft Shadow Directories can be accessed at   http://www.ietf.org/shadow.html.   This Internet-Draft will expire on January 11, 2006.Copyright Notice   Copyright (C) The Internet Society (2005).Abstract   This document describes two methods for deriving the canonically-   ordered predecessor and successor of a DNS name.  These methods may   be used for dynamic NSEC resource record synthesis, enabling   security-aware name servers to provide authenticated denial of   existence without disclosing other owner names in a DNSSEC-secured   zone.Sisson & Laurie         Expires January 11, 2006                [Page 1]Internet-Draft     DNS Name Predecessor and Successor          July 2005Table of Contents   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3   2.  Notational Conventions . . . . . . . . . . . . . . . . . . . .  3   3.  Absolute Method  . . . . . . . . . . . . . . . . . . . . . . .  4     3.1.  Derivation of DNS Name Predecessor . . . . . . . . . . . .  4     3.2.  Derivation of DNS Name Successor . . . . . . . . . . . . .  4   4.  Modified Method  . . . . . . . . . . . . . . . . . . . . . . .  5     4.1.  Derivation of DNS Name Predecessor . . . . . . . . . . . .  6     4.2.  Derivation of DNS Name Successor . . . . . . . . . . . . .  6   5.  Notes  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  7     5.1.  Case Considerations  . . . . . . . . . . . . . . . . . . .  7     5.2.  Choice of Range  . . . . . . . . . . . . . . . . . . . . .  7     5.3.  Wild Card Considerations . . . . . . . . . . . . . . . . .  8     5.4.  Possible Modifications . . . . . . . . . . . . . . . . . .  8       5.4.1.  Restriction of Effective Maximum DNS Name Length . . .  8       5.4.2.  Use of Modified Method With Zones Containing               SRV RRs  . . . . . . . . . . . . . . . . . . . . . . .  9   6.  Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 10     6.1.  Examples of Immediate Predecessors Using Absolute           Method . . . . . . . . . . . . . . . . . . . . . . . . . . 10     6.2.  Examples of Immediate Successors Using Absolute Method . . 13     6.3.  Examples of Predecessors Using Modified Method . . . . . . 19     6.4.  Examples of Successors Using Modified Method . . . . . . . 20   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 21   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 21   10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22     10.1. Normative References . . . . . . . . . . . . . . . . . . . 22     10.2. Informative References . . . . . . . . . . . . . . . . . . 22   9.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 21   Appendix A.  Change History  . . . . . . . . . . . . . . . . . . . 22     A.1.  Changes from sisson-02 to ietf-00  . . . . . . . . . . . . 22     A.2.  Changes from sisson-01 to sisson-02  . . . . . . . . . . . 23     A.3.  Changes from sisson-00 to sisson-01  . . . . . . . . . . . 23   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24   Intellectual Property and Copyright Statements . . . . . . . . . . 25Sisson & Laurie         Expires January 11, 2006                [Page 2]Internet-Draft     DNS Name Predecessor and Successor          July 20051.  Introduction   One of the proposals for avoiding the exposure of zone information   during the deployment DNSSEC is dynamic NSEC resource record (RR)   synthesis.  This technique is described in [I-D.ietf-dnsext-dnssec-   trans] and [I-D.ietf-dnsext-dnssec-online-signing], and involves the   generation of NSEC RRs that just span the query name for non-existent   owner names.  In order to do this, the DNS names which would occur   just prior to and just following a given query name must be   calculated in real time, as maintaining a list of all possible owner   names that might occur in a zone would be impracticable.   Section 6.1 of [RFC4034] defines canonical DNS name order.  This   document does not amend or modify this definition.  However, the   derivation of immediate predecessor and successor, while trivial, is   non-obvious.  Accordingly, several methods are described here as an   aid to implementors and a reference to other interested parties.   This document describes two methods:   1.  An ``absolute method'', which returns the immediate predecessor       or successor of a domain name such that no valid DNS name could       exist between that DNS name and the predecessor or successor.   2.  A ``modified method'', which returns a predecessor and successor       which are more economical in size and computation.  This method       is restricted to use with zones consisting only of single-label       owner names where a maximum-length owner name would not result in       a DNS name exceeding the maximum DNS name length.  This is,       however, the type of zone for which the technique of online-       signing is most likely to be used.2.  Notational Conventions   The following notational conventions are used in this document for   economy of expression:   N: An unspecified DNS name.   P(N): Immediate predecessor to N (absolute method).   S(N): Immediate successor to N (absolute method).   P'(N): Predecessor to N (modified method).Sisson & Laurie         Expires January 11, 2006                [Page 3]Internet-Draft     DNS Name Predecessor and Successor          July 2005   S'(N): Successor to N (modified method).3.  Absolute Method   These derivations assume that all uppercase US-ASCII letters in N   have already been replaced by their corresponding lowercase   equivalents.  Unless otherwise specified, processing stops after the   first step in which a condition is met.3.1.  Derivation of DNS Name Predecessor   To derive P(N):   1.  If N is the same as the owner name of the zone apex, prepend N       repeatedly with labels of the maximum length possible consisting       of octets of the maximum sort value (e.g. 0xff) until N is the       maximum length possible; otherwise continue to the next step.   2.  If the least significant (left-most) label of N consists of a       single octet of the minimum sort value (e.g. 0x00), remove that       label; otherwise continue to the next step.   3.  If the least significant (right-most) octet in the least       significant (left-most) label of N is the minimum sort value,       remove the least significant octet and continue with step 5.   4.  Decrement the value of the least significant (right-most) octet,       skipping any values that correspond to uppercase US-ASCII       letters, and then append the label with as many octets as       possible of the maximum sort value.  Continue to the next step.   5.  Prepend N repeatedly with labels of as long a length as possible       consisting of octets of the maximum sort value until N is the       maximum length possible.3.2.  Derivation of DNS Name Successor   To derive S(N):   1.  If N is two or more octets shorter than the maximum DNS name       length, prepend N with a label containing a single octet of the       minimum sort value (e.g. 0x00); otherwise continue to the next       step.   2.  If N is one or more octets shorter than the maximum DNS name       length and the least significant (left-most) label is one or more       octets shorter than the maximum label length, append an octet ofSisson & Laurie         Expires January 11, 2006                [Page 4]Internet-Draft     DNS Name Predecessor and Successor          July 2005       the minimum sort value to the least significant label; otherwise       continue to the next step.   3.  Increment the value of the least significant (right-most) octet       in the least significant (left-most) label that is less than the       maximum sort value (e.g. 0xff), skipping any values that       correspond to uppercase US-ASCII letters, and then remove any       octets to the right of that one.  If all octets in the label are       the maximum sort value, then continue to the next step.   4.  Remove the least significant (left-most) label.  If N is now the       same as the owner name of the zone apex, do nothing.  (This will       occur only if N is the maximum possible name in canonical DNS       name order, and thus has wrapped to the owner name of zone apex.)       Otherwise repeat starting at step 2.4.  Modified Method   This method is for use with zones consisting only of single-label   owner names where an owner name consisting of label of maximum length   would not result in a DNS name which exceeded the maximum DNS name   length.  This method is computationally simpler and returns values   which are more economical in size than the absolute method.  It   differs from the absolute method detailed above in the following   ways:   1.  Step 1 of the derivation P(N) has been omitted as the existence       of the owner name of the zone apex never requires denial.   2.  A new step 1 has been introduced which removes unnecessary       labels.   3.  Step 4 of the derivation P(N) has been omitted as it is only       necessary for zones containing owner names consisting of more       than one label.  This omission generally results in a significant       reduction of the length of derived predecessors.   4.  Step 1 of the derivation S(N) had been omitted as it is only       necessary for zones containing owner names consisting of more       than one label.  This omission results in a tiny reduction of the       length of derived successors, and maintains consistency with the       modification of step 4 of the derivation P(N) described above.   5.  Steps 2 and 4 of the derivation S(N) have been modified to       eliminate checks for maximum DNS name length, as it is an       assumption of this method that no DNS name in the zone can exceed       the maximum DNS name length.Sisson & Laurie         Expires January 11, 2006                [Page 5]Internet-Draft     DNS Name Predecessor and Successor          July 2005   These derivations assume that all uppercase US-ASCII letters in N   have already been replaced by their corresponding lowercase   equivalents.  Unless otherwise specified, processing stops after the   first step in which a condition is met.4.1.  Derivation of DNS Name Predecessor   To derive P'(N):   1.  If N has more labels than the number of labels in the owner name       of the apex + 1, repeatedly remove the least significant (left-       most) label until N has no more labels than the number of labels       in the owner name of the apex + 1; otherwise continue to next       step.   2.  If the least significant (left-most) label of N consists of a       single octet of the minimum sort value (e.g. 0x00), remove that       label; otherwise continue to the next step.   3.  If the least significant (right-most) octet in the least       significant (left-most) label of N is the minimum sort value,       remove the least significant octet.   4.  Decrement the value of the least significant (right-most) octet,       skipping any values which correspond to uppercase US-ASCII       letters, and then append the label with as many octets as       possible of the maximum sort value.4.2.  Derivation of DNS Name Successor   To derive S'(N):   1.  If N has more labels than the number of labels in the owner name       of the apex + 1, repeatedly remove the least significant (left-       most) label until N has no more labels than the number of labels       in the owner name of the apex + 1.  Continue to next step.   2.  If the least significant (left-most) label of N is one or more       octets shorter than the maximum label length, append an octet of       the minimum sort value to the least significant label; otherwise       continue to the next step.   3.  Increment the value of the least significant (right-most) octet       in the least significant (left-most) label that is less than the       maximum sort value (e.g. 0xff), skipping any values which       correspond to uppercase US-ASCII letters, and then remove any       octets to the right of that one.  If all octets in the label are       the maximum sort value, then continue to the next step.Sisson & Laurie         Expires January 11, 2006                [Page 6]Internet-Draft     DNS Name Predecessor and Successor          July 2005   4.  Remove the least significant (left-most) label.  (This will occur       only if the least significant label is the maximum label length       and consists entirely of octets of the maximum sort value, and       thus has wrapped to the owner name of the zone apex.)5.  Notes5.1.  Case Considerations   Section 3.5 of [RFC1034] specifies that "while upper and lower case   letters are allowed in [DNS] names, no significance is attached to   the case".  Additionally, Section 6.1 of [RFC4034] states that when   determining canonical DNS name order, "uppercase US-ASCII letters are   treated as if they were lowercase US-ASCII letters".  Consequently,   values corresponding to US-ASCII uppercase letters must be skipped   when decrementing and incrementing octets in the derivations   described in Section 3.1 and Section 3.2.   The following pseudo-code is illustrative:   Decrement the value of an octet:      if (octet == '[')       // '[' is just after uppercase 'Z'              octet = '@';    // '@' is just prior to uppercase 'A'      else              octet--;   Increment the value of an octet:      if (octet == '@')       // '@' is just prior to uppercase 'A'              octet = '[';    // '[' is just after uppercase 'Z'      else              octet++;5.2.  Choice of Range   [RFC2181] makes the clarification that "any binary string whatever   can be used as the label of any resource record".  Consequently the   minimum sort value may be set as 0x00 and the maximum sort value as   0xff, and the range of possible values will be any DNS name which   contains octets of any value other than those corresponding to   uppercase US-ASCII letters.   However, if all owner names in a zone are in the letter-digit-hyphen,   or LDH, format specified in [RFC1034], it may be desirable to   restrict the range of possible values to DNS names containing only   LDH values.  This has the effect of:Sisson & Laurie         Expires January 11, 2006                [Page 7]Internet-Draft     DNS Name Predecessor and Successor          July 2005   1.  making the output of tools such as `dig' and `nslookup' less       subject to confusion;   2.  minimising the impact that NSEC RRs containing DNS names with       non-LDH values (or non-printable values) might have on faulty DNS       resolver implementations; and   3.  preventing the possibility of results which are wildcard DNS       names (see Section 5.3).   This may be accomplished by using a minimum sort value of 0x1f (US-   ASCII character `-') and a maximum sort value of 0x7a (US-ASCII   character lowercase `z'), and then skipping non-LDH, non-lowercase   values when incrementing or decrementing octets.5.3.  Wild Card Considerations   Neither derivation avoids the possibility that the result may be a   DNS name containing a wildcard label, i.e. a label containing a   single octet with the value 0x2a (US-ASCII character `*').  With   additional tests, wildcard DNS names may be explicitly avoided;   alternatively, if the range of octet values can be restricted to   those corresponding to letter-digit-hyphen, or LDH, characters (see   Section 5.2), such DNS names will not occur.   Note that it is improbable that a result which is a wildcard DNS name   will occur unintentionally; even if one does occur either as the   owner name of, or in the RDATA of an NSEC RR, it is treated as a   literal DNS name with no special meaning.5.4.  Possible Modifications5.4.1.  Restriction of Effective Maximum DNS Name Length   [RFC1034] specifies that "the total number of octets that represent a   [DNS] name (i.e., the sum of all label octets and label lengths) is   limited to 255", including the null (zero-length) label which   represents the root.  For the purpose of deriving predecessors and   successors during NSEC RR synthesis, the maximum DNS name length may   be effectively restricted to the length of the longest DNS name in   the zone.  This will minimise the size of responses containing   synthesised NSEC RRs but, especially in the case of the modified   method, may result in some additional computational complexity.   Note that this modification will have the effect of revealing   information about the longest name in the zone.  Moreover, when the   contents of the zone changes, e.g. during dynamic updates and zone   transfers, care must be taken to ensure that the effective maximumSisson & Laurie         Expires January 11, 2006                [Page 8]Internet-Draft     DNS Name Predecessor and Successor          July 2005   DNS name length agrees with the new contents.5.4.2.  Use of Modified Method With Zones Containing SRV RRs   Normally the modified method cannot be used in zones that contain   SRV RRs [RFC2782], as SRV RRs have owner names which contain multiple   labels.  However the use of SRV RRs can be accommodated by various   techniques.  There are at least four possible ways to do this:   1.  Use conventional NSEC RRs for the region of the zone that       contains first-level labels beginning with the underscore (`_')       character.  For the purposes of generating these NSEC RRs, the       existence of (possibly fictional) ownernames `9{63}' and `a'       could be assumed, providing a lower and upper bound for this       region.  Then all queries where the QNAME doesn't exist but       contains a first-level label beginning with an underscore could       be handled using the normal DNSSEC protocol.