Subject: draft-lewis-dns-wildcard-clarify-00.tx and DNSSEC

From: Bob Halley <[email-masked]>
Date: 06 May 2003 20:39:11 -0700

INTRODUCTION

I read draft-lewis-dns-wildcard-clarify-00.txt and was very intrigued
by the idea of using the "closest encloser" in DNSSEC wildcard proofs,
but I didn't think that the draft established a critical thing,
namely:

       How do you know, and (more importantly) *prove* using NXT
       records, what the closest encloser of a given QNAME is?

This paper aims to answer that question.  Because security is
involved, I have tried to be fairly rigorous in my proof below.

SOME BACKGROUND

We'd like to have empty nonterminals provably exist in secure zones.
In other words, if someone has:

	a.b.c    3600    IN    A    10.0.0.1

in their zone, but does not have any records with owner names "c" or
"b.c", we'd like to be able to say (with proof) that "nodes 'c' and
'b.c' exist and yet have no RRs."

We want this because it is the behavior mandated by the nameserver
algorithm in section 4.3.2 of RFC 1034, and because it is regarded by
most as a better, more "natural" behavior than the alternative of
treating such empty nonterminals as being nonexistent.

There are two ways to achieve this.  One way is to instantiate all
the implied empty nonterminals, and then add NXT and SIG(NXT) to them.
This works, but is a burden to the server in storage and computation
resources.  It especially complicates updates, since any deletion of
the last record at a node necessitates a computation to determine
which empty nonterminals are no longer relevant and thus must also be
deleted.

The second way is to infer the existence of the empty nonterminals
from the names of the nodes with real data (i.e. the names in the NXT
chain).

Using this technique, the "deepest existing ancestor" a.k.a. the "most
enclosing name" of any query name Q can be easily found, and proved to
exist.  This allows great efficiency in the wildcard matching
algorithm as well, since only one wildcard possibility exists and must
subsequently be either proven to exist or proven not to exist.  This
is a big improvement on the "empty non-terminals do not exist"
approach, which has many more possible candidate wildcard names which
must be proven not to exist.

DEFINITIONS AND PRELIMINARIES

When we say "subdomain" anywhere below, we mean "is contained
within the domain (in the sense that RFC 1034 describes), or is
equal to the domain".  I.e., we're treating it like "subset" in
mathematics.

X is a "superdomain" of Y iff. Y is a subdomain of X.

A name is an "owner name in zone Z" if it is an owner name, is a
subdomain of the origin of zone Z, and is not glue (or otherwise
beneath a zone cut of zone Z).

A name N is "directly in zone Z" iff. there is some owner name in
Z equal to N.

A name N is "inferred to be in zone Z", if it is not directly in
zone Z, but is a superdomain of some direct name of Z and is
still a subdomain of Z.  I.e., it is an "empty nonterminal"
required to make the path from the zone origin to some name
directly in Z.

A name is "in zone Z" if it is directly in zone Z, or is inferred
to be in zone Z.

Let "<" denote the DNSSEC name order relation.

The "greatest common superdomain" of names A and B, denoted
GCS(A,B), is the greatest (according to the DNSSEC ordering) name
X such that X is a superdomain of both A and B.  I.e. it is
the "deepest common ancestor" of A and B.  GCS(A,B) always
exists, because the root name is a superdomain of all names.

Let Q be a name which is a subdomain of the origin of zone Z.

BOUNDS OF Q IN Z

There is always a name directly in Z, call it "GLB(Q,Z)", which
is the greatest lower bound of Q.  I.e. GLB(Q,Z) <= Q, and for
all N in Z where N <= Q, N <= GLB(Q,Z).

There may or may not be a name directly in Z, call it "LUB(Q,Z)",
which is the least upper bound of Q.  If there is no N directly
in Z such that N >= Q, then there is no LUB(Q,Z).  If there is
some N directly in Z where N >= Q, then there is an LUB(Q,Z) >= Q
such that if N >= Q, then LUB(Q,Z) <= N.

GLB(Q,Z) will have a NXT record which:

	If GLB(Q,Z) = Q, proves that Q is directly in Z

	If GLB(Q,Z) != Q, proves that Q is not directly in Z

The "next domain name" field of this NXT record is the LUB, unless it
is the zone origin (the DNSSEC "end of chain" marker) and Q != the
origin of Z, in which case there is no LUB.

THEOREM 1: Let A, B, and Q be subdomains of Z. Let A <= B and
B <= Q.  Then

	GCS(Q, A) <= GCS(Q, B)

Proof:

Assume GCS(Q, A) > GCS(Q, B).  Then A must have more labels in
common with Q than B, but since A and B are less than Q, that
means that A > B by the DNSSEC ordering, which is a contradiction
since A <= B.

THEOREM 2: Let A, B, and Q be subdomains of Z. Let A >= B and
B >= Q.  Then

	GCS(Q, A) <= GCS(Q, B)

Proof:

Assume GCS(Q, A) > GCS(Q, B).  Then A must have more labels in
common with Q than B, but since A and B are greater than Q, that
means that A < B by the DNSSEC ordering, which is a contradiction
since A >= B.

GREATEST ANCESTOR OF Q IN Z

The "greatest ancestor of Q in Z", denoted GA(Q,Z), is the greatest N
in Z, directly or inferred, such that Q is a subdomain of N.  GA(Q,Z)
is also called the "most enclosing name of Q in Z" or the "deepest
ancestor of Q in Z".

GA(Q,Z) always exists.  Since Q is a subdomain of the origin of Z, and
the origin of Z is "directly in zone Z", so there's always at least
one N in Z such that Q is a subdomain of N.

THEOREM 3: Let Q be a subdomain of the origin of zone Z.  If LUB(Q,Z)
exists, then:

	GA(Q,Z) = the greater of GCS(Q, GLB(Q,Z)) and GCS(Q, LUB(Q,Z))

otherwise

	GA(Q,Z) = GCS(Q, GLB(Q,Z))

Proof:

We can eliminate the trivial case where Q is directly in Z, since in
that case GA(Q,Z) is obviously Q.

For notational convenience, let

	L = GCS(Q, GLB(Q,Z))
	U = GCS(Q, LUB(Q,Z))

Assume L and U both exist.  Assume there is an M in Z that is greater
than both L and U, and is a superdomain of Q.

If M is directly in Z, then M > GLB(Q,Z).  This is because if M were
<= GLB(Q,Z), then GCS(Q,M) would be <= L by Theorem 1.  If M is
directly in Z, it cannot be >= Q since it is a superdomain of Q and M
!= Q.  So, we have GLB(Q,Z) < M < Q, which implies that GLB(Q,Z) is
not the greatest lower bound, which is a contradiction.

If M is inferred to be in Z, then there is some N directly in Z and M
is a superdomain of N.  Either N < Q or N > Q (since Q is not directly
in Z).

If N < Q, then N > GLB(Q,Z).  If N were <= GLB(Q,Z), then the GCS(Q,N)
would be <= L by Theorem 1, but GCS(Q,N) = M, and M > L.  We thus have
a contradiction, since this implies that GLB(Q,Z) is not the greatest
lower bound.

If N > Q, then N < LUB(Q,Z).  If N were >= LUB(Q,Z), then the GCS(Q,N)
would be <= U by Theorem 2, but GCS(Q,N) = M, and M > U.  We thus have
a contradiction, since this implies that LUB(Q,Z) is not the least
upper bound.

Now we deal with the case where U doesn't exist.  Again, assume M in Z
that is greater than L, and is a superdomain of Q.

The cases where M is directly in Z, or where M is inferred and N < Q
are as above.  Now we deal with the case where N > Q.  First we note
that since < is a well-ordering of the names in Z, if there are any
upper bounds to Q in Z, then there must be a least upper bound.  Now,
if N existed, it would be an upper bound of Q in Z, and hence a least
upper bound would have to exist, but there is no least upper bound of
Q in Z by assumption, so we again have a contradiction.

Q.E.D.

CONCLUSION

We've shown how to find the "closest encloser" of any given QNAME by
looking at the QNAME along with the owner name and "next domain name"
field of the NXT record which proves the QNAME doesn't exist.  The
technique works even when the closest encloser is an inferred name.

Knowing the closest encloser lets us do very simple wildcard checking
in secure zones, since the only possible matching wildcard is

      *.<closest encloser>

We simply lookup that name, and if found proceed accordingly, and if
not, we add the NXT record which proves it doesn't exist to the
authority section.

/Bob

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Edward Lewis <[email-masked]>
Date: Wed, 7 May 2003 10:07:02 -0400

>I read draft-lewis-dns-wildcard-clarify-00.txt and was very intrigued

I've given an update (-01-beta) to the chairs (about two weeks ago) 
but haven't heard anything recently.  (They wanted a review from Paul 
Mockapetris.)  I think I also strengthened what you mention as the 
weakness, so if the next version appears to have strengthened, it's a 
coincidence. ;)

I really like the text on the first read.  If nothing else, what you 
have here is well suited to be a section unto itself, for those who 
don't get weak in the knees at the sight of mathematics.  If the text 
I already have written contradicts what's in here, or can be filled 
in from here, that should happen.

One issue, and it's in the vein of "it depends on what is is."

>A name N is "directly in zone Z" iff. there is some owner name in

"In" really is "under the authority of".

Probably more significant is another nagging thought of mine. 
Although you're discussion is right, I had been going to lengths to 
stress that what is pertinent to the specifications is what is 
exchanged in the messages and not what is "in" a zone.  I got this 
idea from the word "synthesis" in 1034 when talking about what wild 
cards.

But, still your perspective is important for the proof, which isn't 
the same as the specification of the protocol.  That makes it a 
valuable addition standing on its own.

I don't see anything I'd change in the text, I certainly wouldn't 
change all the "in"s to the longer phrase.  And I wouldn't try to 
reword it to put it into the protocol perspective.  Perhaps, at most, 
an intro to the text that mentions the shift in perspective.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

Note to pilots: a three-point landing SHOULD NOT include a wing.