Skip to main content

Derivation of DNS Name Predecessor and Successor
draft-ietf-dnsext-dns-name-p-s-01

The information below is for an old version of the document that is already published as an RFC.
Document Type
This is an older version of an Internet-Draft that was ultimately published as RFC 4471.
Authors Ben Laurie , Geoffrey Sisson
Last updated 2015-10-14 (Latest revision 2005-10-05)
Replaces draft-sisson-dnsext-dns-name-p-s
RFC stream Internet Engineering Task Force (IETF)
Intended RFC status Experimental
Formats
Additional resources Mailing list discussion
Stream WG state (None)
Document shepherd (None)
IESG IESG state Became RFC 4471 (Experimental)
Action Holders
(None)
Consensus boilerplate Unknown
Telechat date (None)
Responsible AD Mark Townsley
Send notices to olaf@nlnetlabs.nl
draft-ietf-dnsext-dns-name-p-s-01
DNS Extensions Working Group                                   G. Sisson
Internet-Draft                                                 B. Laurie
Expires: March 5, 2006                                           Nominet
                                                          September 2005

            Derivation of DNS Name Predecessor and Successor
                   draft-ietf-dnsext-dns-name-p-s-01

Status 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 March 5, 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 March 5, 2006                 [Page 1]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Notational Conventions . . . . . . . . . . . . . . . . . . . .  3
   3.  Derivations  . . . . . . . . . . . . . . . . . . . . . . . . .  4
     3.1.  Absolute Method  . . . . . . . . . . . . . . . . . . . . .  4
       3.1.1.  Derivation of DNS Name Predecessor . . . . . . . . . .  4
       3.1.2.  Derivation of DNS Name Successor . . . . . . . . . . .  5
     3.2.  Modified Method  . . . . . . . . . . . . . . . . . . . . .  5
       3.2.1.  Derivation of DNS Name Predecessor . . . . . . . . . .  6
       3.2.2.  Derivation of DNS Name Successor . . . . . . . . . . .  6
   4.  Notes  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  7
     4.1.  Test for Existence . . . . . . . . . . . . . . . . . . . .  7
     4.2.  Case Considerations  . . . . . . . . . . . . . . . . . . .  7
     4.3.  Choice of Range  . . . . . . . . . . . . . . . . . . . . .  8
     4.4.  Wild Card Considerations . . . . . . . . . . . . . . . . .  8
     4.5.  Possible Modifications . . . . . . . . . . . . . . . . . .  9
       4.5.1.  Restriction of Effective Maximum DNS Name Length . . .  9
       4.5.2.  Use of Modified Method With Zones Containing
               SRV RRs  . . . . . . . . . . . . . . . . . . . . . . .  9
   5.  Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
     5.1.  Examples of Immediate Predecessors Using Absolute
           Method . . . . . . . . . . . . . . . . . . . . . . . . . . 11
     5.2.  Examples of Immediate Successors Using Absolute Method . . 14
     5.3.  Examples of Predecessors Using Modified Method . . . . . . 20
     5.4.  Examples of Successors Using Modified Method . . . . . . . 21
   6.  Security Considerations  . . . . . . . . . . . . . . . . . . . 22
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 22
   8.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 22
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 23
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 23
   Appendix A.  Change History  . . . . . . . . . . . . . . . . . . . 23
     A.1.  Changes from -00 to -01  . . . . . . . . . . . . . . . . . 23
     A.2.  Changes from sisson-02 to ietf-00  . . . . . . . . . . . . 24
     A.3.  Changes from sisson-01 to sisson-02  . . . . . . . . . . . 24
     A.4.  Changes from sisson-00 to sisson-01  . . . . . . . . . . . 24
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 25
   Intellectual Property and Copyright Statements . . . . . . . . . . 26

Sisson & Laurie           Expires March 5, 2006                 [Page 2]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

1.  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 exclusively of owner
       names that contain no more than one label more than the owner
       name of the apex, where the longest possible owner name (i.e. one
       with a maximum length left-most label) would not exceed 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).

Sisson & Laurie           Expires March 5, 2006                 [Page 3]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   P'(N): Predecessor to N (modified method).

   S'(N): Successor to N (modified method).

3.  Derivations

   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.

   The derivations make reference to maximum label length and maximum
   DNS name length; these are defined in Section 3.1 of [RFC1034] to be
   63 and 255 octets respectively.

3.1.  Absolute Method

3.1.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.  (If this condition
       is met, P(N) is the owner name of the apex.)

   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
       of the least significant (left-most) label, skipping any values
       that correspond to uppercase US-ASCII letters, and then append
       the least significant (left-most) 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.

Sisson & Laurie           Expires March 5, 2006                 [Page 4]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

3.1.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 octet 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 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 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.  Unless N is the
       same as the owner name of the zone apex (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), repeat starting
       at step 2.

3.2.  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.

Sisson & Laurie           Expires March 5, 2006                 [Page 5]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   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.

3.2.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.  (If this condition
       is met, P'(N) is the owner name of the apex.)

   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.

3.2.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.

Sisson & Laurie           Expires March 5, 2006                 [Page 6]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   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.

   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.)

4.  Notes

4.1.  Test for Existence

   Before using the result of P(N) or P'(N) as the owner name of an NSEC
   RR in a DNS response, a name server should test to see whether the
   name exists.  If it does, either a standard non-synthesised NSEC RR
   should be used, or the synthesised NSEC RR should reflect the RRset
   types that exist at the NSEC RR's owner name in the Type Bit Map
   field as specified by Section 4.1.2 of [RFC4034].  Implementors will
   likely find it simpler to use a non-synthesised NSEC RR.  For further
   details see Section 2 of [I-D.ietf-dnsext-dnssec-online-signing].

4.2.  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.

   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--;

Sisson & Laurie           Expires March 5, 2006                 [Page 7]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Increment the value of an octet:

      if (octet == '@')       // '@' is just prior to uppercase 'A'
              octet = '[';    // '[' is just after uppercase 'Z'
      else
              octet++;

4.3.  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:

   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 4.4).

   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.

4.4.  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 4.3), 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

Sisson & Laurie           Expires March 5, 2006                 [Page 8]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   owner name of, or in the RDATA of an NSEC RR, it is treated as a
   literal DNS name with no special meaning.

4.5.  Possible Modifications

4.5.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 maximum
   DNS name length agrees with the new contents.

4.5.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.

       This approach would make it possible to enumerate all DNS names
       in the zone containing a first-level label beginning with
       underscore, including all SRV RRs, but this may be of less a
       concern to the zone administrator than incurring the overhead of
       the absolute method or of the following variants of the modified
       method.

   2.  The absolute method could be used for synthesising NSEC RRs for
       all queries where the QNAME contains a leading underscore.

Sisson & Laurie           Expires March 5, 2006                 [Page 9]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

       However this re-introduces the susceptibility of the absolute
       method to denial of service activity, as an attacker could send
       queries for an effectively inexhaustible supply of domain names
       beginning with a leading underscore.

   3.  A variant of the modified method could be used for synthesising
       NSEC RRs for all queries where the QNAME contains a leading
       underscore.  This variant would assume that all predecessors and
       successors to queries where the QNAME contains a leading
       underscore may consist of two labels rather than only one.  This
       introduces a little additional complexity without incurring the
       full increase in response size and computational complexity as
       the absolute method.

   4.  Finally, a variant the modified method which assumes that all
       owner names in the zone consist of one or two labels could be
       used.  However this negates much of the reduction in response
       size of the modified method and may be nearly as computationally
       complex as the absolute method.

5.  Examples

   In the following examples:

      the owner name of the zone apex is "example.com.";

      the range of octet values is 0x00 - 0xff excluding values
      corresponding to uppercase US-ASCII letters; and

      non-printable octet values are expressed as three-digit decimal
      numbers preceded by a backslash (as specified in Section 5.1 of
      [RFC1035]).

Sisson & Laurie           Expires March 5, 2006                [Page 10]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

5.1.  Examples of Immediate Predecessors Using Absolute Method

   Example of typical case:

      P(foo.example.com.) =

           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255.\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255.fon\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255.example.com.

      or, in alternate notation:

           \255{49}.\255{63}.\255{63}.fon\255{60}.example.com.

      where {n} represents the number of repetitions of an octet.

   Example where least significant (left-most) label of DNS name
   consists of a single octet of the minimum sort value:

      P(\000.foo.example.com.) = foo.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 11]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where least significant (right-most) octet of least
   significant (left-most) label has the minimum sort value:

      P(foo\000.example.com.) =

           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255.\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255.\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255.foo.example.com.

      or, in alternate notation:

           \255{45}.\255{63}.\255{63}.\255{63}.foo.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 12]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name contains an octet which must be decremented by
   skipping values corresponding to US-ASCII uppercase letters:

      P(fo\[.example.com.) =

           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255.\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255.fo\@\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255.example.com.

      or, in alternate notation:

           \255{49}.\255{63}.\255{63}.fo\@\255{60}.example.com.

      where {n} represents the number of repetitions of an octet.

Sisson & Laurie           Expires March 5, 2006                [Page 13]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name is the owner name of the zone apex, and
   consequently wraps to the DNS name with the maximum possible sort
   order in the zone:

      P(example.com.) =

           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255.\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255.\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.example.com.

      or, in alternate notation:

           \255{49}.\255{63}.\255{63}.\255{63}.example.com.

5.2.  Examples of Immediate Successors Using Absolute Method

   Example of typical case:

      S(foo.example.com.) = \000.foo.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 14]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name is one octet short of the maximum DNS name
   length:

      N =  fooooooooooooooooooooooooooooooooooooooooooooooo
           .ooooooooooooooooooooooooooooooooooooooooooooooo
           oooooooooooooooo.ooooooooooooooooooooooooooooooo
           oooooooooooooooooooooooooooooooo.ooooooooooooooo
           oooooooooooooooooooooooooooooooooooooooooooooooo.example.com.

      or, in alternate notation:

           fo{47}.o{63}.o{63}.o{63}.example.com.

      S(N) =

           fooooooooooooooooooooooooooooooooooooooooooooooo
           \000.ooooooooooooooooooooooooooooooooooooooooooo
           oooooooooooooooooooo.ooooooooooooooooooooooooooo
           oooooooooooooooooooooooooooooooooooo.ooooooooooo
           oooooooooooooooooooooooooooooooooooooooooooooooo
           oooo.example.com.

      or, in alternate notation:

           fo{47}\000.o{63}.o{63}.o{63}.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 15]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name is the maximum DNS name length:

      N  = fooooooooooooooooooooooooooooooooooooooooooooooo
           o.oooooooooooooooooooooooooooooooooooooooooooooo
           ooooooooooooooooo.oooooooooooooooooooooooooooooo
           ooooooooooooooooooooooooooooooooo.oooooooooooooo
           oooooooooooooooooooooooooooooooooooooooooooooooo
           o.example.com.

      or, in alternate notation:

           fo{48}.o{63}.o{63}.o{63}.example.com.

      S(N) =

           fooooooooooooooooooooooooooooooooooooooooooooooo
           p.oooooooooooooooooooooooooooooooooooooooooooooo
           ooooooooooooooooo.oooooooooooooooooooooooooooooo
           ooooooooooooooooooooooooooooooooo.oooooooooooooo
           oooooooooooooooooooooooooooooooooooooooooooooooo
           o.example.com.

      or, in alternate notation:

           fo{47}p.o{63}.o{63}.o{63}.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 16]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name is the maximum DNS name length and the least
   significant (left-most) label has the maximum sort value:

      N =  \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.ooooooooooooooooooooooooooooooooooooooooooo
           oooooooooooooooooooo.ooooooooooooooooooooooooooo
           oooooooooooooooooooooooooooooooooooo.ooooooooooo
           oooooooooooooooooooooooooooooooooooooooooooooooo
           oooo.example.com.

      or, in alternate notation:

           \255{49}.o{63}.o{63}.o{63}.example.com.

      S(N) =

           oooooooooooooooooooooooooooooooooooooooooooooooo
           oooooooooooooop.oooooooooooooooooooooooooooooooo
           ooooooooooooooooooooooooooooooo.oooooooooooooooo
           ooooooooooooooooooooooooooooooooooooooooooooooo.
           example.com.

      or, in alternate notation:

           o{62}p.o{63}.o{63}.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 17]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name is the maximum DNS name length and the eight
   least significant (right-most) octets of the least significant (left-
   most) label have the maximum sort value:

      N  = foooooooooooooooooooooooooooooooooooooooo\255
           \255\255\255\255\255\255\255.ooooooooooooooooooo
           oooooooooooooooooooooooooooooooooooooooooooo.ooo
           oooooooooooooooooooooooooooooooooooooooooooooooo
           oooooooooooo.ooooooooooooooooooooooooooooooooooo
           oooooooooooooooooooooooooooo.example.com.

      or, in alternate notation:

           fo{40}\255{8}.o{63}.o{63}.o{63}.example.com.

      S(N) =

           fooooooooooooooooooooooooooooooooooooooop.oooooo
           oooooooooooooooooooooooooooooooooooooooooooooooo
           ooooooooo.oooooooooooooooooooooooooooooooooooooo
           ooooooooooooooooooooooooo.oooooooooooooooooooooo
           ooooooooooooooooooooooooooooooooooooooooo.example.com.

      or, in alternate notation:

           fo{39}p.o{63}.o{63}.o{63}.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 18]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name is the maximum DNS name length and contains an
   octet which must be incremented by skipping values corresponding to
   US-ASCII uppercase letters:

      N  = fooooooooooooooooooooooooooooooooooooooooooooooo
           \@.ooooooooooooooooooooooooooooooooooooooooooooo
           oooooooooooooooooo.ooooooooooooooooooooooooooooo
           oooooooooooooooooooooooooooooooooo.ooooooooooooo
           oooooooooooooooooooooooooooooooooooooooooooooooo
           oo.example.com.

      or, in alternate notation:

           fo{47}\@.o{63}.o{63}.o{63}.example.com.

      S(N) =

           fooooooooooooooooooooooooooooooooooooooooooooooo
           \[.ooooooooooooooooooooooooooooooooooooooooooooo
           oooooooooooooooooo.ooooooooooooooooooooooooooooo
           oooooooooooooooooooooooooooooooooo.ooooooooooooo
           oooooooooooooooooooooooooooooooooooooooooooooooo
           oo.example.com.

      or, in alternate notation:

           fo{47}\[.o{63}.o{63}.o{63}.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 19]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name has the maximum possible sort order in the
   zone, and consequently wraps to the owner name of the zone apex:

      N  = \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255.\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255.\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.example.com.

      or, in alternate notation:

           \255{49}.\255{63}.\255{63}.\255{63}.example.com.

      S(N) = example.com.

5.3.  Examples of Predecessors Using Modified Method

   Example of typical case:

      P'(foo.example.com.) =

           fon\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255.example.com.

      or, in alternate notation:

           fon\255{60}.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 20]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where DNS name contains more labels than DNS names in the
   zone:

      P'(bar.foo.example.com.) = foo.example.com.

   Example where least significant (right-most) octet of least
   significant (left-most) label has the minimum sort value:

      P'(foo\000.example.com.) = foo.example.com.

   Example where least significant (left-most) label has the minimum
   sort value:

      P'(\000.example.com.) = example.com.

   Example where DNS name is the owner name of the zone apex, and
   consequently wraps to the DNS name with the maximum possible sort
   order in the zone:

      P'(example.com.) =

           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255.example.com.

      or, in alternate notation:

           \255{63}.example.com.

5.4.  Examples of Successors Using Modified Method

   Example of typical case:

      S'(foo.example.com.) = foo\000.example.com.

   Example where DNS name contains more labels than DNS names in the
   zone:

      S'(bar.foo.example.com.) = foo\000.example.com.

Sisson & Laurie           Expires March 5, 2006                [Page 21]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

   Example where least significant (left-most) label has the maximum
   sort value, and consequently wraps to the owner name of the zone
   apex:

      N  = \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255\255\255\255\255\255\255\255\255\255
           \255\255\255.example.com.

      or, in alternate notation:

           \255{63}.example.com.

      S'(N) = example.com.

6.  Security Considerations

   The derivation of some predecessors/successors requires the testing
   of more conditions than others.  Consequently the effectiveness of a
   denial-of-service attack may be enhanced by sending queries that
   require more conditions to be tested.  The modified method involves
   the testing of fewer conditions than the absolute method and
   consequently is somewhat less susceptible to this exposure.

7.  IANA Considerations

   This document has no IANA actions.

   Note to RFC Editor: This section is included to make it clear during
   pre-publication review that this document has no IANA actions.  It
   may therefore be removed should it be published as an RFC.

8.  Acknowledgments

   The authors would like to thank Sam Weiler, Olaf Kolkman, Olafur
   Gudmundsson and Niall O'Reilly for their review and input.

9.  References

Sisson & Laurie           Expires March 5, 2006                [Page 22]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

9.1.  Normative References

   [RFC1034]  Mockapetris, P., "Domain names - concepts and facilities",
              STD 13, RFC 1034, November 1987.

   [RFC1035]  Mockapetris, P., "Domain names - implementation and
              specification", STD 13, RFC 1035, November 1987.

   [RFC2181]  Elz, R. and R. Bush, "Clarifications to the DNS
              Specification", RFC 2181, July 1997.

   [RFC2782]  Gulbrandsen, A., Vixie, P., and L. Esibov, "A DNS RR for
              specifying the location of services (DNS SRV)", RFC 2782,
              February 2000.

   [RFC4034]  Arends, R., Austein, R., Larson, M., Massey, D., and S.
              Rose, "Resource Records for the DNS Security Extensions",
              RFC 4034, March 2005.

9.2.  Informative References

   [I-D.ietf-dnsext-dnssec-online-signing]
              Ihren, J. and S. Weiler, "Minimally Covering NSEC Records
              and DNSSEC On-line Signing",
              draft-ietf-dnsext-dnssec-online-signing-01 (work in
              progress), May 2005.

   [I-D.ietf-dnsext-dnssec-trans]
              Arends, R., Koch, P., and J. Schlyter, "Evaluating DNSSEC
              Transition Mechanisms",
              draft-ietf-dnsext-dnssec-trans-02 (work in progress),
              February 2005.

Appendix A.  Change History

A.1.  Changes from -00 to -01

   o  Added note advising testing for the pre-existence of owner names
      prior to using synthesised NSEC RRs.

   o  Added explicit reference to [RFC1034] maximum label and DNS name
      lengths.

   o  Made minor clarifications to derivations.

   o  Reorganised derivations section for clarity.

Sisson & Laurie           Expires March 5, 2006                [Page 23]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

A.2.  Changes from sisson-02 to ietf-00

   o  Added notes on use of SRV RRs with modified method.

   o  Changed reference from weiler-dnssec-online-signing to ietf-
      dnsext-dnssec-online-signing.

   o  Changed reference from ietf-dnsext-dnssec-records to [RFC4034].

   o  Miscellaneous minor changes to text.

A.3.  Changes from sisson-01 to sisson-02

   o  Added modified version of derivation (with supporting examples).

   o  Introduced notational conventions N, P(N), S(N), P'(N) and S'(N).

   o  Added clarification to derivations about when processing stops.

   o  Miscellaneous minor changes to text.

A.4.  Changes from sisson-00 to sisson-01

   o  Split step 3 of derivation of DNS name predecessor into two
      distinct steps for clarity.

   o  Added clarifying text and examples related to the requirement to
      avoid uppercase characters when decrementing or incrementing
      octets.

   o  Added optimisation using restriction of effective maximum DNS name
      length.

   o  Changed examples to use decimal rather than octal notation as per
      [RFC1035].

   o  Corrected DNS name length of some examples.

   o  Added reference to weiler-dnssec-online-signing.

   o  Miscellaneous minor changes to text.

Sisson & Laurie           Expires March 5, 2006                [Page 24]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

Authors' Addresses

   Geoffrey Sisson
   Nominet
   Sandford Gate
   Sandy Lane West
   Oxford
   OX4 6LB
   GB

   Phone: +44 1865 332339
   Email: geoff@nominet.org.uk

   Ben Laurie
   Nominet
   17 Perryn Road
   London
   W3 7LR
   GB

   Phone: +44 20 8735 0686
   Email: ben@algroup.co.uk

Sisson & Laurie           Expires March 5, 2006                [Page 25]
Internet-Draft     DNS Name Predecessor and Successor     September 2005

Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.

Disclaimer of Validity

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Copyright Statement

   Copyright (C) The Internet Society (2005).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78, and
   except as set forth therein, the authors retain all their rights.

Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.

Sisson & Laurie           Expires March 5, 2006                [Page 26]