The following is the technical specification of NO Resource Records  as discussed in chapter 6. It was submitted as a independent submission to the IETF DNS Extensions Work Group . The Work Group adopted it is an official work item. This is the second version (not a final version) of the document.
Network Working Group S.A. Josefsson Internet-Draft RSA Security Expires: February 22, 2001 August 24, 2000 Authenticating denial of existence in DNS with minimum disclosure (or; An alternative to DNSSEC NXT records) draft-ietf-dnsext-not-existing-rr-00 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. 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 February 22, 2001. Copyright Notice Copyright (C) The Internet Society (2000). All Rights Reserved. Abstract 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. One solution, the NO record, is presented. The NO record differ from the NXT record by using a cryptographic hash value instead of the domain name. This prevent an adversery from collecting information by "chaining" through a zone. It also remove delegation point concerns in NXT records. The document also describe hash truncation and record merging that reduces storage/network load. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 3 2. Context . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. The NO Resource Record . . . . . . . . . . . . . . . . . . 4 3.1 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2 NO RDATA Format . . . . . . . . . . . . . . . . . . . . . 4 3.3 NO RDATA on-the-wire format example . . . . . . . . . . . 6 3.4 Owner Names . . . . . . . . . . . . . . . . . . . . . . . 6 3.5 Additional Complexity Due To Wildcards . . . . . . . . . . 7 3.6 No Considerations at Delegation Points . . . . . . . . . . 7 3.7 Hash Truncation and Dynamic Updates . . . . . . . . . . . 8 3.8 Reducing Number of Records . . . . . . . . . . . . . . . . 9 3.9 Hash Collisions . . . . . . . . . . . . . . . . . . . . . 9 3.10 Authenticating Denial of NO Records . . . . . . . . . . . 9 3.11 Case Considerations . . . . . . . . . . . . . . . . . . . 10 3.12 Presentation Format . . . . . . . . . . . . . . . . . . . 10 3.13 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.13.1 Adding NO Records to a Zone . . . . . . . . . . . . . . . 10 3.13.2 Simple NO creating entity . . . . . . . . . . . . . . . . 11 3.13.3 Advanced NO creating entity . . . . . . . . . . . . . . . 11 3.13.4 Resolver Query for Non-existing Domain . . . . . . . . . . 11 3.13.5 Resolver Query for Non-existing Type At Existing Domain . 12 4. Security Considerations . . . . . . . . . . . . . . . . . 13 5. IANA Considerations . . . . . . . . . . . . . . . . . . . 13 References . . . . . . . . . . . . . . . . . . . . . . . . 14 Author's Address . . . . . . . . . . . . . . . . . . . . . 14 Full Copyright Statement . . . . . . . . . . . . . . . . . 15 1. Introduction "Domain Name Security Extensions", RFC 2535 , 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 names and/or 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 . Another aspect exist. When DNS is used to store certificates, as described in RFC 2538 , certificates can identify individuals and/or carry authentication information for special purposes. This context has been the motivation for developing this draft. The delegation considerations for NXT records (different RRsets in the parent and child for the same domain) has also been regarded as a flaw of the NXT records. 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. This idea has been extended in this document into allowing (but not requiring) one record to deny existence of several records, and truncating the hash value to the shortest unique prefix to preserve space. 3.2 NO RDATA Format The RDATA for a NO RR consists of one or more fields with the following structure. The structure have the following elements: a zero-terminated list of RR types, a hash length specifier, and a hash value, as shown below. Both the "RR type" list and the "next hash value" fields are of variable width. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | / / owner RR type list / / | +---------------+-----------------------------------------------+ | # hash octets | SHA-1 hash value / +---------------+ / / / +---------------------------------------------------------------+ Replacing the NXT RR "type bit map" field is a variable length list of RR types. Each RR type is 16 bits. As the list is of variable length, a end-of-list indicator is require. End of the list is signalled by a all-zero RR type. Each element is a 2 byte RR type. The list MUST be sorted in RR type order. The change from NXT's bitmap field removes the limit of authenticating only the first 127 RR types. The RR type list indicates what types exist at the previous hash value -- i.e. the first RR type list in the RRdata of a NO record indicate what RR types exist at the domain name that hashes to the owner name of that NO record. The second RR type list, if any, in the RRdata of a NO record indicate what RR types exist at the domain name that hashes the first SHA-1 value in the RRdata. And so on. See below for a complete example of the on-the-wire-format of a NO record with hash truncation and record merging and its interpretation. Length of the hash value field is denoted by the # hash octets fields, it is a unsigned integer ranging from 0 to 255. The meaning of a zero length integer is reserved. The SHA-1 hash value field is a variable length field containing the actual hash value. The NO RRs for a zone SHOULD be automatically calculated and added 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 RR's MUST only be signed by zone level keys . 3.3 NO RDATA on-the-wire format example The following is a example of the on-the-wire-format of a complete NO resource record were hash truncation and record merging is used. It is the on-the-wire format of the NO record in section 184.108.40.206. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | RR type 1 (A) | RR type 0 (end-of-list) | +---------------+-----------------------------------------------+ | 1 hash octet | Hash 0x22 | RR type 2 (NS) | +---------------+---------------+-------------------------------+ | RR type 6 (SOA) | RR type 15 (MX) | +-------------------------------+---------------+---------------+ | RR type 0 (end-of-list) | 1 hash octet | Hash 0x83 | +-------------------------------+---------------+---------------+ | RR type 1 (A) | RR type 0 (end-of-list) | +---------------+-----------------------------------------------+ | 1 hash octet | Hash 0x90 | RR type 1 (A) | +---------------+---------------+-------------------------------+ | RR type 16 (TXT) | RR type 0 (end-of-list) | +---------------+---------------+-------------------------------+ | 1 hash octet | Hash 0x1b | +-------------------------------+ The intepretation here is that the domain that corresponds with the NO owner name ("1b.example.org.", not shown above) have a A record, that the domain that hash to 0x22 (truncated to one octet) have a NS, SOA and MX record, that the domain that hash to 0x83 (truncated to 1 octet) have a A record etc. Note that the last hash value of NO RRdata does not have a RR type list in the same record. 3.4 Owner Names As the previous NO RR format describe, the "next domain name" of NXT records is replaced by its hash value. This removes the possibility of chaining both backwards and forwards through a zone. But without also modifying the owner names of NO records it is still not difficult to chain through a zone. Consider querying a server for (say) "m.example.org", the reply could contain a NO record for "g.example.org", now an adversary can lookup records for "g.example.org", and then issue a query for a domain that would sort (in "the canonical order" described in RFC 2535) just before "g.example.org". Applying the technique over and over again, all records in the zone can still be collected. To prevent this, the owner names of NO records is replaced by its hash value. As DNS places limits on what characters can be used in owner names, the owner name uses a base 16 "hex" encoding . In order to remove the (very small) chance of generated NO record names colliding with existing, "real", domains, all NO records MUST be stored directly in the "_no" domain of the zone. I.e., a zone "example.org." store its NO records as, say, "35a4d1._no.example.org.". 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 complex. In particular, when a non-existent name response is returned, an NO must be returned showing that the exact name 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 No 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 zone. $ORIGIN parent.example.org. @ SOA NS NXT child SOA NS SIG NXT child NS foo NXT next NS SIG NXT next A 127.0.0.2 $ORIGIN child.parent.example.org. @ SOA NS NXT name SOA NS SIG NXT name A 127.0.2.1 NXT child.parent.example.org. With NO records, the parent would deny existance of domains in "_no.parent.example" and the child in "_no.child.parent.example.org". Thus no NO RRset collision occur. 3.7 Hash Truncation and Dynamic Updates Entities that create NO records MAY truncate the hash field. It MUST NOT truncate hash fields so they are no longer unique throughout a zone. Hash truncations MUST only be done to octet offsets. Truncation MUST be such that less significant bits are truncated, i.e. higher-order bits are preserved (see the examples). Zones that are dynamically updated will have to calculate and add NO records on-the-fly. If hash truncation is used, adding a new name to the zone will require updating (and signing) NO records for the conflicting name(s). As this recalculation might be quite inefficient, the use of "shortest unique prefix" truncation in dynamically updated zones is not recomended. However, a truncation to, say, 64 bits might be possible if the administrators are willing to have their software perform costly operations once every ~2^32 update (on average). Since truncation (and also "compression" described in the next section) make it impossible to predict the corresponding NO record given a domain name, resolvers should not ask for a hashed NO record (aaaa._no.example.org. IN NO) for a known domain name if they want to find out what types exist at the domain. Instead, a resolver might ask for NO records on the original name (www.example.org. IN NO). Such records will never exist, and the correct NO record will be returned by the server. To summarize, the behaviour of hash truncation should be configurable in the entity that creates NO records, to accomodate different usage-patterns. If the zone is not intended to be dynamicly updated, the use of hash truncation reduces size and is recomended. 3.8 Reducing Number of Records Entitities that create NO records MAY deny existence for several records per NO record. Entities that create NO records should take care so that each resulting NO record is not "too large". [Comments on this? Should there be a specific limit? It might be left as a DNS Operational consideration] Merging several NO records into one record also place more work on the resolver. Instead of parsing two hash values for each NO record to determine if it's applicaple, a resolver will have to parse several hash values and compare each. The NO RR record consist of one or more RR type list / hash values, described above, and a resolver need to parse the entire record to collect each individual field. I.e., a NO parse algorithm could looke like: read RRs, stop when you read a zero RR type, read hash length indicator, read hash size, if the entire record is read stop, otherwise read RRs, stop when you read a zero RR type, etc.. 3.9 Hash Collisions Hash value collisions are expected not to occur. For SHA-1, the probability that this should happen is 1 out of 2^80 on average. 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 ; SHA-1(one.example.org) = SHA-1(two.example.org) one.example.org. IN A 220.127.116.11 two.example.org. IN A 18.104.22.168 Given that no other RR types exist for neither domain, both "one.example.org" and "two.example.org" would be authenticated not to exist by the same NO record. 3.10 Authenticating Denial of NO Records NO records (together with SIG records) authenticate denial for other types in a zone. Unlike NXT records that re-use the namespace in the zone, NO records are not intended to authenticate denial of other NO records. 3.11 Case Considerations Before calculating SHA-1 hash values, domain names MUST be converted into canonical format as described in RFC 2535. This is to make hash comparisons possible. 3.12 Presentation Format 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 records is printed or NO records are printed by debugging code, they appear as a list of unsigned integers or RR mnemonics, and the hash value in base 16 hex representation  with "0x" prepended (to distinguish it from integer RR codes). The zero RR that terminate the list of RR types, and the hash value length indicator, does not appear. See the next section for examples of printed NO RRs. 3.13 Examples This section contain examples of NO records, using the reserved domain exmaple.org . 3.13.1 Adding NO Records to a Zone Consider the following zone file. $ORIGIN example.org. @ IN SOA ... @ IN NS ns @ IN MX 0 server ns IN A ... www IN A ... sERVEr IN A ... sERVEr IN TXT "text" ; SHA1(example.org.) = 0x222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1 ; SHA1(ns.example.org.) = 0x1b7838c69a66eb50cc215f66ee4554d0c4c940a5 ; SHA1(www.example.org.) = 0x839ebd4386c0b26d81f147421b5b7036e61438cf ; SHA1(server.example.org.) = 0x906a0ad5e604b1905828499dc8672ecb8de73e2f Note that hash values are calculcated on the canonical form. The following two sections describe two valid ways of adding NO records to a zone. 3.13.2 Simple NO creating entity A simple NO creator entity might not implement truncation or provide the possibility to deny more than one records per NO record. In this case, the following would be added to the zone file. $ORIGIN _no.example.org. 1b7838c69a66eb50cc215f66ee4554d0c4c940a5 IN NO A 0x222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1 222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1 IN NO NS SOA MX 0x839ebd4386c0b26d81f147421b5b7036e61438cf 839ebd4386c0b26d81f147421b5b7036e61438cf IN NO A 0x906a0ad5e604b1905828499dc8672ecb8de73e2f 906a0ad5e604b1905828499dc8672ecb8de73e2f IN NO A TXT 0x1b7838c69a66eb50cc215f66ee4554d0c4c940a5 3.13.3 Advanced NO creating entity A more advanced NO creator entity might append the following instead, using both truncation and "compression". $ORIGIN _no.example.org 1b IN NO A 0x22 NS SOA MX 0x83 A 0x90 A TXT 0x1b A Note that this contain 5 hash values while the zone only contain 4 records, the last value in the line above is in fact the first hash value in the zone, closing the circular NO chain. 3.13.4 Resolver Query for Non-existing Domain Consider a client looking up the non-existant domain name "baz.example.org.", using the zone file from the previous section. First, we note the following calculations. SHA-1(baz.example.org.) = 0xd5d0f98783eec6e9943750f35904304bd1a4090e SHA-1(*.example.org.) = 0x7ab3776e3b529eb42467cc5d279c88ec951cf021 A server would reply with an RCODE of NXDOMAIN and the authority section data including the following: ; backwards compatibility example.org. IN SOA ; prove no baz.example.org 906a0ad5e604b1905828499dc8672ecb8de73e2f.example.org. IN NO A TXT 0x1b7838c69a66eb50cc215f66ee4554d0c4c940a5 906a0ad5e604b1905828499dc8672ecb8de73e2f.example.org. IN SIG NO ; prove no *.example.org: 222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1.example.org. IN NO NS SOA MX 0x839ebd4386c0b26d81f147421b5b7036e61438cf 222c7a74bc40e818aa53b3eb0b15cd2350fbb3a1.example.org. 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 "baz.example.org." and verify it is contained inside the interval of any NO record in the authority section. Also, to prove there are no wildcard records for baz.example.org., NO records for possible wildcard expansions are returned. A client should similarily calculate hash values of possible wildcards and compare them to the authority section. Of course, if the zone was generated with the more advanced NO creating entity, only the NO record from the previous section would have to be returned. 3.13.5 Resolver Query for Non-existing Type At Existing Domain Consider a client looking up TXT records for the existing domain "www.example.org.", again, using the same zone file as previous. A server would reply with an authority section like the following: 839ebd4386c0b26d81f147421b5b7036e61438cf.example.org. IN NO A 0x906a0ad5e604b1905828499dc8672ecb8de73e2f 839ebd4386c0b26d81f147421b5b7036e61438cf.example.org. IN SIG NO The resolver verifies the signature and make sure SHA-1("bar.example.org.") hashes correctly. 4. Security Considerations Chaining through all NO records is still technically possible, altough it cannot be used to collect names and/or records in the zone (other than NO records themself). The security of NO record hash values is dependent on the security of the SHA-1 hash functions used. 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 adding any number of bogus records in the zone. The authentication of NO records is provided by DNS SIG records, as specified in RFC 2535. The security considerations of RFC 2535 is not affected by this document, and should also be considered. 5. IANA Considerations The NO RR type number should be selected by the IANA from the normal RR type space. The meaning of a zero hash length value can only be assigned by a standards action. Acknowledgements The idea of encrypting names, that later evolved into just hashing them, was originally proposed by Jonas Holmerin in private discussions about DNS Security. Magnus Nyström proposed truncating the hash values. Thanks to John Linn and Magnus Nyström for comments on a early version of this draft. Olafur Gudmundsson pointed out delegation point issues, suggested the use of a "_no" subdomain, and suggested replacing the type bit map field with a sorted list. From the namedroppers mailing list, I'd like to thank Andrew Draper, Andreas Gustafsson, Peter Koch and Brian Wellington for comments and suggestions. References  Eastlake, D., "Domain Name System Security Extensions", RFC 2535, March 1999.  Eastlake, D. and O. Gudmundsson, "Storing Certificates in the Domain Name System (DNS)", RFC 2538, March 1999.  Eastlake, D. and A. Panitz, "Reserved Top Level DNS Names", RFC 2606, June 1999.  NIST, , "Secure Hash Standard", FIPS PUB 180-1, April 1995.  Massey, D., Lehman, T. and E. Lewis, "DNSSEC Implementation in the CAIRN Testbed.", I.D. draft-ietf-dnsop-dnsseccairn-00.txt, October 1999.  Josefsson, S.A. (editor), "Base 64, 32 and 16 Encodings", I.D. draft-josefsson-base-encoding-00.txt, August 2000.  Wellington, B, "Domain Name System Security (DNSSEC) Signing Authority", I.D. draft-ietf-dnsext-signing-auth-01.txt, May 2000. Author's Address Simon Josefsson RSA Security Arenavägen 29 121 29 Stockholm Sweden Phone: +46 8 7250914 EMail: firstname.lastname@example.org 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 English. 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 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS 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. Acknowledgement Funding for the RFC editor function is currently provided by the Internet Society.