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) draft-jas-dnsext-no-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 January 12, 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, 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 functions. 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 identifier. 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) "m.dom.org", the reply could contain a NO record for "g.dom.org", now an adversary can lookup records for "g.dom.org", and then issue a query for a domain that would sort (in "the canonical order" described in RFC 2535) just before "g.dom.org". 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 complex. 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 zone. $ORIGIN parent.example. @ 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. @ SOA NS NXT name SOA NS SIG NXT name A 127.0.2.1 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(one.dom.org) = OWH(two.dom.org) ; one.dom.org. IN A 1.2.3.4 two.dom.org. IN A 5.6.7.8 Given that no other RRs exist for neither domain, both "one.dom.org" and "two.dom.org" would be authenticated not to exist by the same NO record. 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 indicated: 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 parenthesis. 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. $ORIGIN dom.org @ IN SOA ... ; OWH(dom.org) = 50 @ IN NS foo ; OWH(dom.org) = 50 foo IN A ... ; OWH(foo.dom.org) = 80 bar IN A ... ; OWH(bar.dom.org) = 30 gee IN A ... ; OWH(gee.dom.org) = 60 gee IN TXT ... ; OWH(gee.dom.org) = 60 zoo IN A ... ; OWH(moo.dom.org) = 10 Now, the following NO records would be added to the zone. A NO record for the fictious wildcard name "*.dom.org" will have to be added, unless it's already present in the zone. Here, assume OWH(*.dom.org) = 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 "baz.dom.org", using the zone file from the previous section. Assume OWH(baz.dom.org) = 17. A server would reply with an RCODE of NXDOMAIN and the authority section data including something like the following: Josefsson Expires January 12, 2001 [Page 8] Internet-Draft The NO Record July 2000 dom.org. IN SOA ... ; backwards compatibility no-10.dom.org. IN NO OWH 30 A ; prove no baz.dom.org no-10.dom.org. IN SIG NO ... no-40.dom.org. IN NO OWH 50 ; prove no *.dom.org no-40.dom.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.dom.org" and verify it is contained inside the interval of 10 ... 30. Also, to prove there are no wildcard records for baz.dom.org, 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 "bar.dom.org", again, using the same zone file as previous. A server would reply with an authority section like the following: no-30.dom.org. IN NO OWH 40 A no-30.dom.org. IN SIG NO ... The resolver verifies the signature and make sure OWH(bar.dom.org) 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 "a.dom.org" 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 records. 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 draft. 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. Acknowledgement 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 References [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 1992. [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 Sweden Phone: +46 8 7250914 EMail: sjosefsson@rsasecurity.com 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 arise: (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 present. 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 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. Josefsson Expires January 12, 2001 [Page 16]