DNSEXT O. Kolkman
Internet-Draft RIPE NCC
Expires: March 21, 2003 J. Ihren
Autonomica
R. Arends
A.R.E.N.D.S.
September 20, 2002
DNSSEC Wildcard optimization
draft-olaf-dnsext-dnssec-wildcard-optimization-00.txt
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 March 21, 2003.
Copyright Notice
Copyright (C) The Internet Society (2002). All Rights Reserved.
Abstract
Secure denial of the existence of wildcards may lead to a large
number of NXT RRs and associated SIG RRs in DNS responses, even in
the common case when wildcards are not present in the zone. This
optimization uses one bit from the NXT type array to signal that
there is no closer wildcard in the zone for a given query name. This
reduces the packet size and the need for executing slow, and
complicated, code paths in common queries. In cases where there are
no wildcard RRs in the zone (i.e. te root zone) only one NXT RR and
Kolkman, et al. Expires March 21, 2003 [Page 1]
Internet-Draft DNSSEC Wildcard optimization September 2002
corresponding SIG is needed for denial of existence of the wildcard.
The key words "MAY","MAY NOT", "MUST", "MUST NOT", "REQUIRED",
"RECOMMENDED", "SHOULD", and "SHOULD NOT" in this document are to be
interpreted as described in RFC2119.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 RFC2535 wildcard processing . . . . . . . . . . . . . . . . 3
1.2 Signaling the existence of a wildcard . . . . . . . . . . . 3
2. DNSSEC Protocol changes . . . . . . . . . . . . . . . . . . 4
2.1 Server responses . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Resolver actions . . . . . . . . . . . . . . . . . . . . . . 4
3. Security considerations . . . . . . . . . . . . . . . . . . 5
4. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 5
References . . . . . . . . . . . . . . . . . . . . . . . . . 5
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 6
A. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 6
A.1 Zone without wildcards . . . . . . . . . . . . . . . . . . . 6
A.2 Zone with wildcards . . . . . . . . . . . . . . . . . . . . 7
A.2.1 Optimized proof . . . . . . . . . . . . . . . . . . . . . . 8
A.2.2 NXDOMAIN with additional proof for no wildcard . . . . . . . 8
A.2.3 Another optimized proof . . . . . . . . . . . . . . . . . . 9
A.2.4 Denial of existence of close match . . . . . . . . . . . . . 9
A.2.5 The NXT dname proving existence of a wildcard . . . . . . . 10
Full Copyright Statement . . . . . . . . . . . . . . . . . . 11
Kolkman, et al. Expires March 21, 2003 [Page 2]
Internet-Draft DNSSEC Wildcard optimization September 2002
1. Introduction
Wildcards make authenticated denial of existence complex. Many zones
do not contain wildcards but still incur a penalty. If the NXT RR
contains a an indication that a wildcard match can not exist then
less DNSSEC related RRs and less computation are needed to
authoritatively deny the existence of a name in the zone.
1.1 RFC2535 wildcard processing
RFC2535 [1] dictates that the non-existence of a match against a
wildcard is proven by a set of number of relevant NXT records. In
practice this will result to at least 2 NXT RRs and corresponding
SIGs being returned. There are cases where the denial of the
existence of wildcards will need many more than 2 NXT RRs. Even in
zones that do not use wildcards this will lead to complex answers for
which the resolvers will need to follow NXT chains and which are hard
to troubleshoot by operators.
1.2 Signaling the existence of a wildcard
The NXT RR, used to the prove the non-existence of data, uses a type
bit-map to track which types are available for a given name. Since a
SIG and a NXT RR are always returned in a DNSSEC response both of
these bits are available for other signaling purposes. We propose to
use the 24th (SIG) bit in the type bitmap to signal if a wildcard is
available in a zone. We refer to this bit as the NTAS bit (NXT type
array sig bit).
If the NTAS bit is set to 0 then the NXT RR signals that there is no
wildcard match possible against the query name, only if the bit is
set to 1 then further processing needs to be done. For zones without
wildcards the NTAS bit will always be set to 0.
The following optimizations are realized:
o Servers and resolvers will only have to execute a slow and
somewhat complicated code paths if wildcard are present in the
zone.
o Packet size of answers reduce in most common cases; for the root
zone the authority section only contains 1 NXT RR with associated
SIGs instead of two NXT RRs with associated SIGs.
o In case of absence of wildcards matches answers will be easier to
interpret by human operators troubleshooting responses;
Kolkman, et al. Expires March 21, 2003 [Page 3]
Internet-Draft DNSSEC Wildcard optimization September 2002
2. DNSSEC Protocol changes
This is an update to the RFC2535 protocol. It is not backwards
compatible.
At zone signing time, when the NXT RRs are generated, the NTAS bit
MUST be set to zero when the owner name has the following property:
there exists a wildcard for the owner name(s) in this zone with the
leftmost label(s) chopped off. In other words, if the owner name of
the NXT RR is label(j).label(j-1).label(j-2) ... label(0) then the
NTAS bit is set to 1 if *.label(i).label(i-1)...label(0) exists for
any i < j.
For all other NXT RRs the NTAS bit is set to 1.
A NXT RR that proves the non-existence of a full match of the QNAME
will also prove that there is no match of the QNAME to any wildcard
that may exist in the zone if the NTAS bit is set to 0.
2.1 Server responses
When queried for a name for which there is no match, i.e. no full
and no wildcard match, in the zone:
o servers MUST return the NXT RR that proves the non-existence of
the query name in the NXDOMAIN response. If there is no match for
a wildcard then the NTAS bit is per definition set to 0 at signing
time and the 1 NXT RR is sufficient (more NXT RRs MAY NOT be
supplied). If the NTAS bit for the NXT RR that proves non-
existence of the queryname is set to 1 then NXT RRs that prove the
non-existence of possible wildcard matches MUST be returned as
well. The proof algorithm conforms to RFC2535.
When queried for a name for which there is a match in the zone:
o If the match is an exact match than no NXT RRs are returned in the
additional section (conforming to RFC2535).
o Servers for zones that contain one or more wildcards MUST return
the NXT RRs that prove the non-existence of the exact match. They
must also provide proof that there is no closer match for the
QNAME than the match returned in the answer section.
2.2 Resolver actions
Resolvers that receive a packet to a given query MUST, in case of a
If the match is a wildcard match then the resolver will need to
Kolkman, et al. Expires March 21, 2003 [Page 4]
Internet-Draft DNSSEC Wildcard optimization September 2002
verify that the exact name does not exist. The NXT RR that supplies
this proof will, per definition, have it's NTAS bit set to 1.
Additional NXT RRs will need to prove that there is no closer match.
(again conforming to RFC2535).
If the response is NXDOMAIN (i.e. no match at all) then the resolver
MUST verify if the NXT RR proves the non-existence of the exact match
in the zone. No further NXT RRs are needed if the NXT RR has it's
NTAS bit set to 0. A DNS packet containing an NXDOMAIN response
accompanied by a NXT RR that has it's NTAS bit set to 1 will need to
contain proof that there are no wildcard matches against the QNAME
(conforming to RFC2535).
The NXT data and the NTAS bit together supply the proof on the non-
existence of a wildcard. There is one situation where the NTAS bit
is set to 0 but the NXT dname proves that there is a wildcard. This
is when the dname itself contains a wildcard. Resolvers that verify
NXDOMAIN replies MUST verify the NXT dname first before the NTAS bit.
Also see example Appendix A.2.5.
Note that the NXT RR might have their NTAS bit set to 0 but may by
virtue of the dname in the RDATA proof that there must be a wildcard
match.
3. Security considerations
The draft provides an optimization for wildcard handling. Resolvers
MUST carefully check for the denial of existence of matches or the
denial of existence of closer matches when an answer is returned and
the NTAS bit is set to 1.
4. Acknowledgments
Daniel Karrenberg for providing a number of comments on earlier
versions of this document.
References
[1] Eastlake, D., "Domain Name System Security Extensions", RFC
2535, March 1999.
Kolkman, et al. Expires March 21, 2003 [Page 5]
Internet-Draft DNSSEC Wildcard optimization September 2002
Authors' Addresses
Olaf M. Kolkman
RIPE NCC
Singel 256
1016 AB Amsterdam
NL
Phone: +31 20 535 4444
EMail: olaf@ripe.net
URI: http://www.ripe.net/
Johan Ihren
Autonomica
Bellmansgatan 30
SE-118 47 Stockholm
SE
EMail: johani@autonomica.se
Roy Arends
A.R.E.N.D.S.
Bankastraat 41-e
1094 EB Amsterdam
NL
Phone: +31206931681
EMail: Roy@logmess.com
Appendix A. Examples
A.1 Zone without wildcards
In the following example zone file there are no wildcards. All NTAS
bits are set to zero (SIG does not occur in the type bitmap.) The
actual SIG RRs and the KEY RRs at the apex are left out for clarity.
Kolkman, et al. Expires March 21, 2003 [Page 6]
Internet-Draft DNSSEC Wildcard optimization September 2002
$ORIGIN example.
@ IN SOA
@ NXT a SOA NXT ; NTAS bit set to 0
a A 10.0.0.1
a NXT a.b A NXT ; NTAS bit set to 0
a.b A 10.0.0.2
a.b NXT a.c A NXT ; NTAS bit set to 0
a.c A 10.0.0.4
a.c NXT a.b.c A NXT ; NTAS bit set to 0
a.b.c A 10.0.0.5
a.b.c NXT f A NXT ; NTAS bit set to 0
f A 10.0.0.6
f NXT @ A NXT ; NTAS bit set to 0
A query for any existing name will return a signed answer without NXT
RRs in the authority section. A query for any non existing name will
only return 1 NXT RR proving the non-existence of the QNAME in the
zone and, by virtue of the NTAS bit bing 0, this is sufficient proof
there is no wildcard.
QNAME= d.b.c.example. QTYPE=A
RCODE=NXDOMAIN
;; Authority
example. SOA
SIG SOA
a.b.c.example. NXT f.example. A NXT
SIG NXT
;; Additional
(... skipped ... )
A.2 Zone with wildcards
In the following example zone file there are two wildcards. Some
NTAS bits are set to 1, others for which there is no wildcard in the
zone if the leftmost labels are chopped off, have there NTAS bit set
to 0. The actual SIG RRs and the KEY RRs at the apex are left out
for clarity. The queries for which a wildcard match is returned will
have the NTAS bit set to 1, there proof for the non-existing closer
match is to be supplied and checked by the resolver.
Kolkman, et al. Expires March 21, 2003 [Page 7]
Internet-Draft DNSSEC Wildcard optimization September 2002
$ORIGIN example.
@ IN SOA
@ NXT a SOA NXT ; NTAS bit set to 0
a A 10.0.0.1
a NXT a.b A NXT ; NTAS bit set to 0
a.b A 10.0.0.2
a.b NXT *.c A NXT ; NTAS bit set to 0
*.c A 10.0.0.3
*.c NXT a.c A NXT SIG ; NTAS bit set to 1
a.c A 10.0.0.4
a.c NXT a.b.c A NXT SIG ; NTAS bit set to 1
a.b.c A 10.0.0.5
a.b.c NXT f A NXT SIG ; NTAS bit set to 1
f A 10.0.0.6
f NXT @ A NXT ; NTAS bit set to 0
A.2.1 Optimized proof
QNAME= c.a.a.example. QTYPE=A
RCODE=NXDOMAIN
;; Authority
example. SOA
SIG SOA
a.example. NXT a.b.example. A NXT SIG ; NTAS bit set to 0
; proves no full match
; and no wildcards that match
; QNAME
SIG NXT
;; Additional
(... skipped ... )
A.2.2 NXDOMAIN with additional proof for no wildcard
The following example contains a NXDOMAIN answer and the proof that
there is no wildcard match.
Kolkman, et al. Expires March 21, 2003 [Page 8]
Internet-Draft DNSSEC Wildcard optimization September 2002
QNAME= e.example. QTYPE=A
RCODE=NXDOMAIN
;; Authority
example.example SOA
SIG SOA
a.b.c.example. NXT f.example. A NXT SIG ; NTAS bit set to 1,
; proves no full match
SIG NXT
a.c.example. NXT a.b.c.example A NXT SIG ; NTAS bit set to 1,
; proves no *.b.c.example.
;; Additional
(... skipped ... )
A.2.3 Another optimized proof
The following example contains a NXDOMAIN answer and the proof that
there is no wildcard match. In this particular case the proof is
optimized because of the NTAS bit on the f NXT RR being set to zero.
QNAME= g.example. QTYPE=A
RCODE=NXDOMAIN
;; Authority
example.example SOA
SIG SOA
f.example. NXT example. A NXT ; NTAS bit set to 0
; proves no full match
;; Additional
(... skipped ... )
A.2.4 Denial of existence of close match
The following example contains an answer with wildcard expansion and
the proof that there is no closer match. This is similar to a
RFC2535 proof of non-existence.
Kolkman, et al. Expires March 21, 2003 [Page 9]
Internet-Draft DNSSEC Wildcard optimization September 2002
QNAME= d.b.c.example. QTYPE=A
RCODE=ANSWER
;; Answer
a.c.example A 10.0.0.3 ; expansion of *.c
SIG A (labelcount=2) ; labelcount proofs wildcard example
;; Authority
example.example SOA
SIG SOA
a.b.c.example. NXT f.example. A NXT SIG ; NTAS bit set to 1,
; proves no full match,
SIG NXT
example. NXT a.example. A NXT ; NTAS bit set to 0
; proves no *.example.
SIG NXT
;; Additional
(... skipped ... )
A.2.5 The NXT dname proving existence of a wildcard
In the zone above the a.b NXT RR has it's NTAS bit set to 0. If one
would query for '#.c' which canonically orders between a.b and *.c
one would get back "a.b NXT *.c". A attacker can use the this NXT RR
in a malformed NXDOMAIN response.
QNAME= #.c.example. QTYPE=A
RCODE=NXDOMAIN ; Black hat answer !!!!
;; Authority
example.example SOA
SIG SOA
a.b.example. NXT *.c.example. A NXT ; NTAS bit set to 0
; but *.c exists
Kolkman, et al. Expires March 21, 2003 [Page 10]
Internet-Draft DNSSEC Wildcard optimization September 2002
Full Copyright Statement
Copyright (C) The Internet Society (2002). 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.
Kolkman, et al. Expires March 21, 2003 [Page 11]