Network Working Group                                     S.A. Josefsson
Internet-Draft                                              RSA Security
Expires: January 12, 2001                                  July 14, 2000

   Authenticating denial of existence in DNS with minimum disclosure
               (or; An alternative to DNSSEC NXT records)

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

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

   The list of Internet-Draft Shadow Directories can be accessed at

   This Internet-Draft will expire on January 12, 2001.

Copyright Notice

   Copyright (C) The Internet Society (2000). All Rights Reserved.


   This draft present an alternative to NXT records, used to achieve
   authenticated denial of existence of a domain name, class and type.
   Problems with NXT records, as specified in RFC 2535, are identified,
   and one solution is presented.

Josefsson               Expires January 12, 2001                [Page 1]

Internet-Draft               The NO Record                     July 2000

1. Introduction

   "Domain Name Security Extensions", RFC 2535 [2], specifies several
   extensions to DNS that provides data integrity and authentication.
   Among them is the NXT record, used to achieve authenticated denial
   of existence of domains, and authenticated denial of existence on
   certain class/types on existing domains.

   As a consequence of NXT records it is possible to "chain" through a
   zone secured by DNS security extensions, collecting all records in
   the zone.  This is the main problem that motivated this draft.

2. Context

   There have been arguments that the "chain" problem of NXT records is
   a non-issue.  Often used is the argument that information in DNS is
   public, and if you wish to keep information private, you shouldn't
   publish it in DNS.  This might be true, but nonetheless major
   service providers and companies are restricting access to zone
   transfers.  Also, people have debated whether NXT records should be
   part of DNSSEC at all because of this problem [1].

   Another aspect exist.  When DNS is used to store certificates, as
   described in RFC 2538 [3], certificates can identify individuals
   and/or carry authentication information for special purposes. This
   context has been the motivation for developing this draft.

3. The NO Resource Record

   This section describe the NO Resource Record.

3.1 Idea

   A straight-forward extension to the NXT record that minimize
   disclosure of information is to store a one-way function value
   instead of the actual domain name.  This is similar to NXT records;
   where NXT records secure a interval where no existing domain names
   are to be found, NO records secure a interval where no one-way value
   of existing domain names are to be found.

   The benefit, of course, is that an adversary does not yield any
   useful information from the record.  Specifically, "chaining"
   through a zone to collect all records is no longer possible.

Josefsson               Expires January 12, 2001                [Page 2]

Internet-Draft               The NO Record                     July 2000

3.2 NO RDATA Format

   The RDATA for an NO RR consists of a hash function identifier, a
   hash value and a bit map, as shown below.  Both the "next hash
   value" and the "type bit map" are variable width fields.

                        1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   |   hash alg.   |                                               /
   +---------------+      next hash value                          /
   /                                                               /
   |                                                               /
   /                      type bit map                             /
   /                                                               /

   The hash algorithm identifier indicate the hash algorithm used to
   hash domain names. It is also used to infer the "next hash value"
   field length, besides it's use in verifying the actual hash value.

   The hash value field is a variable length field containing the
   actual hash value.  Interpretation of the data is specific to each
   hash function, see the next section for currently defined hash

   Like the NXT RR type bit map, the NO RR type bit map format
   currently defined is one bit per RR type present for the domain name
   that hash to the owner name of the RDATA.  A one bit indicates that
   at least one RR of that type is present for the owner name.  A zero
   indicates that no such RR is present. All bits not specified because
   they are beyond the end of the bit map are assumed to be zero.  Note
   that bit TBD, for NO, will always be on so the minimum bit map
   length is actually 6 octets. Trailing zero octets are prohibited in
   this format. The first bit represents RR type zero (an illegal type
   which can not be present) and so will be zero in this format.  This
   format is not used if there exists an RR with a type number greater
   than 127.  If the zero bit of the type bit map is a one, it
   indicates that a different format is being used which will always be
   the case if a type number greater than 127 is present.

   The size of the bit map can be inferred from the RDLENGTH and the
   length of the hash value field, that depend on the hash algorithm

   The NO RRs for a zone SHOULD be automatically calculated and added

Josefsson               Expires January 12, 2001                [Page 3]

Internet-Draft               The NO Record                     July 2000

   to the zone when SIGs are added.  The NO RR's TTL SHOULD NOT exceed
   the zone minimum TTL.

   The type number for the NO RR is TBD.

   NO RRs are only signed by zone level keys.

3.3 The Hash Algorithm Identifier

   Hash algorithms should be chosen to minimize collisions and make it
   impractical to infer input given output. Cryptographic hash
   functions are fine.

   This octet is the hash algorithm.  The following values are assigned:

      VALUE     Algorithm

        0       - reserved, see Section 7
        1       MD5, RFC 1321 [4], recommended
        2       SHA-1 [5], MANDATORY
        3       reserved for SHA-2
      4-250     - available, see Section 7
      251-254   private
      255       - reserved, see Section 7

   As noted above, the size of the hash value field is infered from
   this identifier.  For example, SHA-1 produces 160 bit long size.

   If a hash function does not return values of length in multiples of
   octets, the value should be zero-padded to the next octet boundary.

3.4 Owner names

   As the previous NO RR format describe, the "next domain name" field
   is replaced by its hash value. This removes the possibility of
   chaining both backwards and forwards through a zone.

   But it is still not difficult to chain through a zone; consider
   querying a server for (say) "", the reply could contain a
   NO record for "", now an adversary can lookup records for
   "", and then issue a query for a domain that would sort (in
   "the canonical order" described in RFC 2535) just before
   "".  Applying the technique over and over again, all
   records in the zone can still be downloaded.

   To prevent this, the owner names of NO records should also be
   replaced by its hash value.  As DNS places limits on what characters

Josefsson               Expires January 12, 2001                [Page 4]

Internet-Draft               The NO Record                     July 2000

   can be used in owner names, a base-32 encoding is used (see Appendix
   A).  Since DNS domains need to begin with a alphabetic character,
   the string "no-" should be prepended to the base32 value.

3.5 Additional Complexity Due To Wildcards

   Proving that a non-existent name response is correct or that a
   wildcard expansion response is correct makes things a little more

   In particular, when a non-existent name response is returned, an NO
   must be returned showing that the exact name queried did not exist
   and, in general, one or more additional NO need to be returned to
   also prove that there wasn't a wildcard whose expansion should have
   been returned. (There is no need to return multiple copies of the
   same NO.) These NOs, if any, are returned in the authority section
   of the response.

   Furthermore, if a wildcard expansion is returned in a response, in
   general one or more NOs needs to also be returned in the authority
   section to prove that no more specific name (including possibly more
   specific wildcards in the zone) existed on which the response should
   have been based.

3.6 Considerations at Delegation Points

   When NXT records are used to deny existance, there exists a special
   case at delegation points.  Namely, that two distinct RRsets exist
   for the same owner name, one in the parent zone and one in the child

        $ORIGIN parent.example.
        @       SOA
                   NXT     child   SOA NS SIG NXT
        child   NS      foo
                NXT     next    NS SIG NXT
        next    A

        $ORIGIN child.parent.example.
        @       SOA
                NXT     name    SOA NS SIG NXT
        name    A
                NXT     child.parent.example.

   With NO records instead, the "child.parent.example" domain would
   have NO records "no-1234.parent.example" and
   "no-1234.child.parent.example" respectively.  Thus there will not be

Josefsson               Expires January 12, 2001                [Page 5]

Internet-Draft               The NO Record                     July 2000

   two distinct RRsets at delegation points if NO records are used.

3.7 Hash Value Collisions

   Hash value collisions are expected not to occur.  For MD5, the
   probability that this should happen is 1 out of 2^64.

   However, collisions are actually only a problem if the domain names
   producing the same hash value have different sets of existing types.

   Consider the following records

   ; OWH( = OWH(
   ; IN A IN A

   Given that no other RRs exist for neither domain, both ""
   and "" would be authenticated not to exist by the same NO

   However, the (academic) problem of hash collisions can be solved
   completely within the framework of NO records, should the need
   arise, by defining a "hash" algorithm that uses public key
   encryption to encrypt domain names, with the zone's public key.
   Collisions cannot happen, and a resolver can verify the "hash" value
   by resolving the zone's key and performing the encryption.

   This document does not describe such one-way functions, since they
   are not expected to be necessary.

3.8 ASCII presentation

   NO RRs do not appear in original unsigned zone master files since
   they should be derived from the zone as it is being signed.

   If a signed file with NO added is printed or NOs are printed by
   debugging code, they appear as the hash algorithm identifier (see
   below), and the next hash value, and followed by the RR type present
   bits as an unsigned integer or sequence of RR mnemonics.

Josefsson               Expires January 12, 2001                [Page 6]

Internet-Draft               The NO Record                     July 2000

   The hash algorithm field can be represented as either an unsigned
   integer or symbolicly.  The following initial symbols are defined as

           Value  Symbol

           001    MD5
           002    SHA1

   The hash value is represented in base64 [2] and may be divided up
   into any number of white space separated substrings, down to single
   base 64 digits, which are concatenated to obtain the full hash
   value. These substrings can span lines using the standard

Josefsson               Expires January 12, 2001                [Page 7]

Internet-Draft               The NO Record                     July 2000

3.9 Examples

   This section contain examples of NO records.  For readability, all
   base32/base64 encoded hash values are, unless otherwise stated,
   small integers.  Also, the contrived one-way function identifier OWH
   is used.

3.9.1 Adding NO records to a zone

   Consider the following zone file.

        @       IN SOA ...       ; OWH( = 50
        @       IN NS foo        ; OWH( = 50
        foo     IN A ...         ; OWH( = 80
        bar     IN A ...         ; OWH( = 30
        gee     IN A ...         ; OWH( = 60
        gee     IN TXT ...       ; OWH( = 60
        zoo     IN A ...         ; OWH( = 10

   Now, the following NO records would be added to the zone.  A NO
   record for the fictious wildcard name "*" will have to be
   added, unless it's already present in the zone.  Here, assume
   OWH(* = 40.

        no-10   IN NO OWH 30 A
        no-30   IN NO OWH 40 A
        no-40   IN NO OWH 50         ; wildcard domain
        no-50   IN NO OWH 60 SOA NS
        no-60   IN NO OWH 80 A TXT
        no-80   IN NO OWH 10 A

3.9.2 Resolver query for non-existant domain

   Consider a client looking up the non-existant domain name
   "", using the zone file from the previous section.

   Assume OWH( = 17.  A server would reply with an RCODE of
   NXDOMAIN and the authority section data including something like the

Josefsson               Expires January 12, 2001                [Page 8]

Internet-Draft               The NO Record                     July 2000
        IN SOA ...       ; backwards compatibility  IN NO OWH 30 A   ; prove no  IN SIG NO ...  IN NO OWH 50     ; prove no *  IN SIG NO ...

   In order for a client to verify the authenticity of this reply, in
   addition of verifying the SIG record, it will also need to calculate
   the one-way hash of "" and verify it is contained inside
   the interval of 10 ... 30.  Also, to prove there are no wildcard
   records for, NO records for possible wildcard expansions
   are returned.

3.9.3 Resolver query for non-existing type in existing domain

   Consider a client looking up TXT records for "", again,
   using the same zone file as previous.  A server would reply with an
   authority section like the following:  IN NO OWH 40 A  IN SIG NO ...

   The resolver verifies the signature and make sure OWH(
   hash to 30.

Josefsson               Expires January 12, 2001                [Page 9]

Internet-Draft               The NO Record                     July 2000

4. Savings on size of records (further work)

   To reduce the size of NO records, it is possible to use a scheme to
   truncate hash values to the shortest unique (within the zone file
   being generated) prefix value.  If this is done, the size of the
   hash value field can't be infered from RDLENGTH and the hash
   algorithm, and it will be required to introduce a new field in the
   NO RR data format to specify hash field size.

   When NO records are generated for a zone, instead of printing the
   complete hash value field (128 bits with MD5), the generator should
   print to shortest unique prefix in the zone, together with a length
   indicator.  The length should only be truncated into multiples of
   octets, so that standard base64 and base32 code can be used.

   A resolver verifying that domain "" is contained within the
   interval in a NO record, should calculate the hash value, and
   compare it against both hash values in the record to make sure it is
   indeed contained in the interval.  The comparison should be such
   that lack of bits in the owner name hash value is treated as 0's,
   and lack of bits in the RR data hash value is treated as 1's. (Also,
   the SIG record need to be verified.)

   The size of NO records should, with this modification, be a function
   of the zone file size.  An estimate for a zone with 100.000 domains
   would be that the hash value length could be reduced from 128 bits
   (for MD5) or 160 bits (for SHA1) to a mean of about 16-17 bits. (Not
   all NO records in a zone are required to have equal hash field
   length, but in practice it is likely because of properties in
   cryptographic hash functions.)

   It should be noted, however, that the size of even untruncated NO
   records are much lesser than the size of standard SIG and KEY

Josefsson               Expires January 12, 2001               [Page 10]

Internet-Draft               The NO Record                     July 2000

5. Savings on number of records (further work)

   If there are requirements to trade on-line message size for smaller
   number of NO records (say, in a large zone), it would be possible to
   "compress" several contiguous NO records into one, larger, record.
   Imagine the following records.

        no-10   IN NO OWH 30 A 50 SOA NS
        no-50   IN NO OWH 60 A TXT 80 A
        no-80   IN NO OWH 10 A

   The client will then need to perform a binary search within the
   RRdata of the NO record to verify that the queried domain is located
   between two other one-way hash values.

Josefsson               Expires January 12, 2001               [Page 11]

Internet-Draft               The NO Record                     July 2000

6. Security Considerations

   Chaining through all NO records is still technically possible,
   altough it cannot be used for collecting records in the zone.  The
   security is dependent on the security of the one-way functions used.

   Using base32 encoded owner names place an implicit limit on the
   output size of hash algorithms to 300 bits.

   It should be pointed out that given this scheme, it is easy to
   estimate the number of records within a zone, considering hash
   values are supposed to be equally distributed.  This can be foiled
   by computing any number of bogus records in the zone.

   Calculcation of DNS SIG records of NO records, to provide data
   authority, is specified in RFC 2535 and is not affected by this

   The security considerations in RFC 2535 still apply to DNS.

7. IANA Considerations

   The NO RR type number should be selected by the IANA from the normal
   RR type space.

   Hash algorithm numbers 4 through 250 are available for assignment
   should sufficient reason arise.  However, the designation of a new
   algorithm could have a major impact on interoperability and requires
   an IETF Standards Action [RFC 2434].  The existence of the private
   algorithm types 251 through 254 should satisfy most needs for
   private or proprietary algorithms.

   The meaning of the first bit of the NO RR "type bit map", described
   in section 3.2 paragraph 4, being a one can only be assigned by a
   standards action.


   The idea was originally proposed by Jonas Holmerin in private
   discussions about DNS Security.  Magnus Nyström proposed truncating
   the hash fields to reduce record size. Olafur Gudmundsson pointed
   out delegation point issues.

   Thanks to John Linn and Magnus Nyström for comments on a early
   version of this draft.

Josefsson               Expires January 12, 2001               [Page 12]

Internet-Draft               The NO Record                     July 2000


   [1]  Massey, D., Lehman, T. and E. Lewis, "DNSSEC Implementation in
        the CAIRN Testbed.", October 1999.

   [2]  Eastlake, D., "Domain Name System Security Extensions", RFC
        2535, March 1999.

   [3]  Eastlake, D. and O. Gudmundsson, "Storing Certificates in the
        Domain Name System (DNS)", RFC 2538, March 1999.

   [4]  Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April

   [5]  NIST, , "Secure Hash Standard", FIPS PUB 180-1, April 1995.

   [6]  Myers, J., "SASL GSSAPI mechanisms", May 2000.

Author's Address

   Simon Josefsson
   RSA Security
   Arenavägen 29
   Stockholm  121 29

   Phone: +46 8 7250914

Josefsson               Expires January 12, 2001               [Page 13]

Internet-Draft               The NO Record                     July 2000

Appendix A. Base 32 Encoding

   The following description of base32 is due to [6], the padding
   section was updated to fix two typos.

   The Base32 encoding is designed to represent arbitrary sequences of
   octets in a form that needs to be case insensitive but need not be
   humanly readable.

   A 33-character subset of US-ASCII is used, enabling 5 bits to be
   represented per printable character. (The extra 33rd character, "=",
   is used to signify a special processing function.)

   The encoding process represents 40-bit groups of input bits as
   output strings of 8 encoded characters.  Proceeding from left to
   right, a 40-bit input group is formed by concatenating 5 8bit input
   groups.  These 40 bits are then treated as 8 concatenated 5-bit
   groups, each of which is translated into a single digit in the
   base32 alphabet.  When encoding a bit stream via the base32
   encoding, the bit stream must be presumed to be ordered with the
   most-significant-bit first. That is, the first bit in the stream
   will be the high-order bit in the first 8bit byte, and the eighth
   bit will be the low-order bit in the first 8bit byte, and so on.

   Each 5-bit group is used as an index into an array of 32 printable
   characters.  The character referenced by the index is placed in the
   output string.  These characters, identified in Table 1, below, are
   selected from US-ASCII digits and uppercase letters.

                          Table 1: The Base32 Alphabet

           Value Encoding  Value Encoding  Value Encoding  Value Encoding
               0 A             9 J            18 S            27 3
               1 B            10 K            19 T            28 4
               2 C            11 L            20 U            29 5
               3 D            12 M            21 V            30 6
               4 E            13 N            22 W            31 7
               5 F            14 O            23 X
               6 G            15 P            24 Y         (pad) =
               7 H            16 Q            25 Z
               8 I            17 R            26 2

   Special processing is performed if fewer than 40 bits are available
   at the end of the data being encoded.  A full encoding quantum is
   always completed at the end of a body. When fewer than 40 input bits
   are available in an input group, zero bits are added (on the right)
   to form an integral number of 5-bit groups.  Padding at the end of
   the data is performed using the "=" character.  Since all base32

Josefsson               Expires January 12, 2001               [Page 14]

Internet-Draft               The NO Record                     July 2000

   input is an integral number of octets, only the following cases can

   (1) the final quantum of encoding input is an integral multiple of
   40 bits; here, the final unit of encoded output will be an integral
   multiple of 8 characters with no "=" padding,

   (2) the final quantum of encoding input is exactly 8 bits; here, the
   final unit of encoded output will be two characters followed by six
   "=" padding characters,

   (3) the final quantum of encoding input is exactly 16 bits; here,
   the final unit of encoded output will be four characters followed by
   four "=" padding characters,

   (4) the final quantum of encoding input is exactly 24 bits; here,
   the final unit of encoded output will be five characters followed by
   three "=" padding characters, or

   (5) the final quantum of encoding input is exactly 32 bits; here,
   the final unit of encoded output will be seven characters followed
   by one "=" padding character.

   Because it is used only for padding at the end of the data, the
   occurrence of any "=" characters may be taken as evidence that the
   end of the data has been reached (without truncation in transit).
   No such assurance is possible, however, when the number of octets
   transmitted was a multiple of three and no "=" characters are

   Any characters outside of the base32 alphabet are to be ignored in
   base32-encoded data.

Josefsson               Expires January 12, 2001               [Page 15]

Internet-Draft               The NO Record                     July 2000

Full Copyright Statement

   Copyright (C) The Internet Society (2000). All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph
   are included on all such copies and derivative works. However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an


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

Josefsson               Expires January 12, 2001               [Page 16]