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]